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 | 0 | 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 | 0 | EdgeIterables.initialize(this, edges); |
56 | 0 | } |
57 | |
|
58 | |
@Override |
59 | |
public void initialize(int capacity) { |
60 | 0 | neighbors = new LongArrayList(capacity); |
61 | 0 | edgeValues = new DoubleArrayList(capacity); |
62 | 0 | } |
63 | |
|
64 | |
@Override |
65 | |
public void initialize() { |
66 | 0 | neighbors = new LongArrayList(); |
67 | 0 | edgeValues = new DoubleArrayList(); |
68 | 0 | } |
69 | |
|
70 | |
@Override |
71 | |
public void add(Edge<LongWritable, DoubleWritable> edge) { |
72 | 0 | neighbors.add(edge.getTargetVertexId().get()); |
73 | 0 | edgeValues.add(edge.getValue().get()); |
74 | 0 | } |
75 | |
|
76 | |
|
77 | |
|
78 | |
|
79 | |
|
80 | |
private void trimBack() { |
81 | 0 | if (neighbors.elements().length > 4 * neighbors.size()) { |
82 | 0 | neighbors.trim(neighbors.elements().length / 2); |
83 | 0 | edgeValues.trim(neighbors.elements().length / 2); |
84 | |
} |
85 | 0 | } |
86 | |
|
87 | |
|
88 | |
|
89 | |
|
90 | |
|
91 | |
|
92 | |
private void removeAt(int i) { |
93 | |
|
94 | |
|
95 | |
|
96 | 0 | if (i == neighbors.size() - 1) { |
97 | 0 | neighbors.popLong(); |
98 | 0 | edgeValues.popDouble(); |
99 | |
} else { |
100 | 0 | neighbors.set(i, neighbors.popLong()); |
101 | 0 | edgeValues.set(i, edgeValues.popDouble()); |
102 | |
} |
103 | |
|
104 | 0 | trimBack(); |
105 | 0 | } |
106 | |
|
107 | |
@Override |
108 | |
public void remove(LongWritable targetVertexId) { |
109 | |
|
110 | |
|
111 | 0 | for (int i = neighbors.size() - 1; i >= 0; --i) { |
112 | 0 | if (neighbors.getLong(i) == targetVertexId.get()) { |
113 | 0 | removeAt(i); |
114 | |
} |
115 | |
} |
116 | 0 | } |
117 | |
|
118 | |
@Override |
119 | |
public int size() { |
120 | 0 | return neighbors.size(); |
121 | |
} |
122 | |
|
123 | |
@Override |
124 | |
public Iterator<Edge<LongWritable, DoubleWritable>> iterator() { |
125 | |
|
126 | 0 | return new UnmodifiableIterator<Edge<LongWritable, DoubleWritable>>() { |
127 | |
|
128 | 0 | private final LongIterator neighborsIt = neighbors.iterator(); |
129 | |
|
130 | 0 | private final DoubleIterator edgeValuesIt = edgeValues.iterator(); |
131 | |
|
132 | 0 | private final Edge<LongWritable, DoubleWritable> representativeEdge = |
133 | 0 | EdgeFactory.create(new LongWritable(), new DoubleWritable()); |
134 | |
|
135 | |
@Override |
136 | |
public boolean hasNext() { |
137 | 0 | return neighborsIt.hasNext(); |
138 | |
} |
139 | |
|
140 | |
@Override |
141 | |
public Edge<LongWritable, DoubleWritable> next() { |
142 | 0 | representativeEdge.getTargetVertexId().set(neighborsIt.nextLong()); |
143 | 0 | representativeEdge.getValue().set(edgeValuesIt.nextDouble()); |
144 | 0 | return representativeEdge; |
145 | |
} |
146 | |
}; |
147 | |
} |
148 | |
|
149 | |
|
150 | 0 | private class LongDoubleArrayMutableEdge |
151 | |
extends DefaultEdge<LongWritable, DoubleWritable> { |
152 | |
|
153 | |
private int index; |
154 | |
|
155 | |
|
156 | 0 | public LongDoubleArrayMutableEdge() { |
157 | 0 | super(new LongWritable(), new DoubleWritable()); |
158 | 0 | } |
159 | |
|
160 | |
|
161 | |
|
162 | |
|
163 | |
|
164 | |
|
165 | |
public void setIndex(int index) { |
166 | |
|
167 | 0 | getTargetVertexId().set(neighbors.getLong(index)); |
168 | 0 | getValue().set(edgeValues.getDouble(index)); |
169 | |
|
170 | 0 | this.index = index; |
171 | 0 | } |
172 | |
|
173 | |
@Override |
174 | |
public void setValue(DoubleWritable value) { |
175 | |
|
176 | 0 | getValue().set(value.get()); |
177 | |
|
178 | 0 | edgeValues.set(index, value.get()); |
179 | 0 | } |
180 | |
} |
181 | |
|
182 | |
@Override |
183 | |
public Iterator<MutableEdge<LongWritable, DoubleWritable>> |
184 | |
mutableIterator() { |
185 | 0 | return new Iterator<MutableEdge<LongWritable, DoubleWritable>>() { |
186 | |
|
187 | 0 | private int offset = 0; |
188 | |
|
189 | 0 | private final LongDoubleArrayMutableEdge representativeEdge = |
190 | |
new LongDoubleArrayMutableEdge(); |
191 | |
|
192 | |
@Override |
193 | |
public boolean hasNext() { |
194 | 0 | return offset < neighbors.size(); |
195 | |
} |
196 | |
|
197 | |
@Override |
198 | |
public MutableEdge<LongWritable, DoubleWritable> next() { |
199 | 0 | representativeEdge.setIndex(offset++); |
200 | 0 | return representativeEdge; |
201 | |
} |
202 | |
|
203 | |
@Override |
204 | |
public void remove() { |
205 | |
|
206 | |
|
207 | |
|
208 | 0 | removeAt(--offset); |
209 | 0 | } |
210 | |
}; |
211 | |
} |
212 | |
|
213 | |
@Override |
214 | |
public void write(DataOutput out) throws IOException { |
215 | 0 | out.writeInt(neighbors.size()); |
216 | 0 | LongIterator neighborsIt = neighbors.iterator(); |
217 | 0 | DoubleIterator edgeValuesIt = edgeValues.iterator(); |
218 | 0 | while (neighborsIt.hasNext()) { |
219 | 0 | out.writeLong(neighborsIt.nextLong()); |
220 | 0 | out.writeDouble(edgeValuesIt.nextDouble()); |
221 | |
} |
222 | 0 | } |
223 | |
|
224 | |
@Override |
225 | |
public void readFields(DataInput in) throws IOException { |
226 | 0 | int numEdges = in.readInt(); |
227 | 0 | initialize(numEdges); |
228 | 0 | for (int i = 0; i < numEdges; ++i) { |
229 | 0 | neighbors.add(in.readLong()); |
230 | 0 | edgeValues.add(in.readDouble()); |
231 | |
} |
232 | 0 | } |
233 | |
|
234 | |
@Override |
235 | |
public void trim() { |
236 | 0 | neighbors.trim(); |
237 | 0 | edgeValues.trim(); |
238 | 0 | } |
239 | |
} |