LisaacTM Platform

LINKED_LIST


One way linked list with internal automatic memorization of the last access.
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 consumming (also consider LINKED2_LIST).
Inherit/Insert Summary
parent_linked_collection
parent_collection No developed.
 
Constructor Summary
create
Make an empty list;
 
Slot Summary
first_link
NULL when empty or gives access to the first element.
last_link
NULL when empty or gives access to the last element.
mem_idx
mem_lnk
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 NULL as well as mem_lnk and mem_idx is 0;
is_empty
Is collection empty ?
See also count.
add_first
Add a new item in first position : count is increased by one and all other items are shifted right.
add_last
Add a new item at the end : count is increased by one.
add to
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
Remove the item at position index. Followings items are shifted left by one position.
first
The very first item.
See also last, item.
last
The last item.
See also first, item.
item
Item at the corresponding index i.
put to
Make element the item at index i.
count
Number of available indices.
See also is_empty, lower, upper.
set_all_with
Set all items with value v.
copy
Reinitialize by copying all the items of other.
Infix '=='
Do both collections have the same lower, upper, and items? The basic = is used for comparison of items.
is_equal_map
Do both collections have the same lower, upper, and items? Feature == is used for comparison of items.
index_of start
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.
reverse_index_of start
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.
fast_index_of start
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.
fast_reverse_index_of start
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.
clear
Discard all items in order to make it is_empty.
from_collection
Initialize the current object with the contents of model.
slice to
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.
occurrences
Number of occurrences of element using equal for comparison.
fast_occurrences
Number of occurrences of element using basic = for comparison.
force to
Make element the item at index, enlarging the collection if necessary (new bounds except index are initialized with default values).
all_default
Do all items have their type's default value? Note: for non NULL items, the test is performed with the is_default predicate.
remove_last
Remove the last item.
replace_all with
Replace all occurrences of the element old_value by new_value using equal for comparison.
fast_replace_all with
Replace all occurrences of the element old_value by new_value using operator = for comparison.
reverse
Reverse the order of the elements.
lower
Lower index bound is frozen. Minimum index.
See also upper, valid_index, item.
upper
Memorized upper index bound. Maximum index.
See also lower, valid_index, item.
make
Make an empty list
remove_head
Remove the n elements of the collection.
remove_tail
Remove the last n item(s).
first_index_of
Give the index of the first occurrence of element using == for comparison. Answer upper + 1 when element is not inside.
fast_first_index_of
Give the index of the first occurrence of element using basic = for comparison. Answer upper + 1 when element is not inside.
 
Implement manifest generic creation.
manifest_make
Manifest creation of a list of items of type E.
manifest_put to
 

Inherit/Insert Detail

parent_linked_collection

.../base/collection/linked_list.li line #22

Section:
Inherit

Profile:
+ SelfSELFparent_linked_collection :Expanded  LINKED_COLLECTIONV)

parent_collection

.../base/collection/low_level/linked_collection.li line #12

Section:
Inherit

Profile:
- SelfSELFparent_collection : COLLECTIONV)

Constructor Detail

create

.../base/collection/linked_list.li line #42

Section:
Public

Profile:
- SelfSELFcreate : SELF

Description:
Make an empty list;

Detail slot

first_link

.../base/collection/linked_list.li line #26

Section:
LINKED_LIST

Profile:
+ SelfSELFfirst_link : LINKED_LIST_NODEV)

Description:
NULL when empty or gives access to the first element.

last_link

.../base/collection/linked_list.li line #29

Section:
LINKED_LIST

Profile:
+ SelfSELFlast_link : LINKED_LIST_NODEV)

Description:
NULL when empty or gives access to the last element.

mem_idx

.../base/collection/linked_list.li line #32

Section:
LINKED_LIST

Profile:
+ SelfSELFmem_idx : INTEGER

mem_lnk

.../base/collection/linked_list.li line #33

Section:
LINKED_LIST

Profile:
+ SelfSELFmem_lnk : LINKED_LIST_NODEV)

Description:
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 NULL as well as mem_lnk and mem_idx is 0;

is_empty

.../base/collection/linked_list.li line #51

Section:
Public

Profile:
- SelfSELFis_empty : BOOLEAN

Description:
Is collection empty ?
See also count.

add_first

.../base/collection/linked_list.li line #53

Section:
Public

Profile:
- SelfSELFadd_first   element : V

Description:
Add a new item in first position : count is increased by one and all other items are shifted right.

See:
add_last, first, last, add.

add_last

.../base/collection/linked_list.li line #68

Section:
Public

Profile:
- SelfSELFadd_last   element : V

Description:
Add a new item at the end : count is increased by one.

See:
add_first, last, first, add.

add to

.../base/collection/linked_list.li line #85

Section:
Public

Profile:
- SelfSELFadd   element : V  to   index : INTEGER

Description:
Add a new element at rank index : count is increased by one and range [index .. upper] is shifted right by one position.

See:
add_first, add_last, append_collection.

remove_first

.../base/collection/linked_list.li line #102

Section:
Public

Profile:
- SelfSELFremove_first 

Description:
Remove the first element of the collection.

See:
remove_last, remove, remove_head.

remove

.../base/collection/linked_list.li line #121

Section:
Public

Profile:
- SelfSELFremove   index : INTEGER

Description:
Remove the item at position index. Followings items are shifted left by one position.

See:
remove_first, remove_head, remove_tail, remove_last.

first

.../base/collection/linked_list.li line #138

Section:
Public

Profile:
- SelfSELFfirst : V

Description:
The very first item.
See also last, item.

last

.../base/collection/linked_list.li line #140

Section:
Public

Profile:
- SelfSELFlast : V

Description:
The last item.
See also first, item.

item

.../base/collection/linked_list.li line #142

Section:
Public

Profile:
- SelfSELFitem   i : INTEGERV

Description:
Item at the corresponding index i.

See:
lower, upper, valid_index, put, swap

put to

.../base/collection/linked_list.li line #150

Section:
Public

Profile:
- SelfSELFput   element : V  to   i : INTEGER

Description:
Make element the item at index i.

See:
lower, upper, valid_index, item, swap, force.

count

.../base/collection/linked_list.li line #158

Section:
Public

Profile:
- SelfSELFcount : INTEGER

Description:
Number of available indices.
See also is_empty, lower, upper.

set_all_with

.../base/collection/linked_list.li line #160

Section:
Public

Profile:
- SelfSELFset_all_with   v : V

Description:
Set all items with value v.

See:
set_slice_with.

copy

.../base/collection/linked_list.li line #167

Section:
Public

Profile:
- SelfSELFcopy   other : SELF

Description:
Reinitialize by copying all the items of other.

Infix '=='

.../base/collection/linked_list.li line #172

Section:
Public

Profile:
- SelfSELF== ' Right 60  other : SELFBOOLEAN

Description:
Do both collections have the same lower, upper, and items? The basic = is used for comparison of items.

See:
is_equal_map, same_items.

is_equal_map

.../base/collection/linked_list.li line #191

Section:
Public

Profile:
- SelfSELFis_equal_map   other : SELFBOOLEAN

Description:
Do both collections have the same lower, upper, and items? Feature == is used for comparison of items.

See:
==, same_items.

index_of start

.../base/collection/linked_list.li line #211

Section:
Public

Profile:
- SelfSELFindex_of   element : V  start   start_index : INTEGERINTEGER

Description:
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:
fast_index_of, reverse_index_of, first_index_of.

reverse_index_of start

.../base/collection/linked_list.li line #223

Section:
Public

Profile:
- SelfSELFreverse_index_of   element : V  start   start_index : INTEGERINTEGER

Description:
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:
fast_reverse_index_of, last_index_of, index_of.

fast_index_of start

.../base/collection/linked_list.li line #249

Section:
Public

Profile:
- SelfSELFfast_index_of   element : V  start   start_index : INTEGERINTEGER

Description:
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:
index_of, fast_reverse_index_of, fast_first_index_of.

fast_reverse_index_of start

.../base/collection/linked_list.li line #261

Section:
Public

Profile:
- SelfSELFfast_reverse_index_of   element : V  start   start_index : INTEGERINTEGER

Description:
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:
reverse_index_of, fast_index_of, fast_last_index_of.

clear

.../base/collection/linked_list.li line #287

Section:
Public

Profile:
- SelfSELFclear 

Description:
Discard all items in order to make it is_empty.

See:
clear_all.

from_collection

.../base/collection/linked_list.li line #301

Section:
Public

Profile:
- SelfSELFfrom_collection   model : COLLECTIONV)

Description:
Initialize the current object with the contents of model.

slice to

.../base/collection/linked_list.li line #335

Section:
Public

Profile:
- SelfSELFslice   low : INTEGER  to   up : INTEGERSELF

Description:
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:
from_collection, move, replace_all.

Require:
lower inferior or equal to min

Require:
max inferior or equal to upper

Require:
min inferior or equal to max + 1

Ensure:
Self is same dynamic type of Result

Ensure:
Result size is equal to max - min + 1

Ensure:
Result first element index is same as Self first element index

occurrences

.../base/collection/linked_list.li line #352

Section:
Public

Profile:
- SelfSELFoccurrences   element : VINTEGER

Description:
Number of occurrences of element using equal for comparison.

See:
fast_occurrences, index_of.

fast_occurrences

.../base/collection/linked_list.li line #367

Section:
Public

Profile:
- SelfSELFfast_occurrences   element : VINTEGER

Description:
Number of occurrences of element using basic = for comparison.

See:
occurrences, index_of.

force to

.../base/collection/linked_list.li line #381

Section:
Public

Profile:
- SelfSELFforce   element : V  to   index : INTEGER

Description:
Make element the item at index, enlarging the collection if necessary (new bounds except index are initialized with default values).

See:
put, item, swap.

all_default

.../base/collection/linked_list.li line #390

Section:
Public

Profile:
- SelfSELFall_default : BOOLEAN

Description:
Do all items have their type's default value? Note: for non NULL items, the test is performed with the is_default predicate.

See:
clear_all.

remove_last

.../base/collection/linked_list.li line #408

Section:
Public

Profile:
- SelfSELFremove_last 

Description:
Remove the last item.

See:
remove_first, remove, remove_tail.

replace_all with

.../base/collection/linked_list.li line #426

Section:
Public

Profile:
- SelfSELFreplace_all   old_value : V  with   new_value : V

Description:
Replace all occurrences of the element old_value by new_value using equal for comparison.

See:
fast_replace_all, move.

fast_replace_all with

.../base/collection/linked_list.li line #436

Section:
Public

Profile:
- SelfSELFfast_replace_all   old_value : V  with   new_value : V

Description:
Replace all occurrences of the element old_value by new_value using operator = for comparison.

See:
replace_all, move.

reverse

.../base/collection/linked_list.li line #445

Section:
Public

Profile:
- SelfSELFreverse 

Description:
Reverse the order of the elements.

lower

.../base/collection/low_level/linked_collection.li line #16

Section:
Public

Profile:
- SelfSELFlower : INTEGER

Description:
Lower index bound is frozen. Minimum index.
See also upper, valid_index, item.

upper

.../base/collection/low_level/linked_collection.li line #19

Section:
Public

Profile:
+ SelfSELFupper : INTEGER

Description:
Memorized upper index bound. Maximum index.
See also lower, valid_index, item.

make

.../base/collection/low_level/linked_collection.li line #30

Section:
Public

Profile:
- SelfSELFmake 

Description:
Make an empty list

remove_head

.../base/collection/low_level/linked_collection.li line #36

Section:
Public

Profile:
- SelfSELFremove_head   n : INTEGER

Description:
Remove the n elements of the collection.

See:
remove_tail, remove, remove_first.

remove_tail

.../base/collection/low_level/linked_collection.li line #46

Section:
Public

Profile:
- SelfSELFremove_tail   n : INTEGER

Description:
Remove the last n item(s).

See:
remove_head, remove, remove_last.

first_index_of

.../base/collection/low_level/linked_collection.li line #56

Section:
Public

Profile:
- SelfSELFfirst_index_of   element : VINTEGER

Description:
Give the index of the first occurrence of element using == for comparison. Answer upper + 1 when element is not inside.

Parameter:
element : element to search.

Require:
element not null.

Ensure:
Very good fonction

See:
fast_first_index_of, index_of start, last_index_of, reverse_index_of.

Description en francais:
Donne l'index de la premiere occurence de element en utilisant == pour la comparaison. Renvoi upper + 1 lorsque element est absent.

Necessite:
element pas null.

Voir:
fast_first_index_of, index_of, last_index_of, reverse_index_of.

fast_first_index_of

.../base/collection/low_level/linked_collection.li line #61

Section:
Public

Profile:
- SelfSELFfast_first_index_of   element : VINTEGER

Description:
Give the index of the first occurrence of element using basic = for comparison. Answer upper + 1 when element is not inside.

See:
first_index_of, last_index_of, fast_last_index_of.

Implement manifest generic creation.

manifest_make

.../base/collection/low_level/linked_collection.li line #70

Section:
Public

Profile:
- SelfSELFmanifest_make   needed_capacity : INTEGER

Description:
Manifest creation of a list of items of type E.

manifest_put to

.../base/collection/low_level/linked_collection.li line #76

Section:
Public

Profile:
- SelfSELFmanifest_put   index : INTEGER  to   element : V