--- /dev/null
+// -*- 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
+// <http://www.gnu.org/licenses/>.
+
+
+// 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 __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<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;
+}
+
projects / msp430-gcc.git / blobdiff