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