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.ObjectIterator;
27  
28  import java.io.DataInput;
29  import java.io.DataOutput;
30  import java.io.IOException;
31  import java.util.Iterator;
32  
33  import org.apache.giraph.types.ops.IntTypeOps;
34  import org.apache.giraph.types.ops.LongTypeOps;
35  import org.apache.giraph.types.ops.PrimitiveIdTypeOps;
36  import org.apache.hadoop.io.IntWritable;
37  import org.apache.hadoop.io.LongWritable;
38  import org.apache.hadoop.io.Writable;
39  
40  /**
41   * Basic2ObjectMap with only basic set of operations.
42   * All operations that return object T are returning reusable object,
43   * which is modified after calling any other function.
44   *
45   * @param <K> Key type
46   * @param <V> Value type
47   */
48  public abstract class Basic2ObjectMap<K, V> implements Writable {
49    /** Removes all of the elements from this list. */
50    public abstract void clear();
51    /**
52     * Number of elements in this list
53     * @return size
54     */
55    public abstract int size();
56  
57    /**
58     * Checks whether key is present in the map
59     * @param key Key
60     * @return true if present
61     */
62    public abstract boolean containsKey(K key);
63    /**
64     * Adds a pair to the map.
65     *
66     * @param key Key
67     * @param value Value.
68     * @return the old value, or null if no value was present for the given key.
69     */
70    public abstract V put(K key, V value);
71    /**
72     * Get value for a given key
73     * @param key Key
74     * @return Value, or null
75     */
76    public abstract V get(K key);
77    /**
78     * Removes the mapping with the given key.
79     *
80     * @param key Key
81     * @return the old value, or null if no value was present for the given key.
82     */
83    public abstract V remove(K key);
84  
85    /**
86     * TypeOps for type of keys this object holds
87     * @return TypeOps
88     */
89    public abstract PrimitiveIdTypeOps<K> getKeyTypeOps();
90  
91    /**
92     * Fast iterator over keys within this map, which doesn't allocate new
93     * element for each returned element.
94     *
95     * Object returned by next() is only valid until next() is called again,
96     * because it is reused.
97     *
98     * @return Iterator
99     */
100   public abstract Iterator<K> fastKeyIterator();
101 
102   /**
103    * Iterator that reuses key object.
104    *
105    * @param <Iter> Primitive key iterator type
106    */
107   protected abstract class ReusableIterator<Iter extends Iterator<?>>
108       implements ResettableIterator<K> {
109     /** Primitive Key iterator */
110     protected Iter iter;
111     /** Reusable key object */
112     protected final K reusableKey = getKeyTypeOps().create();
113 
114     /**
115      * Constructor
116      * @param iter Primitive Key iterator
117      */
118     public ReusableIterator(Iter iter) {
119       this.iter = iter;
120     }
121 
122     @Override
123     public boolean hasNext() {
124       return iter.hasNext();
125     }
126 
127     @Override
128     public void remove() {
129       iter.remove();
130     }
131   }
132 
133   /** IntWritable implementation of Basic2ObjectMap */
134   public static final class BasicInt2ObjectOpenHashMap<V>
135       extends Basic2ObjectMap<IntWritable, V> {
136     /** Map */
137     private final Int2ObjectOpenHashMap<V> map;
138     /** Value writer */
139     private final WritableWriter<V> valueWriter;
140 
141     /**
142      * Constructor
143      *
144      * @param valueWriter Writer of values
145      */
146     public BasicInt2ObjectOpenHashMap(WritableWriter<V> valueWriter) {
147       this.map = new Int2ObjectOpenHashMap<>();
148       this.valueWriter = valueWriter;
149     }
150 
151     /**
152      * Constructor
153      *
154      * @param capacity Capacity
155      * @param valueWriter Writer of values
156      */
157     public BasicInt2ObjectOpenHashMap(
158         int capacity, WritableWriter<V> valueWriter) {
159       this.map = new Int2ObjectOpenHashMap<>(capacity);
160       this.valueWriter = valueWriter;
161     }
162 
163     @Override
164     public void clear() {
165       map.clear();
166     }
167 
168     @Override
169     public int size() {
170       return map.size();
171     }
172 
173     @Override
174     public boolean containsKey(IntWritable key) {
175       return map.containsKey(key.get());
176     }
177 
178     @Override
179     public V put(IntWritable key, V value) {
180       return map.put(key.get(), value);
181     }
182 
183     @Override
184     public V get(IntWritable key) {
185       return map.get(key.get());
186     }
187 
188     @Override
189     public V remove(IntWritable key) {
190       return map.remove(key.get());
191     }
192 
193     @Override
194     public PrimitiveIdTypeOps<IntWritable> getKeyTypeOps() {
195       return IntTypeOps.INSTANCE;
196     }
197 
198     @Override
199     public Iterator<IntWritable> fastKeyIterator() {
200       return new ReusableIterator<IntIterator>(map.keySet().iterator()) {
201         @Override
202         public IntWritable next() {
203           reusableKey.set(iter.nextInt());
204           return reusableKey;
205         }
206 
207         @Override
208         public void reset() {
209           iter = map.keySet().iterator();
210         }
211       };
212     }
213 
214     @Override
215     public void write(DataOutput out) throws IOException {
216       out.writeInt(map.size());
217       ObjectIterator<Int2ObjectMap.Entry<V>> iterator =
218           map.int2ObjectEntrySet().fastIterator();
219       while (iterator.hasNext()) {
220         Int2ObjectMap.Entry<V> entry = iterator.next();
221         out.writeInt(entry.getIntKey());
222         valueWriter.write(out, entry.getValue());
223       }
224     }
225 
226     @Override
227     public void readFields(DataInput in)
228       throws IOException {
229       int size = in.readInt();
230       map.clear();
231       map.trim(size);
232       while (size-- > 0) {
233         int key = in.readInt();
234         V value = valueWriter.readFields(in);
235         map.put(key, value);
236       }
237     }
238   }
239 
240   /** LongWritable implementation of Basic2ObjectMap */
241   public static final class BasicLong2ObjectOpenHashMap<V>
242       extends Basic2ObjectMap<LongWritable, V> {
243     /** Map */
244     private final Long2ObjectOpenHashMap<V> map;
245     /** Value writer */
246     private final WritableWriter<V> valueWriter;
247 
248     /**
249      * Constructor
250      *
251      * @param valueWriter Writer of values
252      */
253     public BasicLong2ObjectOpenHashMap(WritableWriter<V> valueWriter) {
254       this.map = new Long2ObjectOpenHashMap<>();
255       this.valueWriter = valueWriter;
256     }
257 
258     /**
259      * Constructor
260      *
261      * @param capacity Capacity
262      * @param valueWriter Writer of values
263      */
264     public BasicLong2ObjectOpenHashMap(
265         int capacity, WritableWriter<V> valueWriter) {
266       this.map = new Long2ObjectOpenHashMap<>(capacity);
267       this.valueWriter = valueWriter;
268     }
269 
270     @Override
271     public void clear() {
272       map.clear();
273     }
274 
275     @Override
276     public int size() {
277       return map.size();
278     }
279 
280     @Override
281     public boolean containsKey(LongWritable key) {
282       return map.containsKey(key.get());
283     }
284 
285     @Override
286     public V put(LongWritable key, V value) {
287       return map.put(key.get(), value);
288     }
289 
290     @Override
291     public V get(LongWritable key) {
292       return map.get(key.get());
293     }
294 
295     @Override
296     public V remove(LongWritable key) {
297       return map.remove(key.get());
298     }
299 
300     @Override
301     public PrimitiveIdTypeOps<LongWritable> getKeyTypeOps() {
302       return LongTypeOps.INSTANCE;
303     }
304 
305     @Override
306     public Iterator<LongWritable> fastKeyIterator() {
307       return new ReusableIterator<LongIterator>(map.keySet().iterator()) {
308         @Override
309         public LongWritable next() {
310           reusableKey.set(iter.nextLong());
311           return reusableKey;
312         }
313 
314         @Override
315         public void reset() {
316           iter = map.keySet().iterator();
317         }
318       };
319     }
320 
321     @Override
322     public void write(DataOutput out) throws IOException {
323       out.writeInt(map.size());
324       ObjectIterator<Long2ObjectMap.Entry<V>> iterator =
325           map.long2ObjectEntrySet().fastIterator();
326       while (iterator.hasNext()) {
327         Long2ObjectMap.Entry<V> entry = iterator.next();
328         out.writeLong(entry.getLongKey());
329         valueWriter.write(out, entry.getValue());
330       }
331     }
332 
333     @Override
334     public void readFields(DataInput in) throws IOException {
335       int size = in.readInt();
336       map.clear();
337       map.trim(size);
338       while (size-- > 0) {
339         long key = in.readLong();
340         V value = valueWriter.readFields(in);
341         map.put(key, value);
342       }
343     }
344   }
345 }