xxl.cursors
Class ReplacementSelection

java.lang.Object
  |
  +--xxl.cursors.ReplacementSelection

public class ReplacementSelection

extends java.lang.Object

implements Cursor

Replacement Selection takes an Iterator as its input and creates sorted runs as its output. This technique is described in "Donald Knuth.: Sorting and Searching. Addison-Wesley 1970." Replacement-selection is especially useful for external sorting. Recall, that an external merge-sort is performed by first producing n sorted input-runs. These runs are then recursively merged to a single output-run. The runs produced by ReplacementSelection tend to be twice as big as the available memory or even bigger.

Field Summary

protected java.lang.Object[]	array
protected java.util.Comparator	comparator
protected Cursor	cursor
protected Heap	heap
protected int	n
protected int	size

Constructor Summary

ReplacementSelection(Cursor cursor, int size, java.util.Comparator comparator)
Creates a new instance of ReplacementSelection.

ReplacementSelection(java.util.Iterator iterator, int size)
Creates a new instance of ReplacementSelection.

ReplacementSelection(java.util.Iterator iterator, int size, java.util.Comparator comparator)
Creates a new instance of ReplacementSelection.

ReplacementSelection(PeekIterator peekIterator, int size, java.util.Comparator comparator)
Creates a new instance of ReplacementSelection.

Method Summary

protected void	check() Checks whether there are more elements to process.
void	close() Closes the Cursor.
boolean	hasNext() Returns true if the iteration has more elements.
protected void	init() Initializes the ReplacementSelection-Object.
static void	main(java.lang.String[] args)
java.lang.Object	next() Returns the next element in the iteration.
java.lang.Object	peek() Shows the next element in the iteration without removing it.
void	remove() Removes from the underlying collection the last element returned by the iterator (unsupported operation).
void	reset() Resets the Cursor to its initial state.
boolean	supportsPeek() Returns true if the peek operation is supported by this PeekIterator.
void	update(java.lang.Object object) Replaces the object that was returned by the last call to next() or peek().

Methods inherited from class java.lang.Object

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

Field Detail

array

protected java.lang.Object[] array

n

protected int n

size

protected int size

cursor

protected Cursor cursor

comparator

protected java.util.Comparator comparator

heap

protected Heap heap

Constructor Detail

ReplacementSelection

public ReplacementSelection(Cursor cursor,
                            int size,
                            java.util.Comparator comparator)

Creates a new instance of ReplacementSelection.

Parameters:

cursor - the input-Cursor

size - the number of elements that can be kept in memory

comparator - the Comparator used to compare elements

ReplacementSelection

public ReplacementSelection(java.util.Iterator iterator,
                            int size)

Creates a new instance of ReplacementSelection.

Parameters:

iterator - the input-Iterator

size - the number of elements that can be kept in memory

ReplacementSelection

public ReplacementSelection(java.util.Iterator iterator,
                            int size,
                            java.util.Comparator comparator)

Creates a new instance of ReplacementSelection.

Parameters:

iterator - the input-Iterator

size - the number of elements that can be kept in memory

comparator - the Comparator used to compare elements

ReplacementSelection

public ReplacementSelection(PeekIterator peekIterator,
                            int size,
                            java.util.Comparator comparator)

Creates a new instance of ReplacementSelection.

Parameters:

peekIterator - the input-PeekIterator

size - the number of elements that can be kept in memory

comparator - the Comparator used to compare elements

Method Detail

init

protected void init()

Initializes the ReplacementSelection-Object.

check

protected void check()
              throws java.util.NoSuchElementException

Checks whether there are more elements to process. If so and the heap is empty, it creates a new heap using the elements that are reside in memory.

close

public void close()

Closes the Cursor. Signals the cursor to cleanup resources, close files, etc. After a call to close() calls to methods like next() or peek() are not guarantied to yield proper results.

Specified by:

close in interface Cursor

hasNext

public boolean hasNext()

Returns true if the iteration has more elements.

Specified by:

hasNext in interface Cursor

Returns:

true if the iterator has more elements.

next

public java.lang.Object next()
                      throws java.util.NoSuchElementException

Returns the next element in the iteration.

Specified by:

next in interface Cursor

Returns:

the next element in the iteration.

Throws:

java.util.NoSuchElementException - iteration has no more elements.

peek

public java.lang.Object peek()
                      throws java.util.NoSuchElementException

Shows the next element in the iteration without removing it.

Specified by:

peek in interface Cursor

Returns:

the next element in the iteration.

Throws:

java.util.NoSuchElementException - iteration has no more elements.

java.lang.UnsupportedOperationException - if the peek operation is not supported by this PeekIterator.

remove

public void remove()
            throws java.lang.UnsupportedOperationException

Removes from the underlying collection the last element returned by the iterator (unsupported operation).

Specified by:

remove in interface Cursor

Throws:

java.lang.IllegalStateException - if the next method has not yet been called, or the remove method has already been called after the last call to the next method.

java.lang.UnsupportedOperationException - if the remove operation is not supported by this PeekIterator.

reset

public void reset()
           throws java.lang.UnsupportedOperationException

Resets the Cursor to its initial state.

Specified by:

reset in interface Cursor

supportsPeek

public boolean supportsPeek()

Returns true if the peek operation is supported by this PeekIterator.

Specified by:

supportsPeek in interface Cursor

Returns:

true if the peek operation is supported by this PeekIterator.

update

public void update(java.lang.Object object)
            throws java.lang.UnsupportedOperationException

Replaces the object that was returned by the last call to next() or peek(). This operation must not be called after a call to hasNext(). It should foow a call to next() or peek().

Specified by:

update in interface Cursor

Parameters:

object - the object that replaces the object returned by the last call to next() or peek()

main

public static void main(java.lang.String[] args)