org.jrabbit.base.data.structures
Class LockingList<T>

java.lang.Object
  extended by org.jrabbit.base.data.structures.LockingList<T>
Type Parameters:
T - The type of object to hold in the list.
All Implemented Interfaces:
java.lang.Iterable<T>, Accepter<T>, Container<T>, Remover<T>
Direct Known Subclasses:
DefaultLayer

public class LockingList<T>
extends java.lang.Object
implements Container<T>

This class is supposed to handle large, dynamic amounts of objects and be able to iterate through them very quickly without being disturbed by changes to its structure. Duplicate entries are not supported. Random access is also not supported. At its heart, LockingList is a LinkedList. However, the weakness in Linked Lists is that removal operations are inefficient when compared to add methods - it has to iterate through the entire list, checking each node. To attempt to combat this, when objects are added to the list, a HashMap keys the object reference to the node that contains it. Thereafter, when remove() is called, it finds the node from the HashMap and does a quick and easy cull. It's a little extreme to make a custom data structure for a single purpose, but all the common "fast" data structures I know of have some flaws in a gaming environment (especially since I wanted to remember order of addition). ArrayList is fast, but it takes time to resize. LinkedLists are fast and highly dynamic when adding, but removal requires a search through the list. LinkedHashMaps have some O(1) operations, but have needless overhead. Adding to the mix is the fact that I needed something that could be modified during iteration without causing errors. Ultimately, I decided to marry a HashMap and a LinkedList. The result is a very stripped down data structure that, nevertheless, performs very well. When no changes are occurring, it performs at LinkedList speed (which is quite fast), and even when the list is being rapidly changed, its operations tend towards O(1) complexity (and are fairly fast at that).

Author:
Chris Molini

Nested Class Summary
protected  class LockingList.UList
          Provides a singly-linked list implementation to dynamically store a large list of objects for quick iteration.
 
Field Summary
protected  LockingList.UList addCache
          A list to cache addition operations.
protected  LockingList.UList adding
          This reference is meant to switch between main and toAdd.
protected  boolean clear
          When the list is locked, if a clear() is demanded, we cannot destroy the list immediately - we need to remember it until we unlock the list (and immediately clear the list on release).
protected  LockingList.UList main
          The currently active list of items.
protected  LockingList.UList removalCache
          Likewise, this caches removal operations.
protected  LockingList.UList removing
          Similarly, this reference handles directing removal operations.
 
Constructor Summary
LockingList()
          Creates a default, unlocked, empty list.
 
Method Summary
 void add(LockingList<T> list)
          Handles adding an entire list of objects of the same generic type.
 void add(T... objects)
          Attempts to add every supplied object.
 boolean add(T object)
          Adds an object or caches the operation.
 void clear()
          Clears the list if unlocked.
 boolean contains(T object)
          Checks if an object is on the list.
 boolean isEmpty()
          Returns whether or not the active list is empty.
 java.util.Iterator<T> iterator()
          Allows iteration through the LockingList in the usual manner.
 void lock()
          Redirects removal and addition operations, causing the active list to become unchangeable through normal methods.
 boolean locked()
          Checks to see if the list is caching changes.
 int predictedSize()
          Returns the predicted size of the list.
 void remove(LockingList<T> list)
          Handles removing an entire list of objects of the same type.
 void remove(T... objects)
          Attempts to remove the supplied list of objects.
 boolean remove(T object)
          Removes an object or caches the operation.
 int size()
          Returns the size of the main list.
 void unlock()
          If locked, redirects removal and addition to the main list, and causes any cached operations to be applied to the main list.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

main

protected LockingList.UList main
The currently active list of items. Because iteration runs through the actual list of objects, we cannot safely allow this list to change while we are going through it. Therefore, we need to cache changes and apply them after the list is safe again.


addCache

protected LockingList.UList addCache
A list to cache addition operations. When the list is "locked," all add() operations are applied to this.


removalCache

protected LockingList.UList removalCache
Likewise, this caches removal operations. NOTE: When we are unlocked, we want to simply remove objects from the main list, but when we lock the list we need to add them to a storage structure. So, we modify this list on instantiation to provide that functionality.


adding

protected LockingList.UList adding
This reference is meant to switch between main and toAdd. When locked, the list automatically (without unnecessary checks) delegates addition operations.


removing

protected LockingList.UList removing
Similarly, this reference handles directing removal operations.


clear

protected boolean clear
When the list is locked, if a clear() is demanded, we cannot destroy the list immediately - we need to remember it until we unlock the list (and immediately clear the list on release).

Constructor Detail

LockingList

public LockingList()
Creates a default, unlocked, empty list.

Method Detail

add

public boolean add(T object)
Adds an object or caches the operation.

Specified by:
add in interface Accepter<T>
Parameters:
object - The object to add.
Returns:
True if the add succeeded, false if not.

add

public void add(T... objects)
Attempts to add every supplied object.

Specified by:
add in interface Accepter<T>
Parameters:
objects - The objects to add.

add

public void add(LockingList<T> list)
Handles adding an entire list of objects of the same generic type. if the other list is locked, only the main list is applied. Pending additions and removals do not factor in.

Parameters:
list - the list of objects to add.

remove

public boolean remove(T object)
Removes an object or caches the operation.

Specified by:
remove in interface Remover<T>
Parameters:
object - The object to remove.
Returns:
If locked, automatically returns false. If unlocked, returns whether or not the removal was successful.

remove

public void remove(T... objects)
Attempts to remove the supplied list of objects.

Specified by:
remove in interface Remover<T>
Parameters:
objects - The objects to remove.

remove

public void remove(LockingList<T> list)
Handles removing an entire list of objects of the same type. If the other list is locked, only the active list is applied. Pending additions and removals do not factor in.

Parameters:
list - The list of objects we wish to remove.

contains

public boolean contains(T object)
Checks if an object is on the list.

Specified by:
contains in interface Container<T>
Parameters:
object - The object to check for.
Returns:
If the object is on the list.

clear

public void clear()
Clears the list if unlocked. If locked, it clears the current state of toAdd and toRemove, and remembers that it should clear the main list on release().

Specified by:
clear in interface Container<T>

size

public int size()
Returns the size of the main list. If the list is locked, there is no concession to pending adds and removals.

Specified by:
size in interface Container<T>
Returns:
How many elements are in the active list.

predictedSize

public int predictedSize()
Returns the predicted size of the list. If the list is not locked, this returns the same value of size(), but if it is, it returns the estimated final size after pending operations have been resolved. NOTE: This list can be inaccurate. It assumes that all pending add and remove operations will be successful, which may not be the case (depending on whether the objects involved in the operations are on the list or not).

Returns:
The estimate for list size when it is unlocked.

isEmpty

public boolean isEmpty()
Returns whether or not the active list is empty. Possibly inaccurate if the list is locked.

Returns:
If the active list has elements.

lock

public void lock()
Redirects removal and addition operations, causing the active list to become unchangeable through normal methods.


unlock

public void unlock()
If locked, redirects removal and addition to the main list, and causes any cached operations to be applied to the main list.


locked

public boolean locked()
Checks to see if the list is caching changes.

Returns:
Whether or not operations apply to the main list.

iterator

public java.util.Iterator<T> iterator()
Allows iteration through the LockingList in the usual manner. Auto-locks the list.

Specified by:
iterator in interface java.lang.Iterable<T>
Returns:
The iterator through the main list.