Pastebin launched a little side project called HostCabi.net, check it out ;-)Pastebin is 300% more awesome when you are logged in. Sign Up, it's FREE!
Guest

MinMaxQ

By: a guest on Jun 22nd, 2012  |  syntax: C++  |  size: 1.20 KB  |  hits: 308  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. /*
  2. * Author : Nikhil Garg
  3. * Date   : 2010-12-31
  4. * A templatized MinMax Queue implementation.
  5. * Provides O(1) insert, delete, fimnMin and findMax opertions.
  6. * Assumption : all elements pushed in queue are different. This assumption can be
  7. * relaxed after some extra book keeping code.
  8. *
  9. * I'm pre allocating space for queues. This can also be changed by replacing vectors with STL queues.
  10. *
  11. */
  12.  
  13. #include<vector>
  14. using namespace std;
  15.  
  16. template <class T>
  17. class MinMaxQueue
  18. {
  19.         vector<T> Q, Qmax, Qmin;
  20.         int qf, qmaxf, qminf, qb, qmaxb, qminb;
  21.        
  22.         public :
  23.                
  24.                 MinMaxQueue(int N)
  25.                 {
  26.                         qf = qb = 0;       Q.resize(N);
  27.                         qmaxf = qmaxb = 0; Qmax.resize(N);
  28.                         qminf = qminb = 0; Qmin.resize(N);
  29.                 }
  30.                
  31.                 void push(T v)
  32.                 {
  33.                         while( qmaxf < qmaxb && Qmax[qmaxb -1] < v)     qmaxb--;
  34.                         while( qminf < qminb && Qmin[qminb -1] > v)     qminb--;
  35.                        
  36.                         Q[qb++] = v;
  37.                         Qmax[qmaxb++] = v;
  38.                         Qmin[qminb++] = v;
  39.                 }
  40.                
  41.                 T pop()
  42.                 {
  43.                         T v = Q[qf++];
  44.                         if (v == Qmax[qmaxf])   qmaxf ++;
  45.                         if (v == Qmin[qminf])   qminf ++;
  46.                         return v;
  47.                 }
  48.  
  49.                 T front()   {  return Q[qf];            }
  50.                 T getMax()  {  return Qmax[qmaxf];      }
  51.                 T getMin()  {  return Qmin[qminf];      }
  52.                
  53.                 int size()  {  return qb - qf;          }
  54. };