// @(#)root/cont:$Name:  $:$Id: TList.cxx,v 1.22 2006/07/26 13:36:42 rdm Exp $
// Author: Fons Rademakers   10/08/95

/*************************************************************************
 * Copyright (C) 1995-2000, Rene Brun and Fons Rademakers.               *
 * All rights reserved.                                                  *
 *                                                                       *
 * For the licensing terms see $ROOTSYS/LICENSE.                         *
 * For the list of contributors see $ROOTSYS/README/CREDITS.             *
 *************************************************************************/

//////////////////////////////////////////////////////////////////////////
//                                                                      //
// TList                                                                //
//                                                                      //
// A doubly linked list. All classes inheriting from TObject can be     //
// inserted in a TList. Before being inserted into the list the object  //
// pointer is wrapped in a TObjLink object which contains, besides      //
// the object pointer also a previous and next pointer.                 //
//                                                                      //
// There are basically four ways to iterate over a TList (in order      //
// of preference, if not forced by other constraints):                  //
//    1) Using the R__FOR_EACH macro:                                   //
//         GetListOfPrimitives()->R__FOR_EACH(TObject,Paint)(option);   //
//                                                                      //
//    2) Using the TList iterator TListIter (via the wrapper class      //
//       TIter):                                                        //
//         TIter next(GetListOfPrimitives());                           //
//         while (TObject *obj = next())                                //
//            obj->Draw(next.GetOption());                              //
//                                                                      //
//    3) Using the TObjLink list entries (that wrap the TObject*):      //
//         TObjLink *lnk = GetListOfPrimitives()->FirstLink();          //
//         while (lnk) {                                                //
//            lnk->GetObject()->Draw(lnk->GetOption());                 //
//            lnk = lnk->Next();                                        //
//         }                                                            //
//                                                                      //
//    4) Using the TList's After() and Before() member functions:       //
//         TFree *idcur = this;                                         //
//         while (idcur) {                                              //
//            ...                                                       //
//            ...                                                       //
//            idcur = (TFree*)GetListOfFree()->After(idcur);            //
//         }                                                            //
//                                                                      //
//   Methods 2, 3 and 4 can also easily iterate backwards using either  //
//   a backward TIter (using argument kIterBackward) or by using        //
//   LastLink() and lnk->Prev() or by using the Before() member.        //
//Begin_Html <img src=gif/tlist.gif> End_Html                           //
//                                                                      //
//////////////////////////////////////////////////////////////////////////

#include "TList.h"

#include <string>
namespace std {} using namespace std;

ClassImp(TList)

//______________________________________________________________________________
TList::~TList()
{
   // Delete the list. Objects are not deleted unless the TList is the
   // owner (set via SetOwner()).

   Clear();
}

//______________________________________________________________________________
void TList::AddFirst(TObject *obj)
{
   // Add object at the beginning of the list.

   if (IsArgNull("AddFirst", obj)) return;

   if (!fFirst) {
      fFirst = NewLink(obj);
      fLast = fFirst;
   } else {
      TObjLink *t = NewLink(obj);
      t->fNext = fFirst;
      fFirst->fPrev = t;
      fFirst = t;
   }
   fSize++;
   Changed();
}

//______________________________________________________________________________
void TList::AddFirst(TObject *obj, Option_t *opt)
{
   // Add object at the beginning of the list and also store option.
   // Storing an option is useful when one wants to change the behaviour
   // of an object a little without having to create a complete new
   // copy of the object. This feature is used, for example, by the Draw()
   // method. It allows the same object to be drawn in different ways.

   if (IsArgNull("AddFirst", obj)) return;

   if (!fFirst) {
      fFirst = NewOptLink(obj, opt);
      fLast = fFirst;
   } else {
      TObjLink *t = NewOptLink(obj, opt);
      t->fNext = fFirst;
      fFirst->fPrev = t;
      fFirst = t;
   }
   fSize++;
   Changed();
}

//______________________________________________________________________________
void TList::AddLast(TObject *obj)
{
   // Add object at the end of the list.

   if (IsArgNull("AddLast", obj)) return;

   if (!fFirst) {
      fFirst = NewLink(obj);
      fLast  = fFirst;
   } else
      fLast = NewLink(obj, fLast);
   fSize++;
   Changed();
}

//______________________________________________________________________________
void TList::AddLast(TObject *obj, Option_t *opt)
{
   // Add object at the end of the list and also store option.
   // Storing an option is useful when one wants to change the behaviour
   // of an object a little without having to create a complete new
   // copy of the object. This feature is used, for example, by the Draw()
   // method. It allows the same object to be drawn in different ways.

   if (IsArgNull("AddLast", obj)) return;

   if (!fFirst) {
      fFirst = NewOptLink(obj, opt);
      fLast  = fFirst;
   } else
      fLast = NewOptLink(obj, opt, fLast);
   fSize++;
   Changed();
}

//______________________________________________________________________________
void TList::AddBefore(const TObject *before, TObject *obj)
{
   // Insert object before object before in the list.

   if (IsArgNull("AddBefore", obj)) return;

   if (!before)
      TList::AddFirst(obj);
   else {
      Int_t    idx;
      TObjLink *t = FindLink(before, idx);
      if (!t) {
         Error("AddBefore", "before not found, object not added");
         return;
      }
      if (t == fFirst)
         TList::AddFirst(obj);
      else {
         NewLink(obj, t->Prev());
         fSize++;
         Changed();
      }
   }
}

//______________________________________________________________________________
void TList::AddBefore(TObjLink *before, TObject *obj)
{
   // Insert object before the specified ObjLink object. If before = 0 then add
   // to the head of the list. An ObjLink can be obtained by looping over a list
   // using the above describe iterator method 3.

   if (IsArgNull("AddBefore", obj)) return;

   if (!before)
      TList::AddFirst(obj);
   else {
      if (before == fFirst)
         TList::AddFirst(obj);
      else {
         NewLink(obj, before->Prev());
         fSize++;
         Changed();
      }
   }
}

//______________________________________________________________________________
void TList::AddAfter(const TObject *after, TObject *obj)
{
   // Insert object after object after in the list.

   if (IsArgNull("AddAfter", obj)) return;

   if (!after)
      TList::AddLast(obj);
   else {
      Int_t    idx;
      TObjLink *t = FindLink(after, idx);
      if (!t) {
         Error("AddAfter", "after not found, object not added");
         return;
      }
      if (t == fLast)
         TList::AddLast(obj);
      else {
         NewLink(obj, t);
         fSize++;
         Changed();
      }
   }
}

//______________________________________________________________________________
void TList::AddAfter(TObjLink *after, TObject *obj)
{
   // Insert object after the specified ObjLink object. If after = 0 then add
   // to the tail of the list. An ObjLink can be obtained by looping over a list
   // using the above describe iterator method 3.

   if (IsArgNull("AddAfter", obj)) return;

   if (!after)
      TList::AddLast(obj);
   else {
      if (after == fLast)
         TList::AddLast(obj);
      else {
         NewLink(obj, after);
         fSize++;
         Changed();
      }
   }
}

//______________________________________________________________________________
void TList::AddAt(TObject *obj, Int_t idx)
{
   // Insert object at position idx in the list.

   if (IsArgNull("AddAt", obj)) return;

   TObjLink *lnk = LinkAt(idx);
   if (!lnk)
      TList::AddLast(obj);
   else if (lnk == fFirst)
      TList::AddFirst(obj);
   else {
      NewLink(obj, lnk->Prev());
      fSize++;
      Changed();
   }
}

//______________________________________________________________________________
TObject *TList::After(const TObject *obj) const
{
   // Returns the object after object obj. Obj is found using the
   // object's IsEqual() method.  Returns 0 if obj is last in list.

   TObjLink *t;

   if (fCache && fCache->GetObject() && fCache->GetObject()->IsEqual(obj)) {
      t = fCache;
      ((TList*)this)->fCache = fCache->Next();  //cast const away, fCache should be mutable
   } else {
      Int_t idx;
      t = FindLink(obj, idx);
      if (t) ((TList*)this)->fCache = t->Next();
   }

   if (t && t->Next())
      return t->Next()->GetObject();
   else
      return 0;
}

//______________________________________________________________________________
TObject *TList::At(Int_t idx) const
{
   // Returns the object at position idx. Returns 0 if idx is out of range.

   TObjLink *lnk = LinkAt(idx);
   if (lnk) return lnk->GetObject();
   return 0;
}

//______________________________________________________________________________
TObject *TList::Before(const TObject *obj) const
{
   // Returns the object before object obj. Obj is found using the
   // object's IsEqual() method.  Returns 0 if obj is first in list.

   TObjLink *t;

   if (fCache && fCache->GetObject() && fCache->GetObject()->IsEqual(obj)) {
      t = fCache;
      ((TList*)this)->fCache = fCache->Prev();  //cast const away, fCache should be mutable
   } else {
      Int_t idx;
      t = FindLink(obj, idx);
      if (t) ((TList*)this)->fCache = t->Prev();
   }

   if (t && t->Prev())
      return t->Prev()->GetObject();
   else
      return 0;
}

//______________________________________________________________________________
void TList::Clear(Option_t *option)
{
   // Remove all objects from the list. Does not delete the objects
   // unless the TList is the owner (set via SetOwner()) and option
   // "nodelete" is not set.
   // If option="nodelete" then don't delete any heap objects that were
   // marked with the kCanDelete bit, otherwise these objects will be
   // deleted (this option is used by THashTable::Clear()).

   Bool_t nodel = option ? (!strcmp(option, "nodelete") ? kTRUE : kFALSE) : kFALSE;

   if (!nodel && IsOwner()) {
      Delete(option);
      return;
   }

   while (fFirst) {
      TObjLink *tlk = fFirst;
      fFirst = fFirst->Next();
      fSize--;
      // delete only heap objects marked OK to clear
      if (!nodel && tlk->GetObject() && tlk->GetObject()->IsOnHeap()) {
         if (tlk->GetObject()->TestBit(kCanDelete)) {
            if(tlk->GetObject()->TestBit(kNotDeleted)) {
               TCollection::GarbageCollect(tlk->GetObject());
            }
         }
      }
      delete tlk;
   }
   fFirst = fLast = fCache = 0;
   fSize  = 0;
   Changed();
}

//______________________________________________________________________________
void TList::Delete(Option_t *option)
{
   // Remove all objects from the list AND delete all heap based objects.
   // If option="slow" then keep list consistent during delete. This allows
   // recursive list operations during the delete (e.g. during the dtor
   // of an object in this list one can still access the list to search for
   // other not yet deleted objects).

   Bool_t slow = option ? (!strcmp(option, "slow") ? kTRUE : kFALSE) : kFALSE;

   if (slow) {

      while (fFirst) {
         TObjLink *tlk = fFirst;
         fFirst = fFirst->Next();
         fSize--;
         // delete only heap objects
         if (tlk->GetObject() && tlk->GetObject()->IsOnHeap())
            TCollection::GarbageCollect(tlk->GetObject());

         delete tlk;
      }
      fFirst = fLast = fCache = 0;
      fSize  = 0;

   } else {

      TObjLink *first = fFirst;    //pointer to first entry in linked list
      fFirst = fLast = fCache = 0;
      fSize  = 0;
      while (first) {
         TObjLink *tlk = first;
         first = first->Next();
         // delete only heap objects
         if (tlk->GetObject() && tlk->GetObject()->IsOnHeap())
            TCollection::GarbageCollect(tlk->GetObject());

         delete tlk;
      }
   }
   Changed();
}

//______________________________________________________________________________
void TList::DeleteLink(TObjLink *lnk)
{
   // Delete a TObjLink object.

   lnk->fNext = lnk->fPrev = 0;
   lnk->fObject = 0;
   delete lnk;
}

//______________________________________________________________________________
TObject *TList::FindObject(const char *name) const
{
   // Find an object in this list using its name. Requires a sequential
   // scan till the object has been found. Returns 0 if object with specified
   // name is not found. This method overrides the generic FindObject()
   // of TCollection for efficiency reasons.

   if (!name) return 0;
   TObjLink *lnk = FirstLink();
   while (lnk) {
      TObject *obj = lnk->GetObject();
      if (obj->GetName() && !strcmp(name, obj->GetName())) return obj;
      lnk = lnk->Next();
   }
   return 0;
}

//______________________________________________________________________________
TObject *TList::FindObject(const TObject *obj) const
{
   // Find an object in this list using the object's IsEqual()
   // member function. Requires a sequential scan till the object has
   // been found. Returns 0 if object is not found.
   // This method overrides the generic FindObject() of TCollection for
   // efficiency reasons.

   TObjLink *lnk = FirstLink();

   while (lnk) {
      TObject *ob = lnk->GetObject();
      if (ob->IsEqual(obj)) return ob;
      lnk = lnk->Next();
   }
   return 0;
}

//______________________________________________________________________________
TObjLink *TList::FindLink(const TObject *obj, Int_t &idx) const
{
   // Returns the TObjLink object that contains object obj. In idx it returns
   // the position of the object in the list.

   if (!fFirst) return 0;

   TObject *object;
   TObjLink *lnk = fFirst;
   idx = 0;

   while (lnk) {
      object = lnk->GetObject();
      if (object) {
         if (object->TestBit(kNotDeleted)) {
            if (object->IsEqual(obj)) return lnk;
         }
      }
      lnk = lnk->Next();
      idx++;
   }
   return 0;
}

//______________________________________________________________________________
TObject *TList::First() const
{
   // Return the first object in the list. Returns 0 when list is empty.

   if (fFirst) return fFirst->GetObject();
   return 0;
}

//______________________________________________________________________________
TObject **TList::GetObjectRef(const TObject *obj) const
{
   // Return address of pointer to obj

   TObjLink *lnk = FirstLink();

   while (lnk) {
      TObject *ob = lnk->GetObject();
      if (ob->IsEqual(obj)) return lnk->GetObjectRef();
      lnk = lnk->Next();
   }
   return 0;
}

//______________________________________________________________________________
TObject *TList::Last() const
{
   // Return the last object in the list. Returns 0 when list is empty.

   if (fLast) return fLast->GetObject();
   return 0;
}

//______________________________________________________________________________
TObjLink *TList::LinkAt(Int_t idx) const
{
   // Return the TObjLink object at index idx.

   Int_t    i = 0;
   TObjLink *lnk = fFirst;
   while (i < idx && lnk) {
      i++;
      lnk = lnk->Next();
   }
   return lnk;
}

//______________________________________________________________________________
TIterator *TList::MakeIterator(Bool_t dir) const
{
   // Return a list iterator.

   return new TListIter(this, dir);
}

//______________________________________________________________________________
TObjLink *TList::NewLink(TObject *obj, TObjLink *prev)
{
   // Return a new TObjLink.

   if (prev)
      return new TObjLink(obj, prev);
   else
      return new TObjLink(obj);
}

//______________________________________________________________________________
TObjLink *TList::NewOptLink(TObject *obj, Option_t *opt, TObjLink *prev)
{
   // Return a new TObjOptLink (a TObjLink that also stores the option).

   if (prev)
      return new TObjOptLink(obj, prev, opt);
   else
      return new TObjOptLink(obj, opt);
}

//______________________________________________________________________________
TObject *TList::Remove(TObject *obj)
{
   // Remove object from the list.

   if (!obj) return 0;

   Int_t    idx;
   TObjLink *lnk = FindLink(obj, idx);

   if (!lnk) return 0;

   // return object found, which may be (pointer wise) different than the
   // input object (depending on what IsEqual() is doing)
   TObject *ob = lnk->GetObject();

   if (lnk == fFirst) {
      fFirst = lnk->Next();
      if (lnk == fLast)
         fLast = fFirst;
      else
         fFirst->fPrev = 0;
      DeleteLink(lnk);
   } else if (lnk == fLast) {
      fLast = lnk->Prev();
      fLast->fNext = 0;
      DeleteLink(lnk);
   } else {
      lnk->Prev()->fNext = lnk->Next();
      lnk->Next()->fPrev = lnk->Prev();
      DeleteLink(lnk);
   }
   fSize--;
   fCache = 0;
   Changed();

   return ob;
}

//______________________________________________________________________________
TObject *TList::Remove(TObjLink *lnk)
{
   // Remove object link (and therefore the object it contains)
   // from the list.

   if (!lnk) return 0;

   TObject *obj = lnk->GetObject();

   if (lnk == fFirst) {
      fFirst = lnk->Next();
      if (lnk == fLast)
         fLast = fFirst;
      else
         fFirst->fPrev = 0;
      DeleteLink(lnk);
   } else if (lnk == fLast) {
      fLast = lnk->Prev();
      fLast->fNext = 0;
      DeleteLink(lnk);
   } else {
      lnk->Prev()->fNext = lnk->Next();
      lnk->Next()->fPrev = lnk->Prev();
      DeleteLink(lnk);
   }
   fSize--;
   fCache = 0;
   Changed();

   return obj;
}

//______________________________________________________________________________
void TList::Sort(Bool_t order)
{
   // Sort linked list. Real sorting is done in private function DoSort().
   // The list can only be sorted when is contains objects of a sortable
   // class.

   if (!fFirst) return;

   fAscending = order;

   if (!fFirst->GetObject()->IsSortable()) {
      Error("Sort", "objects in list are not sortable");
      return;
   }

   DoSort(&fFirst, fSize);

   // correct back links
   TObjLink *ol, *lnk = fFirst;

   if (lnk) lnk->fPrev = 0;
   while ((ol = lnk)) {
      lnk = lnk->fNext;
      if (lnk)
         lnk->fPrev = ol;
      else
         fLast = ol;
   }
   fSorted = kTRUE;
}

//______________________________________________________________________________
Bool_t TList::LnkCompare(TObjLink *l1, TObjLink *l2)
{
   // Compares the objects stored in the TObjLink objects.
   // Depending on the flag IsAscending() the function returns
   // true if the object in l1 <= l2 (ascending) or l2 <= l1 (descending).

   Int_t cmp = l1->GetObject()->Compare(l2->GetObject());

   if ((IsAscending() && cmp <=0) || (!IsAscending() && cmp > 0))
      return kTRUE;
   return kFALSE;
}

//______________________________________________________________________________
TObjLink **TList::DoSort(TObjLink **head, Int_t n)
{
   // Sort linked list.

   TObjLink *p1, *p2, **h2, **t2;

   switch (n) {
      case 0:
         return head;

      case 1:
         return &((*head)->fNext);

      case 2:
         p2 = (p1 = *head)->fNext;
         if (LnkCompare(p1, p2)) return &(p2->fNext);
         p1->fNext = (*head = p2)->fNext;
         return &((p2->fNext = p1)->fNext);
   }

   int m;
   n -= m = n / 2;

   t2 = DoSort(h2 = DoSort(head, n), m);

   if (LnkCompare((p1 = *head), (p2 = *h2))) {
      do {
         if (!--n) return *h2 = p2, t2;
      } while (LnkCompare((p1 = *(head = &(p1->fNext))), p2));
   }

   while (1) {
      *head = p2;
      do {
         if (!--m) return *h2 = *t2, *t2 = p1, h2;
      } while (!LnkCompare(p1, (p2 = *(head = &(p2->fNext)))));
      *head = p1;
      do {
         if (!--n) return *h2 = p2, t2;
      } while (LnkCompare((p1 = *(head = &(p1->fNext))), p2));
   }
}

//////////////////////////////////////////////////////////////////////////
//                                                                      //
// TObjLink                                                             //
//                                                                      //
// Wrapper around a TObject so it can be stored in a TList.             //
//                                                                      //
//////////////////////////////////////////////////////////////////////////

//______________________________________________________________________________
TObjLink::TObjLink(TObject *obj, TObjLink *prev)
          : fNext(prev->fNext), fPrev(prev), fObject(obj)
{
   // Create a new TObjLink.

   fPrev->fNext = this;
   if (fNext) fNext->fPrev = this;
}

//////////////////////////////////////////////////////////////////////////
//                                                                      //
// TListIter                                                            //
//                                                                      //
// Iterator of linked list.                                             //
//                                                                      //
//////////////////////////////////////////////////////////////////////////

ClassImp(TListIter)

//______________________________________________________________________________
TListIter::TListIter(const TList *l, Bool_t dir)
        : fList(l), fCurCursor(0), fCursor(0), fDirection(dir), fStarted(kFALSE)
{
   // Create a new list iterator. By default the iteration direction
   // is kIterForward. To go backward use kIterBackward.
}

//______________________________________________________________________________
TListIter::TListIter(const TListIter &iter) : TIterator(iter)
{
   // Copy ctor.

   fList      = iter.fList;
   fCurCursor = iter.fCurCursor;
   fCursor    = iter.fCursor;
   fDirection = iter.fDirection;
   fStarted   = iter.fStarted;
}

//______________________________________________________________________________
TIterator &TListIter::operator=(const TIterator &rhs)
{
   // Overridden assignment operator.

   if (this != &rhs && rhs.IsA() == TListIter::Class()) {
      const TListIter &rhs1 = (const TListIter &)rhs;
      fList      = rhs1.fList;
      fCurCursor = rhs1.fCurCursor;
      fCursor    = rhs1.fCursor;
      fDirection = rhs1.fDirection;
      fStarted   = rhs1.fStarted;
   }
   return *this;
}

//______________________________________________________________________________
TListIter &TListIter::operator=(const TListIter &rhs)
{
   // Overloaded assignment operator.

   if (this != &rhs) {
      fList      = rhs.fList;
      fCurCursor = rhs.fCurCursor;
      fCursor    = rhs.fCursor;
      fDirection = rhs.fDirection;
      fStarted   = rhs.fStarted;
   }
   return *this;
}

//______________________________________________________________________________
TObject *TListIter::Next()
{
   // Return next object in the list. Returns 0 when no more objects in list.

   if (!fList) return 0;

   if (fDirection == kIterForward) {
      if (!fStarted) {
         fCursor = fList->fFirst;
         fStarted = kTRUE;
      }
      fCurCursor = fCursor;
      if (fCursor) fCursor = fCursor->Next();
   } else {
      if (!fStarted) {
         fCursor = fList->fLast;
         fStarted = kTRUE;
      }
      fCurCursor = fCursor;
      if (fCursor) fCursor = fCursor->Prev();
   }

   if (fCurCursor) return fCurCursor->GetObject();
   return 0;
}

//______________________________________________________________________________
Option_t *TListIter::GetOption() const
{
   // Returns the object option stored in the list.

   if (fCurCursor) return fCurCursor->GetOption();
   return "";
}

//______________________________________________________________________________
void TListIter::SetOption(Option_t *option)
{
   // Sets the object option stored in the list.

   if (fCurCursor) fCurCursor->SetOption(option);
}

//_______________________________________________________________________
void TList::Streamer(TBuffer &b)
{
   // Stream all objects in the collection to or from the I/O buffer.

   Int_t nobjects;
   UChar_t nch;
   Int_t nbig;
   TObject *obj;
   UInt_t R__s, R__c;

   if (b.IsReading()) {
      Version_t v = b.ReadVersion(&R__s, &R__c);
      if (v > 3) {
         TObject::Streamer(b);
         fName.Streamer(b);
         b >> nobjects;
         string readOption;
         for (Int_t i = 0; i < nobjects; i++) {
            b >> obj;
            b >> nch;
            if (v > 4 && nch == 255)  {
               b >> nbig;
            } else {
               nbig = nch;
            }
            readOption.resize(nbig,'\0');
            b.ReadFastArray((char*) readOption.data(),nbig);
            if (nch) {
               Add(obj,readOption.c_str());
            } else {
               Add(obj);
            }
         }
         b.CheckByteCount(R__s, R__c,TList::IsA());
         return;
      }

      //  process old versions when TList::Streamer was in TCollection::Streamer
      if (v > 2)
         TObject::Streamer(b);
      if (v > 1)
         fName.Streamer(b);
      b >> nobjects;
      for (Int_t i = 0; i < nobjects; i++) {
         b >> obj;
         Add(obj);
      }
      b.CheckByteCount(R__s, R__c,TList::IsA());

   } else {
      R__c = b.WriteVersion(TList::IsA(), kTRUE);
      TObject::Streamer(b);
      fName.Streamer(b);
      nobjects = GetSize();
      b << nobjects;

      TObjLink *lnk = fFirst;
      while (lnk) {
         obj = lnk->GetObject();
         b << obj;

         nbig = strlen(lnk->GetAddOption());
         if (nbig > 254) {
            nch = 255;
            b << nch;
            b << nbig;
         } else {
            nch = UChar_t(nbig);
            b << nch;
         }
         b.WriteFastArray(lnk->GetAddOption(),nbig);

         lnk = lnk->Next();
      }
      b.SetByteCount(R__c, kTRUE);
   }
}