org.erights.e.elib.tables
Class FlexMapImpl

java.lang.Object
  |
  +--org.erights.e.elib.tables.EMap
        |
        +--org.erights.e.elib.tables.FlexMap
              |
              +--org.erights.e.elib.tables.FlexMapImpl

All Implemented Interfaces:

EPrintable, Iteratable, Marker, PassByProxy, Persistent, Serializable

Direct Known Subclasses:

IntTable

class FlexMapImpl

extends FlexMap

An implementation of FlexMap by MarkM & Sidney, based on an earlier design by Dan.

Author:

Mark S. Miller

Field Summary

static int	DEFAULT_INIT_CAPACITY Similarly, the default initial capacity of java.util.Hashtable is 101.
static float	DEFAULT_LOAD_FACTOR This default load factor is calculated to preserve the same marginal space cost per hash map entry as java.util.Hashtable, given its default load factor of 0.75.
private static int	DEFAULT_THRESH For either map, multiplying the two defaults gives the same default threshold -- how many a default map can hold without growing: 75.
(package private) KeyColumn	myKeys
(package private) float	myLoadFactor The load factor for the map.
(package private) ShareCount	myShareCount
(package private) int	mySizeThreshold The current size threshold for the map, that is, the number of elements to hold before growing.
(package private) Column	myValues
(package private) static long	serialVersionUID

Fields inherited from class org.erights.e.elib.tables.EMap

Fields inherited from interface org.erights.e.elib.serial.PassByProxy

HONORARY, HONORED_NAMES

Fields inherited from interface org.erights.e.elib.serial.Persistent

HONORARY, HONORED_NAMES

Constructor Summary

	FlexMapImpl() Reasonable defaults
	FlexMapImpl(Class keyType, Class valueType) Reasonable defaults
	FlexMapImpl(Class keyType, Class valueType, int initCapacity)
	FlexMapImpl(Class keyType, Class valueType, int initCapacity, float loadFactor)
	FlexMapImpl(int initialCapacity) Reasonable defaults
	FlexMapImpl(int initialCapacity, float loadFactor) Reasonable defaults
private	FlexMapImpl(KeyColumn keys, Column values) Reasonable defaults
(package private)	FlexMapImpl(KeyColumn keys, Column values, float loadFactor)
(package private)	FlexMapImpl(KeyColumn keys, Column values, float loadFactor, ShareCount shareCount)

Method Summary

FlexMap	diverge(Class kType, Class vType) Unlike java.util.Hashtable, this part efficiently makes a lazy copy by copy-on-write sharing.
Object	get(Object key) Returns the value to which the key is mapped in this map.
Object	get(Object key, Object instead) Returns the value to which the key is mapped in this map.
Object	getKeys(Class type) Enabled: Returns a divergent array-of-type of all the keys in order.
Object	getValues(Class type) Enabled: Returns a divergent array-of-type of all the values in order.
void	iterate(AssocFunc func) Enabled: Call 'func' with each key-value pair in the table, in order.
Class	keyType() All keys in this map must be of this type
boolean	maps(Object key) Returns true if the specified object is a key in the collection, as defined by the equality function of the collection.
void	put(Object key, Object value, boolean strict) Enabled: Causes 'key' to map to 'value'.
(package private) void	rehash()
void	removeAll() Rather than doing a write-fault (which would make a private copy to be immediately dropped) this decrements the sharing count and re-initializes.
void	removeKey(Object key, boolean strict) Enabled: Removes the given key (or its equivalent, according to the equal function) from the collection.
int	size() The number of keys in the collection
Class	valueType() All values in this map must be of this type
(package private) void	writeFault()
private Object	writeReplace() Given that cmap is a snapshot() of this map, writeReplace() unserializes to a promise for cmap.diverge(keyType, valueType).

Methods inherited from class org.erights.e.elib.tables.FlexMap

__optUncall, __printOn, clone, domain, fromColumns, fromPairs, fromTypes, fromTypes, interning, interning, make, make, put, putAll, putAll, readOnly, removeKey, removeKeys, removeKeys, snapshot

Methods inherited from class org.erights.e.elib.tables.EMap

and, butNot, contains, diverge, extract, getKeys, getPair, getPair, getValues, intersects, optExtract, or, or, printOn, sortKeys, sortKeys, sortValues, sortValues, toString, with, without

Methods inherited from class java.lang.Object

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

Field Detail

serialVersionUID

static final long serialVersionUID

DEFAULT_LOAD_FACTOR

public static final float DEFAULT_LOAD_FACTOR

This default load factor is calculated to preserve the same marginal space cost per hash map entry as java.util.Hashtable, given its default load factor of 0.75. For a map of 100 entries, assuming only one word of hidden boxing overhead, java.util.Hastable uses: sizeof(HashtableEntry) == 5*4 == 20 100 * 20 == 2000 (capacity = 100 / 0.75 == 133) capacity * 4 = 533 bytes per entry == 25.33 FlexMapImpl, by contrast, uses 13 bytes per unit capacity (pos) irrespective of how many are occupied. 13/25.33 == 0.52 (approx)

DEFAULT_INIT_CAPACITY

public static final int DEFAULT_INIT_CAPACITY

Similarly, the default initial capacity of java.util.Hashtable is 101. 101 * 0.75 / 0.52 == 146 (approx). But we're using 10 instead.

DEFAULT_THRESH

private static final int DEFAULT_THRESH

For either map, multiplying the two defaults gives the same default threshold -- how many a default map can hold without growing: 75. But we're using 5 instead.

myKeys

KeyColumn myKeys

myValues

Column myValues

mySizeThreshold

int mySizeThreshold

The current size threshold for the map, that is, the number of elements to hold before growing. It is calculated as capacity * myLoadFactor.

myLoadFactor

float myLoadFactor

The load factor for the map.

myShareCount

ShareCount myShareCount

Constructor Detail

FlexMapImpl

public FlexMapImpl()

Reasonable defaults

FlexMapImpl

public FlexMapImpl(int initialCapacity)

Reasonable defaults

FlexMapImpl

public FlexMapImpl(int initialCapacity,
                   float loadFactor)

Reasonable defaults

FlexMapImpl

public FlexMapImpl(Class keyType,
                   Class valueType)

Reasonable defaults

FlexMapImpl

private FlexMapImpl(KeyColumn keys,
                    Column values)

Reasonable defaults

FlexMapImpl

FlexMapImpl(KeyColumn keys,
            Column values,
            float loadFactor)

FlexMapImpl

FlexMapImpl(KeyColumn keys,
            Column values,
            float loadFactor,
            ShareCount shareCount)

FlexMapImpl

public FlexMapImpl(Class keyType,
                   Class valueType,
                   int initCapacity)

FlexMapImpl

public FlexMapImpl(Class keyType,
                   Class valueType,
                   int initCapacity,
                   float loadFactor)

Method Detail

writeReplace

private Object writeReplace()
                     throws ObjectStreamException

Given that cmap is a snapshot() of this map, writeReplace() unserializes to a promise for cmap.diverge(keyType, valueType).

ObjectStreamException

get

public Object get(Object key)
           throws IndexOutOfBoundsException

Returns the value to which the key is mapped in this map. Unlike java.util.Dictionary, a map doesn't indicate a lookup failure by returning null, since null is a valid value. map throws an exception instead.

Overrides:

get in class EMap

Parameters:

key - nullOk;

Returns:

nullOk;

Throws:

IndexOutOfBoundsException - if key doesn't map to anything.

See Also:

org.erights.e.elib.ref.Ref#isSettled

get

public Object get(Object key,
                  Object instead)

Returns the value to which the key is mapped in this map. If key is not mapped, return 'instead' instead.

Specified by:

get in class EMap

Parameters:

key - nullOk;

instead - nullOk;

Returns:

nullOk;

See Also:

org.erights.e.elib.ref.Ref#isSettled

size

public int size()

The number of keys in the collection

Specified by:

size in class EMap

iterate

public void iterate(AssocFunc func)

Description copied from class: EMap

Enabled: Call 'func' with each key-value pair in the table, in order.

Specified by:

iterate in interface Iteratable

Overrides:

iterate in class EMap

maps

public boolean maps(Object key)

Returns true if the specified object is a key in the collection, as defined by the equality function of the collection.

Overrides:

maps in class EMap

Parameters:

key - the object to look for

Returns:

true if the key is in the collection

getKeys

public Object getKeys(Class type)

Description copied from class: EMap

Enabled: Returns a divergent array-of-type of all the keys in order.

XXX Should 'type' be a ValueGuard rather than a Class?

Specified by:

getKeys in class EMap

getValues

public Object getValues(Class type)

Description copied from class: EMap

Enabled: Returns a divergent array-of-type of all the values in order.

XXX Should 'type' be a ValueGuard rather than a Class?

Specified by:

getValues in class EMap

put

public void put(Object key,
                Object value,
                boolean strict)

Description copied from class: FlexMap

Enabled: Causes 'key' to map to 'value'. If 'strict' is false (the default), this will overwrite a previous value if necessary. If 'strict' is true, this only succeeds if there is not already an association for 'key' in the map. If 'strict' is true and there is an already an association, even to the same value, this throws an Exception instead (XXX currently an IllegalArgumentException) and leaves the map unmodified.

Unlike Dictionary, this doesn't return the old value. If you want it, use 'get' first.

If the key is overwritten, then the key order is unchanged. If the key is novel, it's added to the end of the order.

Specified by:

put in class FlexMap

See Also:

org.erights.e.elib.ref.Ref#isSettled

rehash

void rehash()

removeKey

public void removeKey(Object key,
                      boolean strict)

Description copied from class: FlexMap

Enabled: Removes the given key (or its equivalent, according to the equal function) from the collection. If 'strict' is false (the default), this does nothing if 'key' is not currently a key in the collection. If 'strict' is true and 'key' isn't already there to be removed, this throws an Exception (XXX currently an IllegalArgumentException).

Unlike Dictionary, this does not return the old value. If you want this for a FlexMap, use 'get' first.

If 'key' wasn't in the table, the table (including its order) is unmodified. Otherwise, the last key in the table is moved in the ordering to take the place of the removed 'key'.

Specified by:

removeKey in class FlexMap

Parameters:

key - the key to remove

removeAll

public void removeAll()

Rather than doing a write-fault (which would make a private copy to be immediately dropped) this decrements the sharing count and re-initializes.

Specified by:

removeAll in class FlexMap

diverge

public FlexMap diverge(Class kType,
                       Class vType)

Unlike java.util.Hashtable, this part efficiently makes a lazy copy by copy-on-write sharing. Modify operations on a shared map then cause the delayed copy to happen.

Overrides:

diverge in class EMap

keyType

public Class keyType()

All keys in this map must be of this type

Specified by:

keyType in class EMap

valueType

public Class valueType()

All values in this map must be of this type

Specified by:

valueType in class EMap

writeFault

void writeFault()