# 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;
       }
    }