rtree.cpp

   1 /*
   2  *  rtree.cpp
   3  *  openc2e
   4  *
   5  *  Created by Bryan Donlan on Tue 10 Jan 2006.
   6  *  Copyright (c) 2006 Bryan Donlan. All rights reserved.
   7  *
   8  *  This library is free software; you can redistribute it and/or
   9  *  modify it under the terms of the GNU Lesser General Public
  10  *  License as published by the Free Software Foundation; either
  11  *  version 2 of the License, or (at your option) any later version.
  12  *
  13  *  This library is distributed in the hope that it will be useful,
  14  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16  *  Lesser General Public License for more details.
  17  *
  18  */
  19 #include "rtree.h"
  20 #include <cstdlib>
  21 #include <ctime>
  22 #include <iostream>
  23 #include <cstdio>
  24
  25 struct rcmp
  26 {
  27         bool operator()(const Region &r1, const Region &r2)
  28         {
  29 #define CMP(v) \
  30                 do { if (r1.v != r2.v) return r1.v < r2.v; } while (0)
  31                 CMP(xmin); CMP(xmax); CMP(ymin); CMP(ymax);
  32 #undef CMP
  33         }
  34 };
  35
  36 struct R2 : public Region {
  37         bool ok;
  38         ~R2() {
  39                 std::cerr << "R2 dest " << to_s() << " ok " << ok << std::endl;
  40                 ok = false;
  41         }
  42
  43         R2(const Region &r) : Region(r), ok(true) {}
  44         R2(int x1, int x2, int y1, int y2) : Region(x1,x2,y1,y2), ok(true) {}
  45 };
  46
  47 Region random_in(const Region &tr) {
  48         double rp1 = (double)rand() / (double)RAND_MAX;
  49         double rp2 = (double)rand() / (double)RAND_MAX;
  50
  51         int pt1 = tr.xmin + rp1 * (double)(tr.xmax - tr.xmin);
  52         int pt2 = tr.ymin + rp1 * (double)(tr.ymax - tr.ymin);
  53
  54         return Region(pt1, pt1, pt2, pt2);
  55
  56 }
  57
  58 int main() {
  59         std::cerr << "rbr=" << sizeof(RBranch<Region>) << "rn=" << sizeof(RNode<Region>) << "rd=" << sizeof(RData<Region>) << std::endl;
  60         try {
  61                 std::vector<R2> testVec;
  62                 srand(time(NULL));
  63                 RTree<R2> tree;
  64                 for (int i = 0; i < 500; i++) {
  65                         int x1 = rand(); // % 50000;
  66                         int x2 = x1 + rand() % 125;
  67                         int y1 = rand(); // % 50000;
  68                         int y2 = y1 + rand() % 125;
  69
  70                         if (x1 > x2) {
  71                                 int t = x1;
  72                                 x1 = x2;
  73                                 x2 = t;
  74                         }
  75
  76                         if (y1 > y2) {
  77                                 int t = y1;
  78                                 y1 = y2;
  79                                 y2 = t;
  80                         }
  81                         Region r(x1, x2, y1, y2);
  82
  83                         if (tree.find_one(r)) {
  84                                 i--;
  85                                 continue;
  86                         }
  87
  88                         testVec.push_back(R2(r));
  89                 }
  90
  91                 bool allok = true;
  92
  93                 int ct = 0;
  94                 for (std::vector<R2>::iterator i = testVec.begin(); i != testVec.end(); i++) {
  95                         tree.insert(*i, *i);
  96                         ct++;
  97 //                      if (ct % 100 == 0)
  98 //                              fprintf(stderr, "\rins %06d", ct);
  99                 }
 100                 std::cerr << std::endl << "size=" << tree.size() << "inner=" << tree.inner_size() << std::endl;
 101
 102                 ct = 0;
 103                 for (std::vector<R2>::iterator i = testVec.begin(); i != testVec.end(); i++) {
 104                         if (ct++ % 100 == 0)
 105                                 fprintf(stderr, "\rchk %06d", ct);
 106                         std::cout << "Verify of " << (*i).to_s() << "... ";
 107                         Region q = random_in(*i);
 108                         assert(q.overlaps((*i)));
 109                         std::cout << q.to_s() << "... ";
 110                         bool ok = false;
 111
 112                         std::vector<RTree<R2>::ptr> results = tree.find(q);
 113                         std::cout << results.size() << " results ... ";
 114                         for (std::vector<RTree<R2>::ptr>::iterator ci = results.begin(); ci != results.end(); ci++) {
 115                                 if ((*ci).data() == *i) {
 116                                         ok = true;
 117                                         (*ci).erase();
 118                                         break;
 119                                 }
 120                         }
 121
 122                         results = tree.find(q);
 123
 124                         std::cout << results.size() << " results postdel ... ";
 125                         for (std::vector<RTree<R2>::ptr>::iterator ci = results.begin(); ci != results.end(); ci++) {
 126                                 if ((*ci).data() == *i) {
 127                                         ok = false;
 128                                         break;
 129                                 }
 130                         }
 131
 132 // */
 133                         if (ok)
 134                                 std::cout << "ok";
 135                         else
 136                                 std::cout << "nok";
 137                         std::cout << std::endl;
 138                         allok = allok && ok;
 139                 }
 140
 141                 if (!allok)
 142                         std::cout << "Not all ok";
 143                 else
 144                         std::cout << "All ok";
 145                 std::cout << std::endl;
 146
 147                 testVec.clear();
 148                 std::cout << "sz=" << tree.size() << "isz=" << tree.inner_size() << std::endl;
 149                 std::cout << "alloc/free test: " << std::endl;
 150                 tree.insert(Region(1,2,3,4), R2(1,2,3,4));
 151         } catch (std::exception &e) {
 152                 std::cout << "abort: " << e.what();
 153         }
 154         std::cout << std::endl;
 155         fprintf(stderr, "\n");
 156 }