jaulib v1.3.0
Jau Support Library (C++, Java, ..)
ArrayHashMap.java
Go to the documentation of this file.
1/**
2 * Author: Sven Gothel <sgothel@jausoft.com>
3 * Copyright (c) 2020 Gothel Software e.K.
4 * Copyright (c) 2015 Gothel Software e.K.
5 * Copyright (c) 2015 JogAmp Community.
6 *
7 * Permission is hereby granted, free of charge, to any person obtaining
8 * a copy of this software and associated documentation files (the
9 * "Software"), to deal in the Software without restriction, including
10 * without limitation the rights to use, copy, modify, merge, publish,
11 * distribute, sublicense, and/or sell copies of the Software, and to
12 * permit persons to whom the Software is furnished to do so, subject to
13 * the following conditions:
14 *
15 * The above copyright notice and this permission notice shall be
16 * included in all copies or substantial portions of the Software.
17 *
18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
19 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
20 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
21 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
22 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
23 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
24 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
25 */
26
27package org.jau.util;
28
29import java.util.ArrayList;
30import java.util.Collection;
31import java.util.HashMap;
32import java.util.Iterator;
33import java.util.Map;
34import java.util.Set;
35
36/**
37 * {@link HashMap} implementation backed by an {@link ArrayList} to preserve order of values.
38 *
39 * Implementation properties are:
40 * <ul>
41 * <li> Unique elements utilizing {@link java.lang.Object#hashCode()} for O(1) operations, see below.</li>
42 * <li> Java 1.5 compatible</li>
43 * </ul>
44 *
45 * O(1) operations:
46 * <ul>
47 * <li> put new key-value-pair(s) </li>
48 * <li> test for containment </li>
49 * <li> trying to remove non existent elements </li>
50 * </ul>
51 *
52 * O(n) operations:
53 * <ul>
54 * <li> put existing key-value-pair(s) </li>
55 * <li> removing existing elements</li>
56 * </ul>
57 *
58 * For thread safety, the application shall decorate access to instances via
59 * {@link jau.test.util.parallel.locks.RecursiveLock}.
60 *
61*/
62public class ArrayHashMap<K, V>
63 implements Cloneable, Map<K, V>
64{
65 /**
66 * Default load factor: {@value}
67 */
68 public static final float DEFAULT_LOAD_FACTOR = 0.75f;
69 /**
70 * The default initial capacity: {@value}
71 */
72 public static final int DEFAULT_INITIAL_CAPACITY = 16;
73
74 private final HashMap<K,V> map; // key -> object
75 private final ArrayList<V> data; // list of objects
76 private final boolean supportNullValue;
77
78 /**
79 *
80 * @param supportNullValue Use {@code true} for default behavior, i.e. {@code null} can be a valid value.
81 * Use {@code false} if {@code null} is not a valid value,
82 * here {@link #put(Object, Object)} and {@link #remove(Object)} will be optimized.
83 * @param initialCapacity use {@link #DEFAULT_INITIAL_CAPACITY} for default
84 * @param loadFactor use {@link #DEFAULT_LOAD_FACTOR} for default
85 * @see #supportsNullValue()
86 */
87 public ArrayHashMap(final boolean supportNullValue, final int initialCapacity, final float loadFactor) {
88 this.map = new HashMap<K,V>(initialCapacity, loadFactor);
89 this.data = new ArrayList<V>(initialCapacity);
90 this.supportNullValue = supportNullValue;
91 }
92
93 /**
94 * @return a shallow copy of this ArrayHashMap, elements are not copied.
95 */
97 map = new HashMap<K, V>(o.map);
98 data = new ArrayList<V>(o.data);
99 supportNullValue = o.supportNullValue;
100 }
101
102 /**
103 * Returns {@code true} for default behavior, i.e. {@code null} can be a valid value.
104 * <p>
105 * Returns {@code false} if {@code null} is not a valid value,
106 * here {@link #put(Object, Object)} and {@link #remove(Object)} are optimized operations.
107 * </p>
108 * @see #ArrayHashMap(boolean, int, float)
109 */
110 public final boolean supportsNullValue() { return supportNullValue; }
111
112 //
113 // Cloneable
114 //
115
116 /**
117 * Implementation uses {@link #ArrayHashMap(ArrayHashMap)}.
118 * @return a shallow copy of this ArrayHashMap, elements are not copied.
119 */
120 @Override
121 public final Object clone() {
122 return new ArrayHashMap<K, V>(this);
123 }
124
125 /**
126 * Returns this object ordered ArrayList. Use w/ care, it's not a copy.
127 * @see #toArrayList()
128 */
129 public final ArrayList<V> getData() { return data; }
130
131 /**
132 * @return a shallow copy of this ArrayHashMap's ArrayList, elements are not copied.
133 * @see #getData()
134 */
135 public final ArrayList<V> toArrayList() {
136 return new ArrayList<V>(data);
137 }
138
139 /** Returns this object hash map. Use w/ care, it's not a copy. */
140 public final HashMap<K,V> getMap() { return map; }
141
142 @Override
143 public final String toString() { return data.toString(); }
144
145 //
146 // Map
147 //
148
149 @Override
150 public final void clear() {
151 data.clear();
152 map.clear();
153 }
154
155 @Override
156 public Set<K> keySet() {
157 return map.keySet();
158 }
159
160 /**
161 * {@inheritDoc}
162 * <p>
163 * See {@link #getData()} and {@link #toArrayList()}.
164 * </p>
165 * @see #getData()
166 * @see #toArrayList()
167 */
168 @Override
169 public Collection<V> values() {
170 return map.values();
171 }
172
173 @Override
174 public Set<java.util.Map.Entry<K, V>> entrySet() {
175 return map.entrySet();
176 }
177
178 @Override
179 public final V get(final Object key) {
180 return map.get(key);
181 }
182
183 /**
184 * {@inheritDoc}
185 * <p>
186 * This is an O(1) operation, in case the key does not exist,
187 * otherwise O(n).
188 * </p>
189 * @throws NullPointerException if {@code value} is {@code null} but {@link #supportsNullValue()} == {@code false}
190 */
191 @Override
192 public final V put(final K key, final V value) throws NullPointerException {
193 final V oldValue;
194 if( supportNullValue ) {
195 // slow path
196 final boolean exists = map.containsKey(key);
197 if(!exists) {
198 // !exists
199 if( null != ( oldValue = map.put(key, value) ) ) {
200 // slips a valid null ..
201 throw new InternalError("Already existing, but checked before: "+key+" -> "+oldValue);
202 }
203 } else {
204 // exists
205 oldValue = map.put(key, value);
206 if( !data.remove(oldValue) ) {
207 throw new InternalError("Already existing, but not in list: "+oldValue);
208 }
209 }
210 } else {
211 checkNullValue(value);
212 // fast path
213 if( null != ( oldValue = map.put(key, value) ) ) {
214 // exists
215 if( !data.remove(oldValue) ) {
216 throw new InternalError("Already existing, but not in list: "+oldValue);
217 }
218 }
219 }
220 if(!data.add(value)) {
221 throw new InternalError("Couldn't add value to list: "+value);
222 }
223 return oldValue;
224 }
225
226 @Override
227 public void putAll(final Map<? extends K, ? extends V> m) {
228 for (final Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {
229 final Map.Entry<? extends K, ? extends V> e = i.next();
230 put(e.getKey(), e.getValue());
231 }
232 }
233
234 /**
235 * {@inheritDoc}
236 * <p>
237 * This is an O(1) operation, in case the key does not exist,
238 * otherwise O(n).
239 * </p>
240 */
241 @Override
242 public final V remove(final Object key) {
243 if( supportNullValue ) {
244 if( map.containsKey(key) ) {
245 // exists
246 final V oldValue = map.remove(key);
247 if ( !data.remove(oldValue) ) {
248 throw new InternalError("Couldn't remove prev mapped pair: "+key+" -> "+oldValue);
249 }
250 return oldValue;
251 }
252 } else {
253 final V oldValue;
254 if ( null != (oldValue = map.remove(key) ) ) {
255 // exists
256 if ( !data.remove(oldValue) ) {
257 throw new InternalError("Couldn't remove prev mapped pair: "+key+" -> "+oldValue);
258 }
259 }
260 return oldValue;
261 }
262 return null;
263 }
264
265 @Override
266 public final boolean containsKey(final Object key) {
267 return map.containsKey(key);
268 }
269
270 @Override
271 public boolean containsValue(final Object value) {
272 return map.containsValue(value);
273 }
274
275 @Override
276 public final boolean equals(final Object arrayHashMap) {
277 if ( !(arrayHashMap instanceof ArrayHashMap) ) {
278 return false;
279 }
280 return map.equals(((ArrayHashMap<?,?>)arrayHashMap).map);
281 }
282
283 @Override
284 public final int hashCode() {
285 return map.hashCode();
286 }
287
288 @Override
289 public final boolean isEmpty() {
290 return data.isEmpty();
291 }
292
293 @Override
294 public final int size() {
295 return data.size();
296 }
297
298 private static final void checkNullValue(final Object value) throws NullPointerException {
299 if( null == value ) {
300 throw new NullPointerException("Null value not supported");
301 }
302 }
303}
HashMap implementation backed by an ArrayList to preserve order of values.
boolean containsValue(final Object value)
final boolean equals(final Object arrayHashMap)
final ArrayList< V > toArrayList()
void putAll(final Map<? extends K, ? extends V > m)
ArrayHashMap(final boolean supportNullValue, final int initialCapacity, final float loadFactor)
final boolean supportsNullValue()
Returns true for default behavior, i.e.
final V put(final K key, final V value)
static final float DEFAULT_LOAD_FACTOR
Default load factor: {@value}.
final boolean containsKey(final Object key)
final HashMap< K, V > getMap()
Returns this object hash map.
ArrayHashMap(final ArrayHashMap< K, V > o)
final Object clone()
Implementation uses ArrayHashMap(ArrayHashMap).
Set< java.util.Map.Entry< K, V > > entrySet()
static final int DEFAULT_INITIAL_CAPACITY
The default initial capacity: {@value}.
final ArrayList< V > getData()
Returns this object ordered ArrayList.
Collection< V > values()