+
Point of view
All features
class WORDS
Summary
An hashed set of words, usually read from a file
Direct parents
Inherit list: HASHED_SET
Class invariant
• capacity > 0
• capacity >= count
• cache_user.in_range(-1, count)
• cache_user > 0 implies cache_node /= Void
• cache_user > 0 implies cache_buckets.in_range(0, capacity - 1)
Overview
Creation features
Features
{ANY}
{}
{ANY}
{SET}
• buckets: NATIVE_ARRAY[HASHED_SET_NODE[E_]]
The buckets storage area is the primary hash table of capacity elements.
Internal cache handling:
{SET}
{}
{ANY}
{ANY}
Add new item e to the set.
Same job as add, but uses basic = for comparison.
• remove (e: E_)
Remove item e from the set: the mathematical definition of removing from a set is followed.
• fast_remove (e: E_)
Same job as remove, but uses basic = for comparison.
• clear_count
Empty the current set (is_empty is True after that call).
• clear_count_and_capacity
Empty the current set (is_empty is True after that call).
• has (e: E_): BOOLEAN
Is element e in the set?
• fast_has (e: E_): BOOLEAN
Is element e actually stored in the set?
• reference_at (e: E_): E_
Non Void when e is in the set.
• item (index: INTEGER_32): E_
Item at the corresponding index i.
• intersection (other: WORDS)
Make the intersection of the Current set with other.
• copy (other: WORDS)
Copy 'other' into the current set
• from_collection (model: COLLECTION[E_])
Implement manifest generic creation:
{}
{}
Counting:
{ANY}
To provide iterating facilities:
{ANY}
Mathematical operations:
{ANY}
• union (other: WORDS)
Make the union of the Current set with other.
• fast_union (other: WORDS)
Make the union of the Current set with other.
• infix "+" (other: WORDS): WORDS
Return the union of the Current set with other.
• fast_intersection (other: WORDS)
Make the intersection of the Current set with other.
• infix "^" (other: WORDS): WORDS
Return the intersection of the Current set with other.
• minus (other: WORDS)
Make the set Current - other.
• fast_minus (other: WORDS)
Make the set Current - other.
• infix "-" (other: WORDS): WORDS
Return the set Current - other.
Comparison:
{ANY}
Implement manifest generic creation:
{}
{ANY}
Other features:
{ANY}
Agent-based features:
{ANY}
Printing:
{ANY}
{ANY}
{}
Agent-based features:
{ANY}
{}
Indexing:
{ANY}
{ANY}
• test (e1: E_, e2: E_): BOOLEAN
In order to avoid run-time type errors, feature safe_equal calls is_equal only when e1 and e2 have exactly the same dynamic type.
• safe_equal (e1: E_, e2: E_): BOOLEAN
In order to avoid run-time type errors, feature safe_equal calls is_equal only when e1 and e2 have exactly the same dynamic type.
{}
Capacity management: ideally we try to keep the dictionary less than 2/3rd filled
{}
Maximum:
{}
Minimum:
{}
Bits:
{}
effective procedure
{ANY}
If it does not exists or if it is not a file nothing is done.
require
• a_file_name /= Void
print_all
effective procedure
{ANY}
hash_code (e: E_): INTEGER_32
effective function
{}
require
• e /= Void
Default_size: INTEGER_32
is 53
constant attribute
{ANY}
Minimum size for storage in number of items.
buckets: NATIVE_ARRAY[HASHED_SET_NODE[E_]]
writable attribute
{SET}
The buckets storage area is the primary hash table of capacity elements.
To search some element, the first access is done in buckets using the remainder of the division of the key hash_code by capacity. In order to try to avoid clashes, capacity is always a prime number (selected using HASHED_CAPACITY).
cache_user: INTEGER_32
writable attribute
{SET}
The last user's external index in range [1 .. count] (see item and valid_index for example) may be saved in cache_user otherwise -1 to indicate that the cache is not active.
When the cache is active, the corresponding index in buckets is save in cache_buckets and the corresponding node in cache_node.
cache_node: HASHED_SET_NODE[E_]
writable attribute
{SET}
Meaningful only when cache_user is not -1.
cache_buckets: INTEGER_32
writable attribute
{SET}
Meaningful only when cache_user is not -1.
create_with_capacity (new_capacity: INTEGER_32)
effective procedure
{}
require
• new_capacity > 0
make
effective procedure
{}
Create an empty set.
Internal storage capacity of the set is initialized using the Default_size value. Then, tuning of needed storage size is done automatically according to usage. If you are really sure that your set is always really bigger than Default_size, you may use with_capacity to save some execution time.
ensure
with_capacity (medium_size: INTEGER_32)
effective procedure
{}
Create an empty set using medium_size as an appropriate value to help initialization of capacity.
Thus, this feature may be used in place of make to save some execution time if one is sure that storage size will rapidly become really bigger than Default_size (if not sure, simply use make). Anyway, the initial medium_size value is just an indication and never a limit for the possible capacity. Keep in mind that the capacity tuning is done automatically according to usage.
require
• medium_size > 0
ensure
capacity: INTEGER_32
writable attribute
{ANY}
Of the buckets storage area.
count: INTEGER_32
writable attribute
{ANY}
Number of available items in the hoard.
ensure
• Result >= 0
effective procedure
{ANY}
Add new item e to the set.
The mathematical definition of adding in a set is followed, i.e. the element e is added only and only if it is not yet present in the set. As this add feature is actually using is_equal, you may consider to use fast_add for expanded objects as well while trying to get the very best performances.
require
• e /= Void
ensure
• not_in_then_added: not old has(e) implies count = old count + 1
• in_then_not_added: old has(e) implies count = old count
effective procedure
{ANY}
Same job as add, but uses basic = for comparison.
require
• e /= Void
ensure
• not_in_then_added: not old has(e) implies count = old count + 1
• in_then_not_added: old has(e) implies count = old count
remove (e: E_)
effective procedure
{ANY}
Remove item e from the set: the mathematical definition of removing from a set is followed.
require
• e /= Void
ensure
• removed: not has(e)
• not_in_not_removed: not old has(e) implies count = old count
• in_then_removed: old has(e) implies count = old count - 1
fast_remove (e: E_)
effective procedure
{ANY}
Same job as remove, but uses basic = for comparison.
require
• e /= Void
ensure
• removed: not has(e)
• not_in_not_removed: not old has(e) implies count = old count
• in_then_removed: old has(e) implies count = old count - 1
clear_count
effective procedure
{ANY}
Empty the current set (is_empty is True after that call).
If possible, the actual implementation is supposed to keep its internal storage area in order to refill Current in an efficient way. See also clear_count_and_capacity to select the most appropriate.
ensure
clear_count_and_capacity
effective procedure
{ANY}
Empty the current set (is_empty is True after that call).
If possible, the actual implementation is supposed to release its internal storage area for this memory to be used by other objects. See also clear_count to select the most appropriate.
ensure
has (e: E_): BOOLEAN
effective function
{ANY}
Is element e in the set?
As this query is actually using is_equal, you may consider to use fast_has for expanded objects as well while trying to get the very best performances.
require
• e /= Void
ensure
• Result implies not is_empty
fast_has (e: E_): BOOLEAN
effective function
{ANY}
Is element e actually stored in the set?
Warning: this query is using basic = for comparison. See also has when dealing with reference types.
require
• e /= Void
ensure
• Result implies e = reference_at(e)
reference_at (e: E_): E_
effective function
{ANY}
Non Void when e is in the set.
In such a situation, Result is the object which is actually stored in the Current set (see ensure assertion).
require
• e /= Void
• elements_are_not_expanded: Result = Void
ensure
• has(e) implies Result.is_equal(e)
item (index: INTEGER_32): E_
effective function
{ANY}
Item at the corresponding index i.
SETs are intrinsically unordered, so there is no guarantee that item(i) after performing an add or remove operation is related in any way to item(i) before that operation.
require
• valid_index(index)
ensure
• has(Result)
intersection (other: WORDS)
effective procedure
{ANY}
Make the intersection of the Current set with other.
require
• other /= Void
ensure
• count <= other.count.min(old count)
copy (other: WORDS)
effective procedure
{ANY}
Copy 'other' into the current set
require
• not immutable
• same_dynamic_type(other)
• not immutable
• same_dynamic_type(other)
• not immutable
• same_dynamic_type(other)
• not immutable
• same_dynamic_type(other)
ensure
• is_equal(other)
from_collection (model: COLLECTION[E_])
effective procedure
{ANY}
require
• model /= Void
manifest_make (needed_capacity: INTEGER_32)
effective procedure
{}
Manifest creation of a HASHED_SET.
free_nodes: WEAK_REFERENCE[HASHED_SET_NODE[E_]]
writable attribute
{}
If any, they are ready to be recycled.
once function
{}
dispose_node (node: HASHED_SET_NODE[E_]): HASHED_SET_NODE[E_]
effective function
{}
Clear and add node in the free_nodes list.
require
• node /= Void
ensure
new_node (e: E_, next: HASHED_SET_NODE[E_]): HASHED_SET_NODE[E_]
effective function
{}
Recycle from free_nodes or create a new one.
increase_capacity
effective procedure
{}
There are not enough free slots: the set must grow.
require ensure
set_cache_user (index: INTEGER_32)
effective procedure
{}
is_empty: BOOLEAN
effective function
{ANY}
Is the set empty?
ensure
• definition: Result = count = 0
lower: INTEGER_32
is 1
constant attribute
{ANY}
Minimum index.
upper: INTEGER_32
effective function
{ANY}
Maximum index.
ensure
first: E_
effective function
{ANY}
The very first item.
require
• not is_empty
ensure
• definition: Result = item(lower)
last: E_
effective function
{ANY}
The last item.
require
• not is_empty
ensure
• definition: Result = item(upper)
new_iterator: ITERATOR[E_]
effective function
{ANY}
ensure
• Result /= Void
• Result.generation = generation
union (other: WORDS)
effective procedure
{ANY}
Make the union of the Current set with other.
require
• other /= Void
ensure
fast_union (other: WORDS)
effective procedure
{ANY}
Make the union of the Current set with other.
require
• other /= Void
ensure
infix "+" (other: WORDS): WORDS
effective function
{ANY}
Return the union of the Current set with other.
require
• other /= Void
ensure
fast_intersection (other: WORDS)
effective procedure
{ANY}
Make the intersection of the Current set with other.
require
• other /= Void
ensure
infix "^" (other: WORDS): WORDS
effective function
{ANY}
Return the intersection of the Current set with other.
require
• other /= Void
ensure
minus (other: WORDS)
effective procedure
{ANY}
Make the set Current - other.
require
• other /= Void
ensure
fast_minus (other: WORDS)
effective procedure
{ANY}
Make the set Current - other.
require
• other /= Void
ensure
infix "-" (other: WORDS): WORDS
effective function
{ANY}
Return the set Current - other.
require
• other /= Void
ensure
is_subset_of (other: WORDS): BOOLEAN
effective function
{ANY}
Is the Current set a subset of other?
require
• other /= Void
ensure
is_disjoint_from (other: WORDS): BOOLEAN
effective function
{ANY}
Is the Current set disjoint from other ?
require
• other /= Void
ensure
is_equal (other: WORDS): BOOLEAN
effective function
{ANY}
Is the Current set equal to other?
require
• other /= Void
• other /= Void
• other /= Void
ensure
• double_inclusion: Result = is_subset_of(other) and other.is_subset_of(Current)
• commutative: generating_type = other.generating_type implies Result = other.is_equal(Current)
manifest_put (index: INTEGER_32, element: E_)
effective procedure
{}
manifest_semicolon_check: BOOLEAN
is False
constant attribute
{}
enumerate: ENUMERATE[E_]
effective function
{ANY}
get_new_iterator: ITERATOR[E_]
frozen
effective function
{ANY}
This feature is obsolete: Use `new_iterator' instead. This historical SmartEiffel feature is badly named.
for_each (action: PROCEDURE[TUPLE[TUPLE 1[E_]]])
effective procedure
{ANY}
Apply action to every item of Current.
require
• action /= Void
for_all (test: FUNCTION[TUPLE[TUPLE 1[E_]]]): BOOLEAN
effective function
{ANY}
Do all items satisfy test?
require
• test /= Void
exists (test: FUNCTION[TUPLE[TUPLE 1[E_]]]): BOOLEAN
effective function
{ANY}
Does at least one item satisfy test?
require
• test /= Void
aggregate (action: FUNCTION[TUPLE[TUPLE 2[E_, E_], E_]], initial: E_): E_
effective function
{ANY}
Aggregate all the elements starting from the initial value.
require
• action /= Void
out_in_tagged_out_memory
effective procedure
{ANY}
Append terse printable representation of current object in tagged_out_memory.
require
• locked: tagged_out_locked
ensure
• still_locked: tagged_out_locked
• not_cleared: tagged_out_memory.count >= old tagged_out_memory.count
• append_only: old tagged_out_memory.twin.is_equal(tagged_out_memory.substring(1, old tagged_out_memory.count))
generation: INTEGER_32
writable attribute
{ANY}
next_generation
effective procedure
{}
ensure
do_all (action: ROUTINE[TUPLE[TUPLE 1[E_]]])
frozen
effective procedure
{ANY}
Apply action to every item of Current.
This feature is obsolete: Use `for_each` instead. This feature is not secure because it accepts a FUNCTION, the result of which is lost.
_inline_agent2 (a: ROUTINE[TUPLE[TUPLE 1[E_]]], e: E_)
frozen
effective procedure
{}
valid_index (i: INTEGER_32): BOOLEAN
effective function
{ANY}
True when i is valid (i.e., inside actual bounds).
ensure
test (e1: E_, e2: E_): BOOLEAN
effective function
{ANY}
In order to avoid run-time type errors, feature safe_equal calls is_equal only when e1 and e2 have exactly the same dynamic type.
safe_equal (e1: E_, e2: E_): BOOLEAN
effective function
{ANY}
In order to avoid run-time type errors, feature safe_equal calls is_equal only when e1 and e2 have exactly the same dynamic type.
prime_number_ceiling (integer: INTEGER_32): INTEGER_32
effective function
{}
A good prime number, large enough, and no smaller than integer.
require
• is_positive: integer >= 0
ensure
• Result >= integer.max(1)
prime_capacity (a_capacity: INTEGER_32): INTEGER_32
effective function
{}
require
• a_capacity >= 0
ensure
• Result >= a_capacity
should_increase_capacity (a_capacity: INTEGER_32, a_count: INTEGER_32): BOOLEAN
effective function
{}
Maximum_character_code: INTEGER_16
{}
Largest supported code for CHARACTER values.
ensure
• meaningful: Result >= 127
Maximum_integer_8: INTEGER_8
is 127
constant attribute
{}
Largest supported value of type INTEGER_8.
Maximum_integer_16: INTEGER_16
is 32767
constant attribute
{}
Largest supported value of type INTEGER_16.
Maximum_integer: INTEGER_32
is 2147483647
constant attribute
{}
Largest supported value of type INTEGER/INTEGER_32.
Maximum_integer_32: INTEGER_32
is 2147483647
constant attribute
{}
Largest supported value of type INTEGER/INTEGER_32.
Maximum_integer_64: INTEGER_64
is 9223372036854775807
constant attribute
{}
Largest supported value of type INTEGER_64.
Maximum_real_32: REAL_32
is {REAL_32 3.4028234663852885981170418348451692544e+38}
constant attribute
{}
Largest non-special (no NaNs nor infinity) supported value of type REAL_32.
Maximum_real: REAL_64
{}
Largest non-special (no NaNs nor infinity) supported value of type REAL.
Just to give an idea of this value: 1.79769313486231570....e+308
Maximum_real_64: REAL_64
{}
Largest non-special (no NaNs nor infinity) supported value of type REAL.
Just to give an idea of this value: 1.79769313486231570....e+308
Maximum_real_80: REAL_EXTENDED
{}
Largest supported value of type REAL_80.
ensure
Minimum_character_code: INTEGER_16
{}
Smallest supported code for CHARACTER values.
ensure
• meaningful: Result <= 0
Minimum_integer_8: INTEGER_8
is -128
constant attribute
{}
Smallest supported value of type INTEGER_8.
Minimum_integer_16: INTEGER_16
is -32768
constant attribute
{}
Smallest supported value of type INTEGER_16.
Minimum_integer: INTEGER_32
is -2147483648
constant attribute
{}
Smallest supported value of type INTEGER/INTEGER_32.
Minimum_integer_32: INTEGER_32
is -2147483648
constant attribute
{}
Smallest supported value of type INTEGER/INTEGER_32.
Minimum_integer_64: INTEGER_64
is -9223372036854775808
constant attribute
{}
Smallest supported value of type INTEGER_64.
Minimum_real_32: REAL_32
is {REAL_32 -3.40282346638528859811704183484516925440e+38}
constant attribute
{}
Smallest non-special (no NaNs nor infinity) supported value of type REAL_32.
Minimum_real: REAL_64
{}
Smallest non-special (no NaNs nor infinity) supported value of type REAL.
Just to give an idea of this value: -1.79769313486231570....e+308
Minimum_real_64: REAL_64
{}
Smallest non-special (no NaNs nor infinity) supported value of type REAL.
Just to give an idea of this value: -1.79769313486231570....e+308
Minimum_real_80: REAL_64
{}
Smallest supported value of type REAL_80.
ensure
• meaningful: Result <= 0.0
Boolean_bits: INTEGER_32
{}
Number of bits in a value of type BOOLEAN.
ensure
• meaningful: Result >= 1
Character_bits: INTEGER_32
{}
Number of bits in a value of type CHARACTER.
ensure
Integer_bits: INTEGER_32
{}
Number of bits in a value of type INTEGER.
ensure
• integer_definition: Result = 32
Real_bits: INTEGER_32
is 64
constant attribute
{}
Number of bits in a value of type REAL.
Pointer_bits: INTEGER_32
{}
Number of bits in a value of type POINTER.