Return to fixedqueue.h CVS log

Up to [Isaki's NoNo m68k/m88k emulator] / nono / lib

nono 1.6.0

//
// nono
// Copyright (C) 2020 nono project
// Licensed under nono-license.txt
//

//
// 固定長キュー
//

#pragma once

#include "header.h"
#include <vector>

// 固定長キュー
// std::queue では出来ないことがいくつかあるので仕方なく車輪の再開発。
// std::vector を親に使っているが empty() と Empty() の動作が異なるなど
// しているため public にせず private 継承している。
//
// T 型で上限 capacity 個のキュー。
// スレッドセーフではない。
template <typename T, uint capacity>
class FixedQueue final : private std::vector<T>
{
	using inherited = std::vector<T>;
 public:
	// コンストラクタ
	FixedQueue()
		: inherited(capacity)
	{
	}

	// デストラクタ
	~FixedQueue() {
	}

	// 空にする
	void Clear() {
		start = 0;
		length = 0;
	}

	// 空きがあれば追加して true を返す。
	// 空きがなければ何もせず false を返す。
	bool Enqueue(const T& val) {
		if (IsFull()) {
			return false;
		} else {
			(*this)[(start + length) % capacity] = val;
			length++;
			return true;
		}
	}

	// 空きがなければ古いのを捨てて追加する。
	void EnqueueForce(const T& val) {
		if (IsFull()) {
			Dequeue();
		}
		Enqueue(val);
	}

	// 取り出し
	// 要素が1つ以上あれば *outp に取り出して true を返す。
	// キューが空なら false を返す。
	bool Dequeue(T *outp) {
		if (length > 0) {
			// 1つ以上あれば取り出し
			*outp = (*this)[start];
			start = (start + 1) % capacity;
			length--;
			return true;
		} else {
			return false;
		}
	}

	// 取り出し
	// 先頭の要素を取り出して返す。
	// キューが空の時に呼ぶと T() が返る。
	T Dequeue() {
		if (length > 0) {
			T val = (*this)[start];
			start = (start + 1) % capacity;
			length--;
			return val;
		} else {
			return T();
		}
	}

	// 現在の要素数を取得
	uint Length() const {
		return length;
	}

	// 要素が空なら true を返す
	bool Empty() const {
		return (length == 0);
	}

	// 要素が一杯なら true を返す
	bool IsFull() const {
		return (Length() >= capacity);
	}

	// 要素を覗き見る。
	// idx は 0 .. length-1 までで、0 がキューの先頭。
	T Peek(uint idx) const {
		// XXX 範囲チェックすべきだがとりあえず
		return (*this)[(start + idx) % capacity];
	}
	// 最新の要素を覗き見る。
	T PeekLatest() const {
		return Peek(Length() - 1);
	}

	// 要素数を返す
	constexpr uint Capacity() const {
		return capacity;
	}

	// 先頭側から追加する。
	// 空きがなければ何もせず false を返す。
	bool PushFront(const T& val) {
		if (IsFull()) {
			return false;
		} else {
			start = (start + capacity - 1) % capacity;
			(*this)[start] = val;
			length++;
			return true;
		}
	}

	// 移動平均値を返す。(T が数値型のときに限る)
	T GetMovingAverage() const
	{
		static_assert(std::is_arithmetic<T>::value, "T must be arithmetic");

		if (Empty()) {
			return 0;
		}
		T sum = 0;
		for (uint i = 0; i < length; i++) {
			sum += Peek(i);
		}
		return sum / length;
	}

 private:
	uint start {};				// 開始位置
	uint length {};				// 現在有効な長さ
};

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.