UnrolledLinkedList¶

Usage

use UnrolledLinkedList;

or

import UnrolledLinkedList;

This module contains the implementation of the ‘unrolledLinkedList’ type.

An unrolled linked list is a linked list of small arrays, all of the same size where each is so small that the insertion or deletion is fast and quick, but large enough to fill the cache line. The list tends to keep each node half full.

Given a list with size N and nodeCapacity M, indexing is O(N/M). And insertion or deletion at a given place is O(N/M + M), which contains a indexing operation. Appending operation, which doesn’t need to index, is O(M).

record unrolledLinkedList : writeSerializable¶

type eltType¶: The type of the elements contained in this unrolledLinkedList.

param parSafe = false¶: If true, this unrolledLinkedList will perform parallel safe operations.

var nodeCapacity : int = 32¶: The capacity of one linked node in the unrolledLinkedList

proc init(type eltType, param parSafe = false, nodeCapacity: int = 32)¶

Initializes an empty unrolledLinkedList.

Arguments:

eltType – The type of the elements of this unrolledLinkedList.
parSafe : param bool – If true, this unrolledLinkedList will use parallel safe operations.
nodeCapacity : int – The capacity of one linked node of this unrolledLinkedList.

proc init(other: list(?t), param parSafe = false, nodeCapacity: int = 32)

Initializes an unrolledLinkedList containing elements that are copy initialized from the elements contained in a list.

Used in new expressions.

Arguments:

other – The list to initialize from.
parSafe : param bool – If true, this unrolledLinkedList will use parallel safe operations.
nodeCapacity : int – The capacity of one linked node of this unrolledLinkedList.

proc init(other: [?d] ?t, param parSafe = false, nodeCapacity: int = 32)

Initializes an unrolledLinkedList containing elements that are copy initialized from the elements contained in an array.

Used in new expressions.

Arguments:

other – The array to initialize from.
parSafe : param bool – If true, this unrolledLinkedList will use parallel safe operations.
nodeCapacity : int – The capacity of one linked node of this unrolledLinkedList.

proc init=(other: unrolledLinkedList(this.type.eltType, ?p))¶

Initializes an unrolledLinkedList containing elements that are copy initialized from the elements contained in another unrolledLinkedList.

Arguments:: other – The list to initialize from.

proc ref append(x: eltType)¶

Add an element to the end of this unrolledLinkedList.

Arguments:: x : eltType – An element to append.
Returns:: List index where element was inserted.
Return type:: int

proc ref append(other: list(eltType, ?p))

Append a copy of each element contained in a list to the end of this unrolledLinkedList.

Arguments:: other : list(eltType) – A list containing elements of the same type as those contained in this list.
Returns:: List indices where elements were inserted.
Return type:: range

proc ref append(other: unrolledLinkedList(eltType, ?p))

Append a copy of each element contained in another unrolledLinkedList to the end of this unrolledLinkedList.

Arguments:: other : unrolledLinkedList(eltType) – an unrolledLinkedList containing elements of the same type as those contained in this unrolledLinkedList.
Returns:: List indices where elements were inserted.
Return type:: range

proc ref append(other: [?d] eltType)

Append a copy of each element contained in an array to the end of this list.

Arguments:: other : [?d] eltType – An array containing elements of the same type as those contained in this unrolledLinkedList.
Returns:: List indices where elements were inserted.
Return type:: range

proc ref append(other: range(eltType, ?b, ?d))

Append a copy of each element yielded by a range to the end of this unrolledLinkedList.

Note

Attempting to initialize an unrolledLinkedList from an unbounded range will trigger a compiler error.

Arguments:: other : range(eltType) – The range to initialize from.
Returns:: List indices where elements were inserted.
Return type:: range

proc contains(x: eltType) : bool¶

Returns true if this unrolledLinkedList contains an element equal to the value of x, and false otherwise.

Arguments:: x : eltType – An element to search for.
Returns:: true if this unrolledLinkedList contains x.
Return type:: bool

proc ref first() ref¶

Returns a reference to the first item in this unrolledLinkedList.

Warning

Calling this method on an empty unrolledLinkedList will cause the currently running program to halt. If the –fast flag is used, no safety checks will be performed.

Returns:: A reference to the first item in this unrolledLinkedList.
Return type:: ref eltType

proc ref last() ref¶

Returns a reference to the last item in this unrolledLinkedList.

Warning

Calling this method on an empty unrolledLinkedList will cause the currently running program to halt. If the –fast flag is used, no safety checks will be performed.

Returns:: A reference to the last item in this unrolledLinkedList.
Return type:: ref eltType

proc ref insert(idx: int, x: eltType) : bool¶

Insert an element at a given position in this unrolledLinkedList, shifting all elements currently at and following that index one to the right. The call a.insert(0, x) inserts an element at the front of the unrolledLinkedList a, and a.insert((a.size), x) is equivalent to a.append(x).

If the insertion is successful, this method returns true. If the given index is out of bounds, this method does nothing and returns false.

Warning

Inserting an element into this unrolledLinkedList may invalidate existing references to the elements contained in this unrolledLinkedList.

Arguments:

idx : int – The index into this unrolledLinkedList at which to insert.
x : eltType – The element to insert.

Returns:

true if x was inserted, false otherwise.

Return type:

bool

proc ref insert(idx: int, arr: [?d] eltType) : bool

Insert elements of an array arr into this unrolledLinkedList at index idx, shifting all elements at and following the index arr.size positions to the right.

If the insertion is successful, this method returns true. If the given index is out of bounds, this method does nothing and returns false.

Warning

Inserting elements into this unrolledLinkedList may invalidate existing references to the elements contained in this unrolledLinkedList.

Arguments:

idx : int – The index into this unrolledLinkedList at which to insert.
arr – An array of elements to insert.

Returns:

true if arr was inserted, false otherwise.

Return type:

bool

proc ref insert(idx: int, lst: list(eltType)) : bool

Insert elements of a list lst into this unrolledLinkedList at index idx, shifting all elements at and following the index lst.size positions to the right.

If the insertion is successful, this method returns true. If the given index is out of bounds, this method does nothing and returns false.

Warning

Inserting elements into this unrolledLinkedList may invalidate existing references to the elements contained in this unrolledLinkedList.

Arguments:

idx : int – The index into this unrolledLinkedList at which to insert.
lst : list(eltType) – A list of elements to insert.

Returns:

true if lst was inserted, false otherwise.

Return type:

bool

proc ref remove(x: eltType, count: int = 1) : int¶

Remove the first count elements from this unrolledLinkedList with values equal to x, shifting all elements following the removed item left.

If the count of elements to remove is less than or equal to zero, then all elements from this unrolledLinkedList equal to the value of x will be removed.

Warning

Removing elements from this unrolledLinkedList may invalidate existing references to the elements contained in this unrolledLinkedList.

Arguments:

x : eltType – The value of the element to remove.
count : int – The number of elements to remove.

Returns:

The number of elements removed.

Return type:

int

proc ref pop() : eltType¶

Remove the element at the end of this unrolledLinkedList and return it.

Warning

Popping an element from this unrolledLinkedList will invalidate any reference to the element taken while it was contained in this unrolledLinkedList.

Warning

Calling this method on an empty unrolledLinkedList will cause the currently running program to halt. If the –fast flag is used, no safety checks will be performed.

Returns:: The element popped.
Return type:: eltType

proc ref pop(idx: int) : eltType

Remove the element at the index idx from this unrolledLinkedList and return it.

Warning

Popping an element from this unrolledLinkedList will invalidate any reference to the element taken while it was contained in this unrolledLinkedList.

Warning

Calling this method on an empty unrolledLinkedList or with values of idx that are out of bounds will cause the currently running program to halt. If the –fast flag is used, no safety checks will be performed.

Arguments:: idx : int – The index of the element to remove.
Returns:: The element popped.
Return type:: eltType

proc ref clear()¶: Clear the contents of this unrolledLinkedList.

Warning

Clearing the contents of this unrolledLinkedList will invalidate all existing references to the elements contained in this unrolledLinkedList.

proc indexOf(x: eltType, start: int = 0, end: int = -1) : int¶

Return a zero-based index into this unrolledLinkedList of the first item whose value is equal to x. If no such element can be found this method returns the value -1.

Warning

Calling this method on an empty unrolledLinkedList or with values of start or end that are out of bounds will cause the currently running program to halt. If the –fast flag is used, no safety checks will be performed.

Arguments:

x : eltType – An element to search for.
start : int – The start index to start searching from.
end : int – The end index to stop searching at. A value less than 0 will search the entire unrolledLinkedList.

Returns:

The index of the element to search for, or -1 on error.

Return type:

int

proc count(x: eltType) : int¶

Return the number of times a given element is found in this unrolledLinkedList.

Arguments:: x : eltType – An element to count.
Returns:: The number of times a given element is found in this unrolledLinkedList.
Return type:: int

proc ref this(i: int) ref¶

Index this unrolledLinkedList via subscript. Returns a reference to the element at a given index in this unrolledLinkedList.

Arguments:: i – The index of the element to access.

Warning

Use of the this method with an out of bounds index (while bounds checking is on) will cause the currently running program to halt.

Returns:: An element from this unrolledLinkedList.

iter these() ref¶

Iterate over the elements of this unrolledLinkedList.

Yields:: A reference to one of the elements contained in this unrolledLinkedList.

proc serialize(writer, ref serializer) throws¶: Write the contents of this unrolledLinkedList to a channel.

proc isEmpty() : bool¶

Returns true if this unrolledLinkedList contains zero elements.

Returns:: true if this unrolledLinkedList is empty.
Return type:: bool

proc size¶: The current number of elements contained in this unrolledLinkedList. Returns in O(1).

proc indices¶

Returns the unrolledLinkedList’s legal indices as the range 0..<this.size.

Returns:: 0..<this.size
Return type:: range

proc toArray() : [] eltType¶

Returns a new DefaultRectangular array containing a copy of each of the elements contained in this unrolledLinkedList.

Returns:: A new DefaultRectangular array.

operator unrolledLinkedList.=(ref lhs: unrolledLinkedList(?t, ?), rhs: unrolledLinkedList(t, ?))¶: Clear the contents of this unrolledLinkedList, then extend this now-empty unrolledLinkedList with the elements contained in another unrolledLinkedList.

Warning

This will invalidate any references to elements previously contained in lhs.

operator unrolledLinkedList.==(a: unrolledLinkedList(?t, ?), b: unrolledLinkedList(t, ?)) : bool¶

Returns true if the contents of two unrolledLinkedLists are the same.

Returns:: true if the contents of two unrolledLinkedLists are equal.
Return type:: bool

operator unrolledLinkedList.!=(a: unrolledLinkedList(?t, ?), b: unrolledLinkedList(t, ?)) : bool¶

Return true if the contents of two unrolledLinkedLists are not the same.

Returns:: true if the contents of two unrolledLinkedLists are not equal.
Return type:: bool