home *** CD-ROM | disk | FTP | other *** search
/ The Devil's Doorknob BBS Capture (1996-2003) / devilsdoorknobbbscapture1996-2003.iso / Dloads / OTHERUTI / TCPP30-1.ZIP / CLASSINC.ZIP / LISTIMP.H < prev    next >
C/C++ Source or Header  |  1992-02-18  |  18KB  |  582 lines
  1. /*------------------------------------------------------------------------*/
  2. /*                                                                        */
  3. /*  LISTIMP.H                                                             */
  4. /*                                                                        */
  5. /*  Copyright Borland International 1991                                  */
  6. /*  All Rights Reserved                                                   */
  7. /*                                                                        */
  8. /*------------------------------------------------------------------------*/
  9.  
  10. #if !defined( __LISTIMP_H )
  11. #define __LISTIMP_H
  12.  
  13. #if !defined( ___DEFS_H )
  14. #include <_defs.h>
  15. #endif  // ___DEFS_H
  16.  
  17. #if !defined( __MEMMGR_H )
  18. #include <MemMgr.h>
  19. #endif  // __MEMMGR_H
  20.  
  21. /*------------------------------------------------------------------------*/
  22. /*                                                                        */
  23. /*  template <class T> class BI_ListElement                               */
  24. /*                                                                        */
  25. /*  Node for templates BI_ListImp<T> and BI_IListImp<T>                   */
  26. /*                                                                        */
  27. /*------------------------------------------------------------------------*/
  28.  
  29. template <class T> class _CLASSTYPE BI_ListImp;
  30.  
  31. template <class T> class _CLASSTYPE BI_ListBlockInitializer
  32. {
  33.  
  34. protected:
  35.  
  36.     BI_ListBlockInitializer()
  37.         {
  38.         PRECONDITION( count != UINT_MAX );
  39.         if( count++ == 0 )
  40.             BI_ListElement<T>::mgr = 
  41.                 new MemBlocks( sizeof(BI_ListElement<T>), 20 );
  42.         }
  43.  
  44.     ~BI_ListBlockInitializer()
  45.         {
  46.         PRECONDITION( count != 0 );
  47.         if( --count == 0 )
  48.             {
  49.             delete BI_ListElement<T>::mgr;
  50.             BI_ListElement<T>::mgr = 0;
  51.             }
  52.         }
  53.  
  54.     static unsigned count;
  55.  
  56. };
  57.  
  58. template <class T> unsigned BI_ListBlockInitializer<T>::count = 0;
  59.  
  60. template <class T> class _CLASSTYPE BI_ListElement
  61. {
  62.  
  63. public:
  64.  
  65.     BI_ListElement( T t, BI_ListElement<T> _FAR *p ) :
  66.         data(t)
  67.         {
  68.         next = p->next;
  69.         p->next = this;
  70.         }
  71.  
  72.     BI_ListElement();
  73.  
  74.     BI_ListElement<T> _FAR *next;
  75.     T data;
  76.  
  77.     void _FAR *operator new( size_t sz );
  78.     void operator delete( void _FAR * );
  79.  
  80. private:
  81.  
  82.     friend class BI_ListBlockInitializer<T>;
  83.  
  84.     static MemBlocks *mgr;
  85.  
  86. };
  87.  
  88. template <class T> MemBlocks *BI_ListElement<T>::mgr = 0;
  89.  
  90. template <class T> inline BI_ListElement<T>::BI_ListElement()
  91. {
  92.     next = 0;
  93. }
  94.  
  95. template <class T> void _FAR *BI_ListElement<T>::operator new( size_t sz )
  96. {
  97.     PRECONDITION( mgr != 0 );
  98.     return mgr->allocate( sz );
  99. }
  100.  
  101. template <class T> void BI_ListElement<T>::operator delete( void _FAR *b )
  102. {
  103.     PRECONDITION( mgr != 0 );
  104.     mgr->free( b );
  105. }
  106.  
  107. inline BI_ListElement<void _FAR *>::BI_ListElement()
  108. {
  109.     next = 0;
  110.     data = 0;
  111. }
  112.  
  113. /*------------------------------------------------------------------------*/
  114. /*                                                                        */
  115. /*  template <class T> class BI_ListImp                                   */
  116. /*                                                                        */
  117. /*  Implements a list of objects of type T.  Assumes that                 */
  118. /*  T has meaningful copy semantics and a default constructor.            */
  119. /*                                                                        */
  120. /*------------------------------------------------------------------------*/
  121.  
  122. template <class T> class _CLASSTYPE BI_ListIteratorImp;
  123.  
  124. template <class T> class _CLASSTYPE BI_ListImp : 
  125.     private BI_ListBlockInitializer<T>
  126. {
  127.  
  128. public:
  129.  
  130.     friend class BI_ListIteratorImp<T>;
  131.  
  132.     BI_ListImp()
  133.         {
  134.         initList();
  135.         }
  136.  
  137.     ~BI_ListImp()
  138.         {
  139.         flush();
  140.         }
  141.  
  142.     T peekHead() const
  143.         {
  144.         return head.next->data;
  145.         }
  146.  
  147.     void add( T );
  148.     void detach( T, int = 0 );
  149.     void flush( int del = 0 );
  150.  
  151.     int isEmpty() const
  152.         {
  153.         return head.next == &tail;
  154.         }
  155.  
  156.     void forEach( void (_FAR *)(T _FAR &, void _FAR *), void _FAR * );
  157.     T _FAR *firstThat( int (_FAR *)(const T _FAR &, void _FAR *),
  158.                        void _FAR *
  159.                      ) const;
  160.     T _FAR *lastThat( int (_FAR *)(const T _FAR &, void _FAR *),
  161.                       void _FAR *
  162.                     ) const;
  163.  
  164. protected:
  165.  
  166.     BI_ListElement<T> head, tail;
  167.  
  168.     virtual BI_ListElement<T> _FAR *findDetach( T t )
  169.         {
  170.         return findPred(t);
  171.         }
  172.  
  173.     virtual BI_ListElement<T> _FAR *findPred( T );
  174.  
  175. private:
  176.  
  177.     virtual void removeData( BI_ListElement<T> _FAR * )
  178.         {
  179.         }
  180.  
  181.     void initList();
  182.  
  183. };
  184.  
  185. template <class T> void BI_ListImp<T>::initList()
  186. {
  187.     head.next = &tail;
  188.     tail.next = &tail;
  189. }
  190.  
  191. template <class T> void BI_ListImp<T>::add( T toAdd )
  192. {
  193.     new BI_ListElement<T>( toAdd, &head );
  194. }
  195.  
  196. template <class T> BI_ListElement<T> _FAR *BI_ListImp<T>::findPred( T t )
  197. {
  198.     tail.data = t;
  199.     BI_ListElement<T> _FAR *cursor = &head;
  200.     while( !(t == cursor->next->data) )
  201.         cursor = cursor->next;
  202.     return cursor;
  203. }
  204.  
  205. template <class T> void BI_ListImp<T>::detach( T toDetach, int del )
  206. {
  207.     BI_ListElement<T> _FAR *pred = findDetach( toDetach );
  208.     BI_ListElement<T> _FAR *item = pred->next;
  209.     if( item != &tail )
  210.         {
  211.         pred->next = pred->next->next;
  212.         if( del != 0 )
  213.             removeData( item );
  214.         delete item;
  215.         }
  216. }
  217.  
  218. template <class T> void BI_ListImp<T>::flush( int del )
  219. {
  220.     BI_ListElement<T> _FAR *current = head.next;
  221.     while( current != &tail )
  222.         {
  223.         BI_ListElement<T> _FAR *temp = current;
  224.         current = current->next;
  225.         if( del != 0 )
  226.             removeData( temp );
  227.         delete temp;
  228.         }
  229.     initList();
  230. }
  231.  
  232. template <class T>
  233. void BI_ListImp<T>::forEach( void (_FAR *f)(T _FAR &, void _FAR *),
  234.                              void _FAR *args
  235.                            )
  236. {
  237.     BI_ListElement<T> _FAR *cur = head.next;
  238.     while( cur->next != cur )
  239.         {
  240.         f( cur->data, args );
  241.         cur = cur->next;
  242.         }
  243. }
  244.  
  245. template <class T>
  246. T _FAR *BI_ListImp<T>::firstThat( int (_FAR *cond)(const T _FAR &, void _FAR *),
  247.                                   void _FAR *args
  248.                                 ) const
  249. {
  250.     BI_ListElement<T> _FAR *cur = head.next;
  251.     while( cur->next != cur )
  252.         if( cond( cur->data, args ) != 0 )
  253.             return &(cur->data);
  254.         else
  255.             cur = cur->next;
  256.     return 0;
  257. }
  258.  
  259. template <class T>
  260. T _FAR *BI_ListImp<T>::lastThat( int (_FAR *cond)(const T _FAR &, void _FAR *),
  261.                                  void _FAR *args
  262.                                ) const
  263. {
  264.     T _FAR *res = 0;
  265.     BI_ListElement<T> _FAR *cur = head.next;
  266.     while( cur->next != cur )
  267.         {
  268.         if( cond( cur->data, args ) != 0 )
  269.             res = &(cur->data);
  270.         cur = cur->next;
  271.         }
  272.     return res;
  273. }
  274.  
  275. /*------------------------------------------------------------------------*/
  276. /*                                                                        */
  277. /*  template <class T> class BI_SListImp                                  */
  278. /*                                                                        */
  279. /*  Implements a sorted list of objects of type T.  Assumes that          */
  280. /*  T has meaningful copy semantics, a meaningful < operator, and a       */
  281. /*  default constructor.                                                  */
  282. /*                                                                        */
  283. /*------------------------------------------------------------------------*/
  284.  
  285. template <class T> class _CLASSTYPE BI_SListImp : public BI_ListImp<T>
  286. {
  287.  
  288. public:
  289.  
  290.     void add( T );
  291.  
  292. protected:
  293.  
  294.     virtual BI_ListElement<T> _FAR *findDetach( T t );
  295.     virtual BI_ListElement<T> _FAR *findPred( T );
  296.  
  297. };
  298.  
  299. template <class T> void BI_SListImp<T>::add( T t )
  300. {
  301.     new BI_ListElement<T>( t, findPred(t) );
  302. }
  303.  
  304. template <class T> BI_ListElement<T> _FAR *BI_SListImp<T>::findDetach( T t )
  305. {
  306.     BI_ListElement<T> _FAR *res = findPred(t);
  307.     if( res->next->data == t )
  308.         return res;
  309.     else
  310.         return &tail;
  311. }
  312.  
  313. template <class T> BI_ListElement<T> _FAR *BI_SListImp<T>::findPred( T t )
  314. {
  315.     tail.data = t;
  316.     BI_ListElement<T> _FAR *cursor = &head;
  317.     while( cursor->next->data < t )
  318.         cursor = cursor->next;
  319.     return cursor;
  320. }
  321.  
  322. /*------------------------------------------------------------------------*/
  323. /*                                                                        */
  324. /*  template <class T> class BI_ListIteratorImp                           */
  325. /*                                                                        */
  326. /*  Implements a list iterator.  This iterator works with any direct      */
  327. /*  list.  For indirect lists, see BI_IListIteratorImp.                   */
  328. /*                                                                        */
  329. /*------------------------------------------------------------------------*/
  330.  
  331. template <class T> class _CLASSTYPE BI_ListIteratorImp
  332. {
  333.  
  334. public:
  335.  
  336.     BI_ListIteratorImp( const BI_ListImp<T> _FAR &l )
  337.         {
  338.         list = &l;
  339.         cur = list->head.next;
  340.         }
  341.  
  342.     operator int()
  343.         {
  344.         return cur != &(list->tail);
  345.         }
  346.  
  347.     T current()
  348.         {
  349.         return cur->data;
  350.         }
  351.  
  352.     T operator ++ ( int )
  353.         {
  354.         BI_ListElement<T> _FAR *temp = cur;
  355.         cur = cur->next;
  356.         return temp->data;
  357.         }
  358.  
  359.     T operator ++ ()
  360.         {
  361.         cur = cur->next;
  362.         return cur->data;
  363.         }
  364.  
  365.     void restart()
  366.         {
  367.         cur = list->head.next;
  368.         }
  369.  
  370. private:
  371.  
  372.     const BI_ListImp<T> _FAR *list;
  373.     BI_ListElement<T> _FAR *cur;
  374.  
  375. };
  376.  
  377. /*------------------------------------------------------------------------*/
  378. /*                                                                        */
  379. /*  template <class T, class Vect> class BI_InternalIListImp              */
  380. /*                                                                        */
  381. /*  Implements a list of pointers to objects of type T.                   */
  382. /*  This is implemented through the form of BI_ListImp specified by List. */
  383. /*  Since pointers always have meaningful copy semantics, this class      */
  384. /*  can handle any type of object.                                        */
  385. /*                                                                        */
  386. /*------------------------------------------------------------------------*/
  387.  
  388. template <class T, class List> class _CLASSTYPE BI_InternalIListImp :
  389.     public List
  390. {
  391. public:
  392.  
  393.     T _FAR *peekHead() const
  394.         {
  395.         return (T _FAR *)List::peekHead();
  396.         }
  397.  
  398.     void add( T _FAR *t )
  399.         {
  400.         List::add( t );
  401.         }
  402.  
  403.     void detach( T _FAR *t, int del = 0 )
  404.         {
  405.         List::detach( t, del );
  406.         }
  407.  
  408.     void forEach( void (_FAR *)(T _FAR &, void _FAR *), void _FAR * );
  409.     T _FAR *firstThat( int (_FAR *)(const T _FAR &, void _FAR *),
  410.                        void _FAR *
  411.                      ) const;
  412.     T _FAR *lastThat( int (_FAR *)(const T _FAR &, void _FAR *),
  413.                       void _FAR *
  414.                     ) const;
  415.  
  416. protected:
  417.  
  418.     virtual BI_ListElement<void _FAR *> _FAR *findPred( void _FAR * ) = 0;
  419.  
  420. private:
  421.  
  422.     virtual void removeData( BI_ListElement<void _FAR *> _FAR *block )
  423.         {
  424.         delete (T _FAR *)(block->data);
  425.         }
  426. };
  427.  
  428. template <class T, class List>
  429. void BI_InternalIListImp<T, List>::forEach( void (_FAR *f)(T _FAR &, void _FAR *),
  430.                                             void _FAR *args
  431.                                           )
  432. {
  433.     BI_ListElement<void _FAR *> _FAR *cur = head.next;
  434.     while( cur->next != cur )
  435.         {
  436.         f( *(T _FAR *)cur->data, args );
  437.         cur = cur->next;
  438.         }
  439. }
  440.  
  441. template <class T, class List>
  442. T _FAR *BI_InternalIListImp<T, List>::firstThat( int (_FAR *cond)(const T _FAR &, void _FAR *),
  443.                                             void _FAR *args
  444.                                           ) const
  445. {
  446.     BI_ListElement<void _FAR *> _FAR *cur = head.next;
  447.     while( cur->next != cur )
  448.         if( cond( *(T _FAR *)(cur->data), args ) != 0 )
  449.             return (T _FAR *)cur->data;
  450.         else
  451.             cur = cur->next;
  452.     return 0;
  453. }
  454.  
  455. template <class T, class List>
  456. T _FAR *BI_InternalIListImp<T, List>::lastThat( int (_FAR *cond)(const T _FAR &, void _FAR *),
  457.                                            void _FAR *args
  458.                                          ) const
  459. {
  460.     T _FAR *res = 0;
  461.     BI_ListElement<void _FAR *> _FAR *cur = head.next;
  462.     while( cur->next != cur )
  463.         {
  464.         if( cond( *(T _FAR *)(cur->data), args ) != 0 )
  465.             res = (T _FAR *)(cur->data);
  466.         cur = cur->next;
  467.         }
  468.     return res;
  469. }
  470.  
  471. /*------------------------------------------------------------------------*/
  472. /*                                                                        */
  473. /*  template <class T> class BI_IListImp                                  */
  474. /*                                                                        */
  475. /*  Implements a list of pointers to objects of type T.                   */
  476. /*  This is implemented through the template BI_InternalIListImp.  Since  */
  477. /*  pointers always have meaningful copy semantics, this class            */
  478. /*  can handle any type of object.                                        */
  479. /*                                                                        */
  480. /*------------------------------------------------------------------------*/
  481.  
  482. template <class T> class _CLASSTYPE BI_IListImp :
  483.     public BI_InternalIListImp<T, BI_ListImp<void _FAR *> >
  484. {
  485.  
  486. protected:
  487.  
  488.     virtual BI_ListElement<void _FAR *> _FAR *findPred( void _FAR * );
  489.  
  490. };
  491.  
  492. template <class T>
  493. BI_ListElement<void _FAR *> _FAR *BI_IListImp<T>::findPred( void _FAR *t )
  494. {
  495.     tail.data = t;
  496.     BI_ListElement<void _FAR *> _FAR *cursor = &head;
  497.     while( !(*(T _FAR *)t == *(T _FAR *)(cursor->next->data)) )
  498.         cursor = cursor->next;
  499.     return cursor;
  500. }
  501.  
  502. /*------------------------------------------------------------------------*/
  503. /*                                                                        */
  504. /*  template <class T> class BI_ISListImp                                 */
  505. /*                                                                        */
  506. /*  Implements a sorted list of pointers to objects of type T.            */
  507. /*  This is implemented through the template BI_InternalIListImp.  Since  */
  508. /*  pointers always have meaningful copy semantics, this class            */
  509. /*  can handle any type of object.                                        */
  510. /*                                                                        */
  511. /*------------------------------------------------------------------------*/
  512.  
  513. template <class T> class _CLASSTYPE BI_ISListImp :
  514.     public BI_InternalIListImp<T, BI_SListImp<void _FAR *> >
  515. {
  516.  
  517. protected:
  518.  
  519.     virtual BI_ListElement<void _FAR *> _FAR *findDetach( void _FAR * );
  520.     virtual BI_ListElement<void _FAR *> _FAR *findPred( void _FAR * );
  521.  
  522. };
  523.  
  524. template <class T>
  525. BI_ListElement<void _FAR *> _FAR *BI_ISListImp<T>::findDetach( void _FAR *t )
  526. {
  527.     BI_ListElement<void _FAR *> _FAR *res = findPred(t);
  528.     if( *(T _FAR *)(res->next->data) == *(T _FAR *)t )
  529.         return res;
  530.     else
  531.         return &tail;
  532. }
  533.  
  534. template <class T>
  535. BI_ListElement<void _FAR *> _FAR *BI_ISListImp<T>::findPred( void _FAR *t )
  536. {
  537.     tail.data = t;
  538.     BI_ListElement<void _FAR *> _FAR *cursor = &head;
  539.     while( *(T _FAR *)(cursor->next->data) < *(T _FAR *)t )
  540.         cursor = cursor->next;
  541.     return cursor;
  542. }
  543.  
  544. /*------------------------------------------------------------------------*/
  545. /*                                                                        */
  546. /*  template <class T> class BI_IListIteratorImp                          */
  547. /*                                                                        */
  548. /*  Implements a list iterator.  This iterator works with any indirect    */
  549. /*  list.  For direct lists, see BI_ListIteratorImp.                      */
  550. /*                                                                        */
  551. /*------------------------------------------------------------------------*/
  552.  
  553. template <class T>
  554. class _CLASSTYPE BI_IListIteratorImp : public BI_ListIteratorImp<void _FAR *>
  555. {
  556.  
  557. public:
  558.  
  559.    BI_IListIteratorImp( const BI_ListImp<void _FAR *> _FAR &l ) :
  560.         BI_ListIteratorImp<void _FAR *>(l) {}
  561.  
  562.    T _FAR *current()
  563.         {
  564.         return (T _FAR *)BI_ListIteratorImp<void _FAR *>::current();
  565.         }
  566.  
  567.    T _FAR *operator ++ (int)
  568.         {
  569.         return (T _FAR *)BI_ListIteratorImp<void _FAR *>::operator ++ (1);
  570.         }
  571.  
  572.    T _FAR *operator ++ ()
  573.         {
  574.         return (T _FAR *)BI_ListIteratorImp<void _FAR *>::operator ++ ();
  575.         }
  576.  
  577.  
  578. };
  579.  
  580. #endif  // __LISTIMP_H
  581.  
  582.