home
wiki
classes/clusters list
class information
+
Point of view
TWO_WAY_LINKED_LIST
TWO_WAY_LINKED_LIST
ANY
ITERATOR_ON_TWO_WAY_LINKED_LIST
All features
class TWO_WAY_LINKED_LIST [E_]
Summary
top
Two way linked list with internal automatic memorization of the last access.
Direct parents
inherit list:
COLLECTION
insert list:
LINKED_COLLECTION
Class invariant
top
empty_status:
first_link
= Void implies
last_link
= Void and
upper
= 0 and
mem_idx
= 0 and
mem_lnk
= Void
not_empty_status:
first_link
/= Void implies
last_link
/= Void and
upper
> 0 and
mem_idx
> 0 and
mem_lnk
/= Void
valid_bounds:
lower <= upper + 1
Overview
top
creation features
make
Make an empty list
from_collection
(model:
TRAVERSABLE
[E_])
Initialize the current object with the contents of
model
.
exported features
first_link
:
TWO_WAY_LINKED_LIST_NODE
[E_]
Void when empty or gives access to the first element.
last_link
:
TWO_WAY_LINKED_LIST_NODE
[E_]
Void when empty or gives access to the last element.
mem_idx
:
INTEGER_32
mem_lnk
:
TWO_WAY_LINKED_LIST_NODE
[E_]
To speed up accessing,
mem_idx
and
mem_lnk
is the memory of the last access done.
make
Make an empty list
is_empty
:
BOOLEAN
Is collection empty ?
See also
count
.
add_first
(element: E_)
Add a new item in first position :
count
is increased by one and all other items are shifted right.
add_last
(element: E_)
Add a new item at the end :
count
is increased by one.
add
(element: E_, index:
INTEGER_32
)
Add a new
element
at rank
index
:
count
is increased by one and range [
index
..
upper
] is shifted right by one position.
remove_first
Remove the
first
element of the collection.
remove
(index:
INTEGER_32
)
Remove the item at position
index
.
first
: E_
The very
first
item.
last
: E_
The
last
item.
item
(index:
INTEGER_32
): E_
Item at the corresponding index
i
.
put
(element: E_, index:
INTEGER_32
)
Make
element
the item at index
i
.
count
:
INTEGER_32
Number of available indices.
set_all_with
(v: E_)
Set all items with value
v
.
copy
(other: TWO_WAY_LINKED_LIST [E_])
Reinitialize by copying all the items of
other
.
is_equal
(other: TWO_WAY_LINKED_LIST [E_]):
BOOLEAN
Do both collections have the same
lower
,
upper
, and items?
is_equal_map
(other: TWO_WAY_LINKED_LIST [E_]):
BOOLEAN
Do both collections have the same
lower
,
upper
, and items?
index_of
(x: E_, start_index:
INTEGER_32
):
INTEGER_32
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
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
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
Using basic
=
comparison, gives the index of the first occurrence of
element
at or before
start_index
.
clear_count
Discard all items (
is_empty
is True after that call).
clear_count_and_capacity
Discard all items (
is_empty
is True after that call).
from_collection
(model:
TRAVERSABLE
[E_])
Initialize the current object with the contents of
model
.
slice
(low:
INTEGER_32
, up:
INTEGER_32
): TWO_WAY_LINKED_LIST [E_]
New collection consisting of items at indexes in [
min
..
max
].
occurrences
(element: E_):
INTEGER_32
Number of occurrences of
element
using
is_equal
for comparison.
fast_occurrences
(element: E_):
INTEGER_32
Number of occurrences of
element
using basic
=
for comparison.
force
(element: E_, index:
INTEGER_32
)
Make
element
the item at
index
, enlarging the collection if necessary (new bounds except
index
are initialized with default values).
all_default
:
BOOLEAN
Do all items have their type's default value?
remove_last
Remove the
last
item.
replace_all
(old_value: E_, new_value: E_)
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_)
Replace all occurrences of the element
old_value
by
new_value
using basic
=
for comparison.
reverse
Reverse the order of the elements.
get_new_iterator
:
ITERATOR
[E_]
Accessing:
infix "@"
(i:
INTEGER_32
): E_
The infix notation which is actually just a synonym for
item
.
Writing:
swap
(i1:
INTEGER_32
, i2:
INTEGER_32
)
Swap item at index
i1
with item at index
i2
.
set_slice_with
(v: E_, lower_index:
INTEGER_32
, upper_index:
INTEGER_32
)
Set all items in range [
lower_index
..
upper_index
] with
v
.
clear_all
Set every item to its default value.
Adding:
append_collection
(other:
COLLECTION
[E_])
Append
other
to Current.
Removing:
remove_head
(n:
INTEGER_32
)
Remove the
n
elements of the collection.
remove_tail
(n:
INTEGER_32
)
Remove the last
n
item(s).
Looking and Searching:
has
(x: E_):
BOOLEAN
Look for
x
using
is_equal
for comparison.
fast_has
(x: E_):
BOOLEAN
Look for
x
using basic
=
for comparison.
first_index_of
(element: E_):
INTEGER_32
Give the index of the first occurrence of
element
using
is_equal
for comparison.
last_index_of
(element: E_):
INTEGER_32
Using
is_equal
for comparison, gives the index of the last occurrence of
element
at or before
upper
.
fast_first_index_of
(element: E_):
INTEGER_32
Give the index of the first occurrence of
element
using basic
=
for comparison.
fast_last_index_of
(element: E_):
INTEGER_32
Using basic
=
for comparison, gives the index of the last occurrence of
element
at or before
upper
.
Looking and comparison:
same_items
(other:
COLLECTION
[E_]):
BOOLEAN
Do both collections have the same items?
Printing:
fill_tagged_out_memory
Append a viewable information in
tagged_out_memory
in order to affect the behavior of
out
,
tagged_out
, etc.
Agents based features:
do_all
(action:
ROUTINE
[
TUPLE
[
TUPLE 1
[E_]]])
Apply
action
to every item of
Current
.
for_all
(test:
FUNCTION
[
TUPLE
[
TUPLE 1
[E_]]]):
BOOLEAN
Do all items satisfy
test
?
exists
(test:
FUNCTION
[
TUPLE
[
TUPLE 1
[E_]]]):
BOOLEAN
Does at least one item satisfy
test
?
Other features:
move
(lower_index:
INTEGER_32
, upper_index:
INTEGER_32
, distance:
INTEGER_32
)
Move range
lower_index
..
Indexing:
lower
:
INTEGER_32
Minimum index.
upper
:
INTEGER_32
Maximum index.
valid_index
(i:
INTEGER_32
):
BOOLEAN
True when
i
is valid (i.e., inside actual bounds).
first_link
:
TWO_WAY_LINKED_LIST_NODE
[E_]
writable attribute
top
Void when empty or gives access to the first element.
last_link
:
TWO_WAY_LINKED_LIST_NODE
[E_]
writable attribute
top
Void when empty or gives access to the last element.
mem_idx
:
INTEGER_32
writable attribute
top
mem_lnk
:
TWO_WAY_LINKED_LIST_NODE
[E_]
writable attribute
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
top
Make an empty list
ensure
count
= 0
is_empty
:
BOOLEAN
effective function
top
Is collection empty ?
See also
count
.
ensure
definition:
Result = count = 0
add_first
(element: E_)
effective procedure
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
upper
= 1 + old
upper
first = element
count = 1 + old count
lower = old lower
upper = 1 + old upper
add_last
(element: E_)
effective procedure
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
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)
ensure
item(index) = element
count = 1 + old count
upper = 1 + old upper
remove_first
effective procedure
top
Remove the
first
element of the collection.
See also
remove_last
,
remove
,
remove_head
.
require
not is_empty
ensure
count = old count - 1
lower = old lower + 1 xor upper = old upper - 1
remove
(index:
INTEGER_32
)
effective procedure
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)
ensure
count = old count - 1
upper = old upper - 1
first
: E_
effective function
top
The very
first
item.
See also
last
,
item
.
require
not is_empty
ensure
definition:
Result = item(lower)
last
: E_
effective function
top
The
last
item.
See also
first
,
item
.
require
not is_empty
ensure
definition:
Result = item(upper)
item
(index:
INTEGER_32
): E_
effective function
top
Item at the corresponding index
i
.
See also
lower
,
upper
,
valid_index
.
require
valid_index(index)
put
(element: E_, index:
INTEGER_32
)
effective procedure
top
Make
element
the item at index
i
.
See also
lower
,
upper
,
valid_index
,
item
,
swap
,
force
.
require
valid_index(index)
ensure
item(index) = element
count = old count
count
:
INTEGER_32
effective function
top
Number of available indices.
See also
is_empty
,
lower
,
upper
.
ensure
definition:
Result = upper - lower + 1
set_all_with
(v: E_)
effective procedure
top
Set all items with value
v
.
See also
set_slice_with
.
ensure
count = old count
copy
(other: TWO_WAY_LINKED_LIST [E_])
effective procedure
top
Reinitialize by copying all the items of
other
.
require
same_dynamic_type(other)
ensure
is_equal(other)
is_equal
(other: TWO_WAY_LINKED_LIST [E_]):
BOOLEAN
effective function
top
Do both collections have the same
lower
,
upper
, and items?
The basic
=
is used for comparison of items.
See also
is_equal_map
,
same_items
.
require
other /= Void
ensure
Result implies lower = other.lower and upper = other.upper
commutative:
generating_type = other.generating_type implies Result = other.is_equal(Current)
is_equal_map
(other: TWO_WAY_LINKED_LIST [E_]):
BOOLEAN
effective function
top
Do both collections have the same
lower
,
upper
, and items?
Feature
is_equal
is used for comparison of items.
See also
is_equal
,
same_items
.
ensure
Result implies lower = other.lower and upper = other.upper
index_of
(x: E_, start_index:
INTEGER_32
):
INTEGER_32
effective function
top
Using
is_equal
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
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
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)
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
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
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)
ensure
Result.in_range(lower - 1, start_index)
valid_index(Result) implies item(Result) = element
clear_count
effective procedure
top
Discard all items (
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
.
ensure
upper
= 0
is_empty:
count = 0
clear_count_and_capacity
effective procedure
top
Discard all items (
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
.
ensure
upper
= 0
is_empty:
count = 0
from_collection
(model:
TRAVERSABLE
[E_])
effective procedure
top
Initialize the current object with the contents of
model
.
require
model /= Void
useful_work:
model /= Current
ensure
count = model.count
slice
(low:
INTEGER_32
, up:
INTEGER_32
): TWO_WAY_LINKED_LIST [E_]
effective function
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
ensure
same_dynamic_type(Result)
Result.count = up - low + 1
Result.lower = lower
occurrences
(element: E_):
INTEGER_32
effective function
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
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
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
ensure
upper = index.max(old upper)
item(index) = element
all_default
:
BOOLEAN
effective function
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
top
Remove the
last
item.
See also
remove_first
,
remove
,
remove_tail
.
require
not is_empty
ensure
count = old count - 1
upper = old upper - 1
replace_all
(old_value: E_, new_value: E_)
effective procedure
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
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
reverse
effective procedure
top
Reverse the order of the elements.
ensure
count = old count
get_new_iterator
:
ITERATOR
[E_]
effective function
top
ensure
Result /= Void
infix "@"
(i:
INTEGER_32
): E_
frozen
effective function
top
The infix notation which is actually just a synonym for
item
.
See also
item
.
require
valid_index
(i)
ensure
definition:
Result =
item
(i)
swap
(i1:
INTEGER_32
, i2:
INTEGER_32
)
effective procedure
top
Swap item at index
i1
with item at index
i2
.
See also
item
,
put
.
require
valid_index
(i1)
valid_index
(i2)
ensure
item
(i1) = old
item
(i2)
item
(i2) = old
item
(i1)
count
= old
count
set_slice_with
(v: E_, lower_index:
INTEGER_32
, upper_index:
INTEGER_32
)
effective procedure
top
Set all items in range [
lower_index
..
upper_index
] with
v
.
See also
set_all_with
.
require
lower_index <= upper_index
valid_index
(lower_index)
valid_index
(upper_index)
ensure
count
= old
count
clear_all
effective procedure
top
Set every item to its default value.
The
count
is not affected.
See also
clear
,
all_default
.
ensure
stable_upper:
upper
= old
upper
stable_lower:
lower
= old
lower
all_default
append_collection
(other:
COLLECTION
[E_])
effective procedure
top
Append
other
to Current.
See also
add_last
,
add_first
,
add
.
require
other /= Void
ensure
count
= other.
count
+ old
count
remove_head
(n:
INTEGER_32
)
deferred procedure
top
Remove the
n
elements of the collection.
See also
remove_tail
,
remove
,
remove_first
.
require
n > 0 and n <=
count
ensure
count
= old
count
- n
lower
= old
lower
+ n xor
upper
= old
upper
- n
remove_tail
(n:
INTEGER_32
)
deferred procedure
top
Remove the last
n
item(s).
See also
remove_head
,
remove
,
remove_last
.
require
n > 0 and n <=
count
ensure
count
= old
count
- n
upper
= old
upper
- n
has
(x: E_):
BOOLEAN
effective function
top
Look for
x
using
is_equal
for comparison.
See also
fast_has
,
index_of
,
fast_index_of
.
fast_has
(x: E_):
BOOLEAN
effective function
top
Look for
x
using basic
=
for comparison.
See also
has
,
fast_index_of
,
index_of
.
first_index_of
(element: E_):
INTEGER_32
deferred function
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
definition:
Result =
index_of
(element,
lower
)
last_index_of
(element: E_):
INTEGER_32
effective function
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_first_index_of
(element: E_):
INTEGER_32
deferred function
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
definition:
Result =
fast_index_of
(element,
lower
)
fast_last_index_of
(element: E_):
INTEGER_32
effective function
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
)
same_items
(other:
COLLECTION
[E_]):
BOOLEAN
effective function
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 yeld True with
Current
indexed in range [1..2] and
other
indexed in range [2..3]).
See also
is_equal_map
,
is_equal
.
require
other /= Void
ensure
Result implies
count
= other.
count
fill_tagged_out_memory
frozen
effective procedure
top
Append a viewable information in
tagged_out_memory
in order to affect the behavior of
out
,
tagged_out
, etc.
do_all
(action:
ROUTINE
[
TUPLE
[
TUPLE 1
[E_]]])
effective procedure
top
Apply
action
to every item of
Current
.
See also
for_all
,
exists
.
require
action /= Void
for_all
(test:
FUNCTION
[
TUPLE
[
TUPLE 1
[E_]]]):
BOOLEAN
effective function
top
Do all items satisfy
test
?
See also
do_all
,
exists
.
require
test /= Void
exists
(test:
FUNCTION
[
TUPLE
[
TUPLE 1
[E_]]]):
BOOLEAN
effective function
top
Does at least one item satisfy
test
?
See also
do_all
,
for_all
.
require
test /= Void
move
(lower_index:
INTEGER_32
, upper_index:
INTEGER_32
, distance:
INTEGER_32
)
effective procedure
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
lower_index <= upper_index
valid_index
(lower_index)
valid_index
(lower_index + distance)
valid_index
(upper_index)
valid_index
(upper_index + distance)
ensure
count
= old
count
lower
:
INTEGER_32
deferred function
top
Minimum index.
See also
upper
,
valid_index
,
item
.
upper
:
INTEGER_32
deferred function
top
Maximum index.
See also
lower
,
valid_index
,
item
.
valid_index
(i:
INTEGER_32
):
BOOLEAN
effective function
top
True when
i
is valid (i.e., inside actual bounds).
See also
lower
,
upper
,
item
.
ensure
definition:
Result =
lower
<= i and i <=
upper