PointerList | /src/utils/pointerList.ts | velo@0.1.5

class PointerList

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

Implements a fixed size doubly linked list. This implementation relies on a custom pointer system utilizing TypedArrays.

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

To simplify the internals the list is implemented as a ring with a root indicating the first element. This allows for easy access to the front and back elements of the list.

The list will allow pushing any values if it is not full. To not destroy the index based structure use the newPointer() method to create a safe index.

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

Constructors

new

PointerList(capacity: number)

Creates an instance of PointerList

Properties

private

readonly

_capacity: number

The capacity of the list

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

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

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 wrapper to move a pointer to the back

moveToFront(pointer: number)

Convenience wrapper to move a pointer to the front

newPointer(): number | undefined

Method to create a save pointer to be inserted into the list.

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