/* 
 * Kodkod -- Copyright (c) 2005-2011, Emina Torlak
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */
package kodkod.util.ints;

import java.util.AbstractCollection;
import java.util.Collection;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * A skeletal implementation of the SparseSequence interface.
 * The class provides an implementation for the <code>isEmpty</code>, 
 * <code>putAll</code>, <code>contains</code>, <code>indices</code>, <code>equals</code>, <code>hashCode</code>,
 * and <code>toString</code> methods.  All other methods must be
 * implemented by the subclasses. 
 * 
 * @specfield entries: int -> lone V
 * 
 * @author Emina Torlak
 */
public abstract class AbstractSparseSequence<V> implements SparseSequence<V> {

	/**
	 * Constructs a sparse sequence
	 * @ensures no this.entries'
	 */
	protected AbstractSparseSequence() {}
	
	/**
	 * Returns true if the size of this sequence is 0.
	 * @return this.size()==0
	 */
	public boolean isEmpty() { 
		return size()==0; 
	}
	
	/**
	 * Returns an iterator over the entries in this sequence
	 * in the ascending order of indeces, starting at this.first().
	 * This method calls this.iterator(Integer.MIN_VALUE, Integer.MAX_VALUE).
	 * @return an iterator over this.entries starting at the entry
	 * with the smallest index
	 */
	public Iterator<IndexedEntry<V>> iterator() {
		return iterator(Integer.MIN_VALUE, Integer.MAX_VALUE);
	}
	
	/**
	 * Returns the first element in this sequence, if any.  This
	 * method first checks that the sequence is not empty, and 
	 * if not, returns this.iterator().next();
	 * {@inheritDoc}
	 * @see kodkod.util.ints.SparseSequence#first()
	 */
	public IndexedEntry<V> first() {
		return isEmpty() ? null : iterator().next();
	}

	/**
	 * Returns the last element in this sequence, if any.  This
	 * method first checks that the sequence is not empty, and 
	 * if not, returns this.iterator(Integer.MAX_VALUE, Integer.MIN_VALUE).next();
	 * {@inheritDoc}
	 * @see kodkod.util.ints.SparseSequence#last()
	 */
	public IndexedEntry<V> last() {
		return isEmpty() ? null : iterator(Integer.MAX_VALUE, Integer.MIN_VALUE).next();
	}
	
	/**
	 * Returns the entry whose index is the ceiling of the given index in this sequence.
	 * This method calls this.iterator(index, Integer.MAX_VALUE), and if the resulting iterator has 
	 * a next element returns it. 
	 * {@inheritDoc}
	 * @see kodkod.util.ints.SparseSequence#ceil(int)
	 */
	public IndexedEntry<V> ceil(int index) {
		final Iterator<IndexedEntry<V>> itr = iterator(index, Integer.MAX_VALUE);
		return itr.hasNext() ? itr.next() : null;
	}
	
	/**
	 * Returns the entry whose index is the floor of the given index in this sequence.
	 * This method calls this.iterator(index, Integer.MIN_VALUE), and if the resulting iterator has 
	 * a next element returns it. 
	 * {@inheritDoc}
	 * @see kodkod.util.ints.SparseSequence#floor(int)
	 */
	public IndexedEntry<V> floor(int index) {
		final Iterator<IndexedEntry<V>> itr = iterator(index, Integer.MIN_VALUE);
		return itr.hasNext() ? itr.next() : null;
	}
	
	/**
	 * Returns the set of all indices mapped by this sparse sequence.
	 * The returned set supports removal iff this is not an unmodifiable
	 * sparse sequence.  
	 * @return {s: IntSet | s.ints = this.entries.V}
	 */
	public IntSet indices() {
		return new AbstractIntSet() {
			public IntIterator iterator(final int from, final int to) {
				return new IntIterator() {
					Iterator<IndexedEntry<V>> iter = AbstractSparseSequence.this.iterator(from, to);
					public boolean hasNext() {
						return iter.hasNext();
					}
					public int next() {
						return iter.next().index();
					}
					public void remove() {
						iter.remove();
					}
				};
			}
			public int size() {
				return AbstractSparseSequence.this.size();
			}
			public boolean contains(int i) {
				return containsIndex(i);
			}
			public int min() {
				final IndexedEntry<V> first = AbstractSparseSequence.this.first();
				if (first==null) 
					throw new NoSuchElementException();
				return first.index();
			}
			public int max() {
				final IndexedEntry<V> last = AbstractSparseSequence.this.last();
				if (last==null) 
					throw new NoSuchElementException();
				return last.index();
			}
			public boolean remove(int i) {
				final boolean isMapped = containsIndex(i);
				AbstractSparseSequence.this.remove(i);
				return isMapped;
			}
			public int floor(int i) {
				final IndexedEntry<V> floor = AbstractSparseSequence.this.floor(i);
				if (floor==null)
					throw new NoSuchElementException();
				return floor.index();
			}
			public int ceil(int i) {
				final IndexedEntry<V> ceil = AbstractSparseSequence.this.ceil(i);
				if (ceil==null)
					throw new NoSuchElementException();
				return ceil.index();
			}
			public void clear() {
				AbstractSparseSequence.this.clear();
			}
			public IntSet clone() throws CloneNotSupportedException { 
				final IntSet s;
				if (size()==0)
					s = Ints.bestSet(Integer.MIN_VALUE, Integer.MAX_VALUE);
				else 
					s = Ints.bestSet(min(), max());
				s.addAll(this);
				return s;
			}
		};
	}
	
	/**
	 * {@inheritDoc}
	 * @see kodkod.util.ints.SparseSequence#values()
	 */
	public Collection<V> values() {
		return new AbstractCollection<V>() {

			public int size() {
				return AbstractSparseSequence.this.size();
			}

			public boolean isEmpty() {
				return AbstractSparseSequence.this.isEmpty();
			}

			public boolean contains(Object arg0) {
				return AbstractSparseSequence.this.contains(arg0);
			}

			public Iterator<V> iterator() {
				return new Iterator<V>() {
					Iterator<IndexedEntry<V>> iter = AbstractSparseSequence.this.iterator();
					public boolean hasNext() {
						return iter.hasNext();
					}
					public V next() {
						return iter.next().value();
					}
					public void remove() {
						iter.remove();
					}
				};
			}
			
			public void clear() {
				AbstractSparseSequence.this.clear();
			}
		};
	}
	
	/**
	 * Returns true if this sparse sequence has an entry for the
	 * given index; otherwise returns false.  This method returns
	 * the value of this.iterator(index,index).hasNext();
	 * {@inheritDoc}
	 * @see kodkod.util.ints.SparseSequence#containsIndex(int)
	 */
	public boolean containsIndex(int index) {
		return iterator(index,index).hasNext();
	}
	
	/**
	 * Iterates through all the entries in this sequence and returns 
	 * true if one of the encountered entries has the given object as
	 * its value.
	 * @return {@inheritDoc}
	 * @see kodkod.util.ints.SparseSequence#contains(java.lang.Object)
	 */
	public boolean contains(Object value) {
		for(IndexedEntry<?> v: this) {
			if (equal(value, v.value()))
				return true;
		}
		return false;
	}
	
	/**
	 * Returns the result of calling super.clone().
	 * @see java.lang.Object#clone()
	 */
	@SuppressWarnings("unchecked")
	public SparseSequence<V> clone() throws CloneNotSupportedException {
		return (SparseSequence<V>) super.clone();
	}
	
	/*---------- adapted from java.util.AbstractMap -----------*/
		
	/**
	 * Removes the entry with the given index, if it exists, and
	 * returns the value previously stored at the index.  If the
	 * sequence had no previous mapping for the index, null is returned.
	 * This method obtains an iterator from index to index and removes
	 * its sole element, if any.
	 * {@inheritDoc}
	 * @see kodkod.util.ints.SparseSequence#remove(int)
	 */
	public V remove(int index) {
		final Iterator<IndexedEntry<V>> itr = iterator(index,index);
		if (itr.hasNext()) {
			final V ret = itr.next().value();
			itr.remove();
			return ret;
		}
		return null;
	}
	
	/**
	 * Removes all entries from this sequences.  This method
	 * obtains an iterator over the sequences and calls remove()
	 * after each call to next().
	 * {@inheritDoc}
	 * @see kodkod.util.ints.SparseSequence#clear()
	 */
	public void clear() {
		final Iterator<IndexedEntry<V>> itr = iterator();
		while(itr.hasNext()) {
			itr.next();
			itr.remove();
		}
	}
	
	
	/**
	 * Throws an UnsupportedOperationException.
	 * @throws UnsupportedOperationException
	 */
	public V put(int index, V value) {
		throw new UnsupportedOperationException();
	}
	
	/**
	 * Copies all of the entries from the specified sparse sequence to 
	 * this sequence. This implementation calls put(e.index, e.value) on 
	 * this sequence once for each entry e in the specified sequence. 
     * @ensures this.entries' = this.entries ++ s.entries
	 */
	public void putAll(SparseSequence<? extends V> s) {
		Iterator<? extends IndexedEntry<? extends V>> i = s.iterator();
		while (i.hasNext()) {
			IndexedEntry<? extends V> e = i.next();
			put(e.index(), e.value());
		}
	}
	
	/**
	 * Returns true if both o1 and o2 are null, or 
	 * o1.equals(o2)
	 * @return o1 and o2 are equal
	 */
	static boolean equal(Object o1, Object o2) {
		return o1==null ? o2==null : o1.equals(o2);
	}
	
	/**
	 * Returns true if the indexed entries e0 and e1 are equal to each other.
	 * @requires e0 != null && e1 != null
	 * @return e0.index = e1.index && e0.value = e1.value
	 */
	static boolean equal(IndexedEntry<?> e0, IndexedEntry<?> e1) {
		return e0.index()==e1.index() && equal(e0.value(), e1.value());
	}
	
	/**
	 * Compares the specified object with this sequence for equality.  Returns
	 * <tt>true</tt> if the given object is also a sequence and the two sequences
	 * represent the same function from integers to E.<p>
	 *
	 * This implementation first checks if the specified object is this sequence;
	 * if so it returns <tt>true</tt>.  Then, it checks if the specified
	 * object is a sequence whose size is identical to the size of this set; if
	 * not, it returns <tt>false</tt>.  If so, it iterates over this sequences's
	 * entries, and checks that the specified sequence
	 * contains each entry that this sequence contains.  If the specified sequence
	 * fails to contain such an entry, <tt>false</tt> is returned.  If the
	 * iteration completes, <tt>true</tt> is returned.
	 * @return  o in SparseSequence && o.entries = this.entries
	 */
	@SuppressWarnings("unchecked")
	public boolean equals(Object o) {
		if (o == this) return true;
		
		if (!(o instanceof SparseSequence)) return false;
		
		SparseSequence<V> s = (SparseSequence<V>) o;
		if (s.size() != size()) return false;
		
		try {
			final Iterator<IndexedEntry<V>> i1 = iterator(), i2 = s.iterator();
			while (i1.hasNext()) {
				if (!equal(i1.next(), i2.next())) 
					return false;
			}
		} catch(ClassCastException unused) {
			return false;
		} catch(NullPointerException unused) {
			return false;
		}
		
		return true;
	}
	
	/**
	 * Returns the hashcode for an indexed entry.
	 * @requires e !=  null
	 * @return e.index ^ e.value.hashCode()
	 */
	static int hashCode(IndexedEntry<?> e) {
		return e.index() ^ (e.value()==null ? 0 : e.value().hashCode());
	}
	
	/**
	 * Returns the hash code value for this sparse sequence. 
	 * The hash code of a sparse sequence is defined to be the sum of the 
	 * hashCodes of each entry of its entries. This ensures that t1.equals(t2) 
	 * implies that t1.hashCode()==t2.hashCode() for any two sequences t1 and t2, 
	 * as required by the general contract of Object.hashCode.
	 * This implementation iterates over this.entries, calling
	 * <tt>hashCode</tt> on each IndexedEntry in the sequence, and adding
	 * up the results.
	 * @return sum(this.entries.hashCode())
	 */
	public int hashCode() {
		int h = 0;
		for (IndexedEntry<V> e : this)
			h += hashCode(e);
		return h;
	}
	
	/**
	 * Returns a string representation of this sequence.  The string representation
	 * consists of a list of index-value mappings in the order returned by the
	 * sequences <tt>iterator</tt>, enclosed in brackets
	 * (<tt>"[]"</tt>).  Adjacent entries are separated by the characters
	 * <tt>", "</tt> (comma and space).  Each index-value mapping is rendered as
	 * the index followed by an equals sign (<tt>"="</tt>) followed by the
	 * associated value.  Elements are converted to strings as by
	 * <tt>String.valueOf(Object)</tt>.<p>
	 *
	 * This implementation creates an empty string buffer, appends a left
	 * bracket, and iterates over the map's entries, appending
	 * the string representation of each <tt>IndexedEntry</tt> in turn.  After
	 * appending each entry except the last, the string <tt>", "</tt> is
	 * appended.  Finally a right bracket is appended.  A string is obtained
	 * from the stringbuffer, and returned.
	 *
	 * @return a String representation of this map.
	 */
	public String toString() {
		final StringBuilder buf = new StringBuilder();
		buf.append("[");
		
		final Iterator<IndexedEntry<V>> i = iterator();
		boolean hasNext = i.hasNext();
		while (hasNext) {
			IndexedEntry<V> e = i.next();
			buf.append(e.index());
			buf.append("=");
			if (e.value() == this)
				buf.append("(this sequence)");
			else
				buf.append(e.value());
			hasNext = i.hasNext();
			if (hasNext) buf.append(", ");
		}
		
		buf.append("]");
		return buf.toString();
	}

	
}
