1 #ifndef BLISS_KQUEUE_HH
2 #define BLISS_KQUEUE_HH
3 
4 /*
5   Copyright (c) 2003-2015 Tommi Junttila
6   Released under the GNU Lesser General Public License version 3.
7 
8   This file is part of bliss.
9 
10   bliss is free software: you can redistribute it and/or modify
11   it under the terms of the GNU Lesser General Public License as published by
12   the Free Software Foundation, version 3 of the License.
13 
14   bliss is distributed in the hope that it will be useful,
15   but WITHOUT ANY WARRANTY; without even the implied warranty of
16   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17   GNU Lesser General Public License for more details.
18 
19   You should have received a copy of the GNU Lesser General Public License
20   along with bliss.  If not, see <http://www.gnu.org/licenses/>.
21 */
22 
23 #include "defs.hh"
24 
25 namespace bliss_digraphs {
26 
27 /** \internal
28  * \brief A very simple implementation of queues with fixed capacity.
29  */
30 
31 template <class Type>
32 class KQueue
33 {
34 public:
35   /**
36    * Create a new queue with capacity zero.
37    * The function init() should be called next.
38    */
39   typedef typename std::vector<Type>::iterator type_pointer_substitute;
40 
41   KQueue();
42 
43   ~KQueue();
44 
45   /**
46    * Initialize the queue to have the capacity to hold at most \a N elements.
47    */
48   void init(const unsigned int N);
49 
50   /** Is the queue empty? */
51   bool is_empty() const;
52 
53   /** Return the number of elements in the queue. */
54   unsigned int size() const;
55 
56   /** Remove all the elements in the queue. */
57   void clear();
58 
59   /** Return (but don't remove) the first element in the queue. */
60   Type front() const;
61 
62   /** Remove and return the first element of the queue. */
63   Type pop_front();
64 
65   /** Push the element \a e in the front of the queue. */
66   void push_front(Type e);
67 
68   /** Remove and return the last element of the queue. */
69   Type pop_back();
70 
71   /** Push the element \a e in the back of the queue. */
72   void push_back(Type e);
73 private:
74   type_pointer_substitute entries, end;
75   type_pointer_substitute head, tail;
76   std::vector<Type> entries_vec;
77 };
78 
79 template <class Type>
KQueue()80 KQueue<Type>::KQueue()
81 {
82 }
83 
84 template <class Type>
~KQueue()85 KQueue<Type>::~KQueue()
86 {
87 }
88 
89 template <class Type>
init(const unsigned int k)90 void KQueue<Type>::init(const unsigned int k)
91 {
92   assert(k > 0);
93   entries_vec.resize(k + 1);
94   entries = entries_vec.begin();
95   end = entries + k + 1;
96   head = entries;
97   tail = head;
98 }
99 
100 template <class Type>
clear()101 void KQueue<Type>::clear()
102 {
103   head = entries;
104   tail = head;
105 }
106 
107 template <class Type>
is_empty() const108 bool KQueue<Type>::is_empty() const
109 {
110   return(head == tail);
111 }
112 
113 template <class Type>
size() const114 unsigned int KQueue<Type>::size() const
115 {
116   if(tail >= head)
117     return(tail - head);
118   return((end - head) + (tail - entries));
119 }
120 
121 template <class Type>
front() const122 Type KQueue<Type>::front() const
123 {
124   return *head;
125 }
126 
127 template <class Type>
pop_front()128 Type KQueue<Type>::pop_front()
129 {
130   type_pointer_substitute old_head = head;
131   head++;
132   if(head == end)
133     head = entries;
134   return *old_head;
135 }
136 
137 template <class Type>
push_front(Type e)138 void KQueue<Type>::push_front(Type e)
139 {
140   if(head == entries)
141     head = end - 1;
142   else
143     head--;
144   *head = e;
145 }
146 
147 template <class Type>
push_back(Type e)148 void KQueue<Type>::push_back(Type e)
149 {
150   *tail = e;
151   tail++;
152   if(tail == end)
153     tail = entries;
154 }
155 
156 } // namespace bliss_digraphs
157 
158 #endif
159