public class DynamicArray<E>
extends java.lang.Object
All operations on this array are handled using object equality
(comparing references) as opposed to being based on equals
or
compareTo
.
Modifier and Type | Field and Description |
---|---|
private java.lang.Object[] |
elements
Stores our elements.
|
private static int |
INCREMENT
Number of elements by which to grow or shrink the array.
|
private int |
size
Current size.
|
private static int |
THRESHOLD
Number of empty elements at which the array will be shrunk.
|
Constructor and Description |
---|
DynamicArray()
Default constructor.
|
DynamicArray(DynamicArray<E> src)
Copy constructor.
|
Modifier and Type | Method and Description |
---|---|
void |
add(E val)
Add the object to the end of the array.
|
void |
addAll(java.util.Collection<? extends E> val)
Add the objects to the end of the array in the proper order.
|
void |
clear()
Remove all elements and reset state.
|
private void |
compress()
Cause all elements to be continuous in the array such that no
null elements are in between any two non-null
elements. |
boolean |
contains(E val)
Report if the given instance exists in the array based on object
equality.
|
boolean |
containsFromEnd(E val)
Report if the given instance exists in the array based on object equality.
|
private int |
findNextOpenSlot(int idx)
Find the index of the next empty slot in the array starting at the
given index.
|
private void |
grow(int amount)
Grow the array by the standard increment amount if it is full.
|
int |
length()
Gets the current number of elements in the array.
|
private int |
nextIncrement(int size)
Calculate the next multiple of INCREMENT that can hold the given
size elements. |
int |
remove(E val)
Remove the first instance of the given object in the array.
|
int |
remove(E val,
boolean all)
Remove the first instance or all instances of the given object in the
array.
|
private void |
shrink()
Shrink the array to the smallest multiple of the standard increment
amount if there is enough space to reclaim while still leaving some
open slots (so new additions won't cause array growth immediately).
|
E[] |
toArray(E[] example)
Obtain access to a copy of the array.
|
private static final int INCREMENT
private static final int THRESHOLD
private java.lang.Object[] elements
private int size
public DynamicArray()
public DynamicArray(DynamicArray<E> src)
public void add(E val)
val
- The instance to add to the list.public void addAll(java.util.Collection<? extends E> val)
val
- The collection of elements to add to the list.public void clear()
public boolean contains(E val)
compareTo
and equals
are NOT used!val
- The instance to search for in the list.true
if there is at least one copy of this
object instance in the array.public boolean containsFromEnd(E val)
compareTo
and equals
are NOT used!
This implementation searches from the back of the list to the front.
val
- The instance to search for in the list.true
if there is at least one copy of this object instance in the array.public int length()
public E[] toArray(E[] example)
example
- The array on which to base the result.public int remove(E val)
val
- The instance to remove from the list.public int remove(E val, boolean all)
val
- The instance to remove from the list.all
- true
to remove all found instances, otherwise
only remove the first instance found.private void compress()
null
elements are in between any two non-null
elements. This will not affect the size or the order of the elements.
All null
elements will appear at the end of the array
starting at the size
element.private int findNextOpenSlot(int idx)
idx
- The index at which to start searching. If less than 0 then
the search will start at 0.null
element or if the
array is full, the size of the array.private void grow(int amount)
non-null
elements.amount
- The amount of space needed.private void shrink()
non-null
elements.private int nextIncrement(int size)
size
elements.size
- The amount of space needed.size
.