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.ints.IntArrayList;
22import it.unimi.dsi.fastutil.ints.IntIterator;
2324import java.io.DataInput;
25import java.io.DataOutput;
26import java.io.IOException;
27import java.util.Iterator;
2829import org.apache.giraph.utils.EdgeIterables;
30import org.apache.giraph.utils.Trimmable;
31import org.apache.hadoop.io.IntWritable;
32import org.apache.hadoop.io.NullWritable;
3334import com.google.common.collect.UnmodifiableIterator;
3536/**37 * Implementation of {@link OutEdges} with int ids and null edge38 * values, backed by dynamic primitive array.39 * Parallel edges are allowed.40 * Note: this implementation is optimized for space usage,41 * but edge removals are expensive.42 */43publicclassIntNullArrayEdges44implements ReuseObjectsOutEdges<IntWritable, NullWritable>, Trimmable {
45/** Array of target vertex ids */46private IntArrayList neighbors;
4748 @Override
49publicvoid initialize(Iterable<Edge<IntWritable, NullWritable>> edges) {
50 EdgeIterables.initialize(this, edges);
51 }
5253 @Override
54publicvoid initialize(int capacity) {
55 neighbors = new IntArrayList(capacity);
56 }
5758 @Override
59publicvoid initialize() {
60 neighbors = new IntArrayList();
61 }
6263 @Override
64publicint size() {
65return neighbors.size();
66 }
6768 @Override
69publicvoid add(Edge<IntWritable, NullWritable> edge) {
70 neighbors.add(edge.getTargetVertexId().get());
71 }
7273/**74 * Remove edge at position i.75 *76 * @param i Position of edge to be removed77 */78privatevoid removeAt(int i) {
79// The order of the edges is irrelevant, so we can simply replace80// the deleted edge with the rightmost element, thus achieving constant81// time.82if (i == neighbors.size() - 1) {
83 neighbors.popInt();
84 } else {
85 neighbors.set(i, neighbors.popInt());
86 }
87 }
8889 @Override
90publicvoid remove(IntWritable targetVertexId) {
91// Thanks to the constant-time implementation of removeAt(int),92// we can remove all matching edges in linear time.93for (int i = neighbors.size() - 1; i >= 0; --i) {
94if (neighbors.getInt(i) == targetVertexId.get()) {
95 removeAt(i);
96 }
97 }
98 }
99100 @Override
101public Iterator<Edge<IntWritable, NullWritable>> iterator() {
102// Returns an iterator that reuses objects.103returnnew UnmodifiableIterator<Edge<IntWritable, NullWritable>>() {
104/** Wrapped neighbors iterator. */105privatefinal IntIterator neighborsIt = neighbors.iterator();
106/** Representative edge object. */107privatefinal Edge<IntWritable, NullWritable> representativeEdge =
108 EdgeFactory.create(new IntWritable(), NullWritable.get());
109110 @Override
111publicboolean hasNext() {
112return neighborsIt.hasNext();
113 }
114115 @Override
116public Edge<IntWritable, NullWritable> next() {
117 representativeEdge.getTargetVertexId().set(neighborsIt.nextInt());
118return representativeEdge;
119 }
120 };
121 }
122123 @Override
124publicvoid write(DataOutput out) throws IOException {
125 out.writeInt(neighbors.size());
126 IntIterator iterator = neighbors.iterator();
127while (iterator.hasNext()) {
128 out.writeInt(iterator.nextInt());
129 }
130 }
131132 @Override
133publicvoid readFields(DataInput in) throws IOException {
134int numEdges = in.readInt();
135 initialize(numEdges);
136for (int i = 0; i < numEdges; ++i) {
137 neighbors.add(in.readInt());
138 }
139 }
140141 @Override
142publicvoid trim() {
143 neighbors.trim();
144 }
145 }