Package org.openstreetmap.josm.data.osm

Class Storage<T>

java.lang.Object

java.util.AbstractCollection<E>

java.util.AbstractSet<T>

org.openstreetmap.josm.data.osm.Storage<T>

Type Parameters:

T - type of stored objects

All Implemented Interfaces:

java.lang.Iterable<T>, java.util.Collection<T>, java.util.Set<T>

public class Storage<T>
extends java.util.AbstractSet<T>

A Set-like class that allows looking up equivalent preexisting instance. It is useful wherever one would use self-mapping construct like Map<T,T>.put(t,t), that is, for caches, uniqueness filters or similar.

The semantics of equivalency can be external to the object, using the Hash interface. The set also supports querying for entries using different key type, in case you can provide a Hash implementation that can resolve the equality.

Examples

• A String cache:

   Storage<String> cache = new Storage(); // use default Hash
   for (String input : data) {
       String onlyOne = cache.putIfUnique(input);
       ....
   }
   

• Identity-based set:

   Storage<Object> identity = new Storage(new Hash<Object,Object> {
       public int getHashCode(Object o) {
           return System.identityHashCode(o);
       }
       public boolean equals(Object o1, Object o2) {
           return o1 == o2;
       }
    });
   

• An object with int ID and id-based lookup:

   class Thing { int id; }
   Storage<Thing> things = new Storage(new Hash<Thing,Thing>() {
       public int getHashCode(Thing t) {
           return t.id;
       }
       public boolean equals(Thing t1, Thing t2) {
           return t1 == t2;
       }
    });
   Map<Integer,Thing> fk = things.foreignKey(new Hash<Integer,Thing>() {
       public int getHashCode(Integer i) {
           return i.getIntValue();
       }
       public boolean equals(Integer k, Thing t) {
           return t.id == k.getIntvalue();
       }
   }
  
   things.put(new Thing(3));
   assert things.get(new Thing(3)) == fk.get(3);
   

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
private class	Storage.AbstractIter
private class	Storage.FMap<K>
private class	Storage.Iter
static class	Storage.PrimitiveIdHash	Hash for PrimitiveId.
private class	Storage.SafeReadonlyIter

Field Summary

Fields

Modifier and Type	Field	Description
private boolean	arrayCopyNecessary
private T[]	data
private static int	DEFAULT_CAPACITY
private Hash<? super T,? super T>	hash
private static double	LOAD_FACTOR
private int	mask
private int	modCount
private boolean	safeIterator
private int	size

Constructor Summary

Constructors

Constructor	Description
Storage()	Constructs a new Storage with default capacity (16).
Storage(boolean safeIterator)	Constructs a new Storage.
Storage(int capacity)	Constructs a new Storage with given capacity.
Storage(int capacity, boolean safeIterator)	Constructs a new Storage with given capacity.
Storage(Hash<? super T,? super T> ha)	Constructs a new Storage with given hash.
Storage(Hash<? super T,? super T> ha, boolean safeIterator)	Constructs a new Storage with given hash.
Storage(Hash<? super T,? super T> ha, int capacity)	Constructs a new Storage with given hash and capacity.
Storage(Hash<? super T,? super T> ha, int capacity, boolean safeIterator)	Constructs a new Storage with given hash and capacity.

Method Summary

Modifier and Type	Method	Description
boolean	add(T t)
void	clear()
boolean	contains(java.lang.Object o)
private void	copyArray()
static <O> Hash<O,O>	defaultHash()	A factory for default hash implementation.
private T	doRemove(int slot)
private void	ensureSpace()
boolean	equals(java.lang.Object obj)
private void	fillTheHole(int hole)
<K> java.util.Map<K,T>	foreignKey(Hash<K,? super T> h)
T	get(T t)
private <K> int	getBucket(Hash<K,? super T> ha, K key)	Finds a bucket for given key.
int	hashCode()
java.util.Iterator<T>	iterator()
T	put(T t)
T	putUnique(T t)
private static int	rehash(int h)	Additional mixing of hash
boolean	remove(java.lang.Object o)
T	removeElem(T t)
int	size()

Methods inherited from class java.util.AbstractSet

removeAll

Methods inherited from class java.util.AbstractCollection

addAll, containsAll, isEmpty, retainAll, toArray, toArray, toString

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Collection

parallelStream, removeIf, stream, toArray

Methods inherited from interface java.lang.Iterable

forEach

Methods inherited from interface java.util.Set

addAll, containsAll, isEmpty, retainAll, spliterator, toArray, toArray

Field Detail

hash

private final Hash<? super T,? super T> hash

data

private T[] data

mask

private int mask

size

private int size

modCount

private volatile int modCount

LOAD_FACTOR

private static final double LOAD_FACTOR

See Also:

Constant Field Values

DEFAULT_CAPACITY

private static final int DEFAULT_CAPACITY

See Also:

Constant Field Values

safeIterator

private final boolean safeIterator

arrayCopyNecessary

private boolean arrayCopyNecessary

Constructor Detail

Storage

public Storage()

Constructs a new Storage with default capacity (16).

Storage

public Storage(int capacity)

Constructs a new Storage with given capacity.

Parameters:

capacity - capacity

Storage

public Storage(Hash<? super T,? super T> ha)

Constructs a new Storage with given hash.

Parameters:

ha - hash

Storage

public Storage(boolean safeIterator)

Constructs a new Storage.

Parameters:

safeIterator - If set to false, you must not modify the Storage while iterating over it. If set to true, you can safely modify, but the read-only iteration will happen on a copy of the unmodified Storage. This is similar to CopyOnWriteArrayList.

Storage

public Storage(int capacity,
               boolean safeIterator)

Constructs a new Storage with given capacity.

Parameters:

capacity - capacity

safeIterator - If set to false, you must not modify the Storage while iterating over it. If set to true, you can safely modify, but the read-only iteration will happen on a copy of the unmodified Storage. This is similar to CopyOnWriteArrayList.

Storage

public Storage(Hash<? super T,? super T> ha,
               boolean safeIterator)

Constructs a new Storage with given hash.

Parameters:

ha - hash

safeIterator - If set to false, you must not modify the Storage while iterating over it. If set to true, you can safely modify, but the read-only iteration will happen on a copy of the unmodified Storage. This is similar to CopyOnWriteArrayList.

Storage

public Storage(Hash<? super T,? super T> ha,
               int capacity)

Constructs a new Storage with given hash and capacity.

Parameters:

ha - hash

capacity - capacity

Storage

public Storage(Hash<? super T,? super T> ha,
               int capacity,
               boolean safeIterator)

Constructs a new Storage with given hash and capacity.

Parameters:

ha - hash

capacity - capacity

safeIterator - If set to false, you must not modify the Storage while iterating over it. If set to true, you can safely modify, but the read-only iteration will happen on a copy of the unmodified Storage. This is similar to CopyOnWriteArrayList.

Method Detail

copyArray

private void copyArray()

size

public int size()

Specified by:

size in interface java.util.Collection<T>

Specified by:

size in interface java.util.Set<T>

Specified by:

size in class java.util.AbstractCollection<T>

iterator

public java.util.Iterator<T> iterator()

Specified by:

iterator in interface java.util.Collection<T>

Specified by:

iterator in interface java.lang.Iterable<T>

Specified by:

iterator in interface java.util.Set<T>

Specified by:

iterator in class java.util.AbstractCollection<T>

contains

public boolean contains(java.lang.Object o)

Specified by:

contains in interface java.util.Collection<T>

Specified by:

contains in interface java.util.Set<T>

Overrides:

contains in class java.util.AbstractCollection<T>

add

public boolean add(T t)

Specified by:

add in interface java.util.Collection<T>

Specified by:

add in interface java.util.Set<T>

Overrides:

add in class java.util.AbstractCollection<T>

remove

public boolean remove(java.lang.Object o)

Specified by:

remove in interface java.util.Collection<T>

Specified by:

remove in interface java.util.Set<T>

Overrides:

remove in class java.util.AbstractCollection<T>

clear

public void clear()

Specified by:

clear in interface java.util.Collection<T>

Specified by:

clear in interface java.util.Set<T>

Overrides:

clear in class java.util.AbstractCollection<T>

hashCode

public int hashCode()

Specified by:

hashCode in interface java.util.Collection<T>

Specified by:

hashCode in interface java.util.Set<T>

Overrides:

hashCode in class java.util.AbstractSet<T>

equals

public boolean equals(java.lang.Object obj)

Specified by:

equals in interface java.util.Collection<T>

Specified by:

equals in interface java.util.Set<T>

Overrides:

equals in class java.util.AbstractSet<T>

put

public T put(T t)

get

public T get(T t)

putUnique

public T putUnique(T t)

removeElem

public T removeElem(T t)

foreignKey

public <K> java.util.Map<K,T> foreignKey(Hash<K,? super T> h)

rehash

private static int rehash(int h)

Additional mixing of hash

Parameters:

h - hash

Returns:

new hash

getBucket

private <K> int getBucket(Hash<K,? super T> ha,
                          K key)

Finds a bucket for given key.

Type Parameters:

K - type for hashCode and first equals parameter

Parameters:

ha - hash function

key - The key to compare

Returns:

the bucket equivalent to the key or -(bucket) as an empty slot where such an entry can be stored.

doRemove

private T doRemove(int slot)

fillTheHole

private void fillTheHole(int hole)

ensureSpace

private void ensureSpace()

defaultHash

public static <O> Hash<O,O> defaultHash()

A factory for default hash implementation.

Type Parameters:

O - type for hash

Returns:

a hash implementation that just delegates to object's own hashCode and equals.