# PartitionedArray.java

    /*
    ** Module   : PartitionedArray.java
    ** Abstract : maintains an ordered list with multiple partitions in a "stack"
    **
    ** Copyright (c) 2008-2017, Golden Code Development Corporation.
    **
    ** -#- -I- --Date-- --JPRM-- ----------------------------Description-----------------------------
    ** 001 GES 20080429   @38145 First version.  Maintains an ordered list
    **                           with addition/removal of partitions from the
    **                           end of the list.
    ** 002 GES 20080505   @38209 Added support for a global partition.
    ** 003 GES 20080619   @38887 Added a copy constructor and the ability to
    **                           remove arbitrary elements. Please note that
    **                           removal is expensive so avoid this if
    **                           possible.
    ** 004 GES 20080624   @38914 Added a flag to force removal of all
    **                           instances of a value, instead of the default
    **                           of removing only the first matched instance.
    ** 005 GES 20080630   @38995 Rewrite to use an array class that uses
    **                           object equality rather than equals for its
    **                           operation (methods like contains or remove).
    **                           This allows proper removal of all reference
    **                           instances and cannot be achieved with the
    **                           ArrayList.
    ** 006 ECF 20160517          Added partitionContains 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 ordered list with fast removal of partitions. Partitions are
     * marked positions in the list similar to the idea of the levels in a stack.
     * The topmost partition can be deleted with a single, simple method call
     * without the caller storing any additional data to define the range
     * associated with the partition. When a partition is deleted, all elements
     * added since the beginning of that partition will be deleted.
     */
    public class PartitionedArray<E>
    {
       /** Number of elements by which to grow or shrink the array. */
       private static final int INCREMENT = 16;

       /** The stack of our partitions. */
       private DynamicArray<E>[] partitions = null;

       /** The top of the stack (MUST be a <code>non-null</code> value). */
       private int idx = 0;

       /** The total number of elements in the array. */
       private int size = 0;

       /**
        * Default constructor.
        */
       public PartitionedArray()
       {
          clear();
       }

       /**
        * Copy constructor.
        */
       public PartitionedArray(PartitionedArray src)
       {
          partitions = new DynamicArray[src.partitions.length];
          idx        = src.idx;
          size       = src.size;

          // copy the stack contents
          for (int i = 0; i <= idx; i++)
          {
             if (src.partitions[i] != null)
             {
                partitions[i] = new DynamicArray<E>(src.partitions[i]);
             }
          }
       }

       /**
        * Add the object to the end of the array.
        *
        * @param    val
        *           The instance to add to the list.
        */
       public void add(E val)
       {
          partitions[idx].add(val);
          size++;
       }

       /**
        * Add the object to the end of the array. Note that if the same object is
        * added more than once, there will be multiple references to that instance
        * in the array.
        *
        * @param    global
        *           <code>true</code> if the element should be added to the
        *           global partition. Otherwise the element will be added to
        *           the current partition.
        * @param    val
        *           The instance to add to the list.
        */
       public void add(boolean global, E val)
       {
          int i = global ? 0 : idx;
          partitions[i].add(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)
       {
          partitions[idx].addAll(val);
          size += val.size();
       }

       /**
        * Remove all elements and reset state.
        */
       public void clear()
       {
          partitions = new DynamicArray[INCREMENT];
          partitions[0] = new DynamicArray<E>();
          idx  = 0;
          size = 0;
       }

       /**
        * Report if the given instance exists in the array.
        *
        * @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 (int i = 0; i <= idx; i++)
          {
             if (partitionContains(i, val, true))
             {
                return true;
             }
          }

          return false;
       }

       /**
        * Report if the given instance exists in a specific partition within the array.
        *
        * @param    index
        *           Zero-based index of the target partition in the array of partitions.
        * @param    val
        *           The instance to search for in the list.
        * @param    forward
        *           {@code true} to search the partition from front to back; {@code false} to search
        *           from back to front.
        *
        * @return   {@code true} if there is at least one copy of this object instance in the
        *           specified partition.
        */
       public boolean partitionContains(int index, E val, boolean forward)
       {
          DynamicArray<E> partition = partitions[index];

          return forward ? partition.contains(val) : partition.containsFromEnd(val);
       }

       /**
        * Gets the current number of elements in the array.
        *
        * @return   The current size.
        */
       public int size()
       {
          return size;
       }

       /**
        * Obtain access to a copy of the array. Note that all elements are
        * returned, not just those in the current partition.
        *
        * @return   All contained elements in the order they were added.
        */
       public E[] toArray(E[] e)
       {
          // get the global partition
          E[] global = partitions[0].toArray(e);

          // create an array large enough to hold all elements from all partitions
          E[] total = (E[]) Arrays.copyOf(global, size);

          // start copying after the global partition
          int ptr = global.length;

          // iterate through all remaining partitions
          for (int i = 1; i <= idx; i++)
          {
             E[] next = partitions[i].toArray(e);

             if ((ptr + next.length) > total.length)
             {
                throw new IllegalStateException("Unexpected size difference!");
             }

             // copy the elements from this partition into the results array
             for (int j = 0; j < next.length; j++, ptr++)
             {
                total[ptr] = next[j];
             }
          }

          return total;
       }

       /**
        * Mark the current end of the array as a new partition. Any elements
        * added after this call and before the next call to this method or to
        * {@link #removePartition} will be "contained" in this partition. This
        * is similar to a push on a stack, except that
        */
       public void markPartition()
       {
          // move the top of stack index
          idx++;

          // ensure we are not pointing past the end of the stack's size
          if (idx == partitions.length)
          {
             // grow the array
             int len = partitions.length + INCREMENT;
             partitions = (DynamicArray<E>[]) Arrays.copyOf(partitions, len);
          }

          // add the partition
          partitions[idx] = new DynamicArray<E>();
       }

       /**
        * Remove all elements contained in the last partition of the array and
        * remove the partition definition too. This is similar to a pop operation
        * on a stack. Calls to this method must always be paired with an equal
        * number of calls to {@link #markPartition}.
        */
       public void removePartition()
       {
          // don't delete the global partition
          if (idx > 0)
          {
             // clear our knowledge of the partition
             size -= partitions[idx].length();
             partitions[idx] = null;
             idx--;

             // don't leave too much extra capacity in the stack
             if (idx < (partitions.length - (2 * INCREMENT)))
             {
                int len = partitions.length - INCREMENT;
                partitions = (DynamicArray<E>[]) Arrays.copyOf(partitions, len);
             }
          }
       }

       /**
        * Remove the first instance of the given object in the array.
        *
        * @param    val
        *           The instance to remove from the list.
        */
       public void remove(E val)
       {
          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.
        */
       public void remove(E val, boolean all)
       {
          for (int i = 0; i <= idx; i++)
          {
             int num = partitions[i].remove(val, all);

             if (num > 0)
             {
                size -= num;

                if (!all)
                {
                   break;
                }
             }
          }
       }
    }