/* TreeList.h

  G.M.Adelson-Velskii and E.M.Landis (AVL) Binary Tree

The following code is a simplified and yet optimised AVL Tree which can morph to and from a Doubly-Linked List very quickly and efficiently.
As usual the code is written for readability and maintainability - I wrote a marginally faster version, but it was too ugly to survive.
The normal AVL rebalancing makes lots of status checks which are unnecessary if you just do the rotations at the right time in the code.
The order is determined by your implementation of the Compare function (examples follow):
 There must be a function T::Compare(T&) or the function Compare of the Template class CTreeListNode<T> has to be overridden.
In normal use the structure is an AVL Tree (A Binary Search Tree which is optimised (balanced) whenever nodes are Inserted or Deleted).
Once insertion and searching is finished the structure can be turned into a linked list for fast iterations.
The TreeList insertion is faster than linked list insertion for large numbers of nodes (unless the Nodes are inserted in reverse order).
Turning the Tree into a linked list only need happen once all the nodes are inserted.
Then iterating the list is faster than iterating the Tree.
To put some numbers to these ideas:

To insert 32768 nodes in descending order into this structure in List mode took    2 units of time
To insert 32768 nodes in  ascending order into this structure in List mode took 3800 units of time
To insert 32768 nodes in  ascending order into this structure in Tree mode took    5 units of time
To insert 32768 nodes in descending order into this structure in Tree mode took    6 units of time

There are many ways of implementing AVL Trees and a lot of thought went into choosing the methods used here.
If you think you know a faster or better way then let me know, but I've probably tried it already!
(Examples being:
 Having each node store a pointer to its parent (makes Insert 1/3 faster but makes the code bulky and less readable (and isn't neccesary)).
 Using separate code for double rotations (negligible speed increase and creates duplication of code).
 Cut/Link Restructure instead of rotations (big speed decrease (half as long again)).
 Moving methods from one class to another (They're all in the right places:)
)
You can use this Structure just in its Tree mode, or its List mode.
You'd use the Tree to search and sort data quickly or to identify or remove duplicates from data.
It is similar to std::map but (particularly for STL beginners) easier to use (and std::map uses "Red Black" Tree instead of AVL Tree (see http:// www.sgi.com/tech/stl/stl_tree.h)).
The STL tree is slow to iterate in sorted order in comparison to a Linked List.

An AVL tree is not perfectly balanced.
The height of a perfectly balanced tree is approximately lg n, where n is the number of nodes
whereas the worst case height of an AVL tree is approximately 1.44 lg n.
In practice, however, the AVL height approaches lg n as n gets large and so is almost optimal.
So where n is large and performance counts, AVL trees are preferable to random Binary Trees.

This is a template-based class, requiring the nodes to have a Compare function that returns an int value:

 <0, if *this  < t
  0, if *this == t
 >0, if *this  > t

For example:

#include <iostream.h>
#include "TreeList.h"

class CInteger {
public:
  int i;
  CInteger(int i) : i(i) {}
  int Compare(const CInteger& j) const {return i-j.i;}
};

void main() {
  CTreeList<CInteger> TreeList;
  TreeList.Insert(new CInteger(1));
  TreeList.Insert(new CInteger(2));
  TreeList.Insert(new CInteger(2)); // Returns 0 because 2 is already inserted (Duplicates are not stored).
  TreeList.Insert(new CInteger(3));
  for(CTreeListIterator<CInteger> it(TreeList); it; ++it) cout << it.GetData()->i << endl;
}

Here's an example using the Iterator a little more:
#include "TreeList.h"
#include <fstream.h>
#include <string>

class CMyString {
public:
  CMyString(const std::string& S) {String=S;}
  int Compare(const CMyString& S) const {return String.compare(S.String);}
  std::string String;
};

void SortFile(const char* iPath, const char* oPath) {
  ifstream iStream(iPath);
  ofstream oStream(oPath);
  char Buffer[255];

  for(CTreeList<CMyString> Tree; iStream.getline(Buffer, sizeof(Buffer)-1); Tree.Insert(new CMyString(Buffer)));
  Tree.Morph2List(); // (This is only worth doing if you're going to iterate more than once)
  for(CTreeListIterator<CMyString> it(Tree); it; ++it) oStream << it->String.c_str() << endl; // Note that it-> returns it->GetData() it's just easier to write!
  it.Last();
  while(it) oStream << it--.GetData()->String.c_str() << endl;
}

Here's the same thing using MFC:
#include "TreeList.h"
void SortFile(const char* IPath, const char* OPath) {
  CFile IFile,OFile;
  if(!IFile.Open(IPath,CFile::modeRead|CFile::shareDenyNone)) return false;
  CArchive IAr(&IFile, CArchive::load);
  if(!OFile.Open(OPath,CFile::modeCreate|CFile::modeWrite|CFile::shareDenyNone)) return false;
  CArchive OAr(&OFile, CArchive::store);

  CTreeList<CString> TreeList;
  for(CString S; IAr.ReadString(S); TreeList.Insert(new CString(S)));
  TreeList.Morph2List(); // (This is only worth doing if you're going to iterate more than once)
  for(CTreeListIterator<CString> it(TreeList); it; ++it) OAr.WriteString(*it+"\r\n"); // note that *it returns *(it->GetData()) it's just easier to write!
  it.Last();
  while(it) OAr.WriteString(*(it--.GetData())+"\r\n");
}

If you're new to this sort of thing there are a couple of things you'll need to know:
When using MFC files #include <string> in .cpp files has to be at the top of the file above the static char THIS_FILE[] = __FILE__; section.
Declarations using the Standard Template Library sometimes need a space before the trailing > so this will work:

  std::map<std::string, int, std::less<std::string> > UserCode;

and this will give a weird unrelated error (syntax error : missing ',' before identifier 'UserCode') because it sees the >> as the shift-right operator:

  std::map<std::string, int, std::less<std::string>> UserCode;

There must be a function T::Compare(T&) or the function Compare of the Template class CTreeListNode<T> has to be overridden.
You must have the word const twice in the Compare function definition!
You can see that the definition must be identical from the Non-MFC example above: std:string has a suitable compare function but the name Comapare is all lower case...
So I had to make a whole new class that just provides a 'Compare' interface to the 'compare' function...
Of course, if you always use the std::string you'd be better off just changing the case of the Compare function in TreeList.h

Here's an example with nodes that contain a CString Key and int data that I used to maintain a count of files with a specific file extension in a given folder.
The CString in each node is the file extension (eg. "cpp") and the int is the count of files with that extension.
This class is going to be used as the node:

class CExtension : public CString {
  int Count;
public:
  CExtension(const CString& S) : Count(0), CString(S) {}
  int& operator++() {return ++Count;}
};

Ext is a CString currently holding the file extension.
The class has
  CTreeList<CExtension> TreeList;
in the header and each time a file is found the following code inserts a new node or increments the count for the files extension:
  Ext.MakeLower();
  TreeList.Insert(new CExtension(Ext)); // The new CExtension is deleted if a node with this extension already exists.
  CTreeListIterator<CExtension> it(Ext);
  it.Find(CExtension(S));
  int CountOfFilesWithThisExtension=++*it;

Finally a note on my "Behaviour Class"
If you want something to happen to every Node's Data then derive a class from CTreeListNodeBehaviour and use ForAll:
Here's an example class that goes through a Tree of CStrings and puts '<' and '>' characters on either side of the string (so "hello" becomes "<hello>"):
class CTreeListTagger: public CTreeListNodeBehaviour<CString> {
private:
  void Behaviour(CString& S) {S='<'+S+'>';}
};

Don't try Deleting or Inserting within Behaviour, the restructuring that they induce will mess up the recursion and Behaviour may be missed on some nodes and done twice on others as a result.

Here's a version that counts the nodes in the Tree...
It is only 25% slower than the GetNodeCount function:

class CTreeListNodeCounter: public CTreeListNodeBehaviour<CString> {
private:
  int Count;
  void Behaviour(CString&) {++Count;}
public:
  CTreeListNodeCounter() : Count(0) {}
  int  GetCount() const {return Count;}
  void Reset() {Count=0;}
};

It's only slower because the ForAll function has to pass the Behaviour as a parameter.

Here are the statistics from my Tester:

Inserting 1048576 Random Nodes
 CTreeList Insertion Time: 10250ms

Nodes pre-Morph: 1048446 = 1048446  <<<< One is the Count Member, the other actually counts the nodes.
 NodeCount Time: 203ms
  Morph2List Time: 625ms
 Nodes post-Morph: 1048446 = 1048446
 NodeCount Time: 234ms
  Morph2Tree Time: 3516ms           << Insertion not yet optimised
 Nodes post-Morph: 1048446 = 1048446
 NodeCount Time: 187ms

Randomly Deleting 524288 Random Nodes
 CTreeList Deletion Time: 5625ms
  Nodes post-Delete: 524190 = 524190
  NodeCount Time: 5719ms
 CTreeList Deletion Time: 4015ms
  Nodes post-Delete: 0 = 0
  NodeCount Time: 4015ms
*/

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

#ifndef TreeListh
#define TreeListh

#ifndef max
  #define max(a,b) (((a) > (b)) ? (a) : (b))
#endif
#ifndef ASSERT
  #define ASSERT(x) 
#endif

template <class T> class CTreeList;
template <class T> class CTreeListNode;
template <class T> class CTreeListIterator;

template <class T> struct CTreeListNodeBehaviour {
  virtual void Behaviour(T& t, int Depth) {} // This is the one you should normally use.
  virtual void InOrder  (T** t, CTreeListNode<T>** Left, CTreeListNode<T>** Right, int Depth) {Behaviour(**t,Depth);} // Smallest to Largest (Left to Right) across the Tree (as defined by your Compare(...) function).
  virtual void PreOrder (T** t, CTreeListNode<T>** Left, CTreeListNode<T>** Right, int Depth) {} // This is for folk who want to serialize the Tree structure - everyone else can ignore it.
  virtual void PostOrder(T** t, CTreeListNode<T>** Left, CTreeListNode<T>** Right, int Depth) {} // This is for folk who have made an Expression Tree - everyone else can ignore it.
};
/* Just a quick couple of examples of using Pre or Post for those who might want them:
This one prints a Tree as a line of text (only useful for debug of tiny trees):
  class CDump: public CTreeListNodeBehaviour<CString> {
    virtual void PreOrder (CString** t, CTreeListNode<CString>** Left, CTreeListNode<CString>** Right, int Depth) {if(*Left || *Right) cout << "(";}
    virtual void InOrder  (CString** t, CTreeListNode<CString>** Left, CTreeListNode<CString>** Right, int Depth) {if(*Left) cout << "/"; cout << **t; if(*Right) cout << "\\";}
    virtual void PostOrder(CString** t, CTreeListNode<CString>** Left, CTreeListNode<CString>** Right, int Depth) {if(*Left || *Right) cout << ")";}
  };
  TreeList.ForAll(CDump()); cout << endl;
________________________________________________________
class CEvaluate: public CTreeListNodeBehaviour<CToken> {
private:
  void Behaviour(CToken& S) {}
  void PostOrder(CToken** DataPointerLocation, CTreeListNode<CToken>** LeftPointerLocation, CTreeListNode<CToken>** RightPointerLocation) {
    **DataPointerLocation.Do(*LeftPointerLocation, *RightPointerLocation); // Perform the operation at this node given pointers to the two children. This would change this CToken from an operator to a number.
    delete *LeftPointerLocation; // We've finished with the child nodes now:
    *LeftPointerLocation=0;
    delete *RightPointerLocation;
    *RightPointerLocation=0;
  }
};
Then to run this code you'd use:
  CTreeList<CToken> TreeList;
  ...
  TreeList.Insert(...);
  ...
  TreeList.ForAll(CEvaluate());
*/

template <class T> class CTreeListNode {
  friend class CTreeList<T>;
  friend class CTreeListIterator<T>;

  T* Data;
  CTreeListNode<T>* Left;
  CTreeListNode<T>* Right;
  unsigned char Depth; // Used to maintain AVL Balance, give a quick report of Tree Depth, and Depth=0 indicates this is currently as a List structure. A maximum depth of 127 allows for 2 to the power 127 nodes which is more than current computers could handle. It would take 3327582825599102178928845914112 Giga-Bytes to store the tree!
  bool IsList()   const {return Depth==0;}
  char GetLevel() const {return Depth;}

  CTreeListNode(T* data, char Depth=1, CTreeListNode<T>* left=0, CTreeListNode<T>* right=0) : Data(data), Depth(Depth), Left(left), Right(right) {}
  CTreeListNode(const CTreeListNode<T>& Node) : Depth(1), Left(0), Right(0), Data(new T(*(Node.Data))) {}
  virtual ~CTreeListNode() {try{delete Data;}catch(...){ASSERT(0);}}
  const CTreeListNode<T>& operator=(const CTreeListNode<T>& Node) {
    delete Data;
    Data=new T(*(Node.Data));
    return *this;
  }

  // If you get a 'THIS POINTER' ERROR here you have forgotten to const your Compare function: int Compare(const MyNode& n) const {return Count-n.Count;}
  static int Compare(const T& t1, const T& t2) {return t1.Compare(t2);} //                                 ^^^^^    AND     ^^^^^

/* AVL Trees are most often used with large numbers of Nodes.
You may worry that the following recursive routines will run out of Stack Space...
However, only one call is made for each Level of the Tree,
so 2^20 (a million) Nodes would be 20 calls of stack space, two million would use 21 calls.
At 12 bytes per call that's 240 bytes of stack space for a million Nodes; 252 for two million...
Here's an iterative version of GetNodeCount (the others would be harder and uglier to make iterative).
This iterative version is twice as slow as the recursive version:
  long  GetNodeCount() {
    CTreeListNode<T>* it=GetFirst();
    for(long Nodes=1; it=it->GetNext(); ++Nodes);
    return Nodes;
  }
Be aware that since the routine's code is run by every node, if you rewrite anything you will introduce dramatic performance changes! */
  unsigned GetNodeCount() const {return 1+(Left && !IsList() ? Left->GetNodeCount() : 0)+(Right ? Right->GetNodeCount() : 0);}

  CTreeListNode<T>* CopyTree() const { // Return a pointer to a copy of this node and all its children:
    CTreeListNode<T>* NewMe=new CTreeListNode<T>(new T(*Data), Depth); // In-Order Recursion:
    if(Left && !IsList())  NewMe->Left = Left->CopyTree();
    if(Right)              NewMe->Right=Right->CopyTree();
    return NewMe;
  }

  void SetDepth() {Depth=max((Left ? Left->Depth : 0), (Right ? Right->Depth : 0))+1;} // I thought of this! :-D

  CTreeListNode<T>* RotateLeft() { // Swap levels with Right Child
    CTreeListNode<T>* Root=Right;
    Right=Root->Left; // Move Pointers to swap levels with Root
    Root->Left=this;
          SetDepth();
    Root->SetDepth();
    return Root;
  }
  CTreeListNode<T>* RotateRight() { // Swap levels with Left Child
    CTreeListNode<T>* Root=Left;
    Left=Root->Right; // Move Pointers to swap levels with Root
    Root->Right=this;
          SetDepth();
    Root->SetDepth();
    return Root;
  }

  // If you want something to happen to every node then derive a class from CTreeListNodeBehaviour (above) and use ForAll:
  void ForAll(CTreeListNodeBehaviour<T>& Behaviour) {
    Behaviour.PreOrder(&Data, &Left, &Right, Depth);  // PreOrder things happen Root to Leaves
    if(!IsList() && Left) Left->ForAll(Behaviour);
    Behaviour.InOrder(&Data, &Left, &Right, Depth);   // InOrder things happen Smallest to Largest (using Compare(...))
    if(Right) Right->ForAll(Behaviour);
    Behaviour.PostOrder(&Data, &Left, &Right, Depth); // PostOrder things happen Leaves to Root
  }
public: // Just for the Pre and Post methods on ForAll.
  T& GetData() const {return *Data;}
};

/*>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> TreeList <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
Requirements for the class T:
Objects of class T must be comparable.
A function
 int T::Compare(const T& t) const {return this-that;}
must be implemented.
 Return values:
   <0, if *this  < t
    0, if *this == t
   >0, if *this  > t

  CTreeList<CString> TreeList;
  CString* ptr=new CString("1234");
  TreeList.Insert(ptr);
*/
template <class T>
class CTreeList {
  friend class CTreeListIterator<T>;

  CTreeListNode<T>* Tree;  // The root of all evil!
  unsigned          Count; // A maintained Node-Count to save actually Counting Nodes
  bool              List;  // true when the Nodes are a Linked List and false when the Nodes are an AVL Tree.

  // Temporary variables Used as "Globals" by recursing routines.
  CTreeListNode<T>* Node; // Generally stores the Node a recursive routine is searching for or has dealt with etc.
  T*                Data; // Generally stores the Data a recursive routine is searching for or has dealt with etc.
  int               Comparison; // Comparison==0 if Data was already in the Tree (after a search)
  bool              Drop; // Used by private Empty. true if Data is not to be deleted.

public:
  CTreeList() : Tree(0), Count(0), List(false) {}
  CTreeList(const CTreeList<T>& Tree) : List(Tree.List), Count(Tree.Count), Tree(Tree.Tree->CopyTree()), Drop(false) {} // Well, there's egg and bacon; egg, sausage and bacon; egg and Tree; egg, bacon and Tree; egg, bacon, sausage and Tree; Tree, bacon, sausage and Tree; Tree, egg, Tree, Tree, bacon and Tree; Tree, sausage, Tree, Tree, Tree, bacon, Tree, tomato and Tree; Tree, Tree, Tree, egg and Tree... or lobster thermador ecrovets with a bournaise sause, served in the purple salm manor with chalots and overshies, garnished with truffle pate, brandy, a fried egg on top and Tree.
  const CTreeList<T>& operator=(const CTreeList<T>& _Tree) {
    Empty();
    Tree=_Tree.GetRoot()->CopyTree();
    return *this;
  }
  virtual ~CTreeList() {try{Empty();}catch(...){ASSERT(0);}}

  bool IsList  ()      const {return  List;}
  bool IsEmpty ()      const {return !Tree;}
  int  GetDepth()      const {return  Tree && !List ? Tree->GetLevel() : 0;}
  T&   GetRoot ()      const {return  Tree->GetData();} // Just for the Pre and Post methods on ForAll. It's a reference because there will always be Data.
  T*   GetFirst()      const {CTreeListNode<T>* it; for(it=Tree; it->Left ; it=it->Left ); return it->Data;}
  T*   GetLast ()      const {CTreeListNode<T>* it; for(it=Tree; it->Right; it=it->Right); return it->Data;}
  T* operator->()      const {return  GetFirst();}
  T& operator* ()      const {return *GetFirst();}
  unsigned  GetCount() const {return  Count;}
  unsigned GetNodeCount() const { // Count them!
    if(IsEmpty()) return 0;
    if(!List) return Tree->GetNodeCount();
    int Count=1;
    for(CTreeListNode<T>* it=Tree; it=it->Right; ++Count);
    return Count;
  }
  void Exchange(CTreeList& tree) {
    CTreeListNode<T>* tTree =Tree ; Tree =tree.Tree ; tree.Tree =tTree ; // The root of all evil!
    unsigned          tCount=Count; Count=tree.Count; tree.Count=tCount; // A maintained Node-Count to save actually Counting Nodes
    bool              tList =List ; List =tree.List ; tree.List =tList ; // true when the Nodes are a Linked List and false when the Nodes are an AVL Tree.
  }
  void Empty(bool DeleteData=true) { // Since filling is almost always faster as a Tree, reverts to Tree mode.
    if(List) for(CTreeListNode<T>* it=Tree; it; it=Tree) {
      Tree=it->Right;
      if(!DeleteData) it->Data=0;
      delete it;
    }else{
      Drop=!DeleteData;
      Empty(Tree);
    }
    Tree=0;
    Count=0;
    List=false; // Since filling is almost always faster as a Tree, assume Tree mode.
  }
private:
  void Empty(CTreeListNode<T>* Root) {
    if(!Root) return; // PostOrder Recursion:
    Empty(Root->Left );
    Empty(Root->Right);
    if(Drop) Root->Data=0;
    delete Root;
    --Count;
  }

public:
  void ForAll(CTreeListNodeBehaviour<T>& Behaviour) {if(Tree) Tree->ForAll(Behaviour);}

  void Morph2Tree() { // If you are inserting the data in something close to reverse order (List insertions will be fast) and will do lots of iteration before finally doing searching, then use this, but it will take at least as long as loading the Tree would have taken...
    if(!List) return;
    if(Tree) {
      unsigned LastCount=Count;
      CTreeListIterator<T> it(this);
      Tree=0; // Start with a fresh Tree (The Iterator remembers where the List is).
      while(it) {
        List=false; // Insert to the Tree
        Insert(it); // If I thought this was ever likely to be useful I'd make it insert the nodes binary-chop-style to minimise Rotations on Insert...
        List=true ; // Delete from the List
        CTreeListNode<T>* Root=Tree;
        Tree=it.it;
        it.Delete(true,false);
        Tree=Root;
      }
      Count=LastCount;
    }
    List=false;
  }
  void Morph2List() {
    if(List) return;
    if(Tree) {
      CTreeListIterator<T> it(this);
      MakeList(Tree);
      Tree=it.it;
    }
    List=true; // Change mode even when empty
  }
private:
  void MakeList(CTreeListNode<T>* Root) {
    CTreeListIterator<T> Left (this,Root);
    CTreeListIterator<T> Right(this,Root);
    Left .Prev();
    Right.Next();
    if(Root->Left ) MakeList(Root->Left );
    if(Root->Right) MakeList(Root->Right);
    Root->Left =Left .it;
    Root->Right=Right.it;
    Root->Depth=0; // Let Nodes know they are in a List now.
  }

public:
  bool Insert(T* data, bool AutoDelete=true) {
    Data=data;
    if(IsEmpty()) {
      Node=Tree=new CTreeListNode<T>(Data);
      Count=1;
    }else if(List) {
      CTreeListNode<T>* it;
      for(it=Tree; it->Right; it=it->Right) {
        Comparison=it->Compare(*(it->Data), *data);
        if(Comparison==0) it=0; // Error: object already in the Tree (only insert once)!
        if(Comparison>=0) break;
      }
      if(it==0) {
        if(AutoDelete) delete data;
        return false;
      }else if((!it->Right) && (it->Compare(*(it->Data), *data)<0)) {
        Node=it->Right=new CTreeListNode<T>(data, 0, it,0); // Last in List
        ++Count;
      }else{
        Node=new CTreeListNode<T>(data, 0, it->Left,it);
        ++Count;
        if(it->Left) it->Left->Right=Node; // Mid-List
        else Tree=Node; // First in List
        it->Left=Node;
      }
    }else{
      Tree=Insert(Tree);
      if(!Comparison && AutoDelete) delete Data;
      return Comparison!=0;
    }
    return true;
  }
private:
  CTreeListNode<T>* Insert(CTreeListNode<T>* Root) { // Recursive Search, Insert and Rebalance. Sets Node:
    if(Root==0) {++Count; return Node=new CTreeListNode<T>(Data);}
    Comparison=CTreeListNode<T>::Compare(*(Root->Data), *Data);
    if(Comparison==0) return Node=Root; // Data was already in the Tree
    if(Comparison>0) { // Go Left:
      Root->Left=Insert(Root->Left);
      if(GetBalance(Root)==2) { // Rebalance after returning from the Left:
        if(Root->Left->Right && (CTreeListNode<T>::Compare(*(Root->Left->Data), *Data)<0)) Root->Left=Root->Left->RotateLeft();
        Root=Root->RotateRight();
      }
    }else{ // Go Right:
      Root->Right=Insert(Root->Right);
      if(GetBalance(Root)==-2) { // Rebalance after returning from the Right:
        if(Root->Right->Left && (CTreeListNode<T>::Compare(*(Root->Right->Data), *Data)>0)) Root->Right=Root->Right->RotateRight();
        Root=Root->RotateLeft();
    } }
    Root->SetDepth();
    return Root;
  }

  int GetBalance(CTreeListNode<T>* Root) {
    return (Root->Left  ? Root->Left ->Depth : 0)
         - (Root->Right ? Root->Right->Depth : 0);
  }

  CTreeListNode<T>* GetNode(const T* data) { // return 0 if not found
    CTreeListNode<T>* it=Tree;
    if(List) {for(Comparison=0; it &&  (Comparison<=0); it=it->Right         ) if((Comparison=CTreeListNode<T>::Compare(*(it->Data), *data))==0) return it;}
    else     {for(            ; it; it=(Comparison<0  ? it->Right : it->Left)) if((Comparison=CTreeListNode<T>::Compare(*(it->Data), *data))==0) return it;}
    return 0;
  }
public:
  bool Find(T& Data) {return Find(&Data);}
  bool Find(T* Data) {return GetNode(Data)!=0;}

  void DeleteFirst(bool DeleteData=true) {if(Tree) Delete(GetFirst(), DeleteData);}
  bool Delete(T* data, bool DeleteData=true) {
    if(Tree==0) return false;
    Data=data; // Note what to search for during recursion
    if(!List) {
      Node=0; // Used to store the location of the Node to delete when finding that Node's previous node.
      Tree=Delete(Tree, DeleteData);
      return !Comparison;
    }
    CTreeListIterator<T> it(this);
    if(!it.Find(data)) return false;
    Node=it.it;
    if((Node==Tree) && !Node->Left && !Node->Right) {
      if(!DeleteData) Node->Data=0;
      Empty();
    }else{
      if(Node->Left)  Node-> Left->Right=Node->Right;
      else Tree=Node->Right;
      if(Node->Right) Node->Right->Left =Node->Left;
      if(!DeleteData) Node->Data=0;
      delete Node;
      --Count;
    }
    return true;
  }
private: /* Deleting involves a search and swap when the Node to be deleted has both children.
The "shape" of the following routine has been designed to let this happen naturally.
When a Node with both children needs deleting, [Node] is set to point to it and [Comparison] is altered to hit the search and swap sections.
So the if(Comparison...) blocks don't have "else" between them, because Comparison changes and the program may flow through more than one "if" block. */
  CTreeListNode<T>* Delete(CTreeListNode<T>* Root, bool DeleteData=true) { // Recursive Search, Delete and Re-balance:
    Comparison=(Node ? -1 : CTreeListNode<T>::Compare(*(Root->Data), *Data)); // If Node!=0 GoRight to get to Swap
    if(Comparison<0) { // Go Right
      if(Root->Right) {
        Root->Right=Delete(Root->Right); // Recurse
        if(GetBalance(Root)==2) { // Back from visiting Right where a Node got deleted:
          if(Root->Right && Root->Right->Right && GetBalance(Root->Right)<0) Root->Right=Root->Right->RotateLeft();
          Root=Root->RotateRight();
        }else Root->SetDepth();
        return Root;
      }else if(Node==0) return Root; // Node not found: do nothing.
       else{ // Found Node's Previous for a Swap:
        T* t=Node->Data; Node->Data=Root->Data; Root->Data=t; // Swap the Data pointers
        Node=0; // Back to normal Delete
        Comparison=0; // Cancel finding Node's previous and fall through to Delete Root.
    } }
    if(Comparison==0) { // Delete Root:
      if(!Root->Left ^ !Root->Right) { // node to delete has one child
        if(Root->Right) Node=Root->Right; // node to delete only has a right child
        else            Node=Root->Left;  // node to delete only has a left child
        if(!DeleteData) Root->Data=0;
        delete Root;
        --Count;
        return Node;
      }else if(Root->Left) { // node to delete has both children
        Node=Root; // We have to replace Node with the previous Node in order, which is Left's Right-most Node which we will now look for...
        Comparison=1; // Now Go Left and start searching for this Node's previous Node (in Compare(...) order)
      }else{ // node to delete has no children
        if(!DeleteData) Root->Data=0;
        delete Root;
        --Count;
        return 0;
    } }
    //(Comparison>0) Go Left
    if(!Root->Left) return Root; // Node not found: do nothing.
    Root->Left=Delete(Root->Left); // Recurse
    if(GetBalance(Root)==-2) { // Back from visiting Left where a Node got deleted:
      if(Root->Left && Root->Left->Left && GetBalance(Root->Left)<0) Root->Left=Root->Left->RotateRight();
      Root=Root->RotateLeft();
    }else Root->SetDepth();
    return Root;
  }
};

//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> CTreeListIterator <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

template <class T>
class CTreeListIterator {
  friend class CTreeList<T>;
private:
  CTreeListNode<T>* it;
  CTreeList    <T>* Tree;
public:
  CTreeListIterator() : Tree(0), it(0) {}
  CTreeListIterator(CTreeList<T>& Tree) : Tree(&Tree), it(0) {Home();}
  CTreeListIterator(CTreeList<T>* Tree) : Tree( Tree), it(0) {Home();}
  void Set(CTreeList<T>& _Tree) {Set(&_Tree);}
  void Set(CTreeList<T>* _Tree) {Tree=_Tree; it=0; Home();}
private:
  CTreeListIterator(CTreeList<T>* Tree, CTreeListNode<T>* Node) : Tree(Tree), it(Node) {}
  void Set(CTreeList<T>* _Tree, CTreeListNode<T>* Node) {Tree=_Tree; it=Node;}
public:
  virtual ~CTreeListIterator() {}
  T*    GetData() const {return it ? it->Data : 0;}
  bool  IsValid() const {return it!=0;}
  bool operator==(const CTreeListIterator<T>& _it) const {return it==_it.it;}
  bool operator!=(const CTreeListIterator<T>& _it) const {return it!=_it.it;}
// operators to allow the iterator to be accessed as if it were the data:
                              operator   T*() const {return it ?   it->Data  : 0;}
// Leads to ambiguity         operator   T&() const {return      *(it->Data)    ;} // No need to ASSERT, it's going to do that anyway if it==0
                          T&  operator    *() const {return      *(it->Data)    ;} // No need to ASSERT, it's going to do that anyway if it==0
                          T** operator    &() const {return it ? &(it->Data) : 0;}
                          T*  operator   ->() const {return it ?   it->Data  : 0;}
                              operator bool() const {return it!=0;}
                         bool operator    !() const {return it==0;}
// Iteration operators:
  const CTreeListIterator<T>& operator    ++() {Next(); return *this;}
  const CTreeListIterator<T>& operator    --() {Prev(); return *this;}
  const CTreeListIterator<T>  operator ++(int) {CTreeListIterator<T> tit(*this); operator++(); return tit;}
  const CTreeListIterator<T>  operator --(int) {CTreeListIterator<T> tit(*this); operator--(); return tit;}
// Comparison operators to use the iterator as if it were the data type:
  bool operator==(const T& data) const {return CTreeListNode<T>::Compare(*(it->Data), *data)== 0;}
  bool operator!=(const T& data) const {return CTreeListNode<T>::Compare(*(it->Data), *data)!= 0;}
  bool operator< (const T& data) const {return CTreeListNode<T>::Compare(*(it->Data), *data)==-1;}
  bool operator> (const T& data) const {return CTreeListNode<T>::Compare(*(it->Data), *data)== 1;}
  bool operator<=(const T& data) const {return CTreeListNode<T>::Compare(*(it->Data), *data)!= 1;}
  bool operator>=(const T& data) const {return CTreeListNode<T>::Compare(*(it->Data), *data)!=-1;}
/* Not used (simple is safest) but these would let you use compare a node with the Iterator's Node quickly.
private: // private because they're dealing with Node pointers which should only be used by the classes in this file.
  bool operator==(const CTreeListNode<T>* Node) const {return CTreeListNode<T>::Compare(*(it->Data), *Node->Data)== 0;}
  bool operator!=(const CTreeListNode<T>* Node) const {return CTreeListNode<T>::Compare(*(it->Data), *Node->Data)!= 0;}
  bool operator< (const CTreeListNode<T>* Node) const {return CTreeListNode<T>::Compare(*(it->Data), *Node->Data)==-1;}
  bool operator> (const CTreeListNode<T>* Node) const {return CTreeListNode<T>::Compare(*(it->Data), *Node->Data)== 1;}
  bool operator<=(const CTreeListNode<T>* Node) const {return CTreeListNode<T>::Compare(*(it->Data), *Node->Data)!= 1;}
  bool operator>=(const CTreeListNode<T>* Node) const {return CTreeListNode<T>::Compare(*(it->Data), *Node->Data)!=-1;}
  CTreeListNode<T>* operator->() {return it;}
*/
public:
  void  Home() {if(Tree) {if(it=Tree->Tree) while(it->Left ) it=it->Left ;} else it=0;}
  void   End() {if(Tree) {if(it=Tree->Tree) while(it->Right) it=it->Right;} else it=0;}
  bool  Left() {return it && it->Left  ? it=it->Left  : false;}
  bool Right() {return it && it->Right ? it=it->Right : false;}

  bool IsFirst() const {return GetFirst(Tree->Tree)==it;}
  bool IsLast () const {return  GetLast(Tree->Tree)==it;}

  bool Insert(T* data, bool AutoDelete=true) { // Insert a Node and leave Iterator pointing at it.
    bool OK=Tree->Insert(data,AutoDelete);
    it=Tree->Node;
    return OK;
  }

  bool  Find(const T& t) {return Find(&t);}
  bool  Find(const T* t) {return (it=Tree->GetNode(t))!=0;}

  bool Delete(bool MoveNext=true, bool DeleteData=true) {
    if(it==0) return false;
    CTreeListNode<T>* Node=it;
    if(MoveNext) Next();
    else         Prev();
    if(it==0) { // Have to try going the other way
      it=Node;
      if(MoveNext) Prev();
      else         Next();
    }
    Data=GetData(); // Found the data to point to after the delete
    if(!Tree->Delete(Node->Data, DeleteData)) { // Not found to delete!
      it=0; // Big problem so invalidate it.
      ASSERT(0);
      return false;
    }
    if(Data) Find(Data);
    return true;
  }

  bool Next() {
    if(it==0) Home();
    else if(Tree->List) it=it->Right;
    else if(it->Right)  it=GetFirst(it->Right);
    else {
      Data=it->Data;
      it=0;
      GetLeftSubtreeParent(Tree->Tree);
    }
    return IsValid();
  }

  bool Prev() {
    if(it==0) End();
    else if(Tree->List) it=it->Left;
    else if(it->Left)   it=GetLast(it->Left);
    else {
      Data=it->Data;
      it=0;
      GetRightSubtreeParent(Tree->Tree);
    }
    return IsValid();
  }

private:
  CTreeListNode<T>* GetFirst(CTreeListNode<T>* Root) const {while(Root->Left ) Root=Root->Left ; return Root;}
  CTreeListNode<T>* GetLast (CTreeListNode<T>* Root) const {while(Root->Right) Root=Root->Right; return Root;}

  T*  Data; // Used by recursive routines as "globals":
  int Comparison;
  void GetLeftSubtreeParent(CTreeListNode<T>* Node) {
    ASSERT(Node); // If you're crashing out here it's because your Comparison function is dependent on something which is CHANGING. ie. your sort order is changing as you are Inserting Nodes. Use a constant sort orders, create a new TreeList with the final sort order and copy the nodes across, or Morph2List().
    Comparison=CTreeListNode<T>::Compare(*Data, *Node->Data);
    if(Comparison> 0) GetLeftSubtreeParent(Node->Right);
    if(Comparison>=0) return;
    GetLeftSubtreeParent(Node->Left);
    if(it==0) it=Node;
  }
  void GetRightSubtreeParent(CTreeListNode<T>* Node) {
    ASSERT(Node); // If you're crashing out here it's because your Comparison function is dependent on something which is CHANGING. ie. your sort order is changing as you are Inserting Nodes. Use a constant sort orders, create a new TreeList with the final sort order and copy the nodes across, or Morph2List().
    Comparison=CTreeListNode<T>::Compare(*Data, *Node->Data);
    if(Comparison< 0) GetRightSubtreeParent(Node->Left);
    if(Comparison<=0) return;
    GetRightSubtreeParent(Node->Right);
    if(it==0) it=Node;
  }
};

#endif // ndef TreeListh