| /* |
| * 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_ */ |