// -*- C++ -*-
// Copyright (C) 2005, 2006, 2009 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 3, 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 COPYING3. If not see
// .
// 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
#include
#include
using namespace std;
using namespace __gnu_pbds;
// 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
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(nd_it.get_metadata()) =
max((*nd_it)->second, max(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
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,
rb_tree_tag,
intervals_node_update>());
// Test an ordered-vector tree.
some_op_sequence(tree<
interval,
null_mapped_type,
less,
ov_tree_tag,
intervals_node_update>());
// Test a splay tree.
some_op_sequence(tree<
interval,
null_mapped_type,
less,
splay_tree_tag,
intervals_node_update>());
return 0;
}