public class Bag extends java.lang.Object implements java.util.Collection, java.io.Serializable, java.lang.Cloneable, Indexed
By providing direct access to the array, Bags are about three and a half times faster than ArrayLists (whose get/set methods unfortunately at present contain un-inlinable range bounds checks) and four times faster than Vectors (whose methods additionally are synchronized). Even Bag's built-in get() and set() methods, complete with range bounds checks, are twice the speed of ArrayLists. To get faster than a Bag, you'd have to go to a raw fixed-length array of the specific class type of your objects. Accessing a Bag's Object array and casting its Objects into the appropriate class is about 50% slower than accessing a fixed-length array of that class in the first place.
Bag is not synchronized, and so should not be accessed from different threads without locking on it or some appropriate lock object first. Bag also has an unusual, fast method for removing objects called remove(...), which removes the object simply by swapping the topmost object into its place. This means that after remove(...) is called, the Bag may no longer have the same order (hence the reason it's called a "Bag" rather than some variant on "Vector" or "Array" or "List"). You can guarantee order by calling removeNondestructively(...) instead if you wish, but this is O(n) in the worst case.
Bags provide iterators but you are strongly encouraged to just access the array instead. Iterators are slow. Bag's iterator performs its remove operation by calling removeNondestructively(). Like array access, iterator usage is undefined if objects are placed into the Bag or removed from the Bag in the middle of the iterator usage (except by using the iterator's remove operation of course).
Constructor and Description |
---|
Bag() |
Bag(Bag other)
Adds the objects from the other Bag without copying them.
|
Bag(java.util.Collection other)
Creates a Bag with the given elements.
|
Bag(int capacity)
Creates a Bag with a given initial capacity.
|
Bag(java.lang.Object[] other)
Creates a Bag with the given elements.
|
Modifier and Type | Method and Description |
---|---|
boolean |
add(java.lang.Object obj) |
boolean |
addAll(Bag other) |
boolean |
addAll(java.util.Collection other) |
boolean |
addAll(int index,
Bag other) |
boolean |
addAll(int index,
java.util.Collection other) |
boolean |
addAll(int index,
java.lang.Object[] other) |
boolean |
addAll(java.lang.Object[] other) |
void |
clear()
Removes all objects in the Bag.
|
java.lang.Object |
clone() |
java.lang.Class |
componentType()
Always returns null.
|
boolean |
contains(java.lang.Object o) |
boolean |
containsAll(java.util.Collection c) |
void |
copyIntoArray(int fromStart,
java.lang.Object[] to,
int toStart,
int len)
Copies 'len' elements from the Bag into the provided array.
|
void |
fill(java.lang.Object o)
Replaces all elements in the bag with the provided object.
|
java.lang.Object |
get(int index) |
java.lang.Object |
getValue(int index)
identical to get(index)
|
boolean |
isEmpty() |
java.util.Iterator |
iterator()
NOT fail-fast.
|
java.lang.Object |
pop()
Returns null if the Bag is empty, else removes and returns the topmost object.
|
boolean |
push(java.lang.Object obj)
Synonym for add(obj) -- stylistically, you should add instead unless you
want to think of the Bag as a stack.
|
java.lang.Object |
remove(int index)
Removes the object at the given index, moving the topmost object into its position.
|
boolean |
remove(java.lang.Object o)
Removes the object, moving the topmost object into its position.
|
boolean |
removeAll(java.util.Collection c) |
boolean |
removeMultiply(java.lang.Object o)
Removes multiple instantiations of an object
|
java.lang.Object |
removeNondestructively(int index)
Removes the object at the given index, shifting the other objects down.
|
boolean |
removeNondestructively(java.lang.Object o)
Removes the object, shifting the other objects down.
|
void |
resize(int toAtLeast)
Resizes the internal array to at least the requested size.
|
boolean |
retainAll(java.util.Collection c) |
void |
reverse()
Reverses order of the elements in the Bag
|
java.lang.Object |
set(int index,
java.lang.Object element) |
java.lang.Object |
setValue(int index,
java.lang.Object element)
identical to set(index, element)
|
void |
shrink(int desiredLength)
Resizes the objs array to max(numObjs, desiredLength), unless that value is greater than or equal to objs.length,
in which case no resizing is done (this operation only shrinks -- use resize() instead).
|
void |
shuffle(MersenneTwisterFast random)
Shuffles (randomizes the order of) the Bag
|
void |
shuffle(java.util.Random random)
Shuffles (randomizes the order of) the Bag
|
int |
size() |
void |
sort()
Sorts the bag under the assumption that all objects stored within are Comparable.
|
void |
sort(java.util.Comparator c)
Sorts the bag according to the provided comparator
|
java.lang.Object[] |
toArray() |
java.lang.Object[] |
toArray(java.lang.Object[] o) |
java.lang.Object |
top()
Returns null if the Bag is empty, else returns the topmost object.
|
equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
public Bag()
public Bag(int capacity)
public Bag(Bag other)
public Bag(java.lang.Object[] other)
public Bag(java.util.Collection other)
public int size()
public boolean isEmpty()
isEmpty
in interface java.util.Collection
public boolean addAll(java.util.Collection other)
addAll
in interface java.util.Collection
public boolean addAll(int index, java.util.Collection other)
public boolean addAll(java.lang.Object[] other)
public boolean addAll(int index, java.lang.Object[] other)
public boolean addAll(Bag other)
public boolean addAll(int index, Bag other)
public java.lang.Object clone() throws java.lang.CloneNotSupportedException
clone
in class java.lang.Object
java.lang.CloneNotSupportedException
public void resize(int toAtLeast)
public void shrink(int desiredLength)
public java.lang.Object top()
public java.lang.Object pop()
public boolean push(java.lang.Object obj)
public boolean add(java.lang.Object obj)
add
in interface java.util.Collection
public boolean contains(java.lang.Object o)
contains
in interface java.util.Collection
public boolean containsAll(java.util.Collection c)
containsAll
in interface java.util.Collection
public java.lang.Object get(int index)
public java.lang.Object getValue(int index)
public java.lang.Object set(int index, java.lang.Object element)
public java.lang.Object setValue(int index, java.lang.Object element)
public boolean removeAll(java.util.Collection c)
removeAll
in interface java.util.Collection
public boolean retainAll(java.util.Collection c)
retainAll
in interface java.util.Collection
public java.lang.Object removeNondestructively(int index)
public boolean removeNondestructively(java.lang.Object o)
public boolean remove(java.lang.Object o)
remove
in interface java.util.Collection
public boolean removeMultiply(java.lang.Object o)
public java.lang.Object remove(int index)
public void clear()
clear
in interface java.util.Collection
public java.lang.Object[] toArray()
toArray
in interface java.util.Collection
public java.lang.Object[] toArray(java.lang.Object[] o)
toArray
in interface java.util.Collection
public void copyIntoArray(int fromStart, java.lang.Object[] to, int toStart, int len)
public java.util.Iterator iterator()
iterator
in interface java.lang.Iterable
iterator
in interface java.util.Collection
public java.lang.Class componentType()
componentType
in interface Indexed
public void sort(java.util.Comparator c)
public void sort()
public void fill(java.lang.Object o)
public void shuffle(java.util.Random random)
public void shuffle(MersenneTwisterFast random)
public void reverse()