Next: data.sparse
- Sparse data containers, Previous: data.ring-buffer
- Ring buffer, Up: Library modules - Utilities [Contents][Index]
data.skew-list
- Skew binary random-access listsThis module implements skew binary random-access list (we call it skew-list for short). It’s an immutable data structure that has properties of both list and vector; constant time to take the first element (car) and append an element in front of existing one (cons), O(log n) to take the rest of the elements (cdr), and O(log n) for indexed access, wher n is the number of elements.
A skew-list is always ’proper’; that is, it is either an empty
skew-list (skew-list-null
), or an object appended in front
of a skew-list.
{data.skew-list} The class for skew-lists.
It inherits <sequence>
and implements the sequence protocol
(see gauche.sequence
- Sequence framework).
{data.skew-list}
Returns #t
iff obj is a skew-list.
{data.skew-list}
The argument must be a skew list. Returns #t
iff sl
is an empty skew list.
{data.skew-list} An empty skew list.
{data.skew-list} Returns a new skew-list which has obj prepended to a skew-list sl. O(1) operation.
{data.skew-list} Returns the first element of a skew-list sl. O(1) operation. An error is raised when sl is empty.
{data.skew-list} Returns a new skew-list that containts elements in sl but the first one. O(log n) operation. An error is raised when sl is empty.
{data.skew-list} Returns the k-th element of a skew-list sl. O(log n) operation. If k points past the range of sl, fallback is returned if it is given, or an error is signaled.
Sicne a skew-list is also a sequence, you can use generic ref
as well
(see gauche.sequence
- Sequence framework).
{data.skew-list} Returns a new skew-list which is the same as sl except the k-th element is replaced with obj. The argument sl remains intact. O(log n) operation.
It is an error if k points beyond the last element of sl.
{data.skew-list} Returns an integer length of a skew-list sl. O(log n) operation.
Sicne a skew-list is also a sequence, you can use generic size-of
as well
(see gauche.sequence
- Sequence framework).
{data.skew-list}
Returns #t
iff the length of a skew-list sl is less than
or equal to n. It is more efficient than calculating
the total length and compares with n.
{data.skew-list} Returns a new skew-list which contains elements in lis, with the same order. It is an error if lis is not a proper list.
Sicne a skew-list is also a sequence, you can use generic coerce-to
as well (see gauche.sequence
- Sequence framework).
{data.skew-list} The argument lis may be a dotted list (but can’t be circular). Returns two values: a new skew-list which contains elements in lis except the last cdr of it, and the last cdr of lis.
{data.skew-list} Returns a new list that contains all the elements in a skew-list sl, with the same order.
Sicne a skew-list is also a sequence, you can use generic coerce-to
as well (see gauche.sequence
- Sequence framework.
{data.skew-list} Returns a new generator that traverses a skew-list sl.
{data.skew-list} Converts a skew-list sl to a lazy sequence.
{data.skew-list} Returns a new skew-list of the first k elements and the elements except the first k elements, respectively.
{data.skew-list}
Returns two values, the result of (skew-list-take sl k)
and (skew-list-drop sl k)
, but more efficiently.
{data.skew-list} Returns a skew-list which is a concatenation of all the given skew-lists.
{data.skew-list} Like fold on a list.
Sicne a skew-list is also a sequence, you can use generic fold
as well (see gauche.sequence
- Sequence framework.
{data.skew-list} Returns a skew list, each element of which is the result of applying proc on the element of sl. The order of application of proc is not specified.
NB: If you want to map over multiple skew-lists, you can use generic
map
(see gauche.sequence
- Sequence framework). The skew-list-map
employs
optimization that’s specific to one-argument case.
Next: data.sparse
- Sparse data containers, Previous: data.ring-buffer
- Ring buffer, Up: Library modules - Utilities [Contents][Index]