Storage: object collections
How to use the "storage" cluster
This cluster provides the main collection abstractions and their
implementations. This document provides a few hints that may help
choosing the most relevant data structure.
Collections
Collections are linear sequences of objects. They are traversable by
either using an index (an INTEGER between lower
and upper) or an iterator.
The standard library implementations are:
- FAST_ARRAY: a random
accessible array of object; lower is zero.
- ARRAY: a random accessible array
of object with a variable lower bound (hence just a little
bit slower
than FAST_ARRAY)
- RING_ARRAY: a random
accesisble array with variable bounds and optimized for additions
and removals at both ends (used
for QUEUE implementation)
- LINKED_LIST: a collection
of objects linked together; random access is slower but insertion
in the middle is faster.
- TWO_WAY_LINKED_LIST:
the same but objects are linked both forward and backward thus
allowing efficient iteration in both directions.
Multi-dimentsion collections
COLLECTION2
and COLLECTION3 provide similar
facilities for two- and three-dimension object collections.
Maps
Maps provide indexed collections:
access to object values using object keys.
The standard library implementations are:
- HASHED_DICTIONARY: the
classical hash table. The keys must
be HASHABLE. The capacity of
those dictionaries is always a prime number; collisions are resolved
by linking together the objects with the same hash code (module the
table capacity). Therefore a hashed dictionary may contain more
elements than its capacity!
EST_HASHED_DICTIONARY
provides the same data structure but requires an external agent to
provide the hash code of a key (therefore alleviating the need for
the key to be HASHABLE).
- PYTHON_DICTIONARY:
another implementation of hash tables, using Python's algorithm. The
keys must be HASHABLE. The
capacity is exactly what it says: the number of elements may not
exceed the capacity. Collisions are resolved by spreading the
elements in the table's array. There are no linked lists, no
reference nodes, therefore this implementation is a bit less memory
hungry. The capacity is always a power of 2.
EXT_PYTHON_DICTIONARY
provides the same data structure but requires an external agent to
provide the hash code of a key (therefore alleviating the need for
the key to be HASHABLE).
- AVL_DICTIONARY: the
objects are distributed in an AVL
tree using COMPARABLE
keys. Because the elements are linked in a tree, there is no
capacity (it is meaningless).
EXT_AVL_DICTIONARY
provides the same data structure but requires an external agent to
compare two keys (therefore alleviating the need for the key to
be COMPARABLE).
- ZIP is just a pair
of collections with the
same count. One collection is the list of keys, the other is
the list of values.
- ENUMERATE is just a collection
with the object indices as key.
Sets
Sets of objects have unique occurrences of each object. Mathematical
set operators are available.
The standard library implementations are:
Repositories
A repository is a collection
of STORABLE objects. The aim of
this structure is to make objects persistent.
The standard library implementations are:
See
also: REPOSITORY_TRANSIENT
to register objects that must not be persisted.