PointerList | /src/utils/pointer_list.ts | velo@1.0.0

class PointerList

import { PointerList } from "https://deno.land/x/velo@1.0.0/src/utils/pointer_list.ts";

Implements a fixed size double-linked list of reference pointers. This implementation relies on a custom pointer system [1]. Utilizing TypedArrays for better engine optimization.

The list internally relies on an incrementing index. To not destroy the index based structure use the newPointer() method to create a index that can be safely inserted.

const list = new PointerList(10);
const p = list.newPointer();
list.pushFront(p);

[1] https://yomguithereal.github.io/posts/lru-cache#a-custom-pointer-system

Constructors

new

PointerList(capacity: number)

Creates an instance of PointerList

Properties

private

_root: number

Index of the root

private

_size: number

The size

private

next: TypedArray

private

nextIndex: Array<number>

Keeps track of the freed indices

private

prev: TypedArray

readonly

back

The last element of the list

readonly

capacity: number

The capacity of the list

readonly

front

The first element of the list

readonly

size

The size of the list

Methods

clear(): void

Clears the list

insert(pointer: number, after: number): boolean

Inserts a pointer after a given reference pointer into the list if it is not full.

isFull(): boolean

move(pointer: number, after: number)

Moves a given pointer to the position after a reference pointer in the list

moveToBack(pointer: number)

Convenience method to move a pointer to the back

moveToFront(pointer: number)

Convenience method to move a pointer to the front

newPointer(): number

Method to create a save pointer to be inserted into the list. This new pointer is not stored in the list. Use insert to do that.

nextOf(pointer: number): number | undefined

Returns the the next element of a given reference pointer. If the next element would be root undefined is returned.

prevOf(pointer: number): number | undefined

Returns the the previous element of a given reference pointer. If the previous element would be the element before root undefined is returned.

pushBack(pointer: number)

Convinience wrapper for inserting a pointer as back element

pushFront(pointer: number)

Convinience wrapper for inserting a pointer as front element

remove(pointer: number): number

Removes a pointer from the list

removeBack(): number

Convenience wrapper to remove the back pointer

removeFront(): number

Convenience wrapper to remove the front pointer