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
• Composer

Installation

Install the library with Composer:

composer require r34117y/sorted-linked-list

Then import the list class where you need it:

use Agrzelec\SortedLinkedList\SortedLinkedList;

Architecture

SortedLinkedList is factory-only. Its constructor is private, so every list is created with a sorting strategy before values can be inserted.

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

• SortedLinkedList::forIntegers() uses numeric ascending order by default, or descending order when requested.
• SortedLinkedList::forStrings() uses lexicographic ascending order by default, or locale-aware collation when a locale is provided. It can also sort descending.
• SortedLinkedList::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\SortedLinkedList;

$list = SortedLinkedList::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 = SortedLinkedList::forIntegers([3, 1, 2], descending: true);

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

String Lists

use Agrzelec\SortedLinkedList\SortedLinkedList;

$list = SortedLinkedList::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 = SortedLinkedList::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 = SortedLinkedList::forStrings(['ą', 'a', 'ź' 'z'], locale: 'pl_PL.utf8');

$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\SortedLinkedList;
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 = SortedLinkedList::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 not part of the public API. Use SortedLinkedList::forIntegers() for integer lists, SortedLinkedList::forStrings() for string lists, or SortedLinkedList::usingStrategy() for custom value types.

Lists created with SortedLinkedList::forIntegers() or SortedLinkedList::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\SortedLinkedList;

$list = SortedLinkedList::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.

SortedLinkedList::forIntegers([10, -1, 2])->toArray(); // [-1, 2, 10]
SortedLinkedList::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.

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

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

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

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

Descending locale-aware sorting is also supported:

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

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

Locale-aware sorting depends on locales installed in the runtime environment. If the configured locale is not installed, 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 = SortedLinkedList::forIntegers([1, 2, 2, 3]);

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

API Reference

• SortedLinkedList::forIntegers(iterable $values = [], bool $descending = false): self<int> creates an integer-only list.
• SortedLinkedList::forStrings(iterable $values = [], ?string $locale = null, bool $descending = false): self<string> creates a string-only list, optionally using locale-aware sorting.
• SortedLinkedList::usingStrategy(SortedListStrategy<T> $strategy, iterable<T> $values = []): self<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

Development

Install dependencies:

composer install

Common local commands:

Versioning

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