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

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005 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
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 2, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License along
  17 // with this library; see the file COPYING.  If not, write to the Free
  18 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  19 // USA.
  20
  21 // As a special exception, you may use this file as part of a free software
  22 // library without restriction.  Specifically, if other files instantiate
  23 // templates or use macros or inline functions from this file, or you compile
  24 // this file and link it with other files to produce an executable, this
  25 // file does not by itself cause the resulting executable to be covered by
  26 // the GNU General Public License.  This exception does not however
  27 // invalidate any other reasons why the executable file might be covered by
  28 // the GNU General Public License.
  29
  30 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  31
  32 // Permission to use, copy, modify, sell, and distribute this software
  33 // is hereby granted without fee, provided that the above copyright
  34 // notice appears in all copies, and that both that copyright notice and
  35 // this permission notice appear in supporting documentation. None of
  36 // the above authors, nor IBM Haifa Research Laboratories, make any
  37 // representation about the suitability of this software for any
  38 // purpose. It is provided "as is" without express or implied warranty.
  39
  40 /*
  41  * @file tree_set_intervals_example.cpp
  42  * An example showing how to augment a trees to support operations involving
  43  *      line intervals.
  44  */
  45
  46 // For ov_tree_set
  47 #include <ext/pb_assoc/assoc_cntnr.hpp>
  48 // For assert
  49 #include <cassert>
  50 // For NULL
  51 #include <cstdlib>
  52
  53 /*
  54  * Following are definitions of line intervals and functors operating on them.
  55  *      As the purpose of this example is node invariants, and not
  56  *      computational-geometry algorithms per-se, some simplifications are made
  57  *(e.g., intervals are defined by unsigned integers, and not by*a parameterized type, data members are public, etc.).
  58  */
  59
  60 /*
  61  * An interval of unsigned integers.
  62  **/
  63 struct interval
  64 {
  65   /*
  66    * Constructor.
  67    * @param start [i] - Start point.
  68    * @param end [i] - End point.
  69    */
  70   interval(unsigned int start, unsigned int end) : m_start(start),
  71                                                    m_end(end)
  72   {
  73     assert(start <= end);
  74   }
  75
  76   /*
  77    * Comparison predicate.
  78    * @param r_rhs [i] - Right-hand object with which to compare.
  79    **/
  80   bool
  81   operator<(const interval& r_rhs) const
  82   {
  83     if (m_start != r_rhs.m_start)
  84       return (m_start < r_rhs.m_start);
  85
  86     return (m_end < r_rhs.m_end);
  87   }
  88
  89   /*
  90    * Start point.
  91    */
  92   unsigned int m_start;
  93
  94   /*
  95    * End point.
  96    **/
  97   unsigned int m_end;
  98 };
  99
 100 struct intervals_node_updator;
 101
 102 template<class Cntnr>
 103 bool
 104 overlaps(const Cntnr& r_c, const interval& r_interval);
 105
 106 /*
 107  * The entry of the set. It includes an interval and the
 108  *      maximal endpoint of the intervals in its subtree.
 109  */
 110 struct entry
 111 {
 112   // Constructor. The maximal endpoint is set to the endpoint
 113   explicit entry(unsigned int start, unsigned int end) : m_interval(start, end),
 114                                                          m_max_endpoint(end)
 115   { }
 116
 117   // Compares two entries by their intervals.
 118   inline bool
 119   operator<(const entry& r_rhs) const
 120   {
 121     return (m_interval < r_rhs.m_interval);
 122   }
 123
 124   // An interval
 125   interval m_interval;
 126
 127 private:
 128   // The maximal endpoint of the intervals in its subtree.
 129   mutable unsigned int m_max_endpoint;
 130
 131   friend struct intervals_node_updator;
 132
 133   template<class Cntnr>
 134   friend bool
 135   overlaps(const Cntnr& r_c, const interval& r_interval);
 136
 137 };
 138
 139 /*
 140  * Functor updating maximal endpoints of entries.
 141  *      Algorithm taken from "Introduction to Algorithms" by Cormen, Leiserson,
 142  *      and Rivest.
 143  */
 144 struct intervals_node_updator
 145 {
 146   inline void
 147   operator()(const entry* p_entry, const entry* p_l_child_entry, const entry* p_r_child_entry)
 148   {
 149     /* The left maximal endpoint is 0 if there is no left child.
 150      */
 151     const unsigned int l_max_endpoint =(p_l_child_entry == NULL)? 0 : p_l_child_entry->m_max_endpoint;
 152
 153     /* The right maximal endpoint is 0 if there is no right child.
 154      */
 155     const unsigned int r_max_endpoint =(p_r_child_entry == NULL)? 0 : p_r_child_entry->m_max_endpoint;
 156
 157     p_entry->m_max_endpoint = std::max(p_entry->m_interval.m_end,
 158                                        std::max<unsigned int>(l_max_endpoint, r_max_endpoint));
 159   }
 160 };
 161
 162 /*
 163  * Checks whether a set of intervals contains at least one interval
 164  *      overlapping some interval.
 165  *      Algorithm taken from "Introduction to Algorithms" by Cormen, Leiserson,
 166  *      and Rivest.
 167  **/
 168 template<class Cntnr>
 169 bool
 170 overlaps(const Cntnr& r_c, const interval& r_interval)
 171 {
 172   typedef typename Cntnr::const_iterator intr_set_const_it;
 173
 174   typedef typename Cntnr::const_node_iterator intr_set_const_node_it;
 175
 176   intr_set_const_node_it node_it = r_c.node_begin();
 177
 178   while (node_it != r_c.node_end())
 179     {
 180       // Check whether r_interval overlaps the current interval.
 181
 182       intr_set_const_it it =* node_it;
 183
 184       if (r_interval.m_end >= it->m_interval.m_start&&
 185           r_interval.m_start <= it->m_interval.m_end)
 186         return (true);
 187
 188       intr_set_const_node_it l_node_it = node_it.l_child();
 189
 190       const unsigned int l_max_endpoint =(l_node_it == r_c.node_end())?
 191         0 : (*l_node_it)->m_max_endpoint;
 192
 193       if (l_max_endpoint >= r_interval.m_start)
 194         node_it = l_node_it;
 195       else
 196         node_it = node_it.r_child();
 197     }
 198
 199   return (false);
 200 }
 201
 202 template<class Cntnr>
 203 void
 204 some_op_sequence(Cntnr c)
 205 {
 206   // Insert some entries.
 207
 208   c.insert(entry(0, 100));
 209   c.insert(entry(150, 160));
 210   c.insert(entry(300, 1000));
 211   c.insert(entry(10000, 100000));
 212   c.insert(entry(200, 100200));
 213
 214   // Test overlaps.
 215
 216   // Overlaps 150 - 160
 217   assert(overlaps(c, interval(145, 165)) == true);
 218   // Overlaps 150 - 160
 219   assert(overlaps(c, interval(145, 155)) == true);
 220   assert(overlaps(c, interval(165, 175)) == false);
 221   assert(overlaps(c, interval(100201, 100203)) == false);
 222
 223   // Erase an entry.
 224
 225   entry e(150, 160);
 226
 227   c.erase(e);
 228
 229   // Test overlaps again.
 230
 231   assert(overlaps(c, interval(145, 165)) == false);
 232   assert(overlaps(c, interval(165, 175)) == false);
 233   assert(overlaps(c, interval(0, 300000)) == true);
 234 }
 235
 236 int
 237 main()
 238 {
 239   some_op_sequence(pb_assoc::tree_assoc_cntnr<
 240                    entry,
 241                    pb_assoc::null_data_type,
 242                    std::less<entry>,
 243                    pb_assoc::ov_tree_ds_tag,
 244                    intervals_node_updator>());
 245
 246   some_op_sequence(pb_assoc::tree_assoc_cntnr<
 247                    entry,
 248                    pb_assoc::null_data_type,
 249                    std::less<entry>,
 250                    pb_assoc::rb_tree_ds_tag,
 251                    intervals_node_updator>());
 252
 253   some_op_sequence(pb_assoc::tree_assoc_cntnr<
 254                    entry,
 255                    pb_assoc::null_data_type,
 256                    std::less<entry>,
 257                    pb_assoc::splay_tree_ds_tag,
 258                    intervals_node_updator>());
 259 }
 260