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 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 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
69
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
79
80
81
82 private void removeAt(int i) {
83
84
85
86 if (i == neighbors.size() - 1) {
87 neighbors.popLong();
88 } else {
89 neighbors.set(i, neighbors.popLong());
90 }
91
92 trimBack();
93 }
94
95 @Override
96 public void remove(LongWritable targetVertexId) {
97
98
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
114
115
116 return (Iterator) mutableIterator();
117 }
118
119 @Override
120 public Iterator<MutableEdge<LongWritable, NullWritable>> mutableIterator() {
121 return new Iterator<MutableEdge<LongWritable, NullWritable>>() {
122
123 private int offset = 0;
124
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
142
143
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