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¶

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.

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.

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.

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.

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 extend(other: list(eltType, ?p))

Extend this unrolledLinkedList by appending a copy of each element contained in a list.

Arguments: other : list(eltType) – A list containing elements of the same type as those contained in this list.

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

Extend this unrolledLinkedList by appending a copy of each element contained in an unrolledLinkedList.

Arguments: other : unrolledLinkedList(eltType) – an unrolledLinkedList containing elements of the same type as those contained in this unrolledLinkedList.

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

Extend this unrolledLinkedList by appending a copy of each element contained in an array.

Arguments: other : [?d] eltType – An array containing elements of the same type as those contained in this unrolledLinkedList.

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

Extends this unrolledLinkedList by appending a copy of each element yielded by a range.

Note

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

Arguments: other : range(eltType) – The range to initialize from.

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 writeThis(ch: channel) throws¶

Write the contents of this unrolledLinkedList to a channel.

Arguments: ch – A channel to write to.

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.

proc type 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.

proc type 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

proc type 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