Next: Bitwise operations, Previous: Fixnums, Up: Library modules - SRFIs [Contents][Index]

`srfi-146`

- Mappings and hashmapsSRFI-146 defines a *mapping* data structure, which is
a conceptually immutable collection of associations of key and value.
Mappings are assumed to be built on top of treemaps (and indeed,
Gauche uses built-in `<tree-map>`

as mappings) but the API
abstracts the implementation.

SRFI-146 also defines a submodlue `(srfi-146 hash)`

which
provides hashmaps,
whose API is functionally almost identical to mappings but
it assumes to be built on top of hashtables.

“Conceptually immutable” means that the mappings should be used as if they are immutable, but under a certain circumstance the APIs are allowed to mutate the mapping. Such circumstance is marked as

• Mappings: | ||

• Hashmaps: |

Next: Hashmaps, Previous: Mappings and hashmaps, Up: Mappings and hashmaps [Contents][Index]

- Module:
**srfi-146** -
This module provides treemap-based mappings API. On Gauche, an instance of

`mapping`

is just an instance of built-in`<tree-map>`

(see Treemaps). However, the API assumes a mapping to be treated as immutable data structure, except the “linear update” APIs, which is*allowed*to mutate the mappings passed to the arguments, under assumption that the argument won’t be used afterwards.See Hashmaps, which is a sibling of mappings but based on hashtables.

- Class:
**<mapping>** -
{

`srfi-146`} On Gauche, this is just an alias of`<tree-map>`

.

- Function:
**mapping***comparator key value …* [SRFI-146] {

`srfi-146`} Creates a new mapping with the given`comparator`, whose initial content is provided by`key``value`….The

`comparator`argument must be a comparator (see Basic comparators).The

`key``value`… arguments must be even length, alternating keys and values.(define m (mapping default-comparator 'a 1 'b 2)) (mapping-ref m 'a) ⇒ 1 (mapping-ref m 'b) ⇒ 2

- Function:
**mapping-unfold***p f g seed comparator* [SRFI-146] {

`srfi-146`} Creates a new mapping, whose content is populated by three procedures,`p`,`f`and`g`, and a seed value`seed`, as follows.In each iteration, we have a current seed value, whose initial value is

`seed`.First,

`p`, a stop predicate, is applied to the current seed value. If it returns true, we stop iteration and returns the new mapping.Next,

`f`is applied to the current seed value. It must return two values. The first one is for a key and the second one for the value. We add this pair to the mapping.Then,

`g`is applied to the current seed value. The result becomes the seed value of the next iteration. And we iterate.The following example creates a mapping that maps ASCII characters to their character codes:

(mapping-unfold (cut >= <> 128) (^c (values (integer->char c) c)) (cut + <> 1) 0 default-comparator)

- Function:
**mapping/ordered***comparator key value …* [SRFI-146] {

`srfi-146`} Similar to`mapping`

, but keys are given in the ascending order w.r.t. the comparator. An implementation may use more efficient algorithm than`mapping`

. In Gauche, this is the same as`mapping`

at this moment.

- Function:
**mapping-unfold/ordered***p f g seed comparator* [SRFI-146] {

`srfi-146`} Similar to`mapping-unfold`

, but keys are generated in the ascendnig order w.r.t. the comparator. An implementation may use more efficient algorithm than`mapping-unfold`

. In Gauche, this is the same as`mapping-unfold`

at this moment.

- Function:
**mapping?***obj* [SRFI-146] {

`srfi-146`} Returns`#t`

iff`obj`is a mapping object.

- Function:
**mapping-empty?***m* [SRFI-146] {

`srfi-146`}`M`must be a mapping. Returns`#t`

if`m`is empty,`#f`

otherwise. In Gauche, this is same as`tree-map-empty?`

(see Treemaps).

- Function:
**mapping-contains?***m key* [SRFI-146] {

`srfi-146`}`M`must be a mapping. Returns`#t`

if`m`has an entry with`key`,`#f`

otherwise. In Gauche, this is same as`tree-map-exists?`

(see Treemaps).

- Function:
**mapping-disjoint?***m1 m2* [SRFI-146] {

`srfi-146`} Returns`#t`

iff two mappings`m1`and`m2`have no keys in common. In other words, there’s no such key K that satisfy both`(mapping-contains? m1 K)`

and`(mapping-contains? m2 K)`

.

- Function:
**mapping-ref***m key :optional failure success* [SRFI-146] {

`srfi-146`} Get the value from a mapping`m`associated with`key`, and calls`success`on the value, and returns its result. If`m`doesn’t have`key`,`failure`is invoked with no arguments and its result is returned. Both`success`and`failure`is called in tail context.When

`failure`is omitted and`key`is not found, an error is signaled. When`success`is omitted,`identity`

is assumed.

- Function:
**mapping-ref/default***m key default* [SRFI-146] {

`srfi-146`} Returns the value associated to`key`from a mapping`m`. If`m`doesn’t have`key`,`default`is returned.

- Function:
**mapping-key-comparator***m* [SRFI-146] {

`srfi-146`} Returns a comparator used to compare keys in a mapping`m`. See Basic comparators, for the details of comparators.

Note that the basic premise of mappings srfi is to treat mappings as immutable. Each updating operation comes with a purely functional version (without bang) and a linear update version (with bang), but the linear update version may not require to destructively modiy the passed mapping; it’s merely a hint that it may reuse the argument for the efficiency. You always need to use the returned mapping as the result of update. If you use linear update versions, you shouldn’t use the passed mapping afterwards, for there’s no guarantee how the state of the passed mapping is.

- Function:
**mapping-adjoin***m arg …* - Function:
**mapping-adjoin!***m arg …* [SRFI-146] {

`srfi-146`} The`arg`… are alternating between key and value. Returns a mapping that contains all the entries in`m`plus given keys and values, with the same comparator as`m`. Linear update version`mapping-adjoin!`

may destructively modify`m`to create the return value, while`mapping-adjoin`

creates a new mapping.Argments are processed in order. If there’s already an entry in

`m`with the same key as given to`arg`, the original entry remains.`(mapping-adjoin (mapping default-comparator 'a 1 'b 2) 'c 3 'a 4 'c 5) ⇒ mapping with`

`a`→ 1,`b`→ 2,`c`→ 3

- Function:
**mapping-set***m arg …* - Function:
**mapping-set!***m arg …* [SRFI-146] {

`srfi-146`} The`arg`… are alternating between key and value. Returns a mapping that contains all the entries in`m`plus given keys and values, with the same comparator as`m`. Linear update version`mapping-set!`

may destructively modify`m`to create the return value, while`mapping-set`

creates a new mapping.Argments are processed in order. If there’s already an entry in

`m`with the same key as given to`arg`, the new key-value pair supersedes the old one.`(mapping-set (mapping default-comparator 'a 1 'b 2) 'c 3 'a 4 'c 5) ⇒ mapping with`

`a`→ 4,`b`→ 2,`c`→ 5

- Function:
**mapping-replace***m key value* - Function:
**mapping-replace!***m key value* [SRFI-146] {

`srfi-146`} If the mapping`m`has an entry of`key`, return a mapping with the value of the entry replaced for`value`. If`m`doesn’t have an entry with`key`,`m`is returned unchanged.Linear update version

`mapping-replace!`

may destructively modify`m`to produce the return value, while`mapping-replace`

creates a new mapping.(mapping-replace (mapping default-comparator 'a 1 'b 2) 'a 3) ⇒ mapping with

`a`→ 3,`b`→ 2 (mapping-replace (mapping default-comparator 'a 1 'b 2) 'c 3) ⇒ mapping with`a`→ 1,`b`→ 2

- Function:
**mapping-delete***m key …* - Function:
**mapping-delete!***m key …* [SRFI-146] {

`srfi-146`} Returns a mapping that is the same as`m`except its entries with any of the given`key`… being removed. Keys that are not in`m`are ignored.Linear update version

`mapping-delete!`

may destructively modify`m`to produce the return value, while`mapping-delete`

creates a new mapping.

- Function:
**mapping-delete-all***m key-list* - Function:
**mapping-delete-all!***m key-list* [SRFI-146] {

`srfi-146`} Returns a mapping that is the same as`m`except its entries with any of the given keys in`key-list`being removed. Keys that are not in`m`are ignored.Linear update version

`mapping-delete-all!`

may destructively modify`m`to produce the return value, while`mapping-delete-all`

creates a new mapping.

- Function:
**mapping-intern***m key make-value* - Function:
**mapping-intern!***m key make-value* [SRFI-146] {

`srfi-146`} Looks up`key`in the mapping`m`, and returns two values,`m`and the associated value. If`m`does not contain an entry with`key`, a thunk`make-value`is invoked, and creates a new mapping that contains all entries in`m`plus a new entry with`key`and the return value of`make-value`, then returns the new mapping and the return value of`make-value`.Linear update version

`mapping-intern!`

may destructively modify`m`to produce the return value, while`mapping-intern`

creates a new mapping.(mapping-intern (mapping default-comparator 'a 1) 'b (^[] 2)) ⇒ mapping with

`a`→ 1,`b`→ 2 and 2 (mapping-intern (mapping default-comparator 'a 1) 'a (^[] 2)) ⇒ mapping with`a`→ 1 and 1

- Function:
**mapping-update***m key updater :optional failure success* - Function:
**mapping-update!***m key updater :optional failure success* [SRFI-146] {

`srfi-146`} Semantically equivalent to this:(mapping-set

`m``var`(`updater`(mapping-ref`m``key``failure``success`)))The

`failure`and`success`optional arguments are procedures with zero and one arguments, respectively. When omitted,`failure`defaults to a thunk that raises an error, and`success`defaults to`identity`

.First,

`key`is looked up in`m`. If an entry is found, the associated value is passed to`success`; otherwise,`failure`is called with no arguments. Either way, let the returned value be`v0`.Then,

`v0`is passed to`updater`. Let its result be`v1`.Finally, a mapping with the same entries as

`m`except the value of`key`is altered to`v1`is returned.Linear update version

`mapping-update!`

may destructively modify`m`to produce the return value, while`mapping-update`

creates a new mapping.(mapping-update (mapping default-comparator 'a 1) 'a (pa$ + 1)) ⇒ mapping with

`a`→ 2 (mapping-update (mapping default-comparator) 'a (pa$ + 1) (^[] 0)) ⇒ mapping with`a`→ 1

- Function:
**mapping-update/default***m key updater default* - Function:
**mapping-update!/default***m key updater default* [SRFI-146] {

`srfi-146`}

- Function:
**mapping-pop***m :optional failure* - Function:
**mapping-pop!***m :optional failure* [SRFI-146] {

`srfi-146`}

- Function:
**mapping-search***m k failure success* - Function:
**mapping-search!***m k failure success* [SRFI-146] {

`srfi-146`}

- Function:
**mapping-size***m* [SRFI-146] {

`srfi-146`}

- Function:
**mapping-find***pred m failure* [SRFI-146] {

`srfi-146`}

- Function:
**mapping-count***pred m* [SRFI-146] {

`srfi-146`}

- Function:
**mapping-any?***pred m* - Function:
**mapping-every?***pred m* [SRFI-146] {

`srfi-146`}

- Function:
**mapping-keys***m* - Function:
**mapping-values***m* [SRFI-146] {

`srfi-146`}

- Function:
**mapping-entries***m* [SRFI-146] {

`srfi-146`}

- Function:
**mapping-map***proc comparator m* [SRFI-146] {

`srfi-146`}

- Function:
**mapping-map/monotone***proc comparator m* - Function:
**mapping-map/monotone!***proc comparator m* [SRFI-146] {

`srfi-146`}

- Function:
**mapping-for-each***proc m* [SRFI-146] {

`srfi-146`}

- Function:
**mapping-fold***kons knil m* [SRFI-146] {

`srfi-146`}

- Function:
**mapping-fold/reverse***kons knil m* [SRFI-146] {

`srfi-146`}

- Function:
**mapping-map->list***proc m* [SRFI-146] {

`srfi-146`}

- Function:
**mapping-filter***pred m* - Function:
**mapping-filter!***pred m* [SRFI-146] {

`srfi-146`}

- Function:
**mapping-remove***pred m* - Function:
**mapping-remove!***pred m* [SRFI-146] {

`srfi-146`}

- Function:
**mapping-partition***pred m* - Function:
**mapping-partition!***pred m* [SRFI-146] {

`srfi-146`}

- Function:
**mapping-copy***m* [SRFI-146] {

`srfi-146`}

- Function:
**mapping->alist***m* [SRFI-146] {

`srfi-146`}

- Function:
**alist->mapping***comparator alist* [SRFI-146] {

`srfi-146`}

- Function:
**alist->mapping!***m alist* [SRFI-146] {

`srfi-146`}

- Function:
**alist->mapping/ordered***comparator alist* - Function:
**alist->mapping/ordered!***m alist* [SRFI-146] {

`srfi-146`}

- Function:
**mapping=?***comparator m1 m2 …* [SRFI-146] {

`srfi-146`}

- Function:
**mapping<?***comparator m1 m2 …* - Function:
**mapping<=?***comparator m1 m2 …* - Function:
**mapping>?***comparator m1 m2 …* - Function:
**mapping>=?***comparator m1 m2 …* [SRFI-146] {

`srfi-146`}

- Function:
**mapping-union***m1 m2 …* - Function:
**mapping-union!***m1 m2 …* [SRFI-146] {

`srfi-146`}

- Function:
**mapping-intersection***m1 m2 …* - Function:
**mapping-intersection!***m1 m2 …* [SRFI-146] {

`srfi-146`}

- Function:
**mapping-difference***m1 m2 …* - Function:
**mapping-difference!***m1 m2 …* [SRFI-146] {

`srfi-146`}

- Function:
**mapping-xor***m1 m2 …* - Function:
**mapping-xor!***m1 m2 …* [SRFI-146] {

`srfi-146`}

- Function:
**mapping-min-key***m* - Function:
**mapping-max-key***m* [SRFI-146] {

`srfi-146`}

- Function:
**mapping-min-value***m* - Function:
**mapping-max-value***m* [SRFI-146] {

`srfi-146`}

- Function:
**mapping-min-entry***m* - Function:
**mapping-max-entry***m* [SRFI-146] {

`srfi-146`}

- Function:
**mapping-key-predecessor***m obj failure* - Function:
**mapping-key-successor***m obj failure* [SRFI-146] {

`srfi-146`}

- Function:
**mapping-range=***m obj* - Function:
**mapping-range<***m obj* - Function:
**mapping-range<=***m obj* - Function:
**mapping-range>***m obj* - Function:
**mapping-range>=***m obj* [SRFI-146] {

`srfi-146`}

- Function:
**mapping-range=!***m obj* - Function:
**mapping-range<!***m obj* - Function:
**mapping-range<=!***m obj* - Function:
**mapping-range>!***m obj* - Function:
**mapping-range>=!***m obj* [SRFI-146] {

`srfi-146`}

- Function:
**mapping-split***m obj* - Function:
**mapping-split!***m obj* [SRFI-146] {

`srfi-146`}

- Function:
**mapping-catenate***comparator m1 key value m2* - Function:
**mapping-catenate!***m1 key value m2* [SRFI-146] {

`srfi-146`}

- Function:
**make-mapping-comparator***comparator* [SRFI-146] {

`srfi-146`}

- Variable:
**mapping-comparator** [SRFI-146] {

`srfi-146`}

Previous: Mappings, Up: Mappings and hashmaps [Contents][Index]

- Module:
**srfi-146.hash** -
This module provides hashtable-based hashmap API. On Gauche, an instance of

`hashmap`

is just an instance of built-in`<hash-table>`

. However, the API assumes a hashmap to be treated as immutable data structure, except the “linear update” APIs, which is*allowed*to mutate the hashmaps passed to the arguments, under assumption that the argument won’t be used afterwards.See Mappings, which is a sibling of hashmaps but based on treemaps.

- Function:
**hashmap***comparator key value …* [SRFI-146] {

`srfi-146.hash`} Creates a new hashmap with the given`comparator`, whose initial content is provided by`key``value`….The

`comparator`argument must be a comparator (see Basic comparators).The

`key``value`… arguments must be even length, alternating keys and values.(define m (hashmap default-comparator 'a 1 'b 2)) (hashmap-ref m 'a) ⇒ 1 (hashmap-ref m 'b) ⇒ 2

- Function:
**hashmap-unfold***p f g seed comparator* [SRFI-146] {

`srfi-146.hash`} Creates a new hashmap, whose content is populated by three procedures,`p`,`f`and`g`, and a seed value`seed`, as follows.In each iteration, we have a current seed value, whose initial value is

`seed`.First,

`p`, a stop predicate, is applied to the current seed value. If it returns true, we stop iteration and returns the new hashmap.Next,

`f`is applied to the current seed value. It must return two values. The first one is for a key and the second one for the value. We add this pair to the hashmap.Then,

`g`is applied to the current seed value. The result becomes the seed value of the next iteration. And we iterate.The following example creates a hashmap that maps ASCII characters to their character codes:

(hashmap-unfold (cut >= <> 128) (^c (values (integer->char c) c)) (cut + <> 1) 0 default-comparator)

- Function:
**hashmap?***obj* [SRFI-146] {

`srfi-146.hash`} Returns`#t`

iff`obj`is a hashmap object.

- Function:
**hashmap-empty?***m* [SRFI-146] {

`srfi-146.hash`}`M`must be a hashmap. Returns`#t`

if`m`is empty,`#f`

otherwise. In Gauche, this is same as`tree-map-empty?`

(see Treemaps).

- Function:
**hashmap-contains?***m key* [SRFI-146] {

`srfi-146.hash`}`M`must be a hashmap. Returns`#t`

if`m`has an entry with`key`,`#f`

otherwise. In Gauche, this is same as`tree-map-exists?`

(see Treemaps).

- Function:
**hashmap-disjoint?***m1 m2* [SRFI-146] {

`srfi-146.hash`} Returns`#t`

iff two hashmaps`m1`and`m2`have no keys in common. In other words, there’s no such key K that satisfy both`(hashmap-contains? m1 K)`

and`(hashmap-contains? m2 K)`

.

- Function:
**hashmap-ref***m key :optional failure success* [SRFI-146] {

`srfi-146.hash`} Get the value from a hashmap`m`associated with`key`, and calls`success`on the value, and returns its result. If`m`doesn’t have`key`,`failure`is invoked with no arguments and its result is returned. Both`success`and`failure`is called in tail context.When

`failure`is omitted and`key`is not found, an error is signaled. When`success`is omitted,`identity`

is assumed.

- Function:
**hashmap-ref/default***m key default* [SRFI-146] {

`srfi-146.hash`} Returns the value associated to`key`from a hashmap`m`. If`m`doesn’t have`key`,`default`is returned.

- Function:
**hashmap-key-comparator***m* [SRFI-146] {

`srfi-146.hash`} Returns a comparator used to compare keys in a hashmap`m`. See Basic comparators, for the details of comparators.

Note that the basic premise of hashmaps srfi is to treat hashmaps as immutable. Each updating operation comes with a purely functional version (without bang) and a linear update version (with bang), but the linear update version may not require to destructively modiy the passed hashmap; it’s merely a hint that it may reuse the argument for the efficiency. You always need to use the returned hashmap as the result of update. If you use linear update versions, you shouldn’t use the passed hashmap afterwards, for there’s no guarantee how the state of the passed hashmap is.

- Function:
**hashmap-adjoin***m arg …* - Function:
**hashmap-adjoin!***m arg …* [SRFI-146] {

`srfi-146.hash`}

- Function:
**hashmap-set***m arg …* - Function:
**hashmap-set!***m arg …* [SRFI-146] {

`srfi-146.hash`}

- Function:
**hashmap-replace***m key value* - Function:
**hashmap-replace!***m key value* [SRFI-146] {

`srfi-146.hash`}

- Function:
**hashmap-delete***m key …* - Function:
**hashmap-delete!***m key …* [SRFI-146] {

`srfi-146.hash`}

- Function:
**hashmap-delete-all***m key-list* - Function:
**hashmap-delete-all!***m key-list* [SRFI-146] {

`srfi-146.hash`}

- Function:
**hashmap-intern***m key failure* - Function:
**hashmap-intern!***m key failure* [SRFI-146] {

`srfi-146.hash`}

- Function:
**hashmap-update***m key updater :optional failure success* - Function:
**hashmap-update!***m key updater :optional failure success* [SRFI-146] {

`srfi-146.hash`}

- Function:
**hashmap-update/default***m key updater default* - Function:
**hashmap-update!/default***m key updater default* [SRFI-146] {

`srfi-146.hash`}

- Function:
**hashmap-pop***m :optional failure* - Function:
**hashmap-pop!***m :optional failure* [SRFI-146] {

`srfi-146.hash`}

- Function:
**hashmap-search***m k failure success* - Function:
**hashmap-search!***m k failure success* [SRFI-146] {

`srfi-146.hash`}

- Function:
**hashmap-size***m* [SRFI-146] {

`srfi-146.hash`}

- Function:
**hashmap-find***pred m failure* [SRFI-146] {

`srfi-146.hash`}

- Function:
**hashmap-count***pred m* [SRFI-146] {

`srfi-146.hash`}

- Function:
**hashmap-any?***pred m* - Function:
**hashmap-every?***pred m* [SRFI-146] {

`srfi-146.hash`}

- Function:
**hashmap-keys***m* - Function:
**hashmap-values***m* [SRFI-146] {

`srfi-146.hash`}

- Function:
**hashmap-entries***m* [SRFI-146] {

`srfi-146.hash`}

- Function:
**hashmap-map***proc comparator m* [SRFI-146] {

`srfi-146.hash`}

- Function:
**hashmap-for-each***proc m* [SRFI-146] {

`srfi-146.hash`}

- Function:
**hashmap-fold***kons knil m* [SRFI-146] {

`srfi-146.hash`}

- Function:
**hashmap-map->list***proc m* [SRFI-146] {

`srfi-146.hash`}

- Function:
**hashmap-filter***pred m* - Function:
**hashmap-filter!***pred m* [SRFI-146] {

`srfi-146.hash`}

- Function:
**hashmap-remove***pred m* - Function:
**hashmap-remove!***pred m* [SRFI-146] {

`srfi-146.hash`}

- Function:
**hashmap-partition***pred m* - Function:
**hashmap-partition!***pred m* [SRFI-146] {

`srfi-146.hash`}

- Function:
**hashmap-copy***m* [SRFI-146] {

`srfi-146.hash`}

- Function:
**hashmap->alist***m* [SRFI-146] {

`srfi-146.hash`}

- Function:
**alist->hashmap***comparator alist* [SRFI-146] {

`srfi-146.hash`}

- Function:
**alist->hashmap!***m alist* [SRFI-146] {

`srfi-146.hash`}

- Function:
**hashmap=?***comparator m1 m2 …* [SRFI-146] {

`srfi-146.hash`}

- Function:
**hashmap<?***comparator m1 m2 …* - Function:
**hashmap<=?***comparator m1 m2 …* - Function:
**hashmap>?***comparator m1 m2 …* - Function:
**hashmap>=?***comparator m1 m2 …* [SRFI-146] {

`srfi-146.hash`}

- Function:
**hashmap-union***m1 m2 …* - Function:
**hashmap-union!***m1 m2 …* [SRFI-146] {

`srfi-146.hash`}

- Function:
**hashmap-intersection***m1 m2 …* - Function:
**hashmap-intersection!***m1 m2 …* [SRFI-146] {

`srfi-146.hash`}

- Function:
**hashmap-difference***m1 m2 …* - Function:
**hashmap-difference!***m1 m2 …* [SRFI-146] {

`srfi-146.hash`}

- Function:
**hashmap-xor***m1 m2 …* - Function:
**hashmap-xor!***m1 m2 …* [SRFI-146] {

`srfi-146.hash`}

- Function:
**make-hashmap-comparator***comparator* [SRFI-146] {

`srfi-146.hash`}

- Variable:
**hashmap-comparator** [SRFI-146] {

`srfi-146.hash`}

Previous: Mappings, Up: Mappings and hashmaps [Contents][Index]