kodkod.util.ints

Class TreeSequence<V>

java.lang.Object

kodkod.util.ints.AbstractSparseSequence<V>

kodkod.util.ints.TreeSequence<V>

All Implemented Interfaces:

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

public final class TreeSequence<V>
extends AbstractSparseSequence<V>
implements Cloneable

An implementation of a sparse sequence based on a balanced binary search tree.

Author:

Emina Torlak

Constructor Summary

Constructors

Constructor and Description
TreeSequence() Constructs an empty tree sequence.

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.
TreeSequence<V>	clone() Returns a copy of this sparse sequence.
boolean	containsIndex(int index) Returns true if this sparse sequence has an entry for the given index; otherwise returns false.
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.
V	get(int index) Returns the value to which this sequence maps the given index.
Iterator<IndexedEntry<V>>	iterator(int from, int to) Returns an iterator over the entries in this sequence, whose indeces are between from and to.
IndexedEntry<V>	last() Returns the last element in this sequence, if any.
V	put(int index, V value) Throws an UnsupportedOperationException.
V	remove(int index) Removes the entry with the given index, if it exists, and returns the value previously stored at the index.
int	size() Returns the number of entries in this sequence.

Methods inherited from class kodkod.util.ints.AbstractSparseSequence

contains, equals, hashCode, indices, isEmpty, iterator, putAll, toString, values

Methods inherited from class java.lang.Object

getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Constructor Detail

TreeSequence

public TreeSequence()

Constructs an empty tree sequence.

Ensures:

no this.entries'

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>

Overrides:

ceil in class AbstractSparseSequence<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.

Specified by:

clear in interface SparseSequence<V>

Overrides:

clear in class AbstractSparseSequence<V>

Ensures:

no this.entries'

See Also:

SparseSequence.clear()

clone

public TreeSequence<V> clone()

Returns a copy of this sparse sequence. The copy is independent of this sequence.

Specified by:

clone in interface SparseSequence<V>

Overrides:

clone in class AbstractSparseSequence<V>

Returns:

a copy of this sparse sequence.

See Also:

SparseSequence.clone()

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>

Overrides:

containsIndex in class AbstractSparseSequence<V>

Returns:

some this.entries[index]

See Also:

SparseSequence.containsIndex(int)

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>

Overrides:

first in class AbstractSparseSequence<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>

Overrides:

floor in class AbstractSparseSequence<V>

Returns:

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

See Also:

SparseSequence.floor(int)

get

public V get(int index)

Returns the value to which this sequence maps the given index. If the index is not mapped, null is returned.

Specified by:

get in interface SparseSequence<V>

Returns:

this.entries[index]

See Also:

SparseSequence.get(int)

iterator

public Iterator<IndexedEntry<V>> iterator(int from,
                                          int to)

Returns an iterator over the entries in this sequence, whose indeces are between from and to. If from < to, the entries are returned in the ascending order of indeces. Otherwise, they are returned in the descending order of indeces.

Specified by:

iterator in interface SparseSequence<V>

Returns:

an iterator over the entries in this sequence whose indeces are between from and to. Formally, if from < to, then the first and last entries returned by the iterator are this.ceil(from) and this.floor(to). Otherwise, they are this.floor(from) and this.ceil(to).

See Also:

SparseSequence.iterator(int, int)

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>

Overrides:

last in class AbstractSparseSequence<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>

Overrides:

put in class AbstractSparseSequence<V>

Ensures:

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

Returns:

this.entries[index]

See Also:

SparseSequence.put(int, Object)

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.

Specified by:

remove in interface SparseSequence<V>

Overrides:

remove in class AbstractSparseSequence<V>

Ensures:

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

Returns:

this.entries[index]

See Also:

SparseSequence.remove(int)

size

public int size()

Returns the number of entries in this sequence.

Specified by:

size in interface SparseSequence<V>

Returns:

#this.entries

See Also:

SparseSequence.size()