# Example of use of collection classes

    // @(#)root/test:$Name:  $:$Id: tcollex.cxx,v 1.7 2002/01/24 11:39:31 rdm Exp $
    // Author: Fons Rademakers   19/08/96

    #include <stdlib.h>

    #include "Riostream.h"
    #include "TString.h"
    #include "TObjString.h"
    #include "TSortedList.h"
    #include "TObjArray.h"
    #include "TOrdCollection.h"
    #include "THashTable.h"
    #include "TBtree.h"
    #include "TStopwatch.h"

    // To focus on basic collection protocol, this sample program uses
    // simple classes inheriting from TObject. One class, TObjString, is a
    // collectable string class (a TString wrapped in a TObject) provided
    // by the ROOT system. The other class we define below, is an integer
    // wrapped in a TObject, just like TObjString.

    // TObjNum is a simple container for an integer.
    class TObjNum : public TObject {
    private:
       int  num;

    public:
       TObjNum(int i = 0) : num(i) { }
       ~TObjNum() { Printf("~TObjNum = %d", num); }
       void    SetNum(int i) { num = i; }
       int     GetNum() { return num; }
       void    Print(Option_t *) const { Printf("TObjNum = %d", num); }
       ULong_t Hash() const { return num; }
       Bool_t  IsEqual(const TObject *obj) const { return num == ((TObjNum*)obj)->num; }
       Bool_t  IsSortable() const { return kTRUE; }
       Int_t   Compare(const TObject *obj) const { if (num > ((TObjNum*)obj)->num)
                                          return 1;
                                       else if (num < ((TObjNum*)obj)->num)
                                          return -1;
                                       else
                                          return 0; }
    };

    void Test_TObjArray()
    {

       Printf(
       "////////////////////////////////////////////////////////////////n"
       "// Test of TObjArray                                          //n"
       "////////////////////////////////////////////////////////////////"
       );

       // Array of capacity 10, Add() will automatically expand the array if necessary.
       TObjArray  a(10);

       Printf("Filling TObjArray");
       a.Add(new TObjNum(1));            // add at next free slot, pos 0
       a[1] = new TObjNum(2);            // use operator[], put at pos 1
       TObjNum *n3 = new TObjNum(3);
       a.AddAt(n3,2);                    // add at position 2
       a.Add(new TObjNum(4));            // add at next free slot, pos 3
       a.AddLast(new TObjNum(10));       // add at pos 4
       TObjNum n6(6);                    // stack based TObjNum
       a.AddAt(&n6,5);                   // add at pos 5
       a[6] = new TObjNum(5);            // add at respective positions
       a[7] = new TObjNum(8);
       a[8] = new TObjNum(7);
    //   a[10] = &n6;                    // gives out-of-bound error

       Printf("Print array");
       a.Print();                        // invoke Print() of all objects

       Printf("Sort array");
       a.Sort();
       for (int i = 0; i < a.Capacity(); i++)  // typical way of iterating over array
          if (a[i])
             a[i]->Print();      // can also use operator[] to access elements
          else
             Printf("%d empty slot", i);

       Printf("Use binary search to get position of number 6");
       Printf("6 is at position %d", a.BinarySearch(&n6));

       Printf("Find number before 6");
       a.Before(&n6)->Print();

       Printf("Find number after 3");
       a.After(n3)->Print();

       Printf("Remove 3 and print list again");
       a.Remove(n3);
       delete n3;
       a.Print();

       Printf("Iterate forward over list and remove 4 and 7");

       // TIter encapsulates the actual class iterator. The type of iterator
       // used depends on the type of the collection.
       TIter next(&a);

       TObjNum *obj;
       while ((obj = (TObjNum*)next()))     // iterator skips empty slots
          if (obj->GetNum() == 4) {
             a.Remove(obj);
             delete obj;
          }

       // Reset the iterator and loop again
       next.Reset();
       while ((obj = (TObjNum*)next()))
          if (obj->GetNum() == 7) {
             a.Remove(obj);
             delete obj;
          }

       Printf("Iterate backward over list and remove 2");
       TIter next1(&a, kIterBackward);
       while ((obj = (TObjNum*)next1()))
          if (obj->GetNum() == 2) {
             a.Remove(obj);
             delete obj;
          }

       Printf("Delete remainder of list: 1,5,8,10 (6 not deleted since not on heap)");

       // Delete heap objects and clear list. Attention: do this only when you
       // own all objects stored in the collection. When you stored aliases to
       // the actual objects (i.e. you did not create the objects) use Clear()
       // instead.
       a.Delete();

       Printf("Delete stack based objects (6)");
    }

    void Test_TOrdCollection()
    {
       Printf(
       "////////////////////////////////////////////////////////////////n"
       "// Test of TOrdCollection                                     //n"
       "////////////////////////////////////////////////////////////////"
       );

       // Create collection with default size, Add() will automatically expand
       // the collection if necessary.
       TOrdCollection  c;

       Printf("Filling TOrdCollection");
       c.Add(new TObjString("anton"));      // add at next free slot, pos 0
       c.AddFirst(new TObjString("bobo"));  // put at pos 0, bump anton to pos 1
       TObjString *s3 = new TObjString("damon");
       c.AddAt(s3,1);                       // add at position 1, bump anton to pos 2
       c.Add(new TObjString("cassius"));    // add at next free slot, pos 3
       c.AddLast(new TObjString("enigma")); // add at pos 4
       TObjString s6("fons");               // stack based TObjString
       c.AddBefore(s3,&s6);                 // add at pos 1
       c.AddAfter(s3, new TObjString("gaia"));

       Printf("Print collection");
       c.Print();                           // invoke Print() of all objects

       Printf("Sort collection");
       c.Sort();
       c.Print();

       Printf("Use binary search to get position of string damon");
       Printf("damon is at position %d", c.BinarySearch(s3));

       Printf("Find str before fons");
       c.Before(&s6)->Print();

       Printf("Find string after damon");
       c.After(s3)->Print();

       Printf("Remove damon and print list again");
       c.Remove(s3);
       delete s3;
       c.Print();

       Printf("Iterate forward over list and remove cassius");
       TObjString *objs;
       TIter next(&c);
       while ((objs = (TObjString*)next()))     // iterator skips empty slots
          if (objs->String() == "cassius") {
             c.Remove(objs);
             delete objs;
          }

       Printf("Iterate backward over list and remove gaia");
       TIter next1(&c, kIterBackward);
       while ((objs = (TObjString*)next1()))
          if (objs->String() == "gaia") {
             c.Remove(objs);
             delete objs;
          }

       Printf("Delete remainder of list: anton,bobo,enigma (fons not deleted since not on heap)");
       c.Delete();                        // delete heap objects and clear list

       Printf("Delete stack based objects (fons)");
    }

    void Test_TList()
    {
       Printf(
       "////////////////////////////////////////////////////////////////n"
       "// Test of TList                                              //n"
       "////////////////////////////////////////////////////////////////"
       );

       // Create a doubly linked list.
       TList l;

       Printf("Filling TList");
       TObjNum *n3 = new TObjNum(3);
       l.Add(n3);
       l.AddBefore(n3, new TObjNum(5));
       l.AddAfter(n3, new TObjNum(2));
       l.Add(new TObjNum(1));
       l.AddBefore(n3, new TObjNum(4));
       TObjNum n6(6);                     // stack based TObjNum
       l.AddFirst(&n6);

       Printf("Print list");
       l.Print();

       Printf("Remove 3 and print list again");
       l.Remove(n3);
       delete n3;
       l.Print();

       Printf("Iterate forward over list and remove 4");
       TObjNum *obj;
       TIter next(&l);
       while ((obj = (TObjNum*)next()))
          if (obj->GetNum() == 4) l.Remove(obj);

       Printf("Iterate backward over list and remove 2");
       TIter next1(&l, kIterBackward);
       while ((obj = (TObjNum*)next1()))
          if (obj->GetNum() == 2) {
             l.Remove(obj);
             delete obj;
          }

       Printf("Delete remainder of list: 1, 5 (6 not deleted since not on heap)");
       l.Delete();

       Printf("Delete stack based objects (6)");
    }

    void Test_TSortedList()
    {
       Printf(
       "////////////////////////////////////////////////////////////////n"
       "// Test of TSortedList                                        //n"
       "////////////////////////////////////////////////////////////////"
       );

       // Create a sorted doubly linked list.
       TSortedList sl;

       Printf("Filling TSortedList");
       TObjNum *n3 = new TObjNum(3);
       sl.Add(n3);
       sl.AddBefore(n3,new TObjNum(5));
       sl.AddAfter(n3, new TObjNum(2));
       sl.Add(new TObjNum(1));
       sl.AddBefore(n3, new TObjNum(4));
       TObjNum n6(6);                     // stack based TObjNum
       sl.AddFirst(&n6);

       Printf("Print list");
       sl.Print();

       Printf("Delete all heap based objects (6 not deleted since not on heap)");
       sl.Delete();

       Printf("Delete stack based objects (6)");
    }

    void Test_THashTable()
    {
       Printf(
       "////////////////////////////////////////////////////////////////n"
       "// Test of THashTable                                         //n"
       "////////////////////////////////////////////////////////////////"
       );

       int i;

       // Create a hash table with an initial size of 20 (actually the next prime
       // above 20). No automatic rehashing.
       THashTable ht(20);

       Printf("Filling THashTable");
       Printf("Number of slots before filling: %d", ht.Capacity());
       for (i = 0; i < 1000; i++)
          ht.Add(new TObject);

       Printf("Average collisions: %f", ht.AverageCollisions());

       // rehash the hash table to reduce the collission rate
       ht.Rehash(ht.GetSize());

       Printf("Number of slots after rehash: %d", ht.Capacity());
       Printf("Average collisions after rehash: %f", ht.AverageCollisions());

       ht.Delete();

       // Create a hash table and trigger automatic rehashing when average
       // collision rate becomes larger than 5.
       THashTable ht2(20,5);

       Printf("Filling THashTable with automatic rehash when AverageCollisions>5");
       Printf("Number of slots before filling: %d", ht2.Capacity());
       for (i = 0; i < 1000; i++)
          ht2.Add(new TObject);

       Printf("Number of slots after filling: %d", ht2.Capacity());
       Printf("Average collisions: %f", ht2.AverageCollisions());

       Printf("nDelete all heap based objects");
       ht2.Delete();
    }

    void Test_TBtree()
    {
       Printf(
       "////////////////////////////////////////////////////////////////n"
       "// Test of TBtree                                             //n"
       "////////////////////////////////////////////////////////////////"
       );
       TStopwatch timer;      // create a timer
       TBtree     l;          // btree of order 3

       Printf("Filling TBtree");

       TObjNum *n3 = new TObjNum(3);
       l.Add(n3);
       l.AddBefore(n3,new TObjNum(5));
       l.AddAfter(n3, new TObjNum(2));
       l.Add(new TObjNum(1));
       l.AddBefore(n3, new TObjNum(4));
       TObjNum n6(6);                     // stack based TObjNum
       l.AddFirst(&n6);

       timer.Start();
       for (int i = 0; i < 50; i++)
          l.Add(new TObjNum(i));
       timer.Print();

       Printf("Print TBtree");
       l.Print();

       Printf("Remove 3 and print TBtree again");
       l.Remove(n3);
       l.Print();

       Printf("Iterate forward over TBtree and remove 4 from tree");
       TIter next(&l);
       TObjNum *obj;
       while ((obj = (TObjNum*)next()))
          if (obj->GetNum() == 4) l.Remove(obj);

       Printf("Iterate backward over TBtree and remove 2 from tree");
       TIter next1(&l, kIterBackward);
       while ((obj = (TObjNum*)next1()))
          if (obj->GetNum() == 2) l.Remove(obj);

       Printf("nDelete all heap based objects");
       l.Delete();

       Printf("Delete stack based objects (6)");
    }

    int main()
    {
       Test_TObjArray();
       Test_TOrdCollection();
       Test_TList();
       Test_TSortedList();
       Test_THashTable();
       Test_TBtree();

       return 0;
    }