src/context/cdtrail_queue.h

   1 /*********************                                                        */
   2 /*! \file cdtrail_queue.h
   3  ** \verbatim
   4  ** Original author: Tim King
   5  ** Major contributors: none
   6  ** Minor contributors (to current version): Morgan Deters
   7  ** This file is part of the CVC4 project.
   8  ** Copyright (c) 2009-2014  New York University and The University of Iowa
   9  ** See the file COPYING in the top-level source directory for licensing
  10  ** information.\endverbatim
  11  **
  12  ** \brief Context-dependent queue class with an explicit trail of elements
  13  **
  14  ** Context-dependent First-In-First-Out queue class.
  15  ** The implementation is based on a combination of CDList and a CDO<size_t>
  16  ** for tracking the next element to dequeue from the list.
  17  ** The implementation is currently not full featured.
  18  **/
  19
  20
  21 #include "cvc4_private.h"
  22
  23 #ifndef __CVC4__CONTEXT__CDTRAIL_QUEUE_H
  24 #define __CVC4__CONTEXT__CDTRAIL_QUEUE_H
  25
  26 #include "context/context.h"
  27 #include "context/cdlist.h"
  28
  29 namespace CVC4 {
  30 namespace context {
  31
  32
  33 template <class T>
  34 class CDTrailQueue {
  35 private:
  36
  37   /** List of elements in the queue. */
  38   CDList<T> d_list;
  39
  40   /** Points to the next element in the current context to dequeue. */
  41   CDO<size_t> d_iter;
  42
  43
  44 public:
  45
  46   /** Creates a new CDTrailQueue associated with the current context. */
  47   CDTrailQueue(Context* context)
  48     : d_list(context),
  49       d_iter(context, 0)
  50   {}
  51
  52   /** Returns true if the queue is empty in the current context. */
  53   bool empty() const{
  54     return d_iter >= d_list.size();
  55   }
  56
  57   /**
  58    * Enqueues an element in the current context.
  59    * Returns its index in the queue.
  60    */
  61   size_t enqueue(const T& data){
  62     size_t res = d_list.size();
  63     d_list.push_back(data);
  64     return res;
  65   }
  66
  67   size_t frontIndex() const{
  68     return d_iter;
  69   }
  70
  71   const T& front() const{
  72     return d_list[frontIndex()];
  73   }
  74
  75   /** Moves the iterator for the queue forward. */
  76   void dequeue(){
  77     Assert(!empty(), "Attempting to queue from an empty queue.");
  78     d_iter = d_iter + 1;
  79   }
  80
  81   const T& operator[](size_t index) const{
  82     Assert(index < d_list.size());
  83     return d_list[index];
  84   }
  85
  86   size_t size() const{
  87     return d_list.size();
  88   }
  89
  90 };/* class CDTrailQueue<> */
  91
  92 }/* CVC4::context namespace */
  93 }/* CVC4 namespace */
  94
  95 #endif /* __CVC4__CONTEXT__CDTRAIL_QUEUE_H */