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