For Gauche 0.9.5


Next: , Previous: , Up: Library modules - Utilities   [Contents][Index]

12.10 data.imap - Immutable map

Module: data.imap

This 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.

Class: <imap-meta>

Metaclass of <imap>.

Class: <imap>

Immutable map class. An instance of <imap-meta>.

Inherits <ordered-dictionary>, conforms dictionary protocol except mutating operators (see Dictionary framework). As a sequence, you can access key-value pairs in increasing order of keys.

Function: make-imap
Function: make-imap comparator
Function: make-imap key=? key<?

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).

Function: alist->imap alist
Function: alist->imap alist comparator
Function: alist->imap alist key=? key<?

Creates a new empty immutable map, populates it with key-value association list alist, and returns it. 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
Function: tree-map->imap tree-map

Returns a new immutable map with the same content (and the same comparator) as tree-map.

Function: imap? obj

Returns #t if obj is an immutable map, #f otherwise.

Function: imap-empty? immap

Returns #t if an immutable map immap is empty, #f otherwise.

Function: imap-exists? immap key

Returns #t if key exists in an immutable map immap.

Function: imap-get immap key :optional default

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.

Function: imap-put immap key val

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
Function: imap-delete immap key

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
Function: imap-min immap
Function: imap-max immap

Returns a pair of key and value with the minimum or maximum key in immap, respectively. If immap is empty, #f is returned.


Next: , Previous: , Up: Library modules - Utilities   [Contents][Index]