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