1 |
424 |
jeremybenn |
// -*- 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 |
|
|
|
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 Const_Node_Iterator,
|
75 |
|
|
class Node_Iterator,
|
76 |
|
|
class Cmp_Fn,
|
77 |
|
|
class Allocator>
|
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 |
|
|
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 |
|
|
|
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_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 |
|
|
|
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 |
|
|
|
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.
|
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_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 |
|
|
|