1 module betterclist; 2 3 import std.algorithm; 4 import std.range; 5 import std.traits; 6 7 struct List(T, long N = -1) 8 { 9 alias ElementType = T; 10 11 /// Whether List has fixed size, which means it is backed by a static array 12 enum isSized = N >= 0; 13 static if (isSized) 14 { 15 /// Static array with capacity N that holds the List elements. 16 T[N] array; 17 18 /// Construct List with initial elements. 19 this(Args...)(auto ref Args args) 20 { 21 pushBack(args); 22 } 23 } 24 else 25 { 26 /// Slice with dynamic capacity that holds the List elements. 27 T[] array; 28 29 /// Construct List with backing slice and optional initial elements. 30 this(Args...)(T[] backingSlice, auto ref Args args) 31 { 32 this.array = backingSlice; 33 static if (args.length > 0) 34 { 35 pushBack(args); 36 } 37 } 38 39 /// Construct List with backing pointer and capacity and optional initial elements. 40 this(Args...)(T* backingArrayPointer, size_t capacity, auto ref Args args) 41 { 42 this(backingArrayPointer[0 .. capacity], args); 43 } 44 45 /// Construct List with backing buffer slice and optional initial elements. 46 this(Args...)(void[] backingSlice, auto ref Args args) 47 { 48 this(cast(T[]) backingSlice, args); 49 } 50 51 /// Construct List with backing buffer pointer and size and optional initial elements. 52 this(Args...)(void* backingArrayPointer, size_t bufferSize, auto ref Args args) 53 { 54 this(backingArrayPointer[0 .. bufferSize], args); 55 } 56 } 57 /// Current used length, must be less than array's length. 58 /// This is readonly accessible by the `length` property from used slice. 59 private size_t usedLength = 0; 60 61 invariant 62 { 63 assert(usedLength <= array.length); 64 } 65 66 @nogc pure 67 { 68 /// List element capacity, which is the backing array's length. 69 @property size_t capacity() const @safe nothrow 70 { 71 return array.length; 72 } 73 74 /// Available capacity for inserting elements. 75 @property size_t availableCapacity() const @safe nothrow 76 { 77 return capacity - usedLength; 78 } 79 80 /// Returns whether there are no elements in List. 81 @property bool empty() const @safe nothrow 82 { 83 return usedLength == 0; 84 } 85 86 /// Returns whether List is full, that is, has no more available capacity. 87 @property bool full() const @safe nothrow 88 { 89 return usedLength == capacity; 90 } 91 92 /// Get a slice for the used elements. 93 auto usedSlice() inout 94 { 95 return array[0 .. usedLength]; 96 } 97 /// Get a slice for the remaining elements. 98 private auto remainingSlice() inout 99 { 100 return array[usedLength .. capacity]; 101 } 102 103 /// Get a slice for the used elements. 104 auto opIndex() inout 105 { 106 return usedSlice; 107 } 108 /// Index the slice of used elements. 109 auto ref opIndex(const size_t index) inout 110 in { assert(index < usedLength); } 111 do 112 { 113 return usedSlice[index]; 114 } 115 116 /// Get used length. 117 size_t opDollar(const size_t pos : 0)() const 118 { 119 return usedLength; 120 } 121 /// Alias this allows operations to target used slice by default. 122 alias usedSlice this; 123 } 124 125 /++ 126 + Push a value in the end of List. 127 + Returns: 0 if value was successfully inserted, 1 otherwise. 128 +/ 129 long pushBack(U)(auto ref U value) 130 if (!isInputRange!U) 131 { 132 if (full) 133 { 134 return 1; 135 } 136 array[usedLength] = value; 137 usedLength++; 138 return 0; 139 } 140 141 /++ 142 + Push a range of values to the end of List. 143 + Returns: number of values not inserted into List: 144 + 0 if all values were inserted successfully, 145 + positive number if the number of remaining elements is known, 146 + -1 if the number of remaining elements is not know. 147 +/ 148 long pushBack(R)(auto ref R range) 149 if (isInputRange!R) 150 { 151 static if (hasLength!R) 152 { 153 auto rangeLength = range.length; 154 if (rangeLength > availableCapacity) 155 { 156 range.take(availableCapacity).copy(remainingSlice); 157 usedLength = capacity; 158 return cast(typeof(return))(range.length - availableCapacity); 159 } 160 range.copy(remainingSlice); 161 usedLength += rangeLength; 162 return 0; 163 } 164 else 165 { 166 while (!range.empty && usedLength < capacity) 167 { 168 array[usedLength] = range.front; 169 usedLength++; 170 range.popFront; 171 } 172 return range.empty ? 0 : -1; 173 } 174 } 175 176 /// Ditto 177 long pushBack(Args...)(auto ref Args args) 178 if (args.length > 1) 179 { 180 return pushBack(only(args)); 181 } 182 alias push = pushBack; 183 184 /// Push back elements on `list ~= args` 185 auto opOpAssign(string op : "~", Args...)(auto ref Args args) 186 { 187 return pushBack(args); 188 } 189 190 /++ 191 + Pop the last element from List. 192 + If element type has elaborate destructor, popped slot is reinitialized to `T.init`. 193 +/ 194 void popBack() 195 { 196 if (!empty) 197 { 198 usedLength--; 199 static if (hasElaborateDestructor!T) 200 { 201 array[usedLength] = T.init; 202 } 203 } 204 } 205 /++ 206 + Pop `count` elements from the back of the List. 207 + If element type has elaborate destructor, popped slots are reinitialized to `T.init`. 208 +/ 209 void popBack(const size_t count) 210 { 211 auto minCount = min(count, usedLength); 212 static if (hasElaborateDestructor!T) 213 { 214 usedSlice[$ - minCount .. $] = T.init; 215 } 216 usedLength -= minCount; 217 } 218 alias pop = popBack; 219 220 /++ 221 + Clear all elements of List. 222 + If element type has elaborate destructor, popped slots are reinitialized to `T.init`. 223 +/ 224 void clear() 225 out { assert(length == 0); assert(empty); } 226 do 227 { 228 static if (hasElaborateDestructor!T) 229 { 230 usedSlice[] = T.init; 231 } 232 usedLength = 0; 233 } 234 } 235 236 /// Construct List from static array, inferring element type. 237 List!(T, N) list(T, uint N)(const auto ref T[N] values) 238 { 239 return typeof(return)(values[]); 240 } 241 /// 242 unittest 243 { 244 int[3] values = [1, 2, 3]; 245 assert(list(values) == values); 246 } 247 248 /// Construct List from slice. 249 List!(T) list(T)(auto ref T[] array) 250 { 251 typeof(return) l = array; 252 l.usedLength = array.length; 253 return l; 254 } 255 /// 256 unittest 257 { 258 auto v = list([1, 2, 3]); 259 assert(v == [1, 2, 3]); 260 } 261 262 /// Construct List from elements, specifying element type. 263 List!(U, Args.length) list(U, Args...)(const auto ref Args args) 264 { 265 return typeof(return)(args); 266 } 267 /// 268 unittest 269 { 270 const auto v = list!double(1, 2, 3); 271 assert(is(Unqual!(typeof(v)) == List!(double, 3))); 272 assert(v == [1.0, 2.0, 3.0]); 273 } 274 275 /// Construct List from elements, inferring element type. 276 auto list(Args...)(const auto ref Args args) 277 if (!is(CommonType!Args == void)) 278 { 279 return .list!(CommonType!Args)(args); 280 } 281 /// 282 unittest 283 { 284 const auto v = list(1f, 2, 3); 285 assert(is(Unqual!(typeof(v)) == List!(float, 3))); 286 assert(v == [1f, 2f, 3f]); 287 } 288 289 /// Construct List with the specified length and type from Input Range. 290 List!(U, N) list(U, size_t N, T)(scope T range) 291 if (isInputRange!T) 292 { 293 return typeof(return)(range.take(N)); 294 } 295 /// 296 unittest 297 { 298 const auto l = list!(double, 4)(repeat(42)); 299 assert(l == [42.0, 42.0, 42.0, 42.0]); 300 } 301 302 /// Construct List with the specified length from Input Range, inferring element type. 303 auto list(size_t N, T)(scope T range) 304 if (isInputRange!T) 305 { 306 return .list!(ElementType!T, N)(range); 307 } 308 /// 309 unittest 310 { 311 const auto l = list!4(repeat(42)); 312 assert(l == [42, 42, 42, 42]); 313 } 314 315 /// Construct List from Input Range at compile time. 316 auto list(alias values)() 317 if (isInputRange!(typeof(values))) 318 { 319 enum l = .list!(size_t(values.length))(values); 320 return l; 321 } 322 /// 323 unittest 324 { 325 auto l = list!(iota(4).map!"a * a"); 326 assert(l == [0, 1, 4, 9]); 327 l = list!(repeat(42).take(4)); 328 assert(l == [42, 42, 42, 42]); 329 } 330 331 unittest 332 { 333 List!(int, 8) l; 334 assert(l.length == 0); 335 assert(l[] == null); 336 assert(l == null); 337 338 assert(l.pushBack(5) == 0); 339 assert(l.length == 1); 340 assert(l[0] == 5); 341 assert(l == [5]); 342 assert(l[0 .. $] == [5]); 343 344 l[0] = 10; 345 assert(l.length == 1); 346 assert(l[0] == 10); 347 assert(l == [10]); 348 assert(l[0 .. $] == [10]); 349 350 assert(l.pushBack(iota(4)) == 0); 351 assert(l.length == 5); 352 assert(l == [10, 0, 1, 2, 3]); 353 assert(l[].sum == 16); 354 assert(l[$-2 .. $] == [2, 3]); 355 356 int five() { return 5; } 357 assert(l.pushBack(generate!five) < 0); 358 assert(l.full); 359 assert(l == [10, 0, 1, 2, 3, 5, 5, 5]); 360 361 assert(l.pushBack(500) > 0); 362 assert(l.back == 5); 363 l.popBack(); 364 assert(l.length == l.capacity - 1); 365 assert((l ~= 500) == 0); 366 assert(l.full); 367 assert(l.back == 500); 368 369 l.popBack(2); 370 assert(l.length == l.capacity - 2); 371 l.clear(); 372 assert(l.empty); 373 l.popBack(42); 374 } 375 376 unittest 377 { 378 int[10] array = 42; 379 auto l = List!(int)(array[]); 380 assert(l.capacity == 10); 381 assert(l.length == 0); 382 assert(l[] == null); 383 assert(l == null); 384 385 auto l2 = List!(int)(array[], 0, 1); 386 assert(l2.capacity == 10); 387 assert(l2.length == 2); 388 assert(l2[] == [0, 1]); 389 assert(l2 == [0, 1]); 390 } 391 392 unittest 393 { 394 import std.experimental.allocator.mallocator : Mallocator; 395 void[] buffer = Mallocator.instance.allocate(8 * int.sizeof); 396 397 auto l = List!(int)(buffer); 398 assert(l.capacity == 8); 399 400 Mallocator.instance.deallocate(buffer); 401 } 402 403 unittest 404 { 405 import betterclist : List; 406 407 // Lists may be backed by static arrays by passing the capacity to template 408 List!(int, 16) list; 409 assert(list.capacity == 16); 410 411 // Lists track their own element usage 412 assert(list.length == 0); 413 assert(list.empty); 414 415 list.pushBack(0); // pushBack inserts an element in the end of the used slice 416 assert(list.length == 1); 417 assert(list[0] == 0); // opIndex(size_t) indexes used elements slice, `list[1]` is out of bounds here 418 list[0] = 1; // assigning to index works, if your List is mutable 419 420 list.push(2, 3); // push is an alias to pushBack. Several elements may be pushed at once 421 assert(list[] == [1, 2, 3]); // opIndex() returns the used slice 422 assert(list.availableCapacity == 13); 423 424 list ~= 4; // operator ~= also calls pushBack 425 assert(list == [1, 2, 3, 4]); // Lists are aliased to the used slice by `alias this` 426 assert(list[2 .. $] == [3, 4]); // this means stuff like opDollar, slicing and length just works 427 // so does foreach 428 import std.stdio : writeln; 429 foreach (value; list) 430 { 431 writeln(value); 432 } 433 // so does importing common range stuff 434 import std.range; 435 assert(list.front == 1); 436 assert(list.back == 4); 437 438 list.popBack(); // pops the last value. If element type has elaborate detructors, reinitializes element to it's `.init` value 439 assert(list == [1, 2, 3]); 440 list.popBack(2); // pops the last N values. The same caveats apply 441 assert(list == [1]); 442 list.pop(); // pop is an alias to popBack 443 assert(list == null); 444 list.pop(42); // popping more items than there are is safe 445 list.clear(); // pops all elements from List 446 assert(list.empty); 447 448 list.push(iota(16)); // ranges can be pushed at once 449 assert(list.full); 450 auto result = list.push(1, 2); // Trying to push more items than capacity permits is an error, but no exception is thrown... 451 assert(result == 2); // ...rather pushBack returns the number of items that were not inserted 452 list.clear(); 453 result = list.push(1, 1, 2, 3, 5); 454 assert(result == 0); // if all items were inserted, pushBack returns 0 455 result = list.pushBack(repeat(42)); // if range has no known length and not all elements were inserted... 456 assert(result < 0); // ...pushBack returns a negative value 457 458 // Lists can also be backed by a slice 459 import core.stdc.stdlib : malloc, free; 460 alias IntList = List!int; 461 462 enum bufferSize = 8 * int.sizeof; 463 void* buffer = malloc(bufferSize); 464 465 // Construction using void[] 466 auto sliceList = IntList(buffer[0 .. bufferSize]); 467 assert(sliceList.capacity == 8); 468 469 // Construction using element type slice 470 sliceList = IntList(cast(int[]) buffer[0 .. bufferSize]); 471 assert(sliceList.capacity == 8); 472 473 // Construction using void pointer and explicit buffer size (be careful!) 474 sliceList = IntList(buffer, bufferSize); 475 assert(sliceList.capacity == 8); 476 477 // Construction using element type pointer and explicit capacity (be careful!) 478 sliceList = IntList(cast(int*) buffer, 8); 479 assert(sliceList.capacity == 8); 480 481 // Lists backed by slices do not manage their own memory (TODO: memory mamaged (noGC, but destructor/auto resize) List type) 482 free(buffer); 483 }