1/*2 * Licensed to the Apache Software Foundation (ASF) under one3 * or more contributor license agreements. See the NOTICE file4 * distributed with this work for additional information5 * regarding copyright ownership. The ASF licenses this file6 * to you under the Apache License, Version 2.0 (the7 * "License"); you may not use this file except in compliance8 * with the License. You may obtain a copy of the License at9 *10 * http://www.apache.org/licenses/LICENSE-2.011 *12 * Unless required by applicable law or agreed to in writing, software13 * 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 and16 * limitations under the License.17 */1819package org.apache.giraph.edge;
2021import it.unimi.dsi.fastutil.doubles.DoubleArrayList;
22import it.unimi.dsi.fastutil.doubles.DoubleIterator;
23import it.unimi.dsi.fastutil.longs.LongArrayList;
24import it.unimi.dsi.fastutil.longs.LongIterator;
2526import java.io.DataInput;
27import java.io.DataOutput;
28import java.io.IOException;
29import java.util.Iterator;
3031import org.apache.giraph.utils.EdgeIterables;
32import org.apache.giraph.utils.Trimmable;
33import org.apache.hadoop.io.DoubleWritable;
34import org.apache.hadoop.io.LongWritable;
3536import com.google.common.collect.UnmodifiableIterator;
3738/**39 * Implementation of {@link OutEdges} with long ids and double edge40 * 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 */45publicclassLongDoubleArrayEdges46implements ReuseObjectsOutEdges<LongWritable, DoubleWritable>,
47 MutableOutEdges<LongWritable, DoubleWritable>, Trimmable {
48/** Array of target vertex ids. */49private LongArrayList neighbors;
50/** Array of edge values. */51private DoubleArrayList edgeValues;
5253 @Override
54publicvoid initialize(Iterable<Edge<LongWritable, DoubleWritable>> edges) {
55 EdgeIterables.initialize(this, edges);
56 }
5758 @Override
59publicvoid initialize(int capacity) {
60 neighbors = new LongArrayList(capacity);
61 edgeValues = new DoubleArrayList(capacity);
62 }
6364 @Override
65publicvoid initialize() {
66 neighbors = new LongArrayList();
67 edgeValues = new DoubleArrayList();
68 }
6970 @Override
71publicvoid add(Edge<LongWritable, DoubleWritable> edge) {
72 neighbors.add(edge.getTargetVertexId().get());
73 edgeValues.add(edge.getValue().get());
74 }
7576/**77 * If the backing arrays are more than four times as big as the number of78 * elements, halve their size.79 */80privatevoid trimBack() {
81if (neighbors.elements().length > 4 * neighbors.size()) {
82 neighbors.trim(neighbors.elements().length / 2);
83 edgeValues.trim(neighbors.elements().length / 2);
84 }
85 }
8687/**88 * Remove edge at position i.89 *90 * @param i Position of edge to be removed91 */92privatevoid removeAt(int i) {
93// The order of the edges is irrelevant, so we can simply replace94// the deleted edge with the rightmost element, thus achieving constant95// time.96if (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 }
106107 @Override
108publicvoid remove(LongWritable targetVertexId) {
109// Thanks to the constant-time implementation of removeAt(int),110// we can remove all matching edges in linear time.111for (int i = neighbors.size() - 1; i >= 0; --i) {
112if (neighbors.getLong(i) == targetVertexId.get()) {
113 removeAt(i);
114 }
115 }
116 }
117118 @Override
119publicint size() {
120return neighbors.size();
121 }
122123 @Override
124public Iterator<Edge<LongWritable, DoubleWritable>> iterator() {
125// Returns an iterator that reuses objects.126returnnew UnmodifiableIterator<Edge<LongWritable, DoubleWritable>>() {
127/** Wrapped neighbors iterator. */128privatefinal LongIterator neighborsIt = neighbors.iterator();
129/** Wrapped edge values iterator. */130privatefinal DoubleIterator edgeValuesIt = edgeValues.iterator();
131/** Representative edge object. */132privatefinal Edge<LongWritable, DoubleWritable> representativeEdge =
133 EdgeFactory.create(new LongWritable(), new DoubleWritable());
134135 @Override
136publicboolean hasNext() {
137return neighborsIt.hasNext();
138 }
139140 @Override
141public Edge<LongWritable, DoubleWritable> next() {
142 representativeEdge.getTargetVertexId().set(neighborsIt.nextLong());
143 representativeEdge.getValue().set(edgeValuesIt.nextDouble());
144return representativeEdge;
145 }
146 };
147 }
148149/** Helper class for a mutable edge that modifies the backing arrays. */150privateclassLongDoubleArrayMutableEdge151extends DefaultEdge<LongWritable, DoubleWritable> {
152/** Index of the edge in the backing arrays. */153privateint index;
154155/** Constructor. */156publicLongDoubleArrayMutableEdge() {
157super(new LongWritable(), new DoubleWritable());
158 }
159160/**161 * Make the edge point to the given index in the backing arrays.162 *163 * @param index Index in the arrays164 */165publicvoid 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.170this.index = index;
171 }
172173 @Override
174publicvoid 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 }
181182 @Override
183public Iterator<MutableEdge<LongWritable, DoubleWritable>>
184 mutableIterator() {
185returnnew Iterator<MutableEdge<LongWritable, DoubleWritable>>() {
186/** Current position in the array. */187privateint offset = 0;
188/** Representative edge object. */189privatefinalLongDoubleArrayMutableEdge representativeEdge =
190newLongDoubleArrayMutableEdge();
191192 @Override
193publicboolean hasNext() {
194return offset < neighbors.size();
195 }
196197 @Override
198public MutableEdge<LongWritable, DoubleWritable> next() {
199 representativeEdge.setIndex(offset++);
200return representativeEdge;
201 }
202203 @Override
204publicvoid remove() {
205// Since removeAt() might replace the deleted edge with the last edge206// in the array, we need to decrease the offset so that the latter207// won't be skipped.208 removeAt(--offset);
209 }
210 };
211 }
212213 @Override
214publicvoid write(DataOutput out) throws IOException {
215 out.writeInt(neighbors.size());
216 LongIterator neighborsIt = neighbors.iterator();
217 DoubleIterator edgeValuesIt = edgeValues.iterator();
218while (neighborsIt.hasNext()) {
219 out.writeLong(neighborsIt.nextLong());
220 out.writeDouble(edgeValuesIt.nextDouble());
221 }
222 }
223224 @Override
225publicvoid readFields(DataInput in) throws IOException {
226int numEdges = in.readInt();
227 initialize(numEdges);
228for (int i = 0; i < numEdges; ++i) {
229 neighbors.add(in.readLong());
230 edgeValues.add(in.readDouble());
231 }
232 }
233234 @Override
235publicvoid trim() {
236 neighbors.trim();
237 edgeValues.trim();
238 }
239 }