DynamicArray.java
/*
** Module : DynamicArray.java
** Abstract : an array that can grow and shrink as needed
**
** Copyright (c) 2008-2017, Golden Code Development Corporation.
**
** -#- -I- --Date-- --JPRM-- ----------------------------Description-----------------------------
** 001 GES 20080627 @38994 First version. Maintains an array that can grow or shrink as needed
** to add or remove elements.
** 002 ECF 20160517 Added containsFromEnd method.
*/
/*
** This program is free software: you can redistribute it and/or modify
** it under the terms of the GNU Affero General Public License as
** published by the Free Software Foundation, either version 3 of the
** License, or (at your option) any later version.
**
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
** GNU Affero General Public License for more details.
**
** You may find a copy of the GNU Affero GPL version 3 at the following
** location: https://www.gnu.org/licenses/agpl-3.0.en.html
**
** Additional terms under GNU Affero GPL version 3 section 7:
**
** Under Section 7 of the GNU Affero GPL version 3, the following additional
** terms apply to the works covered under the License. These additional terms
** are non-permissive additional terms allowed under Section 7 of the GNU
** Affero GPL version 3 and may not be removed by you.
**
** 0. Attribution Requirement.
**
** You must preserve all legal notices or author attributions in the covered
** work or Appropriate Legal Notices displayed by works containing the covered
** work. You may not remove from the covered work any author or developer
** credit already included within the covered work.
**
** 1. No License To Use Trademarks.
**
** This license does not grant any license or rights to use the trademarks
** Golden Code, FWD, any Golden Code or FWD logo, or any other trademarks
** of Golden Code Development Corporation. You are not authorized to use the
** name Golden Code, FWD, or the names of any author or contributor, for
** publicity purposes without written authorization.
**
** 2. No Misrepresentation of Affiliation.
**
** You may not represent yourself as Golden Code Development Corporation or FWD.
**
** You may not represent yourself for publicity purposes as associated with
** Golden Code Development Corporation, FWD, or any author or contributor to
** the covered work, without written authorization.
**
** 3. No Misrepresentation of Source or Origin.
**
** You may not represent the covered work as solely your work. All modified
** versions of the covered work must be marked in a reasonable way to make it
** clear that the modified work is not originating from Golden Code Development
** Corporation or FWD. All modified versions must contain the notices of
** attribution required in this license.
*/
package com.goldencode.p2j.util;
import java.util.*;
/**
* Maintains an array which can grow or shrink as needed to contain the
* elements.
* <p>
* <b>All operations on this array are handled using object equality
* (comparing references) as opposed to being based on <code>equals</code> or
* <code>compareTo</code>.</b>
*/
public class DynamicArray<E>
{
/** Number of elements by which to grow or shrink the array. */
private static final int INCREMENT = 16;
/** Number of empty elements at which the array will be shrunk. */
private static final int THRESHOLD = INCREMENT * 2;
/** Stores our elements. */
private Object[] elements = null;
/** Current size. */
private int size = 0;
/**
* Default constructor.
*/
public DynamicArray()
{
clear();
}
/**
* Copy constructor.
*/
public DynamicArray(DynamicArray<E> src)
{
elements = Arrays.copyOf(src.elements, src.elements.length);
size = src.size;
}
/**
* Add the object to the end of the array.
*
* @param val
* The instance to add to the list.
*/
public void add(E val)
{
grow(1);
elements[size] = val;
size++;
}
/**
* Add the objects to the end of the array in the proper order.
*
* @param val
* The collection of elements to add to the list.
*/
public void addAll(Collection<? extends E> val)
{
grow(val.size());
for (E next : val)
{
elements[size] = next;
size++;
}
}
/**
* Remove all elements and reset state.
*/
public void clear()
{
elements = new Object[INCREMENT];
size = 0;
}
/**
* Report if the given instance exists in the array based on object
* equality. <code>compareTo</code> and <code>equals</code> are NOT used!
*
* @param val
* The instance to search for in the list.
*
* @return <code>true</code> if there is at least one copy of this
* object instance in the array.
*/
public boolean contains(E val)
{
for (Object next : elements)
{
if (next == val)
{
return true;
}
}
return false;
}
/**
* Report if the given instance exists in the array based on object equality. {@code compareTo}
* and {@code equals} are NOT used!
* <p>
* This implementation searches from the back of the list to the front.
*
* @param val
* The instance to search for in the list.
*
* @return {@code true} if there is at least one copy of this object instance in the array.
*/
public boolean containsFromEnd(E val)
{
int len = elements.length;
for (int i = len - 1; i >= 0; i--)
{
if (elements[i] == val)
{
return true;
}
}
return false;
}
/**
* Gets the current number of elements in the array.
*
* @return The current length.
*/
public int length()
{
return size;
}
/**
* Obtain access to a copy of the array. Note that all elements are
* returned, not just those in the current partition.
*
* @param example
* The array on which to base the result.
*
* @return All contained elements in the order they were added.
*/
public E[] toArray(E[] example)
{
return (E[]) Arrays.copyOf(elements, size, example.getClass());
}
/**
* Remove the first instance of the given object in the array.
*
* @param val
* The instance to remove from the list.
*
* @return The number of elements removed.
*/
public int remove(E val)
{
return remove(val, false);
}
/**
* Remove the first instance or all instances of the given object in the
* array.
*
* @param val
* The instance to remove from the list.
* @param all
* <code>true</code> to remove all found instances, otherwise
* only remove the first instance found.
*
* @return The number of elements removed.
*/
public int remove(E val, boolean all)
{
int num = 0;
for (int i = 0; i < elements.length; i++)
{
// element[i] may be null but this is safe
if (elements[i] == val)
{
num++;
size--;
elements[i] = null;
if (!all)
{
break;
}
}
}
if (num > 0)
{
shrink();
}
return num;
}
/**
* Cause all elements to be continuous in the array such that no
* <code>null</code> elements are in between any two <code>non-null</code>
* elements. This will not affect the size or the order of the elements.
* All <code>null</code> elements will appear at the end of the array
* starting at the <code>size</code> element.
*/
private void compress()
{
int open = findNextOpenSlot(0);
for (int next = open + 1; next < elements.length; next++)
{
if (elements[next] != null && open < next)
{
elements[open] = elements[next];
elements[next] = null;
// find the next open slot
open = findNextOpenSlot(++open);
}
}
}
/**
* Find the index of the next empty slot in the array starting at the
* given index.
*
* @param idx
* The index at which to start searching. If less than 0 then
* the search will start at 0.
*
* @return The index of the first <code>null</code> element or if the
* array is full, the size of the array.
*/
private int findNextOpenSlot(int idx)
{
int open = (idx >= 0) ? idx : 0;
while (elements[open] != null && open < elements.length)
{
open++;
}
return open;
}
/**
* Grow the array by the standard increment amount if it is full. This
* doesn't change the number of <code>non-null</code> elements.
*
* @param amount
* The amount of space needed.
*/
private void grow(int amount)
{
int newsize = size + amount;
if (newsize >= elements.length)
{
elements = Arrays.copyOf(elements, nextIncrement(newsize));
}
}
/**
* 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).
* This doesn't change the number of <code>non-null</code> elements.
*/
private void shrink()
{
compress();
if (size < (elements.length - THRESHOLD))
{
elements = Arrays.copyOf(elements, nextIncrement(size));
}
}
/**
* Calculate the next multiple of INCREMENT that can hold the given
* <code>size</code> elements.
*
* @param size
* The amount of space needed.
*
* @return The nearest multiple of INCREMENT that is larger than the
* given <code>size</code>.
*/
private int nextIncrement(int size)
{
return ((size / INCREMENT) + 1) * INCREMENT;
}
}