循環的な構造の中で大小関係を推定する

3時より8時の方が後にあり、8時より11時の方が後にありますが、11時より3時の方が後にありそうです。 時計のように巡回している場合、局所的には大小関係のようなものがありそうでも、推移律が成り立つような大小関係はうまく定義できません。

その巡回周期の半分以下の差しか現れない場合のみ、局所的な大小関係が正しく求められます。 時計の例でいえば、差が六時間（十二時間の半分）以内の問題は正しく解けるということです。

特定の期間に含まれるかの判定

ある時刻qが、beginから始まりendを含まずに終わる期間に含まれるかの判定は、以下のように行えます。 問題設定よりbeginよりendが後にあることが保証されるので、期間が巡回周期に近いような場合でも正しく問題が解けます。

constexpr bool includes( size_t begin, size_t end, size_t q ) {
    if (begin > end) {
        return begin <=q || q < end;
    } else {
        return begin <= q && q < end;
    }
}

循環バッファを使ったキューの走査

全然関係ないですが、循環バッファを使ったキューを走査するとき、どこを走査するべきかは、先の問題と同一の解き方ができます。

template<class T, std::size_t N>
class Queue {
    std::array<T, N> buf;
    std::size_t head;
    std::size_t tail;
public:
    Queue() : buf{} head(0), tail(0) {}
    bool empty() const { return tail == head; }
    bool full() const { return (tail+1) % N == head; }
    void push(T elem) { assert( !full() ); buf[tail] = std::move(elem); tail = (tail+1) % N; }
    void pop() { assert( !empty() ); head = (head+1) % N; }
    const T& top() const { assert( !empty() );  return buf[head]; }
    void print() const;
};

こんな感じのキューを想定します。tailは次に要素が来た時に挿入するべき位置、headは最も古く入れた要素の位置です。 なお、この実装だと、空っぽか満杯かを区別できないため、N-1要素しか入れることができません。これを防ぐためには、空っぽであるか（あるいは、満杯であるか）のフラグを用意します。

このとき、このキューに入っている要素を全て書き出すには、以下のようにすればよいです（入れた順）。

template<class T, std::size_t N>
void Queue::print() const {
    if (head < tail) {
        for( std::size_t i = head; i < tail; ++i ) { std::cout << buf[i] << std::endl; }
    } else {
        for( std::size_t i =head; i < N; ++i ) { std::cout << buf[i] << std::endl; }
        for( std::size_t i = 0; i < tail; ++i ) { std::cout << buf[i] << std::endl; }
    }
}