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.PrimitiveTypeOps;
29  import org.apache.giraph.types.ops.TypeOpsUtils;
30  import org.apache.giraph.types.ops.collections.array.WArrayList;
31  import org.apache.giraph.utils.EdgeIterables;
32  import org.apache.hadoop.io.Writable;
33  import org.apache.hadoop.io.WritableComparable;
34  
35  import com.google.common.collect.UnmodifiableIterator;
36  
37  /**
38   * Implementation of {@link OutEdges} with IDs and Edge values having their
39   * TypeOps.
40   * Data is backed by a dynamic primitive array. Parallel edges are allowed.
41   * Note: this implementation is optimized for space usage, but random access
42   * and edge removals are expensive.
43   *
44   * @param <I> Vertex id type
45   * @param <E> Edge value type
46   */
47  public class IdAndValueArrayEdges<I extends WritableComparable,
48      E extends Writable> implements ReuseObjectsOutEdges<I, E>,
49      MutableOutEdges<I, E>,
50      ImmutableClassesGiraphConfigurable<I, Writable, E> {
51  
52    /** Array of target vertex ids. */
53    private WArrayList<I> neighborIds;
54    /** Array of edge values. */
55    private WArrayList<E> neighborEdgeValues;
56  
57    @Override
58    public ImmutableClassesGiraphConfiguration<I, Writable, E> getConf() {
59      throw new UnsupportedOperationException();
60    }
61  
62    @Override
63    public void setConf(
64        ImmutableClassesGiraphConfiguration<I, Writable, E> conf) {
65      PrimitiveIdTypeOps<I> idTypeOps =
66          TypeOpsUtils.getPrimitiveIdTypeOps(conf.getVertexIdClass());
67      neighborIds = idTypeOps.createArrayList(10);
68  
69      PrimitiveTypeOps<E> edgeTypeOps =
70          TypeOpsUtils.getPrimitiveTypeOps(conf.getEdgeValueClass());
71      neighborEdgeValues = edgeTypeOps.createArrayList(10);
72    }
73  
74    @Override
75    public void initialize(Iterable<Edge<I, E>> edges) {
76      EdgeIterables.initialize(this, edges);
77    }
78  
79    @Override
80    public void initialize(int capacity) {
81      neighborIds.setCapacity(capacity);
82      neighborEdgeValues.setCapacity(capacity);
83    }
84  
85    @Override
86    public void initialize() {
87      initialize(10);
88    }
89  
90    @Override
91    public void add(Edge<I, E> edge) {
92      neighborIds.addW(edge.getTargetVertexId());
93      neighborEdgeValues.addW(edge.getValue());
94    }
95  
96    /**
97     * If the backing array is more than four times as big as the number of
98     * elements, reduce to 2 times current size.
99     */
100   private void trim() {
101     if (neighborIds.capacity() > 4 * neighborIds.size()) {
102       neighborIds.setCapacity(neighborIds.size() * 2);
103       neighborEdgeValues.setCapacity(neighborIds.size() * 2);
104     }
105   }
106 
107   /**
108    * Remove edge at position i.
109    *
110    * @param i Position of edge to be removed
111    */
112   private void removeAt(int i) {
113     // The order of the edges is irrelevant, so we can simply replace
114     // the deleted edge with the rightmost element, thus achieving constant
115     // time.
116     I tmpId = neighborIds.getElementTypeOps().create();
117     E tmpValue = neighborEdgeValues.getElementTypeOps().create();
118 
119     neighborIds.popIntoW(tmpId);
120     neighborEdgeValues.popIntoW(tmpValue);
121     if (i != neighborIds.size()) {
122       neighborIds.setW(i, tmpId);
123       neighborEdgeValues.setW(i, tmpValue);
124     }
125     // If needed after the removal, trim the array.
126     trim();
127   }
128 
129   @Override
130   public void remove(I targetVertexId) {
131     // Thanks to the constant-time implementation of removeAt(int),
132     // we can remove all matching edges in linear time.
133     I tmpId = neighborIds.getElementTypeOps().create();
134     for (int i = neighborIds.size() - 1; i >= 0; --i) {
135       neighborIds.getIntoW(i, tmpId);
136       if (tmpId.equals(targetVertexId)) {
137         removeAt(i);
138       }
139     }
140   }
141 
142   @Override
143   public int size() {
144     return neighborIds.size();
145   }
146 
147   @Override
148   public Iterator<Edge<I, E>> iterator() {
149     // Returns an iterator that reuses objects.
150     return new UnmodifiableIterator<Edge<I, E>>() {
151       private int index;
152 
153       /** Representative edge object. */
154       private final Edge<I, E> representativeEdge = EdgeFactory.create(
155           neighborIds.getElementTypeOps().create(),
156           neighborEdgeValues.getElementTypeOps().create());
157 
158       @Override
159       public boolean hasNext() {
160         return index < neighborIds.size();
161       }
162 
163       @Override
164       public Edge<I, E> next() {
165         neighborIds.getIntoW(index, representativeEdge.getTargetVertexId());
166         neighborEdgeValues.getIntoW(index, representativeEdge.getValue());
167         index++;
168         return representativeEdge;
169       }
170     };
171   }
172 
173   /** Helper class for a mutable edge that modifies the backing arrays. */
174   private class ArrayMutableEdge extends DefaultEdge<I, E> {
175     /** Index of the edge in the backing arrays. */
176     private int index;
177 
178     /** Constructor. */
179     public ArrayMutableEdge() {
180       super(
181           neighborIds.getElementTypeOps().create(),
182           neighborEdgeValues.getElementTypeOps().create());
183     }
184 
185     /**
186      * Make the edge point to the given index in the backing arrays.
187      *
188      * @param index Index in the arrays
189      */
190     public void setIndex(int index) {
191       // Update the id and value objects from the superclass.
192       neighborIds.getIntoW(index, getTargetVertexId());
193       neighborEdgeValues.getIntoW(index, getValue());
194       // Update the index.
195       this.index = index;
196     }
197 
198     @Override
199     public void setValue(E value) {
200       // Update the value object from the superclass.
201       neighborEdgeValues.getElementTypeOps().set(getValue(), value);
202       // Update the value stored in the backing array.
203       neighborEdgeValues.setW(index, value);
204     }
205   }
206 
207   @Override
208   public Iterator<MutableEdge<I, E>> mutableIterator() {
209     return new Iterator<MutableEdge<I, E>>() {
210       /** Current position in the array. */
211       private int index = 0;
212       /** Representative edge object. */
213       private final ArrayMutableEdge representativeEdge =
214           new ArrayMutableEdge();
215 
216       @Override
217       public boolean hasNext() {
218         return index < neighborIds.size();
219       }
220 
221       @Override
222       public MutableEdge<I, E> next() {
223         representativeEdge.setIndex(index++);
224         return representativeEdge;
225       }
226 
227       @Override
228       public void remove() {
229         // Since removeAt() might replace the deleted edge with the last edge
230         // in the array, we need to decrease the offset so that the latter
231         // won't be skipped.
232         removeAt(--index);
233       }
234     };
235   }
236 
237   @Override
238   public void write(DataOutput out) throws IOException {
239     neighborIds.write(out);
240     neighborEdgeValues.write(out);
241   }
242 
243   @Override
244   public void readFields(DataInput in) throws IOException {
245     neighborIds.readFields(in);
246     neighborEdgeValues.readFields(in);
247   }
248 }