blob: d833d95ed6bca923274d9ff649dc1f8d9c2ccb71 [file] [log] [blame]
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#ifndef _DECAF_UTIL_ARRAYLIST_H_
#define _DECAF_UTIL_ARRAYLIST_H_
#include <memory>
#include <decaf/util/NoSuchElementException.h>
#include <decaf/lang/exceptions/UnsupportedOperationException.h>
#include <decaf/lang/exceptions/IndexOutOfBoundsException.h>
#include <decaf/lang/System.h>
#include <decaf/lang/Integer.h>
#include <decaf/util/Config.h>
#include <decaf/util/Iterator.h>
#include <decaf/util/ListIterator.h>
#include <decaf/util/List.h>
#include <decaf/util/AbstractList.h>
namespace decaf {
namespace util {
using decaf::lang::System;
template< typename E >
class ArrayList : public decaf::util::AbstractList<E> {
private:
E* elements;
int capacity;
int head;
int curSize;
public:
ArrayList() : AbstractList<E>(), elements(NULL), capacity(0), head(0), curSize(0) {
this->ensureCapacity(10);
}
ArrayList(const Collection<E>& collection) :
AbstractList<E>(), elements(NULL), capacity(0), head(0), curSize(0) {
this->capacity = collection.size() + (collection.size() / 10);
this->elements = new E[this->capacity];
std::auto_ptr<Iterator<E> > iter(collection.iterator());
while (iter->hasNext()) {
this->elements[this->head++] = iter->next();
this->curSize++;
}
}
ArrayList(const ArrayList<E>& arrayList) :
AbstractList<E>(), elements(NULL), capacity(0), head(0), curSize(0) {
this->capacity = arrayList.size() + (arrayList.size() / 10);
this->elements = new E[this->capacity];
std::auto_ptr<Iterator<E> > iter(arrayList.iterator());
while (iter->hasNext()) {
this->elements[this->head++] = iter->next();
this->curSize++;
}
}
ArrayList(int initialCapacity) :
AbstractList<E>(), elements(NULL), capacity(initialCapacity), head(0), curSize(0) {
if (initialCapacity < 0) {
throw decaf::lang::exceptions::IllegalArgumentException(__FILE__, __LINE__, "Initial Capacity argument cannot be negative.");
}
this->elements = new E[this->capacity];
}
virtual ~ArrayList() {
try {
delete[] elements;
}
DECAF_CATCHALL_NOTHROW()
}
public:
ArrayList<E>& operator= (const ArrayList<E>& list) {
this->clear();
this->addAll( list );
return *this;
}
ArrayList<E>& operator= (const Collection<E>& collection) {
this->clear();
this->addAll(0, collection);
return *this;
}
bool operator==(const ArrayList<E>& other) const {
return this->equals(other);
}
bool operator!=(const ArrayList<E>& other) const {
return !this->equals(other);
}
public:
/**
* Increases the capacity of this ArrayList instance, if necessary, to ensure that it can
* hold at least the number of elements specified by the minimum capacity argument. If the
* capacity is already greater than or equal to the minimum capacity argument then the array
* is left unchanged.
*
* @param minimumCapacity
* The desired minimum capacity for this ArrayList.
*/
void ensureCapacity(int minimumCapacity) {
if (minimumCapacity < 0 || this->capacity >= minimumCapacity) {
return;
}
int newCapacity = minimumCapacity == 0 ? 10 : minimumCapacity;
E* newElements = new E[newCapacity];
if (this->curSize > 0) {
decaf::lang::System::arraycopy(this->elements, this->head, newElements, 0, this->curSize);
}
delete [] this->elements;
this->elements = newElements;
this->capacity = newCapacity;
AbstractList<E>::modCount++;
}
/**
* Trims the internal array to match the current size of the ArrayList. This compacts
* the internal array to save storage space used by this ArrayList.
*/
void trimToSize() {
if (this->curSize < this->capacity) {
int newCapacity = this->curSize == 0 ? 10 : this->curSize;
E* newElements = new E[newCapacity];
if (this->curSize > 0) {
System::arraycopy(this->elements, 0, newElements, 0, this->curSize);
}
delete [] this->elements;
this->elements = newElements;
this->capacity = newCapacity;
}
AbstractList<E>::modCount++;
}
public:
virtual void clear() {
if (this->curSize > 0) {
delete [] this->elements;
this->curSize = 0;
this->capacity = 10;
this->elements = new E[this->capacity];
AbstractList<E>::modCount++;
} else {
ensureCapacity(10);
}
}
virtual bool isEmpty() const {
return this->curSize == 0;
}
virtual int size() const {
return this->curSize;
}
virtual E set(int index, const E& element) {
if (index < 0 || index >= this->curSize) {
throw decaf::lang::exceptions::IndexOutOfBoundsException(
__FILE__, __LINE__, "Index greater than size() or negative");
}
E oldValue = this->elements[index];
this->elements[index] = element;
return oldValue;
}
virtual E get(int index) const {
if (index < 0 || index >= this->curSize) {
throw decaf::lang::exceptions::IndexOutOfBoundsException(
__FILE__, __LINE__, "Index greater than size() or negative");
}
return this->elements[index];
}
virtual bool add(const E& value) {
this->expandEnd(1);
this->elements[this->curSize++] = value;
AbstractList<E>::modCount++;
return true;
}
virtual void add(int index, const E& element) {
if (index < 0 || index > this->curSize) {
throw decaf::lang::exceptions::IndexOutOfBoundsException(
__FILE__, __LINE__, "Index was negative or greater than size()");
}
if (index == 0) {
this->expandFront(1);
} else if (index == this->curSize) {
this->expandEnd(1);
} else {
this->expandMiddle(index, 1);
}
this->elements[index] = element;
this->curSize++;
AbstractList<E>::modCount++;
}
virtual bool addAll(const Collection<E>& collection) {
int csize = collection.size();
if (csize == 0) {
return false;
}
std::vector<E> array = collection.toArray();
this->expandEnd(csize);
for (int i = 0; i < csize; ++i) {
this->elements[this->curSize++] = array[i];
}
AbstractList<E>::modCount++;
return true;
}
virtual bool addAll(int index, const Collection<E>& collection) {
if(index < 0 || index > this->curSize) {
throw decaf::lang::exceptions::IndexOutOfBoundsException(
__FILE__, __LINE__, "Index greater than size()");
}
int csize = collection.size();
if (csize == 0) {
return false;
}
std::vector<E> array = collection.toArray();
if (index == 0) {
this->expandFront(csize);
} else if (index == this->curSize) {
this->expandEnd(csize);
} else {
this->expandMiddle(index, csize);
}
for (int i = 0; i < csize; ++i, ++this->curSize) {
this->elements[index++] = array[i];
}
AbstractList<E>::modCount++;
return true;
}
virtual bool remove(const E& value) {
int result = indexOf(value);
if (result != -1) {
this->removeAt(result);
return true;
}
return false;
}
virtual E removeAt(int index) {
if (index < 0 || index >= this->curSize) {
throw decaf::lang::exceptions::IndexOutOfBoundsException(
__FILE__, __LINE__, "Index greater than size() or negative");
}
E old = this->elements[index];
System::arraycopy(this->elements, 0, this->elements, 0, index);
if (this->curSize > index) {
System::arraycopy(this->elements, index + 1, this->elements, index, this->curSize - index - 1);
}
this->elements[--this->curSize] = E();
AbstractList<E>::modCount++;
return old;
}
virtual bool contains(const E& value) const {
return this->indexOf(value) != -1;
}
virtual int indexOf(const E& value) const {
for (int i = 0; i < this->curSize; ++i) {
if (this->elements[i] == value) {
return i;
}
}
return -1;
}
virtual int lastIndexOf(const E& value) const {
for (int i = this->curSize - 1; i >= 0; --i) {
if (this->elements[i] == value) {
return i;
}
}
return -1;
}
virtual std::vector<E> toArray() const {
std::vector<E> result;
for (int i = 0; i < this->curSize; ++i) {
result.push_back(this->elements[i]);
}
return result;
}
virtual std::string toString() const {
std::string result;
result.append("decaf::util::ArrayList [ size = ");
result.append(decaf::lang::Integer::toString(this->curSize));
result.append(" ]");
return result;
}
private:
void expandFront(int amount) {
if (amount == 0) {
return;
}
E* previous = this->elements;
if (amount > this->capacity - this->curSize) {
this->capacity = this->capacity + amount + 11;
this->elements = new E[this->capacity];
}
if (this->curSize > 0) {
System::arraycopy(previous, 0, this->elements, amount, this->curSize);
}
if (previous != this->elements) {
delete [] previous;
}
}
void expandEnd(int amount) {
if (amount == 0) {
return;
}
E* previous = this->elements;
if (amount > this->capacity - this->curSize) {
this->capacity = this->capacity + amount + 11;
this->elements = new E[this->capacity];
System::arraycopy( previous, 0, this->elements, 0, this->curSize );
}
if(previous != this->elements) {
delete [] previous;
}
}
void expandMiddle(int index, int amount) {
if (amount == 0) {
return;
}
E* previous = this->elements;
if (amount > this->capacity - this->curSize) {
this->capacity = this->capacity + amount + 11;
this->elements = new E[this->capacity];
}
if (this->curSize > 0) {
System::arraycopy(previous, 0, this->elements, 0, index);
}
if (this->curSize > index) {
System::arraycopy(previous, index, this->elements, index + amount, this->curSize - index);
}
if (previous != this->elements) {
delete [] previous;
}
}
};
}}
#endif /* _DECAF_UTIL_ARRAYLIST_H_ */