NAME
Sidef::Types::Set::Bag - A multiset (bag) data structure for Sidef
DESCRIPTION
This class implements a multiset (also known as a bag): a collection that allows duplicate elements and tracks the frequency (count) of each unique element. Unlike a regular Sidef::Types::Set::Set, where each element appears at most once, a Bag keeps a count alongside each distinct value, making it useful for frequency analysis and operations that need to preserve multiplicity. It's a subclass of Set.
Internally, a Bag maps each element's serialized key (see "DESCRIPTION" in Sidef::Types::Set::Set for how elements are compared/deduplicated) to a small record holding both the original value and its current count.
SYNOPSIS
var a = Bag(1, 1, 2, 3)
var b = Bag(1, 4, 3, 5)
say(a | b) #=> Bag(1, 1, 2, 3, 4, 5)
say(a ^ b) #=> Bag(1, 2, 4, 5)
say(a & b) #=> Bag(1, 3)
say(a - b) #=> Bag(1, 2)
say(a + b) #=> Bag(1, 1, 1, 2, 3, 3, 4, 5)
say(a.count(1)) #=> 2
say(a.elems) #=> 3
say(a.len) #=> 4
say(a.keys) #=> [1, 2, 3]
say(a.freq) #=> [[1, 2], [2, 1], [3, 1]]INHERITS
Inherits methods from Sidef::Types::Set::Set.
CONSTRUCTION
new
Bag(*elements)
Bag.new(*elements)Creates a new bag containing elements, tallying a count for each distinct value. With no arguments, creates an empty bag. Note that this constructor always blesses into the literal Sidef::Types::Set::Bag package itself, regardless of the invocant -- it is not polymorphic.
var bag = Bag.new
var bag2 = Bag.new(1, 2, 2, 3) #=> Bag(1, 2, 2, 3)Aliases: call
SET ALGEBRA
For "union", "intersection", "difference", and "symmetric_difference", the right-hand operand doesn't have to already be a Bag -- if it isn't one, it's first converted with .to_bag. "concat" (the + operator) is the one exception: if other isn't the exact same class, it's added as a single new element (incrementing its own count by 1) rather than merged.
concat
self.concat(other)
self + otherIf other is also a Bag (of the exact same class), returns a new bag where every shared element's count is the sum of its counts in both bags (and every element only present in one side keeps its original count). If other is anything else, it is added as a single new element instead.
say(Bag(1, 2) + Bag(2, 3)) #=> Bag(1, 2, 2, 3)Aliases: operator +
union
self.union(other)
self | otherReturns a new bag where each element's count is the maximum of its counts in self and other.
say(Bag(1, 1, 2) | Bag(1, 3, 3)) #=> Bag(1, 1, 2, 3, 3)Aliases: or, operator |, operator ∪
intersection
self.intersection(other)
self & otherReturns a new bag containing only the elements present in both self and other, with each count being the minimum of the two.
say(Bag(1, 1, 2, 3) & Bag(1, 2, 2, 4)) #=> Bag(1, 2)Aliases: and, operator &, operator ∩
difference
self.difference(other)
self - otherReturns a new bag where each element of self has its count reduced by its count in other; an element is dropped entirely once its count would be zero or negative.
say(Bag(1, 1, 2, 3) - Bag(1, 3)) #=> Bag(1, 2)Aliases: sub, diff, operator -, operator ∖
symmetric_difference
self.symmetric_difference(other)
self ^ otherReturns a new bag with, for each element, the absolute difference between its counts in self and other (an element present in only one bag keeps its full count there; an element with equal counts on both sides is dropped entirely).
say(Bag(1, 1, 2) ^ Bag(1, 3)) #=> Bag(1, 2, 3)Aliases: xor, symdiff, operator ^
MEMBERSHIP AND COMPARISON
has
self.has(obj)
self ∋ objReturns true if obj is an element of the bag (with a count of at least 1), regardless of its actual count, otherwise false.
say(Bag(1, 2, 3) ∋ 2) #=> true
say(Bag(1, 2, 3) ∋ 5) #=> falseAliases: haskey, has_key, exists, include, includes, contain, contains, operator ∋
∌
self ∌ objReturns true if obj is not an element of the bag -- the logical negation of "has".
say(Bag(1, 2, 3) ∌ 5) #=> true
say(Bag(1, 2, 3) ∌ 2) #=> falsecontains_all
self.contains_all(*objects)Returns true if the bag contains every one of objects with at least as high a count as that object appears among objects itself. In other words, this is multiplicity-aware: asking for 1 twice requires the bag to contain at least two 1s, not just one.
say(Bag(1, 2, 3, 3).contains_all(1, 3)) #=> true
say(Bag(1, 2, 3).contains_all(1, 4)) #=> false
say(Bag(1, 2, 3).contains_all(1, 1)) #=> false # only one 1 in the bagis_subset
self.is_subset(other)
self <= otherReturns true if every element of self also appears in other with a count at least as high (other is converted with .to_bag first if it isn't already a bag).
say(Bag(1, 2) <= Bag(1, 2, 2, 3)) #=> trueAliases: operator <=, operator ≤, operator ⊆
is_superset
self.is_superset(other)
self >= otherReturns true if every element of other also appears in self with a count at least as high (other is converted with .to_bag first if it isn't already a bag).
say(Bag(1, 2, 2, 3) >= Bag(1, 2)) #=> trueAliases: operator >=, operator ≥, operator ⊇
eq
self.eq(other)
self ≡ otherReturns true if self and other contain exactly the same elements with exactly the same counts. Handles circular references safely.
say(Bag(1, 2, 2) ≡ Bag(2, 1, 2)) #=> trueAliases: operator ≡, operator ==
ne
self.ne(other)
self ≠ otherReturns the logical negation of "eq".
say(Bag(1, 2) ≠ Bag(1, 2, 2)) #=> trueAliases: operator ≠, operator !=
ADDING ELEMENTS
append
self.append(*objects)
self << objAdds every one of objects to the bag, incrementing each one's count by 1, and returns self.
var bag = Bag(1, 2)
bag << 2
say(bag) #=> Bag(1, 2, 2)Aliases: add, push, operator <<
replace_pair
self.replace_pair(obj, n)Sets obj's count to exactly n (overwriting whatever it was before, or creating it if it wasn't present), and returns self. Unlike most other mutating methods here, this does not treat a non-positive n specially -- setting a count to 0 or less still leaves obj as a present key (so "has" and "elems" still count it), just contributing nothing (or a negative amount) if the bag is later expanded or summed.
var bag = Bag(1, 2, 2)
bag.replace_pair(2, 5)
say(bag) #=> Bag(1, 2, 2, 2, 2, 2)Aliases: set_kv, update_kv, update_pair
replace_pairs
self.replace_pairs(*pairs)Calls "replace_pair" once for each (obj, n) pair given (flattened, e.g. obj1, n1, obj2, n2, ...), and returns self.
var bag = Bag(1)
bag.replace_pairs(1, 3, 2, 2)
say(bag) #=> Bag(1, 1, 1, 2, 2)Aliases: set_kvs, update_kvs, update_pairs
add_pair
self.add_pair(obj, n)Increments obj's count by n (or sets it to n if obj wasn't already present), and returns self. Like "replace_pair", a non-positive n is not treated specially.
var bag = Bag(1, 2)
bag.add_pair(2, 3)
say(bag) #=> Bag(1, 2, 2, 2, 2)Aliases: add_kv, push_kv, append_kv, push_pair, append_pair
add_pairs
self.add_pairs(*pairs)Calls "add_pair" once for each (obj, n) pair given (flattened), and returns self.
var bag = Bag(1)
bag.add_pairs(2, 3, 3, 2)
say(bag) #=> Bag(1, 2, 2, 2, 3, 3)Aliases: add_kvs, push_kvs, append_kvs, push_pairs, append_pairs
REMOVING ELEMENTS
delete
self.delete(*objects)Decrements each one of objects by 1 (removing it entirely once its count reaches 0), and returns the list of removed values -- not the bag itself.
var bag = Bag(1, 1, 2, 3)
say(bag.delete(1, 2)) #=> (1, 2)
say(bag) #=> Bag(1, 3)Aliases: remove, discard
delete_all
self.delete_all(*objects)Removes every one of objects from the bag completely, regardless of count, and returns the removed occurrences (each value repeated according to its former count) -- not the bag itself.
var bag = Bag(1, 1, 2, 3)
say(bag.delete_all(1, 2)) #=> (1, 1, 2)
say(bag) #=> Bag(3)Aliases: remove_all, discard_all
delete_key
self.delete_key(obj)Removes obj from the bag completely, regardless of count, and returns the value that was removed (or nil if it wasn't present) -- not the bag itself.
var bag = Bag(1, 1, 2, 3)
say(bag.delete_key(1)) #=> 1
say(bag) #=> Bag(2, 3)Aliases: remove_key, discard_key
pop
self.popRemoves and returns an arbitrary element from the bag, decrementing its count by 1 (removing it entirely if its count was 1). Returns nil if the bag is empty.
var bag = Bag(1, 2, 2)
say(bag.pop) # some element of the bagshift
self.shiftRemoves and returns an arbitrary element from the bag, decrementing its count by 1 (removing it entirely if its count was 1). Returns nil if the bag is empty. As with "shift" in Sidef::Types::Set::Set, since a bag's keys have no defined order, this behaves identically to "pop".
var bag = Bag(1, 2, 2)
say(bag.shift) # some element of the bagdelete_if
self.delete_if(block)Removes every element (with all of its occurrences) for which block returns a truthy value, and returns self.
var bag = Bag(1, 2, 2, 3, 4)
bag.delete_if {|n| n.is_even }
say(bag) #=> Bag(1, 3)delete_first_if
self.delete_first_if(block)Finds the first element (in the bag's own unordered iteration order) for which block returns a truthy value, and removes just one occurrence of it (decrementing its count by 1, or removing it entirely if its count was 1). Returns self.
var bag = Bag(1, 2, 3, 4)
bag.delete_first_if {|n| n > 2 }
say(bag) #=> one of 3 or 4 removed, e.g. Bag(1, 2, 4)ITERATION
each
self.each(block)Calls block once for every occurrence of every element (respecting multiplicity), and returns self.
Bag(1, 2, 2).each {|n| say(n) }
# Prints: 1, 2, 2 (in some order)each_2d
self.each_2d(block)Like "each_2d" in Sidef::Types::Set::Set: iterates over a bag whose elements are themselves array-like, spreading each element's own contents as separate arguments to block, once per occurrence (respecting multiplicity). Returns self.
var pairs = Bag([1, "a"], [1, "a"], [2, "b"])
pairs.each_2d {|k, v| say("#{k}: #{v}") }
# Prints "1: a" twice and "2: b" once, in some ordereach_kv
self.each_kv(block)Calls block(value, count) once per distinct element (not once per occurrence), passing the element and its total count together. Returns self.
Bag(1, 2, 2, 3).each_kv {|k, v| say("#{k} appears #{v} times") }iter
self.iterReturns an iterator (a Block) over the bag's distinct elements (not its individual occurrences): each call to .run returns a 2-element Array of [value, count], or nil once exhausted.
var it = Bag(1, 2, 2).iter
say(it.run) #=> [1, 1] (in some order)
say(it.run) #=> [2, 2]TRANSFORMATION AND FILTERING
map
self.map(block)Returns a new bag where each distinct element is replaced by the result(s) of calling block on it once; the resulting element's count is increased by the original element's count (so if block returns more than one value for a given input, each one of them gets the full original count, not a split of it). If block is omitted, elements are kept as-is.
say(Bag(1, 2, 2).map {|n| n * 2 }) #=> Bag(2, 4, 4)map_2d
self.map_2d(block)Like "map", but for a bag whose elements are themselves array-like -- each element's own contents are spread as separate arguments to block.
var pairs = Bag([1, "a"], [2, "b"])
say(pairs.map_2d {|k, v| [k * 2, v] })map_kv
self.map_kv(block)Calls block(value, count) once per distinct element, expecting it to return a flattened list of zero or more (new_value, new_count) pairs. Each returned pair sets (not adds to) new_value's count in the result -- if two different original elements happen to produce the same new_value, the later one wins rather than the counts being summed. A pair whose new_count is zero or negative is silently dropped.
say(Bag(1, 2).map_kv {|k, v| [k + 1, v * 2] }) #=> Bag(2, 2, 3, 3)collect
self.collect(block)Calls block once per distinct element and repeats each result according to that element's original count, collecting everything into a plain Array -- not a new Bag. Because block only runs once per distinct element, all of that element's repeated copies in the result share the exact same computed value (relevant if block is non-deterministic).
say(Bag(1, 2, 2).collect {|n| n * 2 }) #=> [2, 4, 4] (an Array, order may vary)grep
self.grep(block)Returns a new bag keeping only the distinct elements for which block returns a truthy value, with their counts unchanged. If block is omitted, elements are kept based on their own truthiness.
say(Bag(1, 2, 2, 3, 4).grep {|n| n.is_even }) #=> Bag(2, 2, 4)Aliases: select
grep_2d
self.grep_2d(block)Like "grep", but for a bag whose elements are themselves array-like -- each element's own contents are spread as separate arguments to block.
var pairs = Bag([10, "a"], [20, "b"], [5, "c"])
say(pairs.grep_2d {|n, label| n > 8 }) #=> Bag([10, "a"], [20, "b"])grep_kv
self.grep_kv(block)Like "grep", but calls block(value, count) for each distinct element, passing its count alongside it.
say(Bag(1, 1, 2, 2, 2, 3).grep_kv {|k, v| v >= k }) #=> Bag(1, 1, 2, 2, 2)AGGREGATION AND PREDICATES
count
self.count(obj)
self.count(block)If given a plain value, returns obj's current count (0 if not present) -- unlike "count" in Sidef::Types::Set::Set, this is a true frequency, not just membership. If given a block, delegates entirely to "count_by".
say(Bag(1, 1, 2, 3).count(1)) #=> 2
say(Bag(1, 1, 2, 3).count(5)) #=> 0Aliases: get
count_by
self.count_by(block)Returns the total count (summed across matching distinct elements, respecting each one's own multiplicity) of every element for which block returns a truthy value. This is a single Number, not a grouped tally.
say(Bag(1, 2, 3, 4).count_by {|n| n.is_even }) #=> 2min
self.minReturns the minimum element in the bag, ignoring counts entirely (equivalent to looking only at the distinct keys).
say(Bag(5, 1, 3, 3).min) #=> 1min_by
self.min_by(block)Returns the distinct element for which block returns the smallest value, ignoring counts.
say(Bag(1, 2, 3).min_by {|n| -n }) #=> 3max
self.maxReturns the maximum element in the bag, ignoring counts entirely.
say(Bag(1, 5, 3, 3).max) #=> 5max_by
self.max_by(block)Returns the distinct element for which block returns the largest value, ignoring counts.
say(Bag(1, 2, 3).max_by {|n| -n }) #=> 1FREQUENCY INSPECTION
freq
self.freqReturns an Array of plain [value, count] 2-element arrays, one per distinct element. (Compare with "pairs", which returns the same information as proper Pair objects instead.)
say(Bag(1, 1, 2, 3).freq) #=> [[1, 2], [2, 1], [3, 1]]most_common
self.most_common(n)Returns an Array of the n distinct elements with the highest counts, sorted by count in descending order, as [value, count] pairs.
say(Bag(1, 2, 2, 3, 3, 3).most_common(2)) #=> [[3, 3], [2, 2]]Aliases: top
uniq
self.uniqReturns a new bag with every element's count reset to exactly 1 (i.e. behaving like the underlying set, but remaining a Bag).
say(Bag(1, 1, 2, 3, 3).uniq) #=> Bag(1, 2, 3)Aliases: unique
elems
self.elemsReturns the number of distinct elements in the bag (ignoring their counts).
say(Bag(1, 1, 2, 3).elems) #=> 3Aliases: keys_len
length
self.lengthReturns the total number of elements in the bag, counting multiplicities (the sum of every element's count).
say(Bag(1, 1, 2, 3).length) #=> 4Aliases: len, size
SORTING AND CONVERSION
sort
self.sort(block)Expands the bag (respecting counts, via "to_a") and returns the result sorted -- in natural order, or by block if given.
say(Bag(3, 1, 2, 2).sort) #=> [1, 2, 2, 3]
say(Bag(3, 1, 2).sort {|a, b| b <=> a }) #=> [3, 2, 1]sort_by
self.sort_by(block)Expands the bag (respecting counts) and returns the result sorted by the value block returns for each element.
say(Bag(1, 2, 3, 3).sort_by {|n| -n }) #=> [3, 3, 2, 1]to_a
self.to_aReturns an Array with every element of the bag, each one repeated according to its count.
say(Bag(1, 2, 2, 3).to_a) #=> [1, 2, 2, 3]Aliases: expand, to_array
to_list
self...Returns every element of the bag as a plain list (not wrapped in an Array), each one repeated according to its count -- the list-returning counterpart to "to_a".
var bag = Bag(1, 2, 2)
var list = bag...
say([list]) #=> [1, 2, 2] (order may vary)Aliases: operator ...
keys
self.keysReturns an Array of the bag's distinct elements, without their counts.
say(Bag(1, 1, 2, 3).keys) #=> [1, 2, 3]values
self.valuesReturns an Array of the counts for each distinct element (in the same order as "keys", so keys[i] and values[i] correspond to each other).
say(Bag(1, 1, 2, 3).values) #=> [2, 1, 1]pairs
self.pairsReturns an Array of Pair objects, one per distinct element, pairing each value with its count. (Compare with "freq", which returns the same information as plain 2-element arrays instead.)
say(Bag(1, 1, 2).pairs) #=> [Pair(1, 2), Pair(2, 1)]Aliases: kv
to_set
self.to_setConverts the bag to a plain Set, discarding all count information and keeping only the distinct elements.
say(Bag(1, 1, 2, 3).to_set) #=> Set(1, 2, 3)to_bag
self.to_bagReturns self unchanged (a Bag is already a bag).
var bag = Bag(1, 2, 3)
say(bag.to_bag == bag) #=> trueclone
self.cloneReturns a shallow copy of the bag: a new bag with the same distinct elements and counts. If an element's own value is itself a reference (e.g. an Array), that nested reference is shared between the original and the clone, not copied.
var a = Bag(1, 2, 3)
var b = a.clone
b << 4
say(a) #=> Bag(1, 2, 3)
say(b) #=> Bag(1, 2, 3, 4)join
self.join(sep)Expands the bag (respecting counts, via "to_a") and joins the elements into a String, separated by sep.
say(Bag(1, 2, 2, 3).join(", ")) #=> "1, 2, 2, 3"INSPECTION
dump
self.dumpReturns a String representation of the bag, in the format Bag(element, element, ...), with each element repeated according to its count. Each element is rendered by calling its own dump method if it has one (falling back to plain stringification, or nil, otherwise), and a circular reference back to the bag itself is shown as an abbreviated placeholder rather than expanded infinitely.
say(Bag(1, 2, 2).dump) #=> "Bag(1, 2, 2)"get_value
self.get_valueReturns the bag's contents as a plain Perl array reference, with every nested Sidef object recursively unwrapped to its own raw underlying value (via its own get_value) and repeated according to its count. Circular references are handled by reusing the same array reference for a bag already seen during the recursion. This is a low-level method, mainly useful for interop rather than everyday Sidef code.
EXAMPLES
Word frequency counter
var text = "the quick brown fox jumps over the lazy dog the fox runs"
var bag = Bag(text.split(' ')...)
say(bag.most_common(2)) #=> [["the", 3], ["fox", 2]]
say(bag.count("the")) #=> 3
say(bag.elems) #=> 9 # distinct words
say(bag.len) #=> 12 # total wordsBuilding up counts incrementally
var votes = Bag()
votes.add_pair("cats", 5)
votes.add_pair("dogs", 3)
votes.add_pair("cats", 2) # increments, doesn't overwrite
say(votes.freq) #=> [["cats", 7], ["dogs", 3]]
say(votes.most_common(1)) #=> [["cats", 7]]Multiset algebra for inventory tracking
var have = Bag("apple", "apple", "banana", "banana", "banana")
var used = Bag("apple", "banana")
var remaining = have - used
say(remaining) #=> Bag(apple, banana, banana)
var restocked = remaining | Bag("apple", "apple")
say(restocked) #=> Bag(apple, apple, banana, banana)