1#!/usr/bin/env python3
2#  Copyright 2016 Google Inc. All Rights Reserved.
3#
4# Licensed under the Apache License, Version 2.0 (the "License");
5# you may not use this file except in compliance with the License.
6# You may obtain a copy of the License at
7#
8#      http://www.apache.org/licenses/LICENSE-2.0
9#
10# Unless required by applicable law or agreed to in writing, software
11# distributed under the License is distributed on an "AS-IS" BASIS,
12# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13# See the License for the specific language governing permissions and
14# limitations under the License.
15
16from fruit_test_common import *
17
18COMMON_DEFINITIONS = '''
19    #include "test_common.h"
20
21    #define IN_FRUIT_CPP_FILE 1
22    #include <fruit/impl/data_structures/semistatic_graph.templates.h>
23
24    using namespace std;
25    using namespace fruit::impl;
26
27    using Graph = SemistaticGraph<int, const char*>;
28    using node_iterator = Graph::node_iterator;
29    using edge_iterator = Graph::edge_iterator;
30
31    vector<int> no_neighbors{};
32
33    struct SimpleNode {
34      int id;
35      const char* value;
36      const vector<int>* neighbors;
37      bool is_terminal;
38
39      int getId() { return id; }
40      const char* getValue() { return value; }
41      bool isTerminal() { return is_terminal; }
42      vector<int>::const_iterator getEdgesBegin() { return neighbors->begin(); }
43      vector<int>::const_iterator getEdgesEnd() { return neighbors->end(); }
44    };
45    '''
46
47def test_empty():
48    source = '''
49        int main() {
50          MemoryPool memory_pool;
51          vector<SimpleNode> values{};
52
53          Graph graph(values.begin(), values.end(), memory_pool);
54          Assert(graph.find(0) == graph.end());
55          Assert(graph.find(2) == graph.end());
56          Assert(graph.find(5) == graph.end());
57          const Graph& cgraph = graph;
58          Assert(cgraph.find(0) == cgraph.end());
59          Assert(cgraph.find(2) == cgraph.end());
60          Assert(cgraph.find(5) == cgraph.end());
61        }
62        '''
63    expect_success(
64        COMMON_DEFINITIONS,
65        source,
66        locals())
67
68def test_1_node_no_edges():
69    source = '''
70        int main() {
71          MemoryPool memory_pool;
72          vector<SimpleNode> values{{2, "foo", &no_neighbors, false}};
73
74          Graph graph(values.begin(), values.end(), memory_pool);
75          Assert(graph.find(0) == graph.end());
76          Assert(!(graph.find(2) == graph.end()));
77          Assert(graph.at(2).getNode() == string("foo"));
78          Assert(graph.at(2).isTerminal() == false);
79          Assert(graph.find(5) == graph.end());
80          const Graph& cgraph = graph;
81          Assert(cgraph.find(0) == cgraph.end());
82          Assert(!(cgraph.find(2) == cgraph.end()));
83          Assert(cgraph.find(2).getNode() == string("foo"));
84          Assert(cgraph.find(2).isTerminal() == false);
85          Assert(cgraph.find(5) == cgraph.end());
86        }
87        '''
88    expect_success(
89        COMMON_DEFINITIONS,
90        source,
91        locals())
92
93def test_1_node_no_edges_terminal():
94    source = '''
95        int main() {
96          MemoryPool memory_pool;
97          vector<SimpleNode> values{{2, "foo", &no_neighbors, true}};
98
99          Graph graph(values.begin(), values.end(), memory_pool);
100          Assert(graph.find(0) == graph.end());
101          Assert(!(graph.find(2) == graph.end()));
102          Assert(graph.at(2).getNode() == string("foo"));
103          Assert(graph.at(2).isTerminal() == true);
104          Assert(graph.find(5) == graph.end());
105          const Graph& cgraph = graph;
106          Assert(cgraph.find(0) == cgraph.end());
107          Assert(!(cgraph.find(2) == cgraph.end()));
108          Assert(cgraph.find(2).getNode() == string("foo"));
109          Assert(cgraph.find(2).isTerminal() == true);
110          Assert(cgraph.find(5) == cgraph.end());
111        }
112        '''
113    expect_success(
114        COMMON_DEFINITIONS,
115        source,
116        locals())
117
118def test_1_node_self_edge():
119    source = '''
120        int main() {
121          MemoryPool memory_pool;
122          vector<int> neighbors = {2};
123          vector<SimpleNode> values{{2, "foo", &neighbors, false}};
124
125          Graph graph(values.begin(), values.end(), memory_pool);
126          Assert(graph.find(0) == graph.end());
127          Assert(!(graph.find(2) == graph.end()));
128          Assert(graph.at(2).getNode() == string("foo"));
129          Assert(graph.at(2).isTerminal() == false);
130          edge_iterator itr = graph.at(2).neighborsBegin();
131          (void)itr;
132          Assert(itr.getNodeIterator(graph.begin()).getNode() == string("foo"));
133          Assert(itr.getNodeIterator(graph.begin()).isTerminal() == false);
134          Assert(graph.find(5) == graph.end());
135          const Graph& cgraph = graph;
136          Assert(cgraph.find(0) == cgraph.end());
137          Assert(!(cgraph.find(2) == cgraph.end()));
138          Assert(cgraph.find(2).getNode() == string("foo"));
139          Assert(cgraph.find(2).isTerminal() == false);
140        }
141        '''
142    expect_success(
143        COMMON_DEFINITIONS,
144        source,
145        locals())
146
147def test_2_nodes_one_edge():
148    source = '''
149        int main() {
150          MemoryPool memory_pool;
151          vector<int> neighbors = {2};
152          vector<SimpleNode> values{{2, "foo", &no_neighbors, false}, {3, "bar", &neighbors, false}};
153
154          Graph graph(values.begin(), values.end(), memory_pool);
155          Assert(graph.find(0) == graph.end());
156          Assert(!(graph.find(2) == graph.end()));
157          Assert(graph.at(2).getNode() == string("foo"));
158          Assert(graph.at(2).isTerminal() == false);
159          Assert(graph.at(3).getNode() == string("bar"));
160          Assert(graph.at(3).isTerminal() == false);
161          edge_iterator itr = graph.at(3).neighborsBegin();
162          (void)itr;
163          Assert(itr.getNodeIterator(graph.begin()).getNode() == string("foo"));
164          Assert(itr.getNodeIterator(graph.begin()).isTerminal() == false);
165          Assert(graph.find(5) == graph.end());
166          const Graph& cgraph = graph;
167          Assert(cgraph.find(0) == cgraph.end());
168          Assert(!(cgraph.find(2) == cgraph.end()));
169          Assert(cgraph.find(2).getNode() == string("foo"));
170          Assert(cgraph.find(2).isTerminal() == false);
171          Assert(cgraph.find(3).getNode() == string("bar"));
172          Assert(cgraph.find(3).isTerminal() == false);
173        }
174        '''
175    expect_success(
176        COMMON_DEFINITIONS,
177        source,
178        locals())
179
180def test_3_nodes_two_edges():
181    source = '''
182        int main() {
183          MemoryPool memory_pool;
184          vector<int> neighbors = {2, 4};
185          vector<SimpleNode> values{{2, "foo", &no_neighbors, false}, {3, "bar", &neighbors, false}, {4, "baz", &no_neighbors, true}};
186
187          Graph graph(values.begin(), values.end(), memory_pool);
188          Assert(graph.find(0) == graph.end());
189          Assert(!(graph.find(2) == graph.end()));
190          Assert(graph.at(2).getNode() == string("foo"));
191          Assert(graph.at(2).isTerminal() == false);
192          Assert(graph.at(3).getNode() == string("bar"));
193          Assert(graph.at(3).isTerminal() == false);
194          edge_iterator itr = graph.at(3).neighborsBegin();
195          Assert(itr.getNodeIterator(graph.begin()).getNode() == string("foo"));
196          Assert(itr.getNodeIterator(graph.begin()).isTerminal() == false);
197          ++itr;
198          Assert(itr.getNodeIterator(graph.begin()).getNode() == string("baz"));
199          Assert(itr.getNodeIterator(graph.begin()).isTerminal() == true);
200          Assert(graph.at(4).getNode() == string("baz"));
201          Assert(graph.at(4).isTerminal() == true);
202          Assert(graph.find(5) == graph.end());
203          const Graph& cgraph = graph;
204          Assert(cgraph.find(0) == cgraph.end());
205          Assert(!(cgraph.find(2) == cgraph.end()));
206          Assert(cgraph.find(2).getNode() == string("foo"));
207          Assert(cgraph.find(2).isTerminal() == false);
208          Assert(cgraph.find(3).getNode() == string("bar"));
209          Assert(cgraph.find(3).isTerminal() == false);
210          Assert(cgraph.find(4).getNode() == string("baz"));
211          Assert(cgraph.find(4).isTerminal() == true);
212          Assert(cgraph.find(5) == cgraph.end());
213        }
214        '''
215    expect_success(
216        COMMON_DEFINITIONS,
217        source,
218        locals())
219
220def test_add_node():
221    source = '''
222        int main() {
223          MemoryPool memory_pool;
224          vector<SimpleNode> old_values{{2, "foo", &no_neighbors, false}, {4, "baz", &no_neighbors, true}};
225
226          Graph old_graph(old_values.begin(), old_values.end(), memory_pool);
227          vector<int> neighbors = {2, 4};
228          vector<SimpleNode> new_values{{3, "bar", &neighbors, false}};
229
230          Graph graph(old_graph, new_values.begin(), new_values.end(), memory_pool);
231          Assert(graph.find(0) == graph.end());
232          Assert(!(graph.find(2) == graph.end()));
233          Assert(graph.at(2).getNode() == string("foo"));
234          Assert(graph.at(2).isTerminal() == false);
235          Assert(graph.at(3).getNode() == string("bar"));
236          Assert(graph.at(3).isTerminal() == false);
237          edge_iterator itr = graph.at(3).neighborsBegin();
238          Assert(itr.getNodeIterator(graph.begin()).getNode() == string("foo"));
239          Assert(itr.getNodeIterator(graph.begin()).isTerminal() == false);
240          ++itr;
241          Assert(itr.getNodeIterator(graph.begin()).getNode() == string("baz"));
242          Assert(itr.getNodeIterator(graph.begin()).isTerminal() == true);
243          Assert(graph.at(4).getNode() == string("baz"));
244          Assert(graph.at(4).isTerminal() == true);
245          Assert(graph.find(5) == graph.end());
246          const Graph& cgraph = graph;
247          Assert(cgraph.find(0) == cgraph.end());
248          Assert(!(cgraph.find(2) == cgraph.end()));
249          Assert(cgraph.find(2).getNode() == string("foo"));
250          Assert(cgraph.find(2).isTerminal() == false);
251          Assert(cgraph.find(3).getNode() == string("bar"));
252          Assert(cgraph.find(3).isTerminal() == false);
253          Assert(cgraph.find(4).getNode() == string("baz"));
254          Assert(cgraph.find(4).isTerminal() == true);
255          Assert(cgraph.find(5) == cgraph.end());
256        }
257        '''
258    expect_success(
259        COMMON_DEFINITIONS,
260        source,
261        locals())
262
263def test_set_terminal():
264    source = '''
265        int main() {
266          MemoryPool memory_pool;
267          vector<int> neighbors = {2, 4};
268          vector<SimpleNode> values{{2, "foo", &no_neighbors, false}, {3, "bar", &neighbors, false}, {4, "baz", &no_neighbors, true}};
269
270          Graph graph(values.begin(), values.end(), memory_pool);
271          graph.find(3).setTerminal();
272          Assert(graph.find(0) == graph.end());
273          Assert(!(graph.find(2) == graph.end()));
274          Assert(graph.at(2).getNode() == string("foo"));
275          Assert(graph.at(2).isTerminal() == false);
276          Assert(graph.at(3).getNode() == string("bar"));
277          Assert(graph.at(3).isTerminal() == true);
278          Assert(graph.at(4).getNode() == string("baz"));
279          Assert(graph.at(4).isTerminal() == true);
280          Assert(graph.find(5) == graph.end());
281          const Graph& cgraph = graph;
282          Assert(cgraph.find(0) == cgraph.end());
283          Assert(!(cgraph.find(2) == cgraph.end()));
284          Assert(cgraph.find(2).getNode() == string("foo"));
285          Assert(cgraph.find(3).getNode() == string("bar"));
286          Assert(cgraph.find(4).getNode() == string("baz"));
287          Assert(cgraph.find(5) == cgraph.end());
288        }
289        '''
290    expect_success(
291        COMMON_DEFINITIONS,
292        source,
293        locals())
294
295def test_move_constructor():
296    source = '''
297        int main() {
298          MemoryPool memory_pool;
299          vector<int> neighbors = {2};
300          vector<SimpleNode> values{{2, "foo", &no_neighbors, false}, {3, "bar", &neighbors, false}};
301
302          Graph graph1(values.begin(), values.end(), memory_pool);
303          Graph graph = std::move(graph1);
304          Assert(graph.find(0) == graph.end());
305          Assert(!(graph.find(2) == graph.end()));
306          Assert(graph.at(2).getNode() == string("foo"));
307          Assert(graph.at(2).isTerminal() == false);
308          Assert(graph.at(3).getNode() == string("bar"));
309          Assert(graph.at(3).isTerminal() == false);
310          edge_iterator itr = graph.at(3).neighborsBegin();
311          (void)itr;
312          Assert(itr.getNodeIterator(graph.begin()).getNode() == string("foo"));
313          Assert(itr.getNodeIterator(graph.begin()).isTerminal() == false);
314          Assert(graph.find(5) == graph.end());
315        }
316        '''
317    expect_success(
318        COMMON_DEFINITIONS,
319        source,
320        locals())
321
322def test_move_assignment():
323    source = '''
324        int main() {
325          MemoryPool memory_pool;
326          vector<int> neighbors = {2};
327          vector<SimpleNode> values{{2, "foo", &no_neighbors, false}, {3, "bar", &neighbors, false}};
328
329          Graph graph1(values.begin(), values.end(), memory_pool);
330          Graph graph;
331          graph = std::move(graph1);
332          Assert(graph.find(0) == graph.end());
333          Assert(!(graph.find(2) == graph.end()));
334          Assert(graph.at(2).getNode() == string("foo"));
335          Assert(graph.at(2).isTerminal() == false);
336          Assert(graph.at(3).getNode() == string("bar"));
337          Assert(graph.at(3).isTerminal() == false);
338          edge_iterator itr = graph.at(3).neighborsBegin();
339          (void)itr;
340          Assert(itr.getNodeIterator(graph.begin()).getNode() == string("foo"));
341          Assert(itr.getNodeIterator(graph.begin()).isTerminal() == false);
342          Assert(graph.find(5) == graph.end());
343        }
344        '''
345    expect_success(
346        COMMON_DEFINITIONS,
347        source,
348        locals())
349
350def test_incomplete_graph():
351    source = '''
352        int main() {
353          MemoryPool memory_pool;
354          vector<int> neighbors = {2};
355          vector<SimpleNode> values{{1, "foo", &neighbors, false}};
356
357          Graph graph(values.begin(), values.end(), memory_pool);
358          Assert(!(graph.find(1) == graph.end()));
359          Assert(graph.at(1).getNode() == string("foo"));
360          Assert(graph.at(1).isTerminal() == false);
361          Assert(graph.find(2) == graph.end());
362          const Graph& cgraph = graph;
363          Assert(!(cgraph.find(1) == cgraph.end()));
364          Assert(cgraph.find(1).getNode() == string("foo"));
365          Assert(cgraph.find(1).isTerminal() == false);
366          Assert(cgraph.find(2) == cgraph.end());
367        }
368        '''
369    expect_success(
370        COMMON_DEFINITIONS,
371        source,
372        locals())
373
374if __name__== '__main__':
375    main(__file__)
376