CAD-2017/Queue.h at Idea2 · LFsWang/CAD-2017 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#pragma once

#include<vector>

template<typename TP>
class Queue{
    std::vector<TP> v;
    using sz_t = std::size_t;
    sz_t p2;
    sz_t mask;
    sz_t S,T;
    void init(int p2sz)
    {
        p2 = (1U<<p2sz);
        mask = p2-1;
        v.resize(p2);
    }
    sz_t next(sz_t p) const
    {
        return (p+1)&mask;
    }
    sz_t prev(sz_t p) const
    {
        return (p+p2-1)&mask;
    }
    bool full() const
    {
        return next(S)==T;
    }
    void extend()
    {
        sz_t nsz = p2<<1;
        v.resize(nsz);
        if( S<T )
        {
            for(sz_t i=T;i<p2;++i)
            {
                v[i+p2] = v[i];
            }
            T+=p2;
        }
        p2 = nsz;
        mask = p2-1;
    }
public:
    Queue(){
        init(15);
        S=T=0;
    }
    void push_back(const TP& val){
        if(full())extend();
        v[S] = val;
        S = next(S);
    }
    void push_front(const TP& val){
        if(full())extend();
        T = prev(T);
        v[T] = val;

    }
    TP& front(){
        return v[T];
    }
    void pop_front(){
        T=next(T);
    }
    bool empty() const
    {
        return S==T;
    }

    std::vector<TP>& shift()
    {
        return v;
    }
};