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

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006 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 2, 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 COPYING.  If not, write to
  18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
  19 // MA 02111-1307, USA.
  20
  21 // As a special exception, you may use this file as part of a free
  22 // software library without restriction.  Specifically, if other files
  23 // instantiate templates or use macros or inline functions from this
  24 // file, or you compile this file and link it with other files to
  25 // produce an executable, this file does not by itself cause the
  26 // resulting executable to be covered by the GNU General Public
  27 // License.  This exception does not however invalidate any other
  28 // reasons why the executable file might be covered by the GNU General
  29 // Public License.
  30
  31 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  32
  33 // Permission to use, copy, modify, sell, and distribute this software
  34 // is hereby granted without fee, provided that the above copyright
  35 // notice appears in all copies, and that both that copyright notice
  36 // and this permission notice appear in supporting documentation. None
  37 // of the above authors, nor IBM Haifa Research Laboratories, make any
  38 // representation about the suitability of this software for any
  39 // purpose. It is provided "as is" without express or implied
  40 // warranty.
  41
  42 /**
  43  * @file basic_multiset_example.cpp
  44  * A basic example showing how to use multisets.
  45  */
  46
  47
  48 // This example shows how to use "multisets".
  49
  50 // In this example we build a very simple priority queue that also can
  51 // be queried if an entry contains (i.e., it is slightly similar to an
  52 // associative container as well as a priority queue). The priority
  53 // queue adapts a "multiset".
  54
  55 // (Note that there are more efficient ways for implementing this than
  56 // by adapting an associative container. This is just an example for
  57 // "multisets".)
  58
  59 #include <iostream>
  60 #include <cassert>
  61 #include <ext/pb_ds/assoc_container.hpp>
  62
  63 using namespace std;
  64 using namespace __gnu_pbds;
  65
  66 // A simple priority queue that also supports an "contains" query.
  67 class contains_pq
  68 {
  69 public:
  70   // Pushes an integer.
  71   void
  72   push(int i);
  73
  74   // Pops the largest integer and returns it.
  75   int
  76   pop();
  77
  78   // Returns true iff i is contained in the container.
  79   bool
  80   contains(int i) const
  81   { return m_tree.find(i) != m_tree.end(); }
  82
  83   // Returns true iff empty.
  84   bool
  85   empty() const
  86   { return m_tree.empty(); }
  87
  88 private:
  89   // This is the container type we adapt - a "multiset".
  90   // It maps each integer to the number of times it logically appears.
  91   typedef
  92   tree<
  93   int,
  94   size_t,
  95   greater<
  96   int> >
  97   tree_t;
  98
  99 private:
 100   tree_t m_tree;
 101 };
 102
 103 void
 104 contains_pq::
 105 push(int i)
 106 {
 107   // To push i, we insert to the "multiset" that i appears 0 times
 108   // (which is a no-op if i already is contained), then increment the
 109   // number of times i is contained by 1.
 110   ++m_tree.insert(make_pair(i, 0)).first->second;
 111 }
 112
 113 int
 114 contains_pq::
 115 pop()
 116 {
 117   assert(!empty());
 118
 119   // The element we need to pop must be the first one, since tree_t is
 120   // an ordered container.
 121   tree_t::iterator it = m_tree.begin();
 122
 123   const int i = it->first;
 124
 125   // Decrease the number of times the popped element appears in the
 126   // container object. If it is 0 - we erase it.
 127   if (--it->second == 0)
 128     m_tree.erase(it);
 129
 130   return i;
 131 }
 132
 133 int main()
 134 {
 135   contains_pq cpq;
 136
 137   // First we push some elements.
 138   cpq.push(4);
 139   cpq.push(3);
 140   cpq.push(2);
 141   cpq.push(1);
 142   cpq.push(4);
 143
 144   // Note that logically, 4 appears 2 times, and each of 1, 2, and 3
 145   // appear once.
 146   assert(cpq.contains(4));
 147   assert(cpq.contains(3));
 148   assert(cpq.contains(2));
 149   assert(cpq.contains(1));
 150
 151   // Now pop the topmost element - it should be 4.
 152   assert(cpq.pop() == 4);
 153
 154   // Now logically, each of 1, 2, 3, and 4 appear once.
 155   assert(cpq.contains(4));
 156
 157   // We pop the topmost element - it should be 4.
 158   assert(cpq.pop() == 4);
 159
 160   // 4 should not be contained any more.
 161   assert(!cpq.contains(4));
 162
 163   assert(cpq.contains(3));
 164   assert(cpq.contains(2));
 165   assert(cpq.contains(1));
 166
 167   assert(cpq.pop() == 3);
 168   assert(cpq.pop() == 2);
 169   assert(cpq.pop() == 1);
 170
 171   assert(cpq.empty());
 172
 173   return 0;
 174 }
 175