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 */18package org.apache.giraph.edge;
1920import java.io.DataInput;
21import java.io.DataOutput;
22import java.io.IOException;
23import java.util.Iterator;
24import java.util.NoSuchElementException;
2526import org.apache.giraph.conf.ImmutableClassesGiraphConfigurable;
27import org.apache.giraph.conf.ImmutableClassesGiraphConfiguration;
28import org.apache.giraph.types.ops.PrimitiveIdTypeOps;
29import org.apache.giraph.types.ops.PrimitiveTypeOps;
30import org.apache.giraph.types.ops.TypeOpsUtils;
31import org.apache.giraph.types.ops.collections.array.WArrayList;
32import org.apache.giraph.utils.EdgeIterables;
33import org.apache.hadoop.io.Writable;
34import org.apache.hadoop.io.WritableComparable;
3536import com.google.common.collect.UnmodifiableIterator;
3738/**39 * Implementation of {@link OutEdges} with IDs and Edge values having their40 * TypeOps.41 * Data is backed by a dynamic primitive array. Parallel edges are allowed.42 * Note: this implementation is optimized for space usage, but random access43 * and edge removals are expensive.44 *45 * @param <I> Vertex id type46 * @param <E> Edge value type47 */48publicclass IdAndValueArrayEdges<I extends WritableComparable,
49 E extends Writable> implements ReuseObjectsOutEdges<I, E>,
50 MutableOutEdges<I, E>,
51 ImmutableClassesGiraphConfigurable<I, Writable, E> {
5253/** Array of target vertex ids. */54private WArrayList<I> neighborIds;
55/** Array of edge values. */56private WArrayList<E> neighborEdgeValues;
5758 @Override
59public ImmutableClassesGiraphConfiguration<I, Writable, E> getConf() {
60thrownew UnsupportedOperationException();
61 }
6263 @Override
64publicvoid setConf(
65 ImmutableClassesGiraphConfiguration<I, Writable, E> conf) {
66 PrimitiveIdTypeOps<I> idTypeOps =
67 TypeOpsUtils.getPrimitiveIdTypeOps(conf.getVertexIdClass());
68 neighborIds = idTypeOps.createArrayList(10);
6970 PrimitiveTypeOps<E> edgeTypeOps =
71 TypeOpsUtils.getPrimitiveTypeOps(conf.getEdgeValueClass());
72 neighborEdgeValues = edgeTypeOps.createArrayList(10);
73 }
7475 @Override
76publicvoid initialize(Iterable<Edge<I, E>> edges) {
77 EdgeIterables.initialize(this, edges);
78 }
7980 @Override
81publicvoid initialize(int capacity) {
82 neighborIds.clear();
83 neighborIds.setCapacity(capacity);
84 neighborEdgeValues.clear();
85 neighborEdgeValues.setCapacity(capacity);
86 }
8788 @Override
89publicvoid initialize() {
90 initialize(10);
91 }
9293 @Override
94publicvoid add(Edge<I, E> edge) {
95 neighborIds.addW(edge.getTargetVertexId());
96 neighborEdgeValues.addW(edge.getValue());
97 }
9899/**100 * If the backing array is more than four times as big as the number of101 * elements, reduce to 2 times current size.102 */103privatevoid trim() {
104if (neighborIds.capacity() > 4 * neighborIds.size()) {
105 neighborIds.setCapacity(neighborIds.size() * 2);
106 neighborEdgeValues.setCapacity(neighborIds.size() * 2);
107 }
108 }
109110/**111 * Remove edge at position i.112 *113 * @param i Position of edge to be removed114 */115privatevoid removeAt(int i) {
116// The order of the edges is irrelevant, so we can simply replace117// the deleted edge with the rightmost element, thus achieving constant118// time.119 I tmpId = neighborIds.getElementTypeOps().create();
120 E tmpValue = neighborEdgeValues.getElementTypeOps().create();
121122 neighborIds.popIntoW(tmpId);
123 neighborEdgeValues.popIntoW(tmpValue);
124if (i != neighborIds.size()) {
125 neighborIds.setW(i, tmpId);
126 neighborEdgeValues.setW(i, tmpValue);
127 }
128// If needed after the removal, trim the array.129 trim();
130 }
131132 @Override
133publicvoid remove(I targetVertexId) {
134// Thanks to the constant-time implementation of removeAt(int),135// we can remove all matching edges in linear time.136 I tmpId = neighborIds.getElementTypeOps().create();
137for (int i = neighborIds.size() - 1; i >= 0; --i) {
138 neighborIds.getIntoW(i, tmpId);
139if (tmpId.equals(targetVertexId)) {
140 removeAt(i);
141 }
142 }
143 }
144145 @Override
146publicint size() {
147return neighborIds.size();
148 }
149150 @Override
151public Iterator<Edge<I, E>> iterator() {
152// Returns an iterator that reuses objects.153returnnew UnmodifiableIterator<Edge<I, E>>() {
154privateint index;
155156/** Representative edge object. */157privatefinal Edge<I, E> representativeEdge = EdgeFactory.create(
158 neighborIds.getElementTypeOps().create(),
159 neighborEdgeValues.getElementTypeOps().create());
160161 @Override
162publicboolean hasNext() {
163return index < neighborIds.size();
164 }
165166 @Override
167public Edge<I, E> next() {
168if (!hasNext()) {
169thrownew NoSuchElementException();
170 }
171 neighborIds.getIntoW(index, representativeEdge.getTargetVertexId());
172 neighborEdgeValues.getIntoW(index, representativeEdge.getValue());
173 index++;
174return representativeEdge;
175 }
176 };
177 }
178179/** Helper class for a mutable edge that modifies the backing arrays. */180privateclassArrayMutableEdgeextends DefaultEdge<I, E> {
181/** Index of the edge in the backing arrays. */182privateint index;
183184/** Constructor. */185publicArrayMutableEdge() {
186super(
187 neighborIds.getElementTypeOps().create(),
188 neighborEdgeValues.getElementTypeOps().create());
189 }
190191/**192 * Make the edge point to the given index in the backing arrays.193 *194 * @param index Index in the arrays195 */196publicvoid setIndex(int index) {
197// Update the id and value objects from the superclass.198 neighborIds.getIntoW(index, getTargetVertexId());
199 neighborEdgeValues.getIntoW(index, getValue());
200// Update the index.201this.index = index;
202 }
203204 @Override
205publicvoid setValue(E value) {
206// Update the value object from the superclass.207 neighborEdgeValues.getElementTypeOps().set(getValue(), value);
208// Update the value stored in the backing array.209 neighborEdgeValues.setW(index, value);
210 }
211 }
212213 @Override
214public Iterator<MutableEdge<I, E>> mutableIterator() {
215returnnew Iterator<MutableEdge<I, E>>() {
216/** Current position in the array. */217privateint index = 0;
218/** Representative edge object. */219privatefinalArrayMutableEdge representativeEdge =
220newArrayMutableEdge();
221222 @Override
223publicboolean hasNext() {
224return index < neighborIds.size();
225 }
226227 @Override
228public MutableEdge<I, E> next() {
229if (!hasNext()) {
230thrownew NoSuchElementException();
231 }
232 representativeEdge.setIndex(index++);
233return representativeEdge;
234 }
235236 @Override
237publicvoid remove() {
238// Since removeAt() might replace the deleted edge with the last edge239// in the array, we need to decrease the offset so that the latter240// won't be skipped.241 removeAt(--index);
242 }
243 };
244 }
245246 @Override
247publicvoid write(DataOutput out) throws IOException {
248 neighborIds.write(out);
249 neighborEdgeValues.write(out);
250 }
251252 @Override
253publicvoid readFields(DataInput in) throws IOException {
254 neighborIds.readFields(in);
255 neighborEdgeValues.readFields(in);
256 }
257 }