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() {
            delete [] this->elements;
            this->curSize = 0;
            this->capacity = 10;
            this->elements = new E[this->capacity];
            AbstractList<E>::modCount++;
        }

        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__,
                        "List::get - 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__,
                        "List::get - 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__,
                        "List::addAll - 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__,
                        "List::removeAt - 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_ */