yu.container.cirularqueue source code

1 module yu.container.cirularqueue;
2 
3 import core.memory;
4 import std.experimental.allocator.common;
5 import std.experimental.allocator.gc_allocator;
6 import std.traits;
7 import yu.container.common;
8 
9 /**
10  * 循环队列
11     Queue Struct Template.
12     Params:
13         T         = the element type;
14         autoExten = if the Queue is full, will or not auto expand;
15         addToGC   = if use other Allocator, will or not add to GC scan.
16         Allocator = which type Allocator will used
17 */
18 
19 @trusted struct CirularQueue(T, Allocator = GCAllocator, bool autoExten = false, bool addInGC = true)  if(is(T == Unqual!T)) {
20     enum TSize = T.sizeof;
21     enum addToGC = addInGC && hasIndirections!T && !is(Unqual!Allocator == GCAllocator);
22     static if (hasIndirections!T)
23         alias InsertT = T;
24     else
25         alias InsertT = const T;
26     
27     /**
28         Params:
29             size        =  the queue init size. 
30     */
31     this(uint size) {
32         assert(size > 3);
33         _size = size;
34         _data = cast(T[]) _alloc.allocate(TSize * size);
35         static if (addToGC)
36             GC.addRange(_data.ptr, len);
37     }
38 
39     static if (!StaticAlloc!Allocator) {
40         this(uint size, Allocator alloc) {
41             this._alloc = alloc;
42             this(size);
43         }
44     }
45     ~this() {
46         if (_data.ptr) {
47             static if (addToGC)
48                 GC.removeRange(_data.ptr);
49             _alloc.deallocate(_data);
50         }
51     }
52 
53     pragma(inline, true) void clear() {
54 
55         _data[] = T.init;
56         _front = _rear = 0;
57     }
58 
59     pragma(inline, true) @property bool empty() const nothrow {
60         return (_rear == _front);
61     }
62 
63     pragma(inline) @property bool full() const {
64         if ((_rear + 1) % _size == _front)
65             return true; //队满
66         else
67             return false;
68     }
69 
70     pragma(inline, true) @property T front() {
71         assert(!empty());
72         return _data[_front];
73     }
74 
75     pragma(inline, true) @property uint length() {
76         return (_rear - _front + _size) % _size;
77     }
78 
79     pragma(inline, true) @property uint maxLength() nothrow {
80         static if (autoExten) {
81             return uint.max;
82         } else {
83             return _size - 1;
84         }
85     }
86 
87     bool enQueue(InsertT x) {
88         if (full()) { //队满
89             static if (autoExten)
90                 exten();
91             else
92                 return false;
93         }
94         _data[_rear] = x;
95         _rear = (_rear + 1) % _size; //队尾指针加 1 取模
96         return true;
97     }
98 
99     pragma(inline, true) T deQueue(T v = T.init) nothrow {
100         assert(!empty());
101         auto x = _data[_front];
102         _data[_front] = v;
103         _front = (_front + 1) % _size; //队头指针加 1 取模
104         return x;
105     }
106 
107     static if (autoExten) {
108     protected:
109         void exten() {
110             auto size = _size > 128 ? _size + ((_size / 3) * 2) : _size * 2;
111             auto len = TSize * size;
112             auto data = cast(T[]) _alloc.allocate(TSize * size);
113             static if (addToGC)
114                 GC.addRange(data.ptr, len);
115             uint i = 0;
116             while (!empty) {
117                 data[i] = deQueue();
118                 ++i;
119             }
120             _size = size;
121             _front = 0;
122             _rear = i;
123             static if (addToGC)
124                 GC.removeRange(_data.ptr);
125             _alloc.deallocate(_data);
126             _data = data;
127         }
128 
129     }
130     mixin AllocDefine!Allocator;
131 private:
132     @disable this();
133     @disable this(this);
134     uint _front = 0;
135     uint _rear = 0;
136     T[] _data = null;
137     uint _size;
138 }
139 
140 unittest {
141     import std.stdio;
142 
143     auto myq = CirularQueue!(int)(5);
144     writeln("init is empty = ", myq.empty);
145     foreach (i; 0 .. 13) {
146         writeln("enQueue i =  ", i, "  en value = ", myq.enQueue(i));
147     }
148     writeln("end is empty = ", myq.empty);
149     writeln("end is full = ", myq.full);
150     writeln("size  = ", myq.length);
151     int i = 0;
152     while (!myq.empty) {
153         writeln("\n");
154         writeln("\tstart while! i = ", i);
155         writeln("\tfront is = ", myq.front());
156         writeln("\tdeQueue is = ", myq.deQueue());
157 
158         ++i;
159     }
160     writeln("size  = ", myq.length);
161     int x = 2;
162     myq.enQueue(x);
163     writeln("front is = ", myq.front());
164     writeln("size  = ", myq.length);
165     x = 3;
166     myq.enQueue(x);
167     writeln("size  = ", myq.length);
168     writeln("front is = ", myq.front());
169     writeln("deQueue is = ", myq.deQueue());
170     writeln("size  = ", myq.length);
171     writeln("front is = ", myq.front());
172 }