de.aitools.aq.algebra.vector
Class VectorSort

java.lang.Object
  de.aitools.aq.algebra.vector.VectorSort

public final class VectorSort
extends java.lang.Object

An optimized implementation of a priority queue of build in doubles. Instead of putting the doubles in the queue, it handles the indices of a vector.
So instead of a remove(double value) a remove(int valueIndex) is implemented.
The queue always sorts descending and there is no method to add new values to the queue (beside the constructor).
Creating the queue has a complexity of O(n log n). Removing (including polling) or changing a value has a complexity of O(log n). Note that a direct change in the vector (not using queue.change(int valueIndex, double newValue)) will most likely lead to a malfunctioned queue. Do not do this unlike you know what you are doing.

Version:

$Id: VectorSort.java,v 1.2 2011/02/22 14:15:36 dogu3912 Exp $

Author:

johannes.kiesel(/\t)uni-weimar.de

Field Summary

static int

NO_NODE

Constructor Summary

VectorSort(double[] nodeValues)
Create a new VectorSort with a new Vector created using given values.

VectorSort(Vector nodeValues, boolean copyVector)
Create a new VectorSort.

VectorSort(Vector nodeValues, boolean copyVector, int numNodes)
Create a new VectorSort.

Method Summary

void	changeValue(int valueIndex, double value) Change a value.
boolean	isYetUnremoved(int valueIndex)
int	peek()
int	poll() Returns the index of the biggest value left and removes it from the queue. This works exactly like calling int index = queue.peek() and queue.remove(index).
void	remove(int valueIndex) Remove a node from the sorting.
static int[]	sortedIndices(Vector input) Return the indices of the input vector, sorted in descending order.
java.lang.String	toString()

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

NO_NODE

public static final int NO_NODE

See Also:

Constant Field Values

Constructor Detail

VectorSort

public VectorSort(double[] nodeValues)

Create a new VectorSort with a new Vector created using given values. Trailing zeros will be sorted as well. Note that this class uses some kind of index pointers to do the sorting. This means only an intern array of the value indexes will be sorted and nodeValues will be left untouched (if the method change is not invoked).

Parameters:

nodeValues - The values to sort

VectorSort

public VectorSort(Vector nodeValues,
                  boolean copyVector)

Create a new VectorSort. The coordinates of the vector will be sorted (up to it's range). Note that this class uses some kind of index pointers to do the sorting. This means only an intern array of the value indexes will be sorted and nodeValues will be left untouched (if the method change is not invoked).

Parameters:

nodeValues - The vector to sort

copyVector - If to copy the vector

VectorSort

public VectorSort(Vector nodeValues,
                  boolean copyVector,
                  int numNodes)

Create a new VectorSort. The coordinates of the vector will be sorted. Note that this class uses some kind of index pointers to do the sorting. This means only an intern array of the value indexes will be sorted and nodeValues will be left untouched (if the method change is not invoked).

Parameters:

nodeValues - The vector to sort

copyVector - If to copy the vector

numNodes - The number of coordinates to be sorted

Method Detail

poll

public int poll()

Returns the index of the biggest value left and removes it from the queue.
This works exactly like calling int index = queue.peek() and queue.remove(index).

Returns:

The index of the biggest value that was not yet removed from this queue

peek

public int peek()

Returns:

The index of the biggest value that was not yet removed from this queue

isYetUnremoved

public boolean isYetUnremoved(int valueIndex)

Parameters:

valueIndex -

Returns:

True if the value was not yet removed (using remove(valueIndex)

remove

public void remove(int valueIndex)

Remove a node from the sorting. This can not be undone.

Parameters:

valueIndex - The index of the value in double array that should be removed

changeValue

public void changeValue(int valueIndex,
                        double value)

Change a value. This is the only method that can alter the nodeValues passed in the constructor.

Parameters:

valueIndex - The index of the value in the double array to change

value - New value

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

sortedIndices

public static int[] sortedIndices(Vector input)

Return the indices of the input vector, sorted in descending order.

Parameters:

input - The vector which indices to sort

Returns:

Sorted indices