+
Point of view
All features
class LINKED_LIST [E_]
Summary
top
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
top
Overview
top
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
{}
top
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
{LINKED_LIST, ITERATOR_ON_LINKED_LIST}
top
Void when empty or gives access to the first element.
last_link: LINKED_LIST_NODE[E_]
writable attribute
{LINKED_LIST}
top
Void when empty or gives access to the last element.
mem_idx: INTEGER_32
writable attribute
{LINKED_LIST}
top
mem_lnk: LINKED_LIST_NODE[E_]
writable attribute
{LINKED_LIST}
top
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}
top
Make an empty list
ensure
is_empty: BOOLEAN
effective function
{ANY}
top
Is the hoard empty ?
See also count.
ensure
  • definition: Result = count = 0
add_first (element: E_)
effective procedure
{ANY}
top
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}
top
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}
top
Add a new element at rank index : count is increased by one and range [index .. upper] is shifted right by one position.
See also add_first, add_last, append_collection.
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}
top
Remove the first element of the collection.
See also remove_last, remove, remove_head.
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}
top
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}
top
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}
top
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}
top
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}
top
Make element the item at index i.
See also lower, upper, valid_index, item, swap, force.
require
    • valid_index(index)
    • valid_index(index)
ensure
  • item(index) = element
  • count = old count
count: INTEGER_32
effective function
{ANY}
top
Number of available items in the hoard.
See also is_empty
ensure
  • Result >= 0
set_all_with (v: E_)
effective procedure
{ANY}
top
Set all items with value v.
See also set_slice_with.
ensure
  • count = old count
copy (other: LINKED_LIST [E_])
effective procedure
{ANY}
top
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}
top
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}
top
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}
top
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}
top
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}
top
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}
top
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}
top
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}
top
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}
top
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}
top
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}
top
Number of occurrences of element using is_equal for comparison.
See also fast_occurrences, index_of.
ensure
  • Result >= 0
fast_occurrences (element: E_): INTEGER_32
effective function
{ANY}
top
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}
top
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}
top
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}
top
Remove the last item.
See also remove_first, remove, remove_tail.
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}
top
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}
top
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}
top
ensure
  • Result /= Void
  • Result.generation = generation
reverse
effective procedure
{ANY}
top
Reverse the order of the elements.
ensure
  • count = old count
go_item (i: INTEGER_32)
effective procedure
{}
top
require ensure
free_nodes: WEAK_REFERENCE[LINKED_LIST_NODE[E_]]
writable attribute
{}
top
If any, they are ready to be recycled.
once function
{}
top
dispose_node (node: LINKED_LIST_NODE[E_]): LINKED_LIST_NODE[E_]
effective function
{}
top
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
{}
top
Recycle from free_nodes or create a new one.
infix "@" (i: INTEGER_32): E_
frozen
effective function
{ANY}
top
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}
top
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}
top
Set all items in range [lower_index .. upper_index] with v.
See also set_all_with.
require ensure
clear_all
effective procedure
{ANY}
top
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}
top
Append other to Current.
This feature is obsolete: Use `append_traversable' instead.
append_traversable (other: TRAVERSABLE[E_])
effective procedure
{ANY}
top
Append other to Current.
See also add_last, add_first, add.
require
  • other /= Void
ensure
remove_head (n: INTEGER_32)
deferred procedure
{ANY}
top
Remove the n elements of the collection.
See also remove_tail, remove, remove_first.
require ensure
remove_tail (n: INTEGER_32)
deferred procedure
{ANY}
top
Remove the last n item(s).
See also remove_head, remove, remove_last.
require ensure
has (x: ANY): BOOLEAN
effective function
{ANY}
top
Look for x using is_equal for comparison.
See also fast_has, index_of, fast_index_of.
ensure
  • definition: Result = valid_index(first_index_of(x))
fast_has (x: ANY): BOOLEAN
effective function
{ANY}
top
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}
top
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}
top
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}
top
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}
top
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}
top
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
{}
top
manifest_put (index: INTEGER_32, element: ANY)
deferred procedure
{}
top
require
  • index >= 0
enumerate: ENUMERATE[E_]
effective function
{ANY}
top
get_new_iterator: ITERATOR[E_]
frozen
effective function
{ANY}
top
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}
top
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}
top
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}
top
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}
top
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}
top
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}
top
next_generation
effective procedure
{}
top
ensure
do_all (action: ROUTINE[TUPLE[TUPLE 1[E_]]])
frozen
effective procedure
{ANY}
top
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
{}
top
lower: INTEGER_32
deferred function
{ANY}
top
Minimum index.
See also upper, valid_index, item.
upper: INTEGER_32
deferred function
{ANY}
top
Maximum index.
See also lower, valid_index, item.
valid_index (i: INTEGER_32): BOOLEAN
effective function
{ANY}
top
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}
top
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}
top
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
{}
top
Manifest creation of a list of items of type E_.