+
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.
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.
make
effective procedure
{ANY}
top
Make an empty list
is_empty: BOOLEAN
effective function
{ANY}
top
Is the hoard empty ?
See also count.
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.
add_last (element: E_)
effective procedure
{ANY}
top
Add a new item at the end : count is increased by one.
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.
remove_first
effective procedure
{ANY}
top
Remove the first element of the collection.
remove (index: INTEGER_32)
effective procedure
{ANY}
top
Remove the item at position index.
first: E_
effective function
{ANY}
top
The very first item.
last: E_
effective function
{ANY}
top
The last item.
item (index: INTEGER_32): E_
effective function
{ANY}
top
Item at the corresponding index i.
put (element: E_, index: INTEGER_32)
effective procedure
{ANY}
top
Make element the item at index i.
count: INTEGER_32
effective function
{ANY}
top
Number of available items in the hoard.
set_all_with (v: E_)
effective procedure
{ANY}
top
Set all items with value v.
copy (other: LINKED_LIST [E_])
effective procedure
{ANY}
top
Reinitialize by copying all the items of other.
fast_is_equal (other: LINKED_LIST [E_]): BOOLEAN
effective function
{ANY}
top
Do both collections have the same lower, upper, and items?
is_equal (other: LINKED_LIST [E_]): BOOLEAN
effective function
{ANY}
top
Do both collections have the same lower, upper, and items?
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.
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.
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.
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.
clear_count
effective procedure
{ANY}
top
Discard all items (is_empty is True after that call).
clear_count_and_capacity
effective procedure
{ANY}
top
Discard all items (is_empty is True after that call).
from_collection (model: TRAVERSABLE[E_])
effective procedure
{ANY}
top
Initialize the current object with the contents of model.
slice (low: INTEGER_32, up: INTEGER_32): LINKED_LIST [E_]
effective function
{ANY}
top
New collection consisting of items at indexes in [min..max].
occurrences (element: E_): INTEGER_32
effective function
{ANY}
top
Number of occurrences of element using is_equal for comparison.
fast_occurrences (element: E_): INTEGER_32
effective function
{ANY}
top
Number of occurrences of element using basic = for comparison.
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).
all_default: BOOLEAN
effective function
{ANY}
top
Do all items have their type's default value?
remove_last
effective procedure
{ANY}
top
Remove the last item.
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.
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.
new_iterator: ITERATOR[E_]
effective function
{ANY}
top
reverse
effective procedure
{ANY}
top
Reverse the order of the elements.
go_item (i: INTEGER_32)
effective procedure
{}
top
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.
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.
swap (i1: INTEGER_32, i2: INTEGER_32)
effective procedure
{ANY}
top
Swap item at index i1 with item at index i2.
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.
clear_all
effective procedure
{ANY}
top
Set every item to its default value.
append_collection (other: COLLECTION[E_])
effective procedure
{ANY}
top
Append other to Current.
append_traversable (other: TRAVERSABLE[E_])
effective procedure
{ANY}
top
Append other to Current.
remove_head (n: INTEGER_32)
deferred procedure
{ANY}
top
Remove the n elements of the collection.
remove_tail (n: INTEGER_32)
deferred procedure
{ANY}
top
Remove the last n item(s).
has (x: ANY): BOOLEAN
effective function
{ANY}
top
Look for x using is_equal for comparison.
fast_has (x: ANY): BOOLEAN
effective function
{ANY}
top
Look for x using basic = for comparison.
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.
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.
is_equal_map (other: LINKED_LIST [E_]): BOOLEAN
effective function
{ANY}
top
Do both collections have the same lower, upper, and items?
same_items (other: COLLECTION[E_]): BOOLEAN
effective function
{ANY}
top
Do both collections have the same items?
move (lower_index: INTEGER_32, upper_index: INTEGER_32, distance: INTEGER_32)
effective procedure
{ANY}
top
Move range lower_index ..
manifest_semicolon_check: BOOLEAN
is False
constant attribute
{}
top
manifest_put (index: INTEGER_32, element: ANY)
deferred procedure
{}
top
enumerate: ENUMERATE[E_]
effective function
{ANY}
top
get_new_iterator: ITERATOR[E_]
frozen
effective function
{ANY}
top
for_each (action: PROCEDURE[TUPLE[TUPLE 1[E_]]])
effective procedure
{ANY}
top
Apply action to every item of Current.
for_all (test: FUNCTION[TUPLE[TUPLE 1[E_]]]): BOOLEAN
effective function
{ANY}
top
Do all items satisfy test?
exists (test: FUNCTION[TUPLE[TUPLE 1[E_]]]): BOOLEAN
effective function
{ANY}
top
Does at least one item satisfy test?
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.
out_in_tagged_out_memory
effective procedure
{ANY}
top
Append terse printable representation of current object in tagged_out_memory.
generation: INTEGER_32
writable attribute
{ANY}
top
next_generation
effective procedure
{}
top
do_all (action: ROUTINE[TUPLE[TUPLE 1[E_]]])
frozen
effective procedure
{ANY}
top
Apply action to every item of Current.
_inline_agent1 (a: ROUTINE[TUPLE[TUPLE 1[E_]]], e: E_)
frozen
effective procedure
{}
top
lower: INTEGER_32
deferred function
{ANY}
top
Minimum index.
upper: INTEGER_32
deferred function
{ANY}
top
Maximum index.
valid_index (i: INTEGER_32): BOOLEAN
effective function
{ANY}
top
True when i is valid (i.e., inside actual bounds).
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.
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.
manifest_make (needed_capacity: INTEGER_32)
effective procedure
{}
top
Manifest creation of a list of items of type E_.