class MULTIMAP{K,E}


Ancestors
H_MULTIMAP{_,_} $MULTIMAP{_,_} $RO_MULTIMAP{_,_} $CONTAINER{_}
$ELT{_} $ELT MULTIMAP_INCL{_,_} RO_MULTIMAP_INCL{_,_}
COMPARE{_}



Public


Readable Attributes
attr n_inds: INT; .. Included as n_inds
**** Returns the number of elements (resp. indices) in the table.
attr total_size: INT; .. Included as total_size

Writable Attributes
attr n_inds: INT; .. Included as n_inds
**** Returns the number of elements (resp. indices) in the table.

Features
aset(k:K,e:E) .. Included as aset
copy: SAME .. Included as copy
create: SAME .. Included as create
delete(k:K) .. Included as delete
**** Delete all elements associated with element "k"
delete(k:K,e:E) .. Included as delete
**** 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 .. Included as has
has_elt(e: E): BOOL .. Included as has_elt
has_ind(k:K): BOOL .. Included as has_ind
**** 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 .. Included as n_targets
size: INT .. Included as size
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

Iters
elt!: E .. Included as elt!
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} .. Included as pair!
target!(once k:K): E .. Included as target!
**** Return the values associated with "k"
target!: E .. Included as target!


Private

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; .. Included as total_size
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.)

The Sather Home Page