kodkod.util.ints

Class AbstractSparseSequence<V>

java.lang.Object

kodkod.util.ints.AbstractSparseSequence<V>

All Implemented Interfaces:

Iterable<IndexedEntry<V>>, SparseSequence<V>

Direct Known Subclasses:

ArraySequence, HomogenousSequence, RangeSequence, TreeSequence

public abstract class AbstractSparseSequence<V>
extends Object
implements SparseSequence<V>

A skeletal implementation of the SparseSequence interface. The class provides an implementation for the isEmpty, putAll, contains, indices, equals, hashCode, and toString methods. All other methods must be implemented by the subclasses.

Author:

Emina Torlak

Specfields:

entries: int -> lone V

Method Summary

Modifier and Type	Method and Description
IndexedEntry<V>	ceil(int index) Returns the entry whose index is the ceiling of the given index in this sequence.
void	clear() Removes all entries from this sequences.
SparseSequence<V>	clone() Returns the result of calling super.clone().
boolean	contains(Object value) Iterates through all the entries in this sequence and returns true if one of the encountered entries has the given object as its value.
boolean	containsIndex(int index) Returns true if this sparse sequence has an entry for the given index; otherwise returns false.
boolean	equals(Object o) Compares the specified object with this sequence for equality.
IndexedEntry<V>	first() Returns the first element in this sequence, if any.
IndexedEntry<V>	floor(int index) Returns the entry whose index is the floor of the given index in this sequence.
int	hashCode() Returns the hash code value for this sparse sequence.
IntSet	indices() Returns the set of all indices mapped by this sparse sequence.
boolean	isEmpty() Returns true if the size of this sequence is 0.
Iterator<IndexedEntry<V>>	iterator() Returns an iterator over the entries in this sequence in the ascending order of indeces, starting at this.first().
IndexedEntry<V>	last() Returns the last element in this sequence, if any.
V	put(int index, V value) Throws an UnsupportedOperationException.
void	putAll(SparseSequence<? extends V> s) Copies all of the entries from the specified sparse sequence to this sequence.
V	remove(int index) Removes the entry with the given index, if it exists, and returns the value previously stored at the index.
String	toString() Returns a string representation of this sequence.
Collection<V>	values() Returns a Collection view of the values stored in this sequence.

Methods inherited from class java.lang.Object

getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface kodkod.util.ints.SparseSequence

get, iterator, size

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Method Detail

ceil

public IndexedEntry<V> ceil(int index)

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. If an entry for the given index exists, it is returned. Otherwise, successor(index) is returned.

Specified by:

ceil in interface SparseSequence<V>

Returns:

this.containsIndex(index) => {e: IndexedEntry | e.index = index && e.value = this.entries[index] }, successor(index)

See Also:

SparseSequence.ceil(int)

clear

public void clear()

Removes all entries from this sequences. This method obtains an iterator over the sequences and calls remove() after each call to next(). Removes all entries from this sequences.

Specified by:

clear in interface SparseSequence<V>

Ensures:

no this.entries'

See Also:

SparseSequence.clear()

clone

public SparseSequence<V> clone()
                        throws CloneNotSupportedException

Returns the result of calling super.clone().

Specified by:

clone in interface SparseSequence<V>

Overrides:

clone in class Object

Returns:

a copy of this sparse sequence.

Throws:

CloneNotSupportedException - this is not cloneable

See Also:

Object.clone()

contains

public boolean contains(Object value)

Iterates through all the entries in this sequence and returns true if one of the encountered entries has the given object as its value.

Specified by:

contains in interface SparseSequence<V>

Returns:

some this.entries.value

See Also:

SparseSequence.contains(java.lang.Object)

containsIndex

public boolean containsIndex(int index)

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(); Returns true if this sparse sequence has an entry for the given index; otherwise returns false.

Specified by:

containsIndex in interface SparseSequence<V>

Returns:

some this.entries[index]

See Also:

SparseSequence.containsIndex(int)

equals

public boolean equals(Object o)

Compares the specified object with this sequence for equality. Returns true if the given object is also a sequence and the two sequences represent the same function from integers to E.

This implementation first checks if the specified object is this sequence; if so it returns true. Then, it checks if the specified object is a sequence whose size is identical to the size of this set; if not, it returns false. 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, false is returned. If the iteration completes, true is returned.

Specified by:

equals in interface SparseSequence<V>

Overrides:

equals in class Object

Returns:

o in SparseSequence && o.entries = this.entries

first

public IndexedEntry<V> first()

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(); Returns the entry with the smallest index. If the sequence is empty, returns null.

Specified by:

first in interface SparseSequence<V>

Returns:

{e: IndexedEntry | e.index = min(this.entries.E) && e.value = this.entries[e.index] }

See Also:

SparseSequence.first()

floor

public IndexedEntry<V> floor(int index)

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. If an entry for the given index exists, it is returned. Otherwise, predecessor(index) is returned.

Specified by:

floor in interface SparseSequence<V>

Returns:

this.containsIndex(index) => {e: IndexedEntry | e.index = index && e.value = this.entries[index] }, predecessor(index)

See Also:

SparseSequence.floor(int)

hashCode

public int 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 hashCode on each IndexedEntry in the sequence, and adding up the results.

Specified by:

hashCode in interface SparseSequence<V>

Overrides:

hashCode in class Object

Returns:

sum(this.entries.hashCode())

indices

public IntSet indices()

Returns the set of all indices mapped by this sparse sequence. The returned set supports removal iff this is not an unmodifiable sparse sequence.

Specified by:

indices in interface SparseSequence<V>

Returns:

{s: IntSet | s.ints = this.entries.V}

isEmpty

public boolean isEmpty()

Returns true if the size of this sequence is 0.

Specified by:

isEmpty in interface SparseSequence<V>

Returns:

this.size()==0

iterator

public Iterator<IndexedEntry<V>> iterator()

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).

Specified by:

iterator in interface Iterable<IndexedEntry<V>>

Specified by:

iterator in interface SparseSequence<V>

Returns:

an iterator over this.entries starting at the entry with the smallest index

last

public IndexedEntry<V> last()

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(); Returns the entry with the largest index. If the sequence is empty, returns null.

Specified by:

last in interface SparseSequence<V>

Returns:

{e: IndexedEntry | e.index = max(this.entries.E) && e.value = this.entries[e.index] }

See Also:

SparseSequence.last()

put

public V put(int index,
             V value)

Throws an UnsupportedOperationException.

Specified by:

put in interface SparseSequence<V>

Ensures:

this.entries' = this.entries + index->value

Returns:

this.entries[index]

Throws:

UnsupportedOperationException

putAll

public void putAll(SparseSequence<? extends V> s)

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.

Specified by:

putAll in interface SparseSequence<V>

Ensures:

this.entries' = this.entries ++ s.entries

remove

public V remove(int index)

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. 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.

Specified by:

remove in interface SparseSequence<V>

Ensures:

this.entries' = this.entries - index->E

Returns:

this.entries[index]

See Also:

SparseSequence.remove(int)

toString

public String toString()

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 iterator, enclosed in brackets ("[]"). Adjacent entries are separated by the characters ", " (comma and space). Each index-value mapping is rendered as the index followed by an equals sign ("=") followed by the associated value. Elements are converted to strings as by String.valueOf(Object).

This implementation creates an empty string buffer, appends a left bracket, and iterates over the map's entries, appending the string representation of each IndexedEntry in turn. After appending each entry except the last, the string ", " is appended. Finally a right bracket is appended. A string is obtained from the stringbuffer, and returned.

Overrides:

toString in class Object

Returns:

a String representation of this map.

values

public Collection<V> values()

Returns a Collection view of the values stored in this sequence. The returned collection supports removal iff this is not an unmodifiable sparse sequence.

Specified by:

values in interface SparseSequence<V>

Returns:

{c: Collection | c.size()=this.size() && all v: V | c.contains(v) <=> this.contains(v) }

See Also:

SparseSequence.values()