

enum NodeType { T_PLACEHOLDER = 0, T_FUNCTIONCALL, T_INT, T_BUILTINCALL, T_UNPARSED };

struct Node
{
    Node *parent;           // NULL for the program root and UserFunction::body
    UserFunction *fparent;  // NULL for the program root and everything else except UserFunction::body
    Node *children;         // NULL for T_INT, T_PLACEHOLDER and T_UNPARSED
    Node *sibling;          // in list starting from Node::children, NULL for the last child
    Node *nextoccurrence;   // in list starting from Shared::occurrences, only used for T_PLACEHOLDER and T_FUNCTIONCALL
    NodeType type;

    int xs, ys, ox, oy;
    bool vertlayout;

    union
    {
        Identifier *id;      // T_PLACEHOLDER | T_FUNCTIONCALL | T_BUILTINCALL
        Shared *sh;          // T_PLACEHOLDER | T_FUNCTIONCALL
        PlaceHolder *ph;     // T_PLACEHOLDER
        UserFunction *uf;    // T_FUNCTIONCALL
        BuiltinFunction *bf; // T_BUILTINCALL
        Unparsed *up;        // T_UNPARSED
        int val;             // T_INT
    };

    Node(NodeType _t) :
        type(_t),
        parent(NULL), fparent(NULL), children(NULL), sibling(NULL), nextoccurrence(NULL),
        id(NULL),
        xs(0), ys(0), ox(0), oy(0),
        vertlayout(false)
        {}

    Node *SetPH(PlaceHolder *_ph)
    {
        ph = _ph;
        nextoccurrence = _ph->occurrences;
        _ph->occurrences = this;
        return this;
    }

    ~Node()
    {
        DELETEP(children);
        DELETEP(sibling);
        switch(type)
        {
            case T_PLACEHOLDER:
            case T_FUNCTIONCALL:
                if(sh)
                {
                    sh->Remove(this);
                    if(!sh->occurrences)
                    {
                        //if(type==T_PLACEHOLDER) RemovePHFromParents(ph);
                        if(type==T_FUNCTIONCALL) delete sh;     // PHs deleted by the function that owns them
                    }
                }
                break;

            case T_UNPARSED:
                delete up;
                break;
        }
    }
    /*
    void RemovePHFromParents(PlaceHolder *ph)
    {
        if(IsFirstUseOfUserFunction() && uf->RemovePH(ph)) return;

        if(parent) parent->RemovePHFromParents(ph);
        else if(fparent && fparent->occurrences) fparent->occurrences->RemovePHFromParents(ph);
    }
    */

    #define loopchildren(n)             for(Node * n =  children;  n; n =    n ->sibling)
    #define loopchildrenindir(n)        for(Node **n = &children; *n; n = &(*n)->sibling)
    #define loopchildrenindirendless(n) for(Node **n = &children;   ; n = &(*n)->sibling)
    #define loopchildrenindirremove(n)  for(Node **n = &children; *n;                   )
    #define loopnextindir(n)                                         (n = &(*n)->sibling)

    bool IsFirstUseOfUserFunction() { return type==T_FUNCTIONCALL && uf->occurrences==this; }       // easy way to help traverse each node exactly once

    int Depth() { return parent ? 1+parent->Depth() : 0; }
    Node *Parent(int i) { return !i ? this : parent->Parent(i-1); }

    int GetX() { return ox+(parent ? parent->GetX() : 0); }
    int GetY() { return oy+(parent ? parent->GetY() : 0); }

    int NumChildren() { int i = 0; loopchildren(n) i++; return i; }


    Node *GetChild(int i) { loopchildren(n) if(i--==0) return n; return NULL; }

    void CollectParents(Vector<Node *> &v)
    {
        for(Node *p = this; p; p = p->parent) v.push() = p;
        if(v.last()->fparent) v.last()->fparent->LCA()->CollectParents(v);  // if we're at the root of a body, any further "parents" can only be beyond the LCA of all function calls
    }

    int FindPos(Node *fn)
    {
        int i = 0;
        loopchildren(n) if(n==fn) return i; else i++;
        ASSERT(0);
        return -1;
    }

    void FindBestVertical(Node *&best, int &bestwidth)
    {
        loopchildren(n) n->FindBestVertical(best, bestwidth);

        if(vertlayout || xs<100 || NumChildren()<=1) return;

        int best1 = 0, best2 = 0;
        loopchildren(n) if(n->xs>best1) { best2 = best1; best1 = n->xs; } else if(n->xs>best2) best2 = n->xs;

        if(best2>bestwidth && best2>40)
        {
            bestwidth = best2;
            best = this;
        }
    }

    void ResetHorizVert()
    {
        vertlayout = false;
        loopchildren(n) n->ResetHorizVert();
    }

    void ConstrainedLayout(wxDC &dc)
    {
        ResetHorizVert();
        loop(i, 20)
        {
            Layout(dc, !i);
            if(xs<500) break;
            Node *best = NULL;
            int bestwidth = 0;
            FindBestVertical(best, bestwidth);
            if(!best) break;
            best->vertlayout = true;
        }
    }

    int Layout(wxDC &dc, bool dofuns)
    {
        ys = dc.GetCharHeight();
        switch(type)
        {
            case T_INT:
                sys->PickFont(dc, 0, STYLE_FIXED);
                dc.GetTextExtent(wxString::Format(L"%d", val), &xs, &ys);
                break;

            case T_UNPARSED:
                xs = id->Layout(dc);
                if(!xs) xs = 10;
                xs += 4;
                ys += 4;
                break;

            case T_PLACEHOLDER:
                xs = id->Layout(dc);
                break;

            case T_FUNCTIONCALL:
                id->Layout(dc);
                if(dofuns && IsFirstUseOfUserFunction())
                {
                    DisplayedSubtree &dst = sys->fundisplaylist.push();
                    dst.uf = uf;
                    uf->body->ConstrainedLayout(dc);
                    uf->Layout(dc);
                }
            case T_BUILTINCALL:
                xs = id->xs;
                xs += sys->bf_openpar.xs;
                if(vertlayout)
                {
                    int maxxs = 0;
                    ys = 0;
                    loopchildren(n)
                    {
                        n->ox = xs;
                        n->oy = ys;
                        n->Layout(dc, dofuns);
                        maxxs = max(maxxs, n->xs);
                        ys += n->ys;
                    }
                    xs += maxxs;
                }
                else
                {
                    loopchildren(n)
                    {
                        n->ox = xs;
                        xs += n->Layout(dc, dofuns);
                        if(n->sibling) xs += sys->bf_comma.xs;
                        ys = max(ys, n->ys);
                    }
                    loopchildren(n)
                    {
                        n->oy = (ys-n->ys)/2;
                    }
                }
                xs += sys->bf_closepar.xs;
                break;
        }
        return xs;
    }

    int Render(wxDC &dc, int x, int y)//, int yspace = 0)
    {
        //if(yspace) y += (yspace-ys)/2;

        switch(type)
        {
            case T_INT:
                sys->PickFont(dc, 0, STYLE_FIXED);
                dc.DrawText(wxString::Format(L"%d", val), x, y);
                break;

            case T_PLACEHOLDER:
                ph->Render(dc, x, y, ys);
                break;

            case T_UNPARSED:
                up->Render(dc, x, y, xs, ys);
                break;

            case T_FUNCTIONCALL:
            case T_BUILTINCALL:
                id->Render(dc, x, y, ys);
                //if(vertlayout)
                {
                    dc.SetPen(*wxBLACK_PEN);
                    dc.DrawEllipticArc(x+id->xs+4, y, sys->bf_openpar.xs, ys, 110, 250);
                }
                //else sys->bf_openpar.Render(dc, x+id->xs, y, ys);
                loopchildren(n)
                {
                    n->Render(dc, x+n->ox, y+n->oy);
                    if(!vertlayout && n->sibling) sys->bf_comma.Render(dc, x+n->ox+n->xs, y, ys);
                }
                //if(vertlayout)
                {
                    dc.SetPen(*wxBLACK_PEN);
                    dc.DrawEllipticArc(x+xs-sys->bf_closepar.xs-4, y, sys->bf_closepar.xs, ys, -70, 70);
                }
                //else sys->bf_closepar.Render(dc, x+xs-sys->bf_closepar.xs, y, ys);
                break;
        }
        return xs;
    }

    bool FindXY(wxDC &dc, int x, int y, Selection &s)
    {
        if(x<0 || y<0 || x>=xs || y>=ys) return false;

        s.n = this;

        switch(type)
        {
            case T_FUNCTIONCALL:
            case T_BUILTINCALL:
                #define checkthin(name, xstart, loc) if(x>=xstart && x<(xstart)+sys->name.xs) { s.start = loc; s.width = 0; return true; }

                checkthin(bf_openpar, id->xs, 0);

                int i = 0;
                loopchildren(n)
                {
                    if(n->FindXY(dc, x-n->ox, y-n->oy, s))
                    {
                        if(s.width) s.start = i;
                        return true;
                    }
                    if(!vertlayout && n->sibling) { checkthin(bf_comma, n->ox+n->xs, i+1); };
                    i++;
                }
                checkthin(bf_closepar, xs-sys->bf_closepar.xs, i);
                break;
        }

        return true;
    }

    Node *Replace(Node *from, Node *to)
    {
        loopchildrenindir(n) if(*n==from) return to->ReplaceIn(n, this);
        ASSERT(0);
        return NULL;
    }

    Node *ReplaceIn(Node **n, Node *_p)                         // *n gets its current content replaced by this
    {
        Node *r = *n;
        sibling = r->sibling;
        parent = _p;
        r->sibling = NULL;
        r->parent = NULL;
        *n = this;
        return r;
    }

    Node *ReplaceWith(Node *with, UserFunction *fparent)
    {
        if(parent)                              // regular child replacement
        {
            parent->Replace(this, with);
        }
        else if(fparent)                        // replacing the root of a function body
        {
            fparent->body = with;
            with->fparent = fparent;
        }
        else                                    // we are replacing the root of the program!
        {
            return with;
        }
        return NULL;
    }

    bool HasOccurrencesOf(PlaceHolder *phlist)
    {
        loopchildren(n) if(n->HasOccurrencesOf(phlist)) return true;

        if(IsFirstUseOfUserFunction()) return uf->body->HasOccurrencesOf(phlist);

        if(type==T_PLACEHOLDER)
        {
            for(; phlist; phlist = phlist->sibling) if(phlist==ph) return true;
        }

        return false;
    }

    UserFunction *FindFunction(wxString &name)
    {
        loopchildren(n)
        {
            UserFunction *uf = n->FindFunction(name);
            if(uf) return uf;
        }

        if(IsFirstUseOfUserFunction())
        {
            if(uf->name==name) return uf;
            return uf->body->FindFunction(name);
        }

        return NULL;
    }

    Node *IterSame(Node *root)
    {
        ASSERT(parent || (fparent && fparent->body==this) || this==root);                // try to catch problems from elsewhere early

        if(type==T_PLACEHOLDER) return NULL;                    // if we'd create placeholders for placeholders..

        PlaceHolder *newph = NULL;
        ASSERT(!root->FindSame(this, newph));                   // root can't be equal to this

        if(newph)                                               // we found 2 or more that match, all but this node have already been replaced
        {
            return (new Node(T_PLACEHOLDER))->SetPH(newph);
        }
        else
        {
            loopchildrenindir(n)
            {
                Node *rep = (*n)->IterSame(root);
                if(rep)
                {
                    rep->ReplaceIn(n, this);                    // replace this child, which completes all matches for this placeholder
                    rep->ph->CreateFunction2b();                // make a function out of whatever LCA dominates all these occurrences of the PH
                }
            }
            if(IsFirstUseOfUserFunction())
            {
                ASSERT(!uf->body->IterSame(root));
                root->FindSameUF(uf);
            }
            return NULL;
        }
    }

    Node *FindSame(Node *tofind, PlaceHolder *&ph)
    {
        if(this==tofind) return NULL;

        if(Equal(*tofind))
        {
            if(!ph)
            {
                ph = new PlaceHolder();
                ph->currentvalue = tofind;                      // temp storage for the shared value until we create the function
            }
            return (new Node(T_PLACEHOLDER))->SetPH(ph);
        }

        if(IsFirstUseOfUserFunction())
        {
            Node *rep = uf->body->FindSame(tofind, ph);
            if(rep)
            {
                delete uf->body;
                uf->body = rep;
                uf->body->fparent = uf;
            }
        }

        loopchildrenindir(n)
        {
            Node *rep = (*n)->FindSame(tofind, ph);             // if rep!=NULL, has been returned from the new PH above
            if(rep)
            {
                delete rep->ReplaceIn(n, this);
            }
        }

        return NULL;
    }

    void FindSameUF(UserFunction *tofind)
    {
        loopchildren(n) n->FindSameUF(tofind);

        if(IsFirstUseOfUserFunction())
        {
            if(uf==tofind) return;

            if(uf->Equal(tofind))
            {
                uf->MergeInto(tofind);
                sys->codechanged = true;
                return;
            }

            uf->body->FindSameUF(tofind);
        }
    }

    bool FindNodeNoFN(Node *tofind)
    {
        if(this==tofind) return true;
        loopchildren(n) if(n->FindNodeNoFN(tofind)) return true;
        return false;
    }

    static Node *Remove(Node **n)
    {
        Node *r = *n;
        *n = r->sibling;
        r->sibling = NULL;
        return r;
    }

    Node *RemoveNthChild(int pos)
    {
        int i = 0;
        loopchildrenindir(n) if(i++==pos) return Remove(n);
        return NULL;
    }

    bool Equal(Node &o, PlaceHolder *thislist = NULL, PlaceHolder *olist = NULL)
    {
        if(type!=o.type) return false;

        Node *on = o.children;
        loopchildren(n)
        {
            if(!on || !n->Equal(*on, thislist, olist)) return false;
            on = on->sibling;
        }
        if(on) return false;

        switch(type)
        {
            case T_INT:
                return val==o.val;

            case T_UNPARSED:
                return up->name==o.up->name;

            case T_PLACEHOLDER:
                if(thislist && olist)
                {
                    int pos1 = thislist->FindPos(ph);
                    if(pos1>=0 && pos1==olist->FindPos(o.ph)) return true;
                }
            case T_BUILTINCALL:
            case T_FUNCTIONCALL:
                return id==o.id;

            default:
                return true;
        }
    }

    void InsertAt(Node *newchild, int pos)
    {
        int i = 0;
        loopchildrenindirendless(n)
            if(i++==pos)
            {
                newchild->sibling = *n;
                *n = newchild;
                newchild->parent = this;
                return;
            }
            else
                ASSERT(*n);
    }

    void IterContexts()
    {
        if(type==T_PLACEHOLDER)
        {
            ph->IterContexts();     // call this for every occurrence, because PH may occur in different contexts
        }
        else
        {
            loopchildren(n) n->IterContexts();

            if(IsFirstUseOfUserFunction()) uf->body->IterContexts();
        }
    }

    Node *RemoveAndReparent(PlaceHolder *toremove, Node *newparent, int pos)
    {
        Node *ret = NULL;
        int i = 0;
        loopchildrenindirremove(n)
        {
            Node *r = *n;
            r->parent = newparent;
            if(i++==pos && r->type==T_PLACEHOLDER && r->ph==toremove)
            {
                ret = Remove(n);
            }
            else
            {
                loopnextindir(n);
            }
        }
        newparent->children = children;
        children = NULL;
        ASSERT(ret);
        return ret;
    }

    PlaceHolder *CreatePHs(Node **dest, Node *parent)
    {
        PlaceHolder *ph = new PlaceHolder();
        Node *phn = new Node(T_PLACEHOLDER);
        phn->ph = ph;
        phn->parent = parent;
        ph->occurrences = phn;
        *dest = phn;
        if(sibling) ph->sibling = sibling->CreatePHs(&phn->sibling, parent);
        return ph;
    }

    void FunctionMerger()
    {
        loopchildren(n) n->FunctionMerger();

        if(IsFirstUseOfUserFunction()) uf->FunctionMerger();
    }

    Node *Inliner()
    {
        loopchildrenindir(n)
        {
            Node *rep = (*n)->Inliner();
            if(rep)
            {
                delete rep->ReplaceIn(n, this);
            }
        }

        if(type==T_FUNCTIONCALL)
        {
            if(!uf->IsShared() && uf->NumPHs()==NumChildren()) uf->InlineSingleUsePHs(this);
            if(IsFirstUseOfUserFunction()) uf->InlineUnusedAndMappedPHs();

            if(uf->phlist==NULL && !uf->IsShared())             // inline entire function if empty from the two refactorings above
            {                                                   // shared functions will first be shared by 2b, and can then be inlined here on the next pass
                Node *body = uf->body;
                uf->body = NULL;
                body->fparent = NULL;
                return body;
            }

            if(IsFirstUseOfUserFunction())
            {
                Node *rep = uf->body->Inliner();
                if(rep)
                {
                    delete uf->body;
                    uf->body = rep;
                    uf->body->fparent = uf;
                }

                if(uf->body->PHCall(uf->NumPHs()))
                {
                    uf->InlineOverAbstract();       // deletes itself
                    sys->codechanged = true;
                }
            }

        }

        return NULL;
    }

    bool PHCall(int numphs)   // see if function maps to a call of PHs only
    {
        if(type!=T_FUNCTIONCALL || uf->NumPHs()!=numphs || NumChildren()!=numphs) return false;
        loopchildren(n) if(n->type!=T_PLACEHOLDER || !n->ph->IsUsed() || n->ph->IsShared()) return false;
        return true;
    }

};

