All Packages  Class Hierarchy  This Package  Previous  Next  Index

Class com.objectspace.jgl.Deque

java.lang.Object
   |
   +----com.objectspace.jgl.Deque

public class Deque

extends Object

implements Sequence

Deques are useful in circumstances where order, compact storage, and fast insertion at extremeties is important. A Deque is ideal for implementing any kind of FIFO structure. If a strict FIFO structure is required that does not allow index-based access, then you should consider using a Queue adaptor with a Deque as the underlying container. If you require very fast insertion near the middle of a sequential structure, then consider using a List instead of a Deque.

The implementation allocates storage for a Deque's elements in 4K blocks (a usual page size) of contiguous memory, and use an array to keep track of a deque's blocks. When a Deque is constructed, it has no associated storage. As elements are added, blocks of storage are added to the beginning or the end of the deque as necessary. A result of this architecture is that items may be inserted very efficiently near either extremity. Once a block has been allocated to a Deque, it is not deallocated until the Deque is destroyed. Insertions are careful to expand the Deque in the direction that involves the least amount of copying. Removals take similar precautions.

If an insertion causes reallocation, all iterators and references are invalidated; otherwise, iterators and references are only invalidated if an item is not inserted at an extremity. In the worst cast, inserting a single element into a Deque takes linear time in the minimum of the distance from the insertion point to the beginning of the Deque and the distance from the insertion point to the end of the Deque. Inserting a single element either at the beginning or end of a Deque always takes constant time.

If the first or last item is removed, all iterators and references remain valid; if any other item is removed, all iterators and references are invalidated.

See Also:

Sequence, Deque examples

Deque()

Construct myself to be an empty Deque.

Deque(Deque)

Construct myself to be a shallow copy of an existing Deque.

Deque(int)

Construct myself to contain a specified number of null elements.

Deque(int, Object)

Construct myself to contain a specified number of elements set to a particular object.

add(Object)

Add an object after my last element and return null.

at(int)

Return the element at the specified index.

back()

Return my last item.

begin()

Return an iterator positioned at my first item.

clear()

Remove all of my elements.

clone()

Return a shallow copy of myself.

contains(Object)

Return true if I contain a particular object.

copy(Deque)

Become a shallow copy of an existing Deque.

count(int, int, Object)

Return the number of objects within a particular range of indices that match a particular value.

count(Object)

Return the number of objects that match a particular value.

elements()

Return an Enumeration of my components

end()

Return an iterator positioned immediately after my last item.

equals(Deque)

Return true if I contain the same items in the same order as another Deque.

equals(Object)

Return true if I'm equal to another object.

finish()

Return an iterator positioned immediately afer my last item.

front()

Return my first item.

hashCode()

Return my hash code for support of hashing containers

indexOf(int, int, Object)

Return the index of the first object within a range of indices that match a particular object, or -1 if the object is not found.

indexOf(Object)

Return the index of the first object that matches a particular value, or -1 if the object is not found.

insert(DequeIterator, BidirectionalIterator, BidirectionalIterator)

Insert a sequence of objects at a particular location.

insert(DequeIterator, int, Object)

Insert multiple objects at a particular position.

insert(DequeIterator, Object)

Insert an object at a particular position and return an iterator positioned at the new element.

insert(int, BidirectionalIterator, BidirectionalIterator)

Insert a sequence of objects at a particular index.

insert(int, int, Object)

Insert multiple objects at a particular index.

insert(int, Object)

Insert an object at a particular index and return an iterator positioned at the new element.

isEmpty()

Return true if I contain no entries.

maxSize()

Return the maximum number of entries that I can contain.

popBack()

Remove and return my last element.

popFront()

Remove and return my first element.

pushBack(Object)

Add an object after my last element.

pushFront(Object)

Insert an object in front of my first element.

put(int, Object)

Set the element at the specified index to a particular object.

remove(Enumeration)

Remove the element at a particular position.

remove(Enumeration, Enumeration)

Remove the elements in the range [ first..last ).

remove(int)

Remove the element at a particular index.

remove(int, int)

Remove the elements within a range of indices.

remove(int, int, Object)

Remove all elements within a range of indices that match a particular object and return the number of objects that were removed.

remove(Object)

Remove all elements that match a particular object and return the numbers of objects that were removed.

remove(Object, int)

Remove at most a given number of elements that match a particular object and return the number of objects that were removed.

replace(int, int, Object, Object)

Replace all elements within a range of indices that match a particular object with a new value and return the number of objects that were replaced.

replace(Object, Object)

Replace all elements that match a particular object with a new value and return the number of objects that were replaced.

size()

Return the number of entries that I contain.

start()

Return an iterator positioned at my first item

swap(Deque)

Swap my contents with another Deque.

toString()

Return a string that describes me.

 public Deque()

Construct myself to be an empty Deque.

 public Deque(int size)

Construct myself to contain a specified number of null elements.

Parameters:

size - The number of elements to contain.

Throws: IllegalArgumentException

If size is negative.

 public Deque(int size,
              Object object)

Construct myself to contain a specified number of elements set to a particular object.

Parameters:

size - The number of elements to contain.

object - The initial value of each element.

Throws: IllegalArgumentException

If size is negative.

 public Deque(Deque deque)

Construct myself to be a shallow copy of an existing Deque.

Parameters:

deque - The Deque to copy.

 public synchronized Object clone()

Return a shallow copy of myself.

Overrides:

clone in class Object

 public boolean equals(Object object)

Return true if I'm equal to another object.

Parameters:

object - The object to compare myself against.

Overrides:

equals in class Object

 public synchronized boolean equals(Deque deque)

Return true if I contain the same items in the same order as another Deque. Use equals() to compare the individual elements.

Parameters:

deque - The Deque to compare myself against.

 public synchronized int hashCode()

Return my hash code for support of hashing containers

Overrides:

hashCode in class Object

 public synchronized String toString()

Return a string that describes me.

Overrides:

toString in class Object

 public synchronized void copy(Deque deque)

Become a shallow copy of an existing Deque.

Parameters:

deque - The Deque that I shall become a shallow copy of.

 public boolean isEmpty()

Return true if I contain no entries.

 public int size()

Return the number of entries that I contain.

 public int maxSize()

Return the maximum number of entries that I can contain.

 public synchronized Object add(Object object)

Add an object after my last element and return null. This function is a synonym for pushBack().

Parameters:

object - The object to add.

 public void pushBack(Object object)

Add an object after my last element.

Parameters:

The - object to add.

 public synchronized void pushFront(Object object)

Insert an object in front of my first element.

Parameters:

object - The object to insert.

 public synchronized Object popFront()

Remove and return my first element.

Throws: InvalidOperationException

If the Deque is empty.

 public synchronized Object popBack()

Remove and return my last element.

Throws: InvalidOperationException

If the Deque is empty.

 public synchronized void clear()

Remove all of my elements.

 public synchronized Enumeration elements()

Return an Enumeration of my components

 public synchronized DequeIterator begin()

Return an iterator positioned at my first item.

 public synchronized DequeIterator end()

Return an iterator positioned immediately after my last item.

 public ForwardIterator start()

Return an iterator positioned at my first item

 public ForwardIterator finish()

Return an iterator positioned immediately afer my last item.

 public synchronized Object front()

Return my first item.

Throws: InvalidOperationException

If the Deque is empty.

 public synchronized Object back()

Return my last item.

Throws: InvalidOperationException

If the Deque is empty.

 public synchronized Object at(int index)

Return the element at the specified index.

Parameters:

index - The index.

Throws: IndexOutOfBoundsException

If the index is invalid.

 public synchronized void put(int index,
                              Object object)

Set the element at the specified index to a particular object.

Parameters:

index - The index.

object - The object.

Throws: IndexOutOfBoundsException

If the index is invalid.

 public synchronized void swap(Deque deque)

Swap my contents with another Deque.

Parameters:

deque - The Deque that I will swap my contents with.

 public synchronized Object remove(int index)

Remove the element at a particular index.

Parameters:

index - The index of the element to remove.

Returns:

The object removed.

Throws: IndexOutOfBoundsException

If the index is invalid.

 public synchronized Object remove(Enumeration e)

Remove the element at a particular position.

Parameters:

e - An Enumeration positioned at the element to remove.

Returns:

The object removed.

Throws: IllegalArgumentException

if the Enumeration isn't a DequeIterator for this Deque object.

 public synchronized int remove(int first,
                                int last)

Remove the elements within a range of indices.

Parameters:

first - The index of the first element to remove.

last - The index of the last element to remove.

Returns:

The number of elements removed.

Throws: IndexOutOfBoundsException

If either index is invalid.

 public synchronized int remove(Enumeration first,
                                Enumeration last)

Remove the elements in the range [ first..last ).

Parameters:

first - An Enumeration positioned at the first element to remove.

last - An Enumeration positioned immediately after the last element to remove.

Returns:

The number of elements removed.

Throws: IllegalArgumentException

if the Enumeration isn't a DequeIterator for this Deque object.

 public synchronized DequeIterator insert(int index,
                                          Object object)

Insert an object at a particular index and return an iterator positioned at the new element.

Parameters:

index - The index of the element that the object will be inserted immediately before.

object - The object to insert.

Throws: IndexOutOfBoundsException

If the index is invalid.

 public synchronized DequeIterator insert(DequeIterator pos,
                                          Object value)

Insert an object at a particular position and return an iterator positioned at the new element.

Parameters:

pos - An iterator positioned at the element that the object will be inserted immediately before.

object - The object to insert.

 public synchronized void insert(int index,
                                 int n,
                                 Object value)

Insert multiple objects at a particular index.

Parameters:

index - The index of the element that the objects will be inserted immediately before.

object - The object to insert.

Throws: IndexOutOfBoundsException

If the index is invalid.

Throws: IllegalArgumentException

If the number of objects to insert is negative.

 public synchronized void insert(DequeIterator pos,
                                 int n,
                                 Object value)

Insert multiple objects at a particular position.

Parameters:

pos - An iterator positioned at the element that the objects will be inserted immediately before.

n - The number of objects to insert.

object - The object to insert.

Throws: IllegalArgumentException

If the number of objects to insert is negative.

 public synchronized void insert(int index,
                                 BidirectionalIterator first,
                                 BidirectionalIterator last)

Insert a sequence of objects at a particular index.

Parameters:

pos - The index of the element that the objects will be inserted immediately before.

first - An iterator positioned at the first element to insert.

last - An iterator positioned immediately after the last element to insert.

Throws: IndexOutOfBoundsException

If the index is invalid.

 public synchronized void insert(DequeIterator pos,
                                 BidirectionalIterator first,
                                 BidirectionalIterator last)

Insert a sequence of objects at a particular location.

Parameters:

pos - The location of the element that the objects will be inserted immediately before.

first - An iterator positioned at the first element to insert.

last - An iterator positioned immediately after the last element to insert.

 public int remove(Object object)

Remove all elements that match a particular object and return the numbers of objects that were removed.

Parameters:

object - The object to remove.

Returns:

The number of objects removed.

 public synchronized int remove(Object object,
                                int count)

Remove at most a given number of elements that match a particular object and return the number of objects that were removed.

Parameters:

object - The object to remove.

count - The maximum number of objects to remove.

Returns:

The number of objects removed.

 public synchronized int remove(int first,
                                int last,
                                Object object)

Remove all elements within a range of indices that match a particular object and return the number of objects that were removed.

Parameters:

first - The index of the first object to consider.

last - The index of the last object to consider.

object - The object to remove.

Returns:

The number of objects removed.

Throws: IndexOutOfBoundsException

If either index is invalid.

 public synchronized int replace(Object oldValue,
                                 Object newValue)

Replace all elements that match a particular object with a new value and return the number of objects that were replaced.

Parameters:

oldValue - The object to be replaced.

newValue - The value to substitute.

 public synchronized int replace(int first,
                                 int last,
                                 Object oldValue,
                                 Object newValue)

Replace all elements within a range of indices that match a particular object with a new value and return the number of objects that were replaced.

Parameters:

first - The index of the first object to be considered.

last - The index of the last object to be considered.

oldValue - The object to be replaced.

newValue - The value to substitute.

Throws: IndexOutOfBoundsException

If either index is invalid.

 public int count(Object object)

Return the number of objects that match a particular value.

Parameters:

object - The object to count.

 public synchronized int count(int first,
                               int last,
                               Object object)

Return the number of objects within a particular range of indices that match a particular value.

Parameters:

first - The index of the first object to consider.

last - The index of the last object to consider.

Throws: IndexOutOfBoundsException

If either index is invalid.

 public int indexOf(Object object)

Return the index of the first object that matches a particular value, or -1 if the object is not found.

Parameters:

object - The object to find.

 public int indexOf(int first,
                    int last,
                    Object object)

Return the index of the first object within a range of indices that match a particular object, or -1 if the object is not found.

Parameters:

first - The index of the first object to consider.

last - The index of the last object to consider.

object - The object to find.

Throws: IndexOutOfBoundsException

If either index is invalid.

 public boolean contains(Object object)

Return true if I contain a particular object.

Parameters:

object - The object in question.

All Packages  Class Hierarchy  This Package  Previous  Next  Index