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