LisaacTM Platform

COLLECTION


Common abstract definition of a sequenceable collection of objects.
Such a collection is traversable using a simple INTEGER index from `lower' to `upper' using `item'. All COLLECTIONs are resizable thanks to `add_last' / `remove_last', `add_first' / `remove_first' as well as `add' / `remove' .


This abstraction provides feature to view a COLLECTION as a stack (as an example by using `add_last', `last', and `remove_last'). One can also use a COLLECTION as a queue (as an example, by using `add_last', `first' and `remove_first').


The Lisaac standard library provides five implementations of COLLECTION: ARRAY, FAST_ARRAY, LINKED_LIST and LINKED2_LIST.
Except for creations all implementations have exactly the same behavior. Switching from one implementation to another only change the memory used and the execution time (see header comment of ARRAY, FAST_ARRAY, LINKED_LIST and LINKED2_LIST for more details).

Inherit/Insert Summary
parent_traversable No developed.
 
Accessing:
item
Item at the corresponding index i.
 
Writing:
put to
Make element the item at index i.
swap with
Swap item at index i1 with item at index i2.
set_all_with
Set all items with value v.
set_slice to with
Set all items in range [lower_index .. upper_index] with v.
clear_all
Set every item to its default value. The count is not affected see also clear, all_default.
 
Adding:
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.
append_collection
Append other to Current.
copy_collection
Copy other to Current.
 
Modification:
force to
Make element the item at index, enlarging the collection if necessary (new bounds except index are initialized with default values).
copy
Reinitialize by copying all the items of other.
from_collection
Initialize the current object with the contents of model.
 
Removing:
remove_first
Remove the first element of the collection.
remove_head
Remove the n elements of the collection.
remove
Remove the item at position index. Followings items are shifted left by one position.
remove_last
Remove the last item.
remove_tail
Remove the last n item(s).
clear
Discard all items in order to make it is_empty.
 
Looking and Searching:
has
Look for x using equal for comparison.
fast_has
Look for x using basic = for comparison.
first_index_of
Give the index of the first occurrence of element using == for comparison. Answer upper + 1 when element is not inside.
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.
last_index_of
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.
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.
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.
fast_last_index_of
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.
 
Looking and comparison:
Infix '=='
Do both collections have the same lower, upper, and items? The basic = is used for comparison of items.
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.
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.
same_items
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]).
occurrences
Number of occurrences of element using equal for comparison.
fast_occurrences
Number of occurrences of element using basic = for comparison.
 
Printing:
fill_tagged_out_memory
 
High Level control Structure:
foreach
do_all
Apply action to every item of Self.
foreach while
Apply action to every item of Self while test is true
foreach until
Apply action to every item of Self until test is true
foreach only_if
is_all
for_all
Do all items satisfy test?
exists
Does at least one item satisfy test?
 
Traditionals features (in functional languages)
map
filter in
Filter all element which test element is true and put the result in other
filter
Filter all element which test element is true
filter_first
Filter first element which test element is true
fold_left with
fold left with function function beginning with element
fold_right with
fold left with function function beginning with element
merge with
Return the intersection between Self and other according to test function
 
Other features
unique
Remove every duplicated element in the collection Only the first duplicate will be kept
fast_unique
Remove every duplicated element in the collection Only the first duplicate will be kept
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.
move to by
Move range lower_index .. upper_index by distance positions. Negative distance moves towards lower indices. Free places get default values.
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.
reverse
Reverse the order of the elements.
 
Invariant.
[ -? { lower <= upper + 1 }; ];
Debug
inspect
 

Inherit/Insert Detail

parent_traversable

.../base/collection/low_level/collection.li line #31

Section:
Inherit

Profile:
- SelfSELFparent_traversable : TRAVERSABLEV)

Accessing:

item

.../base/collection/low_level/collection.li line #39

Section:
Public

Profile:
- SelfSELFitem   i : INTEGERV

Description:
Item at the corresponding index i.

See:
lower, upper, valid_index, put, swap

Writing:

put to

.../base/collection/low_level/collection.li line #55

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.

swap with

.../base/collection/low_level/collection.li line #69

Section:
Public

Profile:
- SelfSELFswap   i1 : INTEGER  with   i2 : INTEGER

Description:
Swap item at index i1 with item at index i2.

See:
item, put.

set_all_with

.../base/collection/low_level/collection.li line #88

Section:
Public

Profile:
- SelfSELFset_all_with   v : V

Description:
Set all items with value v.

See:
set_slice_with.

set_slice to with

.../base/collection/low_level/collection.li line #98

Section:
Public

Profile:
- SelfSELFset_slice   lower_index : INTEGER  to   upper_index : INTEGER  with   v : V

Description:
Set all items in range [lower_index .. upper_index] with v.

See:
set_all_with.

clear_all

.../base/collection/low_level/collection.li line #115

Section:
Public

Profile:
- SelfSELFclear_all 

Description:
Set every item to its default value. The count is not affected see also clear, all_default.

Adding:

add_first

.../base/collection/low_level/collection.li line #133

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/low_level/collection.li line #148

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/low_level/collection.li line #162

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.

append_collection

.../base/collection/low_level/collection.li line #180

Section:
Public

Profile:
- SelfSELFappend_collection   other : COLLECTIONV)

Description:
Append other to Current.

See:
add_last, add_first, add.

copy_collection

.../base/collection/low_level/collection.li line #196

Section:
Public

Profile:
- SelfSELFcopy_collection   other : COLLECTIONV)

Description:
Copy other to Current.

See:
copy.

Modification:

force to

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

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.

copy

.../base/collection/low_level/collection.li line #240

Section:
Public

Profile:
- SelfSELFcopy   other : SELF

Description:
Reinitialize by copying all the items of other.

from_collection

.../base/collection/low_level/collection.li line #246

Section:
Public

Profile:
- SelfSELFfrom_collection   model : COLLECTIONV)

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

Removing:

remove_first

.../base/collection/low_level/collection.li line #263

Section:
Public

Profile:
- SelfSELFremove_first 

Description:
Remove the first element of the collection.

See:
remove_last, remove, remove_head.

remove_head

.../base/collection/low_level/collection.li line #278

Section:
Public

Profile:
- SelfSELFremove_head   n : INTEGER

Description:
Remove the n elements of the collection.

See:
remove_tail, remove, remove_first.

remove

.../base/collection/low_level/collection.li line #294

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.

remove_last

.../base/collection/low_level/collection.li line #310

Section:
Public

Profile:
- SelfSELFremove_last 

Description:
Remove the last item.

See:
remove_first, remove, remove_tail.

remove_tail

.../base/collection/low_level/collection.li line #325

Section:
Public

Profile:
- SelfSELFremove_tail   n : INTEGER

Description:
Remove the last n item(s).

See:
remove_head, remove, remove_last.

clear

.../base/collection/low_level/collection.li line #341

Section:
Public

Profile:
- SelfSELFclear 

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

See:
clear_all.

Looking and Searching:

has

.../base/collection/low_level/collection.li line #356

Section:
Public

Profile:
- SelfSELFhas   x : VBOOLEAN

Description:
Look for x using equal for comparison.

See:
fast_has, index_of start, fast_index_of start.

fast_has

.../base/collection/low_level/collection.li line #364

Section:
Public

Profile:
- SelfSELFfast_has   x : VBOOLEAN

Description:
Look for x using basic = for comparison.

See:
has, fast_index_of start, index_of start.

first_index_of

.../base/collection/low_level/collection.li line #372

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.

index_of start

.../base/collection/low_level/collection.li line #402

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/low_level/collection.li line #418

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.

last_index_of

.../base/collection/low_level/collection.li line #437

Section:
Public

Profile:
- SelfSELFlast_index_of   element : VINTEGER

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

fast_first_index_of

.../base/collection/low_level/collection.li line #451

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.

fast_index_of start

.../base/collection/low_level/collection.li line #464

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/low_level/collection.li line #479

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.

fast_last_index_of

.../base/collection/low_level/collection.li line #499

Section:
Public

Profile:
- SelfSELFfast_last_index_of   element : VINTEGER

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

Looking and comparison:

Infix '=='

.../base/collection/low_level/collection.li line #517

Section:
Public

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

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.

Infix '~='

.../base/collection/low_level/collection.li line #532

Section:
Public

Profile:
- SelfSELF~= ' Right 60  other : COLLECTIONV) : BOOLEAN

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/low_level/collection.li line #546

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.

all_default

.../base/collection/low_level/collection.li line #560

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.

same_items

.../base/collection/low_level/collection.li line #570

Section:
Public

Profile:
- SelfSELFsame_items   other : COLLECTIONV) : BOOLEAN

Description:
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:
is_equal_map, is_equal.

occurrences

.../base/collection/low_level/collection.li line #599

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/low_level/collection.li line #611

Section:
Public

Profile:
- SelfSELFfast_occurrences   element : VINTEGER

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

See:
occurrences, index_of.

Printing:

fill_tagged_out_memory

.../base/collection/low_level/collection.li line #627

Section:
Public

Profile:
- SelfSELFfill_tagged_out_memory 

High Level control Structure:

foreach

.../base/collection/low_level/collection.li line #660

Section:
Public

Profile:
- SelfSELFforeach   action :{ V; }

do_all

.../base/collection/low_level/collection.li line #662

Section:
Public

Profile:
- SelfSELFdo_all   action :{ V; }

Description:
Apply action to every item of Self.

See:
for_all, exists.

foreach while

.../base/collection/low_level/collection.li line #672

Section:
Public

Profile:
- SelfSELFforeach   action :{ V; }  while   test :{ V;  BOOLEAN}

Description:
Apply action to every item of Self while test is true

foreach until

.../base/collection/low_level/collection.li line #684

Section:
Public

Profile:
- SelfSELFforeach   action :{ V; }  until   test :{ V;  BOOLEAN}

Description:
Apply action to every item of Self until test is true

foreach only_if

.../base/collection/low_level/collection.li line #696

Section:
Public

Profile:
- SelfSELFforeach   action :{ V; }  only_if   test :{ V;  BOOLEAN}

is_all

.../base/collection/low_level/collection.li line #705

Section:
Public

Profile:
- SelfSELFis_all   test :{ V;  BOOLEAN}BOOLEAN

for_all

.../base/collection/low_level/collection.li line #707

Section:
Public

Profile:
- SelfSELFfor_all   test :{ V;  BOOLEAN}BOOLEAN

Description:
Do all items satisfy test?

See:
do_all, exists.

exists

.../base/collection/low_level/collection.li line #723

Section:
Public

Profile:
- SelfSELFexists   test :{ V;  BOOLEAN}BOOLEAN

Description:
Does at least one item satisfy test?

See:
do_all, for_all.

Traditionals features (in functional languages)

map

.../base/collection/low_level/collection.li line #742

Section:
Public

Profile:
- SelfSELFmap   action :{ V; }SELF

filter in

.../base/collection/low_level/collection.li line #750

Section:
Public

Profile:
- SelfSELFfilter   test :{ V;  BOOLEAN}  in   other : SELF

Description:
Filter all element which test element is true and put the result in other

filter

.../base/collection/low_level/collection.li line #766

Section:
Public

Profile:
- SelfSELFfilter   test :{ V;  BOOLEAN}SELF

Description:
Filter all element which test element is true

filter_first

.../base/collection/low_level/collection.li line #774

Section:
Public

Profile:
- SelfSELFfilter_first   test :{ V;  BOOLEAN}V

Description:
Filter first element which test element is true

fold_left with

.../base/collection/low_level/collection.li line #792

Section:
Public

Profile:
- SelfSELFfold_left   function :{VV); }  with   element : VV

Description:
fold left with function function beginning with element

fold_right with

.../base/collection/low_level/collection.li line #802

Section:
Public

Profile:
- SelfSELFfold_right   function :{VV); }  with   element : VV

Description:
fold left with function function beginning with element

merge with

.../base/collection/low_level/collection.li line #813

Section:
Public

Profile:
- SelfSELFmerge   other : SELF  with   test :{VV);  BOOLEAN}SELF

Description:
Return the intersection between Self and other according to test function

Other features

unique

.../base/collection/low_level/collection.li line #834

Section:
Public

Profile:
- SelfSELFunique : SELF

Description:
Remove every duplicated element in the collection Only the first duplicate will be kept

fast_unique

.../base/collection/low_level/collection.li line #852

Section:
Public

Profile:
- SelfSELFfast_unique : SELF

Description:
Remove every duplicated element in the collection Only the first duplicate will be kept

replace_all with

.../base/collection/low_level/collection.li line #870

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/low_level/collection.li line #883

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.

move to by

.../base/collection/low_level/collection.li line #896

Section:
Public

Profile:
- SelfSELFmove   lower_index : INTEGER  to   upper_index : INTEGER  by   distance : INTEGER

Description:
Move range lower_index .. upper_index by distance positions. Negative distance moves towards lower indices. Free places get default values.

See:
slice, replace_all.

slice to

.../base/collection/low_level/collection.li line #928

Section:
Public

Profile:
- SelfSELFslice   min : INTEGER  to   max : 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

reverse

.../base/collection/low_level/collection.li line #954

Section:
Public

Profile:
- SelfSELFreverse 

Description:
Reverse the order of the elements.

Invariant.
[ -? { lower <= upper + 1 }; ];
Debug

inspect

.../base/collection/low_level/collection.li line #976

Section:
Public

Profile:
- SelfSELFinspect : STRING