1// -*- C++ -*- 2 3// Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc. 4// 5// This file is part of the GNU ISO C++ Library. This library is free 6// software; you can redistribute it and/or modify it under the terms 7// of the GNU General Public License as published by the Free Software 8// Foundation; either version 3, or (at your option) any later 9// version. 10 11// This library is distributed in the hope that it will be useful, but 12// WITHOUT ANY WARRANTY; without even the implied warranty of 13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14// General Public License for more details. 15 16// You should have received a copy of the GNU General Public License 17// along with this library; see the file COPYING3. If not see 18// <http://www.gnu.org/licenses/>. 19 20 21// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 22 23// Permission to use, copy, modify, sell, and distribute this software 24// is hereby granted without fee, provided that the above copyright 25// notice appears in all copies, and that both that copyright notice 26// and this permission notice appear in supporting documentation. None 27// of the above authors, nor IBM Haifa Research Laboratories, make any 28// representation about the suitability of this software for any 29// purpose. It is provided "as is" without express or implied 30// warranty. 31 32/** 33 * @file tree_order_statistics_example.cpp 34 * An example showing how to use functors for order-statistics 35 * in tree-based containers. 36 */ 37 38/** 39 * In some cases tree structure can be used for various purposes asides 40 * from storing entries by key order. 41 * This example shows how a tree-based container can be used for 42 * order-statistics, i.e., for determining the order of each key 43 * in the (ordered) sequence of keys stored within the container object. 44 */ 45 46#include <cassert> 47#include <ext/pb_ds/assoc_container.hpp> 48#include <ext/pb_ds/tree_policy.hpp> 49 50using namespace std; 51using namespace __gnu_pbds; 52 53// A red-black tree table storing ints and their order 54// statistics. Note that since the tree uses 55// tree_order_statistics_node_update as its update policy, then it 56// includes its methods by_order and order_of_key. 57typedef 58tree< 59 int, 60 null_mapped_type, 61 less<int>, 62 rb_tree_tag, 63 // This policy updates nodes' metadata for order statistics. 64 tree_order_statistics_node_update> 65set_t; 66 67int main() 68{ 69 // Insert some entries into s. 70 set_t s; 71 s.insert(12); 72 s.insert(505); 73 s.insert(30); 74 s.insert(1000); 75 s.insert(10000); 76 s.insert(100); 77 78 // The order of the keys should be: 12, 30, 100, 505, 1000, 10000. 79 assert(*s.find_by_order(0) == 12); 80 assert(*s.find_by_order(1) == 30); 81 assert(*s.find_by_order(2) == 100); 82 assert(*s.find_by_order(3) == 505); 83 assert(*s.find_by_order(4) == 1000); 84 assert(*s.find_by_order(5) == 10000); 85 assert(s.find_by_order(6) == s.end()); 86 87 // The order of the keys should be: 12, 30, 100, 505, 1000, 10000. 88 assert(s.order_of_key(10) == 0); 89 assert(s.order_of_key(12) == 0); 90 assert(s.order_of_key(15) == 1); 91 assert(s.order_of_key(30) == 1); 92 assert(s.order_of_key(99) == 2); 93 assert(s.order_of_key(100) == 2); 94 assert(s.order_of_key(505) == 3); 95 assert(s.order_of_key(1000) == 4); 96 assert(s.order_of_key(10000) == 5); 97 assert(s.order_of_key(9999999) == 6); 98 99 // Erase an entry. 100 s.erase(30); 101 102 // The order of the keys should be: 12, 100, 505, 1000, 10000. 103 assert(*s.find_by_order(0) == 12); 104 assert(*s.find_by_order(1) == 100); 105 assert(*s.find_by_order(2) == 505); 106 assert(*s.find_by_order(3) == 1000); 107 assert(*s.find_by_order(4) == 10000); 108 assert(s.find_by_order(5) == s.end()); 109 110 // The order of the keys should be: 12, 100, 505, 1000, 10000. 111 assert(s.order_of_key(10) == 0); 112 assert(s.order_of_key(12) == 0); 113 assert(s.order_of_key(100) == 1); 114 assert(s.order_of_key(505) == 2); 115 assert(s.order_of_key(707) == 3); 116 assert(s.order_of_key(1000) == 3); 117 assert(s.order_of_key(1001) == 4); 118 assert(s.order_of_key(10000) == 4); 119 assert(s.order_of_key(100000) == 5); 120 assert(s.order_of_key(9999999) == 5); 121 122 return 0; 123} 124 125