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