Lumiera  0.pre.03
»edit your freedom«
split-splice-test.cpp
Go to the documentation of this file.
1 /*
2  SplitSplice(Test) - verify interval splicing
3 
4  Copyright (C)
5  2023, Hermann Vosseler <Ichthyostega@web.de>
6 
7   **Lumiera** is free software; you can redistribute it and/or modify it
8   under the terms of the GNU General Public License as published by the
9   Free Software Foundation; either version 2 of the License, or (at your
10   option) any later version. See the file COPYING for further details.
11 
12 * *****************************************************************/
13 
32 #include "lib/test/run.hpp"
33 #include "lib/test/test-helper.hpp"
34 #include "lib/format-cout.hpp"
35 #include "lib/format-util.hpp"
36 #include "lib/format-string.hpp"
37 #include "lib/split-splice.hpp"
38 #include "lib/nocopy.hpp"
39 #include "lib/util.hpp"
40 
41 #include <utility>
42 #include <string>
43 #include <list>
44 
45 
46 namespace lib {
47 namespace test {
48 
49  using util::_Fmt;
50  using util::isnil;
51  using util::getAdr;
52  using util::isSameObject;
53  using std::string;
54  using std::move;
55 
56  namespace {// Test Fixture....
57 
64  struct Seg
65  : util::MoveOnly
66  {
67  int start;
68  int after;
69  bool empty;
70 
71  ~Seg()
72  {
73  check -= id;
74  if (id) --cnt;
75  }
76 
77  Seg (int s, int a, bool nil=false)
78  : start{s}
79  , after{a}
80  , empty{nil}
81  , id{++idGen}
82  {
83  ++cnt;
84  check += id;
85  }
86 
88  Seg (Seg const& ref, int s, int a)
89  : start{s}
90  , after{a}
91  , empty{ref.empty}
92  , id{ref.id}
93  {
94  ++cnt;
95  check += id;
96  }
97 
99  Seg (Seg&& rr)
100  : start{rr.start}
101  , after{rr.after}
102  , empty{rr.empty}
103  , id{0}
104  {
105  std::swap (id, rr.id);
106  }//transfer identity
107 
108  operator string() const
109  {
110  return _Fmt{"[%i%s%i["}
111  % start
112  % (empty? "~":"_")
113  % after
114  ;
115  }
116 
117 
118  //-- Diagnostics --
119  uint id;
120  static uint idGen;
121  static size_t cnt;
122  static size_t check;
123  };
124 
125  // Storage for static ID-Generator
126  size_t Seg::check{0};
127  size_t Seg::cnt{0};
128  uint Seg::idGen{0};
129 
130  const int SMIN = -100;
131  const int SMAX = +100;
132 
142  struct SegL
143  : std::list<Seg>
144  {
145  SegL (std::initializer_list<int> breaks)
146  {
147  int p = SMIN;
148  bool bound = true;
149  for (int b : breaks)
150  {
151  emplace_back (p,b, bound);
152  bound = false;
153  p = b;
154  }
155  emplace_back(p,SMAX, true);
156  }
157 
158  SegL()
159  : SegL({})
160  { }
161 
162  // using standard copy
163 
164  operator string() const
165  {
166  return renderContent() + assess();
167  }
168 
169  bool
170  isValid() const
171  {
172  return isnil (this->assess());
173  }
174 
175  string
176  renderContent() const
177  {
178  return "├"+util::join(*this,"")+"┤";
179  }
180 
181  string
182  assess() const
183  {
184  string diagnosis;
185  if (empty())
186  diagnosis = "!empty!";
187  else
188  {
189  if (front().start != SMIN)
190  diagnosis += "missing-lower-bound!";
191  if (back().after != SMAX)
192  diagnosis += "missing-upper-bound!";
193  int p = SMIN;
194  for (auto const& s : *this)
195  {
196  if (s.start != p)
197  diagnosis += _Fmt{"!gap_%i<>%i_!"} % p % s.start;
198  if (s.start == s.after)
199  diagnosis += _Fmt{"!degen_%i_!"} % s.start;
200  if (s.start > s.after)
201  diagnosis += _Fmt{"!order_%i>%i_!"} % s.start % s.after;
202  p = s.after;
203  }
204  }
205  return diagnosis;
206  }
207  };
208 
209 
210 
211 
212  /* ======= Split/Splice-Algo Setup ======= */
213 
214  using OptInt = std::optional<int>;
215  using Iter = typename SegL::iterator;
216 
230  auto
231  invokeSplitSplice (SegL& segs, OptInt startNew, OptInt afterNew)
232  {
233  /*---configure-contextually-bound-Functors--------------------*/
234  auto getStart = [](Iter elm) -> int { return elm->start; };
235  auto getAfter = [](Iter elm) -> int { return elm->after; };
236  auto createSeg= [&](Iter pos, int start, int after) -> Iter { return segs.emplace (pos, start, after); };
237  auto emptySeg = [&](Iter pos, int start, int after) -> Iter { return segs.emplace (pos, start, after, true); };
238  auto cloneSeg = [&](Iter pos, int start, int after, Iter src) -> Iter { return segs.emplace (pos, *src, start, after); };
239  auto discard = [&](Iter pos, Iter after) -> Iter { return segs.erase (pos,after); };
240 
241 
242  lib::splitsplice::Algo splicer{ getStart
243  , getAfter
244  , createSeg
245  , emptySeg
246  , cloneSeg
247  , discard
248  , SMAX
249  , segs.begin(),segs.end()
250  , startNew, afterNew
251  };
252  splicer.determineRelations();
253  return splicer.performSplitSplice();
254  }
255  }//(End)Test Fixture
256 
257 
258 
259 
260  /****************************************************************************/
269  class SplitSplice_test : public Test
270  {
271 
272  virtual void
273  run (Arg)
274  {
275  demonstrate_usage();
276  verify_testFixture();
277  verify_standardCases();
278  verify_cornerCases();
279  verify_integrity();
280 
281  // no memory leaked
282  CHECK (0 == Seg::check);
283  CHECK (0 == Seg::cnt);
284  }
285 
286 
290  void
291  demonstrate_usage()
292  {
293  SegL segmentation;
294  CHECK (segmentation == "├[-100~100[┤"_expect);
295 
296  OptInt startNew{5},
297  afterNew{23};
298 
299  invokeSplitSplice (segmentation, startNew, afterNew);
300 
301  // The given segmentation was modified by side-effect
302  // - a new segment [5...23[ has been inserted in the middle
303  // - suitably adapted empty predecessor and successor segments
304  CHECK (segmentation == "├[-100~5[[5_23[[23~100[┤"_expect);
305 
306  // The modified segmentation still seamlessly covers the whole axis
307  CHECK (segmentation.isValid());
308  }
309 
310 
311 
313  void
314  verify_testFixture()
315  {
316  CHECK (0 == Seg::check);
317  Seg::idGen = 0;
318  {
319  Seg x{1,3}; // a segment 1 (inclusive) to 3 (exclusive)
320  Seg u{2,4,true}; // an "empty" segment 2 (incl) to 4 (excl)
321  CHECK (x == "[1_3["_expect);
322  CHECK (u == "[2~4["_expect); // "empty" interval is marked with '~' in string stylisation
323  CHECK (3 == Seg::check);
324  CHECK (2 == Seg::cnt);
325 
326  Seg z{move(u)};
327  CHECK (z == "[2~4["_expect);
328  CHECK (3 == Seg::check);
329  CHECK (2 == Seg::cnt); // the "dead" instance u is not counted
330  CHECK (0 == u.id); // (its ID has been reset to zero in move-ctor)
331  CHECK (2 == z.id);
332 
333  SegL l1; // default ctor always adds an empty base segment -100 ... +100
334  SegL l2{3};
335  SegL l3{5,-5,10};
336  CHECK (l1 == "├[-100~100[┤"_expect);
337  CHECK (l2 == "├[-100~3[[3~100[┤"_expect);
338  CHECK (l3 == "├[-100~5[[5_-5[[-5_10[[10~100[┤!order_5>-5_!"_expect);
339 
340  CHECK (l1.isValid());
341  CHECK (l2.isValid());
342  CHECK (not l3.isValid()); // l3 violates validity condition, because segment [5 ... -5[ is reversed
343  CHECK (l3.assess() == "!order_5>-5_!"_expect);
344 
345  CHECK ( 9 == Seg::cnt ); // 9 objects are alive
346  CHECK ( 9 == Seg::idGen); // ID generator sticks at 9
347  CHECK (45 == Seg::check); // checksum 1+..+9
348 
349  l3.erase(l3.begin());
350  CHECK (l3.assess() == "missing-lower-bound!!gap_-100<>5_!!order_5>-5_!"_expect);
351  CHECK ( 8 == Seg::cnt ); // also one object less alive
352 
353  l3.begin()->after = 5; // manipulate first segment to make it degenerate (empty
354  CHECK (l3.renderContent() == "├[5_5[[-5_10[[10~100[┤"_expect);
355  CHECK (l3.assess() == "missing-lower-bound!!gap_-100<>5_!!degen_5_!!gap_5<>-5_!"_expect);
356  l3.clear();
357  CHECK (l3.assess() == "!empty!"_expect);
358 
359  CHECK ( 5 == Seg::cnt );
360  CHECK ( 9 == Seg::idGen);
361  CHECK (15 == Seg::check);
362  }
363  // all objects go out of scope
364  CHECK (0 == Seg::cnt );
365  CHECK (0 == Seg::check);
366  CHECK (9 == Seg::idGen);
367  }
368 
369 
370 
374  void
375  verify_standardCases()
376  {
377  auto testCase = [](SegL segmentation
378  ,int startNew
379  ,int afterNew
380  ,ExpectString expectedResult)
381  {
382  OptInt startSpec{startNew},
383  afterSpec{afterNew};
384 
385  invokeSplitSplice (segmentation, startSpec, afterSpec);
386  CHECK (segmentation == expectedResult);
387  CHECK (segmentation.isValid());
388  };
390  testCase (SegL{}, -23,24, "├[-100~-23[[-23_24[[24~100[┤"_expect); // simple segment into empty axis
391 
392  // insert smaller segment
393  testCase (SegL{5,10}, 2,3, "├[-100~2[[2_3[[3~5[[5_10[[10~100[┤"_expect); // smaller segment left spaced off
394  testCase (SegL{5,10}, 4,5, "├[-100~4[[4_5[[5_10[[10~100[┤"_expect); // left adjacent
395  testCase (SegL{5,10}, 4,8, "├[-100~4[[4_8[[8_10[[10~100[┤"_expect); // left overlapping
396  testCase (SegL{5,10}, 5,8, "├[-100~5[[5_8[[8_10[[10~100[┤"_expect); // left inside justified
397  testCase (SegL{5,10}, 6,8, "├[-100~5[[5_6[[6_8[[8_10[[10~100[┤"_expect); // smaller segment complete inside
398  testCase (SegL{5,10}, 7,10, "├[-100~5[[5_7[[7_10[[10~100[┤"_expect); // right inside justified
399  testCase (SegL{5,10}, 9,13, "├[-100~5[[5_9[[9_13[[13~100[┤"_expect); // right overlapping
400  testCase (SegL{5,10}, 10,13, "├[-100~5[[5_10[[10_13[[13~100[┤"_expect); // right adjacent
401  testCase (SegL{5,10}, 13,23, "├[-100~5[[5_10[[10~13[[13_23[[23~100[┤"_expect); // right spaced off
402 
403  // insert identical segment
404  testCase (SegL{5,10}, 5,10, "├[-100~5[[5_10[[10~100[┤"_expect); // identical size replacement
405 
406  // insert larger segment
407  testCase (SegL{5,10}, 3,10, "├[-100~3[[3_10[[10~100[┤"_expect); // larger segment right aligned
408  testCase (SegL{5,10}, 3,23, "├[-100~3[[3_23[[23~100[┤"_expect); // larger segment overarching
409  testCase (SegL{5,10}, 5,23, "├[-100~5[[5_23[[23~100[┤"_expect); // larger segment left aligned
410  }
411 
412 
413 
417  void
418  verify_cornerCases()
419  {
420  auto testCase = [](SegL segmentation
421  ,OptInt startNew // Note: these are optional...
422  ,OptInt afterNew
423  ,ExpectString expectedResult)
424  {
425  invokeSplitSplice (segmentation, startNew, afterNew);
426  CHECK (segmentation == expectedResult);
427  CHECK (segmentation.isValid());
428  };
429  auto x = std::nullopt;
431  testCase (SegL{}, 3,2, "├[-100~2[[2_3[[3~100[┤"_expect); // flipped interval spec is reoriented
433  testCase (SegL{}, 3,x, "├[-100~3[[3_100[┤"_expect); // expanded until domain end
434  testCase (SegL{}, x,5, "├[-100_5[[5~100[┤"_expect); // expanded to start of domain
436  testCase (SegL{4,6}, 5,x, "├[-100~4[[4_5[[5_6[[6~100[┤"_expect); // expanded until end of enclosing segment
437  testCase (SegL{4,6}, x,5, "├[-100~4[[4_5[[5_6[[6~100[┤"_expect); // expanded to start of enclosing segment
439  testCase (SegL{4,6}, 3,x, "├[-100~3[[3_4[[4_6[[6~100[┤"_expect); // expanded to fill gap to next segment
440  testCase (SegL{4,6}, x,3, "├[-100_3[[3~4[[4_6[[6~100[┤"_expect); // expanded to cover predecessor completely
441  testCase (SegL{4,6}, 4,x, "├[-100~4[[4_6[[6~100[┤"_expect); // expanded to cover (replace) successor
442  testCase (SegL{4,6}, x,4, "├[-100_4[[4_6[[6~100[┤"_expect); // expanded to cover (replace) predecessor
444  testCase (SegL{4,6}, 7,x, "├[-100~4[[4_6[[6~7[[7_100[┤"_expect); // shorten successor and expand new segment to end of successor (=domain end)
445  testCase (SegL{4,6}, x,7, "├[-100~4[[4_6[[6_7[[7~100[┤"_expect); // fill gap between predecessor and given new segment end
446  testCase (SegL{4,6}, 6,x, "├[-100~4[[4_6[[6_100[┤"_expect); // expand to cover (replace) the following segment until domain end
447  testCase (SegL{4,6}, x,6, "├[-100~4[[4_6[[6~100[┤"_expect); // expanded to cover (replace) the preceding segment
449  testCase (SegL{}, x,x, "├[-100_100[┤"_expect); // without any specification, the whole domain is covered
450  testCase (SegL{4}, x,x, "├[-100~4[[4_100[┤"_expect); // otherwise, without any spec the last segment is replaced
451  testCase (SegL{4,6}, x,x, "├[-100~4[[4_6[[6_100[┤"_expect);
453  testCase (SegL{4,5,6,8}, 3,6, "├[-100~3[[3_6[[6_8[[8~100[┤"_expect); // spanning and thus replacing multiple segments
454  testCase (SegL{4,5,6,8}, 4,6, "├[-100~4[[4_6[[6_8[[8~100[┤"_expect);
455  testCase (SegL{4,5,6,8}, 4,7, "├[-100~4[[4_7[[7_8[[8~100[┤"_expect);
456  testCase (SegL{4,5,6,8}, 3,7, "├[-100~3[[3_7[[7_8[[8~100[┤"_expect);
457  testCase (SegL{4,5,6,8}, 3,8, "├[-100~3[[3_8[[8~100[┤"_expect);
458  testCase (SegL{4,5,6,8}, 4,8, "├[-100~4[[4_8[[8~100[┤"_expect);
459  testCase (SegL{4,5,6,8}, 4,9, "├[-100~4[[4_9[[9~100[┤"_expect);
460  testCase (SegL{4,5,6,8}, 5,9, "├[-100~4[[4_5[[5_9[[9~100[┤"_expect);
461  testCase (SegL{4,5,6,8}, 5,x, "├[-100~4[[4_5[[5_6[[6_8[[8~100[┤"_expect);
462  testCase (SegL{4,5,7,8}, x,6, "├[-100~4[[4_5[[5_6[[6_7[[7_8[[8~100[┤"_expect);
463  }
464 
465 
466 
473  void
474  verify_integrity()
475  {
476  SegL segs{2,6};
477  CHECK (segs == "├[-100~2[[2_6[[6~100[┤"_expect);
478 
479  Iter s = segs.begin();
480  CHECK (s->start == -100);
481  CHECK (s->after == 2);
482  uint id1 = s->id;
483  void* adr1 = &(*s);
484  ++s;
485  CHECK (s->start == 2);
486  CHECK (s->after == 6);
487  uint id2 = s->id;
488  void* adr2 = &(*s);
489  ++s;
490  CHECK (s->start == 6);
491  CHECK (s->after == 100);
492  uint id3 = s->id;
493  void* adr3 = &(*s);
494 
495  auto [p,n,a] = invokeSplitSplice (segs, 3,4);
496  CHECK (5 == segs.size());
497  CHECK (segs == "├[-100~2[[2_3[[3_4[[4_6[[6~100[┤"_expect);
498 
499  s = segs.begin();
500  CHECK (s->start == -100);
501  CHECK (s->after == 2);
502  CHECK (s->id == id1);
503  CHECK (adr1 == getAdr(*s));
504  CHECK (s != p);
505  ++s;
506  CHECK (s == p);
507  CHECK (s->start == 2);
508  CHECK (s->after == 3);
509  CHECK (s->id == id2);
510  CHECK (adr2 != getAdr(*s)); // this is the first part of the split segment (new allocation)
511  ++s;
512  CHECK (s != p);
513  CHECK (s == n);
514  CHECK (s->start == 3);
515  CHECK (s->after == 4);
516  CHECK (s->id != id1);
517  CHECK (s->id != id2);
518  CHECK (s->id != id3);
519  CHECK (adr2 != getAdr(*s));
520  ++s;
521  CHECK (s != n);
522  CHECK (s != a);
523  CHECK (s->start == 4);
524  CHECK (s->after == 6);
525  CHECK (s->id != id1);
526  CHECK (s->id == id2);
527  CHECK (s->id != id3);
528  CHECK (adr2 != getAdr(*s)); // this is the second part of the split segment (new allocation)
529  ++s;
530  CHECK (s == a);
531  CHECK (s->start == 6);
532  CHECK (s->after == 100);
533  CHECK (s->id != id1);
534  CHECK (s->id != id2);
535  CHECK (s->id == id3);
536  CHECK (adr3 == getAdr(*s));
537  ++s;
538  CHECK (s == segs.end());
539  }
540  };
541 
542  LAUNCHER (SplitSplice_test, "unit common");
543 
544 
545 }} // namespace lib::test
lib::test::ExpectString
Helper to produce better diagnostic messages when comparing to an expected result string...
Definition: test-helper.hpp:327
format-cout.hpp
Automatically use custom string conversion in C++ stream output.
lib::test::anonymous_namespace{split-splice-test.cpp}::SegL
Test-Segmentation comprised of a sequence of Seg entries.
Definition: split-splice-test.cpp:142
lib::test::SplitSplice_test::verify_integrity
void verify_integrity()
Definition: split-splice-test.cpp:474
test
Definition: run.hpp:40
lib::test::SplitSplice_test::verify_standardCases
void verify_standardCases()
Definition: split-splice-test.cpp:375
util::MoveOnly
Types marked with this mix-in may be moved but not copied.
Definition: nocopy.hpp:49
format-string.hpp
Front-end for printf-style string template interpolation.
lib::test::anonymous_namespace{split-splice-test.cpp}::Seg::Seg
Seg(Seg const &ref, int s, int a)
create a clone, but modify bounds
Definition: split-splice-test.cpp:88
lib::test::SplitSplice_test::demonstrate_usage
void demonstrate_usage()
Definition: split-splice-test.cpp:291
util::_Fmt
A front-end for using printf-style formatting.
Definition: format-string.hpp:148
lib
Implementation namespace for support and library code.
Definition: common-services.cpp:54
nocopy.hpp
Mix-Ins to allow or prohibit various degrees of copying and cloning.
lib::test::anonymous_namespace{split-splice-test.cpp}::invokeSplitSplice
auto invokeSplitSplice(SegL &segs, OptInt startNew, OptInt afterNew)
Perform the »SplitSplice« Algorithm to splice a new Segment into the given segmentation of the intege...
Definition: split-splice-test.cpp:231
run.hpp
Simplistic test class runner.
util.hpp
Tiny helper functions and shortcuts to be used everywhere Consider this header to be effectively incl...
test-helper.hpp
A collection of frequently used helper functions to support unit testing.
lib::test::SplitSplice_test::verify_testFixture
void verify_testFixture()
Definition: split-splice-test.cpp:314
format-util.hpp
Collection of small helpers and convenience shortcuts for diagnostics & formatting.
lib::test::anonymous_namespace{split-splice-test.cpp}::Seg::Seg
Seg(Seg &&rr)
move-init: causes source-ref to be invalidated
Definition: split-splice-test.cpp:99
lib::splitsplice::Algo
Implementation of »SplitSplice« algorithm.
Definition: split-splice.hpp:106
lib::test::anonymous_namespace{split-splice-test.cpp}::Seg
Test Dummy: a "segment" representing an integer interval.
Definition: split-splice-test.cpp:64
lib::test::SplitSplice_test::verify_cornerCases
void verify_cornerCases()
Definition: split-splice-test.cpp:418
util::isSameObject
bool isSameObject(A const &a, B const &b)
compare plain object identity, based directly on the referee&#39;s memory identities. ...
Definition: util.hpp:421
lib::test::SplitSplice_test
Definition: split-splice-test.cpp:269