
struct Shared : Identifier
{
    Node *occurrences;

    Shared() : occurrences(NULL) {}

    #define loopoccurrences(n)             for(Node * n =  occurrences                ;  n; n =    n ->nextoccurrence)
    #define loopoccurrencesbutfirst(n)     for(Node * n =  occurrences->nextoccurrence;  n; n =    n ->nextoccurrence)
    #define loopoccurrencesindir(n)        for(Node **n = &occurrences                ; *n; n = &(*n)->nextoccurrence)
    #define loopoccurrencesindirremove(n)  for(Node **n = &occurrences                ; *n;                          )
    #define loopoccurrencesindirendless(n) for(Node **n = &occurrences                ;   ; n = &(*n)->nextoccurrence)

    bool IsUsed()   { return occurrences!=NULL; }
    bool IsShared() { return occurrences->nextoccurrence!=NULL; }

    int NumOcc() { int i = 0; loopoccurrences(n) i++; return i; }

    Node *Remove(Node *r)
    {
        loopoccurrencesindir(n) if(*n==r)
        {
            *n = r->nextoccurrence;
            return r;
        }
        ASSERT(0);
        return NULL;
    }

    Node *LCA()                                         // very inefficient if it has to go through many function calls, as it has to calculate the LCA's recursively
    {
        Vector<Node *> lcalist;
        loopoccurrences(n) lcalist.push() = n;

        Vector<Node *> parentsa, parentsb;
        while(lcalist.size()>1)                         // keep merging 2 nodes into an LCA until we have just 1
        {
            lcalist.pop()->CollectParents(parentsa);    // this will call LCA() if it hits a function call
            lcalist.pop()->CollectParents(parentsb);

            Node *lca = NULL;
            while(parentsa.size() && parentsb.size() && parentsa.last()==parentsb.last())
            {
                lca = parentsa.pop();
                parentsb.pop();
            }

            ASSERT(lca);
            lcalist.push() = lca;
            parentsa.setsize_nd(0);
            parentsb.setsize_nd(0);
        }

        return lcalist.pop();
    }

    void Recast(Shared *replacement)
    {
        loopoccurrences(n)
        {
            n->sh = replacement;
            if(!n->nextoccurrence)
            {
                n->nextoccurrence = replacement->occurrences;
                replacement->occurrences = occurrences;
                occurrences = NULL;
                return;
            }
        }
    }
};
