12.18 data.priority-map - Priority map

Module: data.priority-map ¶

Priority map is a dictionary that can map keys to values, while the entires are sorted by their values. (If the entires are sorted by keys, it’s a treemap–see Treemaps).

It is useful when you wanted a sorted sequence, with quick access by keys that are associated to each value.

Note: If what you need is just a priority queue, you can use data.heap (see data.heap - Heap).

Class: <priority-map> ¶

{data.priority-map} Priority map class. It has no public slots. Instances of priority maps must be created by make-priority-map procedure instead of make method on the class.

Inherits <ordered-dictionary>, and implements dictionary protocol. Operations concerning associations of keys and values are done through dictionary generic functions (see Generic functions for dictionaries).

When iterated, it iterates increasing order of values.

Function: make-priority-map :key key-comparator value-comparator ¶

{data.priority-map} Creates and returns an empty priority map. It can take key-comparator, which is used to compare keys, and value-comparator, which must have ordering predicate and is used to order values. When omitted, default-comparator is assumed.

If you apply dict-comparator on a priority map, its key-comparator is returned.

Function: dict->priority-map dict :optional value-comparator ¶

{data.priority-map} Creates and returns a priority map that contains the same key-value entries as given dictionary dict. The priority map’s key comparator is the same as the key comparator of dict, and its value comparator is value-comparator, defaulted to default-comparator.

Function: alist->priority-map alist :optional key-comparator value-comparator ¶

{data.priority-map} Creates and returns a priority map that contains the key-value pairs in an assoc list alist. The optional key-comparator and value-comparator are used to build a priority map. When omitted, default-comparator is used.

Function: priority-map-min pmap ¶

Function: priority-map-max pmap ¶

{data.priority-map} Return a pair of a key and a value, where the value is smallest or largest in the priority map pmap, respectively.

If pmap is empty, #f is returned.

If pmap has more than one value that are equal to each other (w.r.t. value-comparator given to the constructor), either one of them is picked.

Function: priority-map-min-all pmap ¶

Function: priority-map-max-all pmap ¶

{data.priority-map} Return a pair of a list of keys and a value, where the value is smallest or largest in the priority map pmap, respectively. The keys includes all the entries that has the same value. The caller shouldn’t modify the returned key list.

If pmap is empty, #f is returned.

Function: priority-map-pop-min! pmap ¶

Function: priority-map-pop-max! pmap ¶

{data.priority-map} Remove one entry with the smallest or largest value, respectively, and returns a pair of the key and the value of removed entry.

If pmap is empty, #f is returned.

If pmap has more than one value that are equal to each other (w.r.t. value-comparator given to the constructor), either one of them is picked.