This project has retired. For details please refer to its Attic page.
LongDoubleArrayEdges 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.doubles.DoubleArrayList;
22  import it.unimi.dsi.fastutil.doubles.DoubleIterator;
23  import it.unimi.dsi.fastutil.longs.LongArrayList;
24  import it.unimi.dsi.fastutil.longs.LongIterator;
25  
26  import java.io.DataInput;
27  import java.io.DataOutput;
28  import java.io.IOException;
29  import java.util.Iterator;
30  
31  import org.apache.giraph.utils.EdgeIterables;
32  import org.apache.giraph.utils.Trimmable;
33  import org.apache.hadoop.io.DoubleWritable;
34  import org.apache.hadoop.io.LongWritable;
35  
36  import com.google.common.collect.UnmodifiableIterator;
37  
38  /**
39   * Implementation of {@link OutEdges} with long ids and double edge
40   * values, backed by dynamic primitive arrays.
41   * Parallel edges are allowed.
42   * Note: this implementation is optimized for space usage,
43   * but edge removals are expensive.
44   */
45  public class LongDoubleArrayEdges
46      implements ReuseObjectsOutEdges<LongWritable, DoubleWritable>,
47      MutableOutEdges<LongWritable, DoubleWritable>, Trimmable {
48    /** Array of target vertex ids. */
49    private LongArrayList neighbors;
50    /** Array of edge values. */
51    private DoubleArrayList edgeValues;
52  
53    @Override
54    public void initialize(Iterable<Edge<LongWritable, DoubleWritable>> edges) {
55      EdgeIterables.initialize(this, edges);
56    }
57  
58    @Override
59    public void initialize(int capacity) {
60      neighbors = new LongArrayList(capacity);
61      edgeValues = new DoubleArrayList(capacity);
62    }
63  
64    @Override
65    public void initialize() {
66      neighbors = new LongArrayList();
67      edgeValues = new DoubleArrayList();
68    }
69  
70    @Override
71    public void add(Edge<LongWritable, DoubleWritable> edge) {
72      neighbors.add(edge.getTargetVertexId().get());
73      edgeValues.add(edge.getValue().get());
74    }
75  
76    /**
77     * If the backing arrays are more than four times as big as the number of
78     * elements, halve their size.
79     */
80    private void trimBack() {
81      if (neighbors.elements().length > 4 * neighbors.size()) {
82        neighbors.trim(neighbors.elements().length / 2);
83        edgeValues.trim(neighbors.elements().length / 2);
84      }
85    }
86  
87    /**
88     * Remove edge at position i.
89     *
90     * @param i Position of edge to be removed
91     */
92    private void removeAt(int i) {
93      // The order of the edges is irrelevant, so we can simply replace
94      // the deleted edge with the rightmost element, thus achieving constant
95      // time.
96      if (i == neighbors.size() - 1) {
97        neighbors.popLong();
98        edgeValues.popDouble();
99      } else {
100       neighbors.set(i, neighbors.popLong());
101       edgeValues.set(i, edgeValues.popDouble());
102     }
103     // If needed after the removal, trim the arrays.
104     trimBack();
105   }
106 
107   @Override
108   public void remove(LongWritable targetVertexId) {
109     // Thanks to the constant-time implementation of removeAt(int),
110     // we can remove all matching edges in linear time.
111     for (int i = neighbors.size() - 1; i >= 0; --i) {
112       if (neighbors.getLong(i) == targetVertexId.get()) {
113         removeAt(i);
114       }
115     }
116   }
117 
118   @Override
119   public int size() {
120     return neighbors.size();
121   }
122 
123   @Override
124   public Iterator<Edge<LongWritable, DoubleWritable>> iterator() {
125     // Returns an iterator that reuses objects.
126     return new UnmodifiableIterator<Edge<LongWritable, DoubleWritable>>() {
127       /** Wrapped neighbors iterator. */
128       private final LongIterator neighborsIt = neighbors.iterator();
129       /** Wrapped edge values iterator. */
130       private final DoubleIterator edgeValuesIt = edgeValues.iterator();
131       /** Representative edge object. */
132       private final Edge<LongWritable, DoubleWritable> representativeEdge =
133           EdgeFactory.create(new LongWritable(), new DoubleWritable());
134 
135       @Override
136       public boolean hasNext() {
137         return neighborsIt.hasNext();
138       }
139 
140       @Override
141       public Edge<LongWritable, DoubleWritable> next() {
142         representativeEdge.getTargetVertexId().set(neighborsIt.nextLong());
143         representativeEdge.getValue().set(edgeValuesIt.nextDouble());
144         return representativeEdge;
145       }
146     };
147   }
148 
149   /** Helper class for a mutable edge that modifies the backing arrays. */
150   private class LongDoubleArrayMutableEdge
151       extends DefaultEdge<LongWritable, DoubleWritable> {
152     /** Index of the edge in the backing arrays. */
153     private int index;
154 
155     /** Constructor. */
156     public LongDoubleArrayMutableEdge() {
157       super(new LongWritable(), new DoubleWritable());
158     }
159 
160     /**
161      * Make the edge point to the given index in the backing arrays.
162      *
163      * @param index Index in the arrays
164      */
165     public void setIndex(int index) {
166       // Update the id and value objects from the superclass.
167       getTargetVertexId().set(neighbors.getLong(index));
168       getValue().set(edgeValues.getDouble(index));
169       // Update the index.
170       this.index = index;
171     }
172 
173     @Override
174     public void setValue(DoubleWritable value) {
175       // Update the value object from the superclass.
176       getValue().set(value.get());
177       // Update the value stored in the backing array.
178       edgeValues.set(index, value.get());
179     }
180   }
181 
182   @Override
183   public Iterator<MutableEdge<LongWritable, DoubleWritable>>
184   mutableIterator() {
185     return new Iterator<MutableEdge<LongWritable, DoubleWritable>>() {
186       /** Current position in the array. */
187       private int offset = 0;
188       /** Representative edge object. */
189       private final LongDoubleArrayMutableEdge representativeEdge =
190           new LongDoubleArrayMutableEdge();
191 
192       @Override
193       public boolean hasNext() {
194         return offset < neighbors.size();
195       }
196 
197       @Override
198       public MutableEdge<LongWritable, DoubleWritable> next() {
199         representativeEdge.setIndex(offset++);
200         return representativeEdge;
201       }
202 
203       @Override
204       public void remove() {
205         // Since removeAt() might replace the deleted edge with the last edge
206         // in the array, we need to decrease the offset so that the latter
207         // won't be skipped.
208         removeAt(--offset);
209       }
210     };
211   }
212 
213   @Override
214   public void write(DataOutput out) throws IOException {
215     out.writeInt(neighbors.size());
216     LongIterator neighborsIt = neighbors.iterator();
217     DoubleIterator edgeValuesIt = edgeValues.iterator();
218     while (neighborsIt.hasNext()) {
219       out.writeLong(neighborsIt.nextLong());
220       out.writeDouble(edgeValuesIt.nextDouble());
221     }
222   }
223 
224   @Override
225   public void readFields(DataInput in) throws IOException {
226     int numEdges = in.readInt();
227     initialize(numEdges);
228     for (int i = 0; i < numEdges; ++i) {
229       neighbors.add(in.readLong());
230       edgeValues.add(in.readDouble());
231     }
232   }
233 
234   @Override
235   public void trim() {
236     neighbors.trim();
237     edgeValues.trim();
238   }
239 }