| class H_MULTIMAP{K,E} < $MULTIMAP{K,E} |
|---|
| **** | Multimap based on the DYNAMIC_DATABUCKET_TABLE |
| $MULTIMAP{_,_} | $RO_MULTIMAP{_,_} | $CONTAINER{_} | $ELT{_} | $ELT | MULTIMAP_INCL{_,_} | RO_MULTIMAP_INCL{_,_} | COMPARE{_} |
| MULTIMAP{_,_} |
| attr n_inds: INT; .. Included as n_inds |
|---|
| **** | Returns the number of elements (resp. indices) in the table. |
| attr total_size: INT; |
|---|
| attr n_inds: INT; .. Included as n_inds |
|---|
| **** | Returns the number of elements (resp. indices) in the table. |
| aset(k:K,e:E) |
|---|
| copy: SAME |
|---|
| create: SAME .. Included as create |
|---|
| delete(k:K) |
|---|
| **** | Delete all elements associated with element "k" |
| delete(k:K,e:E) |
|---|
| **** | Delete a single occurence of the key value pair(k,e) |
| elt_eq(e1,e2:ETP):BOOL .. Included as elt_eq |
|---|
| **** | The "less than" relation used in the sorting routines. Compares the object "id" by default. May be redefined in descendants. |
| elt_hash(e:ETP):INT .. Included as elt_hash |
|---|
| **** | A hash value associated with an element. Must have the property that if "elt_eq(e1,e2)" then "elt_hash(e1)=elt_hash(e2)". Can be defined to always return 0, but many routines will then become quadratic. Uses object "id" by default. May be redefined in descendants. |
| elt_if(test:ROUT{E}:BOOL,out res:E):BOOL .. Included as elt_if |
|---|
| **** | Return the first element that satisfies "test" in "res" Return true if a element was found, false otherwise |
| elt_lt(e1,e2:ETP):BOOL .. Included as elt_lt |
|---|
| **** | The "less than" relation used in the sorting routines. Compares the object "id" by default. May be redefined in descendants. |
| elt_nil: ETP .. Included as elt_nil |
|---|
| **** | Return the nil value. If the element is under $NIL then return e.nil. Otherwise, return void
_ |
| equals(b: $RO_MULTIMAP{K,E}): BOOL .. Included as equals |
|---|
| **** | Returns true if all of "e"'s elements are equal to self's elts Ordering is an issue. Should be redefined to be more precise for particular descendants |
| has(e: E): BOOL .. Included as has |
|---|
| **** | Return true if this multimap has the element "e" |
| has(k:K,e:E): BOOL |
|---|
| has_elt(e: E): BOOL .. Included as has_elt |
|---|
| has_ind(k:K): BOOL |
|---|
| **** | Return true if the multi-map (dictionary) has the index "k" |
| ind_if(test:ROUT{E}:BOOL):K .. Included as ind_if |
|---|
| **** | Return the index of the leftmost element that satisfies `test', or void if there is none. Must be changed to use an out argument |
| inds: ARRAY{K} .. Included as inds |
|---|
| **** | Return an index array which is the same size as self and is set to the values of the indices |
| is_elt_nil(e:ETP):BOOL .. Included as is_elt_nil |
|---|
| n_targets(k:K): INT |
|---|
| size: INT |
|---|
| str: STR .. Included as str |
|---|
| **** | Prints out a string version of the array of the components that are under $STR, and their associated indices |
| str_of_elts: STR .. Included as str_of_elts |
|---|
| **** | Prints out a string version of the array of the components that are under $STR, and their associated indices |
| targets(k: K): BAG{E} .. Included as targets |
|---|
| elt!: E |
|---|
| filter!(once f:ROUT{E}:BOOL): E .. Included as filter! |
|---|
| **** | Yield all elements that satisfy the boolean predicate "f" |
| filter_not!(once f:ROUT{E}:BOOL): E .. Included as filter_not! |
|---|
| **** | Yield all elements that do not satisfy the boolean predicate "f" |
| map_key!: K .. Included as ind! |
|---|
| pair!: TUP{K,E} |
|---|
| target!(once k:K): E |
|---|
| **** | Return the values associated with "k" |
| target!: E .. Included as target! |
|---|
| attr asize: INT; .. Included as asize |
|---|
| **** | The size of the fraction of the store which is currently in use. Array access beyond this bound is illegal. |
| attr asize: INT; .. Included as asize |
|---|
| **** | The size of the fraction of the store which is currently in use. Array access beyond this bound is illegal. |
| attr bound: INT; .. Included as bound |
|---|
| **** | Upper bound for split_pos. Is always initial_size * 2.pow(doubles) |
| attr bound: INT; .. Included as bound |
|---|
| **** | Upper bound for split_pos. Is always initial_size * 2.pow(doubles) |
| bucket(i:INT): BUCKET .. Included as bucket |
|---|
| create_sized(initial_size:INT): SAME .. Included as create_sized |
|---|
| **** | Creating a table with another minimal size. This might be useful to avoid shrinking of large table which might get very empty. |
| data_nil: E .. Included as data_nil |
|---|
| dbg: STR .. Included as dbg |
|---|
| **** | Returns an interal string representation of the hashtable. For debugging only. |
| attr doubles: INT; .. Included as doubles |
|---|
| **** | Number of times the initial table size has been doubled. |
| attr doubles: INT; .. Included as doubles |
|---|
| **** | Number of times the initial table size has been doubled. |
| elt_eq(e1,e2:ETP):BOOL .. Included as elt_key_eq |
|---|
| **** | The "less than" relation used in the sorting routines. Compares the object "id" by default. May be redefined in descendants. |
| elt_hash(e:ETP):INT .. Included as elt_key_hash |
|---|
| **** | A hash value associated with an element. Must have the property that if "elt_eq(e1,e2)" then "elt_hash(e1)=elt_hash(e2)". Can be defined to always return 0, but many routines will then become quadratic. Uses object "id" by default. May be redefined in descendants. |
| elt_nil: ETP .. Included as elt_key_nil |
|---|
| **** | Return the nil value. If the element is under $NIL then return e.nil. Otherwise, return void
_ |
| elt_str(e: E): STR .. Included as elt_str |
|---|
| grow .. Included as grow |
|---|
| **** | Increases the size of the array by one. The functions changing the size of the bucket table: They are split into two parts. 1.) Splitting the next bucket into two. (update_*) 2.) Resizing the storage area. (shrink/grow) |
| hash(e:E): INT .. Included as hash |
|---|
| **** | Returns the bucket to store e. This number will be generated from the hash-value and be normailzed through the actual size of the set. |
| ind_str(i: K): STR .. Included as ind_str |
|---|
| shared lower_fill_ratio: FLT := 0.800; .. Included as lower_fill_ratio |
|---|
| shared lower_fill_ratio: FLT := 0.800; .. Included as lower_fill_ratio |
|---|
| map_aget(k:K): E .. Included as map_aget |
|---|
| **** | Returns the element equal to 'e' from the set. Returns void or T::nil if there is no such element. Self may not be void. |
| map_aset(k:K,e:E) .. Included as map_aset |
|---|
| **** | Over-ride data if 'k' exists. Otherwise grow the bucket chain associated with hash(k) |
| map_copy: SAME .. Included as map_copy |
|---|
| **** | Returns a copy of self with all properties set like self. |
| map_delete(k:K): E .. Included as map_delete |
|---|
| **** | Removes an element from the set. Does nothing if there is no such element. |
| map_elt!: E .. Included as map_elt! |
|---|
| map_has_ind(k:K): BOOL .. Included as map_has_ind |
|---|
| map_pair!: TUP{K,E} .. Included as map_pair! |
|---|
| attr minsize: INT; .. Included as minsize |
|---|
| **** | Lower bound for the store size. |
| attr minsize: INT; .. Included as minsize |
|---|
| **** | Lower bound for the store size. |
| set_bucket(i:INT,l:BUCKET) .. Included as set_bucket |
|---|
| shrink .. Included as shrink |
|---|
| **** | Decreases the size of the array by one. Resizes the storage area, if neccessary. |
| attr split_pos: INT; .. Included as split_pos |
|---|
| **** | Position of the next bucket to split. |
| attr split_pos: INT; .. Included as split_pos |
|---|
| **** | Position of the next bucket to split. |
| attr store: AREF{BUCKET}; .. Included as store |
|---|
| **** | Here is the data being stored. |
| attr store: AREF{BUCKET}; .. Included as store |
|---|
| **** | Here is the data being stored. |
| attr total_size: INT; |
|---|
| update_delete .. Included as update_delete |
|---|
| **** | Checks the actual fill ratio of the set. Removes a bucket from the hash table if the ratio is low enough. |
| update_insert .. Included as update_insert |
|---|
| **** | Checks the actual fill ratio of the set. Adds a bucket to the hash table if the ratio is high enough. The functions changing the size of the bucket table are split into two parts. 1.) Splitting the next bucket into two. (update_*) 2.) Resizing the storage area. (shrink/grow) |
| shared upper_fill_ratio: FLT := 1.000; .. Included as upper_fill_ratio |
|---|
| **** | For fast access one needs a low ratio between number of elements in the and number of cells. For efficient memory usage one needs a high ratio. The ratio should always be between these two bounds (unless the table is really small; where the ratio can get even lower.) |
| shared upper_fill_ratio: FLT := 1.000; .. Included as upper_fill_ratio |
|---|
| **** | For fast access one needs a low ratio between number of elements in the and number of cells. For efficient memory usage one needs a high ratio. The ratio should always be between these two bounds (unless the table is really small; where the ratio can get even lower.) |