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.longs.LongArrayList;
22import it.unimi.dsi.fastutil.longs.LongIterator;
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.LongWritable;
32import org.apache.hadoop.io.NullWritable;
3334/**35 * Implementation of {@link OutEdges} with long ids and null edge36 * values, backed by a dynamic primitive array.37 * Parallel edges are allowed.38 * Note: this implementation is optimized for space usage,39 * but random access and edge removals are expensive.40 */41publicclassLongNullArrayEdges42implements ReuseObjectsOutEdges<LongWritable, NullWritable>,
43 MutableOutEdges<LongWritable, NullWritable>, Trimmable {
44/** Array of target vertex ids. */45private LongArrayList neighbors;
4647 @Override
48publicvoid initialize(Iterable<Edge<LongWritable, NullWritable>> edges) {
49 EdgeIterables.initialize(this, edges);
50 }
5152 @Override
53publicvoid initialize(int capacity) {
54 neighbors = new LongArrayList(capacity);
55 }
5657 @Override
58publicvoid initialize() {
59 neighbors = new LongArrayList();
60 }
6162 @Override
63publicvoid add(Edge<LongWritable, NullWritable> edge) {
64 neighbors.add(edge.getTargetVertexId().get());
65 }
6667/**68 * If the backing array is more than four times as big as the number of69 * elements, halve its size.70 */71privatevoid trimBack() {
72if (neighbors.elements().length > 4 * neighbors.size()) {
73 neighbors.trim(neighbors.elements().length / 2);
74 }
75 }
7677/**78 * Remove edge at position i.79 *80 * @param i Position of edge to be removed81 */82privatevoid removeAt(int i) {
83// The order of the edges is irrelevant, so we can simply replace84// the deleted edge with the rightmost element, thus achieving constant85// time.86if (i == neighbors.size() - 1) {
87 neighbors.popLong();
88 } else {
89 neighbors.set(i, neighbors.popLong());
90 }
91// If needed after the removal, trim the array.92 trimBack();
93 }
9495 @Override
96publicvoid remove(LongWritable targetVertexId) {
97// Thanks to the constant-time implementation of removeAt(int),98// we can remove all matching edges in linear time.99for (int i = neighbors.size() - 1; i >= 0; --i) {
100if (neighbors.getLong(i) == targetVertexId.get()) {
101 removeAt(i);
102 }
103 }
104 }
105106 @Override
107publicint size() {
108return neighbors.size();
109 }
110111 @Override
112public Iterator<Edge<LongWritable, NullWritable>> iterator() {
113// Returns an iterator that reuses objects.114// The downcast is fine because all concrete Edge implementations are115// mutable, but we only expose the mutation functionality when appropriate.116return (Iterator) mutableIterator();
117 }
118119 @Override
120public Iterator<MutableEdge<LongWritable, NullWritable>> mutableIterator() {
121returnnew Iterator<MutableEdge<LongWritable, NullWritable>>() {
122/** Current position in the array. */123privateint offset = 0;
124/** Representative edge object. */125privatefinal MutableEdge<LongWritable, NullWritable> representativeEdge =
126 EdgeFactory.createReusable(new LongWritable());
127128 @Override
129publicboolean hasNext() {
130return offset < neighbors.size();
131 }
132133 @Override
134public MutableEdge<LongWritable, NullWritable> next() {
135 representativeEdge.getTargetVertexId().set(neighbors.getLong(offset++));
136return representativeEdge;
137 }
138139 @Override
140publicvoid remove() {
141// Since removeAt() might replace the deleted edge with the last edge142// in the array, we need to decrease the offset so that the latter143// won't be skipped.144 removeAt(--offset);
145 }
146 };
147 }
148149 @Override
150publicvoid write(DataOutput out) throws IOException {
151 out.writeInt(neighbors.size());
152 LongIterator neighborsIt = neighbors.iterator();
153while (neighborsIt.hasNext()) {
154 out.writeLong(neighborsIt.nextLong());
155 }
156 }
157158 @Override
159publicvoid readFields(DataInput in) throws IOException {
160int numEdges = in.readInt();
161 initialize(numEdges);
162for (int i = 0; i < numEdges; ++i) {
163 neighbors.add(in.readLong());
164 }
165 }
166167 @Override
168publicvoid trim() {
169 neighbors.trim();
170 }
171 }
172