/*
 * Jakelib2 - General purpose C++ library
 * Copyright (C) 2001 Florian Wolff  (florian@donuz.de)
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 * $Id: AbstractList.h,v 1.7 2003/02/18 17:01:19 alfa Exp $
 */

#ifndef INCLUDE_JAKELIB2_UTIL_ABSTRACTLIST_H
# define INCLUDE_JAKELIB2_UTIL_ABSTRACTLIST_H
#include "AbstractCollection.h"
#include "List.h"

namespace jakelib {
  namespace util {
    class ListIterator;

    /**
     * @brief A basic implementation of most of the methods in the List interface to make
     * it easier to create a List based on a random-access data structure. If
     * the list is sequential (such as a linked list), use AbstractSequentialList.
     * To create an unmodifiable list, it is only necessary to override the
     * size() and get(int) methods (this contrasts with all other abstract
     * collection classes which require an iterator to be provided). To make the
     * list modifiable, the set(int, Object) method should also be overridden, and
     * to make the list resizable, the add(int, Object) and remove(int) methods
     * should be overridden too. Other methods should be overridden if the
     * backing data structure allows for a more efficient implementation.
     * The precise implementation used by AbstractList is documented, so that
     * subclasses can tell which methods could be implemented more efficiently.
     *
     * As recommended by Collection and List, the subclass should provide at
     * least a no-argument and a Collection constructor. This class is not
     * synchronized.
     *
     * @class AbstractList
     * @version $Id: AbstractList.h,v 1.7 2003/02/18 17:01:19 alfa Exp $
     * @author Eric Blake <ebb9@email.byu.edu>
     * @author Florian 'Overflo' Wolff (florian@donuz.de)
     */
    class AbstractList : public AbstractCollection, virtual public List
      {
      protected:

	/**
	 * @brief A count of the number of structural modifications that have been made to
	 * the list (that is, insertions and removals). Structural modifications
	 * are ones which change the list size or affect how iterations would
	 * behave. This field is available for use by Iterator and ListIterator,
	 * in order to throw a {@link ConcurrentModificationException} in response
	 * to the next operation on the iterator. This <i>fail-fast</i> behavior
	 * saves the user from many subtle bugs otherwise possible from concurrent
	 * modification during iteration.
	 * <p>
	 *
	 * To make lists fail-fast, increment this field by just 1 in the
	 * <code>add(int, Object)</code> and <code>remove(int)</code> methods.
	 * Otherwise, this field may be ignored.
	 */
	//int modCount;

	/**
	 * @brief The main constructor, for use by subclasses.
	 */
	AbstractList();

	/**
	 * @brief Remove a subsection of the list. This is called by the clear and
	 * removeRange methods of the class which implements subList, which are
	 * difficult for subclasses to override directly. Therefore, this method
	 * should be overridden instead by the more efficient implementation, if one
	 * exists. Overriding this can reduce quadratic efforts to constant time
	 * in some cases!
	 * <p>
	 *
	 * This implementation first checks for illegal or out of range arguments. It
	 * then obtains a ListIterator over the list using listIterator(fromIndex).
	 * It then calls next() and remove() on this iterator repeatedly, toIndex -
	 * fromIndex times.
	 *
	 * @param fromIndex the index, inclusive, to remove from.
	 * @param toIndex the index, exclusive, to remove to.
	 */
	void removeRange(int fromIndex, int toIndex);

      public:

	/**
	 * @brief Returns the elements at the specified position in the list.
	 *
	 * @param index the element to return
	 * @return the element at that position
	 * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
	 */
	virtual jakelib::lang::Object* get(int index) = 0;

	/**
	 * @brief Insert an element into the list at a given position (optional operation).
	 * This shifts all existing elements from that position to the end one
	 * index to the right.  This version of add has no return, since it is
	 * assumed to always succeed if there is no exception. This implementation
	 * always throws UnsupportedOperationException, and must be overridden to
	 * make a modifiable List.  If you want fail-fast iterators, be sure to
	 * increment modCount when overriding this.
	 *
	 * @param index the location to insert the item
	 * @param o the object to insert
	 * @throws UnsupportedOperationException if this list does not support the
	 *         add operation
	 * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
	 * @throws ClassCastException if o cannot be added to this list due to its
	 *         type
	 * @throws IllegalArgumentException if o cannot be added to this list for
	 *         some other reason
	 * @see #modCount
	 */
	void add(int index, jakelib::lang::Object* o);

	/**
	 * @brief Add an element to the end of the list (optional operation). If the list
	 * imposes restraints on what can be inserted, such as no null elements,
	 * this should be documented. This implementation calls
	 * <code>add(size(), o);</code>, and will fail if that version does.
	 *
	 * @param o the object to add
	 * @return true, as defined by Collection for a modified list
	 * @throws UnsupportedOperationException if this list does not support the
	 *         add operation
	 * @throws ClassCastException if o cannot be added to this list due to its
	 *         type
	 * @throws IllegalArgumentException if o cannot be added to this list for
	 *         some other reason
	 * @see #add(int, Object)
	 */
	jboolean add(jakelib::lang::Object* o);

	/**
	 * @brief Insert the contents of a collection into the list at a given position
	 * (optional operation). Shift all elements at that position to the right
	 * by the number of elements inserted. This operation is undefined if
	 * this list is modified during the operation (for example, if you try
	 * to insert a list into itself). This implementation uses the iterator of
	 * the collection, repeatedly calling add(int, Object); this will fail
	 * if add does. This can often be made more efficient.
	 *
	 * @param index the location to insert the collection
	 * @param c the collection to insert
	 * @return true if the list was modified by this action, that is, if c is
	 *         non-empty
	 * @throws UnsupportedOperationException if this list does not support the
	 *         addAll operation
	 * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
	 * @throws ClassCastException if some element of c cannot be added to this
	 *         list due to its type
	 * @throws IllegalArgumentException if some element of c cannot be added
	 *         to this list for some other reason
	 * @throws NullPointerException if the specified collection is null
	 * @see #add(int, Object)
	 */
	jboolean addAll(int index, Collection* c);

	/**
	 * @brief Clear the list, such that a subsequent call to isEmpty() would return
	 * true (optional operation). This implementation calls
	 * <code>removeRange(0, size())</code>, so it will fail unless remove
	 * or removeRange is overridden.
	 *
	 * @throws UnsupportedOperationException if this list does not support the
	 *         clear operation
	 * @see #remove(int)
	 * @see #removeRange(int, int)
	 */
	void clear();

	/**
	 * @brief Test whether this list is equal to another object. A List is defined to be
	 * equal to an object if and only if that object is also a List, and the two
	 * lists have the same sequence. Two lists l1 and l2 are equal if and only
	 * if <code>l1.size() == l2.size()</code>, and for every integer n between 0
	 * and <code>l1.size() - 1</code> inclusive, <code>l1.get(n) == null ?
	 * l2.get(n) == null : l1.get(n).equals(l2.get(n))</code>.
	 * <p>
	 *
	 * This implementation returns true if the object is this, or false if the
	 * object is not a List.  Otherwise, it iterates over both lists (with
	 * iterator()), returning false if two elements compare false or one list
	 * is shorter, and true if the iteration completes successfully.
	 *
	 * @param o the object to test for equality with this list
	 * @return true if o is equal to this list
	 * @see Object#equals(Object)
	 * @see #hashCode()
	 */
	jboolean equals(jakelib::lang::Object* o);

	/**
	 * @brief Obtain a hash code for this list. In order to obey the general contract of
	 * the hashCode method of class Object, this value is calculated as follows:
	 * <pre>
	 *   hashCode = 1;
	 *   Iterator i = list.iterator();
	 *   while (i.hasNext())
	 *     {
	 *       Object obj = i.next();
	 *       hashCode = 31 * hashCode + (obj == null ? 0 : obj.hashCode());
	 *     }
	 * </pre>
	 * This ensures that the general contract of Object.hashCode() is adhered to.
	 *
	 * @return the hash code of this list
	 * @see Object#hashCode()
	 * @see #equals(Object)
	 */
	int hashCode();

	/**
	 * @brief Obtain the first index at which a given object is to be found in this
	 * list. This implementation follows a listIterator() until a match is found,
	 * or returns -1 if the list end is reached.
	 *
	 * @param o the object to search for
	 * @return the least integer n such that <code>o == null ? get(n) == null :
	 *         o.equals(get(n))</code>, or -1 if there is no such index
	 */
	int indexOf(jakelib::lang::Object* o);

	/**
	 * @brief Obtain an Iterator over this list, whose sequence is the list order.
	 * This implementation uses size(), get(int), and remove(int) of the
	 * backing list, and does not support remove unless the list does. This
	 * implementation is fail-fast if you correctly maintain modCount.
	 * Also, this implementation is specified by Sun to be distinct from
	 * listIterator, although you could easily implement it as
	 * <code>return listIterator(0)</code>.
	 *
	 * @return an Iterator over the elements of this list, in order
	 * @see #modCount
	 */
	Iterator* iterator();

	/**
	 * @brief Obtain the last index at which a given object is to be found in this
	 * list. This implementation grabs listIterator(size()), then searches
	 * backwards for a match or returns -1.
	 *
	 * @return the greatest integer n such that <code>o == null ? get(n) == null
	 *         : o.equals(get(n))</code>, or -1 if there is no such index
	 */
	int lastIndexOf(jakelib::lang::Object* o);

	/**
	 * @brief Obtain a ListIterator over this list, starting at the beginning. This
	 * implementation returns listIterator(0).
	 *
	 * @return a ListIterator over the elements of this list, in order, starting
	 *         at the beginning
	 */
	ListIterator* listIterator();

	/**
	 * @brief Obtain a ListIterator over this list, starting at a given position.
	 * A first call to next() would return the same as get(index), and a
	 * first call to previous() would return the same as get(index - 1).
	 * <p>
	 *
	 * This implementation uses size(), get(int), set(int, Object),
	 * add(int, Object), and remove(int) of the backing list, and does not
	 * support remove, set, or add unless the list does. This implementation
	 * is fail-fast if you correctly maintain modCount.
	 *
	 * @param index the position, between 0 and size() inclusive, to begin the
	 *        iteration from
	 * @return a ListIterator over the elements of this list, in order, starting
	 *         at index
	 * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
	 * @see #modCount
	 */
	ListIterator* listIterator(int index);

	/**
	 * @brief Remove the element at a given position in this list (optional operation).
	 * Shifts all remaining elements to the left to fill the gap. This
	 * implementation always throws an UnsupportedOperationException.
	 * If you want fail-fast iterators, be sure to increment modCount when
	 * overriding this.
	 *
	 * @param index the position within the list of the object to remove
	 * @return the object that was removed
	 * @throws UnsupportedOperationException if this list does not support the
	 *         remove operation
	 * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
	 * @see #modCount
	 */
	jakelib::lang::Object* remove(int index);

	/**
	 * @brief Replace an element of this list with another object (optional operation).
	 * This implementation always throws an UnsupportedOperationException.
	 *
	 * @param index the position within this list of the element to be replaced
	 * @param o the object to replace it with
	 * @return the object that was replaced
	 * @throws UnsupportedOperationException if this list does not support the
	 *         set operation
	 * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
	 * @throws ClassCastException if o cannot be added to this list due to its
	 *         type
	 * @throws IllegalArgumentException if o cannot be added to this list for
	 *         some other reason
	 */
	jakelib::lang::Object* set(int index, jakelib::lang::Object* o);

	/**
	 * @brief Obtain a List view of a subsection of this list, from fromIndex
	 * (inclusive) to toIndex (exclusive). If the two indices are equal, the
	 * sublist is empty. The returned list should be modifiable if and only
	 * if this list is modifiable. Changes to the returned list should be
	 * reflected in this list. If this list is structurally modified in
	 * any way other than through the returned list, the result of any subsequent
	 * operations on the returned list is undefined.
	 * <p>
	 *
	 * This implementation returns a subclass of AbstractList. It stores, in
	 * private fields, the offset and size of the sublist, and the expected
	 * modCount of the backing list. If the backing list implements RandomAccess,
	 * the sublist will also.
	 * <p>
	 *
	 * The subclass's <code>set(int, Object)</code>, <code>get(int)</code>,
	 * <code>add(int, Object)</code>, <code>remove(int)</code>,
	 * <code>addAll(int, Collection)</code> and
	 * <code>removeRange(int, int)</code> methods all delegate to the
	 * corresponding methods on the backing abstract list, after
	 * bounds-checking the index and adjusting for the offset. The
	 * <code>addAll(Collection c)</code> method merely returns addAll(size, c).
	 * The <code>listIterator(int)</code> method returns a "wrapper object"
	 * over a list iterator on the backing list, which is created with the
	 * corresponding method on the backing list. The <code>iterator()</code>
	 * method merely returns listIterator(), and the <code>size()</code> method
	 * merely returns the subclass's size field.
	 * <p>
	 *
	 * All methods first check to see if the actual modCount of the backing
	 * list is equal to its expected value, and throw a
	 * ConcurrentModificationException if it is not. 
	 *
	 * @param fromIndex the index that the returned list should start from
	 *        (inclusive)
	 * @param toIndex the index that the returned list should go to (exclusive)
	 * @return a List backed by a subsection of this list
	 * @throws IndexOutOfBoundsException if fromIndex &lt; 0
	 *         || toIndex &gt; size()
	 * @throws IllegalArgumentException if fromIndex &gt; toIndex
	 * @see ConcurrentModificationException
	 * @see RandomAccess
	 */
	List* subList(int fromIndex, int toIndex);

	/**
	 * Get the number of elements in this collection.
	 * (Must be redeclared here to fool c++ compiler.)
         *
	 * @return the number of elements in the collection.
	 */
        int size() = 0;

	JAKELIB_DECLARE_CLASS(AbstractList);
      };
  }
}

#endif

