home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c082_144 / 2.ddi / CLASSINC.ZIP / VECTIMP.H < prev   
Encoding:
C/C++ Source or Header  |  1992-06-10  |  26.7 KB  |  927 lines
  1. /*------------------------------------------------------------------------*/
  2. /*                                                                        */
  3. /*  VECTIMP.H                                                             */
  4. /*                                                                        */
  5. /*  Copyright Borland International 1991, 1992                            */
  6. /*  All Rights Reserved                                                   */
  7. /*                                                                        */
  8. /*------------------------------------------------------------------------*/
  9.  
  10. #if !defined( __VECTIMP_H )
  11. #define __VECTIMP_H
  12.  
  13. #if !defined( __LIMITS_H )
  14. #include <Limits.h>
  15. #endif  // __LIMITS_H
  16.  
  17. #if !defined( __CHECKS_H )
  18. #include <Checks.h>
  19. #endif  // __CHECKS_H
  20.  
  21. #if !defined( __STDTEMPL_H )
  22. #include <StdTempl.h>
  23. #endif  // __STDTEMPL_H
  24.  
  25. #pragma option -Vo-
  26. #if defined( __BCOPT__ ) && !defined( _ALLOW_po )
  27. #pragma option -po-
  28. #endif
  29.  
  30. /*------------------------------------------------------------------------*/
  31. /*                                                                        */
  32. /*  template <class T> class BI_VectorImp                                 */
  33. /*                                                                        */
  34. /*  Implements a vector of objects of type T.  Assumes that               */
  35. /*  T has meaningful copy semantics and a default constructor.            */
  36. /*                                                                        */
  37. /*------------------------------------------------------------------------*/
  38.  
  39. template <class T> class _CLASSTYPE BI_VectorImp
  40. {
  41.  
  42. public:
  43.  
  44.     friend class _CLASSTYPE BI_VectorIteratorImp<T>;
  45.  
  46.     BI_VectorImp() :
  47.         data(0),
  48.         lim(0)
  49.         {
  50.         }
  51.  
  52.     BI_VectorImp( unsigned sz, unsigned = 0 ) :
  53.         data( new T[sz] ),
  54.         lim(sz)
  55.         {
  56.         }
  57.  
  58.     BI_VectorImp( const BI_VectorImp<T> _FAR & );
  59.  
  60.     const BI_VectorImp<T> _FAR & operator = ( const BI_VectorImp<T> _FAR & );
  61.  
  62.     ~BI_VectorImp()
  63.         {
  64.         delete [] data;
  65.         }
  66.  
  67.     T _FAR & operator [] ( unsigned index ) const
  68.         {
  69.         PRECONDITION( lim > 0 && data != 0 && index < lim );
  70.         return data[index];
  71.         }
  72.  
  73.     unsigned limit() const
  74.         {
  75.         return lim;
  76.         }
  77.  
  78.     virtual unsigned top() const
  79.         {
  80.         return lim;
  81.         }
  82.  
  83.     void resize( unsigned, unsigned = 0 );
  84.  
  85.     void flush( unsigned = 0, unsigned = UINT_MAX, unsigned = 0 ) {}
  86.  
  87.     void forEach( void (_FAR *f)(T _FAR &, void _FAR *), void _FAR *args )
  88.         {
  89.         forEach( f, args, 0, lim );
  90.         }
  91.  
  92.     void forEach( void (_FAR *)(T _FAR &, void _FAR *),
  93.                   void _FAR *,
  94.                   unsigned,
  95.                   unsigned
  96.                 );
  97.  
  98.     T _FAR *firstThat( int (_FAR *)(const T _FAR &, void _FAR *),
  99.                        void _FAR *,
  100.                        unsigned,
  101.                        unsigned
  102.                      ) const;
  103.  
  104.     T _FAR *firstThat( int (_FAR *cond)(const T _FAR &, void _FAR *),
  105.                        void _FAR *args
  106.                      ) const
  107.         {
  108.         return firstThat( cond, args, 0, lim );
  109.         }
  110.  
  111.     T _FAR *lastThat( int (_FAR *)(const T _FAR &, void _FAR *),
  112.                       void _FAR *,
  113.                       unsigned,
  114.                       unsigned
  115.                     ) const;
  116.  
  117.     T _FAR *lastThat( int (_FAR *cond)(const T _FAR &, void _FAR *),
  118.                       void _FAR *args
  119.                     ) const
  120.         {
  121.         return lastThat( cond, args, 0, lim );
  122.         }
  123.  
  124.     virtual unsigned getDelta() const
  125.         {
  126.         return 0;
  127.         }
  128.  
  129. protected:
  130.  
  131.     T _FAR * data;
  132.     unsigned lim;
  133.  
  134.     virtual void zero( unsigned, unsigned )
  135.         {
  136.         }
  137.  
  138.     virtual void removeData( T )
  139.         {
  140.         }
  141.  
  142. };
  143.  
  144. template <class T>
  145. BI_VectorImp<T>::BI_VectorImp( const BI_VectorImp<T> _FAR & v ) :
  146.     data( new T[v.lim] ),
  147.     lim(v.lim)
  148. {
  149.     PRECONDITION( lim == 0 || (data != 0 && v.data != 0) );
  150.     for( unsigned i = 0; i < lim; i++ )
  151.         data[i] = v.data[i];
  152. }
  153.  
  154. template <class T>
  155. const BI_VectorImp<T> _FAR & BI_VectorImp<T>::operator = ( const BI_VectorImp<T> _FAR & v )
  156. {
  157.     if( data != v.data )
  158.         {
  159.         delete [] data;
  160.         data = new T[v.lim];
  161.         CHECK( data != 0 );
  162.         lim = v.lim;
  163.         for( unsigned i = 0; i < lim; i++ )
  164.             data[i] = v.data[i];
  165.         }
  166.     return *this;
  167. }
  168.  
  169. inline unsigned nextDelta( unsigned sz, unsigned delta )
  170. {
  171.     return (sz%delta) ? ((sz+delta)/delta)*delta : sz;
  172. }
  173.  
  174. template <class T>
  175. void BI_VectorImp<T>::resize( unsigned newSz, unsigned offset )
  176. {
  177.     if( newSz <= lim || getDelta() == 0 )
  178.         return;
  179.     unsigned sz = lim + nextDelta( newSz - lim, getDelta() );
  180.     T _FAR *temp = new T[sz];
  181.     unsigned last = min( sz-offset, lim );
  182.     for( unsigned i = 0; i < last; i++ )
  183.         temp[i+offset] = data[i];
  184.     delete [] data;
  185.     data = temp;
  186.     lim = sz;
  187.     zero( last+offset, sz );
  188. }
  189.  
  190. template <class T>
  191. void BI_VectorImp<T>::forEach( void (_FAR *f)( T _FAR &, void _FAR * ),
  192.                                void _FAR *args,
  193.                                unsigned start,
  194.                                unsigned stop
  195.                              )
  196. {
  197.     for( unsigned cur = start; cur < stop; cur++ )
  198.         f( data[cur], args );
  199. }
  200.  
  201. template <class T>
  202. T _FAR *BI_VectorImp<T>::firstThat( int (_FAR *cond)( const T _FAR &, void _FAR * ),
  203.                                void _FAR *args,
  204.                                unsigned start,
  205.                                unsigned stop
  206.                              ) const
  207. {
  208.     for( unsigned cur = start; cur < stop; cur++ )
  209.         if( cond( data[cur], args ) != 0 )
  210.             return &data[cur];
  211.     return 0;
  212. }
  213.  
  214. template <class T>
  215. T _FAR *BI_VectorImp<T>::lastThat( int (_FAR *cond)( const T _FAR &, void _FAR * ),
  216.                               void _FAR *args,
  217.                               unsigned start,
  218.                               unsigned stop
  219.                             ) const
  220. {
  221.     T _FAR *res = 0;
  222.     for( unsigned cur = start; cur < stop; cur++ )
  223.         if( cond( data[cur], args ) != 0 )
  224.             res = &data[cur];
  225.     return res;
  226. }
  227.  
  228. /*------------------------------------------------------------------------*/
  229. /*                                                                        */
  230. /*  template <class T> class BI_CVectorImp                                */
  231. /*                                                                        */
  232. /*  Implements a counted vector of objects of type T.  Assumes that       */
  233. /*  T has meaningful copy semantics and a default constructor.            */
  234. /*                                                                        */
  235. /*------------------------------------------------------------------------*/
  236.  
  237. template <class T> class _CLASSTYPE BI_CVectorImp : public BI_VectorImp<T>
  238. {
  239.  
  240. public:
  241.  
  242.     BI_CVectorImp() :
  243.         count_(0),
  244.         delta(0)
  245.         {
  246.         }
  247.  
  248.     BI_CVectorImp( unsigned sz, unsigned d = 0 ) :
  249.         BI_VectorImp<T>( sz ),
  250.         count_(0),
  251.         delta(d)
  252.         {
  253.         }
  254.  
  255.     void add( T );
  256.     void addAt( T, unsigned );
  257.     void detach( T, int = 0 );
  258.     void detach( unsigned, int = 0 );
  259.  
  260.     int isEmpty() const
  261.         {
  262.         return count_ == 0;
  263.         }
  264.  
  265.     void forEach( void (_FAR *f)(T _FAR &, void _FAR *), void _FAR *args )
  266.         {
  267.         forEach( f, args, 0, count_ );
  268.         }
  269.  
  270.     void forEach( void (_FAR *func)(T _FAR &, void _FAR *),
  271.                   void _FAR *args,
  272.                   unsigned low,
  273.                   unsigned high
  274.                 )
  275.         {
  276.         BI_VectorImp<T>::forEach( func, args, low, high );
  277.         }
  278.  
  279.     T _FAR *firstThat( int (_FAR *cond)(const T _FAR &, void _FAR *),
  280.                        void _FAR *args
  281.                      ) const
  282.         {
  283.         return firstThat( cond, args, 0, count_ );
  284.         }
  285.  
  286.     T _FAR *firstThat( int (_FAR *cond)(const T _FAR &, void _FAR *),
  287.                        void _FAR *args,
  288.                        unsigned low,
  289.                        unsigned high
  290.                      ) const
  291.         {
  292.         return BI_VectorImp<T>::firstThat( cond, args, low, high );
  293.         }
  294.  
  295.     T _FAR *lastThat( int (_FAR *cond)(const T _FAR &, void _FAR *),
  296.                       void _FAR *args
  297.                     ) const
  298.         {
  299.         return lastThat( cond, args, 0, count_ );
  300.         }
  301.  
  302.     T _FAR *lastThat( int (_FAR *cond)(const T _FAR &, void _FAR *),
  303.                       void _FAR *args,
  304.                       unsigned low,
  305.                       unsigned high
  306.                     ) const
  307.         {
  308.         return BI_VectorImp<T>::lastThat( cond, args, low, high );
  309.         }
  310.  
  311.     void flush( unsigned del = 0,
  312.                 unsigned stop = UINT_MAX,
  313.                 unsigned start = 0
  314.               )
  315.         {
  316.         BI_VectorImp<T>::flush( del, stop, start ); count_ = 0;
  317.         }
  318.  
  319.     virtual unsigned find( T ) const;
  320.  
  321.     virtual unsigned top() const
  322.         {
  323.         return count_;
  324.         }
  325.  
  326.     unsigned count() const
  327.         {
  328.         return count_;
  329.         }
  330.  
  331.     virtual unsigned getDelta() const
  332.         {
  333.         return delta;
  334.         }
  335.  
  336. protected:
  337.  
  338.     unsigned count_;
  339.     unsigned delta;
  340.  
  341. };
  342.  
  343. template <class T> void BI_CVectorImp<T>::add( T t )
  344. {
  345.     if( ++count_ > lim )
  346.         resize( count_ );
  347.     data[count_-1] = t;
  348. }
  349.  
  350. template <class T> void BI_CVectorImp<T>::addAt( T t, unsigned loc )
  351. {
  352.     if( loc >= lim )
  353.         resize( loc+1 );
  354.     data[loc] = t;
  355. }
  356.  
  357. template <class T> void BI_CVectorImp<T>::detach( T t, int del )
  358. {
  359.     detach( find(t), del );
  360. }
  361.  
  362. template <class T> void BI_CVectorImp<T>::detach( unsigned loc, int del )
  363. {
  364.     if( loc >= lim )
  365.         return;
  366.     if( del )
  367.         removeData( data[loc] );
  368.     if( loc >= count_ )
  369.         {
  370.         zero( loc, loc+1 ); // removing an element that's not
  371.         return;             // in the counted portion
  372.         }
  373.     count_--;
  374.     for( unsigned cur = loc; cur < count_; cur++ )
  375.         data[cur] = data[cur+1];
  376.     zero( count_, count_+1 );
  377. }
  378.  
  379. template <class T> unsigned BI_CVectorImp<T>::find( T t ) const
  380. {
  381.     if( count_ != 0 )
  382.         {
  383.         for( unsigned loc = 0; loc < count_; loc++ )
  384.             if( data[loc] == t )
  385.                 return loc;
  386.         }
  387.     return UINT_MAX;
  388. }
  389.  
  390. /*------------------------------------------------------------------------*/
  391. /*                                                                        */
  392. /*  template <class T> class BI_SVectorImp                                */
  393. /*                                                                        */
  394. /*  Implements a sorted vector of objects of type T.  Assumes that        */
  395. /*  T has meaningful copy semantics, a meaningful < operator,             */
  396. /*  and a default constructor.                                            */
  397. /*                                                                        */
  398. /*------------------------------------------------------------------------*/
  399.  
  400. template <class T> class _CLASSTYPE BI_SVectorImp : public BI_CVectorImp<T>
  401. {
  402.  
  403. public:
  404.  
  405.     BI_SVectorImp()
  406.         {
  407.         }
  408.  
  409.     BI_SVectorImp( unsigned sz, unsigned d = 0 ) :
  410.         BI_CVectorImp<T>( sz, d )
  411.         {
  412.         }
  413.  
  414.     void add( T );
  415.  
  416.     virtual unsigned find( T ) const;
  417.  
  418. };
  419.  
  420. template <class T> void BI_SVectorImp<T>::add( T t )
  421. {
  422.     unsigned loc = count_++;
  423.     if( count_ > lim )
  424.         resize( count_ );
  425.     while( loc > 0 && t < data[loc-1] )
  426.         {
  427.         data[loc] = data[loc-1];
  428.         loc--;
  429.         }
  430.     data[loc] = t;
  431. }
  432.  
  433. template <class T> unsigned BI_SVectorImp<T>::find( T t ) const
  434. {
  435.     unsigned lower = 0;
  436.     unsigned upper = count_-1;
  437.     if( count_ != 0 )
  438.         {
  439.         while( lower < upper && upper != UINT_MAX )
  440.             {
  441.             unsigned middle = (lower+upper)/2;
  442.             if( data[middle] == t )
  443.                 return middle;
  444.             if( data[middle] < t )
  445.                 lower = middle+1;
  446.             else
  447.                 upper = middle-1;
  448.             }
  449.         }
  450.     if( lower == upper && data[lower] == t )
  451.         return lower;
  452.     else
  453.         return UINT_MAX;
  454. }
  455.  
  456. /*------------------------------------------------------------------------*/
  457. /*                                                                        */
  458. /*  template <class T> class BI_VectorIteratorImp                         */
  459. /*                                                                        */
  460. /*  Implements a vector iterator.  This iterator works with any direct    */
  461. /*  vector.  For indirect vectors, see BI_IVectorIteratorImp.             */
  462. /*                                                                        */
  463. /*------------------------------------------------------------------------*/
  464.  
  465. template <class T> class _CLASSTYPE BI_VectorIteratorImp
  466. {
  467.  
  468. public:
  469.  
  470.     BI_VectorIteratorImp( const BI_VectorImp<T> _FAR &v )
  471.         {
  472.         vect = &v;
  473.         restart(0,v.limit());
  474.         }
  475.  
  476.     BI_VectorIteratorImp( const BI_VectorImp<T> _FAR &v,
  477.                           unsigned start,
  478.                           unsigned stop
  479.                         )
  480.         {
  481.         vect = &v;
  482.         restart( start, stop );
  483.         }
  484.  
  485.  
  486.     operator int()
  487.         {
  488.         return cur < upper;
  489.         }
  490.  
  491.     T current()
  492.         {
  493.         return (cur < upper) ? (*vect)[cur] : (*vect)[upper-1];
  494.         }
  495.  
  496.     T operator ++ ( int )
  497.         {
  498.         if( cur >= upper )
  499.             return (*vect)[upper-1];
  500.         else
  501.             return (*vect)[cur++];
  502.         }
  503.  
  504.     T operator ++ ()
  505.         {
  506.         if( cur < upper )
  507.             cur++;
  508.         if( cur >= upper )
  509.             return (*vect)[upper-1];
  510.         else
  511.             return (*vect)[cur];
  512.         }
  513.  
  514.     void restart()
  515.         {
  516.         restart(lower,upper);
  517.         }
  518.  
  519.     void restart( unsigned start, unsigned stop )
  520.         {
  521.         cur = lower = start;
  522.         upper = stop;
  523.         }
  524.  
  525. private:
  526.  
  527.     const BI_VectorImp<T> _FAR *vect;
  528.     unsigned cur;
  529.     unsigned lower, upper;
  530.  
  531. };
  532.  
  533. /*------------------------------------------------------------------------*/
  534. /*                                                                        */
  535. /*  template <class T, class Vect> class BI_InternalIVectorImp            */
  536. /*                                                                        */
  537. /*  Implements a vector of pointers to objects of type T.                 */
  538. /*  This is implemented through the form of BI_VectorImp specified by     */
  539. /*  Vect.  Since pointers always have meaningful copy semantics,          */
  540. /*  this class can handle any type of object.                             */
  541. /*                                                                        */
  542. /*------------------------------------------------------------------------*/
  543.  
  544. template <class T, class Vect> class _CLASSTYPE BI_InternalIVectorImp :
  545.     public Vect
  546. {
  547.  
  548. public:
  549.  
  550.     BI_InternalIVectorImp( unsigned sz, unsigned d = 0 ) :
  551.         Vect( sz, d )
  552.         {
  553.         zero( 0, sz );
  554.         }
  555.  
  556.     ~BI_InternalIVectorImp()
  557.         {
  558.         flush();
  559.         }
  560.  
  561.     T _FAR * _FAR & operator [] ( unsigned index )
  562.         {
  563.         PRECONDITION( lim == 0 || data != 0 && index < lim );
  564.         return (T _FAR *)(data[index]);
  565.         }
  566.  
  567.     T _FAR * _FAR & operator [] ( unsigned index ) const
  568.         {
  569.         PRECONDITION( lim > 0 && data != 0 && index < lim );
  570.         return (T _FAR *)(data[index]);
  571.         }
  572.  
  573.     void flush( unsigned = 0, unsigned = UINT_MAX, unsigned = 0 );
  574.  
  575.     void forEach( void (_FAR *f)(T _FAR &, void _FAR *), void _FAR *args )
  576.         {
  577.         forEach( f, args, 0, lim );
  578.         }
  579.  
  580.     void forEach( void (_FAR *)(T _FAR &, void _FAR *),
  581.                   void _FAR *,
  582.                   unsigned,
  583.                   unsigned
  584.                 );
  585.  
  586.     T _FAR *firstThat( int (_FAR *cond)(const T _FAR &, void _FAR *),
  587.                        void _FAR *args
  588.                      ) const
  589.         {
  590.         return firstThat( cond, args, 0, lim );
  591.         }
  592.  
  593.     T _FAR *firstThat( int (_FAR *)(const T _FAR &, void _FAR *),
  594.                        void _FAR *,
  595.                        unsigned,
  596.                        unsigned
  597.                      ) const;
  598.  
  599.     T _FAR *lastThat( int (_FAR *cond)(const T _FAR &, void _FAR *),
  600.                       void _FAR *args
  601.                     ) const
  602.         {
  603.         return lastThat( cond, args, 0, lim );
  604.         }
  605.  
  606.     T _FAR *lastThat( int (_FAR *)(const T _FAR &, void _FAR *),
  607.                       void _FAR *,
  608.                       unsigned,
  609.                       unsigned
  610.                     ) const;
  611.  
  612.     virtual void zero( unsigned, unsigned );
  613.  
  614. protected:
  615.  
  616.     virtual void removeData( void _FAR *t )
  617.         {
  618.         delete (T _FAR *)t;
  619.         }
  620.  
  621. private:
  622.  
  623.     static void delObj( T _FAR &, void _FAR * );
  624.  
  625. };
  626.  
  627. template <class T, class Vect>
  628. void BI_InternalIVectorImp<T,Vect>::delObj( T _FAR &tRef, void _FAR *vect )
  629. {
  630.     ((BI_InternalIVectorImp<T,Vect> *)vect)->removeData( &tRef );
  631. }
  632.  
  633. template <class T, class Vect>
  634. void BI_InternalIVectorImp<T,Vect>::flush(
  635.                                            unsigned del,
  636.                                            unsigned upr,
  637.                                            unsigned lwr
  638.                                          )
  639. {
  640.     upr = min( upr, limit() );
  641.     if( del )
  642.         forEach( delObj, this, lwr, upr );
  643.     zero( lwr, upr );
  644.     Vect::flush( del, upr, lwr );
  645. }
  646.  
  647. template <class T, class Vect>
  648. void BI_InternalIVectorImp<T,Vect>::forEach( void (_FAR *f)( T _FAR &, void _FAR * ),
  649.                                              void _FAR *args,
  650.                                              unsigned start,
  651.                                              unsigned stop
  652.                                            )
  653. {
  654.     for( unsigned cur = start; cur < stop; cur++ )
  655.         if( data[cur] != 0 )
  656.             f( *(T _FAR *)(data[cur]), args );
  657. }
  658.  
  659. template <class T, class Vect>
  660. T _FAR *BI_InternalIVectorImp<T,Vect>::firstThat( int (_FAR *cond)( const T _FAR &, void _FAR * ),
  661.                                              void _FAR *args,
  662.                                              unsigned start,
  663.                                              unsigned stop
  664.                                            ) const
  665. {
  666.     for( unsigned cur = start; cur < stop; cur++ )
  667.         if( data[cur] != 0 && cond( *(T _FAR *)(data[cur]), args ) != 0 )
  668.             return (T _FAR *)data[cur];
  669.     return 0;
  670. }
  671.  
  672. template <class T, class Vect>
  673. T _FAR *BI_InternalIVectorImp<T,Vect>::lastThat( int (_FAR *cond)( const T _FAR &, void _FAR * ),
  674.                                             void _FAR *args,
  675.                                             unsigned start,
  676.                                             unsigned stop
  677.                                           ) const
  678. {
  679.     T _FAR *res = 0;
  680.     for( unsigned cur = start; cur < stop; cur++ )
  681.         if( data[cur] != 0 && cond( *(T _FAR *)(data[cur]), args ) != 0 )
  682.             res = (T _FAR *)data[cur];
  683.     return res;
  684. }
  685.  
  686. template <class T, class Vect>
  687. void BI_InternalIVectorImp<T,Vect>::zero( unsigned lwr, unsigned upr )
  688. {
  689.     for( unsigned i = lwr; i < min( limit(), upr ); i++ )
  690.         data[i] = 0;
  691. }
  692.  
  693. /*------------------------------------------------------------------------*/
  694. /*                                                                        */
  695. /*  template <class T> class BI_IVectorImp                                */
  696. /*                                                                        */
  697. /*  Implements a vector of pointers to objects of type T.                 */
  698. /*  This is implemented through the template BI_InternalIVectorImp.       */
  699. /*  Since pointers always have meaningful copy semantics, this class      */
  700. /*  can handle any type of object.                                        */
  701. /*                                                                        */
  702. /*------------------------------------------------------------------------*/
  703.  
  704. template <class T> class _CLASSTYPE BI_IVectorImp :
  705.     public BI_InternalIVectorImp<T, BI_VectorImp<void _FAR *> >
  706. {
  707.  
  708. public:
  709.  
  710.     BI_IVectorImp( unsigned sz ) :
  711.         BI_InternalIVectorImp<T, BI_VectorImp<void _FAR *> >(sz)
  712.         {
  713.         }
  714.  
  715.  
  716. };
  717.  
  718. /*------------------------------------------------------------------------*/
  719. /*                                                                        */
  720. /*  template <class T> class BI_ICVectorImp                               */
  721. /*                                                                        */
  722. /*  Implements a counted vector of pointers to objects of type T.         */
  723. /*  Since pointers always have meaningful copy semantics, this class      */
  724. /*  can handle any type of object.                                        */
  725. /*                                                                        */
  726. /*------------------------------------------------------------------------*/
  727.  
  728. template <class T> class _CLASSTYPE BI_ICVectorImp :
  729.     public BI_InternalIVectorImp<T, BI_CVectorImp<void _FAR *> >
  730. {
  731.  
  732. public:
  733.  
  734.     BI_ICVectorImp( unsigned sz, unsigned d = 0 ) :
  735.         BI_InternalIVectorImp<T, BI_CVectorImp<void _FAR *> >(sz)
  736.         {
  737.         delta = d;
  738.         }
  739.  
  740.     unsigned find( T _FAR *t ) const
  741.         {
  742.         return find( (void _FAR *)t );
  743.         }
  744.  
  745.     void add( T _FAR *t );
  746.  
  747. protected:
  748.  
  749.     virtual unsigned find( void _FAR * ) const;
  750.  
  751. };
  752.  
  753. template <class T> unsigned BI_ICVectorImp<T>::find( void _FAR *t ) const
  754. {
  755.     if( limit() != 0 )
  756.         {
  757.         for( unsigned loc = 0; loc < limit(); loc++ )
  758.             if( data[loc] &&
  759.                 *(const T _FAR *)(data[loc]) == *(const T _FAR *)t
  760.               )
  761.                 return loc;
  762.         }
  763.     return UINT_MAX;
  764. }
  765.  
  766. template <class T > void BI_ICVectorImp<T>::add( T _FAR *t )
  767. {
  768.     while( count_ < limit() && (*this)[count_] != 0 )
  769.         count_++;
  770.     BI_InternalIVectorImp<T, BI_CVectorImp<void _FAR *> >::add(t);
  771. }
  772.  
  773. /*------------------------------------------------------------------------*/
  774. /*                                                                        */
  775. /*  template <class T> class BI_ISVectorImp                               */
  776. /*                                                                        */
  777. /*  Implements a sorted vector of pointers to objects of type T.          */
  778. /*  This is implemented through the template BI_InternalIVectorImp.       */
  779. /*  Since pointers always have meaningful copy semantics, this class      */
  780. /*  can handle any type of object.                                        */
  781. /*                                                                        */
  782. /*------------------------------------------------------------------------*/
  783.  
  784. template <class T> class _CLASSTYPE BI_ISVectorImp :
  785.     public BI_InternalIVectorImp<T, BI_SVectorImp<void _FAR *> >
  786. {
  787.  
  788. public:
  789.  
  790.     BI_ISVectorImp( unsigned sz, unsigned d = 0 ) :
  791.         BI_InternalIVectorImp<T, BI_SVectorImp<void _FAR *> >(sz)
  792.         {
  793.         delta = d;
  794.         }
  795.  
  796.     unsigned find( T _FAR *t ) const
  797.         {
  798.         return find( (void _FAR *)t );
  799.         }
  800.  
  801.     void add( T _FAR *t );
  802.  
  803. protected:
  804.  
  805.     virtual unsigned find( void _FAR * ) const;
  806.  
  807. };
  808.  
  809. template <class T> unsigned BI_ISVectorImp<T>::find( void _FAR *t ) const
  810. {
  811.     unsigned lower = 0;
  812.     unsigned upper = count_-1;
  813.     if( count_ != 0 )
  814.         {
  815.         while( lower < upper )
  816.             {
  817.             unsigned middle = (lower+upper)/2;
  818.             if( *(const T _FAR *)(data[middle]) == *(const T _FAR *)t )
  819.                 return middle;
  820.             if( *(const T _FAR *)(data[middle]) < *(const T _FAR *)t )
  821.                 lower = middle+1;
  822.             else
  823.                 upper = middle-1;
  824.             }
  825.         }
  826.     if( lower == upper && *(const T _FAR*)(data[lower]) == *(const T _FAR*)t )
  827.         return lower;
  828.     else
  829.         return UINT_MAX;
  830. }
  831.  
  832. template <class T> void BI_ISVectorImp<T>::add( T _FAR *t )
  833. {
  834.     unsigned loc = count_++;
  835.     if( count_ > lim )
  836.         resize( count_ );
  837.     while( loc > 0 && *t < *((T _FAR *)(*this)[loc-1]) )
  838.         {
  839.         data[loc] = data[loc-1];
  840.         loc--;
  841.         }
  842.     data[loc] = t;
  843. }
  844.  
  845. /*------------------------------------------------------------------------*/
  846. /*                                                                        */
  847. /*  template <class T> class BI_IVectorIteratorImp                        */
  848. /*                                                                        */
  849. /*  Implements a vector iterator.  This iterator works with any indirect  */
  850. /*  vector.  For direct vectors, see BI_VectorIteratorImp.                */
  851. /*                                                                        */
  852. /*------------------------------------------------------------------------*/
  853.  
  854. template <class T> class _CLASSTYPE BI_IVectorIteratorImp :
  855.     public BI_VectorIteratorImp<void _FAR *>
  856. {
  857.  
  858. public:
  859.  
  860.     BI_IVectorIteratorImp( const BI_VectorImp<void _FAR *> _FAR &v ) :
  861.         BI_VectorIteratorImp<void _FAR *>(v)
  862.         {
  863.         bump();
  864.         }
  865.  
  866.     BI_IVectorIteratorImp( const BI_VectorImp<void _FAR *> _FAR &v,
  867.                            unsigned l, unsigned u
  868.                          ) :
  869.         BI_VectorIteratorImp<void _FAR *>(v,l,u)
  870.         {
  871.         bump();
  872.         }
  873.  
  874.     T _FAR *current()
  875.         {
  876.         return (T _FAR *)BI_VectorIteratorImp<void _FAR *>::current();
  877.         }
  878.  
  879.     T _FAR *operator ++ ( int );
  880.     T _FAR *operator ++ ();
  881.  
  882.     void restart()
  883.         {
  884.         BI_VectorIteratorImp<void _FAR *>::restart();
  885.         bump();
  886.         }
  887.  
  888.     void restart( unsigned start, unsigned stop )
  889.         {
  890.         BI_VectorIteratorImp<void _FAR *>::restart( start, stop );
  891.         bump();
  892.         }
  893.  
  894. private:
  895.  
  896.     void bump();
  897.  
  898. };
  899.  
  900. template <class T> T _FAR * BI_IVectorIteratorImp<T>::operator ++ ()
  901. {
  902.     BI_VectorIteratorImp<void _FAR *>::operator++();
  903.     bump();
  904.     return (T _FAR *)current();
  905. }
  906.  
  907. template <class T> T _FAR * BI_IVectorIteratorImp<T>::operator ++ ( int )
  908. {
  909.     void *temp = current();
  910.     BI_VectorIteratorImp<void _FAR *>::operator++(1);
  911.     bump();
  912.     return (T _FAR *)temp;
  913. }
  914.  
  915. template <class T> void BI_IVectorIteratorImp<T>::bump()
  916. {
  917.     while( *this != 0 && current() == 0 )
  918.         BI_VectorIteratorImp<void _FAR *>::operator++();
  919. }
  920.  
  921. #if defined( __BCOPT__ ) && !defined( _ALLOW_po )
  922. #pragma option -po.
  923. #endif
  924. #pragma option -Vo.
  925.  
  926. #endif // __VECTIMP_H
  927.