com.partnersoft.data
Interface SortingGopher

public interface SortingGopher

Generic adapter to present array-like structures to instances of SortingAlgorithm for sorting.

These adapters allow us to use generic array-sorting algorithms on a variety of structures, including disk-based ones, without substantial additional memory overhead. It does assume a data model that allows fast random-access reads and reasonable random-access swaps, so it is inappropriate for linked lists, variable-length record data files, etc. It is extremely effective at sorting fixed-length records and indexes, and makes the comparison an implementation detail that can be optimized internally (e.g. byte comparisons rather instantiating Strings).

It uses an abstract memory register to store values for comparison later. This means that a SortingGopher must store some kind of state to do the comparison, in addition to any state required to access the underlying data. Since most algorithms collect and repeatedly compare against a minimum or maximum key value, this allows a single read to store the key value, instead of re-reading the item each time a comparison is called for.

Copyright 2003-2006 Partner Software, Inc.

Author:

Paul Reavis

Method Summary

int	compare(int index) Compares the key of the item at the given index with the current remembered key.
void	remember(int index) Remembers the key value at the given index for future comparisons.
int	size() Returns the number of items in the array.
void	swap(int a, int b) Swaps the order of the items at the two given index positions.

Method Detail

remember

void remember(int index)

Remembers the key value at the given index for future comparisons.

Parameters:

index - index of key value to remember

compare

int compare(int index)

Compares the key of the item at the given index with the current remembered key.

Parameters:

index - index of key value to compare to remembered key value

Returns:

value < 0 if less than, 0 if equal, > 0 if greater than.

size

int size()

Returns the number of items in the array.

Returns:

number of items - top index is therefore (size-1)

swap

void swap(int a,
          int b)

Swaps the order of the items at the two given index positions.

Parameters:

a - first index to swap

b - second index to swap