Bag

Bag is a counted set (a multiset; NSCountedSet or CFBag in shape). Like a Set, it holds each member once; unlike one, it counts how many times each was added. Adding a member again raises its count, remove lowers it, and the member leaves when its count reaches zero. From 0.72.

#import "Bag.xc"           // or the Foundation umbrella

Overview

Bag* words = new Bag();
words.add(String.withCString("the"));
words.add(String.withCString("cat"));
words.add(String.withCString("the"));
Stdio.printf("%d words, %d different; 'the' %d times\n",
             words.totalCount(), words.uniqueCount(),
             words.countFor(String.withCString("the")));   // 3 words, 2 different; 'the' 2 times

Membership is a Set’s: a member’s hash() picks its slot and equals() settles collisions. Object’s own hash and equals are its identity, so a bag of plain objects counts references (a tally of tokens, “how many of these are selected”), while a String or a Number is counted by value, as in the example above.

Storage is Set’s table with a count beside each member: open addressing over a power-of-two capacity, so add, countFor and remove are close to O(1). A dense insertion order makes memberAt and countAt O(1) and walks the members in the order they first arrived; removing one closes the gap.

Ownership (ARC). The bag holds one strong reference to each distinct member, however many times it was added, and releases it when the member leaves.

Conforms to

Enumerable: enumLength / enumAt, so for (Object* m in bag) walks the distinct members.

Topics

Adding · add · addTimes

Removing · remove · removeAllOf · removeAll

Counting · countFor · contains · totalCount · uniqueCount

Members in order · memberAt · countAt

Iterating · enumLength · enumAt

Adding

add

void add(Object* o)

One more of o. A member not yet in the bag joins it with a count of one and is retained. A null o is ignored.

addTimes

void addTimes(Object* o, i32 n)

n more of o; nothing when n is zero or negative.

↑ Topics

Removing

remove

void remove(Object* o)

One fewer of o. At zero the member leaves the bag and is released; a member not in the bag is ignored.

removeAllOf

void removeAllOf(Object* o)

Every one of o: the member leaves whatever its count.

removeAll

void removeAll(void)

Empties the bag, releasing every member.

↑ Topics

Counting

countFor

i32 countFor(Object* o)

How many of o the bag holds: 0 when it is not a member.

contains

bool contains(Object* o)

Whether o is a member (its count is at least one).

totalCount

i32 totalCount(void)

The sum of every member’s count.

uniqueCount

i32 uniqueCount(void)

The number of distinct members.

↑ Topics

Members in order

memberAt

Object* memberAt(i32 i)

The i-th distinct member, in the order members first arrived; null when i is out of range.

countAt

i32 countAt(i32 i)

The count of the i-th distinct member; 0 when i is out of range.

↑ Topics

Iterating

enumLength

u32 enumLength(void)

The number of distinct members (u16 on the 6502), for for-in.

enumAt

Object* enumAt(u32 i)

The same as memberAt, for for-in.

↑ Topics