src/context/cdtrail_queue.h

   1 /*********************                                                        */
   2 /*! \file cdtrail_queue.h
   3  ** \verbatim
   4  ** Top contributors (to current version):
   5  **   Tim King, Mathias Preiner
   6  ** This file is part of the CVC4 project.
   7  ** Copyright (c) 2009-2021 by the authors listed in the file AUTHORS
   8  ** in the top-level source directory and their institutional affiliations.
   9  ** All rights reserved.  See the file COPYING in the top-level source
  10  ** directory for licensing 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 #include "cvc4_private.h"
  21
  22 #ifndef CVC4__CONTEXT__CDTRAIL_QUEUE_H
  23 #define CVC4__CONTEXT__CDTRAIL_QUEUE_H
  24
  25 #include "context/context.h"
  26 #include "context/cdlist.h"
  27
  28 namespace CVC4 {
  29 namespace context {
  30
  31
  32 template <class T>
  33 class CDTrailQueue {
  34 private:
  35
  36   /** List of elements in the queue. */
  37   CDList<T> d_list;
  38
  39   /** Points to the next element in the current context to dequeue. */
  40   CDO<size_t> d_iter;
  41
  42
  43 public:
  44
  45   /** Creates a new CDTrailQueue associated with the current context. */
  46   CDTrailQueue(Context* context)
  47     : d_list(context),
  48       d_iter(context, 0)
  49   {}
  50
  51   /** Returns true if the queue is empty in the current context. */
  52   bool empty() const{
  53     return d_iter >= d_list.size();
  54   }
  55
  56   /**
  57    * Enqueues an element in the current context.
  58    * Returns its index in the queue.
  59    */
  60   size_t enqueue(const T& data){
  61     size_t res = d_list.size();
  62     d_list.push_back(data);
  63     return res;
  64   }
  65
  66   size_t frontIndex() const{
  67     return d_iter;
  68   }
  69
  70   const T& front() const{
  71     return d_list[frontIndex()];
  72   }
  73
  74   /** Moves the iterator for the queue forward. */
  75   void dequeue(){
  76     Assert(!empty()) << "Attempting to queue from an empty queue.";
  77     d_iter = d_iter + 1;
  78   }
  79
  80   const T& operator[](size_t index) const{
  81     Assert(index < d_list.size());
  82     return d_list[index];
  83   }
  84
  85   size_t size() const{
  86     return d_list.size();
  87   }
  88
  89 };/* class CDTrailQueue<> */
  90
  91 }/* CVC4::context namespace */
  92 }/* CVC4 namespace */
  93
  94 #endif /* CVC4__CONTEXT__CDTRAIL_QUEUE_H */