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.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 | |
|
36 | |
|
37 | |
|
38 | |
|
39 | |
|
40 | |
|
41 | 0 | public class LongNullArrayEdges |
42 | |
implements ReuseObjectsOutEdges<LongWritable, NullWritable>, |
43 | |
MutableOutEdges<LongWritable, NullWritable>, Trimmable { |
44 | |
|
45 | |
private LongArrayList neighbors; |
46 | |
|
47 | |
@Override |
48 | |
public void initialize(Iterable<Edge<LongWritable, NullWritable>> edges) { |
49 | 0 | EdgeIterables.initialize(this, edges); |
50 | 0 | } |
51 | |
|
52 | |
@Override |
53 | |
public void initialize(int capacity) { |
54 | 0 | neighbors = new LongArrayList(capacity); |
55 | 0 | } |
56 | |
|
57 | |
@Override |
58 | |
public void initialize() { |
59 | 0 | neighbors = new LongArrayList(); |
60 | 0 | } |
61 | |
|
62 | |
@Override |
63 | |
public void add(Edge<LongWritable, NullWritable> edge) { |
64 | 0 | neighbors.add(edge.getTargetVertexId().get()); |
65 | 0 | } |
66 | |
|
67 | |
|
68 | |
|
69 | |
|
70 | |
|
71 | |
private void trimBack() { |
72 | 0 | if (neighbors.elements().length > 4 * neighbors.size()) { |
73 | 0 | neighbors.trim(neighbors.elements().length / 2); |
74 | |
} |
75 | 0 | } |
76 | |
|
77 | |
|
78 | |
|
79 | |
|
80 | |
|
81 | |
|
82 | |
private void removeAt(int i) { |
83 | |
|
84 | |
|
85 | |
|
86 | 0 | if (i == neighbors.size() - 1) { |
87 | 0 | neighbors.popLong(); |
88 | |
} else { |
89 | 0 | neighbors.set(i, neighbors.popLong()); |
90 | |
} |
91 | |
|
92 | 0 | trimBack(); |
93 | 0 | } |
94 | |
|
95 | |
@Override |
96 | |
public void remove(LongWritable targetVertexId) { |
97 | |
|
98 | |
|
99 | 0 | for (int i = neighbors.size() - 1; i >= 0; --i) { |
100 | 0 | if (neighbors.getLong(i) == targetVertexId.get()) { |
101 | 0 | removeAt(i); |
102 | |
} |
103 | |
} |
104 | 0 | } |
105 | |
|
106 | |
@Override |
107 | |
public int size() { |
108 | 0 | return neighbors.size(); |
109 | |
} |
110 | |
|
111 | |
@Override |
112 | |
public Iterator<Edge<LongWritable, NullWritable>> iterator() { |
113 | |
|
114 | |
|
115 | |
|
116 | 0 | return (Iterator) mutableIterator(); |
117 | |
} |
118 | |
|
119 | |
@Override |
120 | |
public Iterator<MutableEdge<LongWritable, NullWritable>> mutableIterator() { |
121 | 0 | return new Iterator<MutableEdge<LongWritable, NullWritable>>() { |
122 | |
|
123 | 0 | private int offset = 0; |
124 | |
|
125 | 0 | private final MutableEdge<LongWritable, NullWritable> representativeEdge = |
126 | 0 | EdgeFactory.createReusable(new LongWritable()); |
127 | |
|
128 | |
@Override |
129 | |
public boolean hasNext() { |
130 | 0 | return offset < neighbors.size(); |
131 | |
} |
132 | |
|
133 | |
@Override |
134 | |
public MutableEdge<LongWritable, NullWritable> next() { |
135 | 0 | representativeEdge.getTargetVertexId().set(neighbors.getLong(offset++)); |
136 | 0 | return representativeEdge; |
137 | |
} |
138 | |
|
139 | |
@Override |
140 | |
public void remove() { |
141 | |
|
142 | |
|
143 | |
|
144 | 0 | removeAt(--offset); |
145 | 0 | } |
146 | |
}; |
147 | |
} |
148 | |
|
149 | |
@Override |
150 | |
public void write(DataOutput out) throws IOException { |
151 | 0 | out.writeInt(neighbors.size()); |
152 | 0 | LongIterator neighborsIt = neighbors.iterator(); |
153 | 0 | while (neighborsIt.hasNext()) { |
154 | 0 | out.writeLong(neighborsIt.nextLong()); |
155 | |
} |
156 | 0 | } |
157 | |
|
158 | |
@Override |
159 | |
public void readFields(DataInput in) throws IOException { |
160 | 0 | int numEdges = in.readInt(); |
161 | 0 | initialize(numEdges); |
162 | 0 | for (int i = 0; i < numEdges; ++i) { |
163 | 0 | neighbors.add(in.readLong()); |
164 | |
} |
165 | 0 | } |
166 | |
|
167 | |
@Override |
168 | |
public void trim() { |
169 | 0 | neighbors.trim(); |
170 | 0 | } |
171 | |
} |
172 | |
|