libstdc++-v3/testsuite/ext/pb_ds/example/tree_order_statistics.cc

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005-2018 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
  50 using namespace std;
  51 using 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.
  57 typedef
  58 tree<
  59   int,
  60   null_type,
  61   less<int>,
  62   rb_tree_tag,
  63   // This policy updates nodes' metadata for order statistics.
  64   tree_order_statistics_node_update>
  65 set_t;
  66
  67 int 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