libstdc++-v3/testsuite/ext/pb_ds/example/priority_queue_xref.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 priority_queue_xref_example.cpp
  44  * A basic example showing how to cross-reference priority queues and other
  45  *    containers for erase.
  46  */
  47
  48 /**
  49  * This example shows how to cross-reference priority queues
  50  * and other containers. I.e., using an associative container to
  51  * map keys to entries in a priority queue, and using the priority
  52  * queue to map entries to the associative container. The combination
  53  * can be used for fast operations involving both priorities and
  54  * arbitrary keys.
  55  *
  56  * The most useful examples of this technique are usually from the
  57  * field of graph algorithms (where erasing or modifying an arbitrary
  58  * entry of a priority queue is sometimes necessary), but a full-blown
  59  * example would be too long. Instead, this example shows a very simple
  60  * version of Dijkstra's
  61  */
  62
  63 #include <iostream>
  64 #include <cassert>
  65 #include <ext/pb_ds/priority_queue.hpp>
  66 #include <ext/pb_ds/assoc_container.hpp>
  67
  68 using namespace std;
  69 using namespace __gnu_pbds;
  70
  71 // A priority queue of integers, which supports fast pushes,
  72 // duplicated-int avoidance, and arbitrary-int erases.
  73 class mapped_priority_queue
  74 {
  75 public:
  76
  77   // Pushes an int into the container. If the key is already in, this
  78   // is a no-op.
  79   void
  80   push(const int& r_str);
  81
  82   // Returns a const reference to the largest int in the container.
  83   const int
  84   top() const
  85   {
  86     assert(!empty());
  87     return m_pq.top();
  88   }
  89
  90   // Erases the largest int in the container.
  91   void
  92   pop();
  93
  94   // Erases an arbitrary int. If the int is not in the container, this
  95   // is a no-op, and the return value is false.
  96   bool
  97   erase(const int& r_str);
  98
  99   bool
 100   empty() const
 101   { return m_pq.empty(); }
 102
 103   size_t
 104   size() const
 105   { return m_pq.size(); }
 106
 107 private:
 108   // A priority queue of strings.
 109   typedef __gnu_pbds::priority_queue< int> pq_t;
 110
 111   // A hash-table mapping strings to point_iterators inside the
 112   // priority queue.
 113   typedef cc_hash_table< int, pq_t::point_iterator> map_t;
 114
 115   pq_t m_pq;
 116   map_t m_map;
 117 };
 118
 119 void
 120 mapped_priority_queue::
 121 push(const int& r_str)
 122 {
 123   // First check if the int is already in the container. If so, just return.
 124   if (m_map.find(r_str) != m_map.end())
 125     return;
 126
 127   // Push the int into the priority queue, and store a point_iterator to it.
 128   pq_t::point_iterator pq_it = m_pq.push(r_str);
 129
 130   try
 131     {
 132       // Now make the map associate the int to the point_iterator.
 133       m_map[r_str] = pq_it;
 134     }
 135   catch(...)
 136     {
 137       // If the above failed, we need to remove the int from the
 138       // priority queue as well.
 139       m_pq.erase(pq_it);
 140       throw;
 141     }
 142 }
 143
 144 void
 145 mapped_priority_queue::
 146 pop()
 147 {
 148   assert(!empty());
 149
 150   // Erase the int from the map.
 151   m_map.erase(m_pq.top());
 152
 153   // ...then from the priority queue.
 154   m_pq.pop();
 155 }
 156
 157 bool
 158 mapped_priority_queue::
 159 erase(const int& r_str)
 160 {
 161   map_t::point_iterator map_it = m_map.find(r_str);
 162
 163   // If the int is not in the map, this is a no-op.
 164   if (map_it == m_map.end())
 165     return false;
 166
 167   // Otherwise, we erase it from the priority queue.
 168   m_pq.erase(map_it->second);
 169
 170   // ...then from the map.
 171   m_map.erase(r_str);
 172
 173   return true;
 174 }
 175
 176 int main()
 177 {
 178   // Push some values into the container object.
 179   mapped_priority_queue m;
 180   m.push(1);
 181   m.push(2);
 182
 183   // The following four operations are no-ops: 2 and 1 are already in
 184   // the container.
 185   m.push(2);
 186   m.push(2);
 187   m.push(2);
 188   m.push(1);
 189
 190   m.push(10);
 191   m.push(11);
 192   m.push(12);
 193
 194   // The size should be 5, since m contains the set {1, 2, 10, 11, 12}.
 195   assert(m.size() == 5);
 196
 197   // The largest value should be 12.
 198   assert(m.top() == 12);
 199
 200   // Now erase some values.
 201
 202   // Erasing 1 actually erases a value.
 203   assert(m.erase(1));
 204
 205   // ...but erasing 1 again is a no-op.
 206   assert(!m.erase(1));
 207
 208   // The size should be 5, since m contains the set {2, 10, 11, 12}.
 209   assert(m.size() == 4);
 210
 211   // Now print the values in the container.
 212   while (!m.empty())
 213     {
 214       cout << m.top() << endl;
 215       m.pop();
 216     }
 217
 218   return 0;
 219 }
 220