anansi.container.queue source code

1 module anansi.container.queue;
2 import std.algorithm, std.conv;
3 
4 /**
5  *
6  */
7 struct FifoQueue(T) {
8     invariant () {
9         assert (_length <= _buffer.length, "Length must always be smaller than capacity.");
10         assert (_length >= (_buffer.length / 2));
11     }
12 
13     @property bool empty() const {
14         return _length == 0;
15     }
16 
17     public void push(T value) {
18         if (_length == _buffer.length ) {
19             realloc(1 + ((_buffer.length * 3) / 2));
20         }
21         _tail = (_tail + 1) % _buffer.length;
22         _buffer[_tail] = value;
23         _length++;
24     }
25 
26     public void pop()
27     in {
28         assert (!empty);
29     }
30     body {
31         _buffer[_head] = T.init;
32         _head = (_head + 1) % _buffer.length; // [0, 1] 2, 1, 0
33         _length = _length - 1;                // [0, 1] 2, 1, 0
34         auto threshold = _buffer.length / 2;
35         if (_length < threshold) {
36             realloc(_length);
37         }
38     }
39 
40     private void realloc(size_t n) {
41         auto newbuffer = new T[n];
42         if( _length > 0 ) {
43             if( _head == _tail) {
44                 newbuffer[0] = move(_buffer[_head]);
45             }
46             else if( _head < _tail ) {
47                 moveAll(_buffer[_head .. _tail+1], newbuffer[0 .. _length]);
48             }
49             else {
50                 auto trailingItems = _buffer.length - _head;
51                 moveAll(_buffer[_head .. $], newbuffer[]);
52                 moveAll(_buffer[0 .. _tail+1], newbuffer[trailingItems .. $]);
53             }
54             _head = 0;
55             _tail = (_length - 1);
56         }
57         _buffer = newbuffer;
58     } 
59 
60     public @property ref inout(T) front() inout
61     in {
62         assert (!empty);
63     }
64     body {
65         return _buffer[_head];
66     }
67 
68     public @property size_t length() const {
69         return _length;
70     }
71 
72     public @property size_t capacity() const  {
73         return _buffer.length;
74     }
75 
76     private T[] _buffer;
77     private size_t _length;
78     private size_t _head = 0;
79     private size_t _tail = 0;
80 }
81 
82 version (unittest) {
83     import std.stdio;
84 }
85 
86 unittest {
87     writeln("FifoQueue: simple add & remove");
88     auto q = FifoQueue!int();
89     foreach(n; 1 .. 11) {
90         q.push(n);
91         assert (q.length == n, 
92             "(push) Expected length " ~ to!string(n + 1) ~ 
93             ", got " ~ to!string(q.length));
94     }
95 
96     foreach(n; 1 .. 11) {
97         assert (q.front == n, 
98             "(pop) Expected front value " ~ to!string(n) ~ 
99             ", got " ~ to!string(q.front));
100 
101         q.pop();
102     }
103 }
104 
105 unittest {
106     writeln("FifoQueue: Staggered add & remove");
107     auto q = FifoQueue!int();
108 
109     q.push(1);
110     q.push(2);
111     assert(q.length == 2, "Expected length == 2");
112     assert(q.front == 1, "Expected front == 1");
113     
114     q.pop();
115     assert(q.front == 2, "Expected front == 2");
116 
117     q.push(3);
118     q.push(4);
119     assert(q.length == 3, "Expected length == 3");
120     assert(q.front == 2, "Expected front == 2");
121 
122     q.pop();
123     assert(q.length == 2, "Expected length == 2");
124     assert(q.front == 3, "Expected front == 3");
125 
126     q.push(5);
127     q.push(6);
128     q.push(7);
129 
130     assert(q.length == 5, "Expected length == 5");
131     assert(q.front == 3, "Expected front == 3");
132 
133     q.pop();
134     q.pop();
135 
136     assert(q.length == 3, "Expected length == 3");
137     assert(q.front == 5, "Expected front == 5");
138 
139     q.push(8);
140     q.push(9);
141     q.push(10);
142 
143     assert(q.length == 6, "Expected length == 6");
144     assert(q.front == 5, "Expected front == 5");
145    
146     q.pop();
147     q.push(11);
148     q.push(12);
149 
150     assert(q.length == 7, "Expected length == 7");
151     assert(q.front == 6, "Expected front == 6");
152 
153     int x = 6; size_t l = q.length;
154     while (!q.empty) {
155         assert (x == q.front);
156         assert (l == q.length);
157         q.pop();
158         x++;
159         l--;
160     }
161 }