home *** CD-ROM | disk | FTP | other *** search
/ C Programming Starter Kit 2.0 / SamsPublishing-CProgrammingStarterKit-v2.0-Win31.iso / bc45 / classinc.pak / DLISTIMP.H < prev    next >
C/C++ Source or Header  |  1997-07-23  |  35KB  |  1,161 lines
  1. /*------------------------------------------------------------------------*/
  2. /*                                                                        */
  3. /*  DLISTIMP.H                                                            */
  4. /*                                                                        */
  5. /*  Copyright (c) 1991, 1994 Borland International                        */
  6. /*  All Rights Reserved                                                   */
  7. /*                                                                        */
  8. /*------------------------------------------------------------------------*/
  9.  
  10. #if !defined( CLASSLIB_DLISTIMP_H )
  11. #define CLASSLIB_DLISTIMP_H
  12.  
  13. #if !defined( __LIMITS_H )
  14. #include <limits.h>
  15. #endif
  16.  
  17. #if !defined( __CHECKS_H )
  18. #include <checks.h>
  19. #endif
  20.  
  21. #if !defined( CLASSLIB_DEFS_H )
  22. #include <classlib/defs.h>
  23. #endif
  24.  
  25. #if !defined( CLASSLIB_MEMMGR_H )
  26. #include <classlib/memmgr.h>
  27. #endif
  28.  
  29. #if !defined( CLASSLIB_ALLOCTR_H )
  30. #include <classlib/alloctr.h>
  31. #endif
  32.  
  33. #if !defined( CLASSLIB_VOIDP_H )
  34. #include <classlib/voidp.h>
  35. #endif
  36.  
  37. #pragma option -Vo-
  38. #if defined( BI_CLASSLIB_NO_po )
  39. #pragma option -po-
  40. #endif
  41.  
  42. /*------------------------------------------------------------------------*/
  43. /*                                                                        */
  44. /*  template <class T,class Alloc> class TMDoubleListElement              */
  45. /*                                                                        */
  46. /*  Node for templates TMDoubleListImp<T,Alloc> and                       */
  47. /*  TMIDoubleListImp<T,Alloc>                                             */
  48. /*                                                                        */
  49. /*------------------------------------------------------------------------*/
  50.  
  51. template <class T,class Alloc> class TMDoubleListImp;
  52.  
  53. template <class T,class Alloc> class TMDoubleListBlockInitializer :
  54.     public Alloc
  55. {
  56.  
  57. protected:
  58.  
  59.     TMDoubleListBlockInitializer();
  60.     ~TMDoubleListBlockInitializer();
  61.  
  62.     static unsigned Count;
  63.  
  64. };
  65.  
  66. #if defined( BI_OLDNAMES )
  67. #define BI_DoubleListBlockInitializer TDoubleListBlockInitializer
  68. #endif
  69.  
  70. template <class T,class Alloc>
  71. TMDoubleListBlockInitializer<T,Alloc>::TMDoubleListBlockInitializer()
  72. {
  73.     PRECONDITION( Count != UINT_MAX );
  74.     if( Count++ == 0 )
  75.         TMDoubleListElement<T,Alloc>::Mgr = 
  76.             new(*this)TMMemBlocks<Alloc>( sizeof(TMDoubleListElement<T,Alloc>), 20 );
  77. }
  78.  
  79. template <class T,class Alloc>
  80. TMDoubleListBlockInitializer<T,Alloc>::~TMDoubleListBlockInitializer()
  81. {
  82.     PRECONDITION( Count != 0 );
  83.     if( --Count == 0 )
  84.         {
  85.         delete TMDoubleListElement<T,Alloc>::Mgr;
  86.         TMDoubleListElement<T,Alloc>::Mgr = 0;
  87.         }
  88. }
  89.  
  90. template <class T,class Alloc>
  91. unsigned TMDoubleListBlockInitializer<T,Alloc>::Count = 0;
  92.  
  93. template <class T,class Alloc> class TMDoubleListElement
  94. {
  95.  
  96. public:
  97.  
  98.     TMDoubleListElement( const T& t, TMDoubleListElement<T,Alloc> *p ) :
  99.         Data(t)
  100.         {
  101.         Next = p->Next;
  102.         Prev = p;
  103.         p->Next = this;
  104.         Next->Prev = this;
  105.         }
  106.  
  107.     TMDoubleListElement();
  108.  
  109.     TMDoubleListElement<T,Alloc> *Next;
  110.     TMDoubleListElement<T,Alloc> *Prev;
  111.     T Data;
  112.  
  113.     void *operator new( size_t sz );
  114.     void operator delete( void * );
  115.  
  116. private:
  117.  
  118.     friend TMDoubleListBlockInitializer<T,Alloc>;
  119.  
  120.     static TMMemBlocks<Alloc> *Mgr;
  121.  
  122. };
  123.  
  124. #if defined( BI_OLDNAMES )
  125. #define BI_MDoubleListElement TMDoubleListElement
  126. #endif
  127.  
  128. template <class T,class Alloc>
  129. TMMemBlocks<Alloc> *TMDoubleListElement<T,Alloc>::Mgr = 0;
  130.  
  131. template <class T,class Alloc>
  132. inline TMDoubleListElement<T,Alloc>::TMDoubleListElement()
  133. {
  134.     Next = Prev = 0;
  135. }
  136.  
  137. template <class T,class Alloc>
  138. void *TMDoubleListElement<T,Alloc>::operator new( size_t sz )
  139. {
  140.     PRECONDITION( Mgr != 0 );
  141.     return Mgr->Allocate( sz );
  142. }
  143.  
  144. template <class T,class Alloc>
  145. void TMDoubleListElement<T,Alloc>::operator delete( void *b )
  146. {
  147.     PRECONDITION( Mgr != 0 );
  148.     Mgr->Free( b );
  149. }
  150.  
  151. /*------------------------------------------------------------------------*/
  152. /*                                                                        */
  153. /*  template <class T,class Alloc> class TMDoubleListImp                  */
  154. /*                                                                        */
  155. /*  Implements a managed double-linked list of objects of type T.         */
  156. /*  Assumes that T has meaningful copy semantics and a default            */
  157. /*  constructor.                                                          */
  158. /*                                                                        */
  159. /*------------------------------------------------------------------------*/
  160.  
  161. template <class T,class Alloc> class TMDoubleListIteratorImp;
  162.  
  163. template <class T,class Alloc> class TMDoubleListImp :
  164.     private TMDoubleListBlockInitializer<T,Alloc>
  165. {
  166.  
  167.     typedef TMDoubleListBlockInitializer<T,Alloc> Parent;
  168.  
  169. public:
  170.  
  171.     typedef void (*IterFunc)(T&, void *);
  172.     typedef int  (*CondFunc)(const T&, void *);
  173.  
  174.     friend TMDoubleListIteratorImp<T,Alloc>;
  175.  
  176.     TMDoubleListImp()
  177.         {
  178.         InitList();
  179.         }
  180.  
  181.     ~TMDoubleListImp()
  182.         {
  183.         Flush();
  184.         }
  185.  
  186.     const T& PeekHead() const
  187.         {
  188.         return Head.Next->Data;
  189.         }
  190.  
  191.     const T& PeekTail() const
  192.         {
  193.         return Tail.Prev->Data;
  194.         }
  195.  
  196.     int Add( const T& t )
  197.         {
  198.         return AddElement(t,&Head);
  199.         }
  200.  
  201.     int AddAtHead( const T& t )
  202.         {
  203.         return AddElement(t,&Head);
  204.         }
  205.  
  206.     int AddAtTail( const T& t )
  207.         {
  208.         return AddElement(t,Tail.Prev);
  209.         }
  210.  
  211.     int Detach( const T& t )
  212.         {
  213.         return DoDetach(t,0);
  214.         }
  215.  
  216.     int DetachAtHead()
  217.         {
  218.         return DoDetachAtHead(0);
  219.         }
  220.  
  221.     int DetachAtTail()
  222.         {
  223.         return DoDetachAtTail(0);
  224.         }
  225.  
  226.     T *Find( const T& t );
  227.  
  228.     void Flush()
  229.         {
  230.         DoFlush(0);
  231.         }
  232.  
  233.     int IsEmpty() const
  234.         {
  235.         return ItemsInContainer == 0;
  236.         }
  237.  
  238.     int GetItemsInContainer() const
  239.         {
  240.         return ItemsInContainer;
  241.         }
  242.  
  243.     void ForEach( IterFunc iter, void *args );
  244.     T *FirstThat( CondFunc cond, void *args ) const;
  245.     T *LastThat( CondFunc cond, void *args ) const;
  246.  
  247.     Parent::operator delete;
  248.     Parent::operator delete [];
  249.  
  250. #if defined( BI_OLDNAMES )
  251.     const T& peekHead() const { return PeekHead(); }
  252.     const T& peekTail() const { return PeekTail(); }
  253.     void add( const T& t ) { Add(t); }
  254.     void addAtTail( const T& t ) { AddAtTail(t); }
  255.     void detach( const T& t, int del = 0 ) { Detach(t); }
  256.     void flush( int = 0 ) { Flush(); }
  257.     int isEmpty() const { return IsEmpty(); }
  258.     int getItemsInContainer() const { return GetItemsInContainer(); }
  259.     void forEach( IterFunc iter, void *args )
  260.         { ForEach( iter, args ); }
  261.     T *firstThat( CondFunc cond, void *args ) const
  262.         { return FirstThat( cond, args ); }
  263.     T *lastThat( CondFunc cond, void *args ) const
  264.         { return LastThat( cond, args ); }
  265. #endif  // BI_OLDNAMES
  266.  
  267. protected:
  268.  
  269.     int DoDetach( const T& t, int del = 0 )
  270.         {
  271.         return DetachElement(FindDetach(t),del);
  272.         }
  273.  
  274.     int DoDetachAtHead( int del = 0 )
  275.         {
  276.         return DetachElement(&Head,del);
  277.         }
  278.  
  279.     int DoDetachAtTail( int del = 0 )
  280.         {
  281.         return DetachElement(Tail.Prev->Prev,del);
  282.         }
  283.  
  284.     void DoFlush( int del = 0 );
  285.  
  286.     TMDoubleListElement<T,Alloc> Head, Tail;
  287.  
  288.     virtual TMDoubleListElement<T,Alloc> *FindDetach( const T& t )
  289.         {
  290.         return FindPred(t);
  291.         }
  292.  
  293.     virtual TMDoubleListElement<T,Alloc> *FindPred( const T& );
  294.  
  295.     int ItemsInContainer;
  296.  
  297. private:
  298.  
  299.     virtual void RemoveData( TMDoubleListElement<T,Alloc> * )
  300.         {
  301.         }
  302.  
  303.     void InitList();
  304.  
  305.     int DetachElement( TMDoubleListElement<T,Alloc> *element, int del = 0 );
  306.     int AddElement( const T& t, TMDoubleListElement<T,Alloc> *element );
  307.  
  308. };
  309.  
  310. template <class T,class Alloc> void TMDoubleListImp<T,Alloc>::InitList()
  311. {
  312.     Head.Next = &Tail;
  313.     Head.Prev = &Head;
  314.     Tail.Prev = &Head;
  315.     Tail.Next = &Tail;
  316.     ItemsInContainer = 0;
  317. }
  318.  
  319. template <class T,class Alloc>
  320. int TMDoubleListImp<T,Alloc>::AddElement( const T& toAdd,
  321.                               TMDoubleListElement<T,Alloc> *Pos )
  322. {
  323.     new TMDoubleListElement<T,Alloc>( toAdd, Pos );
  324.     ItemsInContainer++;
  325.     return 1;
  326. }
  327.  
  328. template <class T,class Alloc>
  329. TMDoubleListElement<T,Alloc> *TMDoubleListImp<T,Alloc>::FindPred( const T&t )
  330. {
  331.     Tail.Data = t;
  332.     TMDoubleListElement<T,Alloc> *cursor = &Head;
  333.     while( !(t == cursor->Next->Data) )
  334.         cursor = cursor->Next;
  335.     Tail.Data = T();
  336.     return cursor;
  337. }
  338.  
  339. template <class T,class Alloc>
  340. int TMDoubleListImp<T,Alloc>::DetachElement(
  341.         TMDoubleListElement<T,Alloc> *pred, int del )
  342. {
  343.     TMDoubleListElement<T,Alloc> *item = pred->Next;
  344.     if( item == &Tail )
  345.         return 0;
  346.     else
  347.         {
  348.         pred->Next = pred->Next->Next;
  349.         pred->Next->Prev = pred;
  350.         if( del != 0 )
  351.             RemoveData( item );
  352.         delete item;
  353.         ItemsInContainer--;
  354.         return 1;
  355.         }
  356. }
  357.  
  358. template <class T,class Alloc>
  359. T *TMDoubleListImp<T,Alloc>::Find( const T& t )
  360. {
  361.     TMDoubleListElement<T,Alloc> *pred = FindPred(t);
  362.     if( pred->Next == &Tail )
  363.         return 0;
  364.     else
  365.         return &pred->Next->Data;
  366. }
  367.  
  368. template <class T,class Alloc>
  369. void TMDoubleListImp<T,Alloc>::DoFlush( int del )
  370. {
  371.     TMDoubleListElement<T,Alloc> *current = Head.Next;
  372.     while( current != &Tail )
  373.         {
  374.         TMDoubleListElement<T,Alloc> *temp = current;
  375.         current = current->Next;
  376.         if( del != 0 )
  377.             RemoveData( temp );
  378.         delete temp;
  379.         }
  380.     InitList();
  381. }
  382.  
  383. template <class T,class Alloc>
  384. void TMDoubleListImp<T,Alloc>::ForEach( IterFunc f, void *args
  385.                                  )
  386. {
  387.     TMDoubleListElement<T,Alloc> *cur = Head.Next;
  388.     while( cur->Next != cur )
  389.         {
  390.         f( cur->Data, args );
  391.         cur = cur->Next;
  392.         }
  393. }
  394.  
  395. template <class T,class Alloc>
  396. T *TMDoubleListImp<T,Alloc>::FirstThat( CondFunc cond, void *args ) const
  397. {
  398.     TMDoubleListElement<T,Alloc> *cur = Head.Next;
  399.     while( cur->Next != cur )
  400.         if( cond( cur->Data, args ) != 0 )
  401.             return &(cur->Data);
  402.         else
  403.             cur = cur->Next;
  404.     return 0;
  405. }
  406.  
  407. template <class T,class Alloc>
  408. T *TMDoubleListImp<T,Alloc>::LastThat( CondFunc cond, void *args ) const
  409. {
  410.     T *res = 0;
  411.     TMDoubleListElement<T,Alloc> *cur = Head.Next;
  412.     while( cur->Next != cur )
  413.         {
  414.         if( cond( cur->Data, args ) != 0 )
  415.             res = &(cur->Data);
  416.         cur = cur->Next;
  417.         }
  418.     return res;
  419. }
  420.  
  421. #if defined( BI_OLDNAMES )
  422. #define BI_MDoubleListImp TMDoubleListImp
  423. #endif
  424.  
  425. /*------------------------------------------------------------------------*/
  426. /*                                                                        */
  427. /*  template <class T,class Alloc> class TMDoubleListIteratorImp          */
  428. /*                                                                        */
  429. /*  Implements a double list iterator.  This iterator works with any      */
  430. /*  direct double list.  For indirect lists, see                          */
  431. /*  TMIDoubleListIteratorImp.                                             */
  432. /*                                                                        */
  433. /*------------------------------------------------------------------------*/
  434.  
  435. template <class T,class Alloc> class TMDoubleListIteratorImp
  436. {
  437.  
  438. public:
  439.  
  440.     TMDoubleListIteratorImp( const TMDoubleListImp<T,Alloc>& l )
  441.         {
  442.         List = &l;
  443.         Cur = List->Head.Next;
  444.         }
  445.  
  446.     TMDoubleListIteratorImp( const TMSDoubleListImp<T,Alloc>& l );
  447.  
  448.     operator int()
  449.         {
  450.         return Cur != &(List->Head) && Cur != &(List->Tail);
  451.         }
  452.  
  453.     const T& Current()
  454.         {
  455.         PRECONDITION( int(*this) != 0 );
  456.         return Cur->Data;
  457.         }
  458.  
  459.     const T& operator ++ ( int )
  460.         {
  461.         PRECONDITION( Cur != &(List->Tail) );
  462.         TMDoubleListElement<T,Alloc> *temp = Cur;
  463.         Cur = Cur->Next;
  464.         return temp->Data;
  465.         }
  466.  
  467.     const T& operator ++ ()
  468.         {
  469.         PRECONDITION( Cur->Next != &(List->Tail) );
  470.         Cur = Cur->Next;
  471.         return Cur->Data;
  472.         }
  473.  
  474.     const T& operator -- ( int )
  475.         {
  476.         PRECONDITION( Cur != &(List->Head) );
  477.         TMDoubleListElement<T,Alloc> *temp = Cur;
  478.         Cur = Cur->Prev;
  479.         return temp->Data;
  480.         }
  481.  
  482.     const T& operator -- ()
  483.         {
  484.         PRECONDITION( Cur->Prev != &(List->Head) );
  485.         Cur = Cur->Prev;
  486.         return Cur->Data;
  487.         }
  488.  
  489.     void Restart()
  490.         {
  491.         Cur = List->Head.Next;
  492.         }
  493.  
  494.     void RestartAtTail()
  495.         {
  496.         Cur = List->Tail.Prev;
  497.         }
  498.  
  499. #if defined( BI_OLDNAMES )
  500.     T current() { return Current(); }
  501.     void restart() { Restart(); }
  502. #endif
  503.  
  504.  
  505. private:
  506.  
  507.     const TMDoubleListImp<T,Alloc> *List;
  508.     TMDoubleListElement<T,Alloc> *Cur;
  509.  
  510. };
  511.  
  512. #if defined( BI_OLDNAMES )
  513. #define BI_MDoubleListIteratorImp TMDoubleListIteratorImp
  514. #endif
  515.  
  516. /*------------------------------------------------------------------------*/
  517. /*                                                                        */
  518. /*  template <class T> class TDoubleListImp                               */
  519. /*  template <class T> class TDoubleListIteratorImp                       */
  520. /*                                                                        */
  521. /*  Implements a double-linked list of objects of type T using            */
  522. /*  TStandardAllocator as its memory manager. Assumes that T has          */
  523. /*  meaningful copy semantics and a default constructor.                  */
  524. /*                                                                        */
  525. /*------------------------------------------------------------------------*/
  526.  
  527. template <class T> class TDoubleListImp :
  528.     public TMDoubleListImp<T,TStandardAllocator>
  529. {
  530. };
  531.  
  532. template <class T> class TDoubleListIteratorImp :
  533.     public TMDoubleListIteratorImp<T,TStandardAllocator>
  534. {
  535.  
  536. public:
  537.  
  538.     TDoubleListIteratorImp( const TDoubleListImp<T>& l ) :
  539.         TMDoubleListIteratorImp<T,TStandardAllocator>(l) {}
  540.  
  541.     TDoubleListIteratorImp( const TSDoubleListImp<T>& l ) :
  542.         TMDoubleListIteratorImp<T,TStandardAllocator>(l) {}
  543.  
  544. };
  545.  
  546. #if defined( BI_OLDNAMES )
  547. #define BI_DoubleListImp TDoubleListImp
  548. #define BI_DoubleListIteratorImp TDoubleListIteratorImp
  549. #endif
  550.  
  551. /*------------------------------------------------------------------------*/
  552. /*                                                                        */
  553. /*  template <class T,class Alloc> class TMSDoubleListImp                 */
  554. /*  template <class T,class Alloc> class TMSDoubleListIteratorImp         */
  555. /*                                                                        */
  556. /*  Implements a managed sorted double-linked list of objects of type T.  */
  557. /*  Assumes that T has meaningful copy semantics, a meaningful            */
  558. /*  < operator, and a default constructor.                                */
  559. /*                                                                        */
  560. /*------------------------------------------------------------------------*/
  561.  
  562. template <class T,class Alloc> class TMSDoubleListImp :
  563.     private TMDoubleListImp<T,Alloc>
  564. {
  565.     typedef TMDoubleListImp<T,Alloc> Parent;
  566.  
  567. public:
  568.  
  569.     friend TMDoubleListIteratorImp<T,Alloc>;
  570.  
  571.     int Add( const T& t );
  572.  
  573.     Parent::IterFunc;
  574.     Parent::CondFunc;
  575.     Parent::PeekHead;
  576.     Parent::PeekTail;
  577.     Parent::Detach;
  578.     Parent::Find;
  579.     Parent::Flush;
  580.     Parent::IsEmpty;
  581.     Parent::GetItemsInContainer;
  582.     Parent::ForEach;
  583.     Parent::FirstThat;
  584.     Parent::LastThat;
  585.     Parent::operator delete;
  586.     Parent::operator delete [];
  587.  
  588. #if defined( BI_OLDNAMES )
  589.     void add( const T& t ) { Add(t); }
  590.     Parent::peekHead;
  591.     Parent::peekTail;
  592.     Parent::detach;
  593.     Parent::flush;
  594.     Parent::isEmpty;
  595.     Parent::getItemsInContainer;
  596.     Parent::forEach;
  597.     Parent::firstThat;
  598.     Parent::lastThat;
  599. #endif  // BI_OLDNAMES
  600.  
  601. protected:
  602.  
  603.     Parent::Head;
  604.     Parent::Tail;
  605.     Parent::ItemsInContainer;
  606.     Parent::DoDetach;
  607.     Parent::DoDetachAtHead;
  608.     Parent::DoDetachAtTail;
  609.     Parent::DoFlush;
  610.  
  611.     virtual TMDoubleListElement<T,Alloc> *FindDetach( const T& );
  612.     virtual TMDoubleListElement<T,Alloc> *FindPred( const T& );
  613.  
  614. };
  615.  
  616. template <class T,class Alloc> class TMSDoubleListIteratorImp :
  617.     public TMDoubleListIteratorImp<T,Alloc>
  618. {
  619.  
  620. public:
  621.  
  622.     TMSDoubleListIteratorImp( const TMSDoubleListImp<T,Alloc>& l ) :
  623.         TMDoubleListIteratorImp<T,Alloc>(l) {}
  624.  
  625. };
  626.  
  627. template <class T,class Alloc>
  628. int TMSDoubleListImp<T,Alloc>::Add( const T& t )
  629. {
  630.     new TMDoubleListElement<T,Alloc>( t, FindPred(t) );
  631.     ItemsInContainer++;
  632.     return 1;
  633. }
  634.  
  635. template <class T,class Alloc>
  636. TMDoubleListElement<T,Alloc>*TMSDoubleListImp<T,Alloc>::FindDetach(const T&t)
  637. {
  638.     TMDoubleListElement<T,Alloc> *res = FindPred(t);
  639.     if( res != 0 &&
  640.         res->Next->Data == t )
  641.         return res;
  642.     else
  643.         return &Tail;
  644. }
  645.  
  646. template <class T,class Alloc>
  647. TMDoubleListElement<T,Alloc>*TMSDoubleListImp<T,Alloc>::FindPred(const T& t)
  648. {
  649.     Tail.Data = t;
  650.     TMDoubleListElement<T,Alloc> *cursor = &Head;
  651.     while( cursor->Next->Data < t )
  652.         cursor = cursor->Next;
  653.     Tail.Data = T();
  654.     return cursor;
  655. }
  656.  
  657. // constructor for TMDoubleListIteratorImp
  658. template <class T,class Alloc>
  659. TMDoubleListIteratorImp<T,Alloc>::TMDoubleListIteratorImp(
  660.     const TMSDoubleListImp<T,Alloc>& l )
  661. {
  662.     List = &l;
  663.     Cur = List->Head.Next;
  664. }
  665.  
  666. #if defined( BI_OLDNAMES )
  667. #define BI_MSDoubleListImp TMSDoubleListImp
  668. #define BI_MSDoubleListIteratorImp TMSDoubleListIteratorImp
  669. #endif
  670.  
  671. /*------------------------------------------------------------------------*/
  672. /*                                                                        */
  673. /*  template <class T> class TSDoubleListImp                              */
  674. /*  template <class T> class TSDoubleListIteratorImp                      */
  675. /*                                                                        */
  676. /*  Implements a sorted double-linked list of objects of type T, using    */
  677. /*  TStandardAllocator as its memory manager. Assumes that T has          */
  678. /*  meaningful copy semantics, a meaningful < operator, and a default     */
  679. /*  constructor.                                                          */
  680. /*                                                                        */
  681. /*------------------------------------------------------------------------*/
  682.  
  683. template <class T> class TSDoubleListImp :
  684.     public TMSDoubleListImp<T,TStandardAllocator>
  685. {
  686. };
  687.  
  688. template <class T> class TSDoubleListIteratorImp :
  689.     public TMSDoubleListIteratorImp<T,TStandardAllocator>
  690. {
  691.  
  692. public:
  693.  
  694.     TSDoubleListIteratorImp( const TSDoubleListImp<T>& l ) :
  695.         TMSDoubleListIteratorImp<T,TStandardAllocator>(l) {}
  696.  
  697. };
  698.  
  699. #if defined( BI_OLDNAMES )
  700. #define BI_SDoubleListImp TSDoubleListImp
  701. #define BI_SDoubleListIteratorImp TSDoubleListIteratorImp
  702. #endif
  703.  
  704. /*------------------------------------------------------------------------*/
  705. /*                                                                        */
  706. /*  template <class T,class List,class Alloc>                             */
  707. /*  class TMInternalIDoubleListImp                                        */
  708. /*                                                                        */
  709. /*  Implements a managed double-linked list of pointers to objects of     */
  710. /*  type T. This is implemented through the form of TMDoubleListImp       */
  711. /*  specified by List.  Since pointers always have meaningful copy        */
  712. /*  semantics, this class can handle any type of object.                  */
  713. /*                                                                        */
  714. /*------------------------------------------------------------------------*/
  715.  
  716. template <class T,class List,class Alloc> class TMInternalIDoubleListImp :
  717.     public List
  718. {
  719.  
  720.     typedef List Parent;
  721.  
  722. public:
  723.  
  724.     typedef void (*IterFunc)(T&, void *);
  725.     typedef int  (*CondFunc)(const T&, void *);
  726.  
  727.     T *PeekHead() const
  728.         {
  729.         return STATIC_CAST(T *, STATIC_CAST(void *, Parent::PeekHead()));
  730.         }
  731.  
  732.     T *PeekTail() const
  733.         {
  734.         return STATIC_CAST(T *, STATIC_CAST(void *, Parent::PeekTail()));
  735.         }
  736.  
  737.     int Add( T *t )
  738.         { 
  739.         return Parent::Add( t ); 
  740.         }
  741.  
  742.     int Detach( T *t, int del = 0 ) 
  743.         { 
  744.         return Parent::DoDetach( t, del ); 
  745.         }
  746.  
  747.     int DetachAtHead( int del = 0 ) 
  748.         { 
  749.         return Parent::DoDetachAtHead( del ); 
  750.         }
  751.  
  752.     int DetachAtTail( int del = 0 ) 
  753.         { 
  754.         return Parent::DoDetachAtTail( del ); 
  755.         }
  756.  
  757.     T *Find( const T *t );
  758.  
  759.     void Flush( int del = 0 )
  760.         {
  761.         DoFlush( del );
  762.         }
  763.  
  764.     void ForEach( IterFunc iter, void * );
  765.     T *FirstThat( CondFunc cond, void * ) const;
  766.     T *LastThat( CondFunc cond, void * ) const;
  767.  
  768. #if defined( BI_OLDNAMES )
  769.     T *peekHead() const { return PeekHead(); }
  770.     T *peekTail() const { return PeekTail(); }
  771.  
  772.     void add( T *t ) { Add(t); }
  773.     void detach( T *t, int del = 0 ) { Detach( t, del ); }
  774.     void forEach( IterFunc iter, void *args )
  775.         { ForEach( iter, args ); }
  776.     T *firstThat(  CondFunc cond, void *args ) const
  777.         { return FirstThat( cond, args ); }
  778.     T *lastThat( CondFunc cond, void *args ) const
  779.         { return LastThat( cond, args ); }
  780. #endif  // BI_OLDNAMES
  781.  
  782. protected:
  783.  
  784.     virtual TMDoubleListElement<TVoidPointer,Alloc> *FindPred( const TVoidPointer& ) = 0;
  785.  
  786. private:
  787.  
  788.     virtual void RemoveData( TMDoubleListElement<TVoidPointer,Alloc> *block )
  789.         {
  790.         delete STATIC_CAST(T *,STATIC_CAST(void *,block->Data));
  791.         }
  792.  
  793. };
  794.  
  795. template <class T, class List, class Alloc>
  796. T *TMInternalIDoubleListImp<T,List,Alloc>::Find( const T *t )
  797. {
  798.     TMDoubleListElement<TVoidPointer,Alloc> *pred = FindPred(t);
  799.     if( pred->Next == &Tail )
  800.         return 0;
  801.     else
  802.         return STATIC_CAST(T *,STATIC_CAST(void *,pred->Next->Data));
  803. }
  804.  
  805. template <class T, class List, class Alloc>
  806. void TMInternalIDoubleListImp<T,List,Alloc>::ForEach( IterFunc iter,
  807.                                                       void *args )
  808. {
  809.     TMDoubleListElement<TVoidPointer,Alloc> *cur = Head.Next;
  810.     while( cur->Next != cur )
  811.         {
  812.         iter( *STATIC_CAST(T *,STATIC_CAST(void *,cur->Data)), args );
  813.         cur = cur->Next;
  814.         }
  815. }
  816.  
  817. template <class T, class List,class Alloc> T *
  818. TMInternalIDoubleListImp<T,List,Alloc>::FirstThat( CondFunc cond,
  819.                                                    void *args ) const
  820. {
  821.     TMDoubleListElement<TVoidPointer,Alloc> *cur = Head.Next;
  822.     while( cur->Next != cur )
  823.         if( cond( *STATIC_CAST(T *,STATIC_CAST(void *,cur->Data)), args ) != 0 )
  824.             return STATIC_CAST(T *,STATIC_CAST(void *,cur->Data));
  825.         else
  826.             cur = cur->Next;
  827.     return 0;
  828. }
  829.  
  830. template <class T, class List, class Alloc> T *
  831. TMInternalIDoubleListImp<T,List,Alloc>::LastThat( CondFunc cond,
  832.                                                   void *args ) const
  833. {
  834.     T *res = 0;
  835.     TMDoubleListElement<TVoidPointer,Alloc> *cur = Head.Next;
  836.     while( cur->Next != cur )
  837.         {
  838.         if( cond( *STATIC_CAST(T *,STATIC_CAST(void *,cur->Data)), args ) != 0 )
  839.             res = STATIC_CAST(T *,STATIC_CAST(void *,cur->Data));
  840.         cur = cur->Next;
  841.         }
  842.     return res;
  843. }
  844.  
  845. template <class T,class List,class Alloc>
  846. class TMInternalIDoubleListIteratorImp :
  847.     public TMDoubleListIteratorImp<TVoidPointer,Alloc>
  848. {
  849.  
  850.     typedef TMDoubleListIteratorImp<TVoidPointer,Alloc> Parent;
  851.  
  852. public:
  853.  
  854.     TMInternalIDoubleListIteratorImp( const TMInternalIDoubleListImp<T,List,Alloc>& l ) :
  855.         TMDoubleListIteratorImp<TVoidPointer,Alloc>(l) {}
  856.  
  857.     T *Current()
  858.         {
  859.         return STATIC_CAST(T *,STATIC_CAST(void *,Parent::Current()));
  860.         }
  861.  
  862.     T *operator ++ (int)
  863.         {
  864.         return STATIC_CAST(T *,STATIC_CAST(void *,Parent::operator++(1)));
  865.         }
  866.  
  867.     T *operator ++ ()
  868.         {
  869.         return STATIC_CAST(T *,STATIC_CAST(void *,Parent::operator++()));
  870.         }
  871.  
  872.     T *operator -- (int)
  873.         {
  874.         return STATIC_CAST(T *,STATIC_CAST(void *,Parent::operator--(1)));
  875.         }
  876.  
  877.     T *operator -- ()
  878.         {
  879.         return STATIC_CAST(T *,STATIC_CAST(void *,Parent::operator--()));
  880.         }
  881.  
  882. #if defined( BI_OLDNAMES )
  883.     T *current() { return Current(); }
  884. #endif  // BI_OLDNAMES
  885.  
  886. };
  887.  
  888. #if defined( BI_OLDNAMES )
  889. #define BI_MInternalIDoubleListImp TMInternalIDoubleListImp
  890. #endif
  891.  
  892. /*------------------------------------------------------------------------*/
  893. /*                                                                        */
  894. /*  template <class T,class Alloc> class TMIDoubleListImp                 */
  895. /*  template <class T,class Alloc> class TMIDoubleListIteratorImp         */
  896. /*                                                                        */
  897. /*  Implements a double-linked list of pointers to objects of             */
  898. /*  type T.  This is implemented through the template                     */
  899. /*  TMInternalIDoubleListImp. Since pointers always have meaningful       */
  900. /*  copy semantics, this class can handle any type of object.             */
  901. /*                                                                        */
  902. /*------------------------------------------------------------------------*/
  903.  
  904. template <class T,class Alloc> class TMIDoubleListIteratorImp;
  905.  
  906. template <class T,class Alloc> class TMIDoubleListImp :
  907.     private TMInternalIDoubleListImp<T,TMDoubleListImp<TVoidPointer,Alloc>,Alloc >
  908. {
  909.  
  910.     typedef TMInternalIDoubleListImp<T,TMDoubleListImp<TVoidPointer,Alloc>,Alloc > Parent;
  911.  
  912. public:
  913.  
  914.     friend TMIDoubleListIteratorImp<T,Alloc>;
  915.  
  916.     Parent::IterFunc;
  917.     Parent::CondFunc;
  918.     Parent::PeekHead;
  919.     Parent::PeekTail;
  920.     Parent::Add;
  921.     Parent::AddAtHead;
  922.     Parent::AddAtTail;
  923.     Parent::Detach;
  924.     Parent::DetachAtHead;
  925.     Parent::DetachAtTail;
  926.     Parent::Find;
  927.     Parent::Flush;
  928.     Parent::IsEmpty;
  929.     Parent::GetItemsInContainer;
  930.     Parent::ForEach;
  931.     Parent::FirstThat;
  932.     Parent::LastThat;
  933.     Parent::operator delete;
  934.     Parent::operator delete [];
  935.  
  936. #if defined( BI_OLDNAMES )
  937.     Parent::peekHead;
  938.     Parent::peekTail;
  939.     Parent::add;
  940.     Parent::addAtTail;
  941.     Parent::detach;
  942.     Parent::flush;
  943.     Parent::isEmpty;
  944.     Parent::forEach;
  945.     Parent::firstThat;
  946.     Parent::lastThat;
  947. #endif  // BI_OLDNAMES
  948.  
  949. protected:
  950.  
  951.     Parent::Head;
  952.     Parent::Tail;
  953.     Parent::ItemsInContainer;
  954.  
  955.     virtual TMDoubleListElement<TVoidPointer,Alloc> *FindPred(const TVoidPointer&);
  956.  
  957. };
  958.  
  959. template <class T,class Alloc> class TMIDoubleListIteratorImp :
  960.     public TMInternalIDoubleListIteratorImp<T,TMDoubleListImp<TVoidPointer,Alloc>,Alloc>
  961. {
  962.  
  963. public:
  964.  
  965.     TMIDoubleListIteratorImp( const TMIDoubleListImp<T,Alloc>& l ) :
  966.         TMInternalIDoubleListIteratorImp<T,TMDoubleListImp<TVoidPointer,Alloc>,Alloc>( l ) {}
  967.  
  968. };
  969.  
  970. template <class T,class Alloc>
  971. TMDoubleListElement<TVoidPointer,Alloc>
  972. *TMIDoubleListImp<T,Alloc>::FindPred( const TVoidPointer& t )
  973. {
  974.     Tail.Data = t;
  975.     TMDoubleListElement<TVoidPointer,Alloc> *cursor = &Head;
  976.     while( !(*STATIC_CAST(T *,STATIC_CAST(void *,t)) ==
  977.              *STATIC_CAST(T *,STATIC_CAST(void *,cursor->Next->Data))) )
  978.         cursor = cursor->Next;
  979.     Tail.Data = TVoidPointer();
  980.     return cursor;
  981. }
  982.  
  983. #if defined( BI_OLDNAMES )
  984. #define BI_MIDoubleListImp TMIDoubleListImp
  985. #define BI_MIDoubleListIteratorImp TMIDoubleListIteratorImp
  986. #endif
  987.  
  988. /*------------------------------------------------------------------------*/
  989. /*                                                                        */
  990. /*  template <class T> class TIDoubleListImp                              */
  991. /*  template <class T> class TIDoubleListIteratorImp                      */
  992. /*                                                                        */
  993. /*  Implements a double-linked list of pointers to objects of             */
  994. /*  type T using TStandardAllocator as its memory manager.                */
  995. /*  This is implemented through the template                              */
  996. /*  TMInternalIDoubleListImp. Since pointers always have meaningful       */
  997. /*  copy semantics, this class can handle any type of object.             */
  998. /*                                                                        */
  999. /*------------------------------------------------------------------------*/
  1000.  
  1001. template <class T> class TIDoubleListImp :
  1002.     public TMIDoubleListImp<T,TStandardAllocator>
  1003. {
  1004. };
  1005.  
  1006. template <class T> class TIDoubleListIteratorImp :
  1007.     public TMIDoubleListIteratorImp<T,TStandardAllocator>
  1008. {
  1009.  
  1010. public:
  1011.  
  1012.     TIDoubleListIteratorImp( const TIDoubleListImp<T>& l ) :
  1013.         TMIDoubleListIteratorImp<T,TStandardAllocator>( l ) {}
  1014.  
  1015. };
  1016.  
  1017. #if defined( BI_OLDNAMES )
  1018. #define BI_IDoubleListImp TIDoubleListImp
  1019. #define BI_IDoubleListIteratorImp TIDoubleListIteratorImp
  1020. #endif
  1021.  
  1022. /*------------------------------------------------------------------------*/
  1023. /*                                                                        */
  1024. /*  template <class T,class Alloc> class TMISDoubleListImp                */
  1025. /*  template <class T,class Alloc> class TMISDoubleListIteratorImp        */
  1026. /*                                                                        */
  1027. /*  Implements a managed sorted double-linked list of pointers to         */
  1028. /*  objects of type T.  This is implemented through the template          */
  1029. /*  TMInternalIDoubleListImp. Since pointers always have meaningful       */
  1030. /*  copy semantics, this class can handle any type of object.             */
  1031. /*                                                                        */
  1032. /*------------------------------------------------------------------------*/
  1033.  
  1034. template <class T,class Alloc> class TMISDoubleListIteratorImp;
  1035.  
  1036. template <class T,class Alloc> class TMISDoubleListImp :
  1037.     private TMInternalIDoubleListImp<T,TMSDoubleListImp<TVoidPointer,Alloc>,Alloc>
  1038. {
  1039.  
  1040.     typedef TMInternalIDoubleListImp<T, TMSDoubleListImp<TVoidPointer,Alloc>, Alloc > Parent;
  1041.  
  1042. public:
  1043.  
  1044.     friend TMISDoubleListIteratorImp<T,Alloc>;
  1045.  
  1046.     Parent::IterFunc;
  1047.     Parent::CondFunc;
  1048.     Parent::PeekHead;
  1049.     Parent::PeekTail;
  1050.     Parent::Add;
  1051.     Parent::Detach;
  1052.     Parent::DetachAtHead;
  1053.     Parent::DetachAtTail;
  1054.     Parent::Find;
  1055.     Parent::Flush;
  1056.     Parent::IsEmpty;
  1057.     Parent::GetItemsInContainer;
  1058.     Parent::ForEach;
  1059.     Parent::FirstThat;
  1060.     Parent::LastThat;
  1061.     Parent::operator delete;
  1062.     Parent::operator delete [];
  1063.  
  1064. protected:
  1065.  
  1066.     Parent::Head;
  1067.     Parent::Tail;
  1068.     Parent::ItemsInContainer;
  1069.  
  1070.     virtual TMDoubleListElement<TVoidPointer,Alloc> *FindDetach(const TVoidPointer&);
  1071.     virtual TMDoubleListElement<TVoidPointer,Alloc> *FindPred(const TVoidPointer&);
  1072.  
  1073. };
  1074.  
  1075. template <class T,class Alloc> class TMISDoubleListIteratorImp :
  1076.     public TMInternalIDoubleListIteratorImp<T,TMSDoubleListImp<TVoidPointer,Alloc>,Alloc>
  1077. {
  1078.  
  1079. public:
  1080.  
  1081.     TMISDoubleListIteratorImp( const TMISDoubleListImp<T,Alloc>& l ) :
  1082.         TMInternalIDoubleListIteratorImp<T,TMSDoubleListImp<TVoidPointer,Alloc>,Alloc>( l ) {}
  1083.  
  1084. };
  1085.  
  1086. template <class T,class Alloc>
  1087. TMDoubleListElement<TVoidPointer,Alloc>
  1088. *TMISDoubleListImp<T,Alloc>::FindDetach( const TVoidPointer& t )
  1089. {
  1090.     TMDoubleListElement<TVoidPointer,Alloc> *res = FindPred(t);
  1091.     if( res == 0 || res->Next == &Tail )
  1092.         return &Tail;
  1093.     else if(
  1094.         *STATIC_CAST(T *,STATIC_CAST(void *,res->Next->Data)) ==
  1095.         *STATIC_CAST(T *,STATIC_CAST(void *,t)) )
  1096.             return res;
  1097.     else
  1098.         return &Tail;
  1099. }
  1100.  
  1101. template <class T,class Alloc>
  1102. TMDoubleListElement<TVoidPointer,Alloc>
  1103. *TMISDoubleListImp<T,Alloc>::FindPred( const TVoidPointer& t )
  1104. {
  1105.     Tail.Data = t;
  1106.     TMDoubleListElement<TVoidPointer,Alloc> *cursor = &Head;
  1107.     while( *STATIC_CAST(T *,STATIC_CAST(void *,cursor->Next->Data)) <
  1108.            *STATIC_CAST(T *,STATIC_CAST(void *,t)) )
  1109.         cursor = cursor->Next;
  1110.     Tail.Data = TVoidPointer();
  1111.     return cursor;
  1112. }
  1113.  
  1114. #if defined( BI_OLDNAMES )
  1115. #define BI_MISDoubleListImp TMISDoubleListImp
  1116. #define BI_MISDoubleListIteratorImp TMISDoubleListIteratorImp
  1117. #endif
  1118.  
  1119. /*------------------------------------------------------------------------*/
  1120. /*                                                                        */
  1121. /*  template <class T> class TISDoubleListImp                             */
  1122. /*  template <class T> class TISDoubleListIteratorImp                     */
  1123. /*                                                                        */
  1124. /*  Implements a managed sorted double-linked list of pointers to         */
  1125. /*  objects of type T using TStandardAllocator as its memory manager.     */
  1126. /*  This is implemented through the template                              */
  1127. /*  TMInternalIDoubleListImp. Since pointers always have meaningful       */
  1128. /*  copy semantics, this class can handle any type of object.             */
  1129. /*                                                                        */
  1130. /*------------------------------------------------------------------------*/
  1131.  
  1132. template <class T> class TISDoubleListImp :
  1133.     public TMISDoubleListImp<T,TStandardAllocator>
  1134. {
  1135. };
  1136.  
  1137. template <class T> class TISDoubleListIteratorImp :
  1138.     public TMISDoubleListIteratorImp<T,TStandardAllocator>
  1139. {
  1140.  
  1141. public:
  1142.  
  1143.     TISDoubleListIteratorImp( const TISDoubleListImp<T>& l ) :
  1144.         TMISDoubleListIteratorImp<T,TStandardAllocator>( l ) {}
  1145.  
  1146. };
  1147.  
  1148. #if defined( BI_OLDNAMES )
  1149. #define BI_ISDoubleListImp TISDoubleListImp
  1150. #define BI_ISDoubleListIteratorImp TISDoubleListIteratorImp
  1151. #endif
  1152.  
  1153. #if defined( BI_CLASSLIB_NO_po )
  1154. #pragma option -po.
  1155. #endif
  1156.  
  1157. #pragma option -Vo.
  1158.  
  1159. #endif  // CLASSLIB_DLISTIMP_H
  1160.  
  1161.