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