Category talk:Wren-ordered
Map iteration order
Wren's built-in Map class ensures fast retrieval and containment checks by key but has the drawback that iteration order is undefined and may even change between invocations.
Most of the time this is unimportant but situations can arise where it is desirable or even necessary to be able to iterate the map elements in the order in which they were added or at least in some predictable (and hence repeatable) order.
The only way to achieve this in Wren is to maintain a separate list of the keys in the order in which they were added and then use this list to iterate through the elements of the map. This module automates that process via the OrderedMap class. It also contains OrderedSet and OrderedBag classes to achieve the same outcome for the Set and Bag classes (in Wren-set) which use a map internally for storage and whose iteration order is therefore undefined also.
It is not a complete reimplementation of these basic classes (and Wren-mapUtil) in ordered form but omits some methods (mostly those which take other similar classes as parameters) where the resulting insertion order or relationships would or might no longer be clear and which are probably unimportant anyway in the kinds of scenarios envisaged.
Although it would be convenient to implement OrderedSet and OrderedBag by using an OrderedMap internally for storage, it is more efficient (albeit slightly less convenient) to use the built-in Map and List classes separately. However, this is transparent to the user.
Clearly, the 'ordered' classes need more memory (to accomodate the key list), will be slower for additions and much slower for removals than their 'unordered' counterparts. Consequently, they should only be preferred where maintaining a defined order is important.
Source code
/* Module "ordered.wren" */
/* OrderedMap represents an ordered collection that associates unique keys to values.
It is implemented as:
1. a Map whose key/value pairs are the elements of the OrderedMap. Consequently, only
element types which can be Map keys are supported; and
2. a List of the keys which is maintained in insertion order.
The Map ensures that retrieval and containment checks are very fast and the List ensures
that the OrderedMap can be iterated (or represented as a string) in insertion order.
*/
class OrderedMap is Sequence {
// Constructs a new empty OrderedMap object.
construct new() {
_m = {}
_k = []
}
// Creates a new OrderedMap from lists of keys and values
// which must be of the same length.
construct create(keys, values) {
if (!((keys is List) && (values is List)) || keys.count != values.count) {
Fiber.abort("Arguments must be lists of the same length.")
}
_m = {}
_k = []
for (i in 0...keys.count) this[keys[i]] = values[i]
}
// Creates a new Map from a sequence of keys and assigns
// the same value to all of them.
construct createSame(keys, value) {
if (!(keys is Sequence)) Fiber.abort("'keys' must be a sequence.")
_m = {}
_k = []
for (key in keys) this[key] = value
}
// Returns the number of elements in this instance.
count { _m.count }
// Returns whether or not the current instance is empty.
isEmpty { _m.count == 0 }
// Returns a sequence of this instance's keys in insertion order.
keys { _k.map { |e| e } }
// Returns a sequence of this instance's values in insertion order.
values { _k.map { |e| _m[e] } }
// Associates 'value' with 'key' in this instance.
// If 'key' is already present, replaces the previous value.
// Synonym for the setter.
add(key, value) { this[key] = value }
// Adds entries to this instance from lists of keys and values
// which must be of the same length.
// Keys which are already present have their values replaced
// if 'replace' is true but not otherwise.
addAll(keys, values, replace) {
if (!((keys is List) && (values is List)) || keys.count != values.count) {
Fiber.abort("Arguments must be lists of the same length.")
}
if (!(replace is Bool)) Fiber.abort("'replace' must be a boolean.")
for (i in 0...keys.count) {
if (!replace && map.containsKey(key[i])) continue
this[keys[i]] = values[i]
}
}
// Adds entries to this instance from a sequence of keys and assigns
// the same value to all of them.
// Keys which are already present have their values replaced
// if 'replace' is true but not otherwise.
addAllSame(keys, value, replace) {
if (!(keys is Sequence)) Fiber.abort("'keys' must be a sequence.")
if (!(replace is Bool)) Fiber.abort("'replace' must be a boolean.")
for (key in keys) {
if (!replace && map.containsKey(key)) continue
this[key] = value
}
}
// Returns whether or not the current instance contains the key 'key'.
containsKey(key) { _m.containsKey(key) }
// Synonym for 'containsKey' method.
contains(key) { _m.containsKey(key) }
// Returns true if all keys in the 'keys' sequence are keys of this instance
// or false otherwise.
containsAll(keys) {
if (!(keys is Sequence)) Fiber.abort("'keys' must be a sequence.")
for (key in keys) {
if (!_m[key]) return false
}
return true
}
// Returns true if any key in the 'keys' sequence is a key of this instance
// or false otherwise.
containsAny(keys) {
if (!(keys is Sequence)) Fiber.abort("'keys' must be a sequence.")
for (key in keys) {
if (_m[key]) return true
}
return false
}
// Returns true if no key in the 'keys' sequence is a key of this instance
// or false otherwise.
containsNone(keys) { !containsAny(map, keys) }
// Removes 'key' and its associated value from this instance.
// Returns the value or null if 'key' is not present.
remove(key) { _m.remove(key) ? _k.remove(key) : null }
// Removes all keys in the 'keys' sequence and their associated values from
// this instance and returns a list of the associated values removed.
removeAll(keys) {
if (!(keys is Sequence)) Fiber.abort("'keys' must be a sequence.")
if (isEmpty) return []
var removals = []
for (key in _k) {
if (containsKey(key)) removals.add(remove(key))
}
return removals
}
// Removes all entries from 'map' whose key satisfies the predicate
// function 'fn' and returns a list of the associated values removed.
removeBy(fn) {
if (!(fn is Fn && fn.arity == 1)) {
Fiber.abort("'fn' must be a function of arity 1.")
}
if (isEmpty) return []
var removals = []
for (key in _k) {
if (fn.call(key)) removals.add(remove(key))
}
return removals
}
// Clears the current instance.
clear() {
_m.clear()
_k.clear()
}
// Gets the value associated with 'key' in this instance.
// If 'key' is not present, returns null.
[key] { _m[key] }
// Associates 'value' with 'key' in this instance.
// If 'key' is already present, replaces the previous value.
[key]=(value) {
if (!_m.containsKey(key)) _k.add(key)
_m[key] = value
}
// Copies the elements of the current instance to a Map and returns it.
// Note that insertion order will no longer be guaranteed.
toMap {
var m = {}
for (key in _k) m[key] = _m[key]
return m
}
// Copies the keys of the current instance to a new OrderedSet object and returns it.
toOrderedSet() { OrderedSet.new(_k) }
// Copies the elements of the current instance to an OrderedBag object and returns it.
// Only works if values are positive integers.
toOrderedBag {
var b = OrderedBag.new()
for (key in _k) b.add(key, _m[key])
return b
}
// Copies the elements of the current instance to a new OrderedMap object.
copy() {
var newMap = OrderedMap.new()
for (key in _k) newMap[key] = _m[key]
return newMap
}
// Returns a string representation of this instance with the key/value pairs
// being in insertion order.
toString {
if (isEmpty) return "{}"
var first = true
var result = "{"
for (key in _k) {
if (!first) result = result + ", " else first = false
result = result + "%(key): %(_m[key])"
}
return result + "}"
}
// Iterator protocol methods using the iteration order of the internal list.
iterate(iterator) { _k.iterate(iterator) }
iteratorValue(iterator) { MapEntry.new(_k[iterator], _m[_k[iterator]]) }
}
/* OrderedSet represents an ordered collection of unique objects. It is implemented as:
1. a Map whose keys are the elements of the set but whose values are always 1.
Consequently, only element types which can be Map keys are supported; and
2. a List of the keys which is maintained in insertion order.
The Map ensures checks for containment are very fast and the List ensures that the
OrderedSet can be iterated (or represented as a string) in insertion order.
*/
class OrderedSet is Sequence {
// Constructs a new empty OrderedSet object.
construct new() {
_m = {}
_k = []
}
// Constructs a new OrderedSet object and adds the elements of a sequence to it.
construct new(seq) {
if (!(seq is Sequence)) Fiber.abort("Argument must be a Sequence.")
_m = {}
_k = []
for (e in seq) add(e)
}
// Returns the number of elements in the current instance.
count { _m.count }
// Returns whether or not the current instance is empty.
isEmpty { _m.count == 0 }
// Adds an element 'e' to the current instance. If the set already contains 'e'
// the set remains unchanged.
add(e) {
if (!_m.containsKey(e)) {
_m[e] = 1
_k.add(e)
}
}
// Adds all the elements of a sequence to the current instance. Duplicates are
// effectively ignored.
addAll(seq) {
if (!(seq is Sequence)) Fiber.abort("Argument must be a Sequence.")
for (e in seq) add(e)
}
// Removes an element 'e' from the current instance if it exists.
// Returns the element removed or null otherwise.
remove(e) { _m.remove(e) ? _k.remove(e) : null }
// Removes all elements of a sequence from the current instance if they exist.
removeAll(seq) {
if (!(seq is Sequence)) Fiber.abort("Argument must be a Sequence.")
for (e in seq) remove(e)
}
// Clears the current instance.
clear() {
_m.clear()
_k.clear()
}
// Returns whether or not the current instance contains an element 'e'.
contains(e) { _m.containsKey(e) }
// Returns whether or not the current instance contains any element of a sequence.
containsAny(seq) {
if (!(seq is Sequence)) Fiber.abort("Argument must be a Sequence.")
for (e in seq) {
if (_m.containsKey(e)) return true
}
return false
}
// Returns whether or not the current instance contains all elements of a sequence.
containsAll(seq) {
if (!(seq is Sequence)) Fiber.abort("Argument must be a Sequence.")
for (e in seq) {
if (!_m.containsKey(e)) return false
}
return true
}
// Returns whether or not the current instance contains no elements of a sequence.
containsNone(seq) { !containsAny(seq) }
// Copies the elements of the current instance to a List and returns the List.
toList { _k.toList }
// Copies the elements of the current instance to a Map, with a value of 1, and
// returns the Map. Note that insertion order will no longer be guaranteed.
toMap {
var m = {}
for (key in _k) m[key] = 1
return m
}
// Copies the elements of the current instance to an OrderedMap, with a value of 1, and
// returns the OrderedMap.
toOrderedMap {
var m = OrderedMap.new()
for (key in _k) m[key] = 1
return m
}
// Copies the elements of the current instance to an OrderedBag, with a value of 1, and
// returns the OrderedBag.
toOrderedBag {
var b = OrderedBag.new()
for (key in _k) b.add(key, 1)
return b
}
// Copies the elements of the current instance to a new OrderedSet object.
copy() { OrderedSet.new(_k) }
// Returns the string representation of the current instance in insertion order
// and enclosed in angle brackets to distinguish from Maps, OrderedMaps and Lists.
toString {
if (isEmpty) return "<>"
var first = true
var result = "<"
for (key in _k) {
if (!first) result = result + ", " else first = false
result = result + "%(key)"
}
return result + ">"
}
// Iterator protocol methods using the iteration order of the internal list.
iterate(iter) { _k.iterate(iter) }
iteratorValue(iter) { _k.iteratorValue(iter) }
}
/* OrderedBag represents an ordered collection of objects which may be repeated.
It is implemented as:
1. a Map whose keys are the distinct elements of the OrderedBag but whose values are
the numbers of each such element. Consequently, only element types which can be
Map keys are supported; and
2. a List of the keys which is maintained in insertion order.
The Map ensures that retrieval and containment checks are very fast and the List ensures
that the OrderedBag can be iterated (or represented as a string) in insertion order.
*/
class OrderedBag is Sequence {
// Constructs a new empty Bag object.
construct new() {
_m = {}
_k = []
}
// Constructs a new Bag object and adds the elements of a sequence to it.
construct new(seq) {
if (!(seq is Sequence)) Fiber.abort("Argument must be a Sequence.")
_m = {}
_k = []
for (e in seq) add(e)
}
// Returns the number of distinct elements in the current instance.
distinctCount { _m.count }
// Returns the total number of elements in the current instance.
count {
var total = 0
for (key in _k) total = total + _m[key]
return total
}
// Returns whether or not the current instance is empty.
isEmpty { _m.count == 0 }
// Returns a sequence of all distinct elements in the current instance.
distinct { _k.map { |e| e } }
// Returns a sequence of all values in the current instance.
values { _m.values }
// Adds an element 'e' to the current instance. If the bag already contains 'e'
// its value is incremented.
add(e) {
if (!_m.containsKey(e)) {
_m[e] = 1
_k.add(e)
} else {
_m[e] = _m[e] + 1
}
}
// Adds all the elements of a sequence to the current instance incrementing their
// values if they're already present.
addAll(seq) {
if (!(seq is Sequence)) Fiber.abort("Argument must be a Sequence.")
for (e in seq) add(e)
}
// Adds an element 'e' with a value of 'v' to the current instance. If the bag
// already contains 'e' its value is increased accordingly.
add(e, v) {
if (v.type != Num || !v.isInteger || v < 1) {
Fiber.abort("Value must be a positive integer.")
}
if (!_m.containsKey(e)) {
_m[e] = v
_k.add(e)
} else {
_m[e] = _m[e] + v
}
}
// Adds an element 'e' with a value of 'v', presented in the form [e, v], to the
// current instance. If the bag already contains 'e' its value is increased accordingly.
addPair(p) {
if (p.type != List || p.count != 2) {
Fiber.abort("Argument must be an [element, value] pair.")
}
add(p[0], p[1])
}
// Reduces the value of an element 'e' of the current instance by 'r' if its exists.
// If this would reduce the value below 1, 'e' is removed completely.
reduce(e, r) {
if (r.type != Num || !r.isInteger || r < 1) {
Fiber.abort("Reduction must be a positive integer.")
}
if (_m.containsKey(e)) {
var v = _m[e] - r
if (v < 1) {
_m.remove(e)
_k.remove(e)
} else {
_m[e] = v
}
}
}
// Removes an element 'e' from the current instance, if it exists and whether distinct
// or not. Returns the element removed and its value or null otherwise.
remove(e) {
if (_m.remove(e)) {
_k.remove(e)
return [e, _m[e]]
}
return null
}
// Removes all elements of a sequence from the current instance if they exist
// and whether distinct or not.
removeAll(seq) {
if (!(seq is Sequence)) Fiber.abort("Argument must be a Sequence.")
for (e in seq) remove(e)
}
// Clears the current instance.
clear() {
_m.clear()
_k.clear()
}
// Returns whether or not the current instance contains an element 'e'.
contains(e) { _m.containsKey(e) }
// Returns whether or not the current instance contains any element of a sequence.
containsAny(seq) {
if (!(seq is Sequence)) Fiber.abort("Argument must be a Sequence.")
for (e in seq) {
if (_m.containsKey(e)) return true
}
return false
}
// Returns whether or not the current instance contains all distinct elements of
// a sequence.
containsAll(seq) {
if (!(seq is Sequence)) Fiber.abort("Argument must be a Sequence.")
for (e in seq) {
if (!_m.containsKey(e)) return false
}
return true
}
// Returns whether or not the current instance contains no elements of a sequence.
containsNone(seq) { !containsAny(seq) }
// Copies the elements of the current instance to a List and returns the List.
// An element with value 'v' is repeated 'v' times.
toFlatList {
var l = []
for (key in _k) {
var v = _m[key]
for (i in 1..v) l.add(key)
}
return l
}
// Copies the elements of the current instance to a Map, with their values, and
// returns the Map. Note that insertion order will no longer be guaranteed.
toMap {
var m = {}
for (key in _k) m[key] = _m[key]
return m
}
// Copies the elements of the current instance to an OrderedMap, with their values, and
// returns the OrderedMap.
toOrderedMap {
var m = OrderedMap.new()
for (key in _k) m[key] = _m[key]
return m
}
// Copies the distinct elements of the current instance to a new OrderedSet object.
toOrderedSet() { OrderedSet.new(_k) }
// Copies the elements of the current instance to a new OrderedBag object.
copy() {
var b = OrderedBag.new()
for (key in _k) b.add(key, _m[key])
return b
}
// Returns the value corresponding to 'e' or null if it doesn't exist.
[e] { _m[e] }
// Sets the value for 'e' creating a new one with that value if it doesn't exist.
// Setting its value to 0 removes 'e' from the bag.
[e]=(v) {
if (v.type != Num || !v.isInteger || v < 0) {
Fiber.abort("Value must be a non-negative integer.")
}
if (_m.containsKey(e)) {
if (v > 0) {
_m[e] = v
} else {
remove(e)
}
} else if (v > 0) {
_m[e] = v
_k.add(e)
}
}
// Returns whether or not all elements of this instance are distinct.
allDistinct { _k.all { |k| _m[k] == 1 } }
// Returns the string representation of the current instance enclosed in angle brackets
// to distinguish from Maps, OrderedMaps and Lists.
toString {
if (isEmpty) return "<>"
var first = true
var result = "<"
for (key in _k) {
if (!first) result = result + ", " else first = false
result = result + "%(key): %(_m[key])"
}
return result + ">"
}
// Iterator protocol methods using the iteration order of the internal list.
iterate(iterator) { _k.iterate(iterator) }
iteratorValue(iterator) { MapEntry.new(_k[iterator], _m[_k[iterator]]) }
}