It's actually not weird at all. A bag is also called a "multiset". It's like a set because it stores objects with its own internal organization and has no guarantee on the order of elements returned by an iterator. It differs from a set because it lets you store multiple copies of each object. Adding an object increases the count and removing one decreases it. You could implement something like this so that internally a bag stores multiple copies of each object and keeps one reference for each one; Or, you could implement a bag such that it stored one reference to each instance of an object and an integer counter to keep track of each additional insertion of the same object.
Like I explained in my "tutorial" on the
subject, bags/multisets can also be implemented similarly to a map. You could almost do the same thing using a Map, but it would require a lot of extra work on the user's end. (Get a value, add one, put the new value back in for adding objects. And getting a value, subtracting one, removing a key-value pair if zero, putting the new value back in otherwise. It requires a lot of extra work and is a lot easier to implement as a separate class.) If you take a look at the Apache Commons implementations, they include a HashBag and a TreeBag, which are analogous to HashSets and TreeSets and HashMaps and TreeMaps. That's why I tried to be precise and say "Array Backed Bag." Kappa's post did not reference that fact.
An array based bag functions the same way, but there are trade offs.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| String s12 = "12", s23 = "23", s1 = "1", s3 = "3";
Bag<String> bag1 = new MyArrayBag<String>(2);
Bag<String> bag2 = new HashBag<String>(2);
Bag<String> bag;
String a = s12 + s3, b = s1 + s23;
bag1.add(a);
bag1.add(b);
bag2.add(a);
bag2.add(b);
for(String s : bag1)
{
System.out.println(s.equals(a) || s.equals(b));
System.out.println("a: " + (s == a) + " b: " + (s == b));
System.out.println();
}
for(String s : bag2)
{
System.out.println(s.equals(a) || s.equals(b));
System.out.println("a: " + (s == a) + " b: " + (s == b));
System.out.println();
}
|
The Apache implementation uses the .equals method of your class to detect duplicates, like Java collections do. It considers objects identical if equals returns true. It doesn't define buckets/ranges, but you could accomplish something like that if you wrote equals a certain way. Mine and Kappa's implementations do not use .equals. (All three sources implement a bag that either violates the Collections interface or could not implement it without doing so.) The array based version is usually more useful in game programming, especially if you only keep one copy or don't override equals.
You might use array based bags in your game loop or as generic containers as an alternative to ArrayLists or HashSets. You might use a HashBag to keep count of stackable items in a player's inventory, calling add(obj) or add(obj, count) for every item picked up and remove(obj) for every item used.
The array based version will have faster adds and removes. It can provide O(n) based contains(obj) and count(obj) function while other implementations could provide O(1) or O(log n) time. The array based implementations will take less space if you keep one copy or only a few copies, but the others will take less space if you have many duplicates.
