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