algopat

Algorithms and Design Patterns

A simple npm package containing common design patterns and algorithms.

Table of Contents

- Features
- Installation
- Usage
- Design Patterns
- Adapter
- Factory Method
- Prototype
- Prototype Registry
- Abstract Prototype Registry
- Singleton
- Algorithms
- Insert Sort
- Selection Sort
- Merge Sort
- Development
- Quick Start with DevContainer
- Install Dependencies
- Build the Project
- Run Tests
- Code Quality
- Scripts
- Publishing
- License

Features

- Design Patterns: Singleton, Factory, Prototype patterns and more
- Algorithms: Sort, Tree Search, Shortest Path and more
- DevContainer: Ready-to-use development environment

Installation

``bash
npm install algopat
`

Usage

$3

#### Adapter

The Adapter pattern is a structural design pattern that allows objects with incompatible interfaces to work together by wrapping an existing object with a new interface.

Adapter is an abstract class. To use it, extend it and implement the desired interface, delegating calls to the _target property.

import { Adapter } from 'design-patterns'
| Method / Property | Description | Example |
|---------------------|------------------------------------------------------------------|-----------------------------------------------------------------------------------------|
| constructor(target: T) | Initializes the adapter with the target object. | const adapter = new Adapter(targetInstance); |
| _target: T | Protected property holding the reference to the adapted target. | this._target.incompatibleRequest(); (used within subclasses) |

#### Factory Method

The Factory Method pattern is a creational design pattern that defines an interface for creating objects, but allows subclasses to alter the type of objects that will be created. This pattern enables a class to delegate the instantiation logic to its subclasses, promoting loose coupling and greater flexibility in object creation.

Creator is an abstract class. To use it, extend it and implement the make(...args) method to create and return instances of your desired type.

import { Creator } from 'design-patterns'

| Method / Property | Description | Example |
| ------------------ | ------------------------------------------------------------- | ---------------------------------------- |
| make(...args): T | Abstract method to create and return an instance of type T. | const product = factory.make('param'); |

#### Prototype

The Prototype pattern is a creational design pattern that enables the creation of new objects by copying existing instances, known as prototypes. This approach is useful when the cost of creating a new object is expensive or complex. Instead of instantiating new objects directly, you clone a prototype and then customize it as needed. This pattern helps reduce the need for subclassing, supports dynamic object creation, and simplifies the process of creating objects with similar configurations or states.

Prototype is an abstract class—extend it in your own classes and implement clone() and initialize(...args) to enable cloning and initialization of your objects.

import { Prototype } from 'design-patterns'

| Method / Property | Description | Example |
| ---------------------------------- | -------------------------------------------------------------- | ------------------------------------- |
| clone(): T | Abstract method to clone the object and return a new instance. | const copy = prototype.clone(); |
| initialize(...args: any[]): void | Abstract method to initialize the object's state. | prototype.initialize('id', 'name'); |

#### Prototype Registry

The PrototypeRegistry is a concrete implementation of the prototype registry pattern. It allows you to register, unregister, and retrieve prototype instances by a unique string identifier. This enables efficient cloning and management of object prototypes, making it easy to create new instances based on existing templates without coupling your code to specific classes.

To use PrototypeRegistry, create an instance, register your prototypes with unique ids, and retrieve them as needed. You can then clone the retrieved prototype to create new objects with the same structure and state.

import { PrototypeRegistry } from 'design-patterns'

| Method / Property | Description | Example |
| ------------------------- | ----------------------------------------------------------------------------- | ------------------------------------------------- |
| register(id, prototype) | Registers a prototype instance with a unique string id. | registry.register('product1', productInstance); |
| unregister(id) | Removes a prototype from the registry by its id. | registry.unregister('product1'); |
| get(id) | Retrieves a registered prototype by id. Returns the prototype or undefined. | const proto = registry.get('product1'); |

#### Abstract Prototype Registry

AbstractPrototypeRegistry is an abstract class. Extend it to implement your own registry logic.

import { AbstractPrototypeRegistry } from 'design-patterns'

| Method / Property | Description | Example |
| --------------------------- | ------------------------------------------------------------------------- | --------------------------------------------------- |
| register(id, prototype) | Abstract method to register a prototype instance with a unique string id. | registry.register('product1', productInstance); |
| unregister(id, prototype) | Abstract method to remove a prototype from the registry by its id. | registry.unregister('product1', productInstance); |
| get(id) | Abstract method to retrieve a registered prototype by id. | const proto = registry.get('product1'); |

#### Singleton

The Singleton pattern ensures that a class has only one instance and provides a global point of access to it. To use, extend the Singleton base class and access the instance via instance().

import { Singleton } from 'design-patterns'

| Method / Property | Description | Example |
| ------------------------------------------ | -------------------------------------------------------------------------- | ---------------------------------------------------------------------------------------------------------------------------- |
| instance() | Returns the single instance of the singleton class. | const instance = Singleton.instance(); |
| constructor(factory: InstanceCreator) | Protected constructor to initialize the singleton instance with a factory. | class MySingleton extends Singleton { protected constructor() { super({ make: () => new MySingleton() }); } } |

$3

#### Insert Sort

The Insertion Sort algorithm is a simple, intuitive sorting technique that builds the sorted array one item at a time. It works by iterating through the array, taking each element, and inserting it into its correct position relative to the already sorted portion of the array. This algorithm is efficient for small or nearly sorted datasets and is stable (preserves the order of equal elements).

import { insertionSort } from 'design-patterns'
| Argument | Description | Default Value | Example |
| ------------- | --------------------------------------------------------------------------- | ------------- | -------------------------------------------- |
| arr | The array to sort. | — | [5, 3, 8, 4, 2] |
| compareFn | Function to compare two elements. Should return -1, 0, or 1. | (a, b) => (a < b ? -1 : a > b ? 1 : 0) | (a, b) => a.localeCompare(b) |
| options | Optional settings for sorting. See below for details. | { mutable: true } | { mutable: false } |

Options

| Option | Description | Default Value | Example |
| --------- | ----------------------------------------------------------------------------- | ------------- | ------- |
| mutable | If true, sorts the input array in-place. If false, returns a sorted copy. | true | false |

#### Selection Sort

The Selection Sort algorithm sorts an array by repeatedly finding the minimum (or maximum, with a custom comparator) element from the unsorted part and moving it to the beginning. It is simple to implement and works well for small arrays, but is generally less efficient than more advanced algorithms for large datasets.

import { selectionSort } from 'design-patterns'

| Argument | Description | Default Value | Example |
| ----------- | ------------------------------------------------------------ | ---------------------------------------- | -------------------- |
| arr | The array to sort. | — | [5, 2, 9, 1, 5, 6] |
| compareFn | Function to compare two elements. Should return -1, 0, or 1. | (a, b) => (a < b ? -1 : a > b ? 1 : 0) | (a, b) => b - a |
| options | Optional settings for sorting. See below for details. | { mutable: true } | { mutable: false } |

Options

| Option | Description | Default Value | Example |
| --------- | ----------------------------------------------------------------------------- | ------------- | ------- |
| mutable | If true, sorts the input array in-place. If false, returns a sorted copy. | true | false |

#### Merge Sort

The Merge Sort algorithm is an efficient, stable, divide-and-conquer sorting technique. It recursively splits the array into halves, sorts each half, and then merges the sorted halves back together. Merge Sort guarantees O(n log n) time complexity and is stable (preserves the order of equal elements).

import { mergeSort } from 'design-patterns'

| Argument | Description | Default Value | Example |
| ----------- | ------------------------------------------------------------ | ---------------------------------------- | ------------------- |
| arr | The array to sort. | — | [5, 3, 8, 4, 2] |
| compareFn | Function to compare two elements. Should return -1, 0, or 1. | (a, b) => (a < b ? -1 : a > b ? 1 : 0) | (a, b) => b - a |
| options | Optional settings for sorting. See below for details. | { mutable: false } | { mutable: true } |

Options

| Option | Description | Default Value | Example |
| --------- | ----------------------------------------------------------------------------- | ------------- | ------- |
| mutable | If true, sorts the input array in-place. If false, returns a sorted copy. | false | true |

Development

$3

The easiest way to get started is using the provided devcontainer:

1. Install Docker
2. Install VS Code with the Dev Containers extension
3. Open this project in VS Code
4. When prompted, click "Reopen in Container"
5. The container will build and install all dependencies automatically

$3

If you prefer to use a different development environment you can simply install dependencies using npm:

`bash
npm install
`

$3

`bash
npm run build
`

This will compile TypeScript files to JavaScript in the dist/ directory.

$3

`bash


Run all tests

npm test

Run tests in watch mode

npm run test:watch

Run tests with coverage

npm run test:coverage
`

$3

`bash


Lint code

npm run lint

Fix linting issues

npm run lint:fix

Format code

npm run format

Check code formatting

npm run format:check
`

$3

`bash
npm run clean
`

$3

- npm run build - Compile TypeScript to JavaScript
- npm test - Run all tests
- npm run test:watch - Run tests in watch mode
- npm run test:coverage - Run tests with coverage report
- npm run clean - Remove build output
- npm run lint - Lint TypeScript files
- npm run lint:fix - Fix linting issues automatically
- npm run format - Format code with Prettier
- npm run format:check - Check code formatting
- npm run prepublishOnly - Clean and build before publishing

Publishing

$3

This project uses GitHub Actions to automatically publish to npm when changes are pushed to the main branch. The workflow will:

1. Run tests and quality checks
2. Create a git tag based on the version in package.json
3. Publish to npm
4. Create a GitHub release

#### Setup Required

To enable automated publishing, you need to add the following secrets to your GitHub repository:

1. NPM_TOKEN: Your npm authentication token
- Go to npmjs.com and log in
- Go to your profile → Access Tokens
- Create a new token with "Automation" type
- Add it as a repository secret named NPM_TOKEN

#### How It Works

- The workflow triggers on pushes to the main branch
- It skips publishing if the commit message contains [skip ci] or [no publish]
- It only publishes if the version hasn't been tagged before
- The workflow runs all quality checks before publishing

$3

To publish manually:

1. Update the version in package.json
2. Run npm run build to ensure the latest code is compiled
3. Run npm publish

The prepublishOnly` script will automatically clean and build the project before publishing.

License

MIT