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