Circle DS

A suite of circular data structures, including deques, lists, maps, queues, sets and stacks. Use circular buffers with ease.

Features

Install

Using npm:

npm install circle-ds

Using yarn:

yarn install circle-ds

API

Common

The following is common across all collections. See the Collection interface for more details.

Constructor

• new (): Initialize an empty collection of infinite capacity.
• new (capacity: number): Initialize an empty collection with the given capacity.

Properties

• capacity: number: A positive integer that represents the maximum size of the collection. Can be updated to grow or shrink the collection. Can also be set to Infinity.

• get size(): number: The number of items in the collection.

• get [Symbol.toStringTag](): string: A string that represents the type of the object. See Symbol.toStringTag for more details.

Events

• BoundedEvent.Overflow: Triggered when existing elements are discarded from the collection. This happens when the collection's capacity is reduced below its size or when new values are added while at capacity.

Methods

• clear(): void: Remove all items from the collection.

• entries(): IterableIterator<K, V>: Returns an iterator of [key/index, value] pairs through the collection.

• forEach(callbackFn: (value: V, index: K, collection: Collection<K, V>) => void, thisArg?: unknown): void: Executes the provided callbackFn function once for each element.

• keys(): IterableIterator<K>: Returns an iterator for the keys / indices in the collection.

• values(): IterableIterator<V>: Returns an iterator for the values in the collection.

• [Symbol.iterator](): IterableIterator: Returns an iterator for the values or key-value pairs in the collection.

CircularDeque & CircularLinkedDeque

CircularDeque is a double-ended queue that combines the features of stacks and queues, allowing insertion and removal at both ends.

Constructor

• new <T>(items: Iterable<T>): Initialize a full deque with the given items.

Methods

• first(): T | undefined: Returns the first item without removing it, or undefined if the collection is empty. Alias for front().

• front(): T | undefined: Returns the item at the front without removing it, or undefined if the collection is empty. Alias for first().

• has(value: T): boolean: Checks if the collection contains a specific value.

• last(): T | undefined: Returns the last item without removing it, or undefined if the collection is empty. Alias for top().

• pop(): T | undefined: Removes and returns the last item, or undefined if the collection is empty.

• push(...items: T[]): number: Appends items to the collection and returns the new size. If at capacity, items at the front are overwritten and emitted via the BoundedEvent.Overflow event.

• shift(): T | undefined: Removes and returns the first item, or undefined if the collection is empty.

• top(): T | undefined: Returns the item at the top without removing it, or undefined if the collection is empty. Alias for last().

• unshift(...items: T[]): number: Prepends items to the collection and returns the new size. If capacity is surpassed, items at the end are overwritten and emitted via the BoundedEvent.Overflow event.

• [Symbol.iterator](): IterableIterator<T>: Returns an iterator for the values in the collection.

CircularLinkedList & CircularDoublyLinkedList

CircularLinkedList is a list of elements allowing for indexed access, modification, and iteration.

Constructor

• new <T>(items: Iterable<T>): Initialize a full list with the given items.

Methods

• at(index: number): V | undefined: Retrieves the element at the specified index in the list.

• delete(index: number): boolean: Deletes the element at the specified index.

• fill(value: V, start?: number, end?: number): this: Fills the list with the specified value from start index (inclusive) to end index (exclusive).

• has(value: T): boolean: Checks if the collection contains a specific value.

• pop(): T | undefined: Removes and returns the last item, or undefined if the collection is empty.

• push(...items: T[]): number: Appends items to the collection and returns the new size. If at capacity, items at the front are overwritten and emitted via the BoundedEvent.Overflow event.

• set(index: number, value: V): V | undefined: Replaces the element at the specified index with a new value. Returns the previous value if it succeeds, otherwise undefined.

• shift(): T | undefined: Removes and returns the first item, or undefined if the collection is empty.

• slice(start?: number, end?: number): CircularLinkedList<V>: Creates a shallow copy of the list from start index (inclusive) to end index (exclusive) into a new list. Does not modify the existing list.

• splice(start: number, deleteCount?: number, ...items: V[]): CircularLinkedList<V>: Changes the contents of the list by removing existing elements and/or adding new elements at a given index.

• [Symbol.iterator](): IterableIterator<T>: Returns an iterator for the values in the collection.

• unshift(...items: T[]): number: Prepends items to the collection and returns the new size. If capacity is surpassed, items at the end are overwritten and emitted via the BoundedEvent.Overflow event.

CircularMap

Constructor

• new <K, V>(items: Iterable<[K, V]>): Initialize a full map with the given items. Capacity will be the number of unique keys given.

Methods

• delete(key: K): boolean: Deletes the value from the collection. Returns true if the value exists and was removed successfully, or false otherwise.

• has(key: K): boolean: Checks if the collection contains a specific value.

• set(key: K, value: V): this: Sets the key to the given value in the collection. If at capacity, the oldest key-value pair is overwritten and emitted via the BoundedEvent.Overflow event. If an existing key is added again, then it will be treated as new.

• [Symbol.iterator](): IterableIterator<[K, V]>: Returns an iterator for the entries in the collection.

CircularQueue & CircularLinkedQueue

CircularQueue is a FIFO (First In, First Out) data structure with a fixed capacity.

Constructor

• new <T>(items: Iterable<T>): Initialize a full queue with the given items.

Methods

• first(): T | undefined: Returns the first item without removing it, or undefined if the collection is empty. Alias for front().

• front(): T | undefined: Returns the item at the front without removing it, or undefined if the collection is empty. Alias for first().

• has(value: T): boolean: Checks if the collection contains a specific value.

• push(...items: T[]): number: Appends items to the collection and returns the new size. If at capacity, items at the front are overwritten and emitted via the BoundedEvent.Overflow event.

• shift(): T | undefined: Removes and returns the first item, or undefined if the collection is empty.

• [Symbol.iterator](): IterableIterator<T>: Returns an iterator for the values in the collection.

CircularSet

Constructor

• new <T>(items: Iterable<T>): Initialize a full set with the given items. Capacity will be the number of unique items given.

Methods

• add(value: T): this: Adds the value to the collection. If at capacity, the oldest values are overwritten and emitted via the BoundedEvent.Overflow event. If an existing value is added again, then it will be treated as new.

• delete(value: T): boolean: Deletes the value from the collection. Returns true if the value exists and was removed successfully, or false otherwise.

• has(value: T): boolean: Checks if the collection contains a specific value.

• [Symbol.iterator](): IterableIterator<T>: Returns an iterator for the values in the collection.

CircularStack & CircularLinkedStack

CircularStack is a LIFO (Last In, First Out) data structure with a fixed capacity.

Constructor

• new <T>(items: Iterable<T>): Initialize a full stack with the given items.

Methods

• has(value: T): boolean: Checks if the collection contains a specific value.

• last(): T | undefined: Returns the last item without removing it, or undefined if the collection is empty. Alias for top().

• pop(): T | undefined: Removes and returns the last item, or undefined if the collection is empty.

• push(...items: T[]): number: Appends items to the collection and returns the new size. If at capacity, items at the front are overwritten and emitted via the BoundedEvent.Overflow event.

• top(): T | undefined: Returns the item at the top without removing it, or undefined if the collection is empty. Alias for last().

• [Symbol.iterator](): IterableIterator<T>: Returns an iterator for the values in the collection.

Build

First clone the project from github:

git clone git@github.com:havelessbemore/circle-ds.git
cd circle-ds

Install the project dependencies:

npm install

Then, the project can be build by executing the build script via npm:

npm run build

This will build ESM and CommonJS outputs from the source files and put them in the dist/ folder.

Test

To execute tests for the library, install the project dependencies once:

npm install

Then, the tests can be executed:

npm test

You can separately run the code linter:

npm run lint

To automatically fix linting issue, run:

npm run format

To test code coverage of the tests:

npm run test:coverage

To see the coverage results, open the generated report in your browser:

./coverage/index.html

Made with ❤️ by Michael Rojas