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.
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" */
import "./trait" for HashableSeq
/* 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 HashableSeq {
// 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 { |key| key } }
// Returns a sequence of this instance's values in insertion order.
values { _k.map { |key| _m[key] } }
// 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 && _m.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 && _m.containsKey(key)) continue
this[key] = value
}
}
// Merges all the elements of 'other' into this instance adding new ones at the end.
// Keys which are already present in this map have their values replaced
// if 'replace' is true but not otherwise.
// A specialized version of 'addAll'.
merge(other, replace) {
if (!(other is OrderedMap)) Fiber.abort("Argument must be an OrderedMap.")
if (!(replace is Bool)) Fiber.abort("'replace' must be a boolean.")
for (key in other.keys) {
if (!replace && _m.containsKey(key)) continue
this[key] = other[key]
}
}
// 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.containsKey(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.containsKey(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) {
if (_m.containsKey(key)) {
var v = _m[key]
_m.remove(key)
_k.remove(key)
return v
} else {
return 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 keys) {
if (_m.containsKey(key)) removals.add(remove(key))
}
return removals
}
// Removes all entries from this instance 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 which takes a single parameter.")
}
if (isEmpty) return []
var removals = []
for (key in keys) {
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 ob = OrderedBag.new()
for (key in _k) ob.add(key, _m[key])
return ob
}
// Copies the elements of the current instance to a new OrderedMap object.
copy() {
var om = OrderedMap.new()
for (key in _k) om[key] = _m[key]
return om
}
// Copies all elements from this map and then 'other' to a new OrderedMap object.
// Keys in this map which are also present in 'other' have their values replaced
// if 'replace' is true but not otherwise. Returns the new OrderedMap.
union(other, replace) {
if (other.type != OrderedMap) Fiber.abort("Argument must be an OrderedMap.")
if (!(replace is Bool)) Fiber.abort("'replace' must be a boolean.")
var om = OrderedMap.new()
for (key in _k) om[key] = _m[key]
for (k in other.keys) {
if (!replace && _m.containsKey(key)) continue
om[k] = other[k]
}
return om
}
// Copies all elements for which this map and 'other' have keys in common to a new
// OrderedMap object. Keys in this map have their values replaced if 'replace' is true
// but not otherwise. Returns the new OrderedMap.
intersect(other, replace) {
if (other.type != OrderedMap) Fiber.abort("Argument must be an OrderedMap.")
if (!(replace is Bool)) Fiber.abort("'replace' must be a boolean.")
var om = OrderedMap.new()
for (key in _k) {
if (other.containsKey(key)) om[key] = replace ? other[key] : _m[key]
}
return om
}
// Copies all elements of this instance which are not elements of 'other'
// to a new OrderedMap object. Returns the new OrderedMap.
except(other) {
if (other.type != OrderedMap) Fiber.abort("Argument must be an OrderedMap.")
var om = OrderedMap.new()
for (key in _k) {
if (!other.containsKey(key)) om[key] = _m[key]
}
return om
}
// Copies all elements which are in this instance or 'other', but not both,
// to a new OrderedMap object. Returns the new OrderedMap.
symDiff(other) {
if (other.type != OrderedMap) Fiber.abort("Argument must be an OrderedMap.")
return this.except(other).union(other.except(this), false)
}
// Returns whether or not this instance is a submap of another OrderedMap
// Only keys are considered and not their associated values.
submapOf(other) {
if (other.type != OrderedMap) Fiber.abort("Argument must be an OrderedMap.")
if (_m.count > other.count) return false
for (key in _k) {
if (!other.containsKey(key)) return false
}
return true
}
// Returns whether or not this instance is a proper submap of another OrderedMap.
// Only keys are considered and not their associated values.
properSubmapOf(other) {
if (other.type != OrderedMap) Fiber.abort("Argument must be an OrderedMap.")
if (_m.count >= other.count) return false
for (key in _k) {
if (!other.containsKey(key)) return false
}
return true
}
// Returns whether or not this instance is a supermap of another OrderedMap.
// Only keys are considered and not their associated values.
// A specialized version of 'containsAll'.
supermapOf(other) {
if (other.type != OrderedMap) Fiber.abort("Argument must be an OrderedMap.")
if (_m.count <= other.count) return false
for (k in other.keys) {
if (!_m.containsKey(k)) return false
}
return true
}
// Finds the maximum value when the function 'f' is applied to each key of this
// instance and returns the first key added which corresponds to that maximum.
// Only works for function return types supporting the '>' operator unless
// there's 1 element (returns its key) or no elements (returns null).
max(f) {
if (!((f is Fn) && f.arity == 1)) {
Fiber.abort("Argument must be a function which takes a single parameter.")
}
var maxKey
var maxVal
var first = true
for (key in _k) {
var val = f.call(key)
if (first || val > maxVal) {
maxKey = key
maxVal = val
if (first) first = false
}
}
return maxKey
}
// Finds the minimum value when the function 'f' is applied to each key of this
// instance and returns the first key added which corresponds to that minimum.
// Only works for function return types supporting the '<' operator unless
// there's 1 element (returns its key) or no elements (returns null).
min(f) {
if (!((f is Fn) && f.arity == 1)) {
Fiber.abort("Argument must be a function which takes a single parameter.")
}
var minKey
var minVal
var first = true
for (key in _k) {
var val = f.call(key)
if (first || val < minVal) {
minKey = key
minVal = val
if (first) first = false
}
}
return minKey
}
// Returns whether or not the elements (keys and associated values) of this instance
// are the same as the elements of another OrderedMap and vice versa.
// Insertion order is irrelevant.
==(other) {
if (other.type != OrderedMap) Fiber.abort("Argument must be an OrderedMap.")
if (_m.count != other.count) return false
for (key in _k) {
if (!other.containsKey(key)) return false
var v1 = _m[key]
var v2 = other[key]
if (v1 != v2) return false
}
return true
}
// Returns whether or not the elements (keys and associated values) of this instance
// are not all the same as the elements of another OrderedMap and vice versa.
// Insertion order is irrelevant.
!=(other) { !(this == other) }
// Returns whether or not the keys of this instance (but not necessarily the associated
// values) are the same as the keys of another OrderedMap and vice versa.
sameDistinct(other) {
if (other.type != OrderedMap) Fiber.abort("Argument must be an OrderedMap.")
if (_m.count != other.count) return false
for (key in _k) {
if (!other.containsKey(key)) return false
}
return true
}
// 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 HashableSeq {
// 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 }
// Returns a sequence of all elements in the current instance.
elements { _k.map { |e| e } }
// 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)
}
// Merges all the elements of another OrderedSet object into the current instance,
// by adding new ones at the end of the latter. Duplicates are effectively ignored.
// A specialized version of 'addAll'.
merge(other) {
if (other.type != OrderedSet) Fiber.abort("Argument must be an OrderedSet.")
for (e in other) add(e)
}
// Returns whether or not the current instance contains an element 'e'.
contains(e) { _m.containsKey(e) }
// 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 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 no elements of a sequence.
containsNone(seq) { !containsAny(seq) }
// Removes an element 'e' from the current instance if it exists.
// Returns the element removed or null otherwise.
remove(e) {
if (_m.containsKey(e)) {
_m.remove(e)
_k.remove(e)
return e
} else {
return 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)
}
// Removes all elements from this instance which satisfy the predicate
// function 'fn' and returns a list of the elements removed.
removeBy(fn) {
if (!((fn is Fn) && fn.arity == 1)) {
Fiber.abort("'fn' must be a function which takes a single parameter.")
}
if (isEmpty) return []
var removals = []
for (key in _k) {
if (fn.call(key)) removals.add(remove(key))
}
return removals
}
// Removes 'removal' and adds 'addition' at the end.
replace(removal, addition) {
remove(removal)
add(addition)
}
// Removes 'removals' and adds 'additions' at the end.
replaceAll(removals, additions) {
removeAll(removals)
addAll(additions)
}
// Clears the current instance.
clear() {
_m.clear()
_k.clear()
}
// 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 om = OrderedMap.new()
for (key in _k) om[key] = 1
return om
}
// Copies the elements of the current instance to an OrderedBag, with a value of 1, and
// returns the OrderedBag.
toOrderedBag {
var ob = OrderedBag.new()
for (key in _k) ob.add(key)
return ob
}
// Copies the elements of the current instance to a new OrderedSet object.
copy() { OrderedSet.new(_k) }
// Copies all elements of this instance and then 'other' to a new RefSet object.
union(other) {
if (other.type != OrderedSet) Fiber.abort("Argument must be an OrderedSet.")
var os = copy()
for (e in other) os.add(e)
return os
}
// Copies all elements which this instance and 'other' have in common
// to a new OrderedSet object. Insertion order is the same as this one.
intersect(other) {
if (other.type != OrderedSet) Fiber.abort("Argument must be an OrderedSet.")
var os = OrderedSet.new()
for (key in _k) {
if (other.contains(key)) os.add(key)
}
return os
}
// Copies all elements of this instance which are not elements of 'other'
// to a new OrderedSet object. Insertion order is the same as this one.
except(other) {
if (other.type != OrderedSet) Fiber.abort("Argument must be an OrderedSet.")
var os = OrderedSet.new()
for (key in _k) {
if (!other.contains(key)) os.add(key)
}
return os
}
// Copies all elements which are in this instance or 'other', but not both,
// to a new OrderedSet object. Returns the new OrderedSet.
symDiff(other) {
if (other.type != OrderedSet) Fiber.abort("Argument must be an OrderedSet.")
return this.except(other).union(other.except(this))
}
// Returns whether or not this instance is a subset of another OrderedSet.
subsetOf(other) {
if (other.type != OrderedSet) Fiber.abort("Argument must be an OrderedSet.")
if (_m.count > other.count) return false
for (key in _k) {
if (!other.contains(key)) return false
}
return true
}
// Returns whether or not this instance is a proper subset of another OrderedSet.
properSubsetOf(other) {
if (other.type != OrderedSet) Fiber.abort("Argument must be a OrderedSet.")
if (_m.count >= other.count) return false
for (key in _k) {
if (!other.contains(key)) return false
}
return true
}
// Returns whether or not this instance is a superset of another OrderedSet.
// A specialized version of 'containsAll'.
supersetOf(other) {
if (other.type != OrderedSet) Fiber.abort("Argument must be an OrderedSet.")
if (_m.count <= other.count) return false
for (e in other) {
if (!_m.containsKey(e)) return false
}
return true
}
// Finds the maximum value when the function 'f' is applied to each element of this
// instance and returns the first element added which corresponds to that maximum.
// Only works for function return types supporting the '>' operator unless
// there's 1 element (returns it) or no elements (returns null).
max(f) {
if (!((f is Fn) && f.arity == 1)) {
Fiber.abort("Argument must be a function which takes a single parameter.")
}
var maxKey
var maxVal
var first = true
for (key in _k) {
var val = f.call(key)
if (first || val > maxVal) {
maxKey = key
maxVal = val
if (first) first = false
}
}
return maxKey
}
// Finds the minimum value when the function 'f' is applied to each element of this
// instance and returns the first element added which corresponds to that minimum.
// Only works for function return types supporting the '<' operator unless
// there's 1 element (returns it) or no elements (returns null).
min(f) {
if (!((f is Fn) && f.arity == 1)) {
Fiber.abort("Argument must be a function which takes a single parameter.")
}
var minKey
var minVal
var first = true
for (key in _k) {
var val = f.call(key)
if (first || val < minVal) {
minKey = key
minVal = val
if (first) first = false
}
}
return minKey
}
// Returns whether or not the elements of this instance are the same as the
// elements of another OrderedSet and vice versa. Insertion order is irrelevant.
==(other) {
if (other.type != OrderedSet) Fiber.abort("Argument must be a OrderedSet.")
if (_m.count != other.count) return false
for (key in _k) {
if (!other.contains(key)) return false
}
return true
}
// Returns whether or not the elements of this instance are not all the same as the
// elements of another OrderedSet and vice versa. Insertion order is irrelevant.
!=(other) { !(this == other) }
// 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 HashableSeq {
// Constructs a new empty OrderedBag object.
construct new() {
_m = {}
_k = []
}
// Constructs a new OrderedBag 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 (v in _m.values) total = total + v
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 in insertion order.
distinct { _k.map { |key| key } }
// Returns a sequence of all values in the current instance in insertion order.
values { _k.map { |key| _m[key] } }
// 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 p = [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
}
}
}
// Merges all the elements of another Ordered Bag object into the current instance
// increasing values where necessary and adding new ones at the end of this one.
// A specialized version of 'addAll'.
merge(other) {
if (other.type != OrderedBag) Fiber.abort("Argument must be an OrderedBag.")
for (e in other.distinct) _m[e] = _m.containsKey(e) ? _m[e] + other[e] : other[e]
}
// 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.containsKey(e)) {
var v = _m[e]
_m.remove(e)
_k.remove(e)
return [e, v]
} else {
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)
}
// Removes 'removal' and adds 'addition'.
replace(removal, addition) {
remove(removal)
add(addition)
}
// Removes 'removals' and adds 'additions'.
replaceAll(removals, additions) {
removeAll(removals)
addAll(additions)
}
// 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 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 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 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 om = OrderedMap.new()
for (key in _k) om[key] = _m[key]
return om
}
// 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 ob = OrderedBag.new()
for (key in _k) ob.add(key, _m[key])
return ob
}
// Copies all elements of this instance and another OrderedBag to a new OrderedBag object,
// increasing values where necessary. Insertion order is this one first, then the other.
union(other) {
if (other.type != OrderedBag) Fiber.abort("Argument must be an OrderedBag.")
var ob = OrderedBag.new()
for (key in _k) ob.add(key, _m[key])
for (k in other.distinct) ob.add(k, other[k])
return ob
}
// Copies all elements which this instance and another OrderedBag have in common
// to a new OrderedBag object. Insertion order is the same as this one.
intersect(other) {
if (other.type != OrderedBag) Fiber.abort("Argument must be an OrderedBag.")
var ob = OrderedBag.new()
for (key in _k) {
if (other.contains(key)) {
var v1 = _m[key]
var v2 = other[key]
var v3 = (v1 < v2) ? v1 : v2
ob.add(key, v3)
}
}
return ob
}
// Copies all elements of this instance which are not elements of another Bag
// to a new Bag object. Insertion order is the same as this one.
except(other) {
if (other.type != OrderedBag) Fiber.abort("Argument must be an OrderedBag.")
var ob = OrderedBag.new()
for (key in _k) {
if (!other.contains(key)) {
ob.add(key, _m[key])
} else {
var v1 = _m[key]
var v2 = other[key]
if (v1 > v2) ob.add(key, v1 - v2)
}
}
return ob
}
// Copies all elements which are in this instance or 'other', but not both,
// to a new OrderedBag object. Returns the new OrderedBag.
symDiff(other) {
if (other.type != OrderedBag) Fiber.abort("Argument must be an OrderedBag.")
return this.except(other).union(other.except(this))
}
// Returns whether or not this instance is a subbag of another OrderedBag.
subbagOf(other) {
if (other.type != OrderedBag) Fiber.abort("Argument must be an OrderedBag.")
if (_m.count > other.distinctCount) return false
for (key in _k) {
if (!other.contains(key)) return false
var v1 = _m[key]
var v2 = other[key]
if (v1 > v2) return false
}
return true
}
// Returns whether or not this instance is a proper subbag of another OrderedBag.
properSubbagOf(other) {
if (other.type != OrderedBag) Fiber.abort("Argument must be an OrderedBag.")
if (_m.count >= other.distinctCount) return false
for (key in _k) {
if (!other.contains(key)) return false
var v1 = _m[key]
var v2 = other[key]
if (v1 >= v2) return false
}
return true
}
// Returns whether or not this instance is a superbag of another OrderedBag.
// A specialized version of 'containsAll'.
superbagOf(other) {
if (other.type != OrderedBag) Fiber.abort("Argument must be an OrderedBag.")
if (_m.count <= other.distinctCount) return false
for (k in other.distinct) {
if (!_m.containsKey(k)) return false
var v1 = _m[k]
var v2 = other[k]
if (v1 < v2) return false
}
return true
}
// 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)
}
}
// Finds the maximum value when the function 'f' is applied to each distinct element of
// this instance and returns the first element added which corresponds to that maximum.
// Only works for function return types supporting the '>' operator unless
// there's 1 distinct element (returns it) or no elements (returns null).
max(f) {
if (!((f is Fn) && f.arity == 1)) {
Fiber.abort("Argument must be a function which takes a single parameter.")
}
var maxKey
var maxVal
var first = true
for (key in _k) {
var val = f.call(key)
if (first || val > maxVal) {
maxKey = key
maxVal = val
if (first) first = false
}
}
return maxKey
}
// Finds the minimum value when the function 'f' is applied to each distinct element of
// this instance and returns the first element added which corresponds to that minimum.
// Only works for function return types supporting the '<' operator unless
// there's 1 distinct element (returns it) or no elements (returns null).
min(f) {
if (!((f is Fn) && f.arity == 1)) {
Fiber.abort("Argument must be a function which takes a single parameter.")
}
var minKey
var minVal
var first = true
for (key in _k) {
var val = f.call(key)
if (first || val < minVal) {
minKey = key
minVal = val
if (first) first = false
}
}
return minKey
}
// Returns whether or not the elements of this instance are the same
// as the elements of another OrderedBag and vice versa.
// Insertion order is irrelevant.
==(other) {
if (other.type != OrderedBag) Fiber.abort("Argument must be an OrderedBag.")
if (_m.count != other.distinctCount) return false
for (key in _k) {
if (!other.contains(key)) return false
var v1 = _m[key]
var v2 = other[key]
if (v1 != v2) return false
}
return true
}
// Returns whether or not the elements of this instance are not all the same
// as the elements of another OrderedBag and vice versa.
// Insertion order is irrelevant.
!=(other) { !(this == other) }
// Returns whether or not the distinct elements of this instance are the same
// as the distinct elements of another OrderedBag and vice versa.
sameDistinct(other) {
if (other.type != OrderedBag) Fiber.abort("Argument must be an OrderedBag.")
if (_m.count != other.count) return false
for (key in _k) {
if (!other.contains(key)) return false
}
return true
}
// 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 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): %(_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]]) }
}