stdx.collections.slist

struct SList(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 singly 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 sl = SList!int(theAllocator);
auto csl = const SList!int(processAllocator);
auto isl = immutable SList!int(processAllocator);

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

Constructs a qualified singly 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 sl = SList!int(1, 2, 3);
    assert(equal(sl, [1, 2, 3]));
}
// Create a list from an array of ints
{
    auto sl = SList!int([1, 2, 3]);
    assert(equal(sl, [1, 2, 3]));
}
// Create a list from a list from an input range
{
    auto sl = SList!int(1, 2, 3);
    auto sl2 = SList!int(sl);
    assert(equal(sl2, [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 singly 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 singly 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 singly 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 sl = SList!int(24, 42);
assert(sl.isUnique);
{
    auto sl2 = sl;
    assert(!sl.isUnique);
    sl2.front = 0;
    assert(sl.front == 0);
} // sl2 goes out of scope
assert(sl.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:

SList!int sl;
assert(sl.empty);
size_t pos = 0;
sl.insert(pos, 1);
assert(!sl.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 sl = SList!int(1, 2, 3);
assert(sl.front == 1);
sl.front = 0;
assert(sl.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 there are no more references to the current element (which is being consumed), then the current element will be destroyed; this will call T's dtor, if one is defined, and will collect it's resources.

Complexity Ο(1).

Examples:

auto a = [1, 2, 3];
auto sl = SList!int(a);
size_t i = 0;
while (!sl.empty)
{
    assert(sl.front == a[i++]);
    sl.popFront;
}
assert(sl.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 isl = immutable SList!int([1, 2, 3]);
assert(isl.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 isl = immutable SList!int([1, 2, 3]);

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

assert(isl.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 sl = SList!int(a);
size_t i = 0;

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

SList!T dup(this Q)();

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 stuff = [1, 2, 3];
auto sl = immutable SList!int(stuff);
auto slDup = sl.dup;
assert(equal(slDup, stuff));
slDup.front = 0;
assert(slDup.front == 0);
assert(sl.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 integer
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 s = SList!int(4, 5);
SList!int sl;
assert(sl.empty);

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

// insert from an input range
pos += sl.insert(pos, s);
assert(equal(sl, [1, 2, 3, 4, 5]));
s.front = 0;
assert(equal(sl, [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 s = SList!int(4, 5);
SList!int sl;
assert(sl.empty);

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

// insert from an input range
sl.insertBack(s);
assert(equal(sl, [1, 2, 3, 4, 5]));
s.front = 0;
assert(equal(sl, [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 singly 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 sl = SList!int(1);
auto sl2 = sl ~ 2;

assert(equal(sl2, [1, 2]));
sl.front = 0;
assert(equal(sl2, [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 singly linked list

Returns:

a reference to this list

Complexity Ο(n).

Examples:

import std.algorithm.comparison : equal;

auto sl = SList!int(1);
auto sl2 = SList!int(1, 2);

sl = sl2; // this will free the old sl
assert(equal(sl, [1, 2]));
sl.front = 0;
assert(equal(sl2, [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 singly 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 s = SList!int(4, 5);
SList!int sl;
assert(sl.empty);

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

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

void remove(size_t idx = 0);

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

Parameters:

size_t idx

a positive integer

Examples:

import std.algorithm.comparison : equal;

auto sl = SList!int(1, 2, 3);
auto sl2 = sl;
auto pos = 1;

assert(equal(sl, [1, 2, 3]));
sl.remove(pos);
assert(equal(sl, [1, 3]));
assert(equal(sl2, [1, 3]));