home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 1997 May / Pcwk0597.iso / sybase / starbuck / h.z / WCVBASE.H < prev    next >
C/C++ Source or Header  |  1996-07-24  |  25KB  |  913 lines
  1. //
  2. //  wcvbase.h    Definitions for the base classes used by
  3. //               the WATCOM Container Vector Class
  4. //
  5. //  Copyright by WATCOM International Corp. 1988-1996.  All rights reserved.
  6. //
  7. #ifndef _WCVBASE_H_INCLUDED
  8. #define _WCVBASE_H_INCLUDED
  9.  
  10. #ifndef __cplusplus
  11. #error wcvbase.h is for use with C++
  12. #endif
  13.  
  14. #ifndef _WCEXCEPT_H_INCLUDED
  15.  #include <wcexcept.h>
  16. #endif
  17.  
  18.  
  19. // "Warning! W549: 'sizeof' operand contains compiler generated information"
  20. #pragma warning 549 9 
  21.  
  22. #if defined( new ) && defined( _WNEW_OPERATOR )
  23. #  undef new
  24. #endif
  25. #if defined( delete ) && defined( _WDELETE_OPERATOR )
  26. #  undef delete
  27. #endif
  28.  
  29. //
  30. //  constants used by vector classes
  31. //
  32.  
  33. //
  34. //  The default number of elements a vector is created to store.  Specifying
  35. //  the first parameter to the vector constructors will override this value.
  36. //
  37. const size_t WCDEFAULT_VECTOR_LENGTH = 10;
  38.  
  39. //
  40. //  The default number of elements a vector will grow by when an element is
  41. //  inserted into a full vector (the number of entries in the vector is
  42. //  the same as the vector length).  This growth is performed using the
  43. //  resize member function.
  44. //  This constant applies only ordered and sorted vectors with the
  45. //  resize_required exception disabled.
  46. //  Specifying the second paramter to the ordered and sorted vector
  47. //  constructors will override this value.
  48. //
  49. const size_t WCDEFAULT_VECTOR_RESIZE_GROW = 5;
  50.  
  51.  
  52.  
  53. //
  54. //  Implementation note:
  55. //  From the user's view, all vector elements have been constructed
  56. //  (possibly with only the default constructor).
  57. //
  58. //  In order to avoid any overhead from default intializing and then
  59. //  immediately assigning a value to a vector element, the C-array used
  60. //  to implement arrays is uninitialized (contains raw memory with none
  61. //  of Type's constuctors called) until it needs to be.  This means
  62. //  more efficient copy constucters can be used, and default constuctors
  63. //  do not get called unless they need to.  This is especially helpfull
  64. //  for the resize member function.
  65. //  Initializing previously allocated chunks of memory requires calling the
  66. //  new operator with the allocated memory as a placement syntax parameter.
  67. //  If Type defines an operator new with any parameters, then Type must
  68. //  provide the following operator new for the vector classes:
  69. //  void *operator new( size_t, void *ptr ) { return ptr; }
  70. //  WCValVector and WCPtrVector are implemented so that whenever the user
  71. //  accesses an element which has not been initialized, all uninitalized
  72. //  elements upto and including the accessed element are initialized using
  73. //  Type's default constructor.
  74. //  ordered and sorted vectors do not have this "random access" issue, since
  75. //  the index operator can only index previously initialized elements.  The
  76. //  last element in a vector is copied in using the copy constructor on and
  77. //  each insert, and the last element(s) in a vector is/are destructed after
  78. //  a remove is performed, so that the number of initialized elements in a
  79. //  vector is always equal to the number of entries in the vector.
  80. //  
  81.  
  82.  
  83.  
  84.  
  85. //
  86. //  This class is the base class for all vector container classes.
  87. //  WCExcept provides common exception handling for all vectors.
  88. //
  89. //  It is an abstract base class to prevent objects of this class
  90. //  from being created.
  91. //
  92.  
  93. template<class Type>
  94. class WCBareVectorBase : public WCExcept {
  95. protected:
  96.     Type *vector;
  97.     int vector_len;
  98.     int num_init;
  99.  
  100.     // WCValVector, WCPtrVector assignment operator base
  101.     void base_assign( const WCBareVectorBase * );
  102.     // WCValVector, WCPtrVector copy constructor base
  103.     void base_construct( const WCBareVectorBase * );
  104.     int base_index_check( int ) const;
  105.     virtual void base_init_upto( int );
  106. public:
  107.     WCBareVectorBase( size_t length );
  108.     virtual ~WCBareVectorBase() = 0;
  109.  
  110.     int operator==( const WCBareVectorBase & rhs ) const {
  111.     return( this == &rhs );
  112.     };
  113.  
  114.     inline void clear() {
  115.     resize( 0 );
  116.     };
  117.  
  118.     WCbool resize( size_t new_length );
  119. };
  120.  
  121.  
  122. template<class Type>
  123. void WCBareVectorBase<Type>::base_assign( const WCBareVectorBase * orig ) {
  124.     if( this != orig ) {
  125.     resize( 0 );
  126.     base_construct( orig );
  127.     }
  128. };
  129.  
  130.  
  131. template<class Type>
  132. void WCBareVectorBase<Type>::base_construct( const WCBareVectorBase * orig ) {
  133.     WCExcept::base_construct( orig );
  134.     num_init = orig->num_init;
  135.     vector_len = orig->vector_len;
  136.     if( vector_len > 0 ) {
  137.     // get the raw memory for the vector's C-array
  138.     vector = ( Type * )new char[ sizeof( Type ) * vector_len ];
  139.     if( vector != 0 ) {
  140.         for( int i = 0; i < num_init; i++ ) {
  141.         // Copy all initialized elements from orig to vector, using
  142.         // Type's copy constructor.  The placement parameter is used
  143.         // so that the C-array's raw memory is initialized, instead
  144.         // of allocating a new chunck of memory.
  145.         new( &( vector[ i ] ) ) Type( orig->vector[ i ] );
  146.         }
  147.     } else {
  148.         num_init = 0;
  149.         vector_len = 0;
  150.         base_throw_out_of_memory();
  151.     }
  152.     } else {
  153.     vector = 0;
  154.     }
  155. };
  156.         
  157.  
  158. template<class Type>
  159. int WCBareVectorBase<Type>::base_index_check( int index ) const {
  160.     int entry_index = vector_len - 1;
  161.     if( index < 0 || index > entry_index ) {
  162.     base_throw_index_range();
  163.         if( index < 0 ) {
  164.             index = 0;
  165.         } else {
  166.         if( entry_index <= 0 ) {
  167.         index = 0;
  168.         } else {
  169.         index = entry_index;
  170.         }
  171.         }
  172.     }
  173.     return( index );
  174. };
  175.  
  176.  
  177. //
  178. //  Initialize all unintialized elements upto and including the index'th
  179. //  element using Type's default constructor.
  180. //
  181.  
  182. template<class Type>
  183. void WCBareVectorBase<Type>::base_init_upto( int index ) {
  184.     if( index >= num_init ){
  185.     for( int i = num_init; i <= index; i++ ){
  186.         // initialize elements using Type's default constructor.  The
  187.         // placement parameter is used so that the C-array's raw memory
  188.         // is initialized, instead of allocating a new chunck of memory.
  189.         new( &( vector[ i ] ) ) Type();
  190.     }
  191.     num_init = index + 1;
  192.     }
  193. }
  194.     
  195.  
  196. template<class Type>
  197. WCBareVectorBase<Type>::WCBareVectorBase( size_t length ){
  198.     vector_len = length;
  199.     num_init = 0;
  200.     if( length > 0 ){
  201.     // get the raw memory for the vector's C-array
  202.     vector = ( Type * )new char[ sizeof( Type ) * length ];
  203.     if( vector == 0 ) {
  204.         vector_len = 0;
  205.     }
  206.     } else {
  207.     vector = 0;
  208.     }
  209. };
  210.  
  211.  
  212. template<class Type>
  213. virtual WCBareVectorBase<Type>::~WCBareVectorBase() {
  214.     if( vector ) {
  215.     base_throw_not_empty();
  216.     // call destructors for any initialized elements
  217.     for( int i = 0; i < num_init; i++ ){
  218.         vector[ i ].~Type();
  219.     }
  220.     // delete the C-array (now just raw memory)
  221.     delete [] (char *)vector;
  222.     }
  223. };
  224.  
  225.  
  226. template<class Type>
  227. WCbool WCBareVectorBase<Type>::resize( size_t new_length ) {
  228.     Type *new_vector;
  229.     int max_index = num_init < new_length ? num_init : new_length;
  230.  
  231.     if( new_length > 0 ) {
  232.     // get the raw memory for the vector's C-array
  233.     new_vector = ( Type * )new char[ sizeof( Type ) * new_length ];
  234.     if( new_vector == 0 ){
  235.         base_throw_out_of_memory();
  236.         return( FALSE );
  237.     }
  238.     // Copy all initialized elements from vector (the old C-array) to
  239.     // new_vector (the new C-array), using Type's copy constructor.
  240.     // The placement parameter is used so that the C-array's raw memory
  241.     // is initialized, instead of allocating a new chunck of memory.
  242.     for( int i = 0; i < max_index; i++ ){
  243.         new( &( new_vector[ i ] ) ) Type( vector[ i ] );
  244.     }
  245.     } else {
  246.     new_vector = 0;
  247.     }
  248.     // call destructors for any initialized elements in the old vector
  249.     for( int i = 0; i < num_init; i++ ){
  250.     vector[ i ].~Type();
  251.     }
  252.     // delete the old C-array (now just raw memory)
  253.     delete [] (char *) vector;
  254.     num_init = max_index;
  255.     vector = new_vector;
  256.     vector_len = new_length;
  257.     return( TRUE );
  258. };
  259.  
  260.  
  261. //
  262. //  This class is the base class for Ptr and Val OrderedVector and SortedVector
  263. //  container classes.
  264. //
  265. //  It is an abstract base class to prevent objects of this class
  266. //  from being created.
  267. //
  268.  
  269. template<class Type>
  270. class WCVectorBase : public WCBareVectorBase<Type> {
  271. protected:
  272.     unsigned num_entries;
  273.     unsigned resize_grow;    // the number of elements to grow a vector
  274.                     // when inserting into a full vector
  275.  
  276.     enum find_type {        // for the base_find function
  277.     find_any,        // find any matching element in the vector
  278.     find_first,        // find first matching element in vector
  279.     next_mult_find,        // find next matching element in vector
  280.     find_for_insert };    // find index to insert element in sorted vector
  281.  
  282.     // the assignment operator base
  283.     void base_assign( const WCVectorBase * );
  284.     // the copy constructor base
  285.     void base_construct( const WCVectorBase * );
  286.     virtual int base_equivalent( const Type &elem1
  287.                        , const Type &elem2 ) const = 0;
  288.     // find first parm in vector, with specified find_type.  index passes
  289.     // in where to start the search, and returns the index where first param
  290.     // found if returns true
  291.     virtual WCbool base_find( const Type &, find_type, int * index ) const = 0;
  292.     int base_index_check( int ) const;
  293.     WCbool base_insert_at( int, const Type& );
  294.     void base_remove_at( int );
  295.  
  296. public:
  297.     inline WCVectorBase( size_t length, unsigned grow )
  298.                 : num_entries( 0 ), resize_grow( grow ),
  299.                     WCBareVectorBase<Type>( length ) {};
  300.     inline virtual ~WCVectorBase() = 0;
  301.  
  302.     inline void clear() {
  303.     WCBareVectorBase::clear();
  304.     num_entries = 0;
  305.     };
  306.  
  307.     WCbool contains( const Type & ) const;
  308.  
  309.     inline unsigned entries() const {
  310.     return( num_entries );
  311.     };
  312.  
  313.     WCbool find( const Type &elem, Type &ret_val ) const;
  314.  
  315.     inline Type first() const {
  316.     return( vector[ base_index_check( 0 ) ] );
  317.     }
  318.  
  319.     int index( const Type & ) const;
  320.  
  321.     inline WCbool isEmpty() const {
  322.     return( num_entries == 0 );
  323.     };
  324.  
  325.     inline Type last() const {
  326.     return( vector[ base_index_check( num_entries - 1 ) ] );
  327.     }
  328.  
  329.     int occurrencesOf( const Type & elem ) const;
  330.     
  331.     WCbool remove( const Type & elem );
  332.  
  333.     unsigned removeAll( const Type & elem );
  334.  
  335.     WCbool removeAt( int );
  336.  
  337.     inline WCbool removeFirst() {
  338.     return( removeAt( 0 ) );
  339.     };
  340.  
  341.     inline WCbool removeLast() {
  342.     return( removeAt( num_entries - 1 ) );
  343.     };
  344.  
  345.     WCbool resize( size_t );
  346.  
  347.     inline Type& operator[] ( int index ) {
  348.     return( vector[ base_index_check( index ) ] );
  349.     };
  350.  
  351.     inline const Type& operator[] ( int index ) const {
  352.     return( vector[ base_index_check( index ) ] );
  353.     };
  354. };
  355.  
  356.  
  357. template<class Type>
  358. void WCVectorBase<Type>::base_assign( const WCVectorBase * orig ) {
  359.     if( this != orig ) {
  360.     resize( 0 );
  361.     base_construct( orig );
  362.     }
  363. };
  364.  
  365.  
  366. template<class Type>
  367. void WCVectorBase<Type>::base_construct( const WCVectorBase * orig ) {
  368.     WCBareVectorBase<Type>::base_construct( orig );
  369.     resize_grow = orig->resize_grow;
  370.     if( vector != 0 ) {
  371.     num_entries = orig->num_entries;
  372.     } else {
  373.     num_entries = 0;
  374.     }
  375. }
  376.     
  377.  
  378. //
  379. //  Check to see if index is valid, and return the closest valid index.
  380. //  If index is invalid then exceptions are thrown if enabled, and if 
  381. //  exceptions are disabled and the vector has no entries, then the first
  382. //  element is default initialized, effectively inserting a first element
  383. //  (this is done for the index operators and first and last member
  384. //  functions)
  385. //
  386. template<class Type>
  387. int WCVectorBase<Type>::base_index_check( int index ) const {
  388.     int entry_index = num_entries - 1;
  389.     if( index < 0 || index > entry_index ) {
  390.     if( num_entries == 0 ) {
  391.         base_throw_empty_container();
  392.         base_throw_index_range();
  393.         // insert the first element as a default intialized element
  394.         WCVectorBase<Type> * const non_const_this
  395.             = ( WCVectorBase<Type> * )this;
  396.         if( vector_len == 0 ) {
  397.             if( !non_const_this->resize( 1 ) ) {
  398.             // An invalid operation on an empty vector, and out memory.
  399.             // return the first element of a NULL C-array.
  400.             return( 0 );
  401.         }
  402.         }
  403.         non_const_this->base_init_upto( 0 );
  404.         non_const_this->num_entries = 1;
  405.         index = 0;
  406.     } else if( index < 0 ) {
  407.             index = 0;
  408.         base_throw_index_range();
  409.         } else {
  410.         index = entry_index;
  411.         base_throw_index_range();
  412.         }
  413.     }
  414.     return( index );
  415. };
  416.  
  417.  
  418. //
  419. //  insert new_entry before the element currently at index.  If index is the
  420. //  number of entries, insert new_entry as the last element.
  421. //
  422.  
  423. template<class Type>
  424. WCbool WCVectorBase<Type>::base_insert_at( int index, const Type& new_entry ) {
  425.     if( index > (int)num_entries ) {
  426.     base_throw_index_range();
  427.     index = num_entries;
  428.     } else if( index < 0 ) {
  429.     base_throw_index_range();
  430.     index = 0;
  431.     }
  432.     if( num_entries == vector_len ){
  433.     base_throw_resize_required();
  434.     // automatically grow the vector if it was full, the resize_required
  435.     // exception is disabled, and the amount to grow the vector is greater
  436.     // than zero.
  437.     if( ( resize_grow == 0 )
  438.       ||( !resize( vector_len + resize_grow ) ) ) {
  439.         return( FALSE );
  440.     }
  441.     }
  442.     // the last entry in the vector must be copied in, since it was previously
  443.     // unused, and unused elements are unitialized.
  444.     if( index == num_entries ){
  445.     new( &( vector[ index ] ) ) Type( new_entry );
  446.     } else {
  447.     new( &( vector[ num_entries ] ) ) Type( vector[ num_entries - 1 ] );
  448.     for( int i = num_entries - 2; i >= index; i-- ) {
  449.         vector[ i + 1 ] = vector[ i ];
  450.     }
  451.     vector[ index ] = new_entry;
  452.     }
  453.     num_entries++;
  454.     num_init++;
  455.     return( TRUE );
  456. }
  457.  
  458.  
  459. template<class Type>
  460. void WCVectorBase<Type>::base_remove_at( int index ) {
  461.     for( int i = index; i < num_entries - 1; i++ ) {
  462.     vector[ i ] = vector[ i + 1 ];
  463.     }
  464.     // destruct the last element in the array, so that unused elements are
  465.     // unitialized.
  466.     vector[ num_entries - 1 ].~Type();
  467.     num_entries--;
  468.     num_init--;
  469. }
  470.     
  471.  
  472. template<class Type>
  473. WCVectorBase<Type>::~WCVectorBase() {};
  474.  
  475.  
  476. template<class Type>
  477. WCbool WCVectorBase<Type>::contains( const Type &elem ) const {
  478.     int index = 0;
  479.  
  480.     if( ( num_entries != 0 )
  481.       &&( base_find( elem, find_any, &index ) ) ) {
  482.     return( TRUE );
  483.     } else {
  484.     return( FALSE );
  485.     }
  486. }
  487.  
  488.  
  489. template<class Type>
  490. WCbool WCVectorBase<Type>::find( const Type &elem, Type &ret_val ) const {
  491.     int index = 0;
  492.     if( ( num_entries > 0 )
  493.       &&( base_find( elem, find_first, &index ) ) ) {
  494.     ret_val = vector[ index ];
  495.     return( TRUE );
  496.     } else {
  497.     Type temp;
  498.     ret_val = temp;
  499.     return( FALSE );
  500.     }
  501. };
  502.     
  503.  
  504. template<class Type>
  505. int WCVectorBase<Type>::index( const Type & elem ) const {
  506.     int ret_index = 0;
  507.  
  508.     if( ( num_entries > 0 )
  509.       &&( base_find( elem, find_first, &ret_index ) ) ) {
  510.     return( ret_index );
  511.     } else {
  512.     return( -1 );
  513.     }
  514. }
  515.  
  516.  
  517. template<class Type>
  518. int WCVectorBase<Type>::occurrencesOf( const Type & elem ) const {
  519.     int index = 0;
  520.     int count = 0;
  521.  
  522.     if( ( num_entries > 0 )
  523.       &&( base_find( elem, find_first, &index ) ) ) {
  524.     do {
  525.         count++;
  526.         index++;
  527.     } while( base_find( elem, next_mult_find, &index ) );
  528.     }
  529.     return( count );
  530. };
  531.     
  532.  
  533. template<class Type>
  534. WCbool WCVectorBase<Type>::remove( const Type & elem ) {
  535.     int index = 0;
  536.  
  537.     if( ( num_entries > 0 )
  538.       &&( base_find( elem, find_first, &index ) ) ) {
  539.     base_remove_at( index );
  540.     return( TRUE );
  541.     } else {
  542.     return( FALSE );
  543.     }
  544. };
  545.  
  546.  
  547. template<class Type>
  548. unsigned WCVectorBase<Type>::removeAll( const Type & elem ) {
  549.     int found_index = 0;
  550.     int count = 0;
  551.  
  552.     // make sure only elements which need to be moved are moved
  553.     // no element is moved more than once
  554.     if( ( num_entries > 0 )
  555.       &&( base_find( elem, find_first, &found_index ) ) ) {
  556.     // at least one element is being removed
  557.     int curr_index = found_index;
  558.     count++;
  559.     found_index++;
  560.     while( base_find( elem, next_mult_find, &found_index ) ) {
  561.         // move entries which were between any occurrances of elem
  562.         for( ;curr_index < found_index - count; curr_index++ ){
  563.         vector[ curr_index ] = vector[ curr_index + count ];
  564.         }
  565.         count++;
  566.         found_index++;
  567.     };
  568.     // move entries after any occurances of elem
  569.     for( ;curr_index < num_entries - count; curr_index++ ){
  570.         vector[ curr_index ] = vector[ curr_index + count ];
  571.     }
  572.     // destruct elements at the end of the vector which were copied or
  573.     // removed, so that unused elements are unitialized
  574.     for( ;curr_index < num_entries; curr_index++ ){
  575.             vector[ curr_index ].~Type();
  576.     }
  577.     num_entries -= count;
  578.     num_init -= count;
  579.     }
  580.     return( count );
  581. }
  582.  
  583.  
  584.  
  585. template<class Type>
  586. WCbool WCVectorBase<Type>::removeAt( int index ) {
  587.     if( num_entries == 0 ) {
  588.     base_throw_empty_container();
  589.     return( FALSE );
  590.     } else {
  591.     index = base_index_check( index );
  592.     base_remove_at( index );
  593.     return( TRUE );
  594.     }
  595. };
  596.     
  597.  
  598. template<class Type>
  599. WCbool WCVectorBase<Type>::resize( size_t new_length ) {
  600.     WCbool return_val = WCBareVectorBase<Type>::resize( new_length );
  601.     if( return_val && num_entries > new_length ){
  602.     num_entries = new_length;
  603.     }
  604.     return( return_val );
  605. };
  606.  
  607.  
  608.  
  609.  
  610. //
  611. // WCOrderedVectorBase     - this is the base class for WCValOrderedVector and
  612. //              WCPtrOrderedVector.
  613. //
  614. // This is a abstract class to prevent objects of this type being created
  615. //
  616.  
  617. template <class Type>
  618. class WCOrderedVectorBase : public WCVectorBase<Type> {
  619. protected:
  620.     virtual WCbool base_find( const Type &, find_type, int * ) const;
  621. public:
  622.     inline WCOrderedVectorBase( size_t length, unsigned default_grow )
  623.                 : WCVectorBase<Type>( length, default_grow ) {};
  624.  
  625.     inline virtual ~WCOrderedVectorBase() = 0;
  626.  
  627.     inline WCbool append( const Type& new_elem ){
  628.     return( insert( new_elem ) );
  629.     };
  630.  
  631.     inline WCbool insert( const Type& new_elem ){
  632.     return( base_insert_at( num_entries, new_elem ) );
  633.     };
  634.  
  635.     inline WCbool insertAt( int index, const Type& new_elem ){
  636.     return( base_insert_at( index, new_elem ) );
  637.     };
  638.  
  639.     inline WCbool prepend( const Type& new_elem ){
  640.     return( base_insert_at( 0, new_elem ) );
  641.     };
  642.  
  643. };
  644.  
  645.  
  646. template <class Type>
  647. WCOrderedVectorBase<Type>::~WCOrderedVectorBase() {};
  648.     
  649.  
  650. template <class Type>
  651. WCbool WCOrderedVectorBase<Type>::base_find( const Type &elem, find_type
  652.                 , int *st_found_index ) const {
  653.     int index = *st_found_index;
  654.     
  655.     while( index < num_entries ) {
  656.          if( base_equivalent( vector[ index ], elem ) ) {
  657.          *st_found_index = index;
  658.          return( TRUE );
  659.      }
  660.      index++;
  661.     }
  662.     return( FALSE );
  663. };
  664.  
  665.  
  666.  
  667.  
  668. //
  669. // WCSortedVectorBase     - this is the base class for WCValSortedVector and
  670. //              WCPtrSortedVector.
  671. //
  672. // This is a abstract class to prevent objects of this type being created
  673. //
  674.  
  675. template <class Type>
  676. class WCSortedVectorBase : public WCVectorBase<Type> {
  677. protected:
  678.     virtual WCbool base_find( const Type &, find_type, int * ) const;
  679.     virtual int base_less_than( const Type& elem1
  680.                       , const Type& elem2 ) const = 0;
  681. public:
  682.     inline WCSortedVectorBase( size_t length, unsigned default_grow )
  683.                 : WCVectorBase<Type>( length, default_grow ) {};
  684.  
  685.     inline virtual ~WCSortedVectorBase() = 0;
  686.  
  687.     WCbool insert( const Type& );
  688. };
  689.  
  690.  
  691. template <class Type>
  692. WCSortedVectorBase<Type>::~WCSortedVectorBase() {};
  693.     
  694.  
  695. template <class Type>
  696. WCbool WCSortedVectorBase<Type>::base_find( const Type &elem, find_type type
  697.     , int * st_found_index ) const {
  698.     // for multiple searches, check to see next element also matches
  699.     if( type == next_mult_find ) {
  700.     int index = *st_found_index;
  701.     if( ( index < num_entries )
  702.       &&( base_equivalent( vector[ index ], elem ) ) ) {
  703.          return( TRUE );
  704.     }
  705.     return( FALSE );
  706.     }
  707.  
  708.     // the binary search
  709.     int low_bound = 0;
  710.     int up_bound = num_entries - 1;
  711.     int bisector;
  712.     while( low_bound < up_bound ) {
  713.     // bisector must be calculated so that it is less than up_bound
  714.     bisector = ( up_bound - low_bound ) / 2 + low_bound;
  715.     if( base_less_than( vector[ bisector ], elem ) ) {
  716.         low_bound = bisector + 1;
  717.     } else {
  718.         up_bound = bisector;
  719.     }
  720.     }
  721.  
  722.     bisector = low_bound;
  723.     // if we found elem, the first match is at index bisector
  724.     
  725.     if( base_equivalent( elem, vector[ bisector ] ) ) {
  726.     // found match, bisector is the first match
  727.     if( type == find_for_insert ) {
  728.         while( ( bisector < num_entries )
  729.          &&( base_equivalent( vector[ bisector ], elem ) ) ) {
  730.         bisector++;
  731.         }
  732.     }
  733.     *st_found_index = bisector;
  734.     return( TRUE );
  735.     } 
  736.  
  737.     // search failed, if find for insert make sure we are *after* elem
  738.     if( type == find_for_insert ){
  739.         if( base_less_than( vector[ bisector ], elem ) ) {
  740.         bisector++;    
  741.         }
  742.     *st_found_index = bisector;
  743.     }
  744.     return( FALSE );
  745. }
  746.  
  747.  
  748. template <class Type>
  749. WCbool WCSortedVectorBase<Type>::insert( const Type& elem ) {
  750.     int index = 0;
  751.  
  752.     if( num_entries > 0 ) {
  753.           base_find( elem, find_for_insert, &index );
  754.     }
  755.     return( base_insert_at( index, elem ) );
  756. };
  757.       
  758.  
  759.  
  760.  
  761. //
  762. // WCPtrVectorBase     - this is a base class for WCPtrOrderedVector and
  763. //              WCPtrSortedVector.
  764. //
  765. // This is a abstract class to prevent objects of this type being created
  766. //
  767. // Implementation note:
  768. // All WCPtrOrdered vectors and WCPtrSorted vectors inherit from WCVectorBase
  769. // templated over <void *>.  This saves most of the vector code being
  770. // generated for pointer vectors templated over different types, speeding
  771. // up compile time, and reducing code size.
  772. //
  773.  
  774. template <class Type, class BaseClass>
  775. class WCPtrVectorBase : public BaseClass {
  776. protected:
  777.     typedef Type * __Type_Ptr;
  778.     typedef void * __Stored_Ptr;
  779.  
  780.     inline Type *base_ptr_remove_at( int index ) {
  781.     Type *ret_ptr = (Type *)vector[ index ];
  782.     base_remove_at( index );
  783.     return( ret_ptr );
  784.     }
  785.  
  786.     virtual void base_init_upto( int );
  787.  
  788. public:
  789.     inline WCPtrVectorBase( size_t length, unsigned default_grow )
  790.                 : BaseClass( length, default_grow ) {};
  791.  
  792.     inline virtual ~WCPtrVectorBase() = 0;
  793.  
  794.     void clearAndDestroy();
  795.  
  796.     inline WCbool contains( const Type * elem ) const {
  797.     return( BaseClass::contains( (const __Type_Ptr)elem ) );
  798.     };
  799.  
  800.     Type *find( const Type * elem ) const;
  801.  
  802.     inline Type *first() const {
  803.     return( (Type *)BaseClass::first() );
  804.     }
  805.  
  806.     inline int index( const Type * elem ) const {
  807.     return( BaseClass::index( (const __Type_Ptr)elem ) );
  808.     };
  809.  
  810.     inline Type *last() const {
  811.     return( (Type *)BaseClass::last() );
  812.     }
  813.  
  814.     int occurrencesOf( const Type * elem ) const {
  815.     return( BaseClass::occurrencesOf( (const __Type_Ptr)elem ) );
  816.     };
  817.  
  818.     Type *remove( const Type * elem );
  819.  
  820.     unsigned removeAll( const Type * elem ) {
  821.     return( BaseClass::removeAll( (const __Type_Ptr)elem ) );
  822.     };
  823.  
  824.     Type *removeAt( int index );
  825.  
  826.     inline Type *removeFirst() {
  827.     return( removeAt( 0 ) );
  828.     };
  829.  
  830.     inline Type *removeLast() {
  831.     return( removeAt( num_entries - 1 ) );
  832.     };
  833.  
  834.     inline Type * &operator[] ( int index ) {
  835.     return( (Type * &)BaseClass::operator[]( index ) );
  836.     };
  837.  
  838.     inline Type * const & operator[] ( int index ) const {
  839.     return( (Type * const &)BaseClass::operator[]( index ) );
  840.     };
  841. };
  842.  
  843.  
  844. template<class Type, class BaseClass>
  845. void WCPtrVectorBase<Type, BaseClass>::base_init_upto( int index ) {
  846.     if( index >= num_init ){
  847.     // intialize the vector by NULLing out unitialized elements
  848.     memset( &vector[ num_init ], 0
  849.           , ( index + 1 - num_init ) * sizeof( void * ) );
  850.     num_init = index + 1;
  851.     }
  852. }
  853.  
  854.  
  855. template <class Type, class BaseClass>
  856. WCPtrVectorBase<Type, BaseClass>::~WCPtrVectorBase() {};
  857.     
  858.  
  859. template<class Type, class BaseClass>
  860. void WCPtrVectorBase<Type, BaseClass>::clearAndDestroy() {
  861.     for( unsigned i = 0; i < num_entries; i++ ) {
  862.     delete( (Type *)vector[ i ] );
  863.     }
  864.     clear();
  865. };
  866.  
  867.  
  868. template<class Type, class BaseClass>
  869. Type *WCPtrVectorBase<Type, BaseClass>::find( const Type * elem ) const {
  870.     int index = 0;
  871.     if( ( num_entries > 0 )
  872.       &&( base_find( (const __Type_Ptr)elem, find_any, &index ) ) ) {
  873.     return( (Type *)vector[ index ] );
  874.     } else {
  875.     return( 0 );
  876.     }
  877. };
  878.  
  879.  
  880. template<class Type, class BaseClass>
  881. Type *WCPtrVectorBase<Type, BaseClass>::remove( const Type *elem ) {
  882.     int index = 0;
  883.  
  884.     if( ( num_entries > 0 )
  885.       &&( base_find( (const __Type_Ptr)elem, find_first, &index ) ) ) {
  886.     return( base_ptr_remove_at( index ) );
  887.     } else {
  888.     return( 0 );
  889.     }
  890. };
  891.  
  892.  
  893. template<class Type, class BaseClass>
  894. Type *WCPtrVectorBase<Type, BaseClass>::removeAt( int index ) {
  895.     if( num_entries == 0 ) {
  896.     base_throw_empty_container();
  897.     return( 0 );
  898.     } else {
  899.     index = base_index_check( index );
  900.     return( base_ptr_remove_at( index ) );
  901.     }
  902. };
  903.  
  904.  
  905. #if defined( _WNEW_OPERATOR )
  906. #  define new _WNEW_OPERATOR
  907. #endif
  908. #if defined( _WDELETE_OPERATOR )
  909. #  define delete _WDELETE_OPERATOR
  910. #endif
  911.  
  912. #endif
  913.