hunt.collection.CirularQueue source code

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