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