This project has retired. For details please refer to its Attic page.
Basic2ObjectMap xref
View Javadoc

1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one
3    * or more contributor license agreements.  See the NOTICE file
4    * distributed with this work for additional information
5    * regarding copyright ownership.  The ASF licenses this file
6    * to you under the Apache License, Version 2.0 (the
7    * "License"); you may not use this file except in compliance
8    * with the License.  You may obtain a copy of the License at
9    *
10   *     http://www.apache.org/licenses/LICENSE-2.0
11   *
12   * Unless required by applicable law or agreed to in writing, software
13   * distributed under the License is distributed on an "AS IS" BASIS,
14   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15   * See the License for the specific language governing permissions and
16   * limitations under the License.
17   */
18  package org.apache.giraph.types.ops.collections;
19  
20  import it.unimi.dsi.fastutil.ints.Int2ObjectMap;
21  import it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap;
22  import it.unimi.dsi.fastutil.ints.IntIterator;
23  import it.unimi.dsi.fastutil.longs.Long2ObjectMap;
24  import it.unimi.dsi.fastutil.longs.Long2ObjectOpenHashMap;
25  import it.unimi.dsi.fastutil.longs.LongIterator;
26  import it.unimi.dsi.fastutil.objects.Object2ObjectMap;
27  import it.unimi.dsi.fastutil.objects.Object2ObjectOpenHashMap;
28  import it.unimi.dsi.fastutil.objects.ObjectIterator;
29  
30  import java.io.DataInput;
31  import java.io.DataOutput;
32  import java.io.IOException;
33  import java.util.Collection;
34  import java.util.Iterator;
35  
36  import org.apache.giraph.types.ops.IntTypeOps;
37  import org.apache.giraph.types.ops.LongTypeOps;
38  import org.apache.giraph.types.ops.PrimitiveIdTypeOps;
39  import org.apache.giraph.utils.WritableUtils;
40  import org.apache.hadoop.io.IntWritable;
41  import org.apache.hadoop.io.LongWritable;
42  import org.apache.hadoop.io.Writable;
43  
44  import com.google.common.base.Preconditions;
45  
46  /**
47   * Basic2ObjectMap with only basic set of operations.
48   * All operations that return object K are returning reusable object,
49   * which is modified after calling any other function.
50   *
51   * @param <K> Key type
52   * @param <V> Value type
53   */
54  public abstract class Basic2ObjectMap<K, V> implements Writable {
55    /** Removes all of the elements from this list. */
56    public abstract void clear();
57    /**
58     * Number of elements in this list
59     * @return size
60     */
61    public abstract int size();
62  
63    /**
64     * Checks whether key is present in the map
65     * @param key Key
66     * @return true if present
67     */
68    public abstract boolean containsKey(K key);
69    /**
70     * Adds a pair to the map.
71     *
72     * @param key Key
73     * @param value Value.
74     * @return the old value, or null if no value was present for the given key.
75     */
76    public abstract V put(K key, V value);
77    /**
78     * Get value for a given key
79     * @param key Key
80     * @return Value, or null
81     */
82    public abstract V get(K key);
83    /**
84     * Removes the mapping with the given key.
85     *
86     * @param key Key
87     * @return the old value, or null if no value was present for the given key.
88     */
89    public abstract V remove(K key);
90    /**
91     * TypeOps for type of keys this object holds
92     * @return TypeOps
93     */
94    public abstract PrimitiveIdTypeOps<K> getKeyTypeOps();
95    /**
96     * Fast iterator over keys within this map, which doesn't allocate new
97     * element for each returned element.
98     *
99     * Object returned by next() is only valid until next() is called again,
100    * because it is reused.
101    *
102    * @return Iterator
103    */
104   public abstract Iterator<K> fastKeyIterator();
105 
106   /**
107    * Iterator over map values.
108    *
109    * @return Iterator
110    */
111   public abstract Iterator<V> valueIterator();
112 
113   /**
114    * A collection of all values.
115    *
116    * @return Iterator
117    */
118   public abstract Collection<V> values();
119 
120   /**
121    * Iterator that reuses key object.
122    *
123    * @param <Iter> Primitive key iterator type
124    */
125   protected abstract class ReusableIterator<Iter extends Iterator<?>>
126       implements ResettableIterator<K> {
127     /** Primitive Key iterator */
128     protected Iter iter;
129     /** Reusable key object */
130     protected final K reusableKey = getKeyTypeOps().create();
131 
132     /**
133      * Constructor
134      * @param iter Primitive Key iterator
135      */
136     public ReusableIterator(Iter iter) {
137       this.iter = iter;
138     }
139 
140     @Override
141     public boolean hasNext() {
142       return iter.hasNext();
143     }
144 
145     @Override
146     public void remove() {
147       iter.remove();
148     }
149   }
150 
151   /** IntWritable implementation of Basic2ObjectMap */
152   public static final class BasicInt2ObjectOpenHashMap<V>
153       extends Basic2ObjectMap<IntWritable, V> {
154     /** Map */
155     private final Int2ObjectOpenHashMap<V> map;
156     /** Value writer */
157     private final WritableWriter<V> valueWriter;
158 
159     /**
160      * Constructor
161      *
162      * @param valueWriter Writer of values
163      */
164     public BasicInt2ObjectOpenHashMap(WritableWriter<V> valueWriter) {
165       this.map = new Int2ObjectOpenHashMap<>();
166       this.valueWriter = valueWriter;
167     }
168 
169     /**
170      * Constructor
171      *
172      * @param capacity Capacity
173      * @param valueWriter Writer of values
174      */
175     public BasicInt2ObjectOpenHashMap(
176         int capacity, WritableWriter<V> valueWriter) {
177       this.map = new Int2ObjectOpenHashMap<>(capacity);
178       this.valueWriter = valueWriter;
179     }
180 
181     @Override
182     public void clear() {
183       map.clear();
184     }
185 
186     @Override
187     public int size() {
188       return map.size();
189     }
190 
191     @Override
192     public boolean containsKey(IntWritable key) {
193       return map.containsKey(key.get());
194     }
195 
196     @Override
197     public V put(IntWritable key, V value) {
198       return map.put(key.get(), value);
199     }
200 
201     @Override
202     public V get(IntWritable key) {
203       return map.get(key.get());
204     }
205 
206     @Override
207     public V remove(IntWritable key) {
208       return map.remove(key.get());
209     }
210 
211     @Override
212     public PrimitiveIdTypeOps<IntWritable> getKeyTypeOps() {
213       return IntTypeOps.INSTANCE;
214     }
215 
216     @Override
217     public Iterator<IntWritable> fastKeyIterator() {
218       return new ReusableIterator<IntIterator>(map.keySet().iterator()) {
219         @Override
220         public IntWritable next() {
221           reusableKey.set(iter.nextInt());
222           return reusableKey;
223         }
224 
225         @Override
226         public void reset() {
227           iter = map.keySet().iterator();
228         }
229       };
230     }
231 
232     @Override
233     public Iterator<V> valueIterator() {
234       return map.values().iterator();
235     }
236 
237     @Override
238     public Collection<V> values() {
239       return map.values();
240     }
241 
242     @Override
243     public void write(DataOutput out) throws IOException {
244       out.writeInt(map.size());
245       ObjectIterator<Int2ObjectMap.Entry<V>> iterator =
246           map.int2ObjectEntrySet().fastIterator();
247       while (iterator.hasNext()) {
248         Int2ObjectMap.Entry<V> entry = iterator.next();
249         out.writeInt(entry.getIntKey());
250         valueWriter.write(out, entry.getValue());
251       }
252     }
253 
254     @Override
255     public void readFields(DataInput in)
256       throws IOException {
257       int size = in.readInt();
258       map.clear();
259       map.trim(size);
260       while (size-- > 0) {
261         int key = in.readInt();
262         V value = valueWriter.readFields(in);
263         map.put(key, value);
264       }
265     }
266   }
267 
268   /** LongWritable implementation of Basic2ObjectMap */
269   public static final class BasicLong2ObjectOpenHashMap<V>
270       extends Basic2ObjectMap<LongWritable, V> {
271     /** Map */
272     private final Long2ObjectOpenHashMap<V> map;
273     /** Value writer */
274     private final WritableWriter<V> valueWriter;
275 
276     /**
277      * Constructor
278      *
279      * @param valueWriter Writer of values
280      */
281     public BasicLong2ObjectOpenHashMap(WritableWriter<V> valueWriter) {
282       this.map = new Long2ObjectOpenHashMap<>();
283       this.valueWriter = valueWriter;
284     }
285 
286     /**
287      * Constructor
288      *
289      * @param capacity Capacity
290      * @param valueWriter Writer of values
291      */
292     public BasicLong2ObjectOpenHashMap(
293         int capacity, WritableWriter<V> valueWriter) {
294       this.map = new Long2ObjectOpenHashMap<>(capacity);
295       this.valueWriter = valueWriter;
296     }
297 
298     @Override
299     public void clear() {
300       map.clear();
301     }
302 
303     @Override
304     public int size() {
305       return map.size();
306     }
307 
308     @Override
309     public boolean containsKey(LongWritable key) {
310       return map.containsKey(key.get());
311     }
312 
313     @Override
314     public V put(LongWritable key, V value) {
315       return map.put(key.get(), value);
316     }
317 
318     @Override
319     public V get(LongWritable key) {
320       return map.get(key.get());
321     }
322 
323     @Override
324     public V remove(LongWritable key) {
325       return map.remove(key.get());
326     }
327 
328     @Override
329     public PrimitiveIdTypeOps<LongWritable> getKeyTypeOps() {
330       return LongTypeOps.INSTANCE;
331     }
332 
333     @Override
334     public Iterator<LongWritable> fastKeyIterator() {
335       return new ReusableIterator<LongIterator>(map.keySet().iterator()) {
336         @Override
337         public LongWritable next() {
338           reusableKey.set(iter.nextLong());
339           return reusableKey;
340         }
341 
342         @Override
343         public void reset() {
344           iter = map.keySet().iterator();
345         }
346       };
347     }
348 
349     @Override
350     public Iterator<V> valueIterator() {
351       return map.values().iterator();
352     }
353 
354     @Override
355     public Collection<V> values() {
356       return map.values();
357     }
358 
359     @Override
360     public void write(DataOutput out) throws IOException {
361       Preconditions.checkState(
362         valueWriter != null,
363         "valueWriter is not provided"
364       );
365 
366       out.writeInt(map.size());
367       ObjectIterator<Long2ObjectMap.Entry<V>> iterator =
368           map.long2ObjectEntrySet().fastIterator();
369       while (iterator.hasNext()) {
370         Long2ObjectMap.Entry<V> entry = iterator.next();
371         out.writeLong(entry.getLongKey());
372         valueWriter.write(out, entry.getValue());
373       }
374     }
375 
376     @Override
377     public void readFields(DataInput in) throws IOException {
378       Preconditions.checkState(
379         valueWriter != null,
380         "valueWriter is not provided"
381       );
382 
383       int size = in.readInt();
384       map.clear();
385       map.trim(size);
386       while (size-- > 0) {
387         long key = in.readLong();
388         V value = valueWriter.readFields(in);
389         map.put(key, value);
390       }
391     }
392   }
393 
394   /** Writable implementation of Basic2ObjectMap */
395   public static final class BasicObject2ObjectOpenHashMap<K extends Writable, V>
396       extends Basic2ObjectMap<K, V> {
397     /** Map */
398     private final Object2ObjectOpenHashMap<K, V> map;
399     /** Key writer */
400     private final WritableWriter<K> keyWriter;
401     /** Value writer */
402     private final WritableWriter<V> valueWriter;
403 
404     /**
405      * Constructor
406      *
407      * @param keyWriter Writer of keys
408      * @param valueWriter Writer of values
409      */
410     public BasicObject2ObjectOpenHashMap(
411       WritableWriter<K> keyWriter,
412       WritableWriter<V> valueWriter
413     ) {
414       this.map = new Object2ObjectOpenHashMap<>();
415       this.keyWriter = keyWriter;
416       this.valueWriter = valueWriter;
417     }
418 
419     /**
420      * Constructor
421      *
422      * @param capacity Map capacity
423      * @param keyWriter Writer of keys
424      * @param valueWriter Writer of values
425      */
426     public BasicObject2ObjectOpenHashMap(
427       int capacity,
428       WritableWriter<K> keyWriter,
429       WritableWriter<V> valueWriter
430     ) {
431       this.map = new Object2ObjectOpenHashMap<>(capacity);
432       this.keyWriter = keyWriter;
433       this.valueWriter = valueWriter;
434     }
435 
436     @Override
437     public void clear() {
438       map.clear();
439     }
440 
441     @Override
442     public int size() {
443       return map.size();
444     }
445 
446     @Override
447     public boolean containsKey(K key) {
448       return map.containsKey(key);
449     }
450 
451     @Override
452     public V put(K key, V value) {
453       // we need a copy since the key object is mutable
454       K copyKey = WritableUtils.createCopy(key);
455       return map.put(copyKey, value);
456     }
457 
458     @Override
459     public V get(K key) {
460       return map.get(key);
461     }
462 
463     @Override
464     public V remove(K key) {
465       return map.remove(key);
466     }
467 
468     @Override
469     public PrimitiveIdTypeOps<K> getKeyTypeOps() {
470       throw new UnsupportedOperationException();
471     }
472 
473     @Override
474     public Iterator<K> fastKeyIterator() {
475       return map.keySet().iterator();
476     }
477 
478     @Override
479     public Iterator<V> valueIterator() {
480       return map.values().iterator();
481     }
482 
483     @Override
484     public Collection<V> values() {
485       return map.values();
486     }
487 
488     @Override
489     public void write(DataOutput out) throws IOException {
490       Preconditions.checkState(
491         keyWriter != null,
492         "keyWriter is not provided"
493       );
494       Preconditions.checkState(
495         valueWriter != null,
496         "valueWriter is not provided"
497       );
498 
499       out.writeInt(map.size());
500       ObjectIterator<Object2ObjectMap.Entry<K, V>> iterator =
501           map.object2ObjectEntrySet().fastIterator();
502       while (iterator.hasNext()) {
503         Object2ObjectMap.Entry<K, V> entry = iterator.next();
504         keyWriter.write(out, entry.getKey());
505         valueWriter.write(out, entry.getValue());
506       }
507     }
508 
509     @Override
510     public void readFields(DataInput in) throws IOException {
511       Preconditions.checkState(
512         keyWriter != null,
513         "keyWriter is not provided"
514       );
515       Preconditions.checkState(
516         valueWriter != null,
517         "valueWriter is not provided"
518       );
519 
520       int size = in.readInt();
521       map.clear();
522       map.trim(size);
523       while (size-- > 0) {
524         K key = keyWriter.readFields(in);
525         V value = valueWriter.readFields(in);
526         map.put(key, value);
527       }
528     }
529   }
530 }