diff options
Diffstat (limited to 'libstdc++-v3/testsuite/ext/pb_ds')
40 files changed, 4669 insertions, 0 deletions
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/assoc_container_traits.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/assoc_container_traits.cc new file mode 100644 index 000000000..050ac3e04 --- /dev/null +++ b/libstdc++-v3/testsuite/ext/pb_ds/example/assoc_container_traits.cc @@ -0,0 +1,230 @@ +// -*- 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 assoc_container_traits_example.cpp + * A basic example showing how to use container_traits for querying container types + * for their behavior. + */ + +/** + * The following example shows how to use container_traits in order to print + * out information on an associative container's behavior, e.g., its underlying + * data structure, or whether its objects guarantee storing entries sorted + * by key order. + */ + +#include <iostream> +#include <ext/pb_ds/assoc_container.hpp> +#include <ext/pb_ds/tag_and_trait.hpp> + +using namespace std; +using namespace __gnu_pbds; + +template<class DS_Category> +void +print_container_category(DS_Category); + +template<> +void +print_container_category(cc_hash_tag) +{ + cout << "Collision-chaining hash based associative-container:" << endl; +} + +template<> +void +print_container_category(gp_hash_tag) +{ + cout << "Probing hash based associative-container:" << endl; +} + +template<> +void +print_container_category(rb_tree_tag) +{ + cout << "Red-black tree associative-container:" << endl; +} + +template<> +void +print_container_category(splay_tree_tag) +{ + cout << "Splay tree associative-container:" << endl; +} + +template<> +void +print_container_category(ov_tree_tag) +{ + cout << "Ordered-vector tree associative-container:" << endl; +} + +template<> +void +print_container_category(list_update_tag) +{ + cout << "List-based associative-container:" << endl; +} + +void +print_erase_can_throw(bool can) +{ + if (can) + { + cout << "Erase can throw" << endl; + return; + } + cout << "Erase cannot throw" << endl; +} + +void +print_order_preserving(bool does) +{ + if (does) + { + cout << "Preserves order" << endl; + return; + } + cout << "Does not preserve order" << endl; +} + +template<class Invalidation_Guarantee> +void +print_invalidation_guarantee(Invalidation_Guarantee); + +template<> +void +print_invalidation_guarantee(basic_invalidation_guarantee) +{ + cout << "Guarantees only that found references, pointers, and " + "iterators are valid as long as the container object is not " + "modified" << endl; +} + +template<> +void +print_invalidation_guarantee(point_invalidation_guarantee) +{ + cout << "Guarantees that found references, pointers, and " + "point_iterators are valid even if the container object " + "is modified" << endl; +} + +template<> +void +print_invalidation_guarantee(range_invalidation_guarantee) +{ + cout << "Guarantees that iterators remain valid even if the " + "container object is modified" << endl; +} + +void +print_reverse_iteration(bool does) +{ + if (does) + { + cout << "Supports reverse iteration" << endl; + return; + } + cout << "Does not support reverse iteration" << endl; +} + +template<class DS_Traits> +void +print_container_attributes() +{ + // First print out the data structure category. + print_container_category(typename DS_Traits::container_category()); + + // Now print the attributes of the container. + print_erase_can_throw(DS_Traits::erase_can_throw); + print_order_preserving(DS_Traits::order_preserving); + print_invalidation_guarantee(typename DS_Traits::invalidation_guarantee()); + print_reverse_iteration(DS_Traits::reverse_iteration); + + cout << endl << endl; +} + +int +main() +{ + { + // Print the attributes of a collision-chaining hash table. + typedef cc_hash_table< int, char> t; + print_container_attributes<container_traits<t> >(); + } + + { + // Print the attributes of a (general) probing hash table. + typedef gp_hash_table< int, char> t; + print_container_attributes<container_traits<t> >(); + } + + { + // Print the attributes of a red-black tree. + typedef tree< int, char> t; + print_container_attributes<container_traits<t> >(); + } + + { + // Print the attributes of a splay tree. + typedef + tree< + int, + char, + less<int>, + splay_tree_tag> + t; + + print_container_attributes<container_traits<t> >(); + } + + { + // Print the attributes of an ordered-vector tree. + typedef + tree< + int, + char, + less<int>, + ov_tree_tag> + t; + print_container_attributes<container_traits<t> >(); + } + + { + // Print the attributes of an list-based container. + typedef list_update< int, char> t; + print_container_attributes<container_traits<t> >(); + } + + return 0; +} diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/basic_map.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/basic_map.cc new file mode 100644 index 000000000..bc629d8d7 --- /dev/null +++ b/libstdc++-v3/testsuite/ext/pb_ds/example/basic_map.cc @@ -0,0 +1,119 @@ +// -*- 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 basic_map_example.cpp + * A basic example showing how to use maps. + */ + +/** + * This example shows how to use "maps". It defines a + * function performing a sequence of operations on + * a generic container. It then calls this function with some containers. + */ + +#include <iostream> +#include <cassert> +#include <ext/pb_ds/assoc_container.hpp> + +using namespace std; +using namespace __gnu_pbds; + +// The following function performs a sequence of operations on an +// associative container object mapping integers to characters. +template<class Cntnr> +void +some_op_sequence(Cntnr& r_c) +{ + assert(r_c.empty()); + assert(r_c.size() == 0); + + r_c.insert(make_pair(1, 'a')); + + r_c[2] = 'b'; + + assert(!r_c.empty()); + assert(r_c.size() == 2); + + cout << "Key 1 is mapped to " << r_c[1] << endl; + cout << "Key 2 is mapped to " << r_c[2] << endl; + + cout << endl << "All value types in the container:" << endl; + + typedef typename Cntnr::const_iterator const_iterator; + for (const_iterator it = r_c.begin(); it != r_c.end(); ++it) + cout << it->first << " -> " << it->second << endl; + cout << endl; + + r_c.clear(); + + assert(r_c.empty()); + assert(r_c.size() == 0); +} + +int main() +{ + { + // Perform operations on a collision-chaining hash map. + cc_hash_table<int, char> c; + some_op_sequence(c); + } + + { + // Perform operations on a general-probing hash map. + gp_hash_table<int, char> c; + some_op_sequence(c); + } + + { + // Perform operations on a red-black tree map. + tree<int, char> c; + some_op_sequence(c); + } + + { + // Perform operations on a splay tree map. + tree<int, char, less<int>, splay_tree_tag> c; + some_op_sequence(c); + } + + { + // Perform operations on an ov tree map. + tree<int, char, less<int>, ov_tree_tag> c; + some_op_sequence(c); + } + + { + // Perform operations on a list-update map. + list_update<int, char> c; + some_op_sequence(c); + } +} diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/basic_multimap.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/basic_multimap.cc new file mode 100644 index 000000000..bdc423a26 --- /dev/null +++ b/libstdc++-v3/testsuite/ext/pb_ds/example/basic_multimap.cc @@ -0,0 +1,152 @@ +// -*- 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 basic_multimap_example.cpp + * A basic example showing how to use multimaps. + */ + +/** + * This example shows how to use "multimaps" in the context of a simple + * bank account application. Each customer holds a bank account + * (or more than one) which holds some balance. + */ + +#include <iostream> +#include <string> +#include <cassert> +#include <ext/pb_ds/assoc_container.hpp> + +using namespace std; +using namespace __gnu_pbds; + +// A simple hash functor. +// hash could serve instead of this functor, but it is not yet +// standard everywhere. +struct string_hash : public unary_function<string, size_t> +{ + inline size_t + operator()(const string& r_s) const + { + size_t ret = 0; + string::const_iterator b = r_s.begin(); + string::const_iterator e = r_s.end(); + while (b != e) + { + ret *= 5; + ret += static_cast<size_t>(*(b++)); + } + return ret; + } +}; + +int main() +{ + // Each customer is identified by a string. + typedef string customer; + + // Each account is identified by an unsigned long. + typedef unsigned long account_id; + + // The balance in the account is a floating point. + typedef float balance_t; + + /* + * This is the data structure type used for storing information + * about accounts. In this case the primary key is the customer, + * and the secondary key is the account id. + * + * A hash-based container maps each customer to a list-based + * container that maps each account to the balance it holds. + * + * Note that we could use any combination of primary and secondary + * associative-containers. In this case we choose a hash-based + * container for the primary keys, since we do not need to store + * customers in a sorted order; we choos a list-based container for + * the secondary keys, since we expect that the average number of + * accounts per customer will be small. + */ + typedef + cc_hash_table< + customer, + list_update< + account_id, + balance_t>, + string_hash> + accounts_t; + + // This object will hold all information. + accounts_t acc; + + // Customer "a" opens empty account 12. + acc["a"][12] = 0; + + // Customer "a" deposits 45 into account 12. + acc["a"][12] += 45; + + // Customer "b" opens account 13 with balance 12.3. + acc["b"][13] = 12.3; + + // Customer "c" opens empty account 14. + acc["c"][14] = 0; + + // Customer "a" opens account 160 with balance 142. + // Note that "a" already holds account 12. + acc["a"][160] = 142; + + // Verify the number of accounts that "a" holds. + accounts_t::const_point_iterator it = acc.find("a"); + assert(it != acc.end()); + assert(it->second.size() == 2); + + // The begining of the month has arrived. We need to give a 3% + // interest to all accounts with a positive balance. + + // First we loop over all customers. + accounts_t::iterator cust_it; + for (cust_it = acc.begin(); cust_it != acc.end(); ++cust_it) + { + // For each customer, we loop over the customer's accounts. + accounts_t::mapped_type::iterator it; + for (it = cust_it->second.begin(); it != cust_it->second.end(); ++it) + if (it->second > 0) + it->second *= 1.03; + } + + // Customer "a" closes all accounts. + acc.erase("a"); + + // The bank now has only 2 customers. + assert(acc.size() == 2); + + return 0; +} + diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/basic_multiset.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/basic_multiset.cc new file mode 100644 index 000000000..1127f7591 --- /dev/null +++ b/libstdc++-v3/testsuite/ext/pb_ds/example/basic_multiset.cc @@ -0,0 +1,165 @@ +// -*- 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 basic_multiset_example.cpp + * A basic example showing how to use multisets. + */ + + +// This example shows how to use "multisets". + +// In this example we build a very simple priority queue that also can +// be queried if an entry contains (i.e., it is slightly similar to an +// associative container as well as a priority queue). The priority +// queue adapts a "multiset". + +// (Note that there are more efficient ways for implementing this than +// by adapting an associative container. This is just an example for +// "multisets".) + +#include <iostream> +#include <cassert> +#include <ext/pb_ds/assoc_container.hpp> + +using namespace std; +using namespace __gnu_pbds; + +// A simple priority queue that also supports an "contains" query. +class contains_pq +{ +public: + // Pushes an integer. + void + push(int i); + + // Pops the largest integer and returns it. + int + pop(); + + // Returns true iff i is contained in the container. + bool + contains(int i) const + { return m_tree.find(i) != m_tree.end(); } + + // Returns true iff empty. + bool + empty() const + { return m_tree.empty(); } + +private: + // This is the container type we adapt - a "multiset". + // It maps each integer to the number of times it logically appears. + typedef + tree< + int, + size_t, + greater< + int> > + tree_t; + +private: + tree_t m_tree; +}; + +void +contains_pq:: +push(int i) +{ + // To push i, we insert to the "multiset" that i appears 0 times + // (which is a no-op if i already is contained), then increment the + // number of times i is contained by 1. + ++m_tree.insert(make_pair(i, 0)).first->second; +} + +int +contains_pq:: +pop() +{ + assert(!empty()); + + // The element we need to pop must be the first one, since tree_t is + // an ordered container. + tree_t::iterator it = m_tree.begin(); + + const int i = it->first; + + // Decrease the number of times the popped element appears in the + // container object. If it is 0 - we erase it. + if (--it->second == 0) + m_tree.erase(it); + + return i; +} + +int main() +{ + contains_pq cpq; + + // First we push some elements. + cpq.push(4); + cpq.push(3); + cpq.push(2); + cpq.push(1); + cpq.push(4); + + // Note that logically, 4 appears 2 times, and each of 1, 2, and 3 + // appear once. + assert(cpq.contains(4)); + assert(cpq.contains(3)); + assert(cpq.contains(2)); + assert(cpq.contains(1)); + + // Now pop the topmost element - it should be 4. + assert(cpq.pop() == 4); + + // Now logically, each of 1, 2, 3, and 4 appear once. + assert(cpq.contains(4)); + + // We pop the topmost element - it should be 4. + assert(cpq.pop() == 4); + + // 4 should not be contained any more. + assert(!cpq.contains(4)); + + assert(cpq.contains(3)); + assert(cpq.contains(2)); + assert(cpq.contains(1)); + + assert(cpq.pop() == 3); + assert(cpq.pop() == 2); + assert(cpq.pop() == 1); + + assert(cpq.empty()); + + return 0; +} + diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/basic_priority_queue.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/basic_priority_queue.cc new file mode 100644 index 000000000..24ebe2e28 --- /dev/null +++ b/libstdc++-v3/testsuite/ext/pb_ds/example/basic_priority_queue.cc @@ -0,0 +1,119 @@ +// -*- 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 basic_priority_queue_example.cpp + * A basic example showing how to use priority queues. + */ + +/** + * This example shows how to use priority queues. It defines a + * function performing a sequence of operations on + * a generic container. It then calls this function with some containers. + */ + +#include <cassert> +#include <iostream> +#include <ext/pb_ds/priority_queue.hpp> + +using namespace std; +using namespace __gnu_pbds; + +// The following function performs a sequence of operations on a +// priority queue object storing integers. +template<class Cntnr> +void +some_op_sequence(Cntnr& r_c) +{ + assert(r_c.empty()); + assert(r_c.size() == 0); + + for (size_t i = 0; i < 10; ++i) + r_c.push(i); + cout << endl << "All values in the container:" << endl; + + typedef typename Cntnr::const_iterator const_iterator; + for (const_iterator it = r_c.begin(); it != r_c.end(); ++it) + cout <<* it << endl; + assert(!r_c.empty()); + assert(r_c.size() == 10); + + cout << "Popping all values: " << endl; + while (!r_c.empty()) + { + cout << r_c.top() << endl; + r_c.pop(); + } + assert(r_c.empty()); + assert(r_c.size() == 0); + + cout << endl; +} + +int main() +{ + { + // Perform operations on a pairing-heap queue. + cout << "Pairing heap" << endl; + __gnu_pbds::priority_queue<int, less<int>, pairing_heap_tag> c; + some_op_sequence(c); + } + + { + // Perform operations on a binomial-heap queue. + cout << "Binomial heap" << endl; + __gnu_pbds::priority_queue<int, less<int>, binomial_heap_tag> c; + some_op_sequence(c); + } + + { + // Perform operations on a binomial-heap queue. + cout << "Redundant-counter binomial heap" << endl; + __gnu_pbds::priority_queue<int, less<int>, rc_binomial_heap_tag> c; + some_op_sequence(c); + } + + { + // Perform operations on a binomial-heap queue. + cout << "Binary heap" << endl; + __gnu_pbds::priority_queue<int, less<int>, binary_heap_tag> c; + some_op_sequence(c); + } + + { + // Perform operations on a thin-heap queue. + cout << "Thin heap" << endl; + __gnu_pbds::priority_queue<int, less<int>, thin_heap_tag> c; + some_op_sequence(c); + } + + return 0; +} diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/basic_set.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/basic_set.cc new file mode 100644 index 000000000..3d2cf14db --- /dev/null +++ b/libstdc++-v3/testsuite/ext/pb_ds/example/basic_set.cc @@ -0,0 +1,126 @@ +// -*- 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 basic_set_example.cpp + * A basic example showing how to use sets. + */ + +/** + * This example shows how to use "sets". It defines a + * function performing a sequence of operations on + * a generic container. It then calls this function with some containers. + */ + +#include <iostream> +#include <cassert> +#include <ext/pb_ds/assoc_container.hpp> +#include <ext/pb_ds/tag_and_trait.hpp> + +using namespace std; +using namespace __gnu_pbds; + +// The following function performs a sequence of operations on an +// associative container object storing integers. +template<class Cntnr> +void +some_op_sequence(Cntnr& r_c) +{ + assert(r_c.empty()); + assert(r_c.size() == 0); + + r_c.insert(1); + r_c.insert(2); + + assert(!r_c.empty()); + assert(r_c.size() == 2); + + cout << "All value types in the container:" << endl; + for (typename Cntnr::const_iterator it = r_c.begin(); it != r_c.end(); + ++it) + cout <<* it << " "; + + cout << endl; + + r_c.clear(); + + assert(r_c.empty()); + assert(r_c.size() == 0); +} + +int main() +{ + { + // Perform operations on a collision-chaining hash set. + cc_hash_table<int, null_mapped_type> c; + some_op_sequence(c); + } + + { + // Perform operations on a general-probing hash set. + gp_hash_table<int, null_mapped_type> c; + some_op_sequence(c); + } + + { + // Perform operations on a red-black tree set. + tree<int, null_mapped_type> c; + some_op_sequence(c); + } + + { + // Perform operations on a splay tree set. + tree< + int, + null_mapped_type, + less<int>, + splay_tree_tag> c; + some_op_sequence(c); + } + + { + // Perform operations on a splay tree set. + tree< + int, + null_mapped_type, + less<int>, + ov_tree_tag> c; + some_op_sequence(c); + } + + { + // Perform operations on a list-update set. + list_update<int, null_mapped_type> c; + some_op_sequence(c); + } + + return 0; +} diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/erase_if.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/erase_if.cc new file mode 100644 index 000000000..3f14f6d08 --- /dev/null +++ b/libstdc++-v3/testsuite/ext/pb_ds/example/erase_if.cc @@ -0,0 +1,122 @@ +// -*- 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 erase_if_example.cpp + * A basic example showing how to use erase_if. + */ + +/** + * The following example shows how to use a conditional-erase + * method of associative containers to erase some of their entries. + */ + +#include <iostream> +#include <cassert> +#include <ext/pb_ds/assoc_container.hpp> + +using namespace std; +using namespace __gnu_pbds; + +// The following functor takes a map's value-type object and returns +// whether its key is between two numbers. +struct between : public unary_function<pair<const int, char>, bool> +{ + // Constructor taking two numbers determining a range. + between(int b, int e) : m_b(b), m_e(e) + { assert(m_b < m_e); } + + // Operator determining whether a value-type object's key is within + // the range. + inline bool + operator()(const pair<const int, char>& r_val) + { return r_val.first >= m_b&& r_val.first < m_e; } + +private: + const int m_b; + const int m_e; +}; + +/** + * The following function performs a sequence of operations on an + * associative container object mapping integers to characters. Specifically + * it inserts 100 values and then uses a conditional-erase method to erase + * the values whose key is between 10 and 90. + */ +template<class Cntnr> +void +some_op_sequence(Cntnr r_c) +{ + assert(r_c.empty()); + assert(r_c.size() == 0); + + for (int i = 0; i < 100; ++i) + r_c.insert(make_pair(i, static_cast<char>(i))); + assert(r_c.size() == 100); + + // Erase all values whose key is between 10 (inclusive) and 90 + // (non-inclusive). + r_c.erase_if(between(10 , 90)); + + assert(!r_c.empty()); + assert(r_c.size() == 20); +} + +int main() +{ + // Perform operations on a list-update set. + some_op_sequence(list_update<int, char>()); + + // Perform operations on a collision-chaining hash set. + some_op_sequence(cc_hash_table<int, char>()); + + // Perform operations on a general-probing hash set. + some_op_sequence(gp_hash_table<int, char>()); + + // Perform operations on a red-black tree set. + some_op_sequence(tree<int, char>()); + + // Perform operations on a splay tree set. + some_op_sequence(tree< + int, + char, + less<int>, + splay_tree_tag>()); + + // Perform operations on a splay tree set. + some_op_sequence(tree< + int, + char, + less<int>, + ov_tree_tag>()); + + return 0; +} diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/hash_find_neg.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/hash_find_neg.cc new file mode 100644 index 000000000..e2781a03e --- /dev/null +++ b/libstdc++-v3/testsuite/ext/pb_ds/example/hash_find_neg.cc @@ -0,0 +1,69 @@ +// { dg-do compile } +// -*- 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 hash_bad_find_example.cpp + * An example showing how *not* to use unordered containers. + */ + +/** + * This non-compiling example shows wrong use of unordered + * associative-containers. These types of containers have distinct + * point-type and range-type iterator types. + **/ + +#include <utility> +#include <ext/pb_ds/assoc_container.hpp> + +using namespace std; +using namespace __gnu_pbds; + +int main() +{ + // A collision-chaining hash table mapping ints to chars. + typedef cc_hash_table<int, char> map_t; + + // A map_t object. + map_t h; + + // Insert a value mapping the int 1 to the char 'a'. + h.insert(make_pair(1, 'a')); + + // Find the entry of the key '1' the* wrong* way. + // The following line will not compile, since map_t::find returns a + // point-iterator, which, by design, is not convertible to a + // range-iterator. + map_t::iterator it = h.find(1); // { dg-error "conversion from" } + + return 0; +} + diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/hash_illegal_resize.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/hash_illegal_resize.cc new file mode 100644 index 000000000..3b239d43c --- /dev/null +++ b/libstdc++-v3/testsuite/ext/pb_ds/example/hash_illegal_resize.cc @@ -0,0 +1,135 @@ +// { dg-timeout-factor 2.0 } + +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2009, 2011 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 hash_illegal_resize_example.cpp + * An example of illegally externally resizing a hash-based container object. + */ + +/** + * This example shows the case where a hash-based container object is + * resized to a value which it cannot accomodate at runtime. Illegal + * runtime resizes cause an exception. + */ + +#include <ext/pb_ds/assoc_container.hpp> +#include <ext/pb_ds/hash_policy.hpp> +#include <ext/pb_ds/exception.hpp> +#include <cassert> + +// size of test containers +#ifdef _GLIBCXX_DEBUG +# define SIZE 100 +# define RESIZE 20 +#else +# define SIZE 1000 +# define RESIZE 200 +#endif + +using namespace std; +using namespace __gnu_pbds; + +// A simple hash functor. +// hash could serve instead of this functor, but it is not yet +// standard everywhere. +struct int_hash : public unary_function<int, size_t> +{ + inline size_t + operator()(const int& r_i) const + { return r_i; } +}; + + +int main() +{ + // A probing hash table mapping ints to chars. + typedef + gp_hash_table< + int, + int, + int_hash, + equal_to<int>, + // Combining function. + direct_mod_range_hashing<>, + // Probe function. + quadratic_probe_fn<>, + // Resize policy. + hash_standard_resize_policy< + hash_prime_size_policy, + hash_load_check_resize_trigger<>, + /* Allow external access to size. + * Without setting this to true, external resizing + * is not possible. + */ + true> > + map_t; + + map_t g; + + // Insert some elements. + int i; + + for (i = 0; i < SIZE; ++i) + g[i] = 2* i; + + // Check all ok. + assert(g.size() == SIZE); + for (i = 0; i < SIZE; ++i) + assert(g.find(i) != g.end() && g.find(i)->second == 2 * i); + + // Now attempt to resize the table to 200 (impossible). + bool ex_thrown = false; + + try + { + g.resize(RESIZE); + } + catch(__gnu_pbds::resize_error& ) + { + ex_thrown = true; + } + + // Assert an exception was thrown. A probing table cannot contain + // 1000 entries in less than 1000 places. + assert(ex_thrown); + + // Irrespective of the fact that the resize was not successful, the + // container object should still be in a valid state; the following + // checks this. + // Check all ok. + assert(g.size() == SIZE); + for (i = 0; i < SIZE; ++i) + assert(g.find(i) != g.end() && g.find(i)->second == 2 * i); + + return 0; +} diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/hash_initial_size.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/hash_initial_size.cc new file mode 100644 index 000000000..4efe8aae8 --- /dev/null +++ b/libstdc++-v3/testsuite/ext/pb_ds/example/hash_initial_size.cc @@ -0,0 +1,110 @@ +// -*- 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 hash_initial_size_example.cpp + * An example of setting an initial size for a container object. + */ + +/** + * This example shows how to set the initial size of a hash-based + * container object through its resize-policy object. + */ + +#include <cassert> +#include <ext/pb_ds/assoc_container.hpp> +#include <ext/pb_ds/hash_policy.hpp> + +using namespace std; +using namespace __gnu_pbds; + +// A simple hash functor. +// hash could serve instead of this functor, but it is not yet +// standard everywhere. +struct int_hash : public unary_function<int, size_t> +{ + inline size_t + operator()(const int& r_i) const + { return r_i; } +}; + +int main() +{ + // Resize policy type. + typedef + hash_standard_resize_policy< + // Size-policy type. + hash_exponential_size_policy<>, + // Trigger-policy type. + hash_load_check_resize_trigger<>, + /* Allow external access to size. + * This is just used in this example for using the + * get_actual_size method (which won't be accessible without + * this flag. + */ + true> + resize_policy_t; + + // A collision-probing hash table mapping ints to chars. + typedef + gp_hash_table< + int, + char, + int_hash, + equal_to< + int>, + // Combining function. + direct_mask_range_hashing<>, + // Probe function. + linear_probe_fn<>, + // Resize policy. + resize_policy_t> + map_t; + + // A resize-policy object with suggested initial size 256. + resize_policy_t res(hash_exponential_size_policy<>(256)); + + map_t g(int_hash(), + equal_to<int>(), + direct_mask_range_hashing<>(), + linear_probe_fn<>(), + res); + + // Check the actual size of the container object. In this case, this + // should be the initial size given by the size policy object. + assert(g.get_actual_size() == 256); + + // The logical size of g, though is 0 (it does not contain any elements). + assert(g.size() == 0); + + return 0; +} + diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/hash_load_set_change.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/hash_load_set_change.cc new file mode 100644 index 000000000..0251060e7 --- /dev/null +++ b/libstdc++-v3/testsuite/ext/pb_ds/example/hash_load_set_change.cc @@ -0,0 +1,131 @@ +// -*- 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 hash_load_set_change_example.cpp + * An example of setting and changing the load factor of a hash-based + * container object. + */ + +/** + * This example shows how to set and change the load-factor of + * a hash-based container object through its resize-policy object. + */ + +#include <functional> +#include <cassert> +#include <ext/pb_ds/assoc_container.hpp> +#include <ext/pb_ds/hash_policy.hpp> + +using namespace std; +using namespace __gnu_pbds; + +// A simple hash functor. +// hash could serve instead of this functor, but it is not yet +// standard everywhere. +struct int_hash : public unary_function<int, size_t> +{ + inline size_t + operator()(int i) const + { return i; } +}; + +int main() +{ + // A trigger policy type. + typedef hash_load_check_resize_trigger< true> trigger_t; + + // A resize policy type. + typedef + hash_standard_resize_policy< + hash_exponential_size_policy<>, + // Trigger type. + trigger_t, + /* Allow external access to size. + * This is not necessary for setting the load factor, + * but it allows to call get_actual_size. + */ + true> + resize_t; + + // A collision-chaining hash table mapping ints to chars. + typedef + cc_hash_table< + int, + char, + int_hash, + equal_to<int>, + // Combining function. + direct_mask_range_hashing<>, + // Resize policy. + resize_t> + map_t; + + // A trigger policy object with load between 0.3 and 0.8. + trigger_t trigger(static_cast<float>(0.3), static_cast<float>(0.8)); + + // A resize policy object with the above trigger. + resize_t resize(hash_exponential_size_policy<>(), + trigger); + + map_t r_c(int_hash(), + equal_to<int>(), + direct_mask_range_hashing<>(), + resize); + + r_c[1] = 'a'; + + // Check the loads and sizes. + assert(r_c.get_loads().first == static_cast<float>(0.3)); + assert(r_c.get_loads().second == static_cast<float>(0.8)); + assert(r_c.get_actual_size() == 8); + assert(r_c.size() == 1); + + // Note that there is a discrepancy between the loads of the policy + // object and the actual size of the container object. This is + // because the container's construction performs an implicit + // external resize. + r_c[2] = 'b'; + r_c[3] = 'c'; + r_c[4] = 'd'; + + assert(r_c.get_actual_size() == 8); + + // Change the loads. This causes (potentially) a resize. + r_c.set_loads(make_pair(static_cast<float>(0.01), + static_cast<float>(0.05))); + + // The actual size should really change in this case. + assert(r_c.get_actual_size() > 8); + + return 0; +} + diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/hash_mod.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/hash_mod.cc new file mode 100644 index 000000000..3d3f27b21 --- /dev/null +++ b/libstdc++-v3/testsuite/ext/pb_ds/example/hash_mod.cc @@ -0,0 +1,86 @@ +// -*- 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 hash_mod_example.cpp + * An example showing how to use a mod range-hasing function + */ + +/** + * This example shows how to use a hash-based container employing + * a modulo-based range-hashing function. + */ + +#include <functional> +#include <ext/pb_ds/assoc_container.hpp> +#include <ext/pb_ds/hash_policy.hpp> + +using namespace std; +using namespace __gnu_pbds; + +// A simple hash functor. +// hash could serve instead of this functor, but it is not yet +// standard everywhere. +struct int_hash : public unary_function<int, size_t> +{ + inline size_t + operator()(int i) const + { return i; } +}; + +int main() +{ + // In this case, we are worried that the key distribution will be + // skewed. We wish to use a more robust combining function. + + // A collision-chaining hash table mapping ints to chars. + typedef + cc_hash_table< + int, + char, + int_hash, + equal_to<int>, + // Combining function. + direct_mod_range_hashing<> > + map_t; + + map_t r_c; + + // Use regularly. + r_c[32] = 'b'; + r_c[1024] = 'c'; + r_c[4096] = 'd'; + + // The above keys are all powers of 2. A mask combining function + // would hamper performance in such a case. + return 0; +} + diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/hash_resize.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/hash_resize.cc new file mode 100644 index 000000000..8dcf878e6 --- /dev/null +++ b/libstdc++-v3/testsuite/ext/pb_ds/example/hash_resize.cc @@ -0,0 +1,125 @@ +// -*- 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 hash_resize_example.cpp + * An example of externally resizing a map. + */ + +/** + * This example shows how to externally manipulate the size of a hash-based + * container object throught its resize-policy object. + **/ + +#include <functional> +#include <cassert> +#include <ext/pb_ds/assoc_container.hpp> +#include <ext/pb_ds/hash_policy.hpp> + +using namespace std; +using namespace __gnu_pbds; + +// A simple hash functor. +// hash could serve instead of this functor, but it is not yet +// standard everywhere. +struct int_hash : public unary_function<int, size_t> +{ + inline size_t + operator()(const int& r_i) const + { return r_i; } +}; + +int main() +{ + // A probing hash table mapping ints to chars. + typedef + gp_hash_table< + int, + char, + int_hash, + equal_to< + int>, + // Combining function. + direct_mask_range_hashing<>, + // Probe function. + linear_probe_fn<>, + // Resize policy. + hash_standard_resize_policy< + hash_exponential_size_policy<>, + hash_load_check_resize_trigger<>, + /* Allow external access to size. + * Without setting this to true, external resizing + * is not possible. + */ + true> > + map_t; + + map_t g; + + // Check the actual size of the container object. In this case, this + // should be the initial size given by the size policy object. + assert(g.get_actual_size() == 8); + + // Insert some elements. + g[1] = 'a'; + g[2] = 'b'; + g[3] = 'c'; + + // Now resize the table upward. + g.resize(200); + + // Check the actual size of the container object. + // For the policy used in this example, the nearest larger size than + // 200 is 256. + assert(g.get_actual_size() == 256); + + g[67] = 'g'; + g[22] = 'f'; + + // Regardless of the internal size, the logical size should be 5. + assert(g.size() == 5); + + // Now resize the table downward. + g.resize(106); + + // Check the actual size of the container object. + // For the policy used in this example, the nearest larger size than + // 106 is 128. + assert(g.get_actual_size() == 128); + + g[37] = 'f'; + + // Regardless of the internal size, the logical size should be 5. + assert(g.size() == 6); + + return 0; +} + diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/hash_resize_neg.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/hash_resize_neg.cc new file mode 100644 index 000000000..9577dfbc0 --- /dev/null +++ b/libstdc++-v3/testsuite/ext/pb_ds/example/hash_resize_neg.cc @@ -0,0 +1,63 @@ +// { dg-do compile } +// -*- 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 +// <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 hash_bad_resize_example.cpp + * An example showing how *not* to resize a hash-based container. + */ + +/** + * This non-compiling example shows wrong use of hash-based + * containers. By default, resize policies don't allow external size + * access. + **/ + +#include <ext/pb_ds/assoc_container.hpp> + +using namespace std; +using namespace __gnu_pbds; + +int main() +{ + // A collision-chaining hash table mapping ints to chars. + typedef cc_hash_table< int, char> map_t; + + // A map_t object. + map_t h; + + // The following line won't compile. The resize policy needs to be + // configured to allow external resize (by default, this is not + // available). + h.resize(20); // { dg-error "instantiated from" } +} + +// { dg-error "invalid" "" { target *-*-* } 187 } diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/hash_shift_mask.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/hash_shift_mask.cc new file mode 100644 index 000000000..1abe25f67 --- /dev/null +++ b/libstdc++-v3/testsuite/ext/pb_ds/example/hash_shift_mask.cc @@ -0,0 +1,108 @@ +// -*- 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 hash_shift_mask_example.cpp + * An example showing how to write a range-hasing functor. + */ + +/** + * In some rare cases, advance knowledge of the distribution of keys allows + * writing more efficient hash-related policies. + * In the rather simplistic case of the example, it is known in advance that + * all keys have 0 two lowest bits. The example shows how to write + * a range-hashing function disregarding the two lowest bits of the hash value. + */ + +#include <functional> +#include <ext/pb_ds/assoc_container.hpp> +#include <ext/pb_ds/hash_policy.hpp> + +using namespace std; +using namespace __gnu_pbds; + +// A simple hash functor. hash could serve instead of this functor, +// but it is not yet standard everywhere. +struct simple_int_hash : public unary_function<int, size_t> +{ + inline size_t + operator()(int i) const + { return i; } +}; + +// A range-hashing function which shifts 2 bits right and then masks. +class shift_two_mask_range_hashing : private direct_mask_range_hashing<> +{ +public: + typedef size_t size_type; + + // Swaps with a different instant. + void + swap(shift_two_mask_range_hashing& other) + { direct_mask_range_hashing<>::swap(other); } + + // Called by the container when internally resized. + void + notify_resized(size_type size) + { direct_mask_range_hashing<>::notify_resized(size); } + + // Given a hash value, returns a number in the range of the internal + // size of the container. + inline size_type + operator()(size_type hash) const + { return direct_mask_range_hashing<>::operator()(hash >> 2); } +}; + +int +main() +{ + // A collision-chaining hash table mapping ints to chars. + typedef + cc_hash_table< + int, + char, + // Hash function. + simple_int_hash, + equal_to<int>, + // Range hashing function. + shift_two_mask_range_hashing> + map_t; + + map_t h; + + // Use normally. + h[16] = 'a'; + h[256] = 'e'; + h[4] = 'z'; + + return 0; +} + diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/priority_queue_container_traits.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/priority_queue_container_traits.cc new file mode 100644 index 000000000..007c19f43 --- /dev/null +++ b/libstdc++-v3/testsuite/ext/pb_ds/example/priority_queue_container_traits.cc @@ -0,0 +1,200 @@ +// -*- 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 priority_queue_container_traits_example.cpp + * A basic example showing how to use container_traits for querying container types + * for their behavior. + */ + +/** + * The following example shows how to use container_traits in order to print + * out information on an priority queue's behavior, e.g., its underlying + * data structure. + */ + +#include <iostream> +#include <ext/pb_ds/priority_queue.hpp> +#include <ext/pb_ds/tag_and_trait.hpp> + +using namespace std; +using namespace __gnu_pbds; + +template<class DS_Category> +void +print_container_category(DS_Category); + +template<> +void +print_container_category(binary_heap_tag) +{ cout << "Binary heap:" << endl; } + +template<> +void +print_container_category(binomial_heap_tag) +{ cout << "Binomial heap:" << endl; } + +template<> +void +print_container_category(rc_binomial_heap_tag) +{ cout << "Redundant-counter binomial heap:" << endl; } + +template<> +void +print_container_category(pairing_heap_tag) +{ cout << "Pairing heap:" << endl; } + +template<> +void +print_container_category(thin_heap_tag) +{ cout << "Thin heap:" << endl; } + +template<class Invalidation_Guarantee> +void +print_invalidation_guarantee(Invalidation_Guarantee); + +template<> +void +print_invalidation_guarantee(basic_invalidation_guarantee) +{ + cout << "Guarantees only that found references, pointers, and " + "iterators are valid as long as the container object is not " + "modified" << endl; +} + +template<> +void +print_invalidation_guarantee(point_invalidation_guarantee) +{ + cout << "Guarantees that found references, pointers, and " + "point_iterators are valid even if the container object " + "is modified" << endl; +} + +template<> +void +print_invalidation_guarantee(range_invalidation_guarantee) +{ + cout << "Guarantees that iterators remain valid even if the " + "container object is modified" << endl; +} + +void +print_split_join_can_throw(bool can) +{ + if (can) + { + cout << "Can throw exceptions if split or joined" << endl; + return; + } + cout << "Cannot throw exceptions if split or joined" << endl; +} + +template<class DS_Traits> +void +print_container_attributes() +{ + // First print out the data structure category. + print_container_category(typename DS_Traits::container_category()); + + // Now print the attributes of the container. + print_invalidation_guarantee(typename DS_Traits::invalidation_guarantee()); + print_split_join_can_throw(DS_Traits::split_join_can_throw); + cout << endl << endl; +} + +int main() +{ + { + // Print the attributes of a binary heap. + typedef + __gnu_pbds::priority_queue< + int, + std::less<int>, + binary_heap_tag> + t; + + print_container_attributes<container_traits<t> >(); + } + + { + // Print the attributes of a binomial heap. + typedef + __gnu_pbds::priority_queue< + int, + std::less<int>, + binomial_heap_tag> + t; + + print_container_attributes<container_traits<t> >(); + } + + { + // Print the attributes of a redundant-counter binomial heap. + typedef + __gnu_pbds::priority_queue< + int, + std::less<int>, + rc_binomial_heap_tag> + t; + + print_container_attributes<container_traits<t> >(); + } + + { + // Print the attributes of a pairing heap. + typedef + __gnu_pbds::priority_queue< + int, + std::less<int>, + pairing_heap_tag> + t; + + print_container_attributes<container_traits<t> >(); + } + + { + /** + * Print the attributes of a thin heap. + */ + + typedef + __gnu_pbds::priority_queue< + int, + std::less<int>, + thin_heap_tag> + t; + + print_container_attributes<container_traits<t> >(); + } + + return 0; +} diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/priority_queue_dijkstra.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/priority_queue_dijkstra.cc new file mode 100644 index 000000000..74fdc0e62 --- /dev/null +++ b/libstdc++-v3/testsuite/ext/pb_ds/example/priority_queue_dijkstra.cc @@ -0,0 +1,157 @@ +// -*- 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 priority_queue_dijkstra_example.cpp + * A basic example showing how to cross reference a vector and a + * priority-queue for modify. + */ + +/** + * This example shows how to cross-reference priority queues + * and a vector. I.e., using a vector to + * map keys to entries in a priority queue, and using the priority + * queue to map entries to the vector. The combination + * can be used for fast modification of keys. + * + * As an example, a very simple form of Diskstra's algorithm is used. The graph + * is represented by an adjacency matrix. Nodes and vertices are size_ts, and + * it is assumed that the minimal path between any two nodes is less than 1000. + */ + + + +#include <vector> +#include <iostream> +#include <ext/pb_ds/priority_queue.hpp> + +using namespace std; +using namespace __gnu_pbds; + +// The value type of the priority queue. +// The first entry is the node's id, and the second is the distance. +typedef std::pair<size_t, size_t> pq_value; + +// Comparison functor used to compare priority-queue value types. +struct pq_value_cmp : public binary_function<pq_value, pq_value, bool> +{ + inline bool + operator()(const pq_value& r_lhs, const pq_value& r_rhs) const + { + // Note that a value is considered smaller than a different value + // if its distance is* larger*. This is because by STL + // conventions, "larger" entries are nearer the top of the + // priority queue. + return r_rhs.second < r_lhs.second; + } +}; + +int main() +{ + enum + { + // Number of vertices is hard-coded in this example. + num_vertices = 5, + // "Infinity". + graph_inf = 1000 + }; + + // The edge-distance matrix. + // For example, the distance from node 0 to node 1 is 5, and the + // distance from node 1 to node 0 is 2. + const size_t a_a_edge_legnth[num_vertices][num_vertices] = + { + {0, 5, 3, 7, 6}, + {2, 0, 2, 8, 9}, + {2, 1, 0, 8, 0}, + {1, 8, 3, 0, 2}, + {2, 3, 4, 2, 0} + }; + + // The priority queue type. + typedef __gnu_pbds::priority_queue< pq_value, pq_value_cmp> pq_t; + + // The priority queue object. + pq_t p; + + // This vector contains for each node, a find-iterator into the + // priority queue. + vector<pq_t::point_iterator> a_it; + + // First we initialize the data structures. + + // For each node, we push into the priority queue a value + // identifying it with a distance of infinity. + for (size_t i = 0; i < num_vertices; ++i) + a_it.push_back(p.push(pq_value(i, graph_inf))); + + // Now we take the initial node, in this case 0, and modify its + // distance to 0. + p.modify(a_it[0], pq_value(0, 0)); + + // The priority queue contains all vertices whose final distance has + // not been determined, so to finish the algorithm, we must loop + // until it is empty. + while (!p.empty()) + { + // First we find the node whose distance is smallest. + const pq_value& r_v = p.top(); + const size_t node_id = r_v.first; + const size_t dist = r_v.second; + + // This is the node's final distance, so we can print it out. + cout << "The distance from 0 to " << node_id + << " is " << dist << endl; + + // Now we go over the node's neighbors and "relax" the + // distances, if applicable. + for (size_t neighbor_i = 0; neighbor_i < num_vertices; ++neighbor_i) + { + // Potentially, the distance to the neighbor is the distance + // to the currently-considered node + the distance from this + // node to the neighbor. + const size_t pot_dist = dist + a_a_edge_legnth[node_id][neighbor_i]; + + if (a_it[neighbor_i] == a_it[0]) + continue; + + // "Relax" the distance (if appropriate) through modify. + if (pot_dist < a_it[neighbor_i]->second) + p.modify(a_it[neighbor_i], pq_value(neighbor_i, pot_dist)); + } + + // Done with the node, so we pop it. + a_it[node_id] = a_it[0]; + p.pop(); + } + + return 0; +} diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/priority_queue_erase_if.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/priority_queue_erase_if.cc new file mode 100644 index 000000000..0f3ca1fb4 --- /dev/null +++ b/libstdc++-v3/testsuite/ext/pb_ds/example/priority_queue_erase_if.cc @@ -0,0 +1,67 @@ +// -*- 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 priority_queue_erase_if.cpp + * Example showing how to conditionally erase values from a priority queue. + */ + +/** + * This example shows how to erase from a priority queue using erase_if. + */ + +#include <functional> +#include <iostream> +#include <cassert> +#include <ext/pb_ds/priority_queue.hpp> + +using namespace std; +using namespace __gnu_pbds; + +int +main() +{ + __gnu_pbds::priority_queue<int> p; + + // First we insert some values into the container. + for (int i = 0; i < 1000; ++i) + p.push(i); + + assert(p.top() == 999); + + // Now we erase all values that satisfy some predicate, in this case + // one that returns true for all those larger than 500. + p.erase_if(bind1st(less<int>(), 500)); + + // The largest value should be now 500. + assert(p.top() == 500); +} + diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/priority_queue_split_join.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/priority_queue_split_join.cc new file mode 100644 index 000000000..c2d83c0b2 --- /dev/null +++ b/libstdc++-v3/testsuite/ext/pb_ds/example/priority_queue_split_join.cc @@ -0,0 +1,124 @@ +// -*- 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 priority_queue_split_join_example.cpp + * A basic example showing how to split and join priority queues. + */ + +/** + * This example shows how to split and join priority queues. + */ + +#include <functional> +#include <iostream> +#include <cassert> +#include <ext/pb_ds/priority_queue.hpp> + +using namespace std; +using namespace __gnu_pbds; + +int +main() +{ + // Two priority queue objects. + __gnu_pbds::priority_queue<int> even_p, odd_p; + + // First we insert some values: even ones into even_p, and odd ones + // into odd_p. + for (size_t i = 0; i < 10; ++i) + { + even_p.push(2* i); + odd_p.push(2* i + 1); + } + + // Check that each one contains the appropriate 10 values. + assert(even_p.size() == 10); + assert(even_p.top() == 18); + + // Print out the values. + cout << "Initial values in even priority queue:" << endl; + __gnu_pbds::priority_queue<int>::const_iterator it; + for (it = even_p.begin(); it != even_p.end(); ++it) + cout <<* it << endl; + + assert(odd_p.size() == 10); + assert(odd_p.top() == 19); + + // Print out the values. + cout << "Initial values in odd priority queue:" << endl; + for (it = odd_p.begin(); it != odd_p.end(); ++it) + cout <<* it << endl; + + // Now join the queues. + even_p.join(odd_p); + + // Check that each one contains the appropriate values. + + assert(even_p.size() == 20); + assert(even_p.top() == 19); + + // Print out the values. + cout << "After-join values in even priority queue:" << endl; + for (it = even_p.begin(); it != even_p.end(); ++it) + cout <<* it << endl; + + assert(odd_p.size() == 0); + + // Print out the values. + cout << "After-join values in odd priority queue:" << endl; + for (it = odd_p.begin(); it != odd_p.end(); ++it) + cout <<* it << endl; + + // Now split the queues. + even_p.split(bind2nd(modulus<int>(), 2), odd_p); + + // Check that each one contains the appropriate 10 values. + + assert(even_p.size() == 10); + assert(even_p.top() == 18); + + // Print out the values. + cout << "After-split values in even priority queue:" << endl; + for (it = even_p.begin(); it != even_p.end(); ++it) + cout <<* it << endl; + + assert(odd_p.size() == 10); + assert(odd_p.top() == 19); + + // Print out the values. + cout << "After-split values in odd priority queue:" << endl; + for (it = odd_p.begin(); it != odd_p.end(); ++it) + cout <<* it << endl; + + return 0; +} + 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 +// <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 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 <iostream> +#include <cassert> +#include <ext/pb_ds/priority_queue.hpp> +#include <ext/pb_ds/assoc_container.hpp> + +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; +} + diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/ranged_hash.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/ranged_hash.cc new file mode 100644 index 000000000..e9f33b113 --- /dev/null +++ b/libstdc++-v3/testsuite/ext/pb_ds/example/ranged_hash.cc @@ -0,0 +1,151 @@ +// -*- 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 ranged_hash_example.cpp + * A basic example showing how to write a ranged-hash functor. + */ + +/** + * In some cases it is beneficial to write a hash function which determines + * hash values based on the size of the container object. + * The example shows an example of a string-hashing function which + * uses a fast method for hashing strings when the number of strings + * in the container object is small, and a slower but more careful method + * for hashing strings when the number of strings in the container object + * is large. + */ + +#include <functional> +#include <cassert> +#include <string> +#include <ext/pb_ds/assoc_container.hpp> +#include <ext/pb_ds/hash_policy.hpp> + +using namespace std; +using namespace __gnu_pbds; + +/** + * A (somewhat simplistic) ranged-hash function for strings. + * It uses the size of the container object to determine + * the hashing method. For smaller sizes it uses a simple hash function; + * for larger sizes it uses a more complicated hash function. + */ +class simple_string_ranged_hash_fn + : public unary_function<string, size_t> +{ +public: + typedef size_t size_type; + + simple_string_ranged_hash_fn() : m_container_size(0) { } + + // Called to notify that the size has changed. + void + notify_resized(size_t size) + { m_container_size = size; } + + // Called for hashing a string into a size_t in a given range. + size_t + operator()(const string& r_string) + { + /* + * This (simplified) hash algorithm decides that if there are + * fewer than 100 strings in the container it will hash + * a string by summing its characters; otherwise, it will + * perform a more complicated operation in order to produce + * hash values with fewer collisions. + */ + string::const_iterator it = r_string.begin(); + size_t hash = 0; + if (m_container_size < 100) + { + // For this size, perform an accumulate type of operation. + while (it != r_string.end()) + hash += static_cast<size_t>(*it++); + } + else + { + // For this size, perform a different operation. + while (it != r_string.end()) + { + hash += static_cast<size_t>(*it++); + hash *= 5; + } + } + + // The function must, by whatever means, return a size in the + // range 0 to m_container_size. + return hash % m_container_size; + } + + // Swaps content. + void + swap(simple_string_ranged_hash_fn& other) + { + std::swap(m_container_size, other.m_container_size); + } + +private: + // Records the size of the container object. + size_t m_container_size; +}; + +int +main() +{ + // A collision-chaining hash table storing strings. + typedef + cc_hash_table< + string, + null_mapped_type, + null_hash_fn, + equal_to<string>, + simple_string_ranged_hash_fn> + set_t; + + // Note that in the above, the library determines a resize policy + // appropriate for modulo-based range hashing. + set_t h; + + // Use the table normally. + h.insert("Hello, "); + h.insert("world"); + + assert(h.size() == 2); + + assert(h.find("Hello, ") != h.end()); + assert(h.find("world") != h.end()); + + assert(h.find("Goodbye, oh cruel world!") == h.end()); + + return 0; +} + diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/store_hash.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/store_hash.cc new file mode 100644 index 000000000..f762bfdb2 --- /dev/null +++ b/libstdc++-v3/testsuite/ext/pb_ds/example/store_hash.cc @@ -0,0 +1,97 @@ +// -*- 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 store_hash_example.cpp + * An example showing how to store hash-values with + * each entry in a hash-based container. + */ + +/** + * This example shows how to configure a hash-based container to store + * the hash value of each key along with each entry. This technique + * is useful for complex keys (e.g., strings in this example), since + * it lowers the cost of collisions. For simpler types (e.g., integers), + * where the cost of comparing keys is of the same order as the cost + * of comparing hash values, this technique adds unnecessary overhead. + */ + +#include <functional> +#include <string> +#include <ext/pb_ds/assoc_container.hpp> +#include <ext/pb_ds/hash_policy.hpp> + +using namespace std; +using namespace __gnu_pbds; + +// A string hash functor. +struct string_hash : public unary_function<string, size_t> +{ + inline size_t + operator()(string str) const + { + string::const_iterator b = str.begin(); + string::const_iterator e = str.end(); + + size_t hash = 0; + while (b != e) + { + hash *= 5; + hash += static_cast<size_t>(*b); + ++b; + } + return hash; + } +}; + +int main() +{ + // A collision-chaining hash table mapping strings to ints. + typedef + cc_hash_table< + string, + int, + string_hash, + equal_to<string>, + direct_mask_range_hashing<>, + hash_standard_resize_policy<>, + true> + map_t; + + map_t h; + + // Use regularly. + h["Hello, "] = 0; + h["world"] = 1; + + return 0; +} + diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/tree_intervals.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/tree_intervals.cc new file mode 100644 index 000000000..406ab8e0c --- /dev/null +++ b/libstdc++-v3/testsuite/ext/pb_ds/example/tree_intervals.cc @@ -0,0 +1,212 @@ +// -*- 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; +} + diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/tree_join.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/tree_join.cc new file mode 100644 index 000000000..5953804f5 --- /dev/null +++ b/libstdc++-v3/testsuite/ext/pb_ds/example/tree_join.cc @@ -0,0 +1,112 @@ +// -*- 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_join_example.cpp + * An example showing how to join splay_tree_map objects. + * The code in the example is relevant to red-black trees as well. + */ + +/** + * This example shows how to join tree based containers, i.e., taking two + * objects with non-overlapping sets of keys and combining them into + * a single object. + */ + +// For tree +#include <ext/pb_ds/assoc_container.hpp> +// For join_error exception. +#include <ext/pb_ds/exception.hpp> +// For assert +#include <cassert> + +using namespace std; +using namespace __gnu_pbds; +using namespace __gnu_pbds; + +int main() +{ + /* + * + */ + // A splay tree table mapping ints to chars. + typedef tree<int, char, less<int>, splay_tree_tag> map_t; + + // Two map_t object. + map_t h0, h1; + + // Insert some values into the first table. + for (int i0 = 0; i0 < 100; ++i0) + h0.insert(make_pair(i0, 'a')); + + // Insert some values into the second table. + for (int i1 = 0; i1 < 100; ++i1) + h1.insert(make_pair(1000 + i1, 'b')); + + // Since all the elements in h0 are smaller than those in h1, it is + // possible to join the two tables. This is exception free. + h0.join(h1); + + // Check that h0 should now contain all entries, and h1 should be empty. + assert(h0.size() == 200); + assert(h1.empty()); + + + // Two other map_t objects. + map_t h2, h3; + + h2[1] = 'a'; + h2[3] = 'c'; + + h3[2] = 'b'; + + // Now perform an illegal join. + // It is not true that all elements in h2 are smaller than those in + // h3, nor is it true that they are all larger. Hence, attempting to + // join h2, and h3 should result in an exception. + bool exception_thrown = false; + try + { + h2.join(h3); + } + catch (__gnu_pbds::join_error& ) + { + exception_thrown = true; + } + assert(exception_thrown); + + // Since the operation was not performed, the tables should be unaltered. + assert(h2.size() == 2); + assert(h3[2] == 'b'); + + return 0; +} + diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/tree_order_statistics.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/tree_order_statistics.cc new file mode 100644 index 000000000..584574030 --- /dev/null +++ b/libstdc++-v3/testsuite/ext/pb_ds/example/tree_order_statistics.cc @@ -0,0 +1,124 @@ +// -*- 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_order_statistics_example.cpp + * An example showing how to use functors for order-statistics + * in tree-based containers. + */ + +/** + * In some cases tree structure can be used for various purposes asides + * from storing entries by key order. + * This example shows how a tree-based container can be used for + * order-statistics, i.e., for determining the order of each key + * in the (ordered) sequence of keys stored within the container object. + */ + +#include <cassert> +#include <ext/pb_ds/assoc_container.hpp> +#include <ext/pb_ds/tree_policy.hpp> + +using namespace std; +using namespace __gnu_pbds; + +// A red-black tree table storing ints and their order +// statistics. Note that since the tree uses +// tree_order_statistics_node_update as its update policy, then it +// includes its methods by_order and order_of_key. +typedef +tree< + int, + null_mapped_type, + less<int>, + rb_tree_tag, + // This policy updates nodes' metadata for order statistics. + tree_order_statistics_node_update> +set_t; + +int main() +{ + // Insert some entries into s. + set_t s; + s.insert(12); + s.insert(505); + s.insert(30); + s.insert(1000); + s.insert(10000); + s.insert(100); + + // The order of the keys should be: 12, 30, 100, 505, 1000, 10000. + assert(*s.find_by_order(0) == 12); + assert(*s.find_by_order(1) == 30); + assert(*s.find_by_order(2) == 100); + assert(*s.find_by_order(3) == 505); + assert(*s.find_by_order(4) == 1000); + assert(*s.find_by_order(5) == 10000); + assert(s.find_by_order(6) == s.end()); + + // The order of the keys should be: 12, 30, 100, 505, 1000, 10000. + assert(s.order_of_key(10) == 0); + assert(s.order_of_key(12) == 0); + assert(s.order_of_key(15) == 1); + assert(s.order_of_key(30) == 1); + assert(s.order_of_key(99) == 2); + assert(s.order_of_key(100) == 2); + assert(s.order_of_key(505) == 3); + assert(s.order_of_key(1000) == 4); + assert(s.order_of_key(10000) == 5); + assert(s.order_of_key(9999999) == 6); + + // Erase an entry. + s.erase(30); + + // The order of the keys should be: 12, 100, 505, 1000, 10000. + assert(*s.find_by_order(0) == 12); + assert(*s.find_by_order(1) == 100); + assert(*s.find_by_order(2) == 505); + assert(*s.find_by_order(3) == 1000); + assert(*s.find_by_order(4) == 10000); + assert(s.find_by_order(5) == s.end()); + + // The order of the keys should be: 12, 100, 505, 1000, 10000. + assert(s.order_of_key(10) == 0); + assert(s.order_of_key(12) == 0); + assert(s.order_of_key(100) == 1); + assert(s.order_of_key(505) == 2); + assert(s.order_of_key(707) == 3); + assert(s.order_of_key(1000) == 3); + assert(s.order_of_key(1001) == 4); + assert(s.order_of_key(10000) == 4); + assert(s.order_of_key(100000) == 5); + assert(s.order_of_key(9999999) == 5); + + return 0; +} + diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/tree_order_statistics_join.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/tree_order_statistics_join.cc new file mode 100644 index 000000000..18b47c134 --- /dev/null +++ b/libstdc++-v3/testsuite/ext/pb_ds/example/tree_order_statistics_join.cc @@ -0,0 +1,90 @@ +// -*- 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_order_statistics_join_example.cpp + * An example showing how to augment a splay tree to support order statistics. + */ + +// This example shows how join operations still maintain node +// invariants. Specifically, it shows how the objects of containers +// supporting order statistics can be joined into an object supporting +// order statistics. +// While the example does not show this, the same holds for split operations. + +#include <cassert> +#include <ext/pb_ds/assoc_container.hpp> +#include <ext/pb_ds/tree_policy.hpp> + +using namespace std; +using namespace __gnu_pbds; + +// A splay tree table mapping ints to chars and storing the ints order +// statistics. +typedef +tree<int, char, less<int>, + splay_tree_tag, + tree_order_statistics_node_update> +tree_map_t; + +int main() +{ + // Insert some entries into s0. + tree_map_t s0; + s0.insert(make_pair(12, 'a')); + s0.insert(make_pair(505, 'b')); + s0.insert(make_pair(30, 'c')); + + // The order of the keys should be: 12, 30, 505. + assert(s0.find_by_order(0)->first == 12); + assert(s0.find_by_order(1)->first == 30); + assert(s0.find_by_order(2)->first == 505); + + // Insert some entries into s1. + tree_map_t s1; + s1.insert(make_pair(506, 'a')); + s1.insert(make_pair(1222, 'b')); + s1.insert(make_pair(3004, 'a')); + + // Now join s0 and s1. + s0.join(s1); + + // The order of the keys should be: 12, 30, 505, 506, 1222, 3004. + assert(s0.find_by_order(0)->first == 12); + assert(s0.find_by_order(1)->first == 30); + assert(s0.find_by_order(2)->first == 505); + assert(s0.find_by_order(3)->first == 506); + assert(s0.find_by_order(4)->first == 1222); + assert(s0.find_by_order(5)->first == 3004); + + return 0; +} + diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/trie_dna.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/trie_dna.cc new file mode 100644 index 000000000..28c895680 --- /dev/null +++ b/libstdc++-v3/testsuite/ext/pb_ds/example/trie_dna.cc @@ -0,0 +1,118 @@ +// -*- 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 +// <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 trie_dna_example.cpp + * An example showing how to use a trie for storing DNA strings. + */ + +/** + * This example shows how to use a PATRICIA trie for storing + DNA strings. The main point is writing element-access traits + for these strings. +*/ + +#include <cassert> +#include <iostream> +#include <cstdlib> +#include <ext/pb_ds/assoc_container.hpp> +#include <ext/pb_ds/trie_policy.hpp> + +using namespace std; +using namespace __gnu_pbds; + +// DNA is represented by a string. +typedef string dna_t; + +// Following is an element access traits for a DNA string. +struct dna_string_e_access_traits +{ +public: + typedef size_t size_type; + typedef dna_t key_type; + typedef const key_type& const_key_reference; + typedef char e_type; + typedef string::const_iterator const_iterator; + + enum + { + // Number of distinct elements. This is 4 = |{'A', 'C', 'G', 'T'}| + max_size = 4 + }; + + // Returns a const_iterator to the firstelement of r_key. + inline static const_iterator + begin(const_key_reference r_key) + { return r_key.begin(); } + + // Returns a const_iterator to the after-lastelement of r_key. + inline static const_iterator + end(const_key_reference r_key) + { return r_key.end(); } + + // Maps an element to a position. + inline static size_t + e_pos(e_type e) + { + switch(e) + { + case 'A': + return 0; + case 'C': + return 1; + case 'G': + return 2; + case 'T': + return 3; + default: + std::abort(); + }; + } +}; + +// A PATRICIA trie with DNA string element-access traits. +typedef dna_string_e_access_traits traits_type; +typedef trie<dna_t, string, traits_type> trie_type; + +int main() +{ + trie_type t; + + // Now map some DNAs to diseases in namespace STD. + t["ACCGGTTACTGGTA"] = "gonorrhea"; + t["CCGTTATCGGTA"] = "syphlis"; + + // Check gonorrhea already contracted. + assert(t.find("ACCGGTTACTGGTA") != t.end()); + + return 0; +} + diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/trie_prefix_search.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/trie_prefix_search.cc new file mode 100644 index 000000000..98b99a76a --- /dev/null +++ b/libstdc++-v3/testsuite/ext/pb_ds/example/trie_prefix_search.cc @@ -0,0 +1,110 @@ +// -*- 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 trie_prefix_search_example.cpp + * An example showing how to use a trie for searching + * for words with a given prefix. + */ + +/** + * This example shows how to use a PATRICIA trie for searching + * for words with a given prefix. + */ + +#include <cassert> +#include <iostream> +#include <ext/pb_ds/assoc_container.hpp> +#include <ext/pb_ds/trie_policy.hpp> +#include <ext/pb_ds/tag_and_trait.hpp> + +using namespace std; +using namespace __gnu_pbds; + +// A PATRICIA trie with a prefix-search node-updator type. Note that +// since the node updator is trie_prefix_search_node_update, then the +// container includes its method prefix_range. +typedef null_mapped_type mapped_type; +typedef string_trie_e_access_traits<> cmp_fn; +typedef pat_trie_tag tag_type; + +typedef trie<string, mapped_type, cmp_fn, tag_type, + trie_prefix_search_node_update> trie_type; + +// The following helper function takes a trie object and r_key, a +// const reference to a string, and prints all entries whose key +// includes r_key as a prefix. +void +print_prefix_match(const trie_type& t, const string& key) +{ + typedef trie_type::const_iterator const_iterator; + typedef pair<const_iterator, const_iterator> pair_type; + + cout << "All keys whose prefix matches \"" << key << "\":" << endl; + + const pair_type match_range = t.prefix_range(key); + for (const_iterator it = match_range.first; it != match_range.second; ++it) + cout << *it << ' '; + cout << endl; +} + +int main() +{ + trie_type t; + + // Insert some entries. + assert(t.insert("I").second == true); + assert(t.insert("wish").second == true); + assert(t.insert("that").second == true); + assert(t.insert("I").second == false); + assert(t.insert("could").second == true); + assert(t.insert("ever").second == true); + assert(t.insert("see").second == true); + assert(t.insert("a").second == true); + assert(t.insert("poem").second == true); + assert(t.insert("lovely").second == true); + assert(t.insert("as").second == true); + assert(t.insert("a").second == false); + assert(t.insert("trie").second == true); + + // Now search for prefixes. + print_prefix_match(t, ""); + print_prefix_match(t, "a"); + print_prefix_match(t, "as"); + print_prefix_match(t, "ad"); + print_prefix_match(t, "t"); + print_prefix_match(t, "tr"); + print_prefix_match(t, "trie"); + print_prefix_match(t, "zzz"); + + return 0; +} + diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/trie_split.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/trie_split.cc new file mode 100644 index 000000000..c08eb9c98 --- /dev/null +++ b/libstdc++-v3/testsuite/ext/pb_ds/example/trie_split.cc @@ -0,0 +1,85 @@ +// -*- 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 trie_split_example.cpp + * A basic example showing how to split trie-based container objects. + */ + +/** + * This example shows how to split trie based containers, i.e., the opposite + * of a join operation. + */ + +#include <string> +#include <cassert> +#include <ext/pb_ds/assoc_container.hpp> + +using namespace std; +using namespace __gnu_pbds; + +int main() +{ + // A PATRICIA trie table mapping strings to chars. + typedef trie<string, char> map_type; + + // A map_type object. + map_type r; + + // Inserts some entries into r. + for (int i = 0; i < 100; ++ i) + r.insert(make_pair(string(i, 'a'), 'b')); + + // Now split r into a different map_type object. + + // larger_r will hold the larger values following the split. + map_type larger_r; + + // Split all elements with key larger than 'a'^1000 into larger_r. + // This is exception free. + r.split(string(1000, 'a'), larger_r); + + // Since there were no elements with key larger than 'a'^1000, r + // should be unchanged. + assert(r.size() == 100); + assert(r.begin()->first == string("")); + + // Now perform a split which actually changes the content of r. + + // Split all elements with key larger than "aaa" into larger_r. + r.split(string("aaa"), larger_r); + + assert(r.size() == 4); + assert(larger_r.begin()->first == string("aaaa")); + + return 0; +} + diff --git a/libstdc++-v3/testsuite/ext/pb_ds/regression/associative_containers.cc b/libstdc++-v3/testsuite/ext/pb_ds/regression/associative_containers.cc new file mode 100644 index 000000000..26dec124d --- /dev/null +++ b/libstdc++-v3/testsuite/ext/pb_ds/regression/associative_containers.cc @@ -0,0 +1,165 @@ +// -*- 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 assoc_link_regression_test_1.cpp + * A linkage regression test. + */ + + +#include <ext/pb_ds/assoc_container.hpp> +#include <iostream> +#include <cassert> + +using namespace std; +using namespace __gnu_pbds; + +/** + * The following function performs a sequence of operations on an + * associative container object mapping integers to characters. + */ +template<typename Cntnr> +void +some_op_sequence(Cntnr& r_c) +{ + assert(r_c.empty()); + assert(r_c.size() == 0); + + r_c.insert(make_pair(1, 'a')); + + r_c[2] = 'b'; + + assert(!r_c.empty()); + assert(r_c.size() == 2); + + cout << "Key 1 is mapped to " << r_c[1] << endl; + cout << "Key 2 is mapped to " << r_c[2] << endl; + + cout << endl << "All value types in the container:" << endl; + for (typename Cntnr::const_iterator it = r_c.begin(); it != r_c.end(); ++it) + cout << it->first << " -> " << it->second << endl; + + cout << endl; + + r_c.clear(); + + assert(r_c.empty()); + assert(r_c.size() == 0); +} + +void +assoc_link_regression_test_0() +{ + { + // Perform operations on a collision-chaining hash map. + cc_hash_table<int, char> c; + some_op_sequence(c); + } + + { + // Perform operations on a general-probing hash map. + gp_hash_table<int, char> c; + some_op_sequence(c); + } + + { + // Perform operations on a red-black tree map. + tree<int, char> c; + some_op_sequence(c); + } + + { + // Perform operations on a splay tree map. + tree<int, char, less<int>, splay_tree_tag> c; + some_op_sequence(c); + } + + { + // Perform operations on a splay tree map. + tree<int, char, less<int>, ov_tree_tag> c; + some_op_sequence(c); + } + + { + // Perform operations on a list-update map. + list_update<int, char> c; + some_op_sequence(c); + } +} + + +void +assoc_link_regression_test_1() +{ + { + // Perform operations on a collision-chaining hash map. + cc_hash_table<int, char> c; + some_op_sequence(c); + } + + { + // Perform operations on a general-probing hash map. + gp_hash_table<int, char> c; + some_op_sequence(c); + } + + { + // Perform operations on a red-black tree map. + tree<int, char> c; + some_op_sequence(c); + } + + { + // Perform operations on a splay tree map. + tree<int, char, less<int>, splay_tree_tag> c; + some_op_sequence(c); + } + + { + // Perform operations on a splay tree map. + tree<int, char, less<int>, ov_tree_tag> c; + some_op_sequence(c); + } + + { + // Perform operations on a list-update map. + list_update<int, char> c; + some_op_sequence(c); + } +} + +int +main() +{ + assoc_link_regression_test_0(); + assoc_link_regression_test_1(); + return 0; +} diff --git a/libstdc++-v3/testsuite/ext/pb_ds/regression/hash_data_map_rand.cc b/libstdc++-v3/testsuite/ext/pb_ds/regression/hash_data_map_rand.cc new file mode 100644 index 000000000..5656a5b29 --- /dev/null +++ b/libstdc++-v3/testsuite/ext/pb_ds/regression/hash_data_map_rand.cc @@ -0,0 +1,73 @@ +// { dg-require-time "" } +// This can take long on simulators, timing out the test. +// { dg-options "-DITERATIONS=5" { target simulator } } +// { dg-timeout-factor 2.0 } + +// -*- 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 hash_data_map_rand_regression_test.cpp + * Contains a random-operation test for maps and sets. + */ + +#define PB_DS_REGRESSION + +#include <regression/rand/assoc/rand_regression_test.hpp> +#include <regression/common_type.hpp> + +#ifndef ITERATIONS +# ifdef _GLIBCXX_DEBUG +# define ITERATIONS 100 +# else +# define ITERATIONS 5000 +#endif +#endif + +#ifndef KEYS +# ifdef _GLIBCXX_DEBUG +# define KEYS 200 +# else +# define KEYS 10000 +# endif +#endif + +int +main(int argc, char* a_p_argv[]) +{ + using namespace __gnu_pbds::test; + typedef hash_map_tl_t map_tl_t; + + return rand_regression_test(ITERATIONS, KEYS, + "hash_data_map_rand_regression_test", + map_tl_t()); +} + diff --git a/libstdc++-v3/testsuite/ext/pb_ds/regression/hash_no_data_map_rand.cc b/libstdc++-v3/testsuite/ext/pb_ds/regression/hash_no_data_map_rand.cc new file mode 100644 index 000000000..e0530f579 --- /dev/null +++ b/libstdc++-v3/testsuite/ext/pb_ds/regression/hash_no_data_map_rand.cc @@ -0,0 +1,72 @@ +// { dg-require-time "" } +// This can take long on simulators, timing out the test. +// { dg-options "-DITERATIONS=5" { target simulator } } +// { dg-timeout-factor 2.0 } + +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2009, 2011 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 hash_no_data_map_rand_regression_test.cpp + * Contains a random-operation test for maps and sets. + */ + +#define PB_DS_REGRESSION + +#include <regression/rand/assoc/rand_regression_test.hpp> +#include <regression/common_type.hpp> + +#ifndef ITERATIONS +# ifdef _GLIBCXX_DEBUG +# define ITERATIONS 100 +# else +# define ITERATIONS 5000 +#endif +#endif + +#ifndef KEYS +# ifdef _GLIBCXX_DEBUG +# define KEYS 200 +# else +# define KEYS 10000 +# endif +#endif + +int +main(int argc, char* a_p_argv[]) +{ + using namespace __gnu_pbds::test; + typedef hash_set_tl_t map_tl_t; + + return rand_regression_test(ITERATIONS, KEYS, + "hash_no_data_map_rand_regression_test", + map_tl_t()); +} diff --git a/libstdc++-v3/testsuite/ext/pb_ds/regression/list_update_data_map_rand.cc b/libstdc++-v3/testsuite/ext/pb_ds/regression/list_update_data_map_rand.cc new file mode 100644 index 000000000..8bd77816c --- /dev/null +++ b/libstdc++-v3/testsuite/ext/pb_ds/regression/list_update_data_map_rand.cc @@ -0,0 +1,54 @@ +// { dg-require-time "" } + +// -*- 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 lu_data_map_rand_regression_test.cpp + * Contains a random-operation test for maps and sets. + */ + +#define PB_DS_REGRESSION + +#include <regression/rand/assoc/rand_regression_test.hpp> +#include <regression/common_type.hpp> + +int +main(int argc, char* a_p_argv[]) +{ + using namespace __gnu_pbds::test; + typedef lu_map_tl_t map_tl_t; + + return rand_regression_test(50, 10, + "lu_data_map_rand_regression_test", + map_tl_t()); +} + diff --git a/libstdc++-v3/testsuite/ext/pb_ds/regression/list_update_no_data_map_rand.cc b/libstdc++-v3/testsuite/ext/pb_ds/regression/list_update_no_data_map_rand.cc new file mode 100644 index 000000000..72273a8bc --- /dev/null +++ b/libstdc++-v3/testsuite/ext/pb_ds/regression/list_update_no_data_map_rand.cc @@ -0,0 +1,54 @@ +// { dg-require-time "" } + +// -*- 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 lu_no_data_map_rand_regression_test.cpp + * Contains a random-operation test for maps and sets. + */ + +#define PB_DS_REGRESSION + +#include <regression/rand/assoc/rand_regression_test.hpp> +#include <regression/common_type.hpp> + +int +main(int argc, char* a_p_argv[]) +{ + using namespace __gnu_pbds::test; + typedef lu_set_tl_t map_tl_t; + + return rand_regression_test(50, 10, + "lu_no_data_map_rand_regression_test", + map_tl_t()); +} + diff --git a/libstdc++-v3/testsuite/ext/pb_ds/regression/priority_queue_rand.cc b/libstdc++-v3/testsuite/ext/pb_ds/regression/priority_queue_rand.cc new file mode 100644 index 000000000..b21f486d6 --- /dev/null +++ b/libstdc++-v3/testsuite/ext/pb_ds/regression/priority_queue_rand.cc @@ -0,0 +1,61 @@ +// { dg-require-time "" } +// This can take long on simulators, timing out the test. +// { dg-options "-DITERATIONS=5" { target simulator } } +// { dg-timeout-factor 2.0 } + +// -*- 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 priority_queue_rand_regression_test.cpp + * Contains a random-operation test for priority queues. + */ + +#define PB_DS_REGRESSION + +#include <regression/rand/priority_queue/rand_regression_test.hpp> +#include <regression/common_type.hpp> + +#ifndef ITERATIONS +#define ITERATIONS 5000 +#endif +#ifndef KEYS +#define KEYS 10000 +#endif +int +main(int argc, char* a_p_argv[]) +{ + using namespace __gnu_pbds::test; + return rand_regression_test(ITERATIONS, KEYS, + "pq_no_data_map_rand_regression_test", + pq_tl_t()); +} + diff --git a/libstdc++-v3/testsuite/ext/pb_ds/regression/priority_queues.cc b/libstdc++-v3/testsuite/ext/pb_ds/regression/priority_queues.cc new file mode 100644 index 000000000..713c887a1 --- /dev/null +++ b/libstdc++-v3/testsuite/ext/pb_ds/regression/priority_queues.cc @@ -0,0 +1,184 @@ +// -*- 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. + +/** + * This example shows how to use priority queues. It defines a + * function performing a sequence of operations on + * a generic container. It then calls this function with some containers. + */ + +#include <ext/pb_ds/priority_queue.hpp> +#include <iostream> +#include <cassert> + +using namespace std; +using namespace __gnu_pbds; +using namespace __gnu_pbds; + +template<typename Cntnr> +void +some_op_sequence(Cntnr& r_c) +{ + assert(r_c.empty()); + assert(r_c.size() == 0); + + for (size_t i = 0; i < 10; ++i) + r_c.push(i); + + cout << endl << "All values in the container:" << endl; + for (typename Cntnr::const_iterator it = r_c.begin(); it != r_c.end(); + ++it) + cout <<* it << endl; + + assert(!r_c.empty()); + assert(r_c.size() == 10); + + cout << "Popping all values: " << endl; + + while (!r_c.empty()) + { + cout << r_c.top() << endl; + + r_c.pop(); + } + + assert(r_c.empty()); + assert(r_c.size() == 0); + + cout << endl; +} + +void +priority_queue_link_regression_test_0() +{ + { + /* + * Perform operations on a pairing-heap queue. + */ + cout << "Pairing heap" << endl; + __gnu_pbds::priority_queue<int, less<int>, pairing_heap_tag> c; + some_op_sequence(c); + } + + { + /* + * Perform operations on a binomial-heap queue. + */ + cout << "Binomial heap" << endl; + __gnu_pbds::priority_queue<int, less<int>, binomial_heap_tag> c; + some_op_sequence(c); + } + + { + /* + * Perform operations on a binomial-heap queue. + */ + cout << "Redundant-counter binomial heap" << endl; + __gnu_pbds::priority_queue<int, less<int>, rc_binomial_heap_tag> c; + some_op_sequence(c); + } + + { + /* + * Perform operations on a binomial-heap queue. + */ + cout << "Binary heap" << endl; + __gnu_pbds::priority_queue<int, less<int>, binary_heap_tag> c; + some_op_sequence(c); + } + + { + /* + * Perform operations on a thin-heap queue. + */ + cout << "Thin heap" << endl; + __gnu_pbds::priority_queue<int, less<int>, thin_heap_tag> c; + some_op_sequence(c); + } +} + + +void +priority_queue_link_regression_test_1() +{ + { + /* + * Perform operations on a pairing-heap queue. + */ + cout << "Pairing heap" << endl; + __gnu_pbds::priority_queue<int, less<int>, pairing_heap_tag> c; + some_op_sequence(c); + } + + { + /* + * Perform operations on a binomial-heap queue. + */ + cout << "Binomial heap" << endl; + __gnu_pbds::priority_queue<int, less<int>, binomial_heap_tag> c; + some_op_sequence(c); + } + + { + /* + * Perform operations on a binomial-heap queue. + */ + cout << "Redundant-counter binomial heap" << endl; + __gnu_pbds::priority_queue<int, less<int>, rc_binomial_heap_tag> c; + some_op_sequence(c); + } + + { + /* + * Perform operations on a binomial-heap queue. + */ + cout << "Binary heap" << endl; + __gnu_pbds::priority_queue<int, less<int>, binary_heap_tag> c; + some_op_sequence(c); + } + + { + /* + * Perform operations on a thin-heap queue. + */ + cout << "Thin heap" << endl; + __gnu_pbds::priority_queue<int, less<int>, thin_heap_tag> c; + some_op_sequence(c); + } +} + +int +main() +{ + priority_queue_link_regression_test_0(); + priority_queue_link_regression_test_1(); + return 0; +} diff --git a/libstdc++-v3/testsuite/ext/pb_ds/regression/tree_data_map_rand.cc b/libstdc++-v3/testsuite/ext/pb_ds/regression/tree_data_map_rand.cc new file mode 100644 index 000000000..01751e39f --- /dev/null +++ b/libstdc++-v3/testsuite/ext/pb_ds/regression/tree_data_map_rand.cc @@ -0,0 +1,72 @@ +// { dg-require-time "" } +// This can take long on simulators, timing out the test. +// { dg-options "-DITERATIONS=5" { target simulator } } +// { dg-timeout-factor 2.0 } + +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2009, 2011 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_data_map_rand_regression_test.cpp + * Contains a random-operation test for maps and sets. + */ + +#define PB_DS_REGRESSION + +#include <regression/rand/assoc/rand_regression_test.hpp> +#include <regression/common_type.hpp> + +#ifndef ITERATIONS +# ifdef _GLIBCXX_DEBUG +# define ITERATIONS 100 +# else +# define ITERATIONS 5000 +#endif +#endif + +#ifndef KEYS +# ifdef _GLIBCXX_DEBUG +# define KEYS 200 +# else +# define KEYS 10000 +# endif +#endif + +int +main(int argc, char* a_p_argv[]) +{ + using namespace __gnu_pbds::test; + typedef tree_map_tl_t map_tl_t; + + return rand_regression_test(ITERATIONS, KEYS, + "tree_data_map_rand_regression_test", + map_tl_t()); +} diff --git a/libstdc++-v3/testsuite/ext/pb_ds/regression/tree_no_data_map_rand.cc b/libstdc++-v3/testsuite/ext/pb_ds/regression/tree_no_data_map_rand.cc new file mode 100644 index 000000000..c7dadb0d8 --- /dev/null +++ b/libstdc++-v3/testsuite/ext/pb_ds/regression/tree_no_data_map_rand.cc @@ -0,0 +1,73 @@ +// { dg-require-time "" } +// This can take long on simulators, timing out the test. +// { dg-options "-DITERATIONS=5" { target simulator } } +// { dg-timeout-factor 2.0 } + +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2009, 2011 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_no_data_map_rand_regression_test.cpp + * Contains a random-operation test for maps and sets. + */ + +#define PB_DS_REGRESSION + +#include <regression/rand/assoc/rand_regression_test.hpp> +#include <regression/common_type.hpp> + + +#ifndef ITERATIONS +# ifdef _GLIBCXX_DEBUG +# define ITERATIONS 100 +# else +# define ITERATIONS 5000 +#endif +#endif + +#ifndef KEYS +# ifdef _GLIBCXX_DEBUG +# define KEYS 200 +# else +# define KEYS 10000 +# endif +#endif + +int +main(int argc, char* a_p_argv[]) +{ + using namespace __gnu_pbds::test; + typedef tree_set_tl_t map_tl_t; + + return rand_regression_test(ITERATIONS, KEYS, + "tree_no_data_map_rand_regression_test", + map_tl_t()); +} diff --git a/libstdc++-v3/testsuite/ext/pb_ds/regression/trie_data_map_rand.cc b/libstdc++-v3/testsuite/ext/pb_ds/regression/trie_data_map_rand.cc new file mode 100644 index 000000000..8a3902812 --- /dev/null +++ b/libstdc++-v3/testsuite/ext/pb_ds/regression/trie_data_map_rand.cc @@ -0,0 +1,72 @@ +// { dg-require-time "" } +// This can take long on simulators, timing out the test. +// { dg-options "-DITERATIONS=5" { target simulator } } +// { dg-timeout-factor 2.0 } + +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2009, 2011 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 trie_data_map_rand_regression_test.cpp + * Contains a random-operation test for maps and sets. + */ + +#define PB_DS_REGRESSION + +#include <regression/rand/assoc/rand_regression_test.hpp> +#include <regression/common_type.hpp> + +#ifndef ITERATIONS +# ifdef _GLIBCXX_DEBUG +# define ITERATIONS 100 +# else +# define ITERATIONS 5000 +#endif +#endif + +#ifndef KEYS +# ifdef _GLIBCXX_DEBUG +# define KEYS 200 +# else +# define KEYS 10000 +# endif +#endif + +int +main(int argc, char* a_p_argv[]) +{ + using namespace __gnu_pbds::test; + typedef trie_map_tl_t map_tl_t; + + return rand_regression_test(ITERATIONS, KEYS, + "trie_data_map_rand_regression_test", + map_tl_t()); +} diff --git a/libstdc++-v3/testsuite/ext/pb_ds/regression/trie_no_data_map_rand.cc b/libstdc++-v3/testsuite/ext/pb_ds/regression/trie_no_data_map_rand.cc new file mode 100644 index 000000000..2414118da --- /dev/null +++ b/libstdc++-v3/testsuite/ext/pb_ds/regression/trie_no_data_map_rand.cc @@ -0,0 +1,72 @@ +// { dg-require-time "" } +// This can take long on simulators, timing out the test. +// { dg-options "-DITERATIONS=5" { target simulator } } +// { dg-timeout-factor 2.0 } + +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2009, 2010, 2011 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 trie_no_data_map_rand_regression_test.cpp + * Contains a random-operation test for maps and sets. + */ + +#define PB_DS_REGRESSION + +#include <regression/rand/assoc/rand_regression_test.hpp> +#include <regression/common_type.hpp> + +#ifndef ITERATIONS +# ifdef _GLIBCXX_DEBUG +# define ITERATIONS 100 +# else +# define ITERATIONS 5000 +#endif +#endif + +#ifndef KEYS +# ifdef _GLIBCXX_DEBUG +# define KEYS 200 +# else +# define KEYS 10000 +# endif +#endif + +int +main(int argc, char* a_p_argv[]) +{ + using namespace __gnu_pbds::test; + typedef trie_set_tl_t map_tl_t; + + return rand_regression_test(ITERATIONS, KEYS, + "trie_no_data_map_rand_regression_test", + map_tl_t()); +} |