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