LisaacTM Platform

LINKED_XOR_LIST


One Xor way linked list with internal automatic memorization of the last access .
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
mem_lnk_prev
mem_lnk_next
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_xor_list.li line #13

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_xor_list.li line #36

Section:
Public

Profile:
- SelfSELFcreate : SELF

Description:
Make an empty list;

Detail slot

first_link

.../base/collection/linked_xor_list.li line #17

Section:
LINKED2_LIST

Profile:
+ SelfSELFfirst_link : LINKED_XOR_NODEV)

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

last_link

.../base/collection/linked_xor_list.li line #20

Section:
LINKED2_LIST

Profile:
+ SelfSELFlast_link : LINKED_XOR_NODEV)

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

mem_idx

.../base/collection/linked_xor_list.li line #23

Section:
LINKED2_LIST

Profile:
+ SelfSELFmem_idx : INTEGER

mem_lnk

.../base/collection/linked_xor_list.li line #25

Section:
LINKED2_LIST

Profile:
+ SelfSELFmem_lnk : LINKED_XOR_NODEV)

mem_lnk_prev

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

Section:
LINKED2_LIST

Profile:
+ SelfSELFmem_lnk_prev : LINKED_XOR_NODEV)

mem_lnk_next

.../base/collection/linked_xor_list.li line #27

Section:
LINKED2_LIST

Profile:
+ SelfSELFmem_lnk_next : LINKED_XOR_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_xor_list.li line #42

Section:
Public

Profile:
- SelfSELFis_empty : BOOLEAN

Description:
Is collection empty ?
See also count.

add_first

.../base/collection/linked_xor_list.li line #44

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_xor_list.li line #66

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_xor_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_xor_list.li line #104

Section:
Public

Profile:
- SelfSELFremove_first 

Description:
Remove the first element of the collection.

See:
remove_last, remove, remove_head.

remove

.../base/collection/linked_xor_list.li line #131

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_xor_list.li line #151

Section:
Public

Profile:
- SelfSELFfirst : V

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

last

.../base/collection/linked_xor_list.li line #153

Section:
Public

Profile:
- SelfSELFlast : V

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

item

.../base/collection/linked_xor_list.li line #155

Section:
Public

Profile:
- SelfSELFitem   index : INTEGERV

Description:
Item at the corresponding index i.

See:
lower, upper, valid_index, put, swap

put to

.../base/collection/linked_xor_list.li line #163

Section:
Public

Profile:
- SelfSELFput   element : V  to   index : INTEGER

Description:
Make element the item at index i.

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

count

.../base/collection/linked_xor_list.li line #171

Section:
Public

Profile:
- SelfSELFcount : INTEGER

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

set_all_with

.../base/collection/linked_xor_list.li line #173

Section:
Public

Profile:
- SelfSELFset_all_with   v : V

Description:
Set all items with value v.

See:
set_slice_with.

copy

.../base/collection/linked_xor_list.li line #182

Section:
Public

Profile:
- SelfSELFcopy   other : SELF

Description:
Reinitialize by copying all the items of other.

Infix '=='

.../base/collection/linked_xor_list.li line #189

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_xor_list.li line #210

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_xor_list.li line #232

Section:
Public

Profile:
- SelfSELFindex_of   x : 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_xor_list.li line #245

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_xor_list.li line #270

Section:
Public

Profile:
- SelfSELFfast_index_of   x : 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_xor_list.li line #284

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_xor_list.li line #307

Section:
Public

Profile:
- SelfSELFclear 

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

See:
clear_all.

from_collection

.../base/collection/linked_xor_list.li line #324

Section:
Public

Profile:
- SelfSELFfrom_collection   model : COLLECTIONV)

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

slice to

.../base/collection/linked_xor_list.li line #360

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_xor_list.li line #378

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_xor_list.li line #395

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_xor_list.li line #411

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_xor_list.li line #422

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_xor_list.li line #441

Section:
Public

Profile:
- SelfSELFremove_last 

Description:
Remove the last item.

See:
remove_first, remove, remove_tail.

replace_all with

.../base/collection/linked_xor_list.li line #463

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_xor_list.li line #475

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_xor_list.li line #487

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