// CList.h

#if _MSC_VER >= 1000
#pragma once
#endif // _MSC_VER >= 1000

#ifndef CListh
#define CListh

/* CCList is a sorted Circular linked List with WORD Key.
Algorithmically, this is supposed to be as fast as linked lists get.
The algorithm is the sort of thing used in Assembly Language real time graphics renderers.
Ideally this should be a template class but there is already a list template, so this is more useful for just demonstrating the principle.
If you want a different key type you have to edit the class and adjust SENTINEL appropriately.

Usage:
  CCList CList;     // List={SENTINEL};
  CList.Add(3);     // List={3,SENTINEL};
  CList.Add(13);    // List={3,13,SENTINEL};
  CList.Add(23);    // List={3,13,23,SENTINEL};
  CList.Add(32);    // List={3,13,23,32,SENTINEL};
  CList.Add(3);     // List={3,3,13,23,32,SENTINEL};
  CList.Add(2);     // List={2,3,3,13,23,32,SENTINEL};
  CList.Delete(13); // List={2,3,3,23,32,SENTINEL};
  bool b=CList.Find(23);    //b=true;
  DWORD Key=CList.GetKey(); //Key=23
  b=CList.Next();           //b=true;
  Key=CList.GetKey();       //Key=32
  b=CList.Next();           //b=false;
  CList.Empty();    // List={SENTINEL};
*/
#define SENTINEL -1 //Largest possible Key field

class CCList {
  struct CCListNode {
    CCListNode(WORD key=SENTINEL) {Next=this; Key=key;}
    CCListNode* Next;
    WORD        Key;
  };
  void Insert(WORD Key) {Insert(new CCListNode(Key));}
  void Insert(CCListNode* NodeToInsert) {
    WORD SearchValue=NodeToInsert->Key;
    for(it=First; it->Next->Key<SearchValue; it=it->Next);
    NodeToInsert->Next=it->Next;
    it->Next=NodeToInsert;
  }

protected:
  CCListNode* First;
  CCListNode* it; //Iterator Points at the Node PRIOR to the one to use.

public:
  CCList() {First=it=new CCListNode;}
  virtual ~CCList() {try{Empty(); delete[] First;}catch(...){}}
  void Add   (WORD Key) {Insert(Key);}
  void Delete(WORD Key) {if(Find(Key)) Delete();}
  void Delete() {
    if(IsEmpty()) return;
    CCListNode* NodePtr=it->Next;
    it->Next=it->Next->Next;
    delete NodePtr;
  }
  bool IsEmpty() const {return First==First->Next;}
  void Empty() {
    while(!IsEmpty()) {
      it=First->Next;
      First->Next=First->Next->Next;
      delete it;
  } }
  void Home()   {it=First;}
  WORD GetKey() {return it->Next->Key;}
  bool Next()   {it=it->Next; return it->Next!=First;}
  bool Find(WORD SearchValue) {
    for(it=First; it->Next->Key<SearchValue; it=it->Next);
    return (it->Next->Key==SearchValue) && (it!=it->Next);
  }
};

#endif // CListh