README

A PHP library providing a sorted linked list for typed values. It provides sorted linked lists for integers and strings, with a strategy-based extension point for custom value types.

Requirements

PHP 8.2 or newer
PHP intl extension
Composer

Installation

Install the library with Composer:

composer require r34117y/sorted-linked-list

Then import the factory class where you need it:

use Agrzelec\SortedLinkedList\SortedLinkedListFactory;

Architecture

Create lists with SortedLinkedListFactory. SortedLinkedList has a public constructor only for factory and extension internals, and that constructor is marked @internal.

Built-in factories configure the strategy for common value types:

SortedLinkedListFactory::forIntegers() uses numeric ascending order by default, or descending order when requested.
SortedLinkedListFactory::forStrings() uses lexicographic ascending order by default, or locale-aware collation when a locale is provided. It can also sort descending.
SortedLinkedListFactory::usingStrategy() accepts a custom SortedListStrategy for any value type.

Strategies validate values through normalize() and compare normalized values through compare(). Invalid values should be rejected by throwing InvalidValueTypeException.

Usage

Integer Lists

use Agrzelec\SortedLinkedList\SortedLinkedListFactory;

$list = SortedLinkedListFactory::forIntegers([3, 1, 2]);
$list->insert(2);

$list->toArray(); // [1, 2, 2, 3]
$list->first(); // 1
$list->last(); // 3
$list->contains(2); // true

Use descending: true for descending integer order:

$list = SortedLinkedListFactory::forIntegers([3, 1, 2], descending: true);

$list->toArray(); // [3, 2, 1]
$list->first(); // 3
$list->last(); // 1

String Lists

use Agrzelec\SortedLinkedList\SortedLinkedListFactory;

$list = SortedLinkedListFactory::forStrings(['banana', 'apple', 'cherry']);
$list->insert('apple');

$list->toArray(); // ['apple', 'apple', 'banana', 'cherry']
$list->first(); // 'apple'
$list->last(); // 'cherry'
$list->contains('banana'); // true

Use descending: true for descending string order:

$list = SortedLinkedListFactory::forStrings(['banana', 'apple', 'cherry'], descending: true);

$list->toArray(); // ['cherry', 'banana', 'apple']
$list->first(); // 'cherry'
$list->last(); // 'apple'

Use a locale to sort strings in locale-aware order:

$list = SortedLinkedListFactory::forStrings(['ą', 'a', 'ź', 'z'], locale: 'pl_PL');

$list->toArray(); // ['a', 'ą', 'z', 'ź']
$list->first(); // 'a'
$list->last(); // 'ź'

If locale cannot be resolved, LocaleNotInstalledException is thrown.

Custom Strategy Lists

use Agrzelec\SortedLinkedList\Exception\InvalidValueTypeException;
use Agrzelec\SortedLinkedList\SortedLinkedListFactory;
use Agrzelec\SortedLinkedList\Strategy\SortedListStrategy;

/**
 * @implements SortedListStrategy<DateTimeImmutable>
 */
final class DateTimeImmutableStrategy implements SortedListStrategy
{
    public function normalize(mixed $value): DateTimeImmutable
    {
        if (!$value instanceof DateTimeImmutable) {
            throw new InvalidValueTypeException(sprintf(
                'Expected value of type %s, got %s.',
                DateTimeImmutable::class,
                get_debug_type($value),
            ));
        }

        return $value;
    }

    public function compare(mixed $left, mixed $right): int
    {
        $left = $this->normalize($left);
        $right = $this->normalize($right);

        return $left->getTimestamp() <=> $right->getTimestamp();
    }
    
    public static function getValueType(): string
    {
        return DateTimeImmutable::class;
    }
}

$list = SortedLinkedListFactory::usingStrategy(
    new DateTimeImmutableStrategy(),
    [
        new DateTimeImmutable('2024-12-01'),
        new DateTimeImmutable('2024-01-01'),
    ],
);

$list->insert(new DateTimeImmutable('2024-06-01'));

$list->toArray(); // 2024-01-01, 2024-06-01, 2024-12-01

Value Typing

Built-in lists can contain integers or strings, but never both.

Direct construction is marked internal and is not supported for consumers. Use SortedLinkedListFactory::forIntegers() for integer lists, SortedLinkedListFactory::forStrings() for string lists, or SortedLinkedListFactory::usingStrategy() for custom value types.

Lists created with SortedLinkedListFactory::forIntegers() or SortedLinkedListFactory::forStrings() are explicitly typed from the start. They keep that type even when empty or after clear().

valueType() returns the value type string defined by the configured strategy.

Invalid values are rejected with Agrzelec\SortedLinkedList\Exception\InvalidValueTypeException. This applies to factory initialization, insertion, contains(), and remove().

use Agrzelec\SortedLinkedList\Exception\InvalidValueTypeException;
use Agrzelec\SortedLinkedList\SortedLinkedListFactory;

$list = SortedLinkedListFactory::forIntegers([1, 2, 3]);

try {
    $list->insert('4');
} catch (InvalidValueTypeException $exception) {
    // The list still contains [1, 2, 3].
}

Sorting

Integer lists use numeric ascending order by default.

SortedLinkedListFactory::forIntegers([10, -1, 2])->toArray(); // [-1, 2, 10]
SortedLinkedListFactory::forIntegers([10, -1, 2], descending: true)->toArray(); // [10, 2, -1]

String lists use lexicographic ascending order by default, using PHP's strcmp() semantics. The default order is case-sensitive, and numeric strings remain strings.

SortedLinkedListFactory::forStrings(['2', '10', '1'])->toArray(); // ['1', '10', '2']
SortedLinkedListFactory::forStrings(['2', '10', '1'], descending: true)->toArray(); // ['2', '10', '1']

Pass a locale to forStrings() to use locale-aware collation through PHP intl's collator_sort():

$list = SortedLinkedListFactory::forStrings(['z', 'ą', 'a'], 'pl_PL');

$list->toArray(); // ['a', 'ą', 'z']

Descending locale-aware sorting is also supported:

$list = SortedLinkedListFactory::forStrings(['z', 'ą', 'a'], 'pl_PL', descending: true);

$list->toArray(); // ['z', 'ą', 'a']

Locale-aware sorting depends on ICU locales provided by PHP's intl extension. If the configured locale cannot be resolved, LocaleNotInstalledException is thrown.

Custom strategy lists use the ordering returned by the strategy's compare() method.

Duplicates

Duplicate values are allowed. New duplicates are placed after existing equal values, so the insertion order is stable among equal values.

remove() removes one matching value at a time:

$list = SortedLinkedListFactory::forIntegers([1, 2, 2, 3]);

$list->remove(2); // true
$list->toArray(); // [1, 2, 3]

API Reference

SortedLinkedListFactory::forIntegers(iterable $values = [], bool $descending = false): SortedLinkedList<int> creates an integer-only list.
SortedLinkedListFactory::forStrings(iterable $values = [], ?string $locale = null, bool $descending = false): SortedLinkedList<string> creates a string-only list, optionally using locale-aware sorting.
SortedLinkedListFactory::usingStrategy(SortedListStrategy<T> $strategy, iterable<T> $values = []): SortedLinkedList<T> creates a custom strategy list.
valueType(): string returns the list value type, defined in the relevant strategy.
isEmpty(): bool returns whether the list has no values.
count(): int returns the number of values. The list also supports PHP's count($list).
insert(T $value): void inserts a value while preserving sorted order.
contains(T $value): bool checks whether a value is present.
remove(T $value): bool removes one matching value and returns whether anything was removed.
first(): T|null returns the first sorted value, or null when empty.
last(): T|null returns the last sorted value, or null when empty.
clear(): void removes all values.
toArray(): list<T> returns values as a sorted PHP list.
getIterator(): Traversable<int, T> supports foreach iteration in sorted order.
jsonSerialize(): list<T> serializes the list as a JSON array.

Operation Complexity

Operation	Complexity	Notes
`insert()`	O(n)	Finds the sorted insertion point.
`contains()`	O(n)	Stops early when the current value is greater than the searched value.
`remove()`	O(n)	Removes the first matching value and stops early when possible.
`first()`	O(1)	Reads the head node.
`last()`	O(1)	Reads the tracked tail node.
`count()` / `isEmpty()`	O(1)	Uses tracked list size.
`clear()`	O(1)	Drops head and tail references.
`toArray()` / iteration / JSON serialization	O(n)	Walks the list in sorted order.

Benchmark

These figures are illustrative, not guarantees. They were measured on a local run with PHP 8.4.6 using integer lists built from deterministic shuffled input. Each value is the median of 3 runs.

Length	Build shuffled list	`contains()` last value	`contains()` missing high value	`toArray()`
100	1.432 ms	0.176 ms	0.003 ms	0.043 ms
1,000	23.423 ms	1.744 ms	0.006 ms	0.378 ms
2,500	74.699 ms	5.078 ms	0.008 ms	1.035 ms
5,000	150.381 ms	8.376 ms	0.008 ms	1.970 ms

Shuffled construction was intentionally the expensive case because every inserted value could scan part of the list. Factory construction now sorts the initial values first, so building shuffled input scales much better. Existing insert() calls still use linked-list insertion and remain O(n).

Development

Install dependencies:

composer install

Common local commands:

Command	Description
`composer test`	Run the PHPUnit test suite.
`composer analyse`	Run PHPStan static analysis.
`composer cs`	Check coding standards with PHP-CS-Fixer.
`composer cs:fix`	Automatically fix coding-standard issues.
`composer check`	Run coding standards, static analysis, and tests.

Versioning

This project follows Semantic Versioning. Release notes are maintained in CHANGELOG.md.

r34117y / sorted-linked-list

Package info

Security

Statistics