// -*- 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; }