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.TypeOpsUtils;
30import org.apache.giraph.types.ops.collections.array.WArrayList;
31import org.apache.giraph.utils.EdgeIterables;
32import org.apache.hadoop.io.NullWritable;
33import org.apache.hadoop.io.Writable;
34import org.apache.hadoop.io.WritableComparable;
3536/**37 * Implementation of {@link OutEdges} with IDs and null edge values having38 * their TypeOps.39 * Backed by a dynamic primitive array. Parallel edges are allowed.40 * Note: this implementation is optimized for space41 * usage, but random access and edge removals are expensive.42 *43 * @param <I> Vertex id type44 */45publicclass IdAndNullArrayEdges<I extends WritableComparable>
46implements ReuseObjectsOutEdges<I, NullWritable>,
47 MutableOutEdges<I, NullWritable>,
48 ImmutableClassesGiraphConfigurable<I, Writable, NullWritable> {
4950/** Array of target vertex ids. */51private WArrayList<I> neighbors;
5253 @Override
54public55 ImmutableClassesGiraphConfiguration<I, Writable, NullWritable> getConf() {
56thrownew UnsupportedOperationException();
57 }
5859 @Override
60publicvoid setConf(
61 ImmutableClassesGiraphConfiguration<I, Writable, NullWritable> conf) {
62 PrimitiveIdTypeOps<I> idTypeOps =
63 TypeOpsUtils.getPrimitiveIdTypeOps(conf.getVertexIdClass());
64 neighbors = idTypeOps.createArrayList(10);
65if (!conf.getEdgeValueClass().equals(NullWritable.class)) {
66thrownew IllegalArgumentException(
67"IdAndNullArrayEdges can be used only with NullWritable " +
68"as edgeValueClass, not with " + conf.getEdgeValueClass());
69 }
70 }
7172 @Override
73publicvoid initialize(Iterable<Edge<I, NullWritable>> edges) {
74 EdgeIterables.initialize(this, edges);
75 }
7677 @Override
78publicvoid initialize(int capacity) {
79 neighbors.clear();
80 neighbors.setCapacity(capacity);
81 }
8283 @Override
84publicvoid initialize() {
85 initialize(10);
86 }
8788 @Override
89publicvoid add(Edge<I, NullWritable> edge) {
90 neighbors.addW(edge.getTargetVertexId());
91 }
9293/**94 * If the backing array is more than four times as big as the number of95 * elements, reduce to 2 times current size.96 */97privatevoid trim() {
98if (neighbors.capacity() > 4 * neighbors.size()) {
99 neighbors.setCapacity(neighbors.size() * 2);
100 }
101 }
102103/**104 * Remove edge at position i.105 *106 * @param i Position of edge to be removed107 */108privatevoid removeAt(int i) {
109// The order of the edges is irrelevant, so we can simply replace110// the deleted edge with the rightmost element, thus achieving constant111// time.112 I tmpValue = neighbors.getElementTypeOps().create();
113 neighbors.popIntoW(tmpValue);
114if (i != neighbors.size()) {
115 neighbors.setW(i, tmpValue);
116 }
117// If needed after the removal, trim the array.118 trim();
119 }
120121 @Override
122publicvoid remove(I targetVertexId) {
123// Thanks to the constant-time implementation of removeAt(int),124// we can remove all matching edges in linear time.125 I tmpValue = neighbors.getElementTypeOps().create();
126for (int i = neighbors.size() - 1; i >= 0; --i) {
127 neighbors.getIntoW(i, tmpValue);
128if (tmpValue.equals(targetVertexId)) {
129 removeAt(i);
130 }
131 }
132 }
133134 @Override
135publicint size() {
136return neighbors.size();
137 }
138139 @Override
140public Iterator<Edge<I, NullWritable>> iterator() {
141// Returns an iterator that reuses objects.142// The downcast is fine because all concrete Edge implementations are143// mutable, but we only expose the mutation functionality when appropriate.144return (Iterator) mutableIterator();
145 }
146147 @Override
148public Iterator<MutableEdge<I, NullWritable>> mutableIterator() {
149returnnew Iterator<MutableEdge<I, NullWritable>>() {
150/** Current position in the array. */151privateint offset = 0;
152/** Representative edge object. */153privatefinal MutableEdge<I, NullWritable> representativeEdge =
154 EdgeFactory.createReusable(neighbors.getElementTypeOps().create());
155156 @Override
157publicboolean hasNext() {
158return offset < neighbors.size();
159 }
160161 @Override
162public MutableEdge<I, NullWritable> next() {
163if (!hasNext()) {
164thrownew NoSuchElementException();
165 }
166 neighbors.getIntoW(offset++, representativeEdge.getTargetVertexId());
167return representativeEdge;
168 }
169170 @Override
171publicvoid remove() {
172// Since removeAt() might replace the deleted edge with the last edge173// in the array, we need to decrease the offset so that the latter174// won't be skipped.175 removeAt(--offset);
176 }
177 };
178 }
179180 @Override
181publicvoid write(DataOutput out) throws IOException {
182 neighbors.write(out);
183 }
184185 @Override
186publicvoid readFields(DataInput in) throws IOException {
187 neighbors.readFields(in);
188 }
189 }