src/main/decaf/util/AbstractList.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_ABSTRACTLIST_H_
#define _DECAF_UTIL_ABSTRACTLIST_H_

#include <decaf/util/Config.h>
#include <decaf/util/NoSuchElementException.h>
#include <decaf/lang/exceptions/UnsupportedOperationException.h>
#include <decaf/lang/exceptions/NullPointerException.h>
#include <decaf/lang/exceptions/IllegalArgumentException.h>
#include <decaf/util/ConcurrentModificationException.h>
#include <decaf/lang/Iterable.h>
#include <decaf/util/Iterator.h>
#include <decaf/util/List.h>
#include <decaf/util/AbstractCollection.h>
#include <memory>

namespace decaf {
namespace util {

    template< typename E >
    class AbstractList : public decaf::util::List<E>,
                         public decaf::util::AbstractCollection<E> {
    protected:

        int modCount;

    private:

        class SimpleListIterator : public ListIterator<E> {
        protected:

            AbstractList<E>* parent;
            int numLeft;
            int expectedModCount;
            int lastPosition;

        private:

            SimpleListIterator( const SimpleListIterator& );
            SimpleListIterator operator= ( const SimpleListIterator& );

        public:

            SimpleListIterator( AbstractList<E>* parent, int start ) :
                ListIterator<E>(), parent(NULL), numLeft(0), expectedModCount(0), lastPosition(-1) {

                if( parent == NULL ) {
                    throw decaf::lang::exceptions::NullPointerException(
                        __FILE__, __LINE__, "List Iterator constructed with NULL parent" );
                }

                if( start < 0 || start > parent->size() ) {
                    throw decaf::lang::exceptions::IndexOutOfBoundsException(
                         __FILE__, __LINE__, "start index passed was negative or greater than size()" );
                }

                this->numLeft = parent->size() - start;
                this->parent = parent;
                this->expectedModCount = parent->modCount;
            }

            virtual ~SimpleListIterator() {}

            virtual bool hasNext() const {
                return this->numLeft > 0;
            }

            virtual E next() {

                if( this->expectedModCount != this->parent->modCount ) {
                    throw ConcurrentModificationException(
                        __FILE__, __LINE__, "Concurrent Modification of Parent List detected." );
                }

                try {

                    int index = this->parent->size() - this->numLeft;
                    E result = this->parent->get( index );
                    this->lastPosition = index;
                    this->numLeft--;

                    return result;
                } catch( decaf::lang::exceptions::IndexOutOfBoundsException& e ) {
                    throw decaf::util::NoSuchElementException(
                        __FILE__, __LINE__, "Next called without a next element to process." );
                }
            }

            virtual void remove() {

                if( this->lastPosition == -1 ) {
                    throw decaf::lang::exceptions::IllegalStateException(
                        __FILE__, __LINE__, "Remove called before next() was called." );
                }

                if( this->expectedModCount != this->parent->modCount ) {
                    throw ConcurrentModificationException(
                        __FILE__, __LINE__, "Concurrent Modification of Parent List detected." );
                }

                try {

                    if( this->lastPosition == this->parent->size() - this->numLeft ) {
                        this->numLeft--; // we're removing after a call to previous()
                    }

                    this->parent->removeAt( lastPosition );

                } catch( decaf::lang::exceptions::IndexOutOfBoundsException& e ) {
                    throw ConcurrentModificationException(
                        __FILE__, __LINE__, "Concurrent Modification detected." );
                }

                this->expectedModCount = this->parent->modCount;
                this->lastPosition = -1;
            }

            virtual void add( const E& value ) {

                if( this->expectedModCount != this->parent->modCount ) {
                    throw ConcurrentModificationException(
                        __FILE__, __LINE__, "Concurrent Modification of Parent List detected." );
                }

                try {
                    this->parent->add( this->parent->size() - this->numLeft, value );
                    this->expectedModCount = this->parent->modCount;
                    this->lastPosition = -1;
                } catch( decaf::lang::exceptions::IndexOutOfBoundsException& e ) {
                    throw decaf::util::NoSuchElementException(
                        __FILE__, __LINE__, "Add called without a next element to process." );
                }
            }

            virtual bool hasPrevious() const {
                return this->numLeft < this->parent->size();
            }

            virtual int nextIndex() const {
                return this->parent->size() - this->numLeft;
            }

            virtual E previous() {

                if( this->expectedModCount != this->parent->modCount ) {
                    throw ConcurrentModificationException(
                        __FILE__, __LINE__, "Concurrent Modification detected." );
                }

                try {

                    int index = this->parent->size() - this->numLeft - 1;
                    E result = this->parent->get( index );
                    this->numLeft++;
                    this->lastPosition = index;

                    return result;
                } catch( decaf::lang::exceptions::IndexOutOfBoundsException& e ) {
                    throw decaf::util::NoSuchElementException(
                        __FILE__, __LINE__, "No previous element exists." );
                }
            }

            virtual int previousIndex() const {
                return this->parent->size() - this->numLeft - 1;
            }

            virtual void set( const E& value ) {

                if( this->expectedModCount != this->parent->modCount ) {
                    throw ConcurrentModificationException(
                        __FILE__, __LINE__, "Concurrent Modification detected." );
                }

                try {
                    this->parent->set( this->lastPosition, value );
                } catch( decaf::lang::exceptions::IndexOutOfBoundsException& e ) {
                    throw decaf::lang::exceptions::IllegalStateException();
                }
            }
        };

        class ConstSimpleListIterator : public ListIterator<E> {
        protected:

            const AbstractList<E>* parent;
            int numLeft;
            int expectedModCount;
            int lastPosition;

        private:

            ConstSimpleListIterator( const ConstSimpleListIterator& );
            ConstSimpleListIterator operator= ( const ConstSimpleListIterator& );

        public:

            ConstSimpleListIterator( const AbstractList<E>* parent, int start ) :
                ListIterator<E>(), parent(parent), numLeft(0), expectedModCount(0), lastPosition(-1) {

                if( parent == NULL ) {
                    throw decaf::lang::exceptions::NullPointerException(
                        __FILE__, __LINE__, "List Iterator constructed with NULL parent" );
                }

                if( start < 0 || start > parent->size() ) {
                    throw decaf::lang::exceptions::IndexOutOfBoundsException(
                         __FILE__, __LINE__, "start index passed was negative or greater than size()" );
                }

                this->numLeft = parent->size() - start;
                this->parent = parent;
                this->expectedModCount = parent->modCount;
            }

            virtual ~ConstSimpleListIterator() {}

            virtual bool hasNext() const {
                return this->numLeft > 0;
            }

            virtual E next() {

                if( this->expectedModCount != this->parent->modCount ) {
                    throw ConcurrentModificationException(
                        __FILE__, __LINE__, "Concurrent Modification of Parent List detected." );
                }

                try {

                    int index = this->parent->size() - this->numLeft;
                    E result = this->parent->get( index );
                    this->lastPosition = index;
                    this->numLeft--;

                    return result;
                } catch( decaf::lang::exceptions::IndexOutOfBoundsException& e ) {
                    throw decaf::util::NoSuchElementException(
                        __FILE__, __LINE__, "Next called without a next element to process." );
                }
            }

            virtual void remove() {
                throw lang::exceptions::UnsupportedOperationException(
                    __FILE__, __LINE__,
                    "AbstractList::Iterator::remove - Const Iterator." );
            }

            virtual void add( const E& value DECAF_UNUSED ) {
                throw lang::exceptions::UnsupportedOperationException(
                    __FILE__, __LINE__,
                    "AbstractList::ListIterator::radd - Const Iterator." );
            }

            virtual bool hasPrevious() const {
                return this->numLeft < this->parent->size();
            }

            virtual int nextIndex() const {
                return this->parent->size() - this->numLeft;
            }

            virtual E previous() {

                if( this->expectedModCount != this->parent->modCount ) {
                    throw ConcurrentModificationException(
                        __FILE__, __LINE__, "Concurrent Modification detected." );
                }

                try {

                    int index = this->parent->size() - this->numLeft - 1;
                    E result = this->parent->get( index );
                    this->numLeft++;
                    this->lastPosition = index;

                    return result;
                } catch( decaf::lang::exceptions::IndexOutOfBoundsException& e ) {
                    throw decaf::util::NoSuchElementException(
                        __FILE__, __LINE__, "No previous element exists." );
                }
            }

            virtual int previousIndex() const {
                return this->parent->size() - this->numLeft - 1;
            }

            virtual void set( const E& value DECAF_UNUSED ) {
                throw lang::exceptions::UnsupportedOperationException(
                    __FILE__, __LINE__,
                    "AbstractList::ListIterator::set - Const Iterator." );
            }
        };

    public:

        AbstractList() : modCount( 0 ) {}

        virtual ~AbstractList() {}

        virtual Iterator<E>* iterator() {
            return new SimpleListIterator( this, 0 );
        }
        virtual Iterator<E>* iterator() const {
            return new ConstSimpleListIterator( this, 0 );
        }

        virtual ListIterator<E>* listIterator() {
            return new SimpleListIterator( this, 0 );
        }
        virtual ListIterator<E>* listIterator() const {
            return new ConstSimpleListIterator( this, 0 );
        }

        virtual ListIterator<E>* listIterator( int index ) {
            return new SimpleListIterator( this, index );
        }
        virtual ListIterator<E>* listIterator( int index ) const {
            return new ConstSimpleListIterator( this, index );
        }

        virtual void clear() {
            this->removeRange( 0, this->size() );
        }

        virtual bool add( const E& value ) {
            this->add( this->size(), value );
            return true;
        }

        virtual void add( int index DECAF_UNUSED, const E& element DECAF_UNUSED ) {
            throw decaf::lang::exceptions::UnsupportedOperationException(
                __FILE__, __LINE__, "Abstract list does not implement the add method." );
        }

        // Use this method since our own addAll will hide the base class version.
        using AbstractCollection<E>::addAll;

        virtual bool addAll( int index, const Collection<E>& source )  {
            std::auto_ptr< decaf::util::Iterator<E> > iter( source.iterator() );
            while( iter->hasNext() ) {
                this->add( index++, iter->next() );
            }

            return !source.isEmpty();
        }

        virtual E removeAt( int index DECAF_UNUSED )  {
            throw decaf::lang::exceptions::UnsupportedOperationException(
                __FILE__, __LINE__, "Abstract list does not implement the removeAt method." );
        }

        virtual E set( int index DECAF_UNUSED, const E& element DECAF_UNUSED ) {
            throw decaf::lang::exceptions::UnsupportedOperationException(
                __FILE__, __LINE__, "Abstract list does not implement the set method." );
        }

        virtual int indexOf( const E& value ) const {

            std::auto_ptr< decaf::util::ListIterator<E> > iter( this->listIterator() );

            while( iter->hasNext() ) {

                if( value == iter->next() ) {
                    return iter->previousIndex();
                }
            }

            return -1;
        }

        virtual int lastIndexOf( const E& value ) const {

            std::auto_ptr< decaf::util::ListIterator<E> > iter( this->listIterator( this->size() ) );

            while( iter->hasPrevious() ) {

                if( value == iter->previous() ) {
                    return iter->nextIndex();
                }
            }

            return -1;
        }

    protected:

        void removeRange( int start, int end ) {
            std::auto_ptr< decaf::util::Iterator<E> > iter( this->listIterator( start ) );
            for( int i = start; i < end; i++ ) {
                iter->next();
                iter->remove();
            }
        }

    };

}}

#endif /* _DECAF_UTIL_ABSTRACTLIST_H_ */