/*
  3001941958 <- last update (yymmddhh'')
     _____________________________________________________________
    /                                                             \
    | Module:       list.cpp - code of explib's list classes
    \_____________________________________________________________/

    Description:    this creates the code for the lists of the
                    expansion library.

    Refers to:      list.h
    Used by:        everywhere
    Uses:           list.h

    Contents:
        see list.h

    Local Terminology:

        Abbrev. Meaning
        ------- ------------------------
        ...     ...


    Developers: ID: Name:
    =========== --- -----
                JTH Juergen Thumm
  _____________________________________/VERSION HISTORY\____________________
 /Date_ Version Who What____________________________________________________\
 yymmdd ------- --- ---------------------------------------------------------
 930823 0.80.0  JTH split .h to .h and .cpp, added this header.
 930824 0.80.1      ListHead.addfront()
 940129 0.80.2      ListHead.deleteall()
 940130             ListHead.deleteall() fixed; should now be safe
 941215             LNode::next/prev,LHead::first/last: commented out
                    the code, made it implicitely inline -> .h
 950503             ifndef ZOTH added.
*/

#   include "expdef.h"
#   include "explib.h"
#   include "list.h"
//# include "display.h"

//  ModInit(list_o);

// the testadr(x) macro will cause a very detailed error message
// and program termination if x does not belong to allocated user memory.

#ifndef NO_MEMTRACK
ListNode* ListNode::next() const
{
    if(succ)    testadr(succ);

    return  succ;
}

ListNode* ListNode::prev() const
{
    if(pred)    testadr(pred);

    return  pred;
}
#endif

rcode ListHead::checkup()
{
#ifndef NO_MEMTRACK
    // if there's any corrupted list node, the following
    // loop will provoce an error (and exit program):

    for(ListNode* ln=first(); ln; ln=ln->next());

    // maybe nlast is illegal?

    ln  = last();
#endif

    return  OK;
}

ListHead::ListHead()
{   nfirst=nlast=0; }   // checkpoint ain't necessary here

#ifndef NO_MEMTRACK
ListNode* ListHead::first() const
{
    if(nfirst)  testadr(nfirst);

    return nfirst;
}

ListNode* ListHead::last() const
{
    if(nlast)   testadr(nlast);

    return nlast;
}
#endif

//  ----------- adding -------------

void ListHead::rawadd(ListNode* nd)
{_
 ListNode *n2=0,*n3;

    // yet empty list?

    if(!nfirst)
    {   nfirst=nlast=nd; nd->succ=nd->pred=0; return;   }

    if(!n2)
    {
        // append node at end of list:

        n2 = nlast;
        n2->succ    = nd;
         nd->pred   = n2;
         nd->succ   = 0;
        nlast       = nd;
    }
}

void ListHead::add(ListNode* nd)
{_
    // trying to add an illegal node?

    if(!nd || testadr(nd))
    {
        perr("ListHead %lx: try to add node with illegal adress (%lx)",
            this, nd);

        exit(1);
    }

    rawadd(nd);
}

void ListHead::rawaddfront(ListNode* nd)
{_
 ListNode *n2=0,*n3;

    // yet empty list?

    if(!nfirst)
    {   nfirst=nlast=nd; nd->succ=nd->pred=0; return;   }

    // make node new front of list:

    n2 = nfirst;
    n2->pred    = nd;
     nd->pred   = 0;
     nd->succ   = n2;
    nfirst      = nd;
}

void ListHead::addfront(ListNode* nd)
{_
    // trying to add an illegal node?

    if(!nd || testadr(nd))
    {
        perr("ListHead %lx: try to add node with illegal adress (%lx)",
            this, nd);

        exit(1);
    }

    rawaddfront(nd);
}

//  ------------ inserting ------------

void ListHead::rawinsert(ListNode *aft, ListNode *nd)
{_
 ListNode *suc = aft->succ; // maybe 0

    aft->succ   = nd;

    nd->pred    = aft;
    nd->succ    = suc;

    if(suc)
     suc->pred  = nd;
    else
        nlast   = nd;
}

void ListHead::insert(ListNode *aft, ListNode *nd)
{_
    // handling with illegal nodes?

    if(!nd || testadr(nd))
    {
        perr("try to insert illegal node %lx after %lx", nd, aft);
        exit(1);
    }

    if(!aft || testadr(aft))
    {
        perr("try to insert node %lx after illegal node %lx", nd, aft);
        exit(1);
    }

    rawinsert(aft,nd);
}

//  ---------- removing ----------

void ListHead::rawremove(ListNode* nd)
{_
 ListNode *pre=nd->pred, *suc=nd->succ; // might both be 0

    nd->succ = nd->pred = 0;

    if(!pre)    // if 'nd' at start of list
    {
        if(nfirst = suc)    // new list start becomes suc ...
            suc->pred = 0;  // ... and if suc exists, adjust it,
        else
            nlast     = 0;  // else list is empty.
    }
    else
    {
        // at least a 'pred' is given.

        if(pre->succ  = suc)    // let pred's 'succ' ptr bypass 'nd' ...
            suc->pred = pre;    // ... and if suc exists, adjust it,
        else
            nlast   = pre;      // else set new listend.
    }
}

void ListHead::remove(ListNode *nd)
{_
    // trying to remove an illegal node?

    if(!nd || testadr(nd))
    {
        perr("ListHead %lx: try to remove nonexistent node %lx",
            this, nd);

        exit(1);
    }

    rawremove(nd);
}

//  ----------- other stuff ------------

void ListHead::deleteall()
{_
 ListNode *n1,*n2;

    if(n1 = first())
    {
        while(n2 = n1->next())
        {
            delete n1;  n1=n2;
        }

        delete n1;
    }

    nfirst = nlast = 0;
}

#ifndef ZOTH

BigListHead::BigListHead() : area_max_entries(6)
{
        Reset();
}

BigListHead::~BigListHead()
{_
 ListMetaHead *ml,*down;
 ListMetaNode *mn;

    ml  = root;

    while(ml)
    {
        // empty metalist:

        while(mn = ml->first()) {ml->remove(mn); delete mn;}

        // delete metalist:

        down = ml->down;

        delete ml;

        ml = down;
    }
}

rcode BigListHead::Reset()
{_
 ListMetaNode *mn;

    hlcnt = 0;

    if(!(root = new ListMetaHead))
    {   MemErr(708931713);  return MEMORY;  }
    else
    if(!(mn = new ListMetaNode))
    {   MemErr(708931806);  return MEMORY;  }
    else
    {
        root->add(mn);
        hlcnt = 1;  // now 1 MetaNode at highest level
    }

    return OK;
}

ListNode* BigListHead::search(ListNode *cmp)
{_
 desc_back  db;

    dmsg("*searching for %lx match",cmp);

    descend(SEARCH, root, (ListMetaNode*)root->first(), cmp, db);

    return db.srchres;
}

rcode BigListHead::SplitMetaNode(ListMetaHead* lev, ListMetaNode* mn)
{_
 ListMetaNode *m2 = new ListMetaNode;
 int i=area_max_entries/2, mn_cnt=0, i2;

    if(!m2) {MemErr(708932036); return MEMORY;}
    if(!i)  {SysErr(1608931120); return INTERNAL;}

    m2->up  = mn->up;   // new node has same parent node

    lev->insert(mn,m2); // insert m2 after mn in current level list

    if(!mn->down)
    {
     ListNode *nd,*nd_pre=0;

        // + splitting a MetaNode directly over data level: +

        // get middle node of mn's area:

        for(nd=mn->lbnd; i-- && nd; nd=nd->next())
        {   nd_pre=nd; mn_cnt++;    }

        if(!nd || !nd_pre)  {SysErr(708932040); return INTERNAL;}

        // enter new boundary pointers:

        m2->lbnd = nd;
        m2->areacnt = mn->areacnt - mn_cnt;

        mn->areacnt = mn_cnt;

        dmsg("split metanode: m2->lbnd=%lx",m2->lbnd);
        dmsg("mn=%lx cnt=%d m2=%lx cnt=%d",mn,mn->areacnt,m2,m2->areacnt);
    }
    else
    {
     ListMetaNode *x,*x_pre=0;

        // + splitting a MetaNode in the index tree: +

        for(x=mn->down; i-- && x; x=(ListMetaNode*)x->next())
        {   x_pre=x; mn_cnt++;  }

        if(!x || !x_pre)    {SysErr(1008931559); return INTERNAL;}

        m2->down    = x;
        m2->lbnd    = x->lbnd;
        m2->areacnt = mn->areacnt - mn_cnt;

        mn->areacnt = mn_cnt;

        // update the 'up' pointer of all MN's in the right halve
        // of the splitted area:

        for(i2=m2->areacnt; i2--; x=(ListMetaNode*)x->next())
            x->up = m2;

        dmsg("split MN %lx -> MN's %lx %lx",mn,mn,m2);
        dmsg(" left cnt=%d  right cnt=%d",mn->areacnt,m2->areacnt);
    }

    return OK;
}

//|| *descend*

BigListHead::desc_res BigListHead::descend(

        BigListHead::desc_com   com,    // command: search, insert, delete

        ListMetaHead    *ml,    // current metalist level
        ListMetaNode    *mn,    // current node in this level
        ListNode        *nd,    // node to search for, insert, delete

        desc_back   &db     // back-promoted results of descend

        )
{_
 ListNode *afn,*curn,*rbnd; // afn = area's first node
 ListMetaNode *m2,*dwn;
 desc_res r,res=nil;
 int cres;

    dmsg("] descend: ml=%lx mn=%lx nd=%lx 0=%lx 1=%lx",
        ml, mn, nd, db.newbnd[0], db.newbnd[1]);

    if(!ml)
    {
        if(!(afn = (ListNode*)mn))
        {
            // nothing at all in the list:

            switch(com)
            {
                case SEARCH: return nil;

                case INSERT:
                    this->nfirst = this->nlast = nd;
                    nd->pred = nd->succ = 0;
                    dmsg("biglist %lx : single entry %lx",this,this->nfirst);

                    db.newbnd[0] = 0;   // before, there was nothing
                    db.newbnd[1] = nd;  // now there's a data node

                    return (desc_res)(nchg|newbnds);

                case DELETE: return nil;

                default: SysErr(808931750); return nil;
            }
        }

        // afn is valid:

        dmsg("seq search from %lx on", afn);

        for(curn = afn; ; curn = curn->succ)
        {
            if(com == DELETE)
            {
                if(curn == nd)  // del: only 1:1 ADRESS match allowed
                    break;
            }
            else
            {
                // ins, search: really compare

                cres = compare(curn,nd);

                if(!cres && com == SEARCH)  break;

                if(cres > 0)    break;
            }

            if(!curn->succ) break;
        }

        dmsg("target node: %lx cres:%d",curn,cres);

        if(cres)    cres = (cres > 0) ? 1 : -1;

        switch(com)
        {
         case SEARCH:

            db.srchres = (!cres) ? curn : 0;

            return nil;

         case INSERT:

            switch(cres)    // well, what was the last comparison's result?
            {
             case -1 :
             case  0 :
                dmsg("insert1: list %lx after %lx new %lx",this,curn,nd);

                this->insert(curn, nd);
                // this requires no lbnd adaption, so don't return 'newbnds'

                break;

             case  1 :
                if(curn->pred)
                {
                    dmsg("insert2: list %lx after %lx new %lx",
                        this,curn->pred,nd);

                    this->insert(curn->pred, nd);
                }
                else
                {
                    // remember: afn must be set, list can't be empty here

                    this->nfirst = nd;
                     nd->pred    = 0;
                     nd->succ    = curn;
                    curn->pred   = nd;

                    dmsg("biglist %lx : new first %lx",this,this->nfirst);
                }

                if(nd->succ == afn) // if inserted as new begin of area
                {
                    db.newbnd[0]    = afn;  // parent: if lbnd matches afn,
                    db.newbnd[1]    = nd;   // replace it by this

                    res = (desc_res)(res|newbnds);
                }

                break;

             default : SysErr(708931727);
            }

            return (desc_res)(res|nchg);

         case DELETE:

            db.newbnd[0]    = nd;
            db.newbnd[1]    = nd->succ;

            db.mdel[0]      = 0;
            db.mdel[1]      = 0;

            remove(nd);     // remove nd from data level

            return (desc_res)(nchg|newbnds);

        }   // endswitch com
    }
    else    // !ml -> ml
    {
        // horizontal scan through MetaNodes:

        if(com == INSERT)
        {
            // INSERT walks as far as possible, so equal entries
            // will be queued in the sequence in which they're added:

            while((m2 = (ListMetaNode*)mn->succ)
                  && compare(m2->lbnd,nd) <= 0)

                mn = (ListMetaNode*)mn->succ;
        }
        else
        {
            // SEARCH, DELETE:
            // check if rightmost entry of this area is a match.
            // if so, take it immediately!

            while(m2 = (ListMetaNode*)mn->succ)
            {
                if(!(rbnd = m2->lbnd->pred))
                {   SysErr(1208931844); return nil; }

                if(compare(rbnd,nd) < 0)
                    mn = m2;    // 'nd' is  > rbnd, warp on
                else
                    break;      // 'nd' is <= rbnd, so stay in this area
            }
        }

        if(!(dwn = mn->down))   dwn = (ListMetaNode*)mn->lbnd;

    //      ------------------------------------
        r = descend(com, ml->down, dwn, nd, db);
    //      ------------------------------------

        dmsg("descend() result: r=%d nb0=%lx nb1=%lx md0=%lx md1=%lx",
            r, db.newbnd[0],db.newbnd[1], db.mdel[0], db.mdel[1]);

        if(!r)  return nil;     // nothing special to do

        if(r & newbnds)
        {
            // check if this level's lbnd entry must be adapted:

            if(!mn->lbnd || mn->lbnd == db.newbnd[0])
            {
                mn->lbnd = db.newbnd[1];    // replace by successor
                res = (desc_res)(res|newbnds);  // check again at next-higher level
            }
        }

        if(com == INSERT)
        {
            if(r & nchg)
                mn->areacnt++;

            if(mn->areacnt > area_max_entries)
            {
                SplitMetaNode(ml, mn);
                res =(desc_res)(res|nchg);
            }

            return res;
        }

        if(com == DELETE)
        {
            if(r & nchg)
            {
                if(m2 = db.mdel[0]) // MUST be 0 if returning from data level
                {
                    // a MetaNode below us was removed. do we care?

                    if(mn->down == m2)
                        mn->down = db.mdel[1];  // yea, update the reference

                    // a MN can only be referenced by it's parent level
                    // and not further, so don't promote 'nchg' here.
                }

                // no. of entries under this MN has decreased:

                if(!--mn->areacnt)
                {
                    // nothing left under this MetaNode!

                    db.mdel[0] = mn;
                    db.mdel[1] = (ListMetaNode*)mn->succ;
                    ml->remove(mn);
                    delete mn;

                    // if there are no nodes left in this ML, delete it;
                    // the deletion will promote through all levels above.

                    if(!ml->first())
                    {
                        dmsg("removing metalist %lx",ml);

                        delete ml;
                    }

                    res =(desc_res)(res|nchg);
                }
            }

            return res;
        }

        SysErr(808931656); return nil;

    } // endelse !ml

    return res; // dead code, just to calm down compiler
}

//||    +=

rcode BigListHead::operator += (ListNode* nd)
{_
 ListMetaNode *mn;
 desc_back  db;
 desc_res   r;

    dmsg("adding node %lx to biglist %lx",nd,this);

    mn  = (ListMetaNode*)root->first();

    dmsg("primar descend:r=%lx mn=%lx nd=%lx",root,mn,nd);

    r = descend(INSERT, root, mn, nd, db);

    dmsg("result of descend from root: %d %lx %lx",
        r, db.newbnd[0], db.newbnd[1]);

    if(r & nchg)
    {
     hlcnt++;

     if(hlcnt > area_max_entries)
     {
        // create new meta-level!

        ListMetaHead *ml;
        ListMetaNode *mn,*kid;

        if(!(ml = new ListMetaHead))
        {   MemErr(708931713);  return MEMORY;  }
        else
        if(!(mn = new ListMetaNode))
        {   MemErr(708931806);  return MEMORY;  }
        else
        {
            // first, enter in ALL MN's of the topmost level
            // the pointer to their new parent node:

            for(kid=(ListMetaNode*)root->first();
                kid; kid=(ListMetaNode*)kid->next())

                kid->up = mn;   // hi, mn daddy

            // init new topmost MetaNode:

            mn->areacnt = hlcnt;    // take highest level cnt
            mn->lbnd    = nfirst;   // use absolute leftmost data entry
            mn->down    = (ListMetaNode*)root->first();

            ml->add(mn);        // enter mn in ml
            ml->down    = root; // old highmost list becomes next-lower

            // now, set the new root:

            root  = ml;

            // reset topmost counter:

            hlcnt = 1;  // now 1 MetaNode (again) at highest level
        }
     }
    }

    dmsg(" ");

    return OK;
}

//||    -=

rcode BigListHead::operator -= (ListNode* nd)
{_
 ListMetaNode *mn;
 desc_back  db;
 desc_res   r;

    dmsg("removing node %lx from biglist %lx",nd,this);

    mn  = (ListMetaNode*)root->first();

    dmsg("primar descend:r=%lx mn=%lx nd=%lx",root,mn,nd);

    r = descend(DELETE, root, mn, nd, db);

    dmsg("result of delete at root: %d %lx %lx %lx",
        r, db.newbnd[0], db.newbnd[1], db.mdel[0]);

    if(r & nchg)
    {
      if(!--hlcnt)
      {
        // whole biglist is empty!

        dmsg("re-init of BigList %lx\n",this);

        Reset();
        // ... calling the constructor instead would be pretty crashy

        dmsg("nfirst/last: %lx %lx\n",nfirst,nlast);
      }
    }

    dmsg(" ");

    return OK;
}

#endif

/*
rcode BigListHead::AddSVList()
{_
 ListMetaHead *ml=root;
 ListMetaNode *mn;
 rcode r;

    while(ml)
    {
        if(r=sv.addobj("ML",ml, ml->nfirst, ALE, ml->down, ALE))
            return r;

        for(mn = (ListMetaNode*)ml->first(); mn; mn=(ListMetaNode*)mn->next())
        {
            if(r=sv.addobj("MN",mn, mn->succ, mn->pred, ALE,
                 mn->lbnd, mn->down, mn->up, ALE))
            return r;
        }

        ml  = ml->down;
    }

    return OK;
}
*/
