Next: data.priority-map
- Priority map, Previous: data.ideque
- Immutable deques, Up: Library modules - Utilities [Contents][Index]
data.imap
- Immutable mapThis module provides a immutable data structure with O(log n) access and update operations (here, update means to return a new structure with requested changes). The current implementation is based on the functional red-black tree.
Although lists and alists are useful for stack-like immutable
operations, where you can add and remove items to the head of
existing data without modifying them, they require O(n) access time
and sometimes you need better one. The <imap>
object
provides O(log n) access, in exchange of O(log n) insertion and
deletion.
{data.imap}
Metaclass of <imap>
.
{data.imap}
Immutable map class. An instance of <imap-meta>
.
Inherits <ordered-dictionary>
, conforms dictionary protocol
except mutating operators (see gauche.dictionary
- Dictionary framework).
As a sequence, you can access key-value
pairs in increasing order of keys.
{data.imap}
Creates a new empty immutable map. Without arguments,
default-comparator
is used to compare keys. To give a
specific comparator, use the second form; the comparator
argument should have comparison procedure.
For the details of comparators, see Basic comparators.
The third form creates a key comparator from a equality
predicate key=? and less-than predicate key<?
,
both must accept two keys. This interface is consistent with
tree-map
(see Treemaps).
{data.imap}
Creates and returns an immutable map containing
key-value associations given by an assoc-list alist.
This may be a bit more efficient than creating an empty map with
make-imap
and populates it with imap-put
one by one.
The comparator argument specifies how to compare the keys.
It must have comparison procedure. If omitted, default-comparator
is used. See Basic comparators, for the details.
The third form creates a key comparator from a equality
predicate key=? and less-than predicate key<?
,
both must accept two keys.
(define m (alist->imap '((a . 1) (b . 2)))) (imap-get m 'a) ⇒ 1 (imap-get m 'b) ⇒ 2
{data.imap} Returns a new immutable map with the same content (and the same comparator) as tree-map.
{data.imap}
Returns #t
if obj is an immutable map,
#f
otherwise.
{data.imap}
Returns #t
if an immutable map immap is empty,
#f
otherwise.
{data.imap}
Returns #t
if key exists in an immutable map immap.
{data.imap} Returns the value associated with key in an immutable map immap. If immap doesn’t have key, default is returned when provided, otherwise an error is signalled.
{data.imap} Returns a new immutable map where association of key to val is added to (or replaced in) an immutable map immap. This operation is O(log n).
(define m1 (alist->imap '((a . 1) (b . 2)))) (define m2 (imap-put m1 'a 3)) (imap-get m2 'a) ⇒ 3 (imap-get m1 'a) ⇒ 1 ; not affected
{data.imap} Returns a new immutable map where key is removed from immap. If immap doesn’t have key, returned map has the same content as immap.
(define m1 (alist->imap '((a . 1) (b . 2)))) (define m2 (imap-delete m1 'a)) (imap-get m2 'a #f) ⇒ #f (imap-get m1 'a) ⇒ 1 ; not affected
Next: data.priority-map
- Priority map, Previous: data.ideque
- Immutable deques, Up: Library modules - Utilities [Contents][Index]