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.



comments?