1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 package org.apache.giraph.edge;
20
21 import it.unimi.dsi.fastutil.doubles.DoubleArrayList;
22 import it.unimi.dsi.fastutil.doubles.DoubleIterator;
23 import it.unimi.dsi.fastutil.longs.LongArrayList;
24 import it.unimi.dsi.fastutil.longs.LongIterator;
25
26 import java.io.DataInput;
27 import java.io.DataOutput;
28 import java.io.IOException;
29 import java.util.Iterator;
30
31 import org.apache.giraph.utils.EdgeIterables;
32 import org.apache.giraph.utils.Trimmable;
33 import org.apache.hadoop.io.DoubleWritable;
34 import org.apache.hadoop.io.LongWritable;
35
36 import com.google.common.collect.UnmodifiableIterator;
37
38
39
40
41
42
43
44
45 public class LongDoubleArrayEdges
46 implements ReuseObjectsOutEdges<LongWritable, DoubleWritable>,
47 MutableOutEdges<LongWritable, DoubleWritable>, Trimmable {
48
49 private LongArrayList neighbors;
50
51 private DoubleArrayList edgeValues;
52
53 @Override
54 public void initialize(Iterable<Edge<LongWritable, DoubleWritable>> edges) {
55 EdgeIterables.initialize(this, edges);
56 }
57
58 @Override
59 public void initialize(int capacity) {
60 neighbors = new LongArrayList(capacity);
61 edgeValues = new DoubleArrayList(capacity);
62 }
63
64 @Override
65 public void initialize() {
66 neighbors = new LongArrayList();
67 edgeValues = new DoubleArrayList();
68 }
69
70 @Override
71 public void add(Edge<LongWritable, DoubleWritable> edge) {
72 neighbors.add(edge.getTargetVertexId().get());
73 edgeValues.add(edge.getValue().get());
74 }
75
76
77
78
79
80 private void trimBack() {
81 if (neighbors.elements().length > 4 * neighbors.size()) {
82 neighbors.trim(neighbors.elements().length / 2);
83 edgeValues.trim(neighbors.elements().length / 2);
84 }
85 }
86
87
88
89
90
91
92 private void removeAt(int i) {
93
94
95
96 if (i == neighbors.size() - 1) {
97 neighbors.popLong();
98 edgeValues.popDouble();
99 } else {
100 neighbors.set(i, neighbors.popLong());
101 edgeValues.set(i, edgeValues.popDouble());
102 }
103
104 trimBack();
105 }
106
107 @Override
108 public void remove(LongWritable targetVertexId) {
109
110
111 for (int i = neighbors.size() - 1; i >= 0; --i) {
112 if (neighbors.getLong(i) == targetVertexId.get()) {
113 removeAt(i);
114 }
115 }
116 }
117
118 @Override
119 public int size() {
120 return neighbors.size();
121 }
122
123 @Override
124 public Iterator<Edge<LongWritable, DoubleWritable>> iterator() {
125
126 return new UnmodifiableIterator<Edge<LongWritable, DoubleWritable>>() {
127
128 private final LongIterator neighborsIt = neighbors.iterator();
129
130 private final DoubleIterator edgeValuesIt = edgeValues.iterator();
131
132 private final Edge<LongWritable, DoubleWritable> representativeEdge =
133 EdgeFactory.create(new LongWritable(), new DoubleWritable());
134
135 @Override
136 public boolean hasNext() {
137 return neighborsIt.hasNext();
138 }
139
140 @Override
141 public Edge<LongWritable, DoubleWritable> next() {
142 representativeEdge.getTargetVertexId().set(neighborsIt.nextLong());
143 representativeEdge.getValue().set(edgeValuesIt.nextDouble());
144 return representativeEdge;
145 }
146 };
147 }
148
149
150 private class LongDoubleArrayMutableEdge
151 extends DefaultEdge<LongWritable, DoubleWritable> {
152
153 private int index;
154
155
156 public LongDoubleArrayMutableEdge() {
157 super(new LongWritable(), new DoubleWritable());
158 }
159
160
161
162
163
164
165 public void setIndex(int index) {
166
167 getTargetVertexId().set(neighbors.getLong(index));
168 getValue().set(edgeValues.getDouble(index));
169
170 this.index = index;
171 }
172
173 @Override
174 public void setValue(DoubleWritable value) {
175
176 getValue().set(value.get());
177
178 edgeValues.set(index, value.get());
179 }
180 }
181
182 @Override
183 public Iterator<MutableEdge<LongWritable, DoubleWritable>>
184 mutableIterator() {
185 return new Iterator<MutableEdge<LongWritable, DoubleWritable>>() {
186
187 private int offset = 0;
188
189 private final LongDoubleArrayMutableEdge representativeEdge =
190 new LongDoubleArrayMutableEdge();
191
192 @Override
193 public boolean hasNext() {
194 return offset < neighbors.size();
195 }
196
197 @Override
198 public MutableEdge<LongWritable, DoubleWritable> next() {
199 representativeEdge.setIndex(offset++);
200 return representativeEdge;
201 }
202
203 @Override
204 public void remove() {
205
206
207
208 removeAt(--offset);
209 }
210 };
211 }
212
213 @Override
214 public void write(DataOutput out) throws IOException {
215 out.writeInt(neighbors.size());
216 LongIterator neighborsIt = neighbors.iterator();
217 DoubleIterator edgeValuesIt = edgeValues.iterator();
218 while (neighborsIt.hasNext()) {
219 out.writeLong(neighborsIt.nextLong());
220 out.writeDouble(edgeValuesIt.nextDouble());
221 }
222 }
223
224 @Override
225 public void readFields(DataInput in) throws IOException {
226 int numEdges = in.readInt();
227 initialize(numEdges);
228 for (int i = 0; i < numEdges; ++i) {
229 neighbors.add(in.readLong());
230 edgeValues.add(in.readDouble());
231 }
232 }
233
234 @Override
235 public void trim() {
236 neighbors.trim();
237 edgeValues.trim();
238 }
239 }