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  package org.apache.giraph.edge;
19  
20  import java.io.DataInput;
21  import java.io.DataOutput;
22  import java.io.IOException;
23  import java.util.Iterator;
24  
25  import org.apache.giraph.conf.ImmutableClassesGiraphConfigurable;
26  import org.apache.giraph.conf.ImmutableClassesGiraphConfiguration;
27  import org.apache.giraph.types.ops.PrimitiveIdTypeOps;
28  import org.apache.giraph.types.ops.TypeOpsUtils;
29  import org.apache.giraph.types.ops.collections.array.WArrayList;
30  import org.apache.giraph.utils.EdgeIterables;
31  import org.apache.hadoop.io.NullWritable;
32  import org.apache.hadoop.io.Writable;
33  import org.apache.hadoop.io.WritableComparable;
34  
35  /**
36   * Implementation of {@link OutEdges} with IDs and null edge values having
37   * their TypeOps.
38   * Backed by a dynamic primitive array. Parallel edges are allowed.
39   * Note: this implementation is optimized for space
40   * usage, but random access and edge removals are expensive.
41   *
42   * @param <I> Vertex id type
43   */
44  public class IdAndNullArrayEdges<I extends WritableComparable>
45    implements ReuseObjectsOutEdges<I, NullWritable>,
46    MutableOutEdges<I, NullWritable>,
47    ImmutableClassesGiraphConfigurable<I, Writable, NullWritable> {
48  
49    /** Array of target vertex ids. */
50    private WArrayList<I> neighbors;
51  
52    @Override
53    public
54    ImmutableClassesGiraphConfiguration<I, Writable, NullWritable> getConf() {
55      throw new UnsupportedOperationException();
56    }
57  
58    @Override
59    public void setConf(
60        ImmutableClassesGiraphConfiguration<I, Writable, NullWritable> conf) {
61      PrimitiveIdTypeOps<I> idTypeOps =
62          TypeOpsUtils.getPrimitiveIdTypeOps(conf.getVertexIdClass());
63      neighbors = idTypeOps.createArrayList(10);
64      if (!conf.getEdgeValueClass().equals(NullWritable.class)) {
65        throw new IllegalArgumentException(
66            "IdAndNullArrayEdges can be used only with NullWritable " +
67            "as edgeValueClass, not with " + conf.getEdgeValueClass());
68      }
69    }
70  
71    @Override
72    public void initialize(Iterable<Edge<I, NullWritable>> edges) {
73      EdgeIterables.initialize(this, edges);
74    }
75  
76    @Override
77    public void initialize(int capacity) {
78      neighbors.setCapacity(capacity);
79    }
80  
81    @Override
82    public void initialize() {
83      initialize(10);
84    }
85  
86    @Override
87    public void add(Edge<I, NullWritable> edge) {
88      neighbors.addW(edge.getTargetVertexId());
89    }
90  
91    /**
92     * If the backing array is more than four times as big as the number of
93     * elements, reduce to 2 times current size.
94     */
95    private void trim() {
96      if (neighbors.capacity() > 4 * neighbors.size()) {
97        neighbors.setCapacity(neighbors.size() * 2);
98      }
99    }
100 
101   /**
102    * Remove edge at position i.
103    *
104    * @param i Position of edge to be removed
105    */
106   private void removeAt(int i) {
107     // The order of the edges is irrelevant, so we can simply replace
108     // the deleted edge with the rightmost element, thus achieving constant
109     // time.
110     I tmpValue = neighbors.getElementTypeOps().create();
111     neighbors.popIntoW(tmpValue);
112     if (i != neighbors.size()) {
113       neighbors.setW(i, tmpValue);
114     }
115     // If needed after the removal, trim the array.
116     trim();
117   }
118 
119   @Override
120   public void remove(I targetVertexId) {
121     // Thanks to the constant-time implementation of removeAt(int),
122     // we can remove all matching edges in linear time.
123     I tmpValue = neighbors.getElementTypeOps().create();
124     for (int i = neighbors.size() - 1; i >= 0; --i) {
125       neighbors.getIntoW(i, tmpValue);
126       if (tmpValue.equals(targetVertexId)) {
127         removeAt(i);
128       }
129     }
130   }
131 
132   @Override
133   public int size() {
134     return neighbors.size();
135   }
136 
137   @Override
138   public Iterator<Edge<I, NullWritable>> iterator() {
139     // Returns an iterator that reuses objects.
140     // The downcast is fine because all concrete Edge implementations are
141     // mutable, but we only expose the mutation functionality when appropriate.
142     return (Iterator) mutableIterator();
143   }
144 
145   @Override
146   public Iterator<MutableEdge<I, NullWritable>> mutableIterator() {
147     return new Iterator<MutableEdge<I, NullWritable>>() {
148       /** Current position in the array. */
149       private int offset = 0;
150       /** Representative edge object. */
151       private final MutableEdge<I, NullWritable> representativeEdge =
152           EdgeFactory.createReusable(neighbors.getElementTypeOps().create());
153 
154       @Override
155       public boolean hasNext() {
156         return offset < neighbors.size();
157       }
158 
159       @Override
160       public MutableEdge<I, NullWritable> next() {
161         neighbors.getIntoW(offset++, representativeEdge.getTargetVertexId());
162         return representativeEdge;
163       }
164 
165       @Override
166       public void remove() {
167         // Since removeAt() might replace the deleted edge with the last edge
168         // in the array, we need to decrease the offset so that the latter
169         // won't be skipped.
170         removeAt(--offset);
171       }
172     };
173   }
174 
175   @Override
176   public void write(DataOutput out) throws IOException {
177     neighbors.write(out);
178   }
179 
180   @Override
181   public void readFields(DataInput in) throws IOException {
182     neighbors.readFields(in);
183   }
184 }