1 | /* | |
2 | * Copyright 2006 - 2013 | |
3 | * Stefan Balev <stefan.balev@graphstream-project.org> | |
4 | * Julien Baudry <julien.baudry@graphstream-project.org> | |
5 | * Antoine Dutot <antoine.dutot@graphstream-project.org> | |
6 | * Yoann Pign������ <yoann.pigne@graphstream-project.org> | |
7 | * Guilhelm Savin <guilhelm.savin@graphstream-project.org> | |
8 | * | |
9 | * This file is part of GraphStream <http://graphstream-project.org>. | |
10 | * | |
11 | * GraphStream is a library whose purpose is to handle static or dynamic | |
12 | * graph, create them from scratch, file or any source and display them. | |
13 | * | |
14 | * This program is free software distributed under the terms of two licenses, the | |
15 | * CeCILL-C license that fits European law, and the GNU Lesser General Public | |
16 | * License. You can use, modify and/ or redistribute the software under the terms | |
17 | * of the CeCILL-C license as circulated by CEA, CNRS and INRIA at the following | |
18 | * URL <http://www.cecill.info> or under the terms of the GNU LGPL as published by | |
19 | * the Free Software Foundation, either version 3 of the License, or (at your | |
20 | * option) any later version. | |
21 | * | |
22 | * This program is distributed in the hope that it will be useful, but WITHOUT ANY | |
23 | * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A | |
24 | * PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. | |
25 | * | |
26 | * You should have received a copy of the GNU Lesser General Public License | |
27 | * along with this program. If not, see <http://www.gnu.org/licenses/>. | |
28 | * | |
29 | * The fact that you are presently reading this means that you have had | |
30 | * knowledge of the CeCILL-C and LGPL licenses and that you accept their terms. | |
31 | */ | |
32 | package org.graphstream.graph.implementations; | |
33 | ||
34 | import java.security.AccessControlException; | |
35 | import java.util.Arrays; | |
36 | import java.util.Iterator; | |
37 | import java.util.NoSuchElementException; | |
38 | ||
39 | import org.graphstream.graph.Edge; | |
40 | import org.graphstream.graph.Node; | |
41 | ||
42 | /** | |
43 | * Nodes used with {@link AdjacencyListGraph} | |
44 | * | |
45 | */ | |
46 | public class AdjacencyListNode extends AbstractNode { | |
47 | protected static final int INITIAL_EDGE_CAPACITY; | |
48 | protected static final double GROWTH_FACTOR = 1.1; | |
49 | ||
50 | static { | |
51 | String p = "org.graphstream.graph.node.initialEdgeCapacity"; | |
52 | int initialEdgeCapacity = 16; | |
53 | try { | |
54 | initialEdgeCapacity = Integer.valueOf(System.getProperty(p, "16")); | |
55 | } catch (AccessControlException e) { | |
56 | } | |
57 | INITIAL_EDGE_CAPACITY = initialEdgeCapacity; | |
58 | } | |
59 | ||
60 | protected static final char I_EDGE = 0; | |
61 | protected static final char IO_EDGE = 1; | |
62 | protected static final char O_EDGE = 2; | |
63 | ||
64 | protected AbstractEdge[] edges; | |
65 | protected int ioStart, oStart, degree; | |
66 | ||
67 | // *** Constructor *** | |
68 | ||
69 | protected AdjacencyListNode(AbstractGraph graph, String id) { | |
70 | super(graph, id); | |
71 | edges = new AbstractEdge[INITIAL_EDGE_CAPACITY]; | |
72 | ioStart = oStart = degree = 0; | |
73 | } | |
74 | ||
75 | // *** Helpers *** | |
76 | ||
77 | protected char edgeType(AbstractEdge e) { | |
78 |
2
1. edgeType : negated conditional → SURVIVED 2. edgeType : negated conditional → KILLED |
if (!e.directed || e.source == e.target) |
79 |
1
1. edgeType : replaced return of integer sized value with (x == 0 ? 1 : 0) → KILLED |
return IO_EDGE; |
80 |
2
1. edgeType : negated conditional → NO_COVERAGE 2. edgeType : replaced return of integer sized value with (x == 0 ? 1 : 0) → NO_COVERAGE |
return e.source == this ? O_EDGE : I_EDGE; |
81 | } | |
82 | ||
83 | @SuppressWarnings("unchecked") | |
84 | protected <T extends Edge> T locateEdge(Node opposite, char type) { | |
85 | // where to search ? | |
86 | int start = 0; | |
87 | int end = degree; | |
88 |
1
1. locateEdge : negated conditional → NO_COVERAGE |
if (type == I_EDGE) |
89 | end = oStart; | |
90 |
1
1. locateEdge : negated conditional → NO_COVERAGE |
else if (type == O_EDGE) |
91 | start = ioStart; | |
92 | ||
93 |
3
1. locateEdge : changed conditional boundary → NO_COVERAGE 2. locateEdge : Changed increment from 1 to -1 → NO_COVERAGE 3. locateEdge : negated conditional → NO_COVERAGE |
for (int i = start; i < end; i++) |
94 |
1
1. locateEdge : negated conditional → NO_COVERAGE |
if (edges[i].getOpposite(this) == opposite) |
95 |
1
1. locateEdge : mutated return of Object value for org/graphstream/graph/implementations/AdjacencyListNode::locateEdge to ( if (x != null) null else throw new RuntimeException ) → NO_COVERAGE |
return (T) edges[i]; |
96 |
1
1. locateEdge : mutated return of Object value for org/graphstream/graph/implementations/AdjacencyListNode::locateEdge to ( if (x != null) null else throw new RuntimeException ) → NO_COVERAGE |
return null; |
97 | } | |
98 | ||
99 | protected void removeEdge(int i) { | |
100 |
2
1. removeEdge : changed conditional boundary → SURVIVED 2. removeEdge : negated conditional → SURVIVED |
if (i >= oStart) { |
101 |
1
1. removeEdge : Replaced integer subtraction with addition → NO_COVERAGE |
edges[i] = edges[--degree]; |
102 | edges[degree] = null; | |
103 | return; | |
104 | } | |
105 | ||
106 |
2
1. removeEdge : changed conditional boundary → KILLED 2. removeEdge : negated conditional → KILLED |
if (i >= ioStart) { |
107 |
1
1. removeEdge : Replaced integer subtraction with addition → SURVIVED |
edges[i] = edges[--oStart]; |
108 |
1
1. removeEdge : Replaced integer subtraction with addition → SURVIVED |
edges[oStart] = edges[--degree]; |
109 | edges[degree] = null; | |
110 | return; | |
111 | } | |
112 | ||
113 |
1
1. removeEdge : Replaced integer subtraction with addition → NO_COVERAGE |
edges[i] = edges[--ioStart]; |
114 |
1
1. removeEdge : Replaced integer subtraction with addition → NO_COVERAGE |
edges[ioStart] = edges[--oStart]; |
115 |
1
1. removeEdge : Replaced integer subtraction with addition → NO_COVERAGE |
edges[oStart] = edges[--degree]; |
116 | edges[degree] = null; | |
117 | ||
118 | } | |
119 | ||
120 | // *** Callbacks *** | |
121 | ||
122 | @Override | |
123 | protected boolean addEdgeCallback(AbstractEdge edge) { | |
124 | // resize edges if necessary | |
125 |
1
1. addEdgeCallback : negated conditional → SURVIVED |
if (edges.length == degree) { |
126 |
2
1. addEdgeCallback : Replaced double multiplication with division → NO_COVERAGE 2. addEdgeCallback : Replaced integer addition with subtraction → NO_COVERAGE |
AbstractEdge[] tmp = new AbstractEdge[(int) (GROWTH_FACTOR * edges.length) + 1]; |
127 |
1
1. addEdgeCallback : removed call to java/lang/System::arraycopy → NO_COVERAGE |
System.arraycopy(edges, 0, tmp, 0, edges.length); |
128 |
1
1. addEdgeCallback : removed call to java/util/Arrays::fill → NO_COVERAGE |
Arrays.fill(edges, null); |
129 | edges = tmp; | |
130 | } | |
131 | ||
132 | char type = edgeType(edge); | |
133 | ||
134 |
1
1. addEdgeCallback : negated conditional → SURVIVED |
if (type == O_EDGE) { |
135 |
1
1. addEdgeCallback : Replaced integer addition with subtraction → NO_COVERAGE |
edges[degree++] = edge; |
136 |
1
1. addEdgeCallback : replaced return of integer sized value with (x == 0 ? 1 : 0) → NO_COVERAGE |
return true; |
137 | } | |
138 | ||
139 |
1
1. addEdgeCallback : negated conditional → KILLED |
if (type == IO_EDGE) { |
140 |
1
1. addEdgeCallback : Replaced integer addition with subtraction → KILLED |
edges[degree++] = edges[oStart]; |
141 |
1
1. addEdgeCallback : Replaced integer addition with subtraction → KILLED |
edges[oStart++] = edge; |
142 |
1
1. addEdgeCallback : replaced return of integer sized value with (x == 0 ? 1 : 0) → KILLED |
return true; |
143 | } | |
144 | ||
145 |
1
1. addEdgeCallback : Replaced integer addition with subtraction → NO_COVERAGE |
edges[degree++] = edges[oStart]; |
146 |
1
1. addEdgeCallback : Replaced integer addition with subtraction → NO_COVERAGE |
edges[oStart++] = edges[ioStart]; |
147 |
1
1. addEdgeCallback : Replaced integer addition with subtraction → NO_COVERAGE |
edges[ioStart++] = edge; |
148 |
1
1. addEdgeCallback : replaced return of integer sized value with (x == 0 ? 1 : 0) → NO_COVERAGE |
return true; |
149 | } | |
150 | ||
151 | @Override | |
152 | protected void removeEdgeCallback(AbstractEdge edge) { | |
153 | // locate the edge first | |
154 | char type = edgeType(edge); | |
155 | int i = 0; | |
156 |
1
1. removeEdgeCallback : negated conditional → SURVIVED |
if (type == IO_EDGE) |
157 | i = ioStart; | |
158 |
1
1. removeEdgeCallback : negated conditional → NO_COVERAGE |
else if (type == O_EDGE) |
159 | i = oStart; | |
160 |
1
1. removeEdgeCallback : negated conditional → KILLED |
while (edges[i] != edge) |
161 |
1
1. removeEdgeCallback : Changed increment from 1 to -1 → NO_COVERAGE |
i++; |
162 | ||
163 |
1
1. removeEdgeCallback : removed call to org/graphstream/graph/implementations/AdjacencyListNode::removeEdge → SURVIVED |
removeEdge(i); |
164 | } | |
165 | ||
166 | @Override | |
167 | protected void clearCallback() { | |
168 |
1
1. clearCallback : removed call to java/util/Arrays::fill → SURVIVED |
Arrays.fill(edges, 0, degree, null); |
169 | ioStart = oStart = degree = 0; | |
170 | } | |
171 | ||
172 | // *** Access methods *** | |
173 | ||
174 | @Override | |
175 | public int getDegree() { | |
176 |
1
1. getDegree : replaced return of integer sized value with (x == 0 ? 1 : 0) → KILLED |
return degree; |
177 | } | |
178 | ||
179 | @Override | |
180 | public int getInDegree() { | |
181 |
1
1. getInDegree : replaced return of integer sized value with (x == 0 ? 1 : 0) → NO_COVERAGE |
return oStart; |
182 | } | |
183 | ||
184 | @Override | |
185 | public int getOutDegree() { | |
186 |
2
1. getOutDegree : Replaced integer subtraction with addition → NO_COVERAGE 2. getOutDegree : replaced return of integer sized value with (x == 0 ? 1 : 0) → NO_COVERAGE |
return degree - ioStart; |
187 | } | |
188 | ||
189 | @SuppressWarnings("unchecked") | |
190 | @Override | |
191 | public <T extends Edge> T getEdge(int i) { | |
192 |
4
1. getEdge : changed conditional boundary → NO_COVERAGE 2. getEdge : changed conditional boundary → NO_COVERAGE 3. getEdge : negated conditional → NO_COVERAGE 4. getEdge : negated conditional → NO_COVERAGE |
if (i < 0 || i >= degree) |
193 | throw new IndexOutOfBoundsException("Node \"" + this + "\"" | |
194 | + " has no edge " + i); | |
195 |
1
1. getEdge : mutated return of Object value for org/graphstream/graph/implementations/AdjacencyListNode::getEdge to ( if (x != null) null else throw new RuntimeException ) → NO_COVERAGE |
return (T) edges[i]; |
196 | } | |
197 | ||
198 | @SuppressWarnings("unchecked") | |
199 | @Override | |
200 | public <T extends Edge> T getEnteringEdge(int i) { | |
201 |
4
1. getEnteringEdge : changed conditional boundary → NO_COVERAGE 2. getEnteringEdge : changed conditional boundary → NO_COVERAGE 3. getEnteringEdge : negated conditional → NO_COVERAGE 4. getEnteringEdge : negated conditional → NO_COVERAGE |
if (i < 0 || i >= getInDegree()) |
202 | throw new IndexOutOfBoundsException("Node \"" + this + "\"" | |
203 | + " has no entering edge " + i); | |
204 |
1
1. getEnteringEdge : mutated return of Object value for org/graphstream/graph/implementations/AdjacencyListNode::getEnteringEdge to ( if (x != null) null else throw new RuntimeException ) → NO_COVERAGE |
return (T) edges[i]; |
205 | } | |
206 | ||
207 | @SuppressWarnings("unchecked") | |
208 | @Override | |
209 | public <T extends Edge> T getLeavingEdge(int i) { | |
210 |
4
1. getLeavingEdge : changed conditional boundary → NO_COVERAGE 2. getLeavingEdge : changed conditional boundary → NO_COVERAGE 3. getLeavingEdge : negated conditional → NO_COVERAGE 4. getLeavingEdge : negated conditional → NO_COVERAGE |
if (i < 0 || i >= getOutDegree()) |
211 | throw new IndexOutOfBoundsException("Node \"" + this + "\"" | |
212 | + " has no edge " + i); | |
213 |
2
1. getLeavingEdge : Replaced integer addition with subtraction → NO_COVERAGE 2. getLeavingEdge : mutated return of Object value for org/graphstream/graph/implementations/AdjacencyListNode::getLeavingEdge to ( if (x != null) null else throw new RuntimeException ) → NO_COVERAGE |
return (T) edges[ioStart + i]; |
214 | } | |
215 | ||
216 | @Override | |
217 | public <T extends Edge> T getEdgeBetween(Node node) { | |
218 |
1
1. getEdgeBetween : mutated return of Object value for org/graphstream/graph/implementations/AdjacencyListNode::getEdgeBetween to ( if (x != null) null else throw new RuntimeException ) → NO_COVERAGE |
return locateEdge(node, IO_EDGE); |
219 | } | |
220 | ||
221 | @Override | |
222 | public <T extends Edge> T getEdgeFrom(Node node) { | |
223 |
1
1. getEdgeFrom : mutated return of Object value for org/graphstream/graph/implementations/AdjacencyListNode::getEdgeFrom to ( if (x != null) null else throw new RuntimeException ) → NO_COVERAGE |
return locateEdge(node, I_EDGE); |
224 | } | |
225 | ||
226 | @Override | |
227 | public <T extends Edge> T getEdgeToward(Node node) { | |
228 |
1
1. getEdgeToward : mutated return of Object value for org/graphstream/graph/implementations/AdjacencyListNode::getEdgeToward to ( if (x != null) null else throw new RuntimeException ) → KILLED |
return locateEdge(node, O_EDGE); |
229 | } | |
230 | ||
231 | // *** Iterators *** | |
232 | ||
233 | protected class EdgeIterator<T extends Edge> implements Iterator<T> { | |
234 | protected int iPrev, iNext, iEnd; | |
235 | ||
236 | protected EdgeIterator(char type) { | |
237 | iPrev = -1; | |
238 | iNext = 0; | |
239 | iEnd = degree; | |
240 |
1
1. |
if (type == I_EDGE) |
241 | iEnd = oStart; | |
242 |
1
1. |
else if (type == O_EDGE) |
243 | iNext = ioStart; | |
244 | } | |
245 | ||
246 | public boolean hasNext() { | |
247 |
4
1. hasNext : replaced return of integer sized value with (x == 0 ? 1 : 0) → SURVIVED 2. hasNext : changed conditional boundary → KILLED 3. hasNext : negated conditional → KILLED 4. hasNext : replaced return of integer sized value with (x == 0 ? 1 : 0) → KILLED |
return iNext < iEnd; |
248 | } | |
249 | ||
250 | @SuppressWarnings("unchecked") | |
251 | public T next() { | |
252 |
2
1. next : changed conditional boundary → SURVIVED 2. next : negated conditional → KILLED |
if (iNext >= iEnd) |
253 | throw new NoSuchElementException(); | |
254 |
1
1. next : Replaced integer addition with subtraction → SURVIVED |
iPrev = iNext++; |
255 |
1
1. next : mutated return of Object value for org/graphstream/graph/implementations/AdjacencyListNode$EdgeIterator::next to ( if (x != null) null else throw new RuntimeException ) → SURVIVED |
return (T) edges[iPrev]; |
256 | } | |
257 | ||
258 | public void remove() { | |
259 |
1
1. remove : negated conditional → KILLED |
if (iPrev == -1) |
260 | throw new IllegalStateException(); | |
261 | AbstractEdge e = edges[iPrev]; | |
262 | // do not call the callback because we already know the index | |
263 |
2
1. remove : removed call to org/graphstream/graph/implementations/AbstractGraph::removeEdge → SURVIVED 2. remove : negated conditional → KILLED |
graph.removeEdge(e, true, e.source != AdjacencyListNode.this, |
264 |
1
1. remove : negated conditional → SURVIVED |
e.target != AdjacencyListNode.this); |
265 |
1
1. remove : removed call to org/graphstream/graph/implementations/AdjacencyListNode::removeEdge → SURVIVED |
removeEdge(iPrev); |
266 | iNext = iPrev; | |
267 | iPrev = -1; | |
268 |
1
1. remove : Replaced integer subtraction with addition → KILLED |
iEnd--; |
269 | } | |
270 | } | |
271 | ||
272 | @Override | |
273 | public <T extends Edge> Iterator<T> getEdgeIterator() { | |
274 |
1
1. getEdgeIterator : mutated return of Object value for org/graphstream/graph/implementations/AdjacencyListNode::getEdgeIterator to ( if (x != null) null else throw new RuntimeException ) → KILLED |
return new EdgeIterator<T>(IO_EDGE); |
275 | } | |
276 | ||
277 | @Override | |
278 | public <T extends Edge> Iterator<T> getEnteringEdgeIterator() { | |
279 |
1
1. getEnteringEdgeIterator : mutated return of Object value for org/graphstream/graph/implementations/AdjacencyListNode::getEnteringEdgeIterator to ( if (x != null) null else throw new RuntimeException ) → NO_COVERAGE |
return new EdgeIterator<T>(I_EDGE); |
280 | } | |
281 | ||
282 | @Override | |
283 | public <T extends Edge> Iterator<T> getLeavingEdgeIterator() { | |
284 |
1
1. getLeavingEdgeIterator : mutated return of Object value for org/graphstream/graph/implementations/AdjacencyListNode::getLeavingEdgeIterator to ( if (x != null) null else throw new RuntimeException ) → NO_COVERAGE |
return new EdgeIterator<T>(O_EDGE); |
285 | } | |
286 | } | |
Mutations | ||
78 |
1.1 2.2 |
|
79 |
1.1 |
|
80 |
1.1 2.2 |
|
88 |
1.1 |
|
90 |
1.1 |
|
93 |
1.1 2.2 3.3 |
|
94 |
1.1 |
|
95 |
1.1 |
|
96 |
1.1 |
|
100 |
1.1 2.2 |
|
101 |
1.1 |
|
106 |
1.1 2.2 |
|
107 |
1.1 |
|
108 |
1.1 |
|
113 |
1.1 |
|
114 |
1.1 |
|
115 |
1.1 |
|
125 |
1.1 |
|
126 |
1.1 2.2 |
|
127 |
1.1 |
|
128 |
1.1 |
|
134 |
1.1 |
|
135 |
1.1 |
|
136 |
1.1 |
|
139 |
1.1 |
|
140 |
1.1 |
|
141 |
1.1 |
|
142 |
1.1 |
|
145 |
1.1 |
|
146 |
1.1 |
|
147 |
1.1 |
|
148 |
1.1 |
|
156 |
1.1 |
|
158 |
1.1 |
|
160 |
1.1 |
|
161 |
1.1 |
|
163 |
1.1 |
|
168 |
1.1 |
|
176 |
1.1 |
|
181 |
1.1 |
|
186 |
1.1 2.2 |
|
192 |
1.1 2.2 3.3 4.4 |
|
195 |
1.1 |
|
201 |
1.1 2.2 3.3 4.4 |
|
204 |
1.1 |
|
210 |
1.1 2.2 3.3 4.4 |
|
213 |
1.1 2.2 |
|
218 |
1.1 |
|
223 |
1.1 |
|
228 |
1.1 |
|
240 |
1.1 |
|
242 |
1.1 |
|
247 |
1.1 2.2 3.3 4.4 |
|
252 |
1.1 2.2 |
|
254 |
1.1 |
|
255 |
1.1 |
|
259 |
1.1 |
|
263 |
1.1 2.2 |
|
264 |
1.1 |
|
265 |
1.1 |
|
268 |
1.1 |
|
274 |
1.1 |
|
279 |
1.1 |
|
284 |
1.1 |