home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 1997 May / Pcwk0597.iso / sybase / starbuck / h.z / WCSKIP.H < prev    next >
C/C++ Source or Header  |  1996-07-24  |  17KB  |  517 lines
  1. //
  2. //  wcskip.h    Definitions and implementation for the WATCOM Container Skip
  3. //              List class
  4. //
  5. //  Copyright by WATCOM International Corp. 1988-1996.  All rights reserved.
  6. //
  7. #ifndef _WCSKIP_H_INCLUDED
  8. #define _WCSKIP_H_INCLUDED
  9.  
  10. #ifndef __cplusplus
  11. #error wcskip.h is for use with C++
  12. #endif
  13.  
  14. //
  15. // Skip Lists are a probabilistic alternative to balanced trees, as
  16. // described in the June 1990 issue of CACM and were invented by
  17. // William Pugh in 1987.
  18. //
  19.  
  20.  
  21. #ifndef _WCDEFS_H_INCLUDED
  22.  #include <wcdefs.h>
  23. #endif
  24. #ifndef _WCEXCEPT_H_INCLUDED
  25.  #include <wcexcept.h>
  26. #endif
  27. #ifndef _WCSBASE_H_INCLUDED
  28.  #include <wcsbase.h>
  29. #endif
  30.  
  31.  
  32. //
  33. // WCValSkipList - the skip list value class which allows duplicates
  34. //
  35.  
  36. template<class Type>
  37. class WCValSkipList : public WCSkipListDuplicatesBase<Type> {
  38. private:
  39.     // define equivalence and less than for the base classes
  40.     // second parameters are really typed (Type *)
  41.     virtual int base_equiv( node_ptr elem1, TTypePtr elem2 ) const {
  42.         return( (const Type)base_whole_node( elem1 )->data
  43.                 == *(const Type *)elem2 );
  44.     };
  45.  
  46.     virtual int base_less( node_ptr lhs, TTypePtr rhs ) const {
  47.         return( (const Type)base_whole_node( lhs )->data
  48.                 < *(const Type *)rhs );
  49.     };
  50.  
  51. public:
  52.     inline WCValSkipList( unsigned prob = WCSKIPLIST_PROB_QUARTER
  53.                         , unsigned max_ptrs = WCDEFAULT_SKIPLIST_MAX_PTRS
  54.                         ) : WCSkipListDuplicatesBase( prob, max_ptrs ) {};
  55.  
  56.     inline WCValSkipList( unsigned prob, unsigned max_ptrs
  57.                         , void * (*user_alloc)( size_t )
  58.                         , void (*user_dealloc)( void *, size_t )
  59.                         ) : WCSkipListDuplicatesBase( prob, max_ptrs
  60.                                         , user_alloc, user_dealloc ) {};
  61.  
  62.     inline WCValSkipList( const WCValSkipList &orig )
  63.                  : WCSkipListDuplicatesBase( orig.probability
  64.                                            , orig.max_ptrs_in_node ) {
  65.         base_construct( &orig );
  66.     };
  67.  
  68.     inline virtual ~WCValSkipList() {};
  69.  
  70.     inline WCbool find( const Type &search, Type &return_val ) const {
  71.         return( base_val_find( search, return_val ) );
  72.     }
  73.  
  74.     inline WCValSkipList &operator=( const WCValSkipList &orig ) {
  75.         base_assign( &orig );
  76.         return( *this );
  77.     };
  78. };
  79.  
  80.  
  81.  
  82.  
  83. //
  84. // WCPtrSkipList - the skip list pointer class which allows duplicates
  85. //
  86.  
  87. template<class Type>
  88. class WCPtrSkipList
  89.         : public WCPtrSkipListBase<Type,WCSkipListDuplicatesBase<void *> > {
  90. public:
  91.     inline WCPtrSkipList( unsigned prob = WCSKIPLIST_PROB_QUARTER
  92.                         , unsigned max_ptrs = WCDEFAULT_SKIPLIST_MAX_PTRS
  93.                         ) : WCPtrSkipListBase( prob, max_ptrs ) {};
  94.  
  95.     inline WCPtrSkipList( unsigned prob, unsigned max_ptrs
  96.                         , void * (*user_alloc)( size_t )
  97.                         , void (*user_dealloc)( void *, size_t )
  98.                         ) : WCPtrSkipListBase( prob, max_ptrs
  99.                                              , user_alloc, user_dealloc ) {};
  100.  
  101.     inline WCPtrSkipList( const WCPtrSkipList &orig )
  102.                          : WCPtrSkipListBase( orig.probability
  103.                                             , orig.max_ptrs_in_node ) {
  104.         base_construct( &orig );
  105.     };
  106.  
  107.     inline virtual ~WCPtrSkipList() {};
  108.     
  109.     inline unsigned occurrencesOf( const Type *elem ) const {
  110.         return( WCSkipListDuplicatesBase
  111.                         ::occurrencesOf( (const TypePtr) elem ) );
  112.     };
  113.  
  114.     inline unsigned removeAll( const Type *elem ) {
  115.         return( WCSkipListDuplicatesBase::removeAll( (const TypePtr) elem ) );
  116.     };
  117.  
  118.     inline WCPtrSkipList &operator=( const WCPtrSkipList &orig ) {
  119.         base_assign( &orig );
  120.         return( *this );
  121.     };
  122. };
  123.     
  124.  
  125.  
  126.  
  127. //
  128. // WCValSkipListSet - the skip list value class which does not allow duplicates
  129. //
  130.  
  131. template<class Type>
  132. class WCValSkipListSet : public WCSkipListBase<Type> {
  133. private:
  134.     // defines equivalence and less than for the base class
  135.     // second parameters are really typed (Type *)
  136.     virtual int base_equiv( node_ptr elem1, TTypePtr elem2 ) const {
  137.         return( (const Type)base_whole_node( elem1 )->data
  138.                 == *(const Type *)elem2 );
  139.     };
  140.     
  141.     virtual int base_less( node_ptr lhs, TTypePtr rhs ) const {
  142.         return( (const Type)base_whole_node( lhs )->data
  143.                 < *(const Type *)rhs );
  144.     };
  145.  
  146. public:
  147.     inline WCValSkipListSet( unsigned prob = WCSKIPLIST_PROB_QUARTER
  148.                            , unsigned max_ptrs = WCDEFAULT_SKIPLIST_MAX_PTRS
  149.                            ) : WCSkipListBase( prob, max_ptrs ) {};
  150.  
  151.     inline WCValSkipListSet( unsigned prob, unsigned max_ptrs
  152.                            , void * (*user_alloc)( size_t )
  153.                            , void (*user_dealloc)( void *, size_t )
  154.                            ) : WCSkipListBase( prob, max_ptrs
  155.                                         , user_alloc, user_dealloc ) {};
  156.  
  157.     inline WCValSkipListSet( const WCValSkipListSet &orig )
  158.                          : WCSkipListBase( orig.probability
  159.                                          , orig.max_ptrs_in_node ) {
  160.         base_construct( &orig );
  161.     };
  162.  
  163.     inline virtual ~WCValSkipListSet() {};
  164.  
  165.     inline WCbool find( const Type &search, Type &return_val ) const {
  166.         return( base_val_find( search, return_val ) );
  167.     }
  168.  
  169.     inline WCValSkipListSet &operator=( const WCValSkipListSet &orig ) {
  170.         base_assign( &orig );
  171.         return( *this );
  172.     };
  173. };
  174.  
  175.  
  176.  
  177.  
  178. //
  179. // WCPtrSkipListSet - the skip list pointer class which does not
  180. // allow duplicates
  181. //
  182.  
  183. template<class Type>
  184. class WCPtrSkipListSet
  185.         : public WCPtrSkipListBase<Type,WCSkipListBase<void *> > {
  186. public:
  187.     inline WCPtrSkipListSet( unsigned prob = WCSKIPLIST_PROB_QUARTER
  188.                            , unsigned max_ptrs = WCDEFAULT_SKIPLIST_MAX_PTRS
  189.                            ) : WCPtrSkipListBase( prob, max_ptrs ) {};
  190.  
  191.     inline WCPtrSkipListSet( unsigned prob, unsigned max_ptrs
  192.                            , void * (*user_alloc)( size_t )
  193.                            , void (*user_dealloc)( void *, size_t )
  194.                            ) : WCPtrSkipListBase( prob, max_ptrs
  195.                                              , user_alloc, user_dealloc ) {};
  196.  
  197.     inline WCPtrSkipListSet( const WCPtrSkipListSet &orig )
  198.                          : WCPtrSkipListBase( orig.probability
  199.                                             , orig.max_ptrs_in_node ) {
  200.         base_construct( &orig );
  201.     };
  202.  
  203.     inline virtual ~WCPtrSkipListSet() {};
  204.     
  205.     inline WCPtrSkipListSet &operator=( const WCPtrSkipListSet &orig ) {
  206.         base_assign( &orig );
  207.         return( *this );
  208.     };
  209. };
  210.  
  211.  
  212.  
  213.  
  214. //
  215. // WCValSkipListDict - the skip list value dictionary class.  Key-Value
  216. // pairs are stored in a skip list, and all lookups are base on Key
  217. //
  218.  
  219. template<class Key, class Value>
  220. class WCValSkipListDict
  221.         : public WCSkipListBase<WCSkipListDictKeyVal<Key, Value> > {
  222. protected:    
  223.     typedef WCSkipListDictKeyVal<Key, Value> KeyVal;
  224.     // for const member functions which modify temp_key_val, but not the
  225.     // skip list
  226.     typedef WCValSkipListDict *const NonConstThis;
  227.  
  228.     // temp_key_val is used in finds, removes, etc., where only the key is
  229.     // given. it is also used by the operator[] to insert.  The value must
  230.     // remain default initialized
  231.     KeyVal temp_key_val;
  232.  
  233.     // second parameters are really typed (KeyVal *)
  234.     virtual int base_equiv( node_ptr elem1, TTypePtr elem2 ) const {
  235.         return( (const Key)base_whole_node( elem1 )->data.key
  236.                 == ( (const KeyVal *)elem2 )->key );
  237.     };
  238.     
  239.     virtual int base_less( node_ptr lhs, TTypePtr rhs ) const {
  240.         return( (const Key)base_whole_node( lhs )->data.key
  241.                 < ( (const KeyVal *)rhs )->key );
  242.     };
  243.  
  244. public:
  245.     inline WCValSkipListDict( unsigned prob = WCSKIPLIST_PROB_QUARTER
  246.                             , unsigned max_ptrs = WCDEFAULT_SKIPLIST_MAX_PTRS
  247.                             ) : WCSkipListBase( prob, max_ptrs ) {};
  248.  
  249.     inline WCValSkipListDict( unsigned prob, unsigned max_ptrs
  250.                             , void * (*user_alloc)( size_t )
  251.                             , void (*user_dealloc)( void *, size_t )
  252.                             ) : WCSkipListBase( prob, max_ptrs
  253.                                               , user_alloc, user_dealloc ) {};
  254.  
  255.     inline WCValSkipListDict( const WCValSkipListDict &orig )
  256.                  : WCSkipListBase( orig.probability, orig.max_ptrs_in_node ) {
  257.         base_construct( &orig );
  258.     };
  259.  
  260.     inline virtual ~WCValSkipListDict() {};
  261.  
  262.     inline WCbool contains( const Key &key ) const {
  263.         NonConstThis This = (NonConstThis)this;
  264.         This->temp_key_val.key = key;
  265.         return( base_find( temp_key_val ) != 0 );
  266.     };
  267.  
  268.     WCbool find( const Key &search, Value &ret_value ) const;
  269.  
  270.     WCbool findKeyAndValue( const Key &search, Key &ret_key
  271.                           , Value &ret_value ) const;
  272.  
  273.     void forAll( void(*)( Key, Value, void * ), void * ) const;
  274.  
  275.     inline WCbool insert( const Key &key, const Value &value ) {
  276.         KeyVal temp( key, value );
  277.         return( WCSkipListBase::insert( temp ) );
  278.     };
  279.  
  280.     inline WCbool remove( const Key &key ) {
  281.         temp_key_val.key = key;
  282.         return( WCSkipListBase::remove( temp_key_val ) );
  283.     };
  284.  
  285.     inline WCValSkipListDict &operator=( const WCValSkipListDict &orig ) {
  286.         base_assign( &orig );
  287.         return( *this );
  288.     };
  289.  
  290.     Value &operator[]( const Key &key );
  291.  
  292.     const Value &operator[]( const Key &key ) const;
  293. };
  294.  
  295.  
  296. template<class Key, class Value>
  297. WCbool WCValSkipListDict<Key, Value>::find( const Key &search
  298.                                          , Value &ret_value ) const {
  299.     NonConstThis This = (NonConstThis)this;
  300.     This->temp_key_val.key = search;
  301.     node_ptr node = base_find( temp_key_val );
  302.     if( node != 0 ) {
  303.         ret_value = base_whole_node( node )->data.value;
  304.         return( TRUE );
  305.     } else {
  306.         return( FALSE );
  307.     }
  308. };
  309.  
  310.  
  311. template<class Key, class Value>
  312. WCbool WCValSkipListDict<Key, Value>::findKeyAndValue( const Key &search
  313.                                 , Key &ret_key, Value &ret_value ) const {
  314.     NonConstThis This = (NonConstThis)this;
  315.     This->temp_key_val.key = search;
  316.     node_ptr node = base_find( temp_key_val );
  317.     if( node != 0 ) {
  318.         ret_key = base_whole_node( node )->data.key;
  319.         ret_value = base_whole_node( node )->data.value;
  320.         return( TRUE );
  321.     } else {
  322.         return( FALSE );
  323.     }
  324. };
  325.  
  326.  
  327. template<class Key, class Value>
  328. void WCValSkipListDict<Key, Value>
  329.                 ::forAll( register void(*user_fn)( Key, Value, void * )
  330.                         , void * data) const {
  331.     register node_ptr curr;
  332.  
  333.     curr = header->forward[ 0 ];
  334.     while ( curr != 0 ) {
  335.         user_fn( base_whole_node( curr )->data.key
  336.                , base_whole_node( curr )->data.value, data );
  337.         curr = curr->forward[ 0 ];
  338.     }
  339. };
  340.  
  341.  
  342. template<class Key, class Value>
  343. Value &WCValSkipListDict<Key, Value>::operator[]( const Key &key ) {
  344.     NonConstThis This = (NonConstThis)this;
  345.     This->temp_key_val.key = key;
  346.     node_ptr node = base_find( temp_key_val );
  347.     if( node == 0 ) {
  348.         node = base_insert( temp_key_val );
  349.         if( !node ) {
  350.             // insert failed because allocation failed and out_of_memory
  351.             // exception disabled
  352.             return( *(Value *)0 );
  353.         }
  354.     }
  355.     return( base_whole_node( node )->data.value );
  356. };
  357.  
  358.  
  359. template<class Key, class Value>
  360. const Value &WCValSkipListDict<Key, Value>
  361.                 ::operator[]( const Key &key ) const {
  362.     NonConstThis This = (NonConstThis)this;
  363.     This->temp_key_val.key = key;
  364.     node_ptr node = base_find( temp_key_val );
  365.     if( node != 0 ) {
  366.         return( base_whole_node( node )->data.value );
  367.     } else {
  368.         base_throw_index_range();
  369.         // find failed, index_range exception off, but must return reference
  370.         return( *(Value *)0 );
  371.     }
  372. };
  373.  
  374.  
  375.  
  376.  
  377. //
  378. // WCPtrSkipListDict - the skip list value dictionary class.  Key-Value
  379. // pairs are stored in a skip list, and all lookups are base on Key
  380. //
  381.  
  382. template<class Key, class Value>
  383. class WCPtrSkipListDict
  384.         : public WCValSkipListDict<void *, void *> {
  385. protected:    
  386.     // for const member functions which modify temp_key_val, but not the
  387.     // skip list
  388.     typedef WCPtrSkipListDict *const NonConstThis;
  389.     // the pointer stored by WCValSkipListDict
  390.     typedef void *Stored_Ptr;  
  391.     // the user function passed to the forAll member function is passed
  392.     // to WCValSkipListDict::forAll using this cast type
  393.     typedef void (*_ForAllFnCast)( void *, void *, void * );
  394.  
  395.     // defines equivalence and less than based on the keys pointed to
  396.     // second parameters are really typed (KeyVal *)
  397.     virtual int base_equiv( node_ptr elem1, TTypePtr elem2 ) const {
  398.         return( *(const Key *)base_whole_node( elem1 )->data.key
  399.                 == *(const Key *)( (const KeyVal *)elem2 )->key );
  400.     };
  401.     
  402.     virtual int base_less( node_ptr lhs, TTypePtr rhs ) const {
  403.         return( *(const Key *)base_whole_node( lhs )->data.key
  404.                 < *(const Key *)( (const KeyVal *)rhs )->key );
  405.     };
  406.  
  407.     // for the clearAndDestroy member function
  408.     static void base_destroy( Key *key, Value *value, void * ) {
  409.         delete( key );
  410.         delete( value );
  411.     };
  412.  
  413. public:
  414.     inline WCPtrSkipListDict( unsigned prob = WCSKIPLIST_PROB_QUARTER
  415.                             , unsigned max_ptrs = WCDEFAULT_SKIPLIST_MAX_PTRS
  416.                             ) : WCValSkipListDict( prob, max_ptrs ) {};
  417.  
  418.     inline WCPtrSkipListDict( unsigned prob, unsigned max_ptrs
  419.                             , void * (*user_alloc)( size_t )
  420.                             , void (*user_dealloc)( void *, size_t )
  421.                             ) : WCValSkipListDict( prob, max_ptrs
  422.                                               , user_alloc, user_dealloc ) {};
  423.  
  424.     inline WCPtrSkipListDict( const WCPtrSkipListDict &orig )
  425.              : WCValSkipListDict( orig.probability, orig.max_ptrs_in_node ) {
  426.         base_construct( &orig );
  427.     };
  428.  
  429.     inline virtual ~WCPtrSkipListDict() {};
  430.  
  431.     inline void clearAndDestroy() {
  432.         forAll( base_destroy, 0 );
  433.         clear();
  434.     };
  435.  
  436.     inline WCbool contains( const Key *key ) const {
  437.         return( WCValSkipListDict::contains( (const Stored_Ptr)key ) );
  438.     };
  439.  
  440.     Value *find( const Key *search ) const;
  441.  
  442.     Value *findKeyAndValue( const Key *search, Key * &ret_key ) const;
  443.  
  444.     void forAll( void(*fn)( Key *, Value *, void * ), void * data ) const {
  445.         WCValSkipListDict::forAll( (_ForAllFnCast)fn, data );
  446.     };
  447.  
  448.     inline WCbool insert( Key *key, Value *value ) {
  449.         return( WCValSkipListDict::insert( (const Stored_Ptr)key
  450.                                          , (const Stored_Ptr)value ) );
  451.     };
  452.  
  453.     Value* remove( const Key *key );
  454.  
  455.     inline WCPtrSkipListDict &operator=( const WCPtrSkipListDict &orig ) {
  456.         base_assign( &orig );
  457.         return( *this );
  458.     };
  459.  
  460.     inline Value * &operator[]( const Key *key ) {
  461.         return( (Value * &)WCValSkipListDict
  462.                                 ::operator[]( (const Stored_Ptr)key ) );
  463.     };
  464.  
  465.     inline Value * const &operator[]( const Key *key ) const {
  466.         return( (Value * const &)WCValSkipListDict
  467.                                 ::operator[]( (const Stored_Ptr)key ) );
  468.     };
  469. };
  470.  
  471.  
  472. template<class Key, class Value>
  473. Value *WCPtrSkipListDict<Key, Value>::find( const Key *search ) const {
  474.     NonConstThis This = (NonConstThis)this;
  475.     This->temp_key_val.key = (Stored_Ptr)search;
  476.     node_ptr node = base_find( temp_key_val );
  477.     if( node != 0 ) {
  478.         return( (Value *)base_whole_node( node )->data.value );
  479.     } else {
  480.         return( 0 );
  481.     }
  482. };
  483.  
  484.  
  485. template<class Key, class Value>
  486. Value *WCPtrSkipListDict<Key, Value>::findKeyAndValue( const Key *search
  487.                                 , Key * &ret_key ) const {
  488.     NonConstThis This = (NonConstThis)this;
  489.     This->temp_key_val.key = (Stored_Ptr)search;
  490.     node_ptr node = base_find( temp_key_val );
  491.     if( node != 0 ) {
  492.         ret_key = (Key *)base_whole_node( node )->data.key;
  493.         return( (Value *)base_whole_node( node )->data.value );
  494.     } else {
  495.         return( 0 );
  496.     }
  497. };
  498.  
  499.  
  500. template<class Key, class Value>
  501. Value *WCPtrSkipListDict<Key, Value>::remove( const Key *elem ) {
  502.     int num_ptrs_in_node;
  503.  
  504.     temp_key_val.key = (Stored_Ptr)elem;
  505.     node_ptr node = base_remove_but_not_delete( temp_key_val
  506.                                          , num_ptrs_in_node );
  507.     if( node ) {
  508.         Value *ret_ptr = (Value *)base_whole_node( node )->data.value;
  509.         base_delete_node( node, num_ptrs_in_node );
  510.         return( ret_ptr );
  511.     } else {
  512.         return( 0 );
  513.     }
  514. }
  515.  
  516. #endif
  517.