| // -*- C++ -*- |
| |
| // Copyright (C) 2005, 2006 Free Software Foundation, Inc. |
| // |
| // This file is part of the GNU ISO C++ Library. This library is free |
| // software; you can redistribute it and/or modify it under the terms |
| // of the GNU General Public License as published by the Free Software |
| // Foundation; either version 2, or (at your option) any later |
| // version. |
| |
| // This library is distributed in the hope that it will be useful, but |
| // WITHOUT ANY WARRANTY; without even the implied warranty of |
| // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| // General Public License for more details. |
| |
| // You should have received a copy of the GNU General Public License |
| // along with this library; see the file COPYING. If not, write to |
| // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, |
| // MA 02111-1307, USA. |
| |
| // As a special exception, you may use this file as part of a free |
| // software library without restriction. Specifically, if other files |
| // instantiate templates or use macros or inline functions from this |
| // file, or you compile this file and link it with other files to |
| // produce an executable, this file does not by itself cause the |
| // resulting executable to be covered by the GNU General Public |
| // License. This exception does not however invalidate any other |
| // reasons why the executable file might be covered by the GNU General |
| // Public License. |
| |
| // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. |
| |
| // Permission to use, copy, modify, sell, and distribute this software |
| // is hereby granted without fee, provided that the above copyright |
| // notice appears in all copies, and that both that copyright notice |
| // and this permission notice appear in supporting documentation. None |
| // of the above authors, nor IBM Haifa Research Laboratories, make any |
| // representation about the suitability of this software for any |
| // purpose. It is provided "as is" without express or implied |
| // warranty. |
| |
| /** |
| * @file tree_intervals_example.cpp |
| * An example showing how to augment a trees to support operations involving |
| * line intervals. |
| */ |
| |
| /** |
| * In some cases tree structure can be used for various purposes other |
| * than storing entries by key order. This example shows how a |
| * tree-based container can be used for geometric-line intersection |
| * determination. That is, the key of the container is a pair of |
| * numbers representing a line interval. The container object can be |
| * used to query whether a line interval intersects any line interval |
| * it currently stores. |
| * |
| * This type of problem arises not only in geometric applications, but |
| * also sometimes in distributed filesystems. Assume that "leases" are |
| * taken for parts of files or LUNs. When a new lease is requested, it |
| * is necessary to check that it does not conflict with a lease |
| * already taken. In this case a file or LUN can be envisioned as a |
| * line segment; leases requested and granted for contiguous parts of |
| * the file or LUN can be represented as line intervals as well. |
| */ |
| |
| #include <cassert> |
| #include <cstdlib> |
| #include <ext/pb_ds/assoc_container.hpp> |
| |
| using namespace std; |
| using namespace pb_ds; |
| using namespace pb_ds; |
| |
| // Following are definitions of line intervals and functors operating |
| // on them. As the purpose of this example is node invariants, and not |
| // computational-geometry algorithms per-se, some simplifications are |
| // made (e.g., intervals are defined by unsigned integers, and not by |
| // a parameterized type, data members are public, etc.). |
| |
| // An interval of unsigned integers. |
| typedef pair< unsigned int, unsigned int> interval; |
| |
| // Functor updating maximal endpoints of entries. Algorithm taken from |
| // "Introduction to Algorithms" by Cormen, Leiserson, and Rivest. |
| template<class Const_Node_Iterator, |
| class Node_Iterator, |
| class Cmp_Fn, |
| class Allocator> |
| struct intervals_node_update |
| { |
| public: |
| // The metadata that each node stores is the largest endpoint of an |
| // interval in its subtree. In this case, this is an unsigned int. |
| typedef unsigned int metadata_type; |
| |
| // Checks whether a set of intervals contains at least one interval |
| // overlapping some interval. Algorithm taken from "Introduction to |
| // Algorithms" by Cormen, Leiserson, and Rivest. |
| bool |
| overlaps(const interval& r_interval) |
| { |
| Const_Node_Iterator nd_it = node_begin(); |
| Const_Node_Iterator end_it = node_end(); |
| |
| while (nd_it != end_it) |
| { |
| // Check whether r_interval overlaps the current interval. |
| if (r_interval.second >= (*nd_it)->first&& |
| r_interval.first <= (*nd_it)->second) |
| return true; |
| |
| // Get the const node iterator of the node's left child. |
| Const_Node_Iterator l_nd_it = nd_it.get_l_child(); |
| |
| // Calculate the maximal endpoint of the left child. If the |
| // node has no left child, then this is the node's maximal |
| // endpoint. |
| const unsigned int l_max_endpoint =(l_nd_it == end_it)? |
| 0 : l_nd_it.get_metadata(); |
| |
| // Now use the endpoint to determine which child to choose. |
| if (l_max_endpoint >= r_interval.first) |
| nd_it = l_nd_it; |
| else |
| nd_it = nd_it.get_r_child(); |
| } |
| |
| return false; |
| } |
| |
| protected: |
| // Update predicate: nd_it is a node iterator to the node currently |
| // updated; end_nd_it is a const node iterator to a just-after leaf |
| // node. |
| inline void |
| operator()(Node_Iterator nd_it, Const_Node_Iterator end_nd_it) |
| { |
| // The left maximal endpoint is 0 if there is no left child. |
| const unsigned int l_max_endpoint =(nd_it.get_l_child() == end_nd_it)? |
| 0 : nd_it.get_l_child().get_metadata(); |
| |
| // The right maximal endpoint is 0 if there is no right child. |
| const unsigned int r_max_endpoint =(nd_it.get_r_child() == end_nd_it)? |
| 0 : nd_it.get_r_child().get_metadata(); |
| |
| // The maximal endpoint is the endpoint of the node's interval, |
| // and the maximal endpoints of its children. |
| const_cast<unsigned int&>(nd_it.get_metadata()) = |
| max((*nd_it)->second, max<unsigned int>(l_max_endpoint, r_max_endpoint)); |
| } |
| |
| virtual Const_Node_Iterator |
| node_begin() const = 0; |
| |
| virtual Const_Node_Iterator |
| node_end() const = 0; |
| |
| virtual |
| ~intervals_node_update() |
| { } |
| }; |
| |
| // The following function performs some operation sequence on a |
| // generic associative container supporting order statistics. It |
| // inserts some intervals, and checks for overlap. |
| template<class Cntnr> |
| void |
| some_op_sequence(Cntnr r_c) |
| { |
| // Insert some entries. |
| r_c.insert(make_pair(0, 100)); |
| r_c.insert(make_pair(150, 160)); |
| r_c.insert(make_pair(300, 1000)); |
| r_c.insert(make_pair(10000, 100000)); |
| r_c.insert(make_pair(200, 100200)); |
| |
| // Test overlaps. |
| |
| // Overlaps 150 - 160 |
| assert(r_c.overlaps(make_pair(145, 165)) == true); |
| // Overlaps 150 - 160 |
| assert(r_c.overlaps(make_pair(145, 155)) == true); |
| assert(r_c.overlaps(make_pair(165, 175)) == false); |
| assert(r_c.overlaps(make_pair(100201, 100203)) == false); |
| |
| // Erase an interval |
| r_c.erase(make_pair(150, 160)); |
| |
| // Test overlaps again. |
| assert(r_c.overlaps(make_pair(145, 165)) == false); |
| assert(r_c.overlaps(make_pair(165, 175)) == false); |
| assert(r_c.overlaps(make_pair(0, 300000)) == true); |
| } |
| |
| int main() |
| { |
| // Test a red-black tree. |
| some_op_sequence(tree< |
| interval, |
| null_mapped_type, |
| less<interval>, |
| rb_tree_tag, |
| intervals_node_update>()); |
| |
| // Test an ordered-vector tree. |
| some_op_sequence(tree< |
| interval, |
| null_mapped_type, |
| less<interval>, |
| ov_tree_tag, |
| intervals_node_update>()); |
| |
| // Test a splay tree. |
| some_op_sequence(tree< |
| interval, |
| null_mapped_type, |
| less<interval>, |
| splay_tree_tag, |
| intervals_node_update>()); |
| |
| return 0; |
| } |
| |