View Javadoc

1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one
3    * or more contributor license agreements.  See the NOTICE file
4    * distributed with this work for additional information
5    * regarding copyright ownership.  The ASF licenses this file
6    * to you under the Apache License, Version 2.0 (the
7    * "License"); you may not use this file except in compliance
8    * with the License.  You may obtain a copy of the License at
9    *
10   *     http://www.apache.org/licenses/LICENSE-2.0
11   *
12   * Unless required by applicable law or agreed to in writing, software
13   * 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 and
16   * limitations under the License.
17   */
18  
19  package org.apache.giraph.edge;
20  
21  import it.unimi.dsi.fastutil.ints.IntArrayList;
22  import it.unimi.dsi.fastutil.ints.IntIterator;
23  
24  import java.io.DataInput;
25  import java.io.DataOutput;
26  import java.io.IOException;
27  import java.util.Iterator;
28  
29  import org.apache.giraph.utils.EdgeIterables;
30  import org.apache.giraph.utils.Trimmable;
31  import org.apache.hadoop.io.IntWritable;
32  import org.apache.hadoop.io.NullWritable;
33  
34  import com.google.common.collect.UnmodifiableIterator;
35  
36  /**
37   * Implementation of {@link OutEdges} with int ids and null edge
38   * 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   */
43  public class IntNullArrayEdges
44      implements ReuseObjectsOutEdges<IntWritable, NullWritable>, Trimmable {
45    /** Array of target vertex ids */
46    private IntArrayList neighbors;
47  
48    @Override
49    public void initialize(Iterable<Edge<IntWritable, NullWritable>> edges) {
50      EdgeIterables.initialize(this, edges);
51    }
52  
53    @Override
54    public void initialize(int capacity) {
55      neighbors = new IntArrayList(capacity);
56    }
57  
58    @Override
59    public void initialize() {
60      neighbors = new IntArrayList();
61    }
62  
63    @Override
64    public int size() {
65      return neighbors.size();
66    }
67  
68    @Override
69    public void add(Edge<IntWritable, NullWritable> edge) {
70      neighbors.add(edge.getTargetVertexId().get());
71    }
72  
73    /**
74     * Remove edge at position i.
75     *
76     * @param i Position of edge to be removed
77     */
78    private void removeAt(int i) {
79      // The order of the edges is irrelevant, so we can simply replace
80      // the deleted edge with the rightmost element, thus achieving constant
81      // time.
82      if (i == neighbors.size() - 1) {
83        neighbors.popInt();
84      } else {
85        neighbors.set(i, neighbors.popInt());
86      }
87    }
88  
89    @Override
90    public void remove(IntWritable targetVertexId) {
91      // Thanks to the constant-time implementation of removeAt(int),
92      // we can remove all matching edges in linear time.
93      for (int i = neighbors.size() - 1; i >= 0; --i) {
94        if (neighbors.getInt(i) == targetVertexId.get()) {
95          removeAt(i);
96        }
97      }
98    }
99  
100   @Override
101   public Iterator<Edge<IntWritable, NullWritable>> iterator() {
102     // Returns an iterator that reuses objects.
103     return new UnmodifiableIterator<Edge<IntWritable, NullWritable>>() {
104       /** Wrapped neighbors iterator. */
105       private final IntIterator neighborsIt = neighbors.iterator();
106       /** Representative edge object. */
107       private final Edge<IntWritable, NullWritable> representativeEdge =
108           EdgeFactory.create(new IntWritable(), NullWritable.get());
109 
110       @Override
111       public boolean hasNext() {
112         return neighborsIt.hasNext();
113       }
114 
115       @Override
116       public Edge<IntWritable, NullWritable> next() {
117         representativeEdge.getTargetVertexId().set(neighborsIt.nextInt());
118         return representativeEdge;
119       }
120     };
121   }
122 
123   @Override
124   public void write(DataOutput out) throws IOException {
125     out.writeInt(neighbors.size());
126     IntIterator iterator = neighbors.iterator();
127     while (iterator.hasNext()) {
128       out.writeInt(iterator.nextInt());
129     }
130   }
131 
132   @Override
133   public void readFields(DataInput in) throws IOException {
134     int numEdges = in.readInt();
135     initialize(numEdges);
136     for (int i = 0; i < numEdges; ++i) {
137       neighbors.add(in.readInt());
138     }
139   }
140 
141   @Override
142   public void trim() {
143     neighbors.trim();
144   }
145 }