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