From 554fd8c5195424bdbcabf5de30fdc183aba391bd Mon Sep 17 00:00:00 2001 From: upstream source tree Date: Sun, 15 Mar 2015 20:14:05 -0400 Subject: obtained gcc-4.6.4.tar.bz2 from upstream website; verified gcc-4.6.4.tar.bz2.sig; imported gcc-4.6.4 source tree from verified upstream tarball. downloading a git-generated archive based on the 'upstream' tag should provide you with a source tree that is binary identical to the one extracted from the above tarball. if you have obtained the source via the command 'git clone', however, do note that line-endings of files in your working directory might differ from line-endings of the respective files in the upstream repository. --- .../ext/pb_ds/example/priority_queue_xref.cc | 210 +++++++++++++++++++++ 1 file changed, 210 insertions(+) create mode 100644 libstdc++-v3/testsuite/ext/pb_ds/example/priority_queue_xref.cc (limited to 'libstdc++-v3/testsuite/ext/pb_ds/example/priority_queue_xref.cc') diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/priority_queue_xref.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/priority_queue_xref.cc new file mode 100644 index 000000000..690814091 --- /dev/null +++ b/libstdc++-v3/testsuite/ext/pb_ds/example/priority_queue_xref.cc @@ -0,0 +1,210 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2007, 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 priority_queue_xref_example.cpp + * A basic example showing how to cross-reference priority queues and other + * containers for erase. + */ + +/** + * This example shows how to cross-reference priority queues + * and other containers. I.e., using an associative container to + * map keys to entries in a priority queue, and using the priority + * queue to map entries to the associative container. The combination + * can be used for fast operations involving both priorities and + * arbitrary keys. + * + * The most useful examples of this technique are usually from the + * field of graph algorithms (where erasing or modifying an arbitrary + * entry of a priority queue is sometimes necessary), but a full-blown + * example would be too long. Instead, this example shows a very simple + * version of Dijkstra's + */ + +#include +#include +#include +#include + +using namespace std; +using namespace __gnu_pbds; + +// A priority queue of integers, which supports fast pushes, +// duplicated-int avoidance, and arbitrary-int erases. +class mapped_priority_queue +{ +public: + + // Pushes an int into the container. If the key is already in, this + // is a no-op. + void + push(const int& r_str); + + // Returns a const reference to the largest int in the container. + int + top() const + { + assert(!empty()); + return m_pq.top(); + } + + // Erases the largest int in the container. + void + pop(); + + // Erases an arbitrary int. If the int is not in the container, this + // is a no-op, and the return value is false. + bool + erase(const int& r_str); + + bool + empty() const + { return m_pq.empty(); } + + size_t + size() const + { return m_pq.size(); } + +private: + // A priority queue of strings. + typedef __gnu_pbds::priority_queue< int> pq_t; + + // A hash-table mapping strings to point_iterators inside the + // priority queue. + typedef cc_hash_table< int, pq_t::point_iterator> map_t; + + pq_t m_pq; + map_t m_map; +}; + +void +mapped_priority_queue:: +push(const int& r_str) +{ + // First check if the int is already in the container. If so, just return. + if (m_map.find(r_str) != m_map.end()) + return; + + // Push the int into the priority queue, and store a point_iterator to it. + pq_t::point_iterator pq_it = m_pq.push(r_str); + + try + { + // Now make the map associate the int to the point_iterator. + m_map[r_str] = pq_it; + } + catch(...) + { + // If the above failed, we need to remove the int from the + // priority queue as well. + m_pq.erase(pq_it); + throw; + } +} + +void +mapped_priority_queue:: +pop() +{ + assert(!empty()); + + // Erase the int from the map. + m_map.erase(m_pq.top()); + + // ...then from the priority queue. + m_pq.pop(); +} + +bool +mapped_priority_queue:: +erase(const int& r_str) +{ + map_t::point_iterator map_it = m_map.find(r_str); + + // If the int is not in the map, this is a no-op. + if (map_it == m_map.end()) + return false; + + // Otherwise, we erase it from the priority queue. + m_pq.erase(map_it->second); + + // ...then from the map. + m_map.erase(r_str); + + return true; +} + +int main() +{ + // Push some values into the container object. + mapped_priority_queue m; + m.push(1); + m.push(2); + + // The following four operations are no-ops: 2 and 1 are already in + // the container. + m.push(2); + m.push(2); + m.push(2); + m.push(1); + + m.push(10); + m.push(11); + m.push(12); + + // The size should be 5, since m contains the set {1, 2, 10, 11, 12}. + assert(m.size() == 5); + + // The largest value should be 12. + assert(m.top() == 12); + + // Now erase some values. + + // Erasing 1 actually erases a value. + assert(m.erase(1)); + + // ...but erasing 1 again is a no-op. + assert(!m.erase(1)); + + // The size should be 5, since m contains the set {2, 10, 11, 12}. + assert(m.size() == 4); + + // Now print the values in the container. + while (!m.empty()) + { + cout << m.top() << endl; + m.pop(); + } + + return 0; +} + -- cgit v1.2.3