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