libstdc++-v3/testsuite/ext/pb_ds/example/tree_intervals.cc

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005-2016 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the terms
   7 // of the GNU General Public License as published by the Free Software
   8 // Foundation; either version 3, or (at your option) any later
   9 // version.
  10
  11 // This library is distributed in the hope that it will be useful, but
  12 // WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 // General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License
  17 // along with this library; see the file COPYING3.  If not see
  18 // <http://www.gnu.org/licenses/>.
  19
  20
  21 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  22
  23 // Permission to use, copy, modify, sell, and distribute this software
  24 // is hereby granted without fee, provided that the above copyright
  25 // notice appears in all copies, and that both that copyright notice
  26 // and this permission notice appear in supporting documentation. None
  27 // of the above authors, nor IBM Haifa Research Laboratories, make any
  28 // representation about the suitability of this software for any
  29 // purpose. It is provided "as is" without express or implied
  30 // warranty.
  31
  32 /**
  33  * @file tree_intervals_example.cpp
  34  * An example showing how to augment a trees to support operations involving
  35  *    line intervals.
  36  */
  37
  38 /**
  39  * In some cases tree structure can be used for various purposes other
  40  * than storing entries by key order.  This example shows how a
  41  * tree-based container can be used for geometric-line intersection
  42  * determination. That is, the key of the container is a pair of
  43  * numbers representing a line interval. The container object can be
  44  * used to query whether a line interval intersects any line interval
  45  * it currently stores.
  46  *
  47  * This type of problem arises not only in geometric applications, but
  48  * also sometimes in distributed filesystems. Assume that "leases" are
  49  * taken for parts of files or LUNs. When a new lease is requested, it
  50  * is necessary to check that it does not conflict with a lease
  51  * already taken. In this case a file or LUN can be envisioned as a
  52  * line segment; leases requested and granted for contiguous parts of
  53  * the file or LUN can be represented as line intervals as well.
  54  */
  55
  56 #include <cassert>
  57 #include <cstdlib>
  58 #include <ext/pb_ds/assoc_container.hpp>
  59
  60 using namespace std;
  61 using namespace __gnu_pbds;
  62
  63 // Following are definitions of line intervals and functors operating
  64 // on them. As the purpose of this example is node invariants, and not
  65 // computational-geometry algorithms per-se, some simplifications are
  66 // made (e.g., intervals are defined by unsigned integers, and not by
  67 // a parameterized type, data members are public, etc.).
  68
  69 // An interval of unsigned integers.
  70 typedef pair< unsigned int, unsigned int> interval;
  71
  72 // Functor updating maximal endpoints of entries. Algorithm taken from
  73 // "Introduction to Algorithms" by Cormen, Leiserson, and Rivest.
  74 template<class Node_CItr,
  75          class Node_Itr,
  76          class Cmp_Fn,
  77          typename _Alloc>
  78 struct intervals_node_update
  79 {
  80 public:
  81   // The metadata that each node stores is the largest endpoint of an
  82   // interval in its subtree. In this case, this is an unsigned int.
  83   typedef unsigned int metadata_type;
  84
  85   // Checks whether a set of intervals contains at least one interval
  86   // overlapping some interval. Algorithm taken from "Introduction to
  87   // Algorithms" by Cormen, Leiserson, and Rivest.
  88   bool
  89   overlaps(const interval& r_interval)
  90   {
  91     Node_CItr nd_it = node_begin();
  92     Node_CItr end_it = node_end();
  93
  94     while (nd_it != end_it)
  95       {
  96         // Check whether r_interval overlaps the current interval.
  97         if (r_interval.second >= (*nd_it)->first&&
  98             r_interval.first <= (*nd_it)->second)
  99           return true;
 100
 101         // Get the const node iterator of the node's left child.
 102         Node_CItr l_nd_it = nd_it.get_l_child();
 103
 104         // Calculate the maximal endpoint of the left child. If the
 105         // node has no left child, then this is the node's maximal
 106         // endpoint.
 107         const unsigned int l_max_endpoint =(l_nd_it == end_it)?
 108           0 : l_nd_it.get_metadata();
 109
 110         // Now use the endpoint to determine which child to choose.
 111         if (l_max_endpoint >= r_interval.first)
 112           nd_it = l_nd_it;
 113         else
 114           nd_it = nd_it.get_r_child();
 115       }
 116
 117     return false;
 118   }
 119
 120 protected:
 121   // Update predicate: nd_it is a node iterator to the node currently
 122   // updated; end_nd_it is a const node iterator to a just-after leaf
 123   // node.
 124   inline void
 125   operator()(Node_Itr nd_it, Node_CItr end_nd_it)
 126   {
 127     // The left maximal endpoint is 0 if there is no left child.
 128     const unsigned int l_max_endpoint =(nd_it.get_l_child() == end_nd_it)?
 129       0 : nd_it.get_l_child().get_metadata();
 130
 131     // The right maximal endpoint is 0 if there is no right child.
 132     const unsigned int r_max_endpoint =(nd_it.get_r_child() == end_nd_it)?
 133       0 : nd_it.get_r_child().get_metadata();
 134
 135     // The maximal endpoint is the endpoint of the node's interval,
 136     // and the maximal endpoints of its children.
 137     const_cast<unsigned int&>(nd_it.get_metadata()) =
 138       max((*nd_it)->second, max<unsigned int>(l_max_endpoint, r_max_endpoint));
 139   }
 140
 141   virtual Node_CItr
 142   node_begin() const = 0;
 143
 144   virtual Node_CItr
 145   node_end() const = 0;
 146
 147   virtual
 148   ~intervals_node_update()
 149   { }
 150 };
 151
 152 // The following function performs some operation sequence on a
 153 // generic associative container supporting order statistics. It
 154 // inserts some intervals, and checks for overlap.
 155 template<class Cntnr>
 156 void
 157 some_op_sequence(Cntnr r_c)
 158 {
 159   // Insert some entries.
 160   r_c.insert(make_pair(0, 100));
 161   r_c.insert(make_pair(150, 160));
 162   r_c.insert(make_pair(300, 1000));
 163   r_c.insert(make_pair(10000, 100000));
 164   r_c.insert(make_pair(200, 100200));
 165
 166   // Test overlaps.
 167
 168   // Overlaps 150 - 160
 169   assert(r_c.overlaps(make_pair(145, 165)) == true);
 170   // Overlaps 150 - 160
 171   assert(r_c.overlaps(make_pair(145, 155)) == true);
 172   assert(r_c.overlaps(make_pair(165, 175)) == false);
 173   assert(r_c.overlaps(make_pair(100201, 100203)) == false);
 174
 175   // Erase an interval
 176   r_c.erase(make_pair(150, 160));
 177
 178   // Test overlaps again.
 179   assert(r_c.overlaps(make_pair(145, 165)) == false);
 180   assert(r_c.overlaps(make_pair(165, 175)) == false);
 181   assert(r_c.overlaps(make_pair(0, 300000)) == true);
 182 }
 183
 184 int main()
 185 {
 186   // Test a red-black tree.
 187   some_op_sequence(tree<
 188                    interval,
 189                    null_type,
 190                    less<interval>,
 191                    rb_tree_tag,
 192                    intervals_node_update>());
 193
 194   // Test an ordered-vector tree.
 195   some_op_sequence(tree<
 196                    interval,
 197                    null_type,
 198                    less<interval>,
 199                    ov_tree_tag,
 200                    intervals_node_update>());
 201
 202   // Test a splay tree.
 203   some_op_sequence(tree<
 204                    interval,
 205                    null_type,
 206                    less<interval>,
 207                    splay_tree_tag,
 208                    intervals_node_update>());
 209
 210   return 0;
 211 }
 212