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