This project has retired. For details please refer to its Attic page.
LongNullArrayEdges 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  
19  package org.apache.giraph.edge;
20  
21  import it.unimi.dsi.fastutil.longs.LongArrayList;
22  import it.unimi.dsi.fastutil.longs.LongIterator;
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.LongWritable;
32  import org.apache.hadoop.io.NullWritable;
33  
34  /**
35   * Implementation of {@link OutEdges} with long ids and null edge
36   * values, backed by a dynamic primitive array.
37   * Parallel edges are allowed.
38   * Note: this implementation is optimized for space usage,
39   * but random access and edge removals are expensive.
40   */
41  public class LongNullArrayEdges
42      implements ReuseObjectsOutEdges<LongWritable, NullWritable>,
43      MutableOutEdges<LongWritable, NullWritable>, Trimmable {
44    /** Array of target vertex ids. */
45    private LongArrayList neighbors;
46  
47    @Override
48    public void initialize(Iterable<Edge<LongWritable, NullWritable>> edges) {
49      EdgeIterables.initialize(this, edges);
50    }
51  
52    @Override
53    public void initialize(int capacity) {
54      neighbors = new LongArrayList(capacity);
55    }
56  
57    @Override
58    public void initialize() {
59      neighbors = new LongArrayList();
60    }
61  
62    @Override
63    public void add(Edge<LongWritable, NullWritable> edge) {
64      neighbors.add(edge.getTargetVertexId().get());
65    }
66  
67    /**
68     * If the backing array is more than four times as big as the number of
69     * elements, halve its size.
70     */
71    private void trimBack() {
72      if (neighbors.elements().length > 4 * neighbors.size()) {
73        neighbors.trim(neighbors.elements().length / 2);
74      }
75    }
76  
77    /**
78     * Remove edge at position i.
79     *
80     * @param i Position of edge to be removed
81     */
82    private void removeAt(int i) {
83      // The order of the edges is irrelevant, so we can simply replace
84      // the deleted edge with the rightmost element, thus achieving constant
85      // time.
86      if (i == neighbors.size() - 1) {
87        neighbors.popLong();
88      } else {
89        neighbors.set(i, neighbors.popLong());
90      }
91      // If needed after the removal, trim the array.
92      trimBack();
93    }
94  
95    @Override
96    public void remove(LongWritable targetVertexId) {
97      // Thanks to the constant-time implementation of removeAt(int),
98      // we can remove all matching edges in linear time.
99      for (int i = neighbors.size() - 1; i >= 0; --i) {
100       if (neighbors.getLong(i) == targetVertexId.get()) {
101         removeAt(i);
102       }
103     }
104   }
105 
106   @Override
107   public int size() {
108     return neighbors.size();
109   }
110 
111   @Override
112   public Iterator<Edge<LongWritable, NullWritable>> iterator() {
113     // Returns an iterator that reuses objects.
114     // The downcast is fine because all concrete Edge implementations are
115     // mutable, but we only expose the mutation functionality when appropriate.
116     return (Iterator) mutableIterator();
117   }
118 
119   @Override
120   public Iterator<MutableEdge<LongWritable, NullWritable>> mutableIterator() {
121     return new Iterator<MutableEdge<LongWritable, NullWritable>>() {
122       /** Current position in the array. */
123       private int offset = 0;
124       /** Representative edge object. */
125       private final MutableEdge<LongWritable, NullWritable> representativeEdge =
126           EdgeFactory.createReusable(new LongWritable());
127 
128       @Override
129       public boolean hasNext() {
130         return offset < neighbors.size();
131       }
132 
133       @Override
134       public MutableEdge<LongWritable, NullWritable> next() {
135         representativeEdge.getTargetVertexId().set(neighbors.getLong(offset++));
136         return representativeEdge;
137       }
138 
139       @Override
140       public void remove() {
141         // Since removeAt() might replace the deleted edge with the last edge
142         // in the array, we need to decrease the offset so that the latter
143         // won't be skipped.
144         removeAt(--offset);
145       }
146     };
147   }
148 
149   @Override
150   public void write(DataOutput out) throws IOException {
151     out.writeInt(neighbors.size());
152     LongIterator neighborsIt = neighbors.iterator();
153     while (neighborsIt.hasNext()) {
154       out.writeLong(neighborsIt.nextLong());
155     }
156   }
157 
158   @Override
159   public void readFields(DataInput in) throws IOException {
160     int numEdges = in.readInt();
161     initialize(numEdges);
162     for (int i = 0; i < numEdges; ++i) {
163       neighbors.add(in.readLong());
164     }
165   }
166 
167   @Override
168   public void trim() {
169     neighbors.trim();
170   }
171 }
172