diff options
Diffstat (limited to 'libstdc++-v3/testsuite/ext/pb_assoc/example/tree_intervals.cc')
| -rw-r--r-- | libstdc++-v3/testsuite/ext/pb_assoc/example/tree_intervals.cc | 260 |
1 files changed, 0 insertions, 260 deletions
diff --git a/libstdc++-v3/testsuite/ext/pb_assoc/example/tree_intervals.cc b/libstdc++-v3/testsuite/ext/pb_assoc/example/tree_intervals.cc deleted file mode 100644 index dbc9430a64e..00000000000 --- a/libstdc++-v3/testsuite/ext/pb_assoc/example/tree_intervals.cc +++ /dev/null @@ -1,260 +0,0 @@ -// -*- C++ -*- - -// Copyright (C) 2005 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, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, -// 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_set_intervals_example.cpp - * An example showing how to augment a trees to support operations involving - * line intervals. - */ - -// For ov_tree_set -#include <ext/pb_assoc/assoc_cntnr.hpp> -// For assert -#include <cassert> -// For NULL -#include <cstdlib> - -/* - * 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. - **/ -struct interval -{ - /* - * Constructor. - * @param start [i] - Start point. - * @param end [i] - End point. - */ - interval(unsigned int start, unsigned int end) : m_start(start), - m_end(end) - { - assert(start <= end); - } - - /* - * Comparison predicate. - * @param r_rhs [i] - Right-hand object with which to compare. - **/ - bool - operator<(const interval& r_rhs) const - { - if (m_start != r_rhs.m_start) - return (m_start < r_rhs.m_start); - - return (m_end < r_rhs.m_end); - } - - /* - * Start point. - */ - unsigned int m_start; - - /* - * End point. - **/ - unsigned int m_end; -}; - -struct intervals_node_updator; - -template<class Cntnr> -bool -overlaps(const Cntnr& r_c, const interval& r_interval); - -/* - * The entry of the set. It includes an interval and the - * maximal endpoint of the intervals in its subtree. - */ -struct entry -{ - // Constructor. The maximal endpoint is set to the endpoint - explicit entry(unsigned int start, unsigned int end) : m_interval(start, end), - m_max_endpoint(end) - { } - - // Compares two entries by their intervals. - inline bool - operator<(const entry& r_rhs) const - { - return (m_interval < r_rhs.m_interval); - } - - // An interval - interval m_interval; - -private: - // The maximal endpoint of the intervals in its subtree. - mutable unsigned int m_max_endpoint; - - friend struct intervals_node_updator; - - template<class Cntnr> - friend bool - overlaps(const Cntnr& r_c, const interval& r_interval); - -}; - -/* - * Functor updating maximal endpoints of entries. - * Algorithm taken from "Introduction to Algorithms" by Cormen, Leiserson, - * and Rivest. - */ -struct intervals_node_updator -{ - inline void - operator()(const entry* p_entry, const entry* p_l_child_entry, const entry* p_r_child_entry) - { - /* The left maximal endpoint is 0 if there is no left child. - */ - const unsigned int l_max_endpoint =(p_l_child_entry == NULL)? 0 : p_l_child_entry->m_max_endpoint; - - /* The right maximal endpoint is 0 if there is no right child. - */ - const unsigned int r_max_endpoint =(p_r_child_entry == NULL)? 0 : p_r_child_entry->m_max_endpoint; - - p_entry->m_max_endpoint = std::max(p_entry->m_interval.m_end, - std::max<unsigned int>(l_max_endpoint, r_max_endpoint)); - } -}; - -/* - * 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. - **/ -template<class Cntnr> -bool -overlaps(const Cntnr& r_c, const interval& r_interval) -{ - typedef typename Cntnr::const_iterator intr_set_const_it; - - typedef typename Cntnr::const_node_iterator intr_set_const_node_it; - - intr_set_const_node_it node_it = r_c.node_begin(); - - while (node_it != r_c.node_end()) - { - // Check whether r_interval overlaps the current interval. - - intr_set_const_it it =* node_it; - - if (r_interval.m_end >= it->m_interval.m_start&& - r_interval.m_start <= it->m_interval.m_end) - return (true); - - intr_set_const_node_it l_node_it = node_it.l_child(); - - const unsigned int l_max_endpoint =(l_node_it == r_c.node_end())? - 0 : (*l_node_it)->m_max_endpoint; - - if (l_max_endpoint >= r_interval.m_start) - node_it = l_node_it; - else - node_it = node_it.r_child(); - } - - return (false); -} - -template<class Cntnr> -void -some_op_sequence(Cntnr c) -{ - // Insert some entries. - - c.insert(entry(0, 100)); - c.insert(entry(150, 160)); - c.insert(entry(300, 1000)); - c.insert(entry(10000, 100000)); - c.insert(entry(200, 100200)); - - // Test overlaps. - - // Overlaps 150 - 160 - assert(overlaps(c, interval(145, 165)) == true); - // Overlaps 150 - 160 - assert(overlaps(c, interval(145, 155)) == true); - assert(overlaps(c, interval(165, 175)) == false); - assert(overlaps(c, interval(100201, 100203)) == false); - - // Erase an entry. - - entry e(150, 160); - - c.erase(e); - - // Test overlaps again. - - assert(overlaps(c, interval(145, 165)) == false); - assert(overlaps(c, interval(165, 175)) == false); - assert(overlaps(c, interval(0, 300000)) == true); -} - -int -main() -{ - some_op_sequence(pb_assoc::tree_assoc_cntnr< - entry, - pb_assoc::null_data_type, - std::less<entry>, - pb_assoc::ov_tree_ds_tag, - intervals_node_updator>()); - - some_op_sequence(pb_assoc::tree_assoc_cntnr< - entry, - pb_assoc::null_data_type, - std::less<entry>, - pb_assoc::rb_tree_ds_tag, - intervals_node_updator>()); - - some_op_sequence(pb_assoc::tree_assoc_cntnr< - entry, - pb_assoc::null_data_type, - std::less<entry>, - pb_assoc::splay_tree_ds_tag, - intervals_node_updator>()); -} - |