source: trunk/test/segment.cc @ 4027

// $Id: segment.cc 4027 2021-01-17 10:46:38Z peter $

/*
  Copyright (C) 2010, 2011, 2012, 2014, 2015, 2016, 2017 Peter Johansson

  This file is part of the yat library, http://dev.thep.lu.se/yat

  The yat library is free software; you can redistribute it and/or
  modify it under the terms of the GNU General Public License as
  published by the Free Software Foundation; either version 3 of the
  License, or (at your option) any later version.

  The yat library is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with yat. If not, see <http://www.gnu.org/licenses/>.
*/

#include <config.h>

#include "Suite.h"

#include "yat/utility/Segment.h"
#include "yat/utility/SegmentMap.h"
#include "yat/utility/SegmentSet.h"

using namespace theplu::yat;
using namespace utility;
void test_compare(test::Suite& suite);
void test_count(test::Suite&);
void test_erase(test::Suite&);
void test_includes(test::Suite&);
void test_insert(test::Suite&);
void test_insert_merge(test::Suite&);
void test_make_segment(test::Suite&);
void test_overlap(test::Suite&);
void test_segment(test::Suite& suite);
void test_operator(test::Suite& suite);
void test_segment_map(test::Suite& suite);
void test_segment_set(test::Suite& suite);
void test_set_bound(test::Suite&);
void test_union(test::Suite&);

template<typename T>
void avoid_pedantic_warning(T) {}

int main(int argc, char* argv[])
{
  test::Suite suite(argc, argv);

  test_compare(suite);
  test_count(suite);
  test_erase(suite);
  test_includes(suite);
  test_insert(suite);
  test_insert_merge(suite);
  test_make_segment(suite);
  test_overlap(suite);
  test_segment(suite);
  test_set_bound(suite);
  test_union(suite);

  test_segment_map(suite);
  test_segment_set(suite);

  return suite.return_value();
}


void test_compare_(test::Suite& suite, double lhs_begin, double lhs_end, 
                   double rhs_begin, double rhs_end, int expected)
{
  int result = compare_3way(Segment<double>(lhs_begin,lhs_end), 
                            Segment<double>(rhs_begin,rhs_end));
  if (result!=expected) {
    suite.add(false);
    suite.err() << "error:"
                << "[" << lhs_begin << ", " << lhs_end << ") vs "
                << "[" << rhs_begin << ", " << rhs_end << ")\n"
                << "result: " << result << "\n"
                << "expected: " << expected << "\n"
                << "\n";
  }

  compare_3way(lhs_begin, Segment<double>(rhs_begin,rhs_end));
  compare_3way(Segment<double>(rhs_begin,rhs_end), lhs_begin);
}

void test_compare(test::Suite& suite, double lhs_begin, double lhs_end, 
                  double rhs_begin, double rhs_end, int expected)
{
  test_compare_(suite, lhs_begin, lhs_end, rhs_begin, rhs_end, expected);
  // test symmetry
  test_compare_(suite, rhs_begin, rhs_end, lhs_begin, lhs_end, -expected);
}

void test_compare(test::Suite& suite)
{
  test_compare(suite, 0, 10, 20, 30, -1);
  test_compare(suite, 0, 10, 10, 30, -1);
  test_compare(suite, 0, 10, 5, 30, 0);
  test_compare(suite, 0, 10, -5, 5, 0);
  test_compare(suite, 0, 10, -5, 0, 1);
  test_compare(suite, 0, 10, -5, -1, 1);
  // zero sized 
  test_compare(suite, 0, 0, 20, 30, -1);
  test_compare(suite, 0, 0, 0, 1, -1);
  test_compare(suite, 0, 0, -5, 5, 0);
  test_compare(suite, 0, 0, -5, 0, 1);
  test_compare(suite, 0, 0, -5, -1, 1);

  // zero sized on both sides
  test_compare(suite, 0, 0, 1, 1, -1);
  test_compare(suite, 0, 0, 0, 0, 0);
  test_compare(suite, 0, 0, -1, -1, 1);
}


void test_erase(test::Suite& suite)
{
  suite.out() << "test_erase\n";
  suite.out() << "  SegmentSet\n";
  SegmentSet<double> set;
  set.insert(Segment<double>(0,2));
  set.insert(Segment<double>(10,20));
  set.insert(Segment<double>(30,50));
  SegmentSet<double>::iterator iter = set.find(15);
  set.erase(iter);
  if (!suite.add(set.size()==2))
    suite.err() << "size: " << set.size() << " expected 2\n";
  set.erase(set.begin(), set.end());
  if (!suite.add(set.size()==0))
    suite.err() << "size: " << set.size() << " expected 0\n";
  suite.out() << "  SegmentMap\n";
  typedef SegmentMap<double, std::string> Map;
  Map map;
  Map::key_type s(0,2);
  map.insert(Map::value_type(s, "aha"));
  map.erase(map.begin());
  map.erase(map.begin(), map.end());
}


void test_insert(test::Suite& suite)
{
  Segment<double> segment;
  Segment<double> segment2(0,2);

  SegmentSet<double> set;
  if (set.size()!=0) {
    suite.add(false);
    suite.err() << "expected size 0\n";
  }
  set.insert(segment2);
  if (set.size()!=1) {
    suite.add(false);
    suite.err() << "expected size 1\n";
  }
  set.insert(segment2);
  if (set.size()!=1) {
    suite.add(false);
    suite.err() << "expected size 1\n";
  }
  set.insert(Segment<double>(1,3));
  if (set.size()!=1) {
    suite.add(false);
    suite.err() << "expected size 1\n";
  }
  else if (set.begin()->begin()!=0.0 || set.begin()->end()!=2.0) {
    suite.add(false);
    suite.err() << "error: expected segment to be [0, 2)\n"
                << "found: [" << set.begin()->begin() 
                << ", " << set.begin()->end() << ")\n";
  }
  if (!suite.add(set.find(0)!=set.end()))
    suite.err() << "error: set.find(0): expected not end()\n";
}

void test_count(test::Suite& suite)
{
  SegmentSet<double> set;
  set.insert(Segment<double>(0,2));
  // test count
  if (!suite.add(set.count(0)==1))
    suite.err() << "error: set.count(0): expected 1\n";
  if (!suite.add(set.count(1)==1))
    suite.err() << "error: set.count(1): expected 1\n";
  if (!suite.add(set.count(2)==0))
    suite.err() << "error: set.count(2): expected 0\n";
}

void test_insert_merge(test::Suite& suite)
{
  SegmentSet<double> set;
  set.insert(Segment<double>(0,2));
  set.insert_merge(Segment<double>(3,5));
  if (!suite.add(set.size()==2))
    suite.err() << "error: set.size(): expected 2\n";

  set.insert_merge(Segment<double>(12,13));
  if (!suite.add(set.size()==3))
    suite.err() << "error: set.size(): expected 3\n";

  set.insert_merge(Segment<double>(1,4));
  if (!suite.add(set.size()==2))
    suite.err() << "error: set.size(): " << set.size() << " expected 2\n";

  set.insert_merge(Segment<double>(0,100));
  if (!suite.add(set.size()==1))
    suite.err() << "error: set.size(): " << set.size() << " expected 1\n";
  set.insert_merge(set.end(), Segment<double>(200, 1000));

  SegmentSet<double> set2;
  set2.insert_merge(set.begin(), set.end());
  std::vector<Segment<double> > vec(set.size());
  std::copy(set.begin(), set.end(), vec.begin());
  set2.insert_merge(vec.begin(), vec.end());
}


void make_segment_foo(Segment<int> seg)
{
}


void test_make_segment(test::Suite& suite)
{
  make_segment_foo(make_segment(12, 18));
}


void test_set_bound(test::Suite& suite)
{
  SegmentSet<double> set;
  set.insert(Segment<double>(0,2));
  set.begin();
  set.end();
  if (!suite.add(set.lower_bound(-1)==set.begin()))
    suite.err() << "error: expected set.lower_bound to return begin()\n";
  if (!suite.add(set.lower_bound(1)==set.begin()))
    suite.err() << "error: expected set.lower_bound to return begin()\n";
  if (!suite.add(set.lower_bound(2)==set.end()))
    suite.err() << "error: expected set.lower_bound to return end()\n";

  if (!suite.add(set.upper_bound(0)==set.end()))
    suite.err() << "error: expected set.upper_bound to return end()\n";
  if (!suite.add(set.upper_bound(2)==set.end()))
    suite.err() << "error: expected set.upper_bound to return end()\n";

  set.insert_merge(Segment<double>(3,4));
  SegmentSet<double>::const_iterator i=set.lower_bound(3.5);
  if (i->begin() != 3 || i->end() != 4) {
    suite.add(false);
    suite.out() << "found: " << i->begin() << " " << i->end() << "\n";
    suite.out() << "expected: 3 4\n";
  }

  i=set.lower_bound(1);
  if (i->begin() != 0 || i->end() != 2) {
    suite.add(false);
    suite.out() << "found: " << i->begin() << " " << i->end() << "\n";
    suite.out() << "expected: 0 2\n";
  }

  set.clear();
}


void test_segment_map(test::Suite& suite)
{
  typedef SegmentMap<double, std::string> Map;
  Map map;
  Map::element_type x = 0.0;
  avoid_pedantic_warning(x);
  Map::key_type key = Segment<double>(1.0,2.0);
  Map::mapped_type  mapped = "foofana";

  map.insert(Map::value_type(key, mapped));
  suite.add(map.find(1.5) != map.end());
  suite.add(map.find(1.5)->second == "foofana");

  Map::iterator i = map.begin();
  i = map.end();
  const Map const_map(map);
  Map::const_iterator ci = const_map.begin();
  ci = const_map.end();

  suite.add(map.size()==1);
  map.clear();
  suite.add(map.empty()==true);
  suite.add(map.size()==0);
  map = const_map;
  suite.add(map.size()==1);
  suite.add(const_map.count(1.0)==1);
  suite.add(const_map.count(0.0)==0);
  suite.add(const_map.empty()==false);
  suite.add(const_map.find(1.0)==const_map.begin());
  suite.add(const_map.find(30.0)==const_map.end());
  ci = const_map.lower_bound(0.0);
  ci = const_map.upper_bound(0.0);
  i = map.lower_bound(0.0);
  i = map.upper_bound(0.0);
}


void test_segment_set(test::Suite& suite)
{
  SegmentSet<double> set;
  Segment<double> segment(0.12,23.2);
  set.insert_merge(segment);
  set.insert_merge(Segment<double>(0.12,23.2));
  SegmentSet<double>::iterator hint = set.begin();
  set.insert_merge(hint, segment);
  set.insert_merge(hint, Segment<double>(0.12,23.2));
  SegmentSet<double>::const_iterator chint = set.begin();
  set.insert_merge(chint, segment);
  set.insert_merge(chint, Segment<double>(0.12,23.2));
  std::vector<Segment<double>> vec(set.begin(), set.end());
  set.insert_merge(vec.begin(), vec.end());

  // test functions inherited from SegmentTree
  SegmentSet<double>::const_iterator citer = set.begin();
  SegmentSet<double>::const_iterator iter = set.begin();

  citer = set.end();
  iter = set.end();

  if (set.count(0.13)!=1) {
    suite.add(false);
    suite.err() << "error: expected count = 1\n";
  }
  if (set.count(0.02)!=0) {
    suite.add(false);
    suite.err() << "error: expected count = 0\n";
  }
  if (set.empty()) {
    suite.add(false);
    suite.err() << "error: expected empty() return false";
  }
  if (set.find(0.15) == set.end()) {
    suite.add(false);
    suite.err() << "error: find returned end()";
  }
  set.erase(set.begin());
  set.clear();
  set.erase(set.begin(), set.end());

  set.insert(segment);
  set.insert(Segment<double>(102, 200));

  iter = set.lower_bound(1.0);
  citer = set.lower_bound(1.0);
  iter = set.upper_bound(1.0);
  citer = set.upper_bound(1.0);
  SegmentSet<double>::size_type s = set.size();
  test::avoid_compiler_warning(s);
}


void test_segment(test::Suite& suite)
{
  Segment<double> segment12(0,2);
  Segment<double> segment13(1,3);
  if (segment12==segment13) {
    suite.add(false);
    suite.err() << "segment12==segment13 : expected false\n";
  }
  if (!(segment12!=segment13)) {
    suite.add(false);
    suite.err() << "segment12!=segment13 : expected true\n";
  }
  Segment<double> segment14 = intersection(segment12, segment13);
  suite.add(segment14.begin()==1);
  suite.add(segment14.end()==2);

  if (!suite.add(compare(Segment<double>(0,2), Segment<double>(3,4))))
    suite.err() << "error: compare: expected 1\n";
  if (!suite.add(compare_3way(Segment<double>(0,2), Segment<double>(3,4))==-1))
    suite.err() << "error: compare_3way: expected -1\n";

  if (!suite.add(compare(Segment<double>(0,2), Segment<double>(1,2))==false))
    suite.err() << "error: compare: expected 0\n";
  if (!suite.add(compare_3way(Segment<double>(0,2), Segment<double>(1,2))==0))
    suite.err() << "error: compare_3way: expected 0\n";

  if (!suite.add(compare(Segment<double>(3,4), Segment<double>(0,2))==false))
    suite.err() << "error: compare: expected 0\n";
  if (!suite.add(compare_3way(Segment<double>(3,4), Segment<double>(0,2))==1))
    suite.err() << "error: compare_3way: expected 1\n";

}


void test_includes(test::Suite& suite, const Segment<int>& a,
                   const Segment<int>& b, bool answer)
{
  if (includes(a, b) != answer) {
    suite.add(false);
    suite.err() << "error: includes: "
                << "[" << a.begin() << ", "
                << a.end() << ") "
                << "[" << b.begin() << ", "
                << b.end() << ") "
                << "expected: " << answer << "\n";
  }
}


void test_includes(test::Suite& suite)
{
  Segment<int> a(0, 10);
  Segment<int> b(0, 5);
  Segment<int> c(5, 10);

  test_includes(suite, a, a, true);
  test_includes(suite, a, b, false);
  test_includes(suite, a, c, false);

  test_includes(suite, b, a, true);
  test_includes(suite, b, b, true);
  test_includes(suite, b, c, false);

  test_includes(suite, c, a, true);
  test_includes(suite, c, b, false);
  test_includes(suite, c, c, true);
}


void test_overlap(test::Suite& suite, const Segment<int>& a,
                  const Segment<int>& b, bool answer)
{
  if (overlap(a, b) != answer) {
    suite.add(false);
    suite.err() << "error: overlap: "
                << "[" << a.begin() << ", "
                << a.end() << ") "
                << "[" << b.begin() << ", "
                << b.end() << ") "
                << "expected: " << answer << "\n";
  }
}


void test_overlap(test::Suite& suite)
{
  Segment<int> a(0, 10);
  Segment<int> b(0, 5);
  Segment<int> c(5, 10);

  test_overlap(suite, a, a, true);
  test_overlap(suite, a, b, true);
  test_overlap(suite, a, c, true);

  test_overlap(suite, b, a, true);
  test_overlap(suite, b, b, true);
  test_overlap(suite, b, c, false);

  test_overlap(suite, c, a, true);
  test_overlap(suite, c, b, false);
  test_overlap(suite, c, c, true);
}


void test_union(test::Suite& suite, const Segment<int>& a,
                const Segment<int>& b, const Segment<int>& answer)
{
  if (set_union(a, b) != answer) {
    suite.add(false);
    suite.err() << "error: union: "
                << "[" << a.begin() << ", "
                << a.end() << ") "
                << "[" << b.begin() << ", "
                << b.end() << ") "
                << "expected: [" << answer.begin() << "," << answer.end()
                << " )\n";
  }
}


void test_union(test::Suite& suite)
{
  Segment<int> a(0, 10);
  Segment<int> b(0, 5);
  Segment<int> c(5, 12);

  test_union(suite, a, a, a);
  test_union(suite, a, b, a);
  test_union(suite, a, c, Segment<int>(0,12));

  test_union(suite, b, a, a);
  test_union(suite, b, b, b);
  test_union(suite, b, c, Segment<int>(0,12));

  test_union(suite, c, a, Segment<int>(0,12));
  test_union(suite, c, b, Segment<int>(0,12));
  test_union(suite, c, c, c);
}