1 /*******************************************************************************
2 
3         Copyright:
4             Copyright (c) 2008 Kris Bell.
5             Some parts copyright (c) 2009-2016 dunnhumby Germany GmbH.
6             All rights reserved.
7 
8         License:
9             Tango Dual License: 3-Clause BSD License / Academic Free License v3.0.
10             See LICENSE_TANGO.txt for details.
11 
12         Version: Initial release: April 2008
13 
14         Authors: Kris
15 
16 *******************************************************************************/
17 
18 module ocean.util.container.more.Vector;
19 
20 import core.stdc..string : memmove;
21 
22 /******************************************************************************
23 
24         A vector of the given value-type V, with maximum depth Size. Note
25         that this does no memory allocation of its own when Size != 0, and
26         does heap allocation when Size == 0. Thus you can have a fixed-size
27         low-overhead instance, or a heap oriented instance.
28 
29 ******************************************************************************/
30 
31 struct Vector (V, int Size = 0)
32 {
33         alias add       push;
34         alias slice     opSlice;
35 
36         public template opOpAssign ( string op : "~" )
37         {
38             alias opOpAssign = push;
39         }
40 
41         static if (Size == 0)
42                   {
43                   private uint depth;
44                   private V[]  vector;
45                   }
46                else
47                   {
48                   private uint     depth;
49                   private V[Size]  vector;
50                   }
51 
52         /***********************************************************************
53 
54                 Clear the vector
55 
56         ***********************************************************************/
57 
58         Vector* clear ()
59         {
60                 depth = 0;
61                 return &this;
62         }
63 
64         /***********************************************************************
65 
66                 Return depth of the vector
67 
68         ***********************************************************************/
69 
70         uint size ()
71         {
72                 return depth;
73         }
74 
75         /***********************************************************************
76 
77                 Return remaining unused slots
78 
79         ***********************************************************************/
80 
81         uint unused ()
82         {
83                 return vector.length - depth;
84         }
85 
86         /***********************************************************************
87 
88                 Returns a (shallow) clone of this vector
89 
90         ***********************************************************************/
91 
92         Vector clone ()
93         {
94                 Vector v;
95                 static if (Size == 0)
96                            v.vector.length = vector.length;
97 
98                 v.vector[0..depth] = vector[0..depth];
99                 v.depth = depth;
100                 return v;
101         }
102 
103         /**********************************************************************
104 
105                 Add a value to the vector.
106 
107                 Throws an exception when the vector is full
108 
109         **********************************************************************/
110 
111         V* add (V value)
112         {
113                 static if (Size == 0)
114                           {
115                           if (depth >= vector.length)
116                               vector.length = vector.length + 64;
117                           vector[depth++] = value;
118                           }
119                        else
120                           {
121                           if (depth < vector.length)
122                               vector[depth++] = value;
123                           else
124                              error (__LINE__);
125                           }
126                 return &vector[depth-1];
127         }
128 
129         /**********************************************************************
130 
131                 Add a value to the vector.
132 
133                 Throws an exception when the vector is full
134 
135         **********************************************************************/
136 
137         V* add ()
138         {
139                 static if (Size == 0)
140                           {
141                           if (depth >= vector.length)
142                               vector.length = vector.length + 64;
143                           }
144                        else
145                           if (depth >= vector.length)
146                               error (__LINE__);
147 
148                 auto p = &vector[depth++];
149                 *p = V.init;
150                 return p;
151         }
152 
153         /**********************************************************************
154 
155                 Add a series of values to the vector.
156 
157                 Throws an exception when the vector is full
158 
159         **********************************************************************/
160 
161         Vector* append (V[] value...)
162         {
163                 foreach (v; value)
164                          add (v);
165                 return &this;
166         }
167 
168         /**********************************************************************
169 
170                 Remove and return the most recent addition to the vector.
171 
172                 Throws an exception when the vector is empty
173 
174         **********************************************************************/
175 
176         V remove ()
177         {
178                 if (depth)
179                     return vector[--depth];
180 
181                 return error (__LINE__);
182         }
183 
184         /**********************************************************************
185 
186                 Index vector entries, where a zero index represents the
187                 oldest vector entry.
188 
189                 Throws an exception when the given index is out of range
190 
191         **********************************************************************/
192 
193         V remove (uint i)
194         {
195                 if (i < depth)
196                    {
197                    if (i is depth-1)
198                        return remove;
199                    --depth;
200                    auto v = vector [i];
201                    memmove (vector.ptr+i, vector.ptr+i+1, V.sizeof * (depth-i));
202                    return v;
203                    }
204 
205                 return error (__LINE__);
206         }
207 
208         /**********************************************************************
209 
210                 Index vector entries, as though it were an array
211 
212                 Throws an exception when the given index is out of range
213 
214         **********************************************************************/
215 
216         V opIndex (uint i)
217         {
218                 if (i < depth)
219                     return vector [i];
220 
221                 return error (__LINE__);
222         }
223 
224         /**********************************************************************
225 
226                 Assign vector entries as though it were an array.
227 
228                 Throws an exception when the given index is out of range
229 
230         **********************************************************************/
231 
232         V opIndexAssign (V value, uint i)
233         {
234                 if (i < depth)
235                    {
236                    vector[i] = value;
237                    return value;
238                    }
239 
240                 return error (__LINE__);
241         }
242 
243         /**********************************************************************
244 
245                 Return the vector as an array of values, where the first
246                 array entry represents the oldest value.
247 
248                 Doing a foreach() on the returned array will traverse in
249                 the opposite direction of foreach() upon a vector
250 
251         **********************************************************************/
252 
253         V[] slice ()
254         {
255                 return vector [0 .. depth];
256         }
257 
258         /**********************************************************************
259 
260                 Throw an exception
261 
262         **********************************************************************/
263 
264         private V error (size_t line)
265         {
266                 throw new ArrayBoundsException (__FILE__, line);
267         }
268 
269         /***********************************************************************
270 
271                 Iterate from the most recent to the oldest vector entries
272 
273         ***********************************************************************/
274 
275         int opApply (scope int delegate(ref V value) dg)
276         {
277                         int result;
278 
279                         for (int i=depth; i-- && result is 0;)
280                              result = dg (vector [i]);
281                         return result;
282         }
283 
284         /***********************************************************************
285 
286                 Iterate from the most recent to the oldest vector entries
287 
288         ***********************************************************************/
289 
290         int opApply (scope int delegate(ref V value, ref bool kill) dg)
291         {
292                         int result;
293 
294                         for (int i=depth; i-- && result is 0;)
295                             {
296                             auto kill = false;
297                             result = dg (vector[i], kill);
298                             if (kill)
299                                 remove (i);
300                             }
301                         return result;
302         }
303 }
304 
305 
306 /*******************************************************************************
307 
308 *******************************************************************************/
309 
310 debug (Vector)
311 {
312         import ocean.io.Stdout;
313 
314         void main()
315         {
316                 Vector!(int, 0) v;
317                 v.add (1);
318 
319                 Vector!(int, 10) s;
320 
321                 Stdout.formatln ("add four");
322                 s.add (1);
323                 s.add (2);
324                 s.add (3);
325                 s.add (4);
326                 foreach (v; s)
327                          Stdout.formatln ("{}", v);
328 
329                 s = s.clone;
330                 Stdout.formatln ("pop one: {}", s.remove);
331                 foreach (v; s)
332                          Stdout.formatln ("{}", v);
333 
334                 Stdout.formatln ("remove[1]: {}", s.remove(1));
335                 foreach (v; s)
336                          Stdout.formatln ("{}", v);
337 
338                 Stdout.formatln ("remove two");
339                 s.remove;
340                 s.remove;
341                 foreach (v; s)
342                          Stdout.formatln ("> {}", v);
343 
344                 s.add (1);
345                 s.add (2);
346                 s.add (3);
347                 s.add (4);
348                 foreach (v, ref k; s)
349                          k = true;
350                 Stdout.formatln ("size {}", s.size);
351         }
352 }