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