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()80KQueue<Type>::KQueue() 81 { 82 } 83 84 template <class Type> ~KQueue()85KQueue<Type>::~KQueue() 86 { 87 } 88 89 template <class Type> init(const unsigned int k)90void 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()101void KQueue<Type>::clear() 102 { 103 head = entries; 104 tail = head; 105 } 106 107 template <class Type> is_empty() const108bool KQueue<Type>::is_empty() const 109 { 110 return(head == tail); 111 } 112 113 template <class Type> size() const114unsigned 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() const122Type KQueue<Type>::front() const 123 { 124 return *head; 125 } 126 127 template <class Type> pop_front()128Type 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)138void 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)148void 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