//*CMZ :  2.00/11 17/08/98  15.18.35  by  Rene Brun
//*CMZ :  1.00/06 23/03/97  11.05.27  by  Rene Brun
//*-- Author :    Fons Rademakers   14/09/95

//*KEEP,CopyRight,T=C.
/*************************************************************************
 * Copyright(c) 1995-1999, The ROOT System, All rights reserved.         *
 * Authors: Rene Brun, Fons Rademakers.                                  *
 * For list of contributors see $ROOTSYS/AA_CREDITS.                     *
 *                                                                       *
 * Permission to use, copy, modify and distribute this software and its  *
 * documentation for non-commercial purposes is hereby granted without   *
 * fee, provided that the above copyright notice appears in all copies   *
 * and that both the copyright notice and this permission notice appear  *
 * in the supporting documentation. The authors make no claims about the *
 * suitability of this software for any purpose. It is provided "as is"  *
 * without express or implied warranty.                                  *
 *************************************************************************/
//*KEND.

//////////////////////////////////////////////////////////////////////////
//                                                                      //
// A sorted doubly linked list. All sortable classes inheriting from    //
// TObject can be inserted in a TSortedList.                            //
//                                                                      //
//////////////////////////////////////////////////////////////////////////

//*KEEP,TSortedList.
#include "TSortedList.h"
//*KEND.


ClassImp(TSortedList)

//______________________________________________________________________________
 void TSortedList::Add(TObject *obj)
{
   // Add object in sorted list. Uses object Compare() member to find right
   // position.

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

   if (!obj->IsSortable()) {
      Error("Add", "object must be sortable");
      return;
   }

   if (!fFirst) {
      TList::AddLast(obj);
      return;
   }

   TObjLink *lnk = fFirst;

   while (lnk) {
      Int_t cmp = lnk->GetObject()->Compare(obj);
      if ((IsAscending() && cmp > 0) || (!IsAscending() && cmp < 0)) {
         if (lnk->Prev()) {
            NewLink(obj, lnk->Prev());
            fSize++;
            return;
         } else {
            TList::AddFirst(obj);
            return;
         }
      }
      lnk = lnk->Next();
   }
   TList::AddLast(obj);
}

//______________________________________________________________________________
 void TSortedList::Add(TObject *obj, Option_t *opt)
{
   // Add object in sorted list. Uses object Compare() member to find right
   // position and also store option. See TList::Add for explanation of
   // usage of option.

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

   if (!obj->IsSortable()) {
      Error("Add", "object must be sortable");
      return;
   }

   if (!fFirst) {
      TList::Add(obj, opt);
      return;
   }

   TObjLink *lnk = fFirst;

   while (lnk) {
      Int_t cmp = lnk->GetObject()->Compare(obj);
      if ((IsAscending() && cmp > 0) || (!IsAscending() && cmp < 0)) {
         if (lnk->Prev()) {
            NewOptLink(obj, opt, lnk);
            fSize++;
            return;
         } else {
            TList::AddFirst(obj, opt);
            return;
         }
      }
      lnk = lnk->Next();
   }
   TList::Add(obj, opt);
}