queue.hpp

//
// キュー
//
 
#ifndef _COLLECTION2_QUEUE_H_
#define _COLLECTION2_QUEUE_H_
 
#include <stddef.h>
 
#include "common.hpp"
 
namespace collection2 {
 
template <typename Element, typename Size = size_t>
class Queue {
   private:
    Element* const internalData;
 
    Size internalDataSize;
 
    Size head = 0;
 
    Size tail = 0;
 
    Size count = 0;
 
   public:
    Queue(Element* const data, const Size& dataSize);
 
    Queue(const Queue&) = delete;
    Queue& operator=(const Queue&) = delete;
 
    ~Queue() = default;
 
    OperationResult enqueue(const Element& data);
 
    OperationResult dequeue(Element* const data);
 
    Size capacity() const {
        return internalDataSize;
    }
 
    Size amount() const {
        return count;
    }
 
    bool hasSpace() const {
        return count < internalDataSize;
    }
 
    bool isEmpty() const {
        return count == 0;
    }
};
 
template <typename Element, typename Size>
Queue<Element, Size>::Queue(Element* const data, const Size& dataSize) : internalData(data) {
    // ゼロ長のキューなら何もしない
    if (dataSize == 0) {
        internalDataSize = dataSize;
        return;
    }
 
    // 与えられたサイズを上回らない最大の2の冪数を探す
    unsigned char maxbitPos = 0;
    Size size = dataSize;
    while ((size >>= 1) != 0) {
        maxbitPos++;
    }
    internalDataSize = 1 << maxbitPos;
};
 
template <typename Element, typename Size>
OperationResult Queue<Element, Size>::enqueue(const Element& data) {
    // キューがいっぱいなら戻る
    if (!hasSpace()) {
        return OperationResult::Overflow;
    }
 
    // tailの位置にデータを書き込む
    *(internalData + tail) = data;
 
    tail = (tail + 1) & (internalDataSize - 1);
    count++;
 
    return OperationResult::Success;
}
 
template <typename Element, typename Size>
OperationResult Queue<Element, Size>::dequeue(Element* const data) {
    // キューが空なら戻る
    if (isEmpty()) {
        return OperationResult::Empty;
    }
 
    // 読み出して渡す
    *data = *(internalData + head);
 
    head = (head + 1) & (internalDataSize - 1);
    count--;
 
    return OperationResult::Success;
}
 
}  // namespace collection2
 
#endif