com.google.gwt.dev.util.editdistance

Class CharIndex

java.lang.Object

com.google.gwt.dev.util.editdistance.CharIndex

Direct Known Subclasses:

CharIndex.FullHash, CharIndex.Masked, CharIndex.Straight

public abstract class CharIndex
extends Object

A performance-oriented character-indexed map. Provides a mapping from characters in a limited alphabet (defined by a CharSequence) to integer values (for array indexing). Emphasis is on performance (e.g., compared to using a generic HashMap), in terms of speed of (post-construction) lookup and space required. Maps are constructed using a static getInstance method that chooses an efficient implementation for a given string. The map interface consists of: a size method for determining the maximum range of indices used; a lookup method for translating a character to its index; and, a nullElement method that returns the index that is not returned by lookup for any characer actually in the map. The target application is the mapping of natural-language strings. Most strings include characters from a single language, and thus fall into a small slice of the Unicode space. In particular, many strings fall into just the Latin series.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	CharIndex.FullHash An index based on a garden-variety hash map.
static class	CharIndex.Masked An index based on a simple mask: index(c) = (c & MASK).
static class	CharIndex.Straight An index based on the identity mapping: index(c) = c.

Constructor Summary

Constructors

Constructor and Description
CharIndex()

Method Summary

Methods

Modifier and Type	Method and Description
static CharIndex	getInstance(CharSequence s) Generates an index for a given alphabet, defined by a character sequence.
abstract int	lookup(char c) Returns the index (mapping result) for a given character.
abstract int[]	map(CharSequence s, int[] mapped) Performs lookups on an entire sequence of characters.
abstract int	nullElement() Returns an index that is not used for any character in the alphabet.
abstract int	size() Returns the maximum index result that can be returned by the lookup function (including the nullElement result if applicable).

Methods inherited from class java.lang.Object

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

Constructor Detail

CharIndex

public CharIndex()

Method Detail

getInstance

public static CharIndex getInstance(CharSequence s)

Generates an index for a given alphabet, defined by a character sequence. An appropriate implementation is chosen for the alphabet. The character sequence is allowed to contain multiple instances of the same character.

Parameters:

s - the alphabet to be indexed

Returns:

an index appropriate to this alphabet

lookup

public abstract int lookup(char c)

Returns the index (mapping result) for a given character. If the character is present in the alphabet, then a unique index is returned; other characters may be mapped to unique values, *or* may be mapped to a shared nullElement value.

Parameters:

c - character for which an index is sought

Returns:

an integer index for the character

map

public abstract int[] map(CharSequence s,
        int[] mapped)

Performs lookups on an entire sequence of characters. This allows an entire string to be mapped with fewer method invocations, and possibly with some added internal efficiencies.

Parameters:

s - character sequence to be indexed

mapped - array for storing results

Returns:

an array of indices for the character sequence, either the mapped parameter or a larger newly-allocated array if required

nullElement

public abstract int nullElement()

Returns an index that is not used for any character in the alphabet. This index *may* be returned for characters not in the alphabet.

Returns:

an index not used for a valid character

size

public abstract int size()

Returns the maximum index result that can be returned by the lookup function (including the nullElement result if applicable). No negative values are ever returned from lookup.

Returns:

maximum index returned from any lookup