CompactPairKeyHashMap - map Pair to Object

/*
 * #!
 * Ontopia Engine
 * #-
 * Copyright (C) 2001 - 2013 The Ontopia Project
 * #-
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 * 
 *      http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 * !#
 */

sclass CompactPairKeyHashMap<K, V> extends AbstractMap<Pair<K>, V> {
  final static int INITIAL_SIZE = 3;
  final static double LOAD_FACTOR = 0.6;

  // This object is used to represent null, should clients use that as
  final static Object nullObject = new Object();
  
  /**
   * When a key is deleted this object is put into the hashtable in
   * its place, so that other entries with the same key (collisions)
   * further down the hashtable are not lost after we delete an object
   * in the collision chain.
   */
  final static Object deletedObject = new Object();
  int elements;
  int freecells;
  K[] keys1;
  K[] keys2;
  V[] values; // object at pos x corresponds to key at pos x
  int modCount;

  *() {
    this(INITIAL_SIZE);
  }

  *(int size) {
    keys1 = (K[]) new Object[(size==0 ? 1 : size)];
    keys2 = (K[]) new Object[(size==0 ? 1 : size)];
    values = (V[]) new Object[(size==0 ? 1 : size)];
    elements = 0;
    freecells = keys1.length;
    modCount = 0;
  }

  // ===== MAP IMPLEMENTATION =============================================

  /**
   * Returns the number of key/value mappings in this map.
   */
  public synchronized int size() {
    return elements;
  }
  
  /**
   * Returns <tt>true</tt> if this map contains no mappings.
   */
  public synchronized boolean isEmpty() {
    return elements == 0;
  }

  /**
   * Removes all key/value mappings in the map.
   */
  public synchronized void clear() {
    elements = 0;
    for (int ix = 0; ix < keys1.length; ix++) {
      keys1[ix] = keys2[ix] = null;
      values[ix] = null;
    }
    freecells = values.length;
    modCount++;
  }
  
  /**
   * Returns <tt>true</tt> if this map contains the specified key.
   */
  public synchronized boolean containsKey(Object k) {
    return keys1[findKeyIndex(k)] != null;
  }
  
  /**
   * Returns <tt>true</tt> if this map contains the specified value.
   */
  public synchronized boolean containsValue(Object v) {
    if (v == null)
      v = (V)nullObject;

    for (int ix = 0; ix < values.length; ix++)
      if (values[ix] != null && values[ix].equals(v))
        return true;

    return false;
  }

  /**
   * Returns a read-only set view of the map's keys.
   */
  public synchronized Set<Entry<Pair<K>, V>> entrySet() {
    throw new UnsupportedOperationException();
  }

  /**
   * Removes the mapping with key k, if there is one, and returns its
   * value, if there is one, and null if there is none.
   */
  public synchronized V remove(Object k) {
    int index = findKeyIndex(k);

    // we found the right position, now do the removal
    if (keys1[index] != null) {
      // we found the object

      // same problem here as with put
      V v = values[index];
      keys1[index] = keys2[index] = (K) deletedObject;
      values[index] = (V) deletedObject;
      modCount++;
      elements--;
      return v;
    } else
      // we did not find the key
      return null;
  }

  /**
   * Adds the specified mapping to this map, returning the old value for
   * the mapping, if there was one.
   */
  public synchronized V put(Pair<K> k, V v) {
    if (k.a == null)
      k = pair((K)nullObject, k.b);
    if (k.b == null)
      k = pair(k.a, (K)nullObject);

    int hash = k.hashCode();
    int hash1 = k.a.hashCode();
    int hash2 = k.b.hashCode();
    int index = (hash & 0x7FFFFFFF) % keys1.length;
    int offset = 1;
    int deletedix = -1;
    
    // search for the key (continue while !null and !this key)
    while(keys1[index] != null &&
          !(keys1[index].hashCode() == hash1 &&
            keys2[index].hashCode() == hash2 &&
            keys1[index].equals(k.a) &&
            keys2[index].equals(k.b))) {

      // if there's a deleted mapping here we can put this mapping here,
      // provided it's not in here somewhere else already
      if (keys1[index] == deletedObject)
        deletedix = index;
      
      index = ((index + offset) & 0x7FFFFFFF) % keys1.length;
      offset = offset*2 + 1;

      if (offset == -1)
        offset = 2;
    }
    
    if (keys1[index] == null) { // wasn't present already
      if (deletedix != -1) // reusing a deleted cell
        index = deletedix;
      else
        freecells--;

      modCount++;
      elements++;

      keys1[index] = k.a;
      keys2[index] = k.b;
      values[index] = (V) v;
      
      // rehash with increased capacity
      if (1 - (freecells / (double) keys1.length) > LOAD_FACTOR)
        rehash(keys1.length*2 + 1);
      return null;
    } else { // was there already
      modCount++;
      V oldv = values[index];
      values[index] = (V) v;
      return oldv;
    }
  }

  /**
   * INTERNAL: Rehashes the hashmap to a bigger size.
   */
  void rehash(int newCapacity) {
    int oldCapacity = keys1.length;
    K[] newKeys1 = (K[]) new Object[newCapacity];
    K[] newKeys2 = (K[]) new Object[newCapacity];
    V[] newValues = (V[]) new Object[newCapacity];

    for (int ix = 0; ix < oldCapacity; ix++) {
      Object k1 = keys1[ix];
      if (k1 == null || k1 == deletedObject)
        continue;
      
      Object k2 = keys2[ix];
      int hash = pair(k1, k2).hashCode();
      int index = (hash & 0x7FFFFFFF) % newCapacity;
      int offset = 1;

      // search for the key
      while(newKeys1[index] != null) { // no need to test for duplicates
        index = ((index + offset) & 0x7FFFFFFF) % newCapacity;
        offset = offset*2 + 1;

        if (offset == -1)
          offset = 2;
      }

      newKeys1[index] = (K) k1;
      newKeys2[index] = (K) k2;
      newValues[index] = values[ix];
    }

    keys1 = newKeys1;
    keys2 = newKeys2;
    values = newValues;
    freecells = keys1.length - elements;
  }

  /**
   * Returns the value for the key k, if there is one, and null if
   * there is none.
   */
  public synchronized V get(Object k) {
    return values[findKeyIndex(k)];
  }

  /**
   * Returns a virtual read-only collection containing all the values
   * in the map.
   */
  public synchronized Collection<V> values() {
    return new ValueCollection();
  }

  /**
   * Returns a virtual read-only set of all the keys in the map.
   */
  public synchronized Set<Pair<K>> keySet() {
    return new KeySet();
  }

  // --- Internal utilities

  final int findKeyIndex(Object _k) {
    Pair k = cast _k;
    if (k.a == null)
      k = pair((K)nullObject, k.b);
    if (k.b == null)
      k = pair(k.a, (K)nullObject);

    int hash = k.hashCode();
    int hash1 = k.a.hashCode();
    int hash2 = k.b.hashCode();
    int index = (hash & 0x7FFFFFFF) % keys1.length;
    int offset = 1;
    int deletedix = -1;
    
    // search for the key (continue while !null and !this key)
    while(keys1[index] != null &&
          !(keys1[index].hashCode() == hash1 &&
            keys2[index].hashCode() == hash2 &&
            keys1[index].equals(k.a) &&
            keys2[index].equals(k.b))) {
      index = ((index + offset) & 0x7FFFFFFF) % keys1.length;
      offset = offset*2 + 1;

      if (offset == -1)
        offset = 2;
    }
    return index;
  }
  
  // --- Key set

  class KeySet extends AbstractSet<Pair<K>> {
    public synchronized int size() {
      return elements;
    }

    public synchronized boolean contains(Object k) {
      return containsKey(k);
    }

    public synchronized Iterator<Pair<K>> iterator() {
      return new KeyIterator();
    }
  }

  class KeyIterator implements Iterator<Pair<K>> {
    private int ix;
    
    private KeyIterator() {
      // walk up to first value, so that hasNext() and next() return
      // correct results
      for (; ix < keys1.length; ix++)
        if (values[ix] != null && keys1[ix] != deletedObject)
          break;
    }

    public synchronized boolean hasNext() {
      return ix < keys1.length;
    }

    public synchronized void remove() {
      throw new UnsupportedOperationException("Collection is read-only");
    }

    public synchronized Pair<K> next() {
      if (ix >= keys1.length)
        throw new NoSuchElementException();
      K key1 = (K) keys1[ix];
      K key2 = (K) keys2[ix];
      ix++;
      
      // walk up to next value
      for (; ix < keys1.length; ix++)
        if (keys1[ix] != null && keys1[ix] != deletedObject)
          break;
      
      // ix now either points to next key, or outside array (if no next)
      return pair(key1, key2);
    }
  }
  
  // --- Value collection

  class ValueCollection extends AbstractCollection<V> {
    public synchronized int size() {
      return elements;
    }

    public synchronized Iterator<V> iterator() {
      return new ValueIterator();
    }

    public synchronized boolean contains(Object v) {
      return containsValue(v);
    }
  }

  class ValueIterator implements Iterator<V> {
    private int ix;
    
    private ValueIterator() {
      // walk up to first value, so that hasNext() and next() return
      // correct results
      for (; ix < values.length; ix++)
        if (values[ix] != null && values[ix] != deletedObject)
          break;
    }

    public synchronized boolean hasNext() {
      return ix < values.length;
    }

    public synchronized void remove() {
      throw new UnsupportedOperationException("Collection is read-only");
    }

    public synchronized V next() {
      if (ix >= values.length)
        throw new NoSuchElementException();
      V value = (V) values[ix++];
      
      // walk up to next value
      for (; ix < values.length; ix++)
        if (values[ix] != null && values[ix] != deletedObject)
          break;
      
      // ix now either points to next value, or outside array (if no next)
      return value;
    }
  }
}

Travelled to 13 computer(s): aoiabmzegqzx, bhatertpkbcr, cbybwowwnfue, cfunsshuasjs, gwrvuhgaqvyk, ishqpsrjomds, lpdgvwnxivlt, mqqgnosmbjvj, pyentgdyhuwx, pzhvpgtvlbxg, tslmcundralx, tvejysmllsmz, vouqrxazstgt

Snippet ID:	#1013385
Snippet name:	CompactPairKeyHashMap - map Pair to Object - synchronized
Eternal ID of this version:	#1013385/9
Text MD5:	23d7126110be94924140caad240495d7
Author:	stefan
Category:	javax / collections
Type:	JavaX fragment (include)
Public (visible to everyone):	Yes
Archived (hidden from active list):	No
Created/modified:	2018-01-04 00:12:40
Source code size:	10675 bytes / 390 lines
Pitched / IR pitched:	No / No
Views / Downloads:	460 / 1028
Version history:	8 change(s)
Referenced in:	[show references]

< > BotCompany Repo | #1013385 // CompactPairKeyHashMap - map Pair to Object - synchronized

JavaX fragment (include)

Author comment

1	/*
2	* #!
3	* Ontopia Engine
4	* #-
5	* Copyright (C) 2001 - 2013 The Ontopia Project
6	* #-
7	* Licensed under the Apache License, Version 2.0 (the "License");
8	* you may not use this file except in compliance with the License.
9	* You may obtain a copy of the License at
10	*
11	* http://www.apache.org/licenses/LICENSE-2.0
12	*
13	* Unless required by applicable law or agreed to in writing, software
14	* distributed under the License is distributed on an "AS IS" BASIS,
15	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16	* See the License for the specific language governing permissions and
17	* limitations under the License.
18	* !#
19	*/
20
21	sclass CompactPairKeyHashMap<K, V> extends AbstractMap<Pair<K>, V> {
22	final static int INITIAL_SIZE = 3;
23	final static double LOAD_FACTOR = 0.6;
24
25	// This object is used to represent null, should clients use that as
26	final static Object nullObject = new Object();
27
28	/**
29	* When a key is deleted this object is put into the hashtable in
30	* its place, so that other entries with the same key (collisions)
31	* further down the hashtable are not lost after we delete an object
32	* in the collision chain.
33	*/
34	final static Object deletedObject = new Object();
35	int elements;
36	int freecells;
37	K[] keys1;
38	K[] keys2;
39	V[] values; // object at pos x corresponds to key at pos x
40	int modCount;
41
42	*() {
43	this(INITIAL_SIZE);
44	}
45
46	*(int size) {
47	keys1 = (K[]) new Object[(size==0 ? 1 : size)];
48	keys2 = (K[]) new Object[(size==0 ? 1 : size)];
49	values = (V[]) new Object[(size==0 ? 1 : size)];
50	elements = 0;
51	freecells = keys1.length;
52	modCount = 0;
53	}
54
55	// ===== MAP IMPLEMENTATION =============================================
56
57	/**
58	* Returns the number of key/value mappings in this map.
59	*/
60	public synchronized int size() {
61	return elements;
62	}
63
64	/**
65	* Returns <tt>true</tt> if this map contains no mappings.
66	*/
67	public synchronized boolean isEmpty() {
68	return elements == 0;
69	}
70
71	/**
72	* Removes all key/value mappings in the map.
73	*/
74	public synchronized void clear() {
75	elements = 0;
76	for (int ix = 0; ix < keys1.length; ix++) {
77	keys1[ix] = keys2[ix] = null;
78	values[ix] = null;
79	}
80	freecells = values.length;
81	modCount++;
82	}
83
84	/**
85	* Returns <tt>true</tt> if this map contains the specified key.
86	*/
87	public synchronized boolean containsKey(Object k) {
88	return keys1[findKeyIndex(k)] != null;
89	}
90
91	/**
92	* Returns <tt>true</tt> if this map contains the specified value.
93	*/
94	public synchronized boolean containsValue(Object v) {
95	if (v == null)
96	v = (V)nullObject;
97
98	for (int ix = 0; ix < values.length; ix++)
99	if (values[ix] != null && values[ix].equals(v))
100	return true;
101
102	return false;
103	}
104
105	/**
106	* Returns a read-only set view of the map's keys.
107	*/
108	public synchronized Set<Entry<Pair<K>, V>> entrySet() {
109	throw new UnsupportedOperationException();
110	}
111
112	/**
113	* Removes the mapping with key k, if there is one, and returns its
114	* value, if there is one, and null if there is none.
115	*/
116	public synchronized V remove(Object k) {
117	int index = findKeyIndex(k);
118
119	// we found the right position, now do the removal
120	if (keys1[index] != null) {
121	// we found the object
122
123	// same problem here as with put
124	V v = values[index];
125	keys1[index] = keys2[index] = (K) deletedObject;
126	values[index] = (V) deletedObject;
127	modCount++;
128	elements--;
129	return v;
130	} else
131	// we did not find the key
132	return null;
133	}
134
135	/**
136	* Adds the specified mapping to this map, returning the old value for
137	* the mapping, if there was one.
138	*/
139	public synchronized V put(Pair<K> k, V v) {
140	if (k.a == null)
141	k = pair((K)nullObject, k.b);
142	if (k.b == null)
143	k = pair(k.a, (K)nullObject);
144
145	int hash = k.hashCode();
146	int hash1 = k.a.hashCode();
147	int hash2 = k.b.hashCode();
148	int index = (hash & 0x7FFFFFFF) % keys1.length;
149	int offset = 1;
150	int deletedix = -1;
151
152	// search for the key (continue while !null and !this key)
153	while(keys1[index] != null &&
154	!(keys1[index].hashCode() == hash1 &&
155	keys2[index].hashCode() == hash2 &&
156	keys1[index].equals(k.a) &&
157	keys2[index].equals(k.b))) {
158
159	// if there's a deleted mapping here we can put this mapping here,
160	// provided it's not in here somewhere else already
161	if (keys1[index] == deletedObject)
162	deletedix = index;
163
164	index = ((index + offset) & 0x7FFFFFFF) % keys1.length;
165	offset = offset*2 + 1;
166
167	if (offset == -1)
168	offset = 2;
169	}
170
171	if (keys1[index] == null) { // wasn't present already
172	if (deletedix != -1) // reusing a deleted cell
173	index = deletedix;
174	else
175	freecells--;
176
177	modCount++;
178	elements++;
179
180	keys1[index] = k.a;
181	keys2[index] = k.b;
182	values[index] = (V) v;
183
184	// rehash with increased capacity
185	if (1 - (freecells / (double) keys1.length) > LOAD_FACTOR)
186	rehash(keys1.length*2 + 1);
187	return null;
188	} else { // was there already
189	modCount++;
190	V oldv = values[index];
191	values[index] = (V) v;
192	return oldv;
193	}
194	}
195
196	/**
197	* INTERNAL: Rehashes the hashmap to a bigger size.
198	*/
199	void rehash(int newCapacity) {
200	int oldCapacity = keys1.length;
201	K[] newKeys1 = (K[]) new Object[newCapacity];
202	K[] newKeys2 = (K[]) new Object[newCapacity];
203	V[] newValues = (V[]) new Object[newCapacity];
204
205	for (int ix = 0; ix < oldCapacity; ix++) {
206	Object k1 = keys1[ix];
207	if (k1 == null \|\| k1 == deletedObject)
208	continue;
209
210	Object k2 = keys2[ix];
211	int hash = pair(k1, k2).hashCode();
212	int index = (hash & 0x7FFFFFFF) % newCapacity;
213	int offset = 1;
214
215	// search for the key
216	while(newKeys1[index] != null) { // no need to test for duplicates
217	index = ((index + offset) & 0x7FFFFFFF) % newCapacity;
218	offset = offset*2 + 1;
219
220	if (offset == -1)
221	offset = 2;
222	}
223
224	newKeys1[index] = (K) k1;
225	newKeys2[index] = (K) k2;
226	newValues[index] = values[ix];
227	}
228
229	keys1 = newKeys1;
230	keys2 = newKeys2;
231	values = newValues;
232	freecells = keys1.length - elements;
233	}
234
235	/**
236	* Returns the value for the key k, if there is one, and null if
237	* there is none.
238	*/
239	public synchronized V get(Object k) {
240	return values[findKeyIndex(k)];
241	}
242
243	/**
244	* Returns a virtual read-only collection containing all the values
245	* in the map.
246	*/
247	public synchronized Collection<V> values() {
248	return new ValueCollection();
249	}
250
251	/**
252	* Returns a virtual read-only set of all the keys in the map.
253	*/
254	public synchronized Set<Pair<K>> keySet() {
255	return new KeySet();
256	}
257
258	// --- Internal utilities
259
260	final int findKeyIndex(Object _k) {
261	Pair k = cast _k;
262	if (k.a == null)
263	k = pair((K)nullObject, k.b);
264	if (k.b == null)
265	k = pair(k.a, (K)nullObject);
266
267	int hash = k.hashCode();
268	int hash1 = k.a.hashCode();
269	int hash2 = k.b.hashCode();
270	int index = (hash & 0x7FFFFFFF) % keys1.length;
271	int offset = 1;
272	int deletedix = -1;
273
274	// search for the key (continue while !null and !this key)
275	while(keys1[index] != null &&
276	!(keys1[index].hashCode() == hash1 &&
277	keys2[index].hashCode() == hash2 &&
278	keys1[index].equals(k.a) &&
279	keys2[index].equals(k.b))) {
280	index = ((index + offset) & 0x7FFFFFFF) % keys1.length;
281	offset = offset*2 + 1;
282
283	if (offset == -1)
284	offset = 2;
285	}
286	return index;
287	}
288
289	// --- Key set
290
291	class KeySet extends AbstractSet<Pair<K>> {
292	public synchronized int size() {
293	return elements;
294	}
295
296	public synchronized boolean contains(Object k) {
297	return containsKey(k);
298	}
299
300	public synchronized Iterator<Pair<K>> iterator() {
301	return new KeyIterator();
302	}
303	}
304
305	class KeyIterator implements Iterator<Pair<K>> {
306	private int ix;
307
308	private KeyIterator() {
309	// walk up to first value, so that hasNext() and next() return
310	// correct results
311	for (; ix < keys1.length; ix++)
312	if (values[ix] != null && keys1[ix] != deletedObject)
313	break;
314	}
315
316	public synchronized boolean hasNext() {
317	return ix < keys1.length;
318	}
319
320	public synchronized void remove() {
321	throw new UnsupportedOperationException("Collection is read-only");
322	}
323
324	public synchronized Pair<K> next() {
325	if (ix >= keys1.length)
326	throw new NoSuchElementException();
327	K key1 = (K) keys1[ix];
328	K key2 = (K) keys2[ix];
329	ix++;
330
331	// walk up to next value
332	for (; ix < keys1.length; ix++)
333	if (keys1[ix] != null && keys1[ix] != deletedObject)
334	break;
335
336	// ix now either points to next key, or outside array (if no next)
337	return pair(key1, key2);
338	}
339	}
340
341	// --- Value collection
342
343	class ValueCollection extends AbstractCollection<V> {
344	public synchronized int size() {
345	return elements;
346	}
347
348	public synchronized Iterator<V> iterator() {
349	return new ValueIterator();
350	}
351
352	public synchronized boolean contains(Object v) {
353	return containsValue(v);
354	}
355	}
356
357	class ValueIterator implements Iterator<V> {
358	private int ix;
359
360	private ValueIterator() {
361	// walk up to first value, so that hasNext() and next() return
362	// correct results
363	for (; ix < values.length; ix++)
364	if (values[ix] != null && values[ix] != deletedObject)
365	break;
366	}
367
368	public synchronized boolean hasNext() {
369	return ix < values.length;
370	}
371
372	public synchronized void remove() {
373	throw new UnsupportedOperationException("Collection is read-only");
374	}
375
376	public synchronized V next() {
377	if (ix >= values.length)
378	throw new NoSuchElementException();
379	V value = (V) values[ix++];
380
381	// walk up to next value
382	for (; ix < values.length; ix++)
383	if (values[ix] != null && values[ix] != deletedObject)
384	break;
385
386	// ix now either points to next value, or outside array (if no next)
387	return value;
388	}
389	}
390	}