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

    /**
     * This class provides a skeletal implementation of the List  interface to minimize
     * the effort required to implement this interface backed by a "random access" data
     * store (such as an array). For sequential access data (such as a linked list),
     * AbstractSequentialList should be used in preference to this class.
     *
     * To implement an unmodifiable list, the programmer needs only to extend this class
     * and provide implementations for the get(int) and size() methods.
     *
     * To implement a modifiable list, the programmer must additionally override the
     * set(int, E) method (which otherwise throws an UnsupportedOperationException). If
     * the list is variable-size the programmer must additionally override the add(int, E)
     * and remove(int) methods.
     *
     * The programmer should generally provide a void (no argument) and collection
     * constructor, as per the recommendation in the Collection interface specification.
     *
     * Unlike the other abstract collection implementations, the programmer does not have
     * to provide an iterator implementation; the iterator and list iterator are implemented
     * by this class, on top of the "random access" methods: get(int), set(int, E),
     * add(int, E) and remove(int).
     *
     * The documentation for each non-abstract method in this class describes its
     * implementation in detail. Each of these methods may be overridden if the collection
     * being implemented admits a more efficient implementation.
     *
     * @since 1.0
     */
    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_ */