ArrayList.h

Go to the documentation of this file.

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

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

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