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.

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.

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 writeThis(ch: fileWriter) 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.

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