/*
* Copyright (c) 2005, Graph Builder
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* * Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
*
* * Redistributions in binary form must reproduce the above copyright notice,
* this list of conditions and the following disclaimer in the documentation
* and/or other materials provided with the distribution.
*
* * Neither the name of Graph Builder nor the names of its contributors may be
* used to endorse or promote products derived from this software without
* specific prior written permission.
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
* SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
* CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
package com.graphbuilder.struc;
/**
Bag is a container of objects using an array. The Bag is designed to be as light weight as possible.
It only contains a reference to an array and a size counter. In methods that accept both an Object and
an int as parameters, the Object is always specified first.
*/
public class
Bag {
protected
Object[]
data = null;
protected int
size = 0;
public
Bag() {
data = new
Object[2];
}
public
Bag(int
initialCapacity) {
data = new
Object[
initialCapacity];
}
public
Bag(
Object[]
data, int
size) {
if (
data == null)
throw new
IllegalArgumentException("data array cannot be null.");
if (
size < 0 ||
size >
data.length)
throw new
IllegalArgumentException("required: (size >= 0 && size <= data.length) but: (size = " +
size + ", data.length = " +
data.length + ")");
this.
data =
data;
this.
size =
size;
}
public void
add(
Object o) {
insert(
o,
size);
}
public int
size() {
return
size;
}
public void
setSize(int
s) {
if (
s < 0 ||
s >
data.length)
throw new
IllegalArgumentException("required: (size >= 0 && size <= data.length) but: (size = " +
size + ", data.length = " +
data.length + ")");
size =
s;
}
public void
insert(
Object o, int
index) {
if (
index < 0 ||
index >
size)
throw new
IllegalArgumentException("required: (index >= 0 && index <= size) but: (index = " +
index + ", size = " +
size + ")");
ensureCapacity(
size + 1);
for (int
i =
size;
i >
index;
i--)
data[
i] =
data[
i - 1];
data[
index] =
o;
size++;
}
public void
ensureCapacity(int
capacity) {
if (
capacity >
data.length) {
int
x = 2 *
data.length;
if (
x <
capacity)
x =
capacity;
Object[]
arr = new
Object[
x];
for (int
i = 0;
i <
size;
i++)
arr[
i] =
data[
i];
data =
arr;
}
}
public int
getCapacity() {
return
data.length;
}
private int
find(
Object o, int
i, boolean
forward) {
if (
i < 0 ||
i >=
size) return -1;
if (
forward) {
if (
o == null) {
for (;
i <
size;
i++)
if (
data[
i] == null)
return
i;
}
else {
for (;
i <
size;
i++)
if (
o.
equals(
data[
i]))
return
i;
}
}
else {
if (
o == null) {
for (;
i >= 0;
i--)
if (
data[
i] == null)
return
i;
}
else {
for (;
i >= 0;
i--)
if (
o.
equals(
data[
i]))
return
i;
}
}
return -1;
}
public int
remove(
Object o) {
int
i =
find(
o, 0, true);
if (
i >= 0)
remove(
i);
return
i;
}
public
Object remove(int
index) {
if (
index < 0 ||
index >=
size)
throw new
IllegalArgumentException("required: (index >= 0 && index < size) but: (index = " +
index + ", size = " +
size + ")");
Object o =
data[
index];
for (int
i =
index + 1;
i <
size;
i++)
data[
i-1] =
data[
i];
data[--
size] = null;
return
o;
}
public
Object get(int
index) {
if (
index < 0 ||
index >=
size)
throw new
IllegalArgumentException("required: (index >= 0 && index < size) but: (index = " +
index + ", size = " +
size + ")");
return
data[
index];
}
public
Object set(
Object o, int
index) {
if (
index < 0 ||
index >=
size)
throw new
IllegalArgumentException("required: (index >= 0 && index < size) but: (index = " +
index + ", size = " +
size + ")");
Object old =
data[
index];
data[
index] =
o;
return
old;
}
public boolean
contains(
Object o) {
return
find(
o, 0, true) >= 0;
}
public boolean
isEmpty() {
return
size == 0;
}
public void
trimArray() {
if (
size <
data.length) {
Object[]
arr = new
Object[
size];
for (int
i = 0;
i <
size;
i++)
arr[
i] =
data[
i];
data =
arr;
}
}
public int
indexOf(
Object o) {
return
find(
o, 0, true);
}
public int
indexOf(
Object o, int
startIndex) {
return
find(
o,
startIndex, true);
}
public int
lastIndexOf(
Object o) {
return
find(
o,
size - 1, false);
}
public int
lastIndexOf(
Object o, int
startIndex) {
return
find(
o,
startIndex, false);
}
}