File indexing completed on 2021-12-21 12:50:22

0001 /*
0002  *  ksokoban - a Sokoban game by KDE
0003  *  Copyright (C) 1998  Anders Widell  <d95-awi@nada.kth.se>
0004  *
0005  *  This program is free software; you can redistribute it and/or modify
0006  *  it under the terms of the GNU General Public License as published by
0007  *  the Free Software Foundation; either version 2 of the License, or
0008  *  (at your option) any later version.
0009  *
0010  *  This program is distributed in the hope that it will be useful,
0011  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
0012  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
0013  *  GNU General Public License for more details.
0014  *
0015  *  You should have received a copy of the GNU General Public License
0016  *  along with this program; if not, write to the Free Software
0017  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
0018  */
0019 
0020 #ifndef QUEUE_H
0021 #define QUEUE_H
0022 
0023 #include <assert.h>
0024 
0025 template <class Type, int SizePow2>
0026 class Queue {
0027 private:
0028   Type *queue_;
0029   long   head_, tail_;
0030 
0031 public:
0032   void clear() { head_ = tail_ = 0; }
0033   bool empty() { return head_ == tail_; }
0034   bool full() { return ((tail_ + 1) & ((1l<<SizePow2)-1)) == head_; }
0035 
0036   Queue() {
0037     queue_ = new Type[1l << SizePow2];
0038     clear();
0039   }
0040   ~Queue() { delete [] queue_; }
0041 
0042   void enqueue(Type _x) {
0043     assert(!full());
0044     queue_[tail_] = _x;
0045     tail_ = (tail_ + 1) & ((1l<<SizePow2)-1);
0046   }
0047 
0048   Type dequeue() {
0049     assert(!empty());
0050     Type x = queue_[head_];
0051     head_ = (head_ + 1) & ((1l<<SizePow2)-1);
0052     return x;
0053   }
0054 };
0055 
0056 #endif  /* QUEUE_H */