#   ifndef  _EXP_LIST_H_
#   define  _EXP_LIST_H_ 80

/*
  2901942114 <- last update (yymmddhh'')
     _____________________________________________________________
    /                                                             \ 
    | Headerfile:   list.h
    \_____________________________________________________________/

    Description:    explib's list classes
    Refers to:      explib.h
    Included by:    explib.h
    Called by:      everywhere

    Contents:

        ListHead :      simple double linked list;
                        low overhead, poor performance.

        BigListHead :   sorted list with an index tree;
                        medium overhead, high performance.

    Local Terminology:

        Abbrev. Meaning
        ------- ------------------------
        Node    entry in a list
        MN      MetaNode
        ML      MetaList


    Developers: ID: Name:
    =========== --- -----
                JTH Juergen Thumm
  _____________________________________/VERSION HISTORY\____________________
 /Date_ Version Who What____________________________________________________\ 
 yymmdd ------- --- ---------------------------------------------------------
 930823 0.800   JTH added this header
 940125             moved StructView to display.h;
                    no further display.h auto-including
 940129 0.80.2      ListHead.deleteall()

 940905 0.81    JTH PORTED TO WINDOWS 3.1
 941215             ListNode::next/prev,ListHead::first/last:
                    with NO_MEMTRACK defined, it's now compiled as implicite
                    inline, which seems to be the only inline to work;
                    explicite works only if source is in same module, and
                    'inline' statement is in function definition (NOT
                    declaration).
*/

#ifndef _EXPDEF_H_
#   include "expdef.h"
#endif
#ifndef _EXPLIB_H_
#   include "explib.h"
#endif

/*   _____________________________________________________________
    /                                                             \ 
    | Class:    ListNode
    \_____________________________________________________________/

    Description:    simple node in a simple double-linked list

    Refers to:      ListHead

    Methods:
        next    - gives successor node or 0 if there's no successor
        prev    - gives predecessor node or 0 if at start of list

    Tested: wt

  _____________________________________/VERSION HISTORY\____________________
 /Date_ Version Who What____________________________________________________\ 
 yymmdd ------- --- ---------------------------------------------------------
 930816 1.00    JTH created

*/

//|| ListNode 

class ListNode {

    ListNode* succ;
    ListNode* pred;

    friend class ListHead;
    friend class BigListHead;

    // the following two are necessary for MemControl to avoid
    // recursion overflows: e.g. ListNode::next calls MemControl,
    // MemControl calls ListNode::raw(!)next to handle an internal list.

    friend class MemControl;

 public:

    ListNode* rawnext() const {return succ;} // like next()/prev() but w/o
    ListNode* rawprev() const {return pred;} // surveillance of succ/pred

    // give successor of current node
    ListNode* next() const
#   ifdef   NO_MEMTRACK
        {   return  succ;   }
#   endif
        ;

    // give predecessor of current node
    ListNode* prev() const
#   ifdef   NO_MEMTRACK
        {   return  pred;   }
#   endif
        ;

    ListNode()  {succ=pred=0;}

    };

/*   _____________________________________________________________
    /                                                             \ 
    | Class:    ListHead
    \_____________________________________________________________/

    Description:    head of a simple double-linked list

    Refers to:      ListNode

    Methods:
        add     - add a new ListNode to the list
        remove  - remove a ListNode from the list
        insert  - insert ListNode after another ListNode in the list
        first   - gives first ListNode of the list
        last    - gives  last ListNode of the list

    Tested: wt

  _____________________________________/VERSION HISTORY\____________________
 /Date_ Version Who What____________________________________________________\ 
 yymmdd ------- --- ---------------------------------------------------------
 930816 1.00    JTH created

*/

//|| ListHead 

class ListHead {

 protected:

    ListNode *nfirst;
    ListNode *nlast;

    // raw access for MemControl to avoid recursions:

    friend class MemControl;

    void rawadd(ListNode*);
    void rawaddfront(ListNode*);
    void rawinsert(ListNode* after, ListNode *nd);
    void rawremove(ListNode*);

 public:

    ListHead();     // initialize

    ListNode* rawfirst() const  {return nfirst;};
    ListNode* rawlast()  const  {return  nlast;};

    // give first entry of list
    ListNode* first() const
#   ifdef   NO_MEMTRACK
        {   return  nfirst; }
#   endif
        ;

    // give  last entry of list
    ListNode*  last() const
#   ifdef   NO_MEMTRACK
        {   return  nlast;  }
#   endif
        ;

    void add(ListNode*);        // add node at end of the list

    void addfront(ListNode*);   // add node at front of list

    void insert(ListNode* after, ListNode *nd);

    void remove(ListNode*); // remove node from list

    // int (*compare)(ListNode*,ListNode*);
    // IF you want to build a tiny(!) sorted list,
    // set this ptr to your compare function.
    // It must return
    //      0   if equal
    //      <0  if this < other
    //      >0  if this > other
    // If no comparison is required (unsorted list), leave this ptr 0
    // NOTE: use this only for tiny lists;
    //       for large sorted lists use the 'BigList' !

    void deleteall();   // remove & delete all nodes from list

    rcode checkup();    // check list for corruption. returns OK if none

    };

/*   _____________________________________________________________
    /                                                             \ 
    | Class:    ListMetaNode
    \_____________________________________________________________/

    Description:    some sort of 'index' node used in BigLists's
                    index tree.

    Derived from:   ListNode

    Refers to:      ListMetaHead, BigListHead

    Methods:    --

    Tested: wt

  _____________________________________/VERSION HISTORY\____________________
 /Date_ Version Who What____________________________________________________\ 
 yymmdd ------- --- ---------------------------------------------------------
 930816 0.90    JTH created

*/

//|| LMetaNode

class ListMetaNode : public ListNode {

    friend class BigListHead;

    int areacnt;    // how much entries of the next lower level
    // belong to this MetaNode?

    ListNode* lbnd; // left boundary of this MetaNode's area
    // this is the lowest data level node belonging to this MN

    ListMetaNode *down;     // IF there is another level of metanodes
    // below the level this MN belongs to, this points to the FIRST
    // MN of the MN's belonging to this MN.
    // IF this pointer is NULL, next level is pure data, i.e.
    // the ListNode's starting at 'lbnd' must be sequentially searched.

    ListMetaNode *up;
    // IF there's another metalevel above the current,
    // this points to the parent MetaNode to which this MN belongs to.
    // on topmost level, points to a dummy

    ListMetaNode()  {areacnt=0; lbnd=0; down=up=0;}

    ListMetaNode* next() {return (ListMetaNode*)ListNode::next();}

    };

/*   _____________________________________________________________
    /                                                             \ 
    | Class:    ListMetaHead
    \_____________________________________________________________/

    Description:    Head of an index level of BigList's index tree.

    Derived from:   ListHead

    Refers to:      BigListHead

  _____________________________________/VERSION HISTORY\____________________
 /Date_ Version Who What____________________________________________________\ 
 yymmdd ------- --- ---------------------------------------------------------
 930816 0.90    JTH created

*/

//||ListMetaHd

class ListMetaHead : public ListHead {

    friend class BigListHead;

    ListMetaHead *down; // downward link to next MetaList level

    ListMetaHead()  {down=0;}

    ListMetaNode* first() {return (ListMetaNode*)ListHead::first();}

    };

/*   _____________________________________________________________
    /                                                             \ 
    | Class:    BigListHead
    \_____________________________________________________________/

    Description:    Head of a sorted high-performance list.

    Refers to:      ListNode, ListHead, ListMetaNode, ListMetaHead

    Methods:
        +=      - add a node to the list
        -=      - remove a node from the list
        search  - search for a node
        first   - give first entry of list
        last    - give  last entry of list

    Requirements:
        This class MUST hold the data in a sorted order to work right.
        So, to use it, you MUST
        a) derive your own class from it
        b) implement the 'compare' method which compares two of the
           elements you want to store in the class.
           for more see declaration below.

    Tested: v1.00/wt

  _____________________________________/VERSION HISTORY\____________________
 /Date_ Version Who What____________________________________________________\ 
 yymmdd ------- --- ---------------------------------------------------------
 930816 1.00    JTH created

*/

//|| BListHead

class BigListHead : public ListHead {

  public:
    enum desc_res {nil=0,nchg=1,newbnds=2}; // result type of 'descend'

  private:
    struct desc_back {

        ListNode    *srchres;   // search result

        ListNode    *newbnd[2]; // for insert, delete:
        // if some flag is set, check if lbnd in the current MN
        // matches newbnd[0]. if so, replace lbnd by newbnd[1]

        ListMetaNode *mdel[2];  // for delete:
        // if some flag is set, check if MN->down matches [0].
        // if so, replace by [1].

        desc_back() {srchres=newbnd[0]=newbnd[1]=0; mdel[0]=mdel[1]=0;}

        };

    enum desc_com {SEARCH, INSERT, DELETE};

    desc_res descend(

        desc_com        dc,     // command: search, insert, delete

        ListMetaHead    *ml,    // current metalist level

        ListMetaNode    *mn,    // current node in this level
        // this can also be a ListNode* if entering lowest level

        ListNode        *nd,    // node to search for, insert, delete

        desc_back   &db     // back-promoted results of descend

        );

    ListMetaHead *root; // ptr to highest MetaNode level list

    const int area_max_entries;
    // if a MetaNode has more than that entries below it, it must
    // be split into two nodes.

    rcode SplitMetaNode(ListMetaHead* lev, ListMetaNode* mn);

    int hlcnt;  // highest level counter
    // everytime something's added to this list, and descend()
    // returns with 'nchg' set, this cnt is incremented, i.e.
    // a new node was added to current highest metalevel.
    // If this cnt surpasses area_max_entries, a new metalevel is installed.

    rcode Reset();  // initialize BigListHead entries (again)

 public:

    BigListHead();  // initialize
    ~BigListHead(); // delete metadata

    rcode operator += (ListNode*);  // add a node to the list
    rcode operator -= (ListNode*);  // remove node from list

    ListNode* search(ListNode*);    // check if a 1:1 match of the
    // supplied node already exists

    virtual int compare(ListNode*, ListNode*) = 0;
    // required compare fn
    // result like ListHead::compare

    // virtual ulong hash(ListNode*) {};
    // optional hash calculation fn
    // if implemented, this returns a ulong value x calculated from
    // the important entries of the node.
    // NOTE: x must fulfill these rules:
    //  IF node A < node B  then A.hash <= B.hash
    //  IF node A > node B  then A.hash >= B.hash
    // If this is NOT the case, the list will crash.

    // /- these two are for debugging purposes only:
    //class StructView sv;
    //rcode AddSVList();    // put your whole structure into sv
    // \- comment out if not needed

    };

#   endif
