1// -*- C++ -*- 2 3// Copyright (C) 2005, 2006, 2009 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 60using namespace std; 61using 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. 70typedef 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. 74template<class Const_Node_Iterator, 75 class Node_Iterator, 76 class Cmp_Fn, 77 class Allocator> 78struct intervals_node_update 79{ 80public: 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 Const_Node_Iterator nd_it = node_begin(); 92 Const_Node_Iterator 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 Const_Node_Iterator 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 120protected: 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_Iterator nd_it, Const_Node_Iterator 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 Const_Node_Iterator 142 node_begin() const = 0; 143 144 virtual Const_Node_Iterator 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. 155template<class Cntnr> 156void 157some_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 184int main() 185{ 186 // Test a red-black tree. 187 some_op_sequence(tree< 188 interval, 189 null_mapped_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_mapped_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_mapped_type, 206 less<interval>, 207 splay_tree_tag, 208 intervals_node_update>()); 209 210 return 0; 211} 212 213