net.aerith.misao.util
Class SortableArray

java.lang.Object
  |
  +--net.aerith.misao.util.SortableArray

Direct Known Subclasses:

Array, StringArray

public abstract class SortableArray

extends java.lang.Object

The SortableArray represents a virtual array of data values with a function to sort data.

Field Summary

protected static int	COMPARE_EQUAL The number which represents the comparison result is the first data and the second data are equal.
protected static int	COMPARE_LARGER The number which represents the comparison result is the first data is larger than the second data.
protected static int	COMPARE_SMALLER The number which represents the comparison result is the first data is smaller than the second data.
private static int	SORT_ASCENDANT The sorting direction number used in quick_sort indicating the ascending order.
private static int	SORT_DESCENDANT The sorting direction number used in quick_sort indicating the descending order.
protected ArrayIndex	sort_index The index of sorting result.

Constructor Summary

SortableArray()

Method Summary

protected abstract int	compare(int index1, int index2) Compares the two data represented by the specified index and returns which is smaller.
abstract int	getArraySize() Gets the size of this array.
private void	quick_sort(int first, int last, int direction) Sorts part of the data between the specified first and last location in order of the specified direction.
protected abstract void	sort() Sorts this array itself based on the sorted index.
ArrayIndex	sortAscendant() Sorts data in ascendant order.
ArrayIndex	sortDescendant() Sorts data in descendant order.

Methods inherited from class java.lang.Object

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

Field Detail

sort_index

protected ArrayIndex sort_index

The index of sorting result. It is used in the recurrsive quick_sort method.

SORT_ASCENDANT

private static final int SORT_ASCENDANT

The sorting direction number used in quick_sort indicating the ascending order.

SORT_DESCENDANT

private static final int SORT_DESCENDANT

The sorting direction number used in quick_sort indicating the descending order.

COMPARE_EQUAL

protected static final int COMPARE_EQUAL

The number which represents the comparison result is the first data and the second data are equal.

COMPARE_SMALLER

protected static final int COMPARE_SMALLER

The number which represents the comparison result is the first data is smaller than the second data.

COMPARE_LARGER

protected static final int COMPARE_LARGER

The number which represents the comparison result is the first data is larger than the second data.

Constructor Detail

SortableArray

public SortableArray()

Method Detail

getArraySize

public abstract int getArraySize()

Gets the size of this array.

Returns:

the size of this array.

compare

protected abstract int compare(int index1,
                               int index2)

Compares the two data represented by the specified index and returns which is smaller. If the first data is smaller, it returns COMPARE_SMALLER. If the first data is larger, it returns COMPARE_LARGER. If both the data are equal, it returns COMPARE_EQUAL.

Parameters:

index1 - the index to represent the first data to compare.

index2 - the index to represent the second data to compare.

Returns:

the number to represent the comparison result.

sort

protected abstract void sort()

Sorts this array itself based on the sorted index. It is invoked in the sorting functions. It must be overrided in the subclasses.

sortAscendant

public ArrayIndex sortAscendant()

Sorts data in ascendant order. It returns a table indicating the original location. For example,

     ArrayIndex index = array.sortAscendant();
 

then the k-th value in the sorted buffer was originally at the index.get(k)-th location.

Returns:

the table indicating the original location.

sortDescendant

public ArrayIndex sortDescendant()

Sorts data in descendant order. It returns a table indicating the original location. For example,

     ArrayIndex index = array.sortDescendant();
 

then the k-th value in the sorted buffer was originally at the index.get(k)-th location.

Returns:

the table indicating the original location.

quick_sort

private void quick_sort(int first,
                        int last,
                        int direction)

Sorts part of the data between the specified first and last location in order of the specified direction. It is invoked recurrsively. The data in the buffer is not really changed by this process. Only sort_index, indicating the location after sorted, is changed.

Parameters:

first - the first index of part to sort.

last - the last index of part to sort.

direction - the sorting direction.