Quickly identify a common ancestor among 2+ categories.

common_ancestors.cpp

// Suppose you have a bunch of category IDs:uint16_t and you need to identify their common ancestor (0 == root category ID)
// Also, suppose `byIndex[]` provides access to a structure that holds the parentId for each category.
// This here implementation will quickly identify the most common ancestor among them.
uint16_t CommonAncestor(const uint16_t *const cids, const uint8_t cnt)
{
        if (cnt < 2)
        {
                // Too few to have any common ancestors
                return 0;
        }
        else
        {
                for (uint32_t i = 1; i != cnt; ++i)
                {
                        const uint16_t *it;
                        uint16_t parentId = byIndex[cids[i]]->parentId;

                        for (;;)
                        {
                                for (it = trailEnd; it != trailStart && *it != parentId; --it)
                                        continue;

                                if (it == trailStart)
                                {
                                        if (parentId == 0)
                                                return 0;
                                        else
                                                parentId = byIndex[parentId]->parentId;
                                }
                                else
                                {
                                        trailEnd = const_cast<uint16_t *>(it);
                                        break;
                                }
                        }
                }

                return *trailEnd;

        }  
        
}