// TreeListTester.cpp

#include "stdafx.h"
#include <conio.h>
#include <iostream.h>
#include <fstream.h>
#include <string>
#include "TreeList.h"


#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

CWinApp theApp;

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

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

class CTreeListTagger: public CTreeListNodeBehaviour<CString> {
private:
  void Behaviour(CString& S) {S='<'+S+'>';}
};

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;}
};

struct CDump: public CTreeListNodeBehaviour<CString> {
  CString Tree;
private:
  virtual void PreOrder (CString** t, CTreeListNode<CString>** Left, CTreeListNode<CString>** Right, int Depth) {
    if(*Left || *Right) Tree+="(";
  }
  virtual void InOrder  (CString** t, CTreeListNode<CString>** Left, CTreeListNode<CString>** Right, int Depth) {
    if(*Left)  Tree+="/";
               Tree+=**t;
    if(*Right) Tree+="\\";
  }
  virtual void PostOrder(CString** t, CTreeListNode<CString>** Left, CTreeListNode<CString>** Right, int Depth) {
    if(*Left || *Right) Tree+=")";
  }
};

int __cdecl _tmain(int argc, TCHAR* argv[], TCHAR* envp[]) {
  if(!AfxWinInit(::GetModuleHandle(NULL), NULL, ::GetCommandLine(), 0)) return 1;
  { // {Scope}  Example 1
    CTreeList<CInteger> TreeList;
    VERIFY( TreeList.Insert(new CInteger(1)));
    VERIFY( TreeList.Insert(new CInteger(2)));
    VERIFY(!TreeList.Insert(new CInteger(2))); // Returns 0 because 2 is already inserted (Duplicates are not stored).
    VERIFY( TreeList.Insert(new CInteger(3)));
    for(CTreeListIterator<CInteger> it(TreeList); it; ++it) TRACE("%u ",it.GetData()->i);
    TRACE("\r\n");
  }
  { // {Scope}  Example 2
    ifstream iStream("t.txt");
    ofstream oStream("t1.txt");
    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() its just easier to write!
    it.End();
    while(it) oStream << it--.GetData()->String.c_str() << endl;
  }
  { // {Scope}  Example 3
    CFile IFile,OFile;
    if(!IFile.Open("t.txt",CFile::modeRead|CFile::shareDenyNone)) return false;
    CArchive IAr(&IFile, CArchive::load);
    if(!OFile.Open("t2.txt",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()) its just easier to write!
    TreeList.Morph2Tree(); // I'm pretty sure this isn't ever a good idea... But I implemented it incase someone knows better...
    it.End();
    while(it) OAr.WriteString(*(it--.GetData())+"\r\n");
  }
  { // {Scope}  Example 4
    CTreeList<CString> TreeList;
    TreeList.Morph2List();
    for(char c='a'; c<'e'; ++c) TreeList.Insert(new CString(c));
    TreeList.ForAll(CTreeListTagger()); // Create the CTreeListTagger on the stack
    for(CTreeListIterator<CString> it(TreeList); it; ++it) cout << *it << endl;
    CTreeListNodeCounter NodeCounter;
    TreeList.ForAll(NodeCounter);
    cout << NodeCounter.GetCount() << " Nodes." << endl;
  }
  { // {Scope}
    CTreeList<CString> TreeList;
    VERIFY(TreeList.IsEmpty());
// Test Empty Mode Changes
    VERIFY(!TreeList.IsList());
    TreeList.Morph2List();
    VERIFY(TreeList.IsList());
    TreeList.Morph2Tree();
    VERIFY(!TreeList.IsList());
// Test Insertion
    VERIFY( TreeList.GetDepth()==0);
    VERIFY( TreeList.IsEmpty());
    VERIFY( TreeList.Insert(new CString("3")));
    VERIFY(!TreeList.IsEmpty());
    VERIFY( TreeList.GetNodeCount()==1);
    VERIFY( TreeList.GetCount    ()==1);
    VERIFY( TreeList.GetDepth    ()==1);
    VERIFY( TreeList.Insert(new CString("4")));
    VERIFY( TreeList.GetNodeCount()==2);
    VERIFY( TreeList.GetCount    ()==2);
    VERIFY( TreeList.GetDepth    ()==2);
    VERIFY(!TreeList.Insert(new CString("4")));
    VERIFY( TreeList.GetNodeCount()==2); // Don't allow duplicates
    VERIFY( TreeList.GetCount    ()==2);
    VERIFY( TreeList.GetDepth    ()==2);
    VERIFY( TreeList.Insert(new CString("7"))); // L Rotation on 3
    VERIFY( TreeList.GetNodeCount()==3);
    VERIFY( TreeList.GetCount    ()==3);
    VERIFY( TreeList.GetDepth    ()==2);
    VERIFY( TreeList.Insert(new CString("6")));
    VERIFY( TreeList.GetNodeCount()==4);
    VERIFY( TreeList.GetCount    ()==4);
    VERIFY( TreeList.GetDepth    ()==3);
    VERIFY( TreeList.Insert(new CString("5"))); // R Rotation on 7
    VERIFY( TreeList.GetNodeCount()==5);
    VERIFY( TreeList.GetCount    ()==5);
    VERIFY( TreeList.GetDepth    ()==3);
    VERIFY( TreeList.Insert(new CString("1")));
    VERIFY( TreeList.GetNodeCount()==6);
    VERIFY( TreeList.GetCount    ()==6);
    VERIFY( TreeList.GetDepth    ()==3);
    VERIFY( TreeList.Insert(new CString("2"))); // LR Rotation: 1 Left, 3 Right
    VERIFY( TreeList.GetNodeCount()==7);
    VERIFY( TreeList.GetCount    ()==7);
    VERIFY( TreeList.GetDepth    ()==3);
    VERIFY( TreeList.Insert(new CString("9")));
    VERIFY( TreeList.GetNodeCount()==8);
    VERIFY( TreeList.GetCount    ()==8);
    VERIFY( TreeList.GetDepth    ()==4);
    VERIFY( TreeList.Insert(new CString("8"))); // RL Rotation: 9 Right, 7 Left
    VERIFY( TreeList.GetNodeCount()==9);
    VERIFY( TreeList.GetCount    ()==9);
    VERIFY( TreeList.GetDepth    ()==4);
/*
   4
   ^
 2   6
 ^   ^
1 3 5 8
      ^
     7 9
*/  CDump Dump;
    { // {Scope} Stack/Queue Iteratorless Functions:
      TreeList.ForAll(Dump); cout << Dump.Tree << endl;
      VERIFY(Dump.Tree=="((1/2\\3)/4\\(5/6\\(7/8\\9)))");

      CTreeList<CString> TreeList2(TreeList); // Copy Constuctor
      TreeList2.ForAll(CDump()); cout << endl;
      VERIFY( TreeList2.GetNodeCount()==9);
      VERIFY( TreeList2.GetCount    ()==9);
      VERIFY( TreeList2.GetDepth    ()==4);
      VERIFY(*TreeList2.GetFirst    ()=="1");
      VERIFY(*TreeList2.GetLast     ()=="9");

      for(int i=1; i<=9; ++i) {
        VERIFY(atoi(*TreeList2.GetFirst())==i);
        TreeList2.DeleteFirst();
        VERIFY(TreeList2.GetNodeCount()==9-i);
        VERIFY(TreeList2.GetCount    ()==9-i);
        Dump.Tree.Empty();
        TreeList2.ForAll(Dump); cout << Dump.Tree << endl;
      }
      VERIFY(TreeList2.IsEmpty());
/*
((1/2\3)/4\(5/6\(7/8\9)))
((1/2\3)/4\(5/6\(7/8\9)))
((2\3)/4\(5/6\(7/8\9)))
((3/4\5)/6\(7/8\9))
((4\5)/6\(7/8\9))
(5/6\(7/8\9))
((6\7)/8\9)
(7/8\9)
(8\9)
9 */
    }
/*
       12
      /  \
     8   16
     ^    ^
    5 9 15 19
   /    /  /\
  2    14 17 25
              \
               32
*/  { // {Scope} Deletion:
      CTreeList<CString> TreeList2; // Copy Constuctor
      VERIFY(TreeList2.Insert(new CString("12")));
      VERIFY(TreeList2.Insert(new CString(" 8")));
      VERIFY(TreeList2.Insert(new CString("16")));
      VERIFY(TreeList2.Insert(new CString(" 5")));
      VERIFY(TreeList2.Insert(new CString(" 9")));
      VERIFY(TreeList2.Insert(new CString("15")));
      VERIFY(TreeList2.Insert(new CString("19")));
      VERIFY(TreeList2.Insert(new CString(" 2")));
      VERIFY(TreeList2.Insert(new CString("14")));
      VERIFY(TreeList2.Insert(new CString("17")));
      VERIFY(TreeList2.Insert(new CString("25")));
      VERIFY(TreeList2.Insert(new CString("32")));
      Dump.Tree.Empty();
      TreeList2.ForAll(Dump); cout << Dump.Tree << endl;
      VERIFY(Dump.Tree=="((( 2/ 5)/ 8\\ 9)/12\\((14/15)/16\\(17/19\\(25\\32))))");
      CTreeListIterator<CString> it(TreeList2);
      it.Find(" 9"); // Requires 8>>>R 12<<<L
      it.Delete();
      Dump.Tree.Empty();
      TreeList2.ForAll(Dump); cout << Dump.Tree << endl;
      VERIFY(Dump.Tree=="((( 2/ 5\\ 8)/12\\(14/15))/16\\(17/19\\(25\\32)))");
      it.Find("16");
      it.Delete();
      Dump.Tree.Empty();
      TreeList2.ForAll(Dump); cout << Dump.Tree << endl;
      VERIFY(Dump.Tree=="((( 2/ 5\\ 8)/12\\14)/15\\(17/19\\(25\\32)))");
    }
// Test Insertion and Iteration in Tree Mode
    CTreeListIterator<CString> it(TreeList);
    VERIFY(              it=="1");
    VERIFY( it.Next() && it=="2");
    VERIFY( it.Next() && it=="3");
    VERIFY( it.Next() && it=="4");
    VERIFY( it.Next() && it=="5");
    VERIFY( it.Next() && it=="6");
    VERIFY( it.Next() && it=="7");
    VERIFY( it.Next() && it=="8");
    VERIFY( it.Next() && it=="9");
    VERIFY(!it.Next() && it.GetData()==0);
    VERIFY( it.Prev() && it=="9");
    VERIFY( it.Prev() && it=="8");
    VERIFY( it.Prev() && it=="7");
    VERIFY( it.Prev() && it=="6");
    VERIFY( it.Prev() && it=="5");
    VERIFY( it.Prev() && it=="4");
    VERIFY( it.Prev() && it=="3");
    VERIFY( it.Prev() && it=="2");
    VERIFY( it.Prev() && it=="1");
    VERIFY(!it.Prev() && it.GetData()==0);
// Test Find
    it.Find(CString("0")); VERIFY(it.GetData()==0);
    it.Find(CString("1")); VERIFY(it=="1");  // First
    it.Find(CString("4")); VERIFY(it=="4");  // Root
    it.Find(CString("5")); VERIFY(it=="5");  // Mid
    it.Find(CString("9")); VERIFY(it=="9");  // Last
// Test Deletion
    VERIFY(it.Delete());                     // No children
    VERIFY(it=="8");                         // MoveNext should fail and so we get left pointing to the previous Node
    VERIFY( TreeList.GetNodeCount()==8);
    VERIFY( TreeList.GetDepth()==4);
    VERIFY(!TreeList.Delete(&CString("9"))); // Already deleted so should return false
    VERIFY( TreeList.Delete(&CString("8"))); // Left Child
    VERIFY( TreeList.GetNodeCount()==7);
    VERIFY( TreeList.GetDepth()==3);
    VERIFY( TreeList.Delete(&CString("6"))); // Both Children (Previous Node to swap with is just Left)
    VERIFY( TreeList.GetNodeCount()==6);
    VERIFY( TreeList.GetDepth()==3);
    VERIFY( TreeList.Delete(&CString("5"))); // Right Child
    VERIFY( TreeList.GetNodeCount()==5);
    VERIFY( TreeList.GetDepth()==3);
    VERIFY( TreeList.Delete(&CString("4"))); // Root (Both Children (Previous Node to swap with is Left's Right))
    VERIFY( TreeList.GetNodeCount()==4);
    VERIFY( TreeList.GetDepth()==3);
// Test List Mode
    VERIFY(!TreeList.IsList());
    TreeList.Morph2List();
    VERIFY(TreeList.IsList());
// Test List conversion and Iterator
    it.Set(TreeList);
    VERIFY(              it=="1");
    VERIFY( it.Next() && it=="2");
    VERIFY( it.Next() && it=="3");
    VERIFY( it.Next() && it=="7");
    VERIFY(!it.Next() && it.GetData()==0);
    VERIFY( it.Prev() && it=="7");
    VERIFY( it.Prev() && it=="3");
    VERIFY( it.Prev() && it=="2");
    VERIFY( it.Prev() && it=="1");
    VERIFY(!it.Prev() && it.GetData()==0);
// Test Insertion
    VERIFY( TreeList.Insert(new CString("8"))); // End
    VERIFY( TreeList.GetNodeCount()==5);
    VERIFY( TreeList.GetDepth()==0);
    VERIFY( TreeList.Insert(new CString("0"))); // Start
    VERIFY( TreeList.GetNodeCount()==6);
    VERIFY( TreeList.GetDepth()==0);
    VERIFY( TreeList.Insert(new CString("4"))); // Middle
    VERIFY( TreeList.GetNodeCount()==7);
    VERIFY( TreeList.GetDepth()==0);
    VERIFY(!TreeList.Insert(new CString("4"))); // Don't insert duplicates
    VERIFY( TreeList.GetNodeCount()==7);
    VERIFY( TreeList.GetDepth()==0);
// Test Find
    it.Find(CString("5")); VERIFY(it.GetData()==0);
    it.Find(CString("4")); VERIFY(it=="4"); // Mid
    it.Find(CString("8")); VERIFY(it=="8"); // Last
    it.Find(CString("0")); VERIFY(it=="0"); // First
// Test Deletion
    VERIFY(it.Delete(false));                // First
    VERIFY(it=="1");                         // MovePrev should fail and so we get left pointing to the next Node
    VERIFY( TreeList.GetNodeCount()==6);
    VERIFY( TreeList.GetDepth()==0);
    VERIFY(!TreeList.Delete(&CString("0"))); // Already deleted so should return false
    VERIFY( TreeList.Delete(&CString("8"))); // Last
    VERIFY( TreeList.GetNodeCount()==5);
    VERIFY( TreeList.GetDepth()==0);
    VERIFY( TreeList.Delete(&CString("3"))); // Mid
    VERIFY( TreeList.GetNodeCount()==4);
    VERIFY( TreeList.GetDepth()==0);
// 1 2 4 7
// Test Copy constructor
    CTreeList<CString> TreeListCopy(TreeList);
    VERIFY(TreeListCopy.IsList());
    VERIFY(TreeListCopy.GetDepth()==0);
// Test Tree Mode
    VERIFY(TreeList.IsList());
    TreeList.Morph2Tree();
    VERIFY(!TreeList.IsList());
// Test Copy constructor
    CTreeList<CString> TreeListCopy1(TreeList);
    VERIFY(!TreeListCopy1.IsList());
    VERIFY(TreeListCopy1.GetDepth()==3);
// Test Iterator Copy constructor (Default Implementation)
    CTreeListIterator<CString> it1(++it);
    VERIFY(it==it1);
    VERIFY(it1=="4");
    VERIFY(it.GetData()==it1.GetData());
    VERIFY(*(it.GetData())==*(it1.GetData()));
// Test Iterator operator= (Default Implementation)
    CTreeListIterator<CString> it2(TreeList);
    VERIFY(it2=="1");
    it1=it2;
    VERIFY(it1==it2);
    VERIFY(it1=="1");
    VERIFY(it1.GetData()==it2.GetData());
    VERIFY(*(it1.GetData())==*(it2.GetData()));
// Test Iterator operator++
    it=it1++;
    VERIFY(*( it.GetData())=="1");
    VERIFY(*(it1.GetData())=="2");
// Test remaining Iterator Deletes
    VERIFY( it1.Delete(false));
    VERIFY( it1=="1");                    // MovePrev should leave us looking at the previous Node
    VERIFY( TreeList.GetNodeCount()==3);
    VERIFY( TreeList.GetDepth()==2);
    VERIFY( it1.Delete());
    VERIFY( it1=="4");                    // MoveNext should leave us looking at the next Node
    VERIFY( TreeList.GetNodeCount()==2);
    VERIFY( TreeList.GetDepth()==2);
    VERIFY( it1.Delete());
    VERIFY( it1=="7");
    VERIFY( TreeList.GetNodeCount()==1);
    VERIFY( TreeList.GetDepth()==1);
    VERIFY( it1.Delete());                // Last Node
    VERIFY( it1.GetData()==0);
    VERIFY( TreeList.GetNodeCount()==0);
    VERIFY( TreeList.GetDepth()==0);
    VERIFY(!it1.Delete());                // No Nodes!
    VERIFY( it1.GetData()==0);
    VERIFY( TreeList.GetNodeCount()==0);
    VERIFY( TreeList.GetDepth()==0);
  }
  CTreeList<CInteger> Tree;
  unsigned Nodes=1<<20;
  cout << "Inserting " << Nodes << " Random Nodes" << endl;
  srand(0); // Since this is a value-dependent test, keep the numbers the same each time.
  DWORD Time=GetTickCount();
  while(Nodes--) Tree.Insert(new CInteger((rand()<<16)|rand()));
  cout << " CTreeList Insertion Time: " << GetTickCount()-Time << "ms" << endl;
  Time=GetTickCount();
  cout << "Nodes pre-Morph: " << Tree.GetCount() << " = " << Tree.GetNodeCount() << endl;
  cout << " NodeCount Time: " << GetTickCount()-Time << "ms" << endl;
  Time=GetTickCount();
  Tree.Morph2List();
  cout << "  Morph2List Time: " << GetTickCount()-Time << "ms" << endl;
  Time=GetTickCount();
  cout << " Nodes post-Morph: " << Tree.GetCount() << " = "  << Tree.GetNodeCount() << endl;
  cout << " NodeCount Time: " << GetTickCount()-Time << "ms" << endl;
  Time=GetTickCount();
  Tree.Morph2Tree();
  cout << "Morph2Tree Time: " << GetTickCount()-Time << "ms" << endl;
  Time=GetTickCount();
  cout << " Nodes post-Morph: " << Tree.GetCount() << " = "  << Tree.GetNodeCount() << endl;
  cout << " NodeCount Time: " << GetTickCount()-Time << "ms" << endl;
  srand(0); // Since this is a value-dependent test, keep the numbers the same each time.
  Nodes=1<<19;
  cout << "Randomly Deleting " << Nodes << " Random Nodes" << endl;
  Time=GetTickCount();
  for(CInteger Int(1); Nodes--; Int.i=(rand()<<16)|rand()) Tree.Delete(&Int);
  cout << " CTreeList Deletion Time: " << GetTickCount()-Time << "ms" << endl;
  cout << "  Nodes post-Delete: " << Tree.GetCount() << " = "  << Tree.GetNodeCount() << endl;
  cout << "  NodeCount Time: " << GetTickCount()-Time << "ms" << endl;
  Time=GetTickCount();
  while(!Tree.IsEmpty()) Tree.DeleteFirst();
  cout << " CTreeList Deletion Time: " << GetTickCount()-Time << "ms" << endl;
  cout << "  Nodes post-Delete: " << Tree.GetCount() << " = "  << Tree.GetNodeCount() << endl;
  cout << "  NodeCount Time: " << GetTickCount()-Time << "ms" << endl;

  cout << "Press any key to exit..." << endl;
  cout << endl;
  getch();
  return 0;
}