Struct CompressedList

Unrolled list

struct CompressedList(T, Allocator, bool GCRangesAllowed = true) ;

Methods

NameDescription
back List back item.
clear remove anything from list
empty Is list empty?
front List front item
insertBack Insert item back.
insertFront Insert item at front.
length Items in the list.
popBack Pop back item from list.
popFront Pop front item
range Iterator over items.
remove remove node (by 'Pointer')

Inner structs

NameDescription
Page unrolled list with support only for: 1. insert/delete front 2. insert/delete back 3. keep unstable "pointer" to arbitrary element 4. remove element by pointer

Example

import std.experimental.logger;
import std.algorithm;
import std.range;

globalLogLevel = LogLevel.info;
CompressedList!int list;
foreach(i;0..66)
{
    list.insertFront(i);
    assert(list.front == i);
}
assert(list.length == 66);
assert(list.back == 0);
list.popFront();
assert(list.length == 65);
assert(list.front == 64);
list.popFront();
assert(list.length == 64);
assert(list.front == 63);
while( !list.empty )
{
    list.popFront();
}
foreach(i;1..19)
{
    list.insertFront(i);
    assert(list.front == i);
}
foreach(i;1..19)
{
    assert(list.back == i);
    assert(list.length == 19-i);
    list.popBack();
}
assert(list.empty);
auto p99 = list.insertBack(99);
assert(list.front == 99);
assert(list.back == 99);
auto p100 = list.insertBack(100);
assert(list.front == 99);
assert(list.back == 100);
auto p98 = list.insertFront(98);
auto p101 = list.insertBack(101);
() @trusted // * and remove for poiners is unsafe
{
    assert(*p98 == 98);
    assert(list.length == 4);
    list.remove(p98);
    assert(list.length == 3);
    assert(list.front == 99);
    list.remove(p100);
    assert(list.length == 2);
    assert(list.front == 99);
    assert(list.back == 101);
    list.remove(p99);
    assert(list.length == 1);
    list.clear();

    foreach(i;0..1000)
    {
        list.insertBack(i);
    }
    assert(equal(list.range(), iota(0,1000)));
    list.clear();

    iota(0, 1000).
        map!(i => list.insertBack(i)).
        array.
        each!(p => list.remove(p));
    assert(list.empty);
    iota(0, 1000).map!(i => list.insertBack(i));
    auto r = list.range();
    while(!r.empty)
    {
        int v = r.front;
        r.popFront();
    }
    assert(list.empty);
}();

() @nogc
{
    struct S {}
    CompressedList!(immutable S) islist;
    immutable S s = S();
    islist.insertFront(s);
}();
class C
{
    int c;
    this(int v) {
        c = v;
    }
}
CompressedList!C clist;
foreach(i;0..5000)
{
    clist.insertBack(new C(i));
}
foreach(i;0..4500)
{
    clist.popBack();
}
assert(clist.length == 500);
clist.clear();