stdx.collections.dlist

struct DList(T);

this(A, this Q)(A allocator)
if (!is(Q == shared) && (is(A == RCISharedAllocator) || !is(Q == immutable)) && (is(A == RCIAllocator) || is(A == RCISharedAllocator)));

Constructs a qualified doubly linked list that will use the provided allocator object. For immutable objects, a RCISharedAllocator must be supplied.

Parameters:

A allocator

a allocator.html#.RCIAllocator">std.experimental.allocator.RCIAllocator or allocator.html#.RCISharedAllocator">std.experimental.allocator.RCISharedAllocator allocator object

Complexity Ο(1)

Examples:

auto dl = DList!int(theAllocator);
auto cdl = const DList!int(processAllocator);
auto idl = immutable DList!int(processAllocator);

this(U, this Q)(U[] values...)
if (isImplicitlyConvertible!(U, T));

Constructs a qualified doubly linked list out of a number of items. Because no allocator was provided, the list will use the GCAllocator.std.experimental.allocator.

Parameters:

U[] values

a variable number of items, either in the form of a list or as a built-in array

Complexity Ο(m), where m is the number of items.

Examples:

import std.algorithm.comparison : equal;

// Create a list from a list of ints
{
    auto dl = DList!int(1, 2, 3);
    assert(equal(dl, [1, 2, 3]));
}
// Create a list from an array of ints
{
    auto dl = DList!int([1, 2, 3]);
    assert(equal(dl, [1, 2, 3]));
}
// Create a list from a list from an input range
{
    auto dl = DList!int(1, 2, 3);
    auto dl2 = DList!int(dl);
    assert(equal(dl2, [1, 2, 3]));
}

this(A, U, this Q)(A allocator, U[] values...)
if (!is(Q == shared) && (is(A == RCISharedAllocator) || !is(Q == immutable)) && (is(A == RCIAllocator) || is(A == RCISharedAllocator)) && isImplicitlyConvertible!(U, T));

Constructs a qualified doubly linked list out of a number of items that will use the provided allocator object. For immutable objects, a RCISharedAllocator must be supplied.

Parameters:

A allocator	a allocator.html#.RCIAllocator">std.experimental.allocator.RCIAllocator or allocator.html#.RCISharedAllocator">std.experimental.allocator.RCISharedAllocator allocator object
U[] values	a variable number of items, either in the form of a list or as a built-in array

Complexity Ο(m), where m is the number of items.

this(Stuff, this Q)(Stuff stuff)
if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T) && !is(Stuff == T[]));

Constructs a qualified doubly linked list out of an input range. Because no allocator was provided, the list will use the GCAllocator.std.experimental.allocator.

Parameters:

Stuff stuff

an input range of elements that are implitictly convertible to T

Complexity Ο(m), where m is the number of elements in the range.

this(A, Stuff, this Q)(A allocator, Stuff stuff)
if (!is(Q == shared) && (is(A == RCISharedAllocator) || !is(Q == immutable)) && (is(A == RCIAllocator) || is(A == RCISharedAllocator)) && isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T) && !is(Stuff == T[]));

Constructs a qualified doubly linked list out of an input range that will use the provided allocator object. For immutable objects, a RCISharedAllocator must be supplied.

Parameters:

A allocator	a allocator.html#.RCIAllocator">std.experimental.allocator.RCIAllocator or allocator.html#.RCISharedAllocator">std.experimental.allocator.RCISharedAllocator allocator object
Stuff stuff	an input range of elements that are implitictly convertible to T

Complexity Ο(m), where m is the number of elements in the range.

const bool isUnique();

Check whether there are no more references to this list instance.

Returns:

true if this is the only reference to this list instance; false otherwise.

Complexity Ο(n).

Examples:

auto dl = DList!int(24, 42);
assert(dl.isUnique);
{
    auto dl2 = dl;
    assert(!dl.isUnique);
    dl2.front = 0;
    assert(dl.front == 0);
} // dl2 goes out of scope
assert(dl.isUnique);

const pure nothrow @nogc @safe bool empty();

Check if the list is empty.

Returns:

true if there are no nodes in the list; false otherwise.

Complexity Ο(1).

Examples:

DList!int dl;
assert(dl.empty);
size_t pos = 0;
dl.insert(pos, 1);
assert(!dl.empty);

ref auto front(this _)();

Provide access to the first element in the list. The user must check that the list isn't empty, prior to calling this function.

Returns:

a reference to the first element.

Complexity Ο(1).

Examples:

auto dl = DList!int(1, 2, 3);
assert(dl.front == 1);
dl.front = 0;
assert(dl.front == 0);

void popFront();

Advance to the next element in the list. The user must check that the list isn't empty, prior to calling this function.

If this was the last element in the list and there are no more references to the current list, then the list and all it's elements will be destroyed; this will call T's dtor, if one is defined, and will collect the resources.

Complexity usually Ο(1), worst case Ο(n).

Examples:

auto a = [1, 2, 3];
auto dl = DList!int(a);
size_t i = 0;
while (!dl.empty)
{
    assert(dl.front == a[i++]);
    dl.popFront;
}
assert(dl.empty);

void popPrev();

Go to the previous element in the list. The user must check that the list isn't empty, prior to calling this function.

If this was the first element in the list and there are no more references to the current list, then the list and all it's elements will be destroyed; this will call T's dtor, if one is defined, and will collect the resources.

Complexity usually Ο(1), worst case Ο(n).

Examples:

auto dl = DList!int([1, 2, 3]);
dl.popFront;
assert(dl.front == 2);
dl.popPrev;
assert(dl.front == 1);
dl.popPrev;
assert(dl.empty);

Qualified tail(this Qualified)();

Advance to the next element in the list. The user must check that the list isn't empty, prior to calling this function.

This must be used in order to iterate through a const or immutable list. For a mutable list this is equivalent to calling popFront.

Returns:

a list that starts with the next element in the original list

Complexity Ο(1).

Examples:

auto idl = immutable DList!int([1, 2, 3]);
assert(idl.tail.front == 2);

template each(alias fun)

Eagerly iterate over each element in the list and call fun over each element. This should be used to iterate through const and immutable lists.

Normally, the entire list is iterated. If partial iteration (early stopping) is desired, fun needs to return a value of type std.typecons.Flag!"each" (Yes.each to continue iteration, or No.each to stop).

Parameters:

fun	unary function to apply on each element of the list.

Returns:

Yes.each if it has iterated through all the elements in the list, or No.each otherwise.

Complexity Ο(n).

Examples:

import std.typecons : Flag, Yes, No;

auto idl = immutable DList!int([1, 2, 3]);

static bool foo(int x) { return x > 0; }

assert(idl.each!foo == Yes.each);

ref Qualified save(this Qualified)();

Perform a shallow copy of the list.

Returns:

a new reference to the current list.

Complexity Ο(1).

Examples:

auto a = [1, 2, 3];
auto dl = DList!int(a);
size_t i = 0;

auto tmp = dl.save;
while (!tmp.empty)
{
    assert(tmp.front == a[i++]);
    tmp.popFront;
}
assert(tmp.empty);
assert(!dl.empty);

typeof(this) dup();

Perform a copy of the list. This will create a new list that will copy the elements of the current list. This will NOT call dup on the elements of the list, regardless if T defines it or not.

Returns:

a new list.

Complexity Ο(n).

Examples:

import std.algorithm.comparison : equal;

auto dl = DList!int(1, 2, 3);
auto dlDup = dl.dup;
assert(equal(dl, dlDup));
dlDup.front = 0;
assert(!equal(dl, dlDup));
assert(dlDup.front == 0);
assert(dl.front == 1);

size_t insert(Stuff)(size_t pos, Stuff stuff)
if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T));

size_t insert(Stuff)(size_t pos, Stuff[] stuff...)
if (isImplicitlyConvertible!(Stuff, T));

Inserts the elements of an input range, or a variable number of items, at the given pos.

If no allocator was provided when the list was created, the GCAllocator.std.experimental.allocator will be used.

Parameters:

size_t pos	a positive integral
Stuff stuff	an input range of elements that are implitictly convertible to T; a variable number of items either in the form of a list or as a built-in array

Returns:

the number of elements inserted

Complexity Ο(pos + m), where m is the number of elements in the range.

Examples:

import std.algorithm.comparison : equal;

auto d = DList!int(4, 5);
DList!int dl;
assert(dl.empty);

size_t pos = 0;
pos += dl.insert(pos, 1);
pos += dl.insert(pos, [2, 3]);
assert(equal(dl, [1, 2, 3]));

// insert from an input range
pos += dl.insert(pos, d);
assert(equal(dl, [1, 2, 3, 4, 5]));
d.front = 0;
assert(equal(dl, [1, 2, 3, 4, 5]));

size_t insertBack(Stuff)(Stuff stuff)
if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T));

size_t insertBack(Stuff)(Stuff[] stuff...)
if (isImplicitlyConvertible!(Stuff, T));

Inserts the elements of an input range, or a variable number of items, at the end of the list.

If no allocator was provided when the list was created, the GCAllocator.std.experimental.allocator will be used.

Parameters:

Stuff stuff

an input range of elements that are implitictly convertible to T; a variable number of items either in the form of a list or as a built-in array

Returns:

the number of elements inserted

Complexity Ο(pos + m), where m is the number of elements in the range.

Examples:

import std.algorithm.comparison : equal;

auto d = DList!int(4, 5);
DList!int dl;
assert(dl.empty);

dl.insertBack(1);
dl.insertBack([2, 3]);
assert(equal(dl, [1, 2, 3]));

// insert from an input range
dl.insertBack(d);
assert(equal(dl, [1, 2, 3, 4, 5]));
d.front = 0;
assert(equal(dl, [1, 2, 3, 4, 5]));

ref auto opBinary(string op, U)(auto ref U rhs)
if (op == "~" && (is(U == typeof(this)) || is(U : T) || isInputRange!U && isImplicitlyConvertible!(ElementType!U, T)));

Create a new list that results from the concatenation of this list with rhs.

Parameters:

U rhs

can be an element that is implicitly convertible to T, an input range of such elements, or another doubly linked list

Returns:

the newly created list

Complexity Ο(n + m), where m is the number of elements in rhs.

Examples:

import std.algorithm.comparison : equal;

auto dl = DList!int(1);
auto dl2 = dl ~ 2;

assert(equal(dl2, [1, 2]));
dl.front = 0;
assert(equal(dl2, [1, 2]));

ref auto opAssign()(auto ref typeof(this) rhs);

Assign rhs to this list. The current list will now become another reference to rhs, unless rhs is null, in which case the current list will become empty. If rhs refers to the current list nothing will happen.

All the previous list elements that have no more references to them will be destroyed; this leads to a Ο(n) complexity.

Parameters:

typeof(this) rhs

a reference to a doubly linked list

Returns:

a reference to this list

Complexity Ο(n).

Examples:

import std.algorithm.comparison : equal;

auto dl = DList!int(1);
auto dl2 = DList!int(1, 2);

dl = dl2; // this will free the old dl
assert(equal(dl, [1, 2]));
dl.front = 0;
assert(equal(dl2, [0, 2]));

ref auto opOpAssign(string op, U)(auto ref U rhs)
if (op == "~" && (is(U == typeof(this)) || is(U : T) || isInputRange!U && isImplicitlyConvertible!(ElementType!U, T)));

Append the elements of rhs at the end of the list.

If no allocator was provided when the list was created, the GCAllocator.std.experimental.allocator will be used.

Parameters:

U rhs

can be an element that is implicitly convertible to T, an input range of such elements, or another doubly linked list

Returns:

a reference to this list

Complexity Ο(n + m), where m is the number of elements in rhs.

Examples:

import std.algorithm.comparison : equal;

auto d = DList!int(4, 5);
DList!int dl;
assert(dl.empty);

dl ~= 1;
dl ~= [2, 3];
assert(equal(dl, [1, 2, 3]));

// append an input range
dl ~= d;
assert(equal(dl, [1, 2, 3, 4, 5]));
d.front = 0;
assert(equal(dl, [1, 2, 3, 4, 5]));

void remove();

Remove the current element from the list. If there are no more references to the current element, then it will be destroyed.

Examples:

import std.algorithm.comparison : equal;

auto dl = DList!int(1, 2, 3);
auto dl2 = dl;

assert(equal(dl, [1, 2, 3]));
dl.popFront;
dl.remove();
assert(equal(dl, [3]));
assert(equal(dl2, [1, 3]));
dl.popPrev;
assert(equal(dl, [1, 3]));