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