This project has retired. For details please refer to its Attic page.
LongDoubleHashMapEdges 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  
19  package org.apache.giraph.edge;
20  
21  import it.unimi.dsi.fastutil.longs.Long2DoubleMap;
22  import it.unimi.dsi.fastutil.longs.Long2DoubleOpenHashMap;
23  import it.unimi.dsi.fastutil.objects.ObjectIterator;
24  
25  import java.io.DataInput;
26  import java.io.DataOutput;
27  import java.io.IOException;
28  import java.util.Iterator;
29  
30  import org.apache.giraph.utils.EdgeIterables;
31  import org.apache.giraph.utils.Trimmable;
32  import org.apache.hadoop.io.DoubleWritable;
33  import org.apache.hadoop.io.LongWritable;
34  
35  import com.google.common.collect.UnmodifiableIterator;
36  
37  /**
38   * {@link OutEdges} implementation with long ids and double edge values,
39   * backed by a {@link Long2DoubleOpenHashMap}.
40   * Parallel edges are not allowed.
41   * Note: this implementation is optimized for fast random access and mutations,
42   * and uses less space than a generic {@link HashMapEdges} (but more than
43   * {@link LongDoubleArrayEdges}.
44   */
45  public class LongDoubleHashMapEdges
46      implements StrictRandomAccessOutEdges<LongWritable, DoubleWritable>,
47      ReuseObjectsOutEdges<LongWritable, DoubleWritable>,
48      MutableOutEdges<LongWritable, DoubleWritable>, Trimmable {
49    /** Hash map from target vertex id to edge value. */
50    private Long2DoubleOpenHashMap edgeMap;
51    /** Representative edge value object, used by getEdgeValue(). */
52    private DoubleWritable representativeEdgeValue;
53  
54    @Override
55    public void initialize(Iterable<Edge<LongWritable, DoubleWritable>> edges) {
56      EdgeIterables.initialize(this, edges);
57    }
58  
59    @Override
60    public void initialize(int capacity) {
61      edgeMap = new Long2DoubleOpenHashMap(capacity);
62    }
63  
64    @Override
65    public void initialize() {
66      edgeMap = new Long2DoubleOpenHashMap();
67    }
68  
69    @Override
70    public void add(Edge<LongWritable, DoubleWritable> edge) {
71      edgeMap.put(edge.getTargetVertexId().get(), edge.getValue().get());
72    }
73  
74    @Override
75    public void remove(LongWritable targetVertexId) {
76      edgeMap.remove(targetVertexId.get());
77    }
78  
79    @Override
80    public DoubleWritable getEdgeValue(LongWritable targetVertexId) {
81      if (!edgeMap.containsKey(targetVertexId.get())) {
82        return null;
83      }
84      if (representativeEdgeValue == null) {
85        representativeEdgeValue = new DoubleWritable();
86      }
87      representativeEdgeValue.set(edgeMap.get(targetVertexId.get()));
88      return representativeEdgeValue;
89    }
90  
91    @Override
92    public void setEdgeValue(LongWritable targetVertexId,
93                             DoubleWritable edgeValue) {
94      if (edgeMap.containsKey(targetVertexId.get())) {
95        edgeMap.put(targetVertexId.get(), edgeValue.get());
96      }
97    }
98  
99    @Override
100   public int size() {
101     return edgeMap.size();
102   }
103 
104   @Override
105   public Iterator<Edge<LongWritable, DoubleWritable>> iterator() {
106     // Returns an iterator that reuses objects.
107     return new UnmodifiableIterator<Edge<LongWritable, DoubleWritable>>() {
108       /** Wrapped map iterator. */
109       private final ObjectIterator<Long2DoubleMap.Entry> mapIterator =
110           edgeMap.long2DoubleEntrySet().fastIterator();
111       /** Representative edge object. */
112       private final ReusableEdge<LongWritable, DoubleWritable>
113       representativeEdge =
114           EdgeFactory.createReusable(new LongWritable(), new DoubleWritable());
115 
116       @Override
117       public boolean hasNext() {
118         return mapIterator.hasNext();
119       }
120 
121       @Override
122       public Edge<LongWritable, DoubleWritable> next() {
123         Long2DoubleMap.Entry nextEntry = mapIterator.next();
124         representativeEdge.getTargetVertexId().set(nextEntry.getLongKey());
125         representativeEdge.getValue().set(nextEntry.getDoubleValue());
126         return representativeEdge;
127       }
128     };
129   }
130 
131   @Override
132   public void trim() {
133     edgeMap.trim();
134   }
135 
136   /** Helper class for a mutable edge that modifies the backing map entry. */
137   private static class LongDoubleHashMapMutableEdge
138       extends DefaultEdge<LongWritable, DoubleWritable> {
139     /** Backing entry for the edge in the map. */
140     private Long2DoubleMap.Entry entry;
141 
142     /** Constructor. */
143     public LongDoubleHashMapMutableEdge() {
144       super(new LongWritable(), new DoubleWritable());
145     }
146 
147     /**
148      * Make the edge point to the given entry in the backing map.
149      *
150      * @param entry Backing entry
151      */
152     public void setEntry(Long2DoubleMap.Entry entry) {
153       // Update the id and value objects from the superclass.
154       getTargetVertexId().set(entry.getLongKey());
155       getValue().set(entry.getDoubleValue());
156       // Update the entry.
157       this.entry = entry;
158     }
159 
160     @Override
161     public void setValue(DoubleWritable value) {
162       // Update the value object from the superclass.
163       getValue().set(value.get());
164       // Update the value stored in the backing map.
165       entry.setValue(value.get());
166     }
167   }
168 
169   @Override
170   public Iterator<MutableEdge<LongWritable, DoubleWritable>> mutableIterator() {
171     return new Iterator<MutableEdge<LongWritable, DoubleWritable>>() {
172       /**
173        * Wrapped map iterator.
174        * Note: we cannot use the fast iterator in this case,
175        * because we need to call setValue() on an entry.
176        */
177       private final ObjectIterator<Long2DoubleMap.Entry> mapIterator =
178           edgeMap.long2DoubleEntrySet().iterator();
179       /** Representative edge object. */
180       private final LongDoubleHashMapMutableEdge representativeEdge =
181           new LongDoubleHashMapMutableEdge();
182 
183       @Override
184       public boolean hasNext() {
185         return mapIterator.hasNext();
186       }
187 
188       @Override
189       public MutableEdge<LongWritable, DoubleWritable> next() {
190         representativeEdge.setEntry(mapIterator.next());
191         return representativeEdge;
192       }
193 
194       @Override
195       public void remove() {
196         mapIterator.remove();
197       }
198     };
199   }
200 
201   @Override
202   public void write(DataOutput out) throws IOException {
203     out.writeInt(edgeMap.size());
204     for (Long2DoubleMap.Entry entry : edgeMap.long2DoubleEntrySet()) {
205       out.writeLong(entry.getLongKey());
206       out.writeDouble(entry.getDoubleValue());
207     }
208   }
209 
210   @Override
211   public void readFields(DataInput in) throws IOException {
212     int numEdges = in.readInt();
213     initialize(numEdges);
214     for (int i = 0; i < numEdges; ++i) {
215       edgeMap.put(in.readLong(), in.readDouble());
216     }
217   }
218 }