org.erights.e.elib.tables
Class EqualityKeyColumn

java.lang.Object
  |
  +--org.erights.e.elib.tables.Column
        |
        +--org.erights.e.elib.tables.KeyColumn
              |
              +--org.erights.e.elib.tables.EqualityKeyColumn

All Implemented Interfaces:

Cloneable

class EqualityKeyColumn

extends KeyColumn

Author:

Mark S. Miller

Field Summary

(package private) static int	KEY_DELETED A value in myPos2Rank indicating that this position used to be occupied since the last rehash, but no longer is.
(package private) static int	KEY_UNUSED A value in myPos2Rank indicating that this position has never been occupied since the last rehash.
private int[]	myHashes The array of computed hashes for each key in the set.
(package private) Object[]	myKeys The sparse array of keys by position.
private int	myMaxProbes The maximum number of probes made so far.
(package private) int	myNumDeleted The number of keys currently marked deleted in the column.
(package private) int	myNumTaken The number of key currently in the column.
(package private) int[]	myPos2Rank A sparse array parallel to myKeys.
(package private) int[]	myRank2Pos A dense array, listing positions in their enumeration order.
static int	POSITIVE_MASK Used to ensure ints are positive

Constructor Summary

	EqualityKeyColumn() Reasonable defaults
	EqualityKeyColumn(Class memberType) Reasonable defaults
	EqualityKeyColumn(Class memberType, int capacity)
	EqualityKeyColumn(int capacity) Reasonable defaults
private	EqualityKeyColumn(Object[] keys, int[] pos2Rank, int[] rank2Pos, int numTaken, int numDeleted, int maxProbes, int[] hashes)

Method Summary

(package private) int	capacity()
protected Object	clone() Argument defaults to memberType()
protected Column	diverge(Class membType) A shallow copy of the column.
(package private) int	findPosOf(Object key) Returns the pos at which key resides, or -1 if the key is absent from the map.
(package private) Object	get(int pos)
(package private) boolean	isPosTaken(int pos) Given a pos, say whether this pos contains a valid key.
(package private) static KeyColumn	make(Class memberType, int capacity) Makes a key column that's equivalent to a SamenessKeyColumn(memberType, capacity), but may select a more efficient implementation based on how instances of memberType compare for sameness.
(package private) Class	memberType() All the members of the column must conform to this type
(package private) Column	newVacant(int capacity) Makes a new column just like this one, except of the specified size and without any members.
(package private) int	numTaken() Get the number of keys in the column
(package private) int	occupy(int pos, Object key)
private int	occupy(int pos, Object key, int hash)
(package private) void	put(int pos, Object value)
(package private) int[]	rank2Pos() Caller should only read, and only between 0..!numTaken()
(package private) static int	skip(int hash, int len)
(package private) int	store(Object key) Put the given key into the map, and return its pos.
(package private) void	vacate(int pos) cause pos not to contain a valid key
static Column	values(Class memberType, int capacity) Make a value-column that can only hold values that conform to 'memberType' and has 'capacity' positions.
static Column	values(int capacity) memberType defaults to Object

Methods inherited from class java.lang.Object

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

Field Detail

myMaxProbes

private final int myMaxProbes

The maximum number of probes made so far.

myHashes

private final int[] myHashes

The array of computed hashes for each key in the set.

POSITIVE_MASK

public static final int POSITIVE_MASK

Used to ensure ints are positive

myKeys

final Object[] myKeys

The sparse array of keys by position. null is a valid entry. The value of an entry is only valid if indicated by the corresponding myPos2Rank entry.

myPos2Rank

final int[] myPos2Rank

A sparse array parallel to myKeys. Each element contains either KEY_UNUSED, KEY_DELETED, or an index into myRank2Pos indicating where the association at this position fits into the ordering.

KEY_UNUSED

static final int KEY_UNUSED

A value in myPos2Rank indicating that this position has never been occupied since the last rehash. Note that KEY_UNUSED is negative, so it can't conflict with an array index.

KEY_DELETED

static final int KEY_DELETED

A value in myPos2Rank indicating that this position used to be occupied since the last rehash, but no longer is. Note that KEY_DELETED is negative, so it can't conflict with an array index.

myRank2Pos

final int[] myRank2Pos

A dense array, listing positions in their enumeration order. The allocated size of myRank2Pos is actually the same as the sparse arrays, but it's dense in 0..!myNumTaken, and unused after that.

myNumTaken

int myNumTaken

The number of key currently in the column.

myNumDeleted

int myNumDeleted

The number of keys currently marked deleted in the column.

Constructor Detail

EqualityKeyColumn

public EqualityKeyColumn()

Reasonable defaults

EqualityKeyColumn

private EqualityKeyColumn(Object[] keys,
                          int[] pos2Rank,
                          int[] rank2Pos,
                          int numTaken,
                          int numDeleted,
                          int maxProbes,
                          int[] hashes)

EqualityKeyColumn

public EqualityKeyColumn(int capacity)

Reasonable defaults

EqualityKeyColumn

public EqualityKeyColumn(Class memberType)

Reasonable defaults

EqualityKeyColumn

public EqualityKeyColumn(Class memberType,
                         int capacity)

Parameters:

memberType -

capacity -

Method Detail

diverge

protected Column diverge(Class membType)

Description copied from class: Column

A shallow copy of the column. The members are shared, not copied. The new Column is restricted to only holding members of type membType.

Specified by:

diverge in class Column

newVacant

Column newVacant(int capacity)

Description copied from class: Column

Makes a new column just like this one, except of the specified size and without any members.

Specified by:

newVacant in class Column

findPosOf

int findPosOf(Object key)

Description copied from class: KeyColumn

Returns the pos at which key resides, or -1 if the key is absent from the map.

Specified by:

findPosOf in class KeyColumn

store

int store(Object key)

Description copied from class: KeyColumn

Put the given key into the map, and return its pos. If the key is equivalent (according to the concrete column's equality function) to a key already in the map, that pos is returned. If the key is novel but the map is too small to add it, a -1 is returned.

If the key already exists, no ordering information is affected. If a novel key is inserted, it's position gets the next rank.

Specified by:

store in class KeyColumn

Parameters:

key - the key to place in the map

Returns:

the pos at which the key now resides in the map, or -1 if we need more room.

occupy

private int occupy(int pos,
                   Object key,
                   int hash)

vacate

void vacate(int pos)

Description copied from class: KeyColumn

cause pos not to contain a valid key

Overrides:

vacate in class KeyColumn

make

static KeyColumn make(Class memberType,
                      int capacity)

Makes a key column that's equivalent to a SamenessKeyColumn(memberType, capacity), but may select a more efficient implementation based on how instances of memberType compare for sameness.

get

Object get(int pos)

Specified by:

get in class Column

isPosTaken

boolean isPosTaken(int pos)

Given a pos, say whether this pos contains a valid key.

memberType

Class memberType()

Description copied from class: Column

All the members of the column must conform to this type

Specified by:

memberType in class Column

capacity

int capacity()

Specified by:

capacity in class Column

numTaken

int numTaken()

Get the number of keys in the column

rank2Pos

int[] rank2Pos()

Caller should only read, and only between 0..!numTaken()

put

void put(int pos,
         Object value)

Specified by:

put in class Column

skip

static int skip(int hash,
                int len)

occupy

int occupy(int pos,
           Object key)

clone

protected Object clone()

Argument defaults to memberType()

Overrides:

clone in class Object

Returns:

a clone of this instance.

See Also:

java.lang.Cloneable

values

public static Column values(int capacity)

memberType defaults to Object

values

public static Column values(Class memberType,
                            int capacity)

Make a value-column that can only hold values that conform to 'memberType' and has 'capacity' positions. If the memberType is a scalar type, the column will represent these values unboxed.