org.key_project.util.collection

Class ImmutableLeftistHeap<T extends java.lang.Comparable<T>>

java.lang.Object

org.key_project.util.collection.ImmutableLeftistHeap<T>

All Implemented Interfaces:

java.io.Serializable, java.lang.Iterable<T>, ImmutableHeap<T>

Direct Known Subclasses:

ImmutableLeftistHeap.Empty, ImmutableLeftistHeap.Node

public abstract class ImmutableLeftistHeap<T extends java.lang.Comparable<T>>
extends java.lang.Object
implements ImmutableHeap<T>

This class implements the leftist heap, see "Functional Data Structures" by Chris Okasaki

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
private static class	ImmutableLeftistHeap.Empty<S extends java.lang.Comparable<S>> Singleton class for empty heaps
private static class	ImmutableLeftistHeap.Node<S extends java.lang.Comparable<S>> Class for non-empty heaps
private static class	ImmutableLeftistHeap.SortedIterator<T extends java.lang.Comparable<T>> Class for iterating the elements of a heap in increasing order
private static class	ImmutableLeftistHeap.UnsortedIterator<T extends java.lang.Comparable<T>> Class for iterating the elements of a heap in unspecified order

Field Summary

Fields

Modifier and Type	Field and Description
private static long	serialVersionUID

Constructor Summary

Constructors

Constructor and Description
ImmutableLeftistHeap()

Method Summary

Modifier and Type	Method and Description
protected abstract int	getRightHeight() Length of the right spine, i.e. the length of the path from the root to rightmost leaf
ImmutableHeap<T>	insert(java.util.Iterator<T> elements) Add multiple elements to this heap object
java.util.Iterator<T>	iterator()
static <T extends java.lang.Comparable<T>> ImmutableLeftistHeap<T>	nilHeap()
java.util.Iterator<T>	sortedIterator()
java.lang.String	toString()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface org.key_project.util.collection.ImmutableHeap

deleteMin, findMin, insert, insert, isEmpty, removeAll, size

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Field Detail

serialVersionUID

private static final long serialVersionUID

See Also:

Constant Field Values

Constructor Detail

ImmutableLeftistHeap

public ImmutableLeftistHeap()

Method Detail

nilHeap

public static <T extends java.lang.Comparable<T>> ImmutableLeftistHeap<T> nilHeap()

getRightHeight

protected abstract int getRightHeight()

Length of the right spine, i.e. the length of the path from the root to rightmost leaf

insert

public ImmutableHeap<T> insert(java.util.Iterator<T> elements)

Add multiple elements to this heap object

Specified by:

insert in interface ImmutableHeap<T extends java.lang.Comparable<T>>

Parameters:

elements - the elements to be added

Returns:

a heap that contains all elements of this heap, and additionally all objects from elements

iterator

public java.util.Iterator<T> iterator()

Specified by:

iterator in interface java.lang.Iterable<T extends java.lang.Comparable<T>>

Returns:

an iterator that returns all elements of this heap

sortedIterator

public java.util.Iterator<T> sortedIterator()

Specified by:

sortedIterator in interface ImmutableHeap<T extends java.lang.Comparable<T>>

Returns:

an iterator that returns all elements of this heap in increasing order

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object