sim.util
Class Bag

java.lang.Object
  extended by sim.util.Bag
All Implemented Interfaces:
java.io.Serializable, java.lang.Cloneable, java.lang.Iterable, java.util.Collection, Indexed

public class Bag
extends java.lang.Object
implements java.util.Collection, java.io.Serializable, java.lang.Cloneable, Indexed

Maintains a simple array (objs) of Objects and the number of objects (numObjs) in the array (the array can be bigger than this number). Unlike Vector or ArrayList, Bag is designed to encourage direct access of the array. If you access the objects directly, they are stored in positions [0 ... numObjs-1]. If you wish to extend the array, you should call the resize method.

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).

See Also:
Serialized Form

Field Summary
 int numObjs
           
 java.lang.Object[] objs
           
 
Constructor Summary
Bag()
           
Bag(Bag other)
          Adds the objects from the other Bag without copying them.
Bag(int capacity)
          Creates a Bag with a given initial capacity.
 
Method Summary
 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)
           
 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 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.
 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(java.util.Comparator c)
          Sorts the bag according to the provided comparator
protected  void throwIndexOutOfBoundsException(int index)
           
 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.
 
Methods inherited from class java.lang.Object
equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 
Methods inherited from interface java.util.Collection
equals, hashCode
 

Field Detail

objs

public java.lang.Object[] objs

numObjs

public int numObjs
Constructor Detail

Bag

public Bag()

Bag

public Bag(int capacity)
Creates a Bag with a given initial capacity.


Bag

public Bag(Bag other)
Adds the objects from the other Bag without copying them. The size of the new Bag is the minimum necessary size to hold the objects.

Method Detail

size

public int size()
Specified by:
size in interface java.util.Collection
Specified by:
size in interface Indexed

isEmpty

public boolean isEmpty()
Specified by:
isEmpty in interface java.util.Collection

addAll

public boolean addAll(java.util.Collection other)
Specified by:
addAll in interface java.util.Collection

addAll

public boolean addAll(int index,
                      java.util.Collection other)

addAll

public boolean addAll(int index,
                      java.lang.Object[] other)

addAll

public boolean addAll(Bag other)

addAll

public boolean addAll(int index,
                      Bag other)

clone

public java.lang.Object clone()
                       throws java.lang.CloneNotSupportedException
Overrides:
clone in class java.lang.Object
Throws:
java.lang.CloneNotSupportedException

resize

public void resize(int toAtLeast)
Resizes the internal array to at least the requested size.


shrink

public 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). This is an O(n) operation, so use it sparingly.


top

public java.lang.Object top()
Returns null if the Bag is empty, else returns the topmost object.


pop

public java.lang.Object pop()
Returns null if the Bag is empty, else removes and returns the topmost object.


push

public 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.


add

public boolean add(java.lang.Object obj)
Specified by:
add in interface java.util.Collection

contains

public boolean contains(java.lang.Object o)
Specified by:
contains in interface java.util.Collection

containsAll

public boolean containsAll(java.util.Collection c)
Specified by:
containsAll in interface java.util.Collection

get

public java.lang.Object get(int index)

getValue

public java.lang.Object getValue(int index)
identical to get(index)

Specified by:
getValue in interface Indexed

set

public java.lang.Object set(int index,
                            java.lang.Object element)

setValue

public java.lang.Object setValue(int index,
                                 java.lang.Object element)
identical to set(index, element)

Specified by:
setValue in interface Indexed

removeAll

public boolean removeAll(java.util.Collection c)
Specified by:
removeAll in interface java.util.Collection

retainAll

public boolean retainAll(java.util.Collection c)
Specified by:
retainAll in interface java.util.Collection

removeNondestructively

public java.lang.Object removeNondestructively(int index)
Removes the object at the given index, shifting the other objects down.


remove

public boolean remove(java.lang.Object o)
Removes the object, moving the topmost object into its position.

Specified by:
remove in interface java.util.Collection

removeMultiply

public boolean removeMultiply(java.lang.Object o)
Removes multiple instantiations of an object


remove

public java.lang.Object remove(int index)
Removes the object at the given index, moving the topmost object into its position.


throwIndexOutOfBoundsException

protected void throwIndexOutOfBoundsException(int index)

clear

public void clear()
Removes all objects in the Bag. This is done by clearing the internal array but not replacing it with a new, smaller one.

Specified by:
clear in interface java.util.Collection

toArray

public java.lang.Object[] toArray()
Specified by:
toArray in interface java.util.Collection

toArray

public java.lang.Object[] toArray(java.lang.Object[] o)
Specified by:
toArray in interface java.util.Collection

iterator

public java.util.Iterator iterator()
NOT fail-fast. Use this method only if you're concerned about accessing numObjs and objs directly.

Specified by:
iterator in interface java.lang.Iterable
Specified by:
iterator in interface java.util.Collection

componentType

public java.lang.Class componentType()
Always returns null. This method is to adhere to Indexed.

Specified by:
componentType in interface Indexed

sort

public void sort(java.util.Comparator c)
Sorts the bag according to the provided comparator


fill

public void fill(java.lang.Object o)
Replaces all elements in the bag with the provided object.


shuffle

public void shuffle(java.util.Random random)
Shuffles (randomizes the order of) the Bag


shuffle

public void shuffle(MersenneTwisterFast random)
Shuffles (randomizes the order of) the Bag


reverse

public void reverse()
Reverses order of the elements in the Bag