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 }