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) Lumiera.org
5  2023, Hermann Vosseler <Ichthyostega@web.de>
6 
7  This program is free software; you can redistribute it and/or
8  modify it under the terms of the GNU General Public License as
9  published by the Free Software Foundation; either version 2 of
10  the License, or (at your option) any later version.
11 
12  This program is distributed in the hope that it will be useful,
13  but WITHOUT ANY WARRANTY; without even the implied warranty of
14  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15  GNU General Public License for more details.
16 
17  You should have received a copy of the GNU General Public License
18  along with this program; if not, write to the Free Software
19  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
20 
21 * *****************************************************/
22 
41 #include "lib/test/run.hpp"
42 #include "lib/test/test-helper.hpp"
43 #include "lib/format-cout.hpp"
44 #include "lib/format-util.hpp"
45 #include "lib/format-string.hpp"
46 #include "lib/split-splice.hpp"
47 #include "lib/nocopy.hpp"
48 #include "lib/util.hpp"
49 
50 #include <utility>
51 #include <string>
52 #include <list>
53 
54 
55 namespace lib {
56 namespace test {
57 
58  using util::_Fmt;
59  using util::isnil;
60  using util::getAddr;
61  using util::isSameObject;
62  using std::string;
63  using std::move;
64 
65  namespace {// Test Fixture....
66 
73  struct Seg
74  : util::MoveOnly
75  {
76  int start;
77  int after;
78  bool empty;
79 
80  ~Seg()
81  {
82  check -= id;
83  if (id) --cnt;
84  }
85 
86  Seg (int s, int a, bool nil=false)
87  : start{s}
88  , after{a}
89  , empty{nil}
90  , id{++idGen}
91  {
92  ++cnt;
93  check += id;
94  }
95 
97  Seg (Seg const& ref, int s, int a)
98  : start{s}
99  , after{a}
100  , empty{ref.empty}
101  , id{ref.id}
102  {
103  ++cnt;
104  check += id;
105  }
106 
108  Seg (Seg&& rr)
109  : start{rr.start}
110  , after{rr.after}
111  , empty{rr.empty}
112  , id{0}
113  {
114  std::swap (id, rr.id);
115  }//transfer identity
116 
117  operator string() const
118  {
119  return _Fmt{"[%i%s%i["}
120  % start
121  % (empty? "~":"_")
122  % after
123  ;
124  }
125 
126 
127  //-- Diagnostics --
128  uint id;
129  static uint idGen;
130  static size_t cnt;
131  static size_t check;
132  };
133 
134  // Storage for static ID-Generator
135  size_t Seg::check{0};
136  size_t Seg::cnt{0};
137  uint Seg::idGen{0};
138 
139  const int SMIN = -100;
140  const int SMAX = +100;
141 
151  struct SegL
152  : std::list<Seg>
153  {
154  SegL (std::initializer_list<int> breaks)
155  {
156  int p = SMIN;
157  bool bound = true;
158  for (int b : breaks)
159  {
160  emplace_back (p,b, bound);
161  bound = false;
162  p = b;
163  }
164  emplace_back(p,SMAX, true);
165  }
166 
167  SegL()
168  : SegL({})
169  { }
170 
171  // using standard copy
172 
173  operator string() const
174  {
175  return renderContent() + assess();
176  }
177 
178  bool
179  isValid() const
180  {
181  return isnil (this->assess());
182  }
183 
184  string
185  renderContent() const
186  {
187  return "├"+util::join(*this,"")+"┤";
188  }
189 
190  string
191  assess() const
192  {
193  string diagnosis;
194  if (empty())
195  diagnosis = "!empty!";
196  else
197  {
198  if (front().start != SMIN)
199  diagnosis += "missing-lower-bound!";
200  if (back().after != SMAX)
201  diagnosis += "missing-upper-bound!";
202  int p = SMIN;
203  for (auto const& s : *this)
204  {
205  if (s.start != p)
206  diagnosis += _Fmt{"!gap_%i<>%i_!"} % p % s.start;
207  if (s.start == s.after)
208  diagnosis += _Fmt{"!degen_%i_!"} % s.start;
209  if (s.start > s.after)
210  diagnosis += _Fmt{"!order_%i>%i_!"} % s.start % s.after;
211  p = s.after;
212  }
213  }
214  return diagnosis;
215  }
216  };
217 
218 
219 
220 
221  /* ======= Split/Splice-Algo Setup ======= */
222 
223  using OptInt = std::optional<int>;
224  using Iter = typename SegL::iterator;
225 
239  auto
240  invokeSplitSplice (SegL& segs, OptInt startNew, OptInt afterNew)
241  {
242  /*---configure-contextually-bound-Functors--------------------*/
243  auto getStart = [](Iter elm) -> int { return elm->start; };
244  auto getAfter = [](Iter elm) -> int { return elm->after; };
245  auto createSeg= [&](Iter pos, int start, int after) -> Iter { return segs.emplace (pos, start, after); };
246  auto emptySeg = [&](Iter pos, int start, int after) -> Iter { return segs.emplace (pos, start, after, true); };
247  auto cloneSeg = [&](Iter pos, int start, int after, Iter src) -> Iter { return segs.emplace (pos, *src, start, after); };
248  auto discard = [&](Iter pos, Iter after) -> Iter { return segs.erase (pos,after); };
249 
250 
251  lib::splitsplice::Algo splicer{ getStart
252  , getAfter
253  , createSeg
254  , emptySeg
255  , cloneSeg
256  , discard
257  , SMAX
258  , segs.begin(),segs.end()
259  , startNew, afterNew
260  };
261  splicer.determineRelations();
262  return splicer.performSplitSplice();
263  }
264  }//(End)Test Fixture
265 
266 
267 
268 
269  /****************************************************************************/
278  class SplitSplice_test : public Test
279  {
280 
281  virtual void
282  run (Arg)
283  {
284  demonstrate_usage();
285  verify_testFixture();
286  verify_standardCases();
287  verify_cornerCases();
288  verify_integrity();
289 
290  // no memory leaked
291  CHECK (0 == Seg::check);
292  CHECK (0 == Seg::cnt);
293  }
294 
295 
299  void
300  demonstrate_usage()
301  {
302  SegL segmentation;
303  CHECK (segmentation == "├[-100~100[┤"_expect);
304 
305  OptInt startNew{5},
306  afterNew{23};
307 
308  invokeSplitSplice (segmentation, startNew, afterNew);
309 
310  // The given segmentation was modified by side-effect
311  // - a new segment [5...23[ has been inserted in the middle
312  // - suitably adapted empty predecessor and successor segments
313  CHECK (segmentation == "├[-100~5[[5_23[[23~100[┤"_expect);
314 
315  // The modified segmentation still seamlessly covers the whole axis
316  CHECK (segmentation.isValid());
317  }
318 
319 
320 
322  void
323  verify_testFixture()
324  {
325  CHECK (0 == Seg::check);
326  Seg::idGen = 0;
327  {
328  Seg x{1,3}; // a segment 1 (inclusive) to 3 (exclusive)
329  Seg u{2,4,true}; // an "empty" segment 2 (incl) to 4 (excl)
330  CHECK (x == "[1_3["_expect);
331  CHECK (u == "[2~4["_expect); // "empty" interval is marked with '~' in string stylisation
332  CHECK (3 == Seg::check);
333  CHECK (2 == Seg::cnt);
334 
335  Seg z{move(u)};
336  CHECK (z == "[2~4["_expect);
337  CHECK (3 == Seg::check);
338  CHECK (2 == Seg::cnt); // the "dead" instance u is not counted
339  CHECK (0 == u.id); // (its ID has been reset to zero in move-ctor)
340  CHECK (2 == z.id);
341 
342  SegL l1; // default ctor always adds an empty base segment -100 ... +100
343  SegL l2{3};
344  SegL l3{5,-5,10};
345  CHECK (l1 == "├[-100~100[┤"_expect);
346  CHECK (l2 == "├[-100~3[[3~100[┤"_expect);
347  CHECK (l3 == "├[-100~5[[5_-5[[-5_10[[10~100[┤!order_5>-5_!"_expect);
348 
349  CHECK (l1.isValid());
350  CHECK (l2.isValid());
351  CHECK (not l3.isValid()); // l3 violates validity condition, because segment [5 ... -5[ is reversed
352  CHECK (l3.assess() == "!order_5>-5_!"_expect);
353 
354  CHECK ( 9 == Seg::cnt ); // 9 objects are alive
355  CHECK ( 9 == Seg::idGen); // ID generator sticks at 9
356  CHECK (45 == Seg::check); // checksum 1+..+9
357 
358  l3.erase(l3.begin());
359  CHECK (l3.assess() == "missing-lower-bound!!gap_-100<>5_!!order_5>-5_!"_expect);
360  CHECK ( 8 == Seg::cnt ); // also one object less alive
361 
362  l3.begin()->after = 5; // manipulate first segment to make it degenerate (empty
363  CHECK (l3.renderContent() == "├[5_5[[-5_10[[10~100[┤"_expect);
364  CHECK (l3.assess() == "missing-lower-bound!!gap_-100<>5_!!degen_5_!!gap_5<>-5_!"_expect);
365  l3.clear();
366  CHECK (l3.assess() == "!empty!"_expect);
367 
368  CHECK ( 5 == Seg::cnt );
369  CHECK ( 9 == Seg::idGen);
370  CHECK (15 == Seg::check);
371  }
372  // all objects go out of scope
373  CHECK (0 == Seg::cnt );
374  CHECK (0 == Seg::check);
375  CHECK (9 == Seg::idGen);
376  }
377 
378 
379 
383  void
384  verify_standardCases()
385  {
386  auto testCase = [](SegL segmentation
387  ,int startNew
388  ,int afterNew
389  ,ExpectString expectedResult)
390  {
391  OptInt startSpec{startNew},
392  afterSpec{afterNew};
393 
394  invokeSplitSplice (segmentation, startSpec, afterSpec);
395  CHECK (segmentation == expectedResult);
396  CHECK (segmentation.isValid());
397  };
399  testCase (SegL{}, -23,24, "├[-100~-23[[-23_24[[24~100[┤"_expect); // simple segment into empty axis
400 
401  // insert smaller segment
402  testCase (SegL{5,10}, 2,3, "├[-100~2[[2_3[[3~5[[5_10[[10~100[┤"_expect); // smaller segment left spaced off
403  testCase (SegL{5,10}, 4,5, "├[-100~4[[4_5[[5_10[[10~100[┤"_expect); // left adjacent
404  testCase (SegL{5,10}, 4,8, "├[-100~4[[4_8[[8_10[[10~100[┤"_expect); // left overlapping
405  testCase (SegL{5,10}, 5,8, "├[-100~5[[5_8[[8_10[[10~100[┤"_expect); // left inside justified
406  testCase (SegL{5,10}, 6,8, "├[-100~5[[5_6[[6_8[[8_10[[10~100[┤"_expect); // smaller segment complete inside
407  testCase (SegL{5,10}, 7,10, "├[-100~5[[5_7[[7_10[[10~100[┤"_expect); // right inside justified
408  testCase (SegL{5,10}, 9,13, "├[-100~5[[5_9[[9_13[[13~100[┤"_expect); // right overlapping
409  testCase (SegL{5,10}, 10,13, "├[-100~5[[5_10[[10_13[[13~100[┤"_expect); // right adjacent
410  testCase (SegL{5,10}, 13,23, "├[-100~5[[5_10[[10~13[[13_23[[23~100[┤"_expect); // right spaced off
411 
412  // insert identical segment
413  testCase (SegL{5,10}, 5,10, "├[-100~5[[5_10[[10~100[┤"_expect); // identical size replacement
414 
415  // insert larger segment
416  testCase (SegL{5,10}, 3,10, "├[-100~3[[3_10[[10~100[┤"_expect); // larger segment right aligned
417  testCase (SegL{5,10}, 3,23, "├[-100~3[[3_23[[23~100[┤"_expect); // larger segment overarching
418  testCase (SegL{5,10}, 5,23, "├[-100~5[[5_23[[23~100[┤"_expect); // larger segment left aligned
419  }
420 
421 
422 
426  void
427  verify_cornerCases()
428  {
429  auto testCase = [](SegL segmentation
430  ,OptInt startNew // Note: these are optional...
431  ,OptInt afterNew
432  ,ExpectString expectedResult)
433  {
434  invokeSplitSplice (segmentation, startNew, afterNew);
435  CHECK (segmentation == expectedResult);
436  CHECK (segmentation.isValid());
437  };
438  auto x = std::nullopt;
440  testCase (SegL{}, 3,2, "├[-100~2[[2_3[[3~100[┤"_expect); // flipped interval spec is reoriented
442  testCase (SegL{}, 3,x, "├[-100~3[[3_100[┤"_expect); // expanded until domain end
443  testCase (SegL{}, x,5, "├[-100_5[[5~100[┤"_expect); // expanded to start of domain
445  testCase (SegL{4,6}, 5,x, "├[-100~4[[4_5[[5_6[[6~100[┤"_expect); // expanded until end of enclosing segment
446  testCase (SegL{4,6}, x,5, "├[-100~4[[4_5[[5_6[[6~100[┤"_expect); // expanded to start of enclosing segment
448  testCase (SegL{4,6}, 3,x, "├[-100~3[[3_4[[4_6[[6~100[┤"_expect); // expanded to fill gap to next segment
449  testCase (SegL{4,6}, x,3, "├[-100_3[[3~4[[4_6[[6~100[┤"_expect); // expanded to cover predecessor completely
450  testCase (SegL{4,6}, 4,x, "├[-100~4[[4_6[[6~100[┤"_expect); // expanded to cover (replace) successor
451  testCase (SegL{4,6}, x,4, "├[-100_4[[4_6[[6~100[┤"_expect); // expanded to cover (replace) predecessor
453  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)
454  testCase (SegL{4,6}, x,7, "├[-100~4[[4_6[[6_7[[7~100[┤"_expect); // fill gap between predecessor and given new segment end
455  testCase (SegL{4,6}, 6,x, "├[-100~4[[4_6[[6_100[┤"_expect); // expand to cover (replace) the following segment until domain end
456  testCase (SegL{4,6}, x,6, "├[-100~4[[4_6[[6~100[┤"_expect); // expanded to cover (replace) the preceding segment
458  testCase (SegL{}, x,x, "├[-100_100[┤"_expect); // without any specification, the whole domain is covered
459  testCase (SegL{4}, x,x, "├[-100~4[[4_100[┤"_expect); // otherwise, without any spec the last segment is replaced
460  testCase (SegL{4,6}, x,x, "├[-100~4[[4_6[[6_100[┤"_expect);
462  testCase (SegL{4,5,6,8}, 3,6, "├[-100~3[[3_6[[6_8[[8~100[┤"_expect); // spanning and thus replacing multiple segments
463  testCase (SegL{4,5,6,8}, 4,6, "├[-100~4[[4_6[[6_8[[8~100[┤"_expect);
464  testCase (SegL{4,5,6,8}, 4,7, "├[-100~4[[4_7[[7_8[[8~100[┤"_expect);
465  testCase (SegL{4,5,6,8}, 3,7, "├[-100~3[[3_7[[7_8[[8~100[┤"_expect);
466  testCase (SegL{4,5,6,8}, 3,8, "├[-100~3[[3_8[[8~100[┤"_expect);
467  testCase (SegL{4,5,6,8}, 4,8, "├[-100~4[[4_8[[8~100[┤"_expect);
468  testCase (SegL{4,5,6,8}, 4,9, "├[-100~4[[4_9[[9~100[┤"_expect);
469  testCase (SegL{4,5,6,8}, 5,9, "├[-100~4[[4_5[[5_9[[9~100[┤"_expect);
470  testCase (SegL{4,5,6,8}, 5,x, "├[-100~4[[4_5[[5_6[[6_8[[8~100[┤"_expect);
471  testCase (SegL{4,5,7,8}, x,6, "├[-100~4[[4_5[[5_6[[6_7[[7_8[[8~100[┤"_expect);
472  }
473 
474 
475 
482  void
483  verify_integrity()
484  {
485  SegL segs{2,6};
486  CHECK (segs == "├[-100~2[[2_6[[6~100[┤"_expect);
487 
488  Iter s = segs.begin();
489  CHECK (s->start == -100);
490  CHECK (s->after == 2);
491  uint id1 = s->id;
492  void* adr1 = &(*s);
493  ++s;
494  CHECK (s->start == 2);
495  CHECK (s->after == 6);
496  uint id2 = s->id;
497  void* adr2 = &(*s);
498  ++s;
499  CHECK (s->start == 6);
500  CHECK (s->after == 100);
501  uint id3 = s->id;
502  void* adr3 = &(*s);
503 
504  auto [p,n,a] = invokeSplitSplice (segs, 3,4);
505  CHECK (5 == segs.size());
506  CHECK (segs == "├[-100~2[[2_3[[3_4[[4_6[[6~100[┤"_expect);
507 
508  s = segs.begin();
509  CHECK (s->start == -100);
510  CHECK (s->after == 2);
511  CHECK (s->id == id1);
512  CHECK (adr1 == getAddr(*s));
513  CHECK (s != p);
514  ++s;
515  CHECK (s == p);
516  CHECK (s->start == 2);
517  CHECK (s->after == 3);
518  CHECK (s->id == id2);
519  CHECK (adr2 != getAddr(*s)); // this is the first part of the split segment (new allocation)
520  ++s;
521  CHECK (s != p);
522  CHECK (s == n);
523  CHECK (s->start == 3);
524  CHECK (s->after == 4);
525  CHECK (s->id != id1);
526  CHECK (s->id != id2);
527  CHECK (s->id != id3);
528  CHECK (adr2 != getAddr(*s));
529  ++s;
530  CHECK (s != n);
531  CHECK (s != a);
532  CHECK (s->start == 4);
533  CHECK (s->after == 6);
534  CHECK (s->id != id1);
535  CHECK (s->id == id2);
536  CHECK (s->id != id3);
537  CHECK (adr2 != getAddr(*s)); // this is the second part of the split segment (new allocation)
538  ++s;
539  CHECK (s == a);
540  CHECK (s->start == 6);
541  CHECK (s->after == 100);
542  CHECK (s->id != id1);
543  CHECK (s->id != id2);
544  CHECK (s->id == id3);
545  CHECK (adr3 == getAddr(*s));
546  ++s;
547  CHECK (s == segs.end());
548  }
549  };
550 
551  LAUNCHER (SplitSplice_test, "unit common");
552 
553 
554 }} // namespace lib::test
lib::test::ExpectString
Helper to produce better diagnostic messages when comparing to an expected result string...
Definition: test-helper.hpp:323
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:151
lib::test::SplitSplice_test::verify_integrity
void verify_integrity()
Definition: split-splice-test.cpp:483
test
Definition: run.hpp:49
lib::test::SplitSplice_test::verify_standardCases
void verify_standardCases()
Definition: split-splice-test.cpp:384
util::MoveOnly
Types marked with this mix-in may be moved but not copied.
Definition: nocopy.hpp:58
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:97
lib::test::SplitSplice_test::demonstrate_usage
void demonstrate_usage()
Definition: split-splice-test.cpp:300
util::_Fmt
A front-end for using printf-style formatting.
Definition: format-string.hpp:157
lib
Implementation namespace for support and library code.
Definition: common-services.cpp:63
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:240
run.hpp
Simple 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:323
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:108
lib::splitsplice::Algo
Implementation of »SplitSplice« algorithm.
Definition: split-splice.hpp:115
lib::test::anonymous_namespace{split-splice-test.cpp}::Seg
Test Dummy: a "segment" representing an integer interval.
Definition: split-splice-test.cpp:73
lib::test::SplitSplice_test::verify_cornerCases
void verify_cornerCases()
Definition: split-splice-test.cpp:427
util::isSameObject
bool isSameObject(A const &a, B const &b)
compare plain object identity, bypassing any custom comparison operators.
Definition: util.hpp:372
lib::test::SplitSplice_test
Definition: split-splice-test.cpp:278