+
Point of view
All features
class LINKED_LIST [E_]
Summary
One way linked list implementation with internal automatic cached memorization of the last access. Because of the last access memory cache, the traversal of a LINKED_LIST from the lower index to the upper index using item is quite efficient. As one can expect, adding element using add_first or add_last is really efficient too, actually, the total number of elements (i.e. count) as well as a reference to the last cell is also cached automatically. Keep in mind that LINKED_LIST uses a one way linked storage from lower to upper, so traversing a LINKED_LIST from upper to lower will be extremely time consuming (also consider TWO_WAY_LINKED_LIST).
Direct parents
Inherit list: COLLECTION
Insert list: LINKED_COLLECTION
Class invariant
Overview
Creation features
{ANY}
Features
{}
{LINKED_LIST, ITERATOR_ON_LINKED_LIST}
  • first_link: LINKED_LIST_NODE[E_]
    Void when empty or gives access to the first element.
{LINKED_LIST}
{ANY}
{}
Accessing:
{ANY}
Writing:
{ANY}
Adding:
{ANY}
Removing:
{ANY}
Looking and Searching:
{ANY}
Looking and comparison:
{ANY}
Other features:
{ANY}
Implement manifest generic creation:
{}
{ANY}
Other features:
{ANY}
Agent-based features:
{ANY}
Printing:
{ANY}
{ANY}
{}
Agent-based features:
{ANY}
{}
Indexing:
{ANY}
Looking and Searching:
{ANY}
Implement manifest generic creation:
{}
default_create
effective procedure
{}
Default creation method.
It is used when no creation method is specified if allowed. Note it may be renamed.
first_link: LINKED_LIST_NODE[E_]
writable attribute
Void when empty or gives access to the first element.
last_link: LINKED_LIST_NODE[E_]
writable attribute
Void when empty or gives access to the last element.
mem_idx: INTEGER_32
writable attribute
mem_lnk: LINKED_LIST_NODE[E_]
writable attribute
To speed up accessing, mem_idx and mem_lnk is the memory of the last access done.
For example, after item(1), mem_idx is 1 and mem_lnk is first_link. When list is empty, first_link is Void as well as mem_lnk and mem_idx is 0
make
effective procedure
{ANY}
Make an empty list
ensure
is_empty: BOOLEAN
effective function
{ANY}
Is the hoard empty ?
See also count.
ensure
  • definition: Result = count = 0
add_first (element: E_)
effective procedure
{ANY}
Add a new item in first position : count is increased by one and all other items are shifted right.
See also add_last, first, last, add.
ensure
  • first = element
  • count = 1 + old count
  • lower = old lower
  • upper = 1 + old upper
add_last (element: E_)
effective procedure
{ANY}
Add a new item at the end : count is increased by one.
See also add_first, last, first, add.
ensure
  • last = element
  • count = 1 + old count
  • lower = old lower
  • upper = 1 + old upper
add (element: E_, index: INTEGER_32)
effective procedure
{ANY}
Add a new element at rank index : count is increased by one and range [index .. upper] is shifted right by one position.
require
    • index.in_range(lower, upper + 1)
    • index.in_range(lower, upper + 1)
ensure
  • item(index) = element
  • count = 1 + old count
  • upper = 1 + old upper
remove_first
effective procedure
{ANY}
Remove the first element of the collection.
require
    • not is_empty
    • not is_empty
ensure
  • count = old count - 1
  • lower = old lower + 1 xor upper = old upper - 1
remove (index: INTEGER_32)
effective procedure
{ANY}
Remove the item at position index.
Followings items are shifted left by one position.
See also remove_first, remove_head, remove_tail, remove_last.
require
    • valid_index(index)
    • valid_index(index)
ensure
  • count = old count - 1
  • upper = old upper - 1
first: E_
effective function
{ANY}
The very first item.
See also last, item.
require
      • not is_empty
      • not is_empty
      • not is_empty
      • not is_empty
ensure
  • definition: Result = item(lower)
last: E_
effective function
{ANY}
The last item.
See also first, item.
require
      • not is_empty
      • not is_empty
      • not is_empty
      • not is_empty
ensure
  • definition: Result = item(upper)
item (index: INTEGER_32): E_
effective function
{ANY}
Item at the corresponding index i.
See also lower, upper, valid_index.
require
      • valid_index(index)
      • valid_index(index)
      • valid_index(index)
      • valid_index(index)
put (element: E_, index: INTEGER_32)
effective procedure
{ANY}
Make element the item at index i.
require
    • valid_index(index)
    • valid_index(index)
ensure
  • item(index) = element
  • count = old count
count: INTEGER_32
effective function
{ANY}
Number of available items in the hoard.
See also is_empty
ensure
  • Result >= 0
set_all_with (v: E_)
effective procedure
{ANY}
Set all items with value v.
See also set_slice_with.
ensure
  • count = old count
copy (other: LINKED_LIST [E_])
effective procedure
{ANY}
Reinitialize by copying all the items of other.
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)
        • not immutable
        • same_dynamic_type(other)
        • not immutable
        • same_dynamic_type(other)
ensure
  • is_equal(other)
fast_is_equal (other: LINKED_LIST [E_]): BOOLEAN
effective function
{ANY}
Do both collections have the same lower, upper, and items?
The basic = is used for comparison of items.
See also is_equal, same_items.
ensure
  • Result implies lower = other.lower and upper = other.upper
is_equal (other: LINKED_LIST [E_]): BOOLEAN
effective function
{ANY}
Do both collections have the same lower, upper, and items?
Feature is_equal is used for comparison of items.
See also fast_is_equal, same_items.
require
      • other /= Void
        • other /= Void
        • other /= Void
      • other /= Void
        • other /= Void
        • other /= Void
ensure
  • Result implies lower = other.lower and upper = other.upper
  • commutative: generating_type = other.generating_type implies Result = other.is_equal(Current)
index_of (x: E_, start_index: INTEGER_32): INTEGER_32
effective function
{ANY}
Using is_equal for comparison, gives the index of the first occurrence of element at or after start_index.
Return upper + 1 if the search for element failed.
See also fast_index_of, reverse_index_of, first_index_of.
ensure
  • Result.in_range(start_index, upper + 1)
  • valid_index(Result) implies (create {SAFE_EQUAL}).test(x, item(Result))
reverse_index_of (element: E_, start_index: INTEGER_32): INTEGER_32
effective function
{ANY}
Using is_equal for comparison, gives the index of the first occurrence of element at or before start_index.
Search is done in reverse direction, which means from the start_index down to the lower index . Answer lower -1 when the search fail.
See also fast_reverse_index_of, last_index_of, index_of.
require
    • valid_index(start_index)
    • valid_index(start_index)
ensure
  • Result.in_range(lower - 1, start_index)
  • valid_index(Result) implies item(Result).is_equal(element)
fast_index_of (x: E_, start_index: INTEGER_32): INTEGER_32
effective function
{ANY}
Using basic = for comparison, gives the index of the first occurrence of element at or after start_index.
Answer upper + 1 when element when the search fail.
See also index_of, fast_reverse_index_of, fast_first_index_of.
ensure
  • Result.in_range(start_index, upper + 1)
  • valid_index(Result) implies x = item(Result)
fast_reverse_index_of (element: E_, start_index: INTEGER_32): INTEGER_32
effective function
{ANY}
Using basic = comparison, gives the index of the first occurrence of element at or before start_index.
Search is done in reverse direction, which means from the start_index down to the lower index . Answer lower -1 when the search fail.
See also reverse_index_of, fast_index_of, fast_last_index_of.
require
    • valid_index(start_index)
    • valid_index(start_index)
ensure
  • Result.in_range(lower - 1, start_index)
  • valid_index(Result) implies item(Result) = element
clear_count
effective procedure
{ANY}
Discard all items (is_empty is True after that call).
If possible, the actual implementation supposed to keep its internal storage area in order to refill Current in an efficient way.
See also clear_count_and_capacity.
ensure
  • upper = 0
  • is_empty: count = 0
clear_count_and_capacity
effective procedure
{ANY}
Discard all items (is_empty is True after that call).
If possible, the actual implementation supposed to release its internal storage area for this memory to be used by other objects.
See also clear_count.
ensure
  • upper = 0
  • is_empty: count = 0
from_collection (model: TRAVERSABLE[E_])
effective procedure
{ANY}
Initialize the current object with the contents of model.
require
    • model /= Void
    • useful_work: model /= Current
    • model /= Void
    • useful_work: model /= Current
ensure
  • count = model.count
slice (low: INTEGER_32, up: INTEGER_32): LINKED_LIST [E_]
effective function
{ANY}
New collection consisting of items at indexes in [min..max].
Result has the same dynamic type as Current. The lower index of the Result is the same as lower.
See also from_collection, move, replace_all.
require
    • lower <= low
    • up <= upper
    • low <= up + 1
    • lower <= low
    • up <= upper
    • low <= up + 1
ensure
  • same_dynamic_type(Result)
  • Result.count = up - low + 1
  • Result.lower = lower
occurrences (element: E_): INTEGER_32
effective function
{ANY}
Number of occurrences of element using is_equal for comparison.
ensure
  • Result >= 0
fast_occurrences (element: E_): INTEGER_32
effective function
{ANY}
Number of occurrences of element using basic = for comparison.
See also occurrences, index_of.
ensure
  • Result >= 0
force (element: E_, index: INTEGER_32)
effective procedure
{ANY}
Make element the item at index, enlarging the collection if necessary (new bounds except index are initialized with default values).
See also put, item, swap.
require
    • index >= lower
    • index >= lower
ensure
  • upper = index.max(old upper)
  • item(index) = element
all_default: BOOLEAN
effective function
{ANY}
Do all items have their type's default value?
Note: for non Void items, the test is performed with the is_default predicate.
See also clear_all.
remove_last
effective procedure
{ANY}
Remove the last item.
require
    • not is_empty
    • not is_empty
ensure
  • count = old count - 1
  • upper = old upper - 1
replace_all (old_value: E_, new_value: E_)
effective procedure
{ANY}
Replace all occurrences of the element old_value by new_value using is_equal for comparison.
See also fast_replace_all, move.
ensure
  • count = old count
  • not (create {SAFE_EQUAL}).test(old_value, new_value) implies occurrences(old_value) = 0
fast_replace_all (old_value: E_, new_value: E_)
effective procedure
{ANY}
Replace all occurrences of the element old_value by new_value using basic = for comparison.
See also replace_all, move.
ensure
  • count = old count
  • old_value /= new_value implies fast_occurrences(old_value) = 0
new_iterator: ITERATOR[E_]
effective function
{ANY}
ensure
  • Result /= Void
  • Result.generation = generation
reverse
effective procedure
{ANY}
Reverse the order of the elements.
ensure
  • count = old count
go_item (i: INTEGER_32)
effective procedure
{}
require ensure
free_nodes: WEAK_REFERENCE[LINKED_LIST_NODE[E_]]
writable attribute
{}
If any, they are ready to be recycled.
once function
{}
dispose_node (node: LINKED_LIST_NODE[E_]): LINKED_LIST_NODE[E_]
effective function
{}
Add node in the free_nodes list.
require
  • node /= Void
ensure
  • Result = old node.next
new_node (e: E_, next: LINKED_LIST_NODE[E_]): LINKED_LIST_NODE[E_]
effective function
{}
Recycle from free_nodes or create a new one.
infix "@" (i: INTEGER_32): E_
frozen
effective function
{ANY}
The infix notation which is actually just a synonym for item.
See also item.
require ensure
  • definition: Result = item(i)
swap (i1: INTEGER_32, i2: INTEGER_32)
effective procedure
{ANY}
Swap item at index i1 with item at index i2.
See also item, put.
require ensure
set_slice_with (v: ANY, lower_index: INTEGER_32, upper_index: INTEGER_32)
effective procedure
{ANY}
Set all items in range [lower_index .. upper_index] with v.
See also set_all_with.
require ensure
clear_all
effective procedure
{ANY}
Set every item to its default value.
The count is not affected.
See also clear, all_default.
ensure
append_collection (other: COLLECTION[E_])
effective procedure
{ANY}
Append other to Current.
This feature is obsolete: Use `append_traversable' instead.
append_traversable (other: TRAVERSABLE[E_])
effective procedure
{ANY}
Append other to Current.
See also add_last, add_first, add.
require
  • other /= Void
ensure
remove_head (n: INTEGER_32)
deferred procedure
{ANY}
Remove the n elements of the collection.
require ensure
remove_tail (n: INTEGER_32)
deferred procedure
{ANY}
Remove the last n item(s).
require ensure
has (x: ANY): BOOLEAN
effective function
{ANY}
Look for x using is_equal for comparison.
ensure
  • definition: Result = valid_index(first_index_of(x))
fast_has (x: ANY): BOOLEAN
effective function
{ANY}
Look for x using basic = for comparison.
See also has, fast_index_of, index_of.
ensure
  • definition: Result = valid_index(fast_first_index_of(x))
last_index_of (element: ANY): INTEGER_32
effective function
{ANY}
Using is_equal for comparison, gives the index of the last occurrence of element at or before upper.
Search is done in reverse direction, which means from the upper down to the lower index . Answer lower -1 when the search fail.
See also fast_last_index_of, reverse_index_of, index_of.
ensure
  • definition: Result = reverse_index_of(element, upper)
fast_last_index_of (element: ANY): INTEGER_32
effective function
{ANY}
Using basic = for comparison, gives the index of the last occurrence of element at or before upper.
Search is done in reverse direction, which means from the upper down to the lower index . Answer lower -1 when the search fail.
See also fast_reverse_index_of, last_index_of.
ensure
  • definition: Result = fast_reverse_index_of(element, upper)
is_equal_map (other: LINKED_LIST [E_]): BOOLEAN
effective function
{ANY}
Do both collections have the same lower, upper, and items?
This feature is obsolete: Use `is_equal' instead.
same_items (other: COLLECTION[E_]): BOOLEAN
effective function
{ANY}
Do both collections have the same items?
The basic = is used for comparison of items and indices are not considered (for example this routine may yield True with Current indexed in range [1..2] and other indexed in range [2..3]).
See also is_equal, fast_is_equal.
require
  • other /= Void
ensure
move (lower_index: INTEGER_32, upper_index: INTEGER_32, distance: INTEGER_32)
effective procedure
{ANY}
Move range lower_index ..
upper_index by distance positions. Negative distance moves towards lower indices. Free places get default values.
See also slice, replace_all.
require ensure
manifest_semicolon_check: BOOLEAN
is False
constant attribute
{}
manifest_put (index: INTEGER_32, element: ANY)
deferred procedure
{}
require
  • index >= 0
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.
See also for_all, exists, aggregate.
require
  • action /= Void
for_all (test: FUNCTION[TUPLE[TUPLE 1[E_]]]): BOOLEAN
effective function
{ANY}
Do all items satisfy test?
See also for_each, exists, aggregate.
require
  • test /= Void
exists (test: FUNCTION[TUPLE[TUPLE 1[E_]]]): BOOLEAN
effective function
{ANY}
Does at least one item satisfy test?
See also for_each, for_all, aggregate.
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.
See also for_each, for_all, exists.
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_agent1 (a: ROUTINE[TUPLE[TUPLE 1[E_]]], e: E_)
frozen
effective procedure
{}
lower: INTEGER_32
deferred function
{ANY}
Minimum index.
See also upper, valid_index, item.
upper: INTEGER_32
deferred function
{ANY}
Maximum index.
See also lower, valid_index, item.
valid_index (i: INTEGER_32): BOOLEAN
effective function
{ANY}
True when i is valid (i.e., inside actual bounds).
See also lower, upper, item.
ensure
first_index_of (element: ANY): INTEGER_32
deferred function
{ANY}
Give the index of the first occurrence of element using is_equal for comparison.
Answer upper + 1 when element is not inside.
See also fast_first_index_of, index_of, last_index_of, reverse_index_of.
ensure
fast_first_index_of (element: ANY): INTEGER_32
deferred function
{ANY}
Give the index of the first occurrence of element using basic = for comparison.
Answer upper + 1 when element is not inside.
See also first_index_of, last_index_of, fast_last_index_of.
ensure
manifest_make (needed_capacity: INTEGER_32)
effective procedure
{}
Manifest creation of a list of items of type E_.