xxl.cursors
Class Divider

java.lang.Object
  |
  +--xxl.cursors.AbstractCursor
        |
        +--xxl.cursors.Divider

public class Divider

extends AbstractCursor

TODO: Verbesserung, dass Tupel markiert werden, die nach dem Teilen groesser oder gleich sind als vorher eventl. Rekursionslevel merken, so daß hierueber Abbruchbedingung spezifiziert werden kann eventl. parametrisierbar ob Replikation oder nicht (Optimierung) The Divider distributes input data to partitions using a given function, i.e. this Cursor provides the Divide-part of Divide&Conquer. The input Cursor(s) to the Divider is/are divided into partitions. The resulting partitions are inserted into a Queue (tupleQueue). This subpartitions are then divided recursively until the tupleAssessment-Function returns true. This is very useful, e.g. if you want to split an input in pieces of a certain size. Depending on the tupleQueue-implementation different "tree"-traversal strategies can be implemented: if you use a StackQueue the Divider will perform a depth-first-traversal. This means, that it is likely to find a partition that passes the tupleAssessment-FUNCTION in logarithmic time. Only the first divison of the data is "blocking". This is extremely useful for pipelined processing. In contrast, if a FIFO-Queue is used, the divider will perform a level-order traversal.

Inner Class Summary

static class	Divider.DividerFunction
protected class	Divider.DividerMap
static class	Divider.IntegerDividerFunction

Field Summary

static Function	DIVIDE_ONCE The Function DIVIDE_ONCE returns Boolean.TRUE.
protected Divider.DividerMap	dividerMap
protected Function	newDividerFunction
static Function	SINGLE_PARTITION The Function SINGLE_PARTITION returns Boolean.FALSE as long as input[0] contains more than one element.
protected Function	tupleAssessment
protected Queue	tupleQueue

Fields inherited from class xxl.cursors.AbstractCursor

hasNext, iterator, next

Constructor Summary

Divider(Cursor[] input, Function newDividerFunction, Function newQueue, Function tupleAssessment)

Divider(Cursor[] input, Function newDividerFunction, Function newQueue, Function tupleAssessment, Queue tupleQueue, java.util.Map map)
Creates a new Divider.

Divider(Cursor input, Function newDividerFunction, Function newQueue, Function tupleAssessment)

Divider(Cursor input, Function newDividerFunction, Function newQueue, Function tupleAssessment, Queue tupleQueue, java.util.Map map)

Method Summary

protected void	computeNext()
protected void	divide(java.util.Iterator[] input)
static void	main(java.lang.String[] args)

Methods inherited from class xxl.cursors.AbstractCursor

close, hasNext, next, peek, remove, reset, setNext, setNextIterator, supportsPeek, update

Methods inherited from class java.lang.Object

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

Field Detail

DIVIDE_ONCE

public static final Function DIVIDE_ONCE

The Function DIVIDE_ONCE returns Boolean.TRUE. i.e. the input data is divided exactly once.

SINGLE_PARTITION

public static final Function SINGLE_PARTITION

The Function SINGLE_PARTITION returns Boolean.FALSE as long as input[0] contains more than one element. This means, the input is divided until each data element of input[0] builds a single partition.

newDividerFunction

protected Function newDividerFunction

tupleAssessment

protected Function tupleAssessment

tupleQueue

protected Queue tupleQueue

dividerMap

protected Divider.DividerMap dividerMap

Constructor Detail

Divider

public Divider(Cursor[] input,
               Function newDividerFunction,
               Function newQueue,
               Function tupleAssessment,
               Queue tupleQueue,
               java.util.Map map)

Creates a new Divider. The Divider is an Iterator of Queues[]. The Divider divides the input into partitions recursively until the tupleAssessment-Function returns Boolean.TRUE.

Divider

public Divider(Cursor input,
               Function newDividerFunction,
               Function newQueue,
               Function tupleAssessment,
               Queue tupleQueue,
               java.util.Map map)

Divider

public Divider(Cursor[] input,
               Function newDividerFunction,
               Function newQueue,
               Function tupleAssessment)

Divider

public Divider(Cursor input,
               Function newDividerFunction,
               Function newQueue,
               Function tupleAssessment)

Method Detail

divide

protected void divide(java.util.Iterator[] input)

computeNext

protected void computeNext()

Overrides:

computeNext in class AbstractCursor

main

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