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