.. default-domain:: chpl .. module:: UnrolledLinkedList :synopsis: This module contains the implementation of the 'unrolledLinkedList' type. UnrolledLinkedList ================== **Usage** .. code-block:: chapel use UnrolledLinkedList; or .. code-block:: chapel 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 .. attribute:: type eltType The type of the elements contained in this unrolledLinkedList. .. attribute:: param parSafe = false If `true`, this unrolledLinkedList will perform parallel safe operations. .. attribute:: var nodeCapacity: int = 32 The capacity of one linked node in the unrolledLinkedList .. method:: proc init(type eltType, param parSafe = false, nodeCapacity: int = 32) Initializes an empty unrolledLinkedList. :arg eltType: The type of the elements of this unrolledLinkedList. :arg parSafe: If `true`, this unrolledLinkedList will use parallel safe operations. :type parSafe: `param bool` :arg nodeCapacity: The capacity of one linked node of this unrolledLinkedList. :type nodeCapacity: `int` .. method:: 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. :arg other: The list to initialize from. :arg parSafe: If `true`, this unrolledLinkedList will use parallel safe operations. :type parSafe: `param bool` :arg nodeCapacity: The capacity of one linked node of this unrolledLinkedList. :type nodeCapacity: `int` .. method:: 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. :arg other: The array to initialize from. :arg parSafe: If `true`, this unrolledLinkedList will use parallel safe operations. :type parSafe: `param bool` :arg nodeCapacity: The capacity of one linked node of this unrolledLinkedList. :type nodeCapacity: `int` .. method:: proc init=(other: unrolledLinkedList(this.type.eltType, ?p)) Initializes an unrolledLinkedList containing elements that are copy initialized from the elements contained in another unrolledLinkedList. :arg other: The list to initialize from. .. method:: proc ref append(x: eltType) Add an element to the end of this unrolledLinkedList. :arg x: An element to append. :type x: `eltType` :return: List index where element was inserted. :rtype: `int` .. method:: proc ref append(other: list(eltType, ?p)) Append a copy of each element contained in a list to the end of this unrolledLinkedList. :arg other: A list containing elements of the same type as those contained in this list. :type other: `list(eltType)` :return: List indices where elements were inserted. :rtype: `range` .. method:: proc ref append(other: unrolledLinkedList(eltType, ?p)) Append a copy of each element contained in another unrolledLinkedList to the end of this unrolledLinkedList. :arg other: an unrolledLinkedList containing elements of the same type as those contained in this unrolledLinkedList. :type other: `unrolledLinkedList(eltType)` :return: List indices where elements were inserted. :rtype: `range` .. method:: proc ref append(other: [?d] eltType) Append a copy of each element contained in an array to the end of this list. :arg other: An array containing elements of the same type as those contained in this unrolledLinkedList. :type other: `[?d] eltType` :return: List indices where elements were inserted. :rtype: `range` .. method:: 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. :arg other: The range to initialize from. :type other: `range(eltType)` :return: List indices where elements were inserted. :rtype: `range` .. method:: proc contains(x: eltType): bool Returns `true` if this unrolledLinkedList contains an element equal to the value of `x`, and `false` otherwise. :arg x: An element to search for. :type x: `eltType` :return: `true` if this unrolledLinkedList contains `x`. :rtype: `bool` .. method:: 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. :return: A reference to the first item in this unrolledLinkedList. :rtype: `ref eltType` .. method:: 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. :return: A reference to the last item in this unrolledLinkedList. :rtype: `ref eltType` .. method:: 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. :arg idx: The index into this unrolledLinkedList at which to insert. :type idx: `int` :arg x: The element to insert. :type x: `eltType` :return: `true` if `x` was inserted, `false` otherwise. :rtype: `bool` .. method:: 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. :arg idx: The index into this unrolledLinkedList at which to insert. :type idx: `int` :arg arr: An array of elements to insert. :type x: `[] eltType` :return: `true` if `arr` was inserted, `false` otherwise. :rtype: `bool` .. method:: 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. :arg idx: The index into this unrolledLinkedList at which to insert. :type idx: `int` :arg lst: A list of elements to insert. :type lst: `list(eltType)` :return: `true` if `lst` was inserted, `false` otherwise. :rtype: `bool` .. method:: 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. :arg x: The value of the element to remove. :type x: `eltType` :arg count: The number of elements to remove. :type count: `int` :return: The number of elements removed. :rtype: `int` .. method:: 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. :return: The element popped. :rtype: `eltType` .. method:: 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. :arg idx: The index of the element to remove. :type idx: `int` :return: The element popped. :rtype: `eltType` .. method:: 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. .. method:: 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. :arg x: An element to search for. :type x: `eltType` :arg start: The start index to start searching from. :type start: `int` :arg end: The end index to stop searching at. A value less than `0` will search the entire unrolledLinkedList. :type end: `int` :return: The index of the element to search for, or `-1` on error. :rtype: `int` .. method:: proc count(x: eltType): int Return the number of times a given element is found in this unrolledLinkedList. :arg x: An element to count. :type x: `eltType` :return: The number of times a given element is found in this unrolledLinkedList. :rtype: `int` .. method:: proc ref this(i: int) ref Index this unrolledLinkedList via subscript. Returns a reference to the element at a given index in this unrolledLinkedList. :arg 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. :return: An element from this unrolledLinkedList. .. itermethod:: iter these() ref Iterate over the elements of this unrolledLinkedList. :yields: A reference to one of the elements contained in this unrolledLinkedList. .. method:: proc serialize(writer, ref serializer) throws Write the contents of this unrolledLinkedList to a channel. .. method:: proc isEmpty(): bool Returns `true` if this unrolledLinkedList contains zero elements. :return: `true` if this unrolledLinkedList is empty. :rtype: `bool` .. method:: proc size The current number of elements contained in this unrolledLinkedList. Returns in O(1). .. method:: proc indices Returns the unrolledLinkedList's legal indices as the range ``0..