DoubleLinked.php with not numeric keys

DoubleLinked.php

<?php declare(strict_types=1);

class DoubleLinkedException extends \Exception
{
}

class WrongNameDoubleLinkedException extends DoubleLinkedException
{
}

class NotFoundDoubleLinkedException extends DoubleLinkedException
{
}

class DoubleLinked implements Iterator, ArrayAccess, Countable
{
    protected $name_first;
    protected $name_last;
    protected $count = 0;
    protected $random_len = 10;
    protected $name_current;

    public function count()
    {
        return $this->count;
    }

    public function next(string $name = null)
    {
        $name_current_next = $this->keyNext($name);

        if ($name_current_next == null) {
            $this->name_current = null;
            return null;
        }

        $this->rewind($name_current_next);//set current

        return $this->getByKey($name_current_next);//current
    }

    public function prev(string $name = null)
    {
        $name_current_prev = $this->keyPrev($name);
        if ($name_current_prev == null) {
            return null;
        }
        $this->rewind($name_current_prev);//set current

        return $this->getByKey($name_current_prev);//current
    }

    public function keyNext(string $name = null): ?string
    {
        if ($name === null) {
            $name = $this->key();
            if ($name === null) {
                return null;
            }
        } else {
            $this->checkValidKey($name);
        }

        $name_current_next = "next_{$name}";

        return $this->$name_current_next ?? null;
    }

    public function keyPrev($name = null): ?string
    {
        if ($name === null) {
            $name = $this->key();
            if ($name === null) {
                return null;
            }
        } else {
            $this->checkValidKey($name);
        }
        $name_current_prev = "prev_{$name}";

        return $this->$name_current_prev ?? null;
    }

    public function rewind(string $name = null): void
    {
        if ($name === null) {
            $this->name_current = $this->name_first;
        } else {
            $this->valid($name);
            $this->name_current = $name;
        }
    }

    public function toArray(): array
    {
        $name = $this->keyFirst();
        $result = [];
        while ($name !== null) {
            $result[$name] = $this->getByKey($name);

            $name = $this->keyNext($name);
        }


        return $result;
    }

    protected function getNewKey(): string
    {
        $i = 0;
        while (true) {
            $name = bin2hex(random_bytes($this->random_len));
            $key = "value_{$name}";
            if (!isset($this->$key)) {
                return $name;
            }

            if (++$i > 100) {
                $this->random_len += 1;
                $i = 0;
                if ($this->random_len > 120) {
                    throw new \Exception('iterable error');
                }
            }
        }
    }

    public function pushAfter($name_after, $value): string
    {
        $this->checkValidKey($name_after);
        $name = $this->getNewKey();

        $name_cur_value = "value_{$name}";
        $name_cur_prev = "prev_{$name}";
        $name_cur_next = "next_{$name}";

        $name_prev_next = "next_{$name_after}";
        $name_next_prev = "prev_{$this->$name_prev_next}";

        $this->$name_cur_value = $value;
        $this->$name_cur_prev = $name_after;
        $this->$name_cur_next = $this->$name_prev_next;

        $this->$name_next_prev = $name;
        $this->$name_prev_next = $name;

        if ($this->name_last === $name_after) {
            $this->name_last = $name;
        }

        $this->count += 1;
        
        return $name;
    }

    function push(... $values): void
    {
        $pushed = [];
        foreach ($values as $value) {
            $name = $this->getNewKey();
            $name_cur_value = "value_{$name}";

            $name_cur_prev = "prev_{$name}";
            $name_prev = $this->name_last;
            $this->$name_cur_value = $value;

            if ($name_prev === null) {
                assert($this->name_first === null);
                assert($this->count === 0);
                $this->name_first = $name;
                $this->name_current = $this->name_current ?? $name;
            } else {
                $name_prev_next = "next_{$name_prev}";
                $this->$name_prev_next = $name;
                $this->$name_cur_prev = $name_prev;
            }
            $this->name_last = $name;
            $this->count += 1;
            //$pushed[] = $name;
        }
        //todo revert on exception
    }

    function unshift(... $values): void
    {
        $pushed = [];
        foreach ($values as $value) {
            $name = $this->getNewKey();
            $name_cur_value = "value_{$name}";
            $name_cur_next = "next_{$name}";

            $name_next = $this->name_first;
            $this->$name_cur_value = $value;

            if ($name_next === null) {
                assert($this->name_last === null);
                assert($this->count === 0);
                $this->name_last = $name;
                $this->name_current = $this->name_current ?? $name;
            } else {
                $name_next_prev = "prev_{$name_next}";
                $this->$name_next_prev = $name;
                $this->$name_cur_next = $name_next;
            }
            $this->name_first = $name;
            $this->count += 1;
            //$pushed[] = $name;
        }
        //todo revert on exception
    }

    public function current()
    {
        $current_name = $this->key();

        return $current_name ? $this->getByKey($current_name) : null;
    }

    public function key(): ?string
    {
        return $this->name_current;
    }

    public function offsetGet($offset)
    {
        return $this->getByKey($this->getKeyByOffset($offset));
    }

    public function getByKey($name)
    {
        $this->checkValidKey($name);

        $current_value_key = "value_{$name}";
        $result = $this->$current_value_key ?? null;
        if ($result === null && !$this->isKeyExist($name)) {
            throw new NotFoundDoubleLinkedException("!{$name}");
        }

        return $result;
    }

    public function first()
    {
        if (!$this->name_first) {
            return null;
        }
        return $this->getByKey($this->name_first);
    }

    public function last()
    {
        if (!$this->name_last) {
            return null;
        }
        return $this->getByKey($this->name_last);
    }

    public function end()
    {
        $this->name_current = $this->name_last;
        return $this->current();
    }


    public function keyFirst(): ?string
    {
        return $this->name_first;
    }

    public function keyLast(): ?string
    {
        return $this->name_last;
    }

    public function valid(string $name = null): bool
    {
        if ($name === null) {
            return $this->name_current !== null;
        }

        return $this->isKeyExist($name);
    }

    protected function checkValidKey($name)
    {
        $result = (
            (
                is_string($name)
                || (
                    is_object($name)
                    && $name instanceof StringableClass
                )
            )
            && strlen($name) > 0
        );

        if (!$result) {
            throw new WrongNameDoubleLinkedException('wrong name: ' . var_export($name, true));
        }

        return $this;
    }

    public function isKeyExist($name)
    {
        $this->checkValidKey($name);

        return property_exists(
            $this,
            "value_{$name}"
        );
    }

    public function offsetExists($offset)
    {
        return $this->isKeyExist(
            $this->getKeyByOffset($offset)
        );
    }

    public function getKeyByOffset($offset)
    {
        if (is_numeric($offset) && $offset < 0) {
            throw new DoubleLinkedException('wrong offset');
        }
        $cur = $this->keyFirst();
        while ($cur !== null && --$offset > 0) {
            $cur = $this->keyNext($cur);
        }

        if ($cur === null) {
            throw new NotFoundDoubleLinkedException();
        }

        return $cur;
    }

    /**
     * too slow. USE pushAfter
     * @param mixed $offset
     * @param mixed $value
     * @throws DoubleLinkedException
     * @throws NotFoundDoubleLinkedException
     */
    public function offsetSet($offset, $value)
    {
        return $this->pushAfter(
            $this->getKeyByOffset($offset),
            $value
        );
    }

    public function offsetUnset($offset): void
    {
        $this->unsetKey(
            $this->getKeyByOffset($offset)
        );
    }

    public function unsetKey($name): void
    {
        if (!$this->isKeyExist($name)) {
            return;
        }

        $name_cur_value = "value_{$name}";
        $name_cur_next = "next_{$name}";
        $name_cur_prev = "prev_{$name}";
        $name_prev_next = "next_{$this->$name_cur_prev}";
        $name_next_prev = "prev_{$this->$name_cur_next}";
        $this->$name_next_prev = $this->$name_cur_prev ?? null;
        $this->$name_prev_next = $this->$name_cur_next ?? null;

        if ($this->name_first === $name) {
            $this->name_first = $this->$name_cur_next ?? null;
        }

        if ($this->name_last === $name) {
            $this->name_last = $this->$name_cur_prev ?? null;
        }

        unset(
            $this->$name_cur_value,
            $this->$name_cur_prev,
            $this->$name_cur_next
        );
    }

}

<?php declare(strict_types=1);
include "vendor/autoload.php";
include "DoubleLinked.php";

$max_count = 100000;

$min_delimer = 10;
$min_count = (int)($max_count / $min_delimer);

for ($y = 0; $y < 3; ++$y) {

    $time_extra_start = microtime(true);
    $test_linked = new DoubleLinked;

    for ($i = 0; $i < $min_count; ++$i) {
        $test_linked->push($i);
        $test_linked->unshift(-$i);
        $name = $test_linked->offsetSet(
            (int)($test_linked->count() / 2),
            'offsetSet_' . $i
        );
        $name = $test_linked->pushAfter($name, 'pushAfter_' . $i);
        $test_linked->unsetKey($name);
        //$test_linked->offsetUnset(1+(int)($test_linked->count() / 2));
    }

    $time_create_middle_offset = microtime(true);

    $test_linked = new DoubleLinked;

    $name_moddle = null;
    for ($i = 0; $i < $max_count; ++$i) {
        $test_linked->push($i);
        $test_linked->unshift(-$i);
        $name_moddle = $name_moddle ?? $test_linked->keyFirst();
        $name =$test_linked->pushAfter($name_moddle, "pushAfter1_{$i}");
        $name =$test_linked->pushAfter($name, "pushAfter2_{$i}");
        $test_linked->unsetKey($name);
    }

    $time_start = $time_create_middle_after = microtime(true);

    $test_linked = new DoubleLinked;

    for ($i = 0; $i < $max_count; ++$i) {
        $test_linked->push($i);
        $test_linked->unshift(-$i);
    }
    $time_create = microtime(true);

    foreach ($test_linked as $key => $value) {
        $x = [$key => $value];
    }

    $time_foreach = microtime(true);
    $test_linked->rewind();
    $check_1 = 0;
    while ($test_linked->valid()) {
        ++$check_1;
        $test_linked->next();
        $test_linked->prev();
        $test_linked->next();
        $test_linked->next();
    }

    $time_nextprev = microtime(true);

    $mem = memory_get_usage();
    //dump($test_linked);
    $count_linked = $test_linked->count();
    unset($test_linked);

    dump(['DoubleLinked' => [
        'mem' => round($mem / 1024 / 1024, 2) . 'mb',
        "time_create_middle_offset: X / $min_delimer" => round($time_create_middle_offset - $time_extra_start, 2),
        "time_create_middle_after" => round($time_create_middle_after - $time_create_middle_offset, 2),
        'time_create' => round($time_create - $time_start, 2),
        'time_foreach' => round($time_foreach - $time_create, 2),
        'time_nextprev' => round($time_nextprev - $time_foreach, 2),
        'time_total' => round($time_nextprev - $time_start, 2) . ' + extra: ' . round($time_start - $time_extra_start, 2),
    ]]);

//----------------------------------------

    $time_extra_start = microtime(true);
    $test_spl = new SplDoublyLinkedList;

    for ($i = 0; $i < $max_count; ++$i) {
        $test_spl->push($i);
        $test_spl->unshift(-$i);
        $offset = (int)($test_spl->count() / 2);
        $test_spl->add($offset, 'add1_' . $i);
        $test_spl->add($offset + 1, 'add2_' . $i);
        $test_spl->offsetUnset($offset + 1);
    }

    $time_create_middle_offset = microtime(true);


    $test_spl = new SplDoublyLinkedList;
    $test_array = [];
    for ($i = 0; $i < $min_count; ++$i) {
        $test_spl->push($i);
        $test_spl->unshift(-$i);
        foreach ($test_spl as $offset => $value) {
            if ($value === 0) {
                $test_spl->add($offset, 'middle1_' . $i);
                $test_spl->add($offset+1, 'middle2_' . $i);
                $test_spl->offsetUnset($offset + 1);
                break;
            }
        }
    }

    $time_start = $time_create_middle_after = microtime(true);

    $test_spl = new SplDoublyLinkedList;
    for ($i = 0; $i < $max_count; ++$i) {
        $test_spl->push($i);
        $test_spl->unshift(-$i);
    }
    $time_create = microtime(true);

    foreach ($test_spl as $key => $value) {
        $x = [$key => $value];
    }
    $time_foreach = microtime(true);
    $test_spl->rewind();
    $check_2 = 0;
    while ($test_spl->valid()) {
        ++$check_2;
        $test_spl->next();
        $test_spl->prev();
        $test_spl->next();
        $test_spl->next();
    }

    $time_nextprev = microtime(true);

    $mem = memory_get_usage();
    //dump($test_spl);
    $count_spl = $test_spl->count();
    unset($test_spl);
    dump(['SplDoublyLinkedList' => [
        'mem' => round($mem / 1024 / 1024, 2) . 'mb',
        "time_create_middle_offset" => round($time_create_middle_offset - $time_extra_start, 2),
        "time_create_middle_after: X / $min_delimer" => round($time_create_middle_after - $time_create_middle_offset, 2),
        'time_create' => round($time_create - $time_start, 2),
        'time_foreach' => round($time_foreach - $time_create, 2),
        'time_nextprev' => round($time_nextprev - $time_foreach, 2),
        'time_total' => round($time_nextprev - $time_create, 2),
    ]]);

//----------------------------------------

    $time_extra_start = microtime(true);
    $test_array = [];

    for ($i = 0; $i < $min_count; ++$i) {
        $key = bin2hex(random_bytes(10));
        $test_array[$key] = $i;
        array_unshift($test_array, -$i);
        $offset = (int)(count($test_array) / 2);
        $unset_key = bin2hex(random_bytes(10));

        $test_array = (
            array_slice($test_array, 0, $offset, true)
            + [
                bin2hex(random_bytes(10)) => 'pos1_' . $i,
                $unset_key => 'pos2_' . $i,
            ]
            + array_slice($test_array, $offset, null, true)
        );

        unset($test_array[$unset_key]);
    }

    $time_create_middle_offset = microtime(true);


    $name_moddle = null;
    $test_array = [];
    for ($i = 0; $i < $min_count; ++$i) {
        $key = bin2hex(random_bytes(10));
        $test_array[$key] = $i;
        //array_unshift($test_array, -$i);//very slow
        $test_array = [bin2hex(random_bytes(10)) => -$i] + $test_array;

        $name_moddle = $name_moddle ?? $key;
        $offset = array_search($name_moddle, array_keys($test_array));
        $unset_key = bin2hex(random_bytes(10));
        $test_array = (
            array_slice($test_array, 0, $offset, true)
            + [
                bin2hex(random_bytes(10)) => 'array_slice1_' . $i,
                $unset_key => 'array_slice2_' . $i,
            ]
            + array_slice($test_array, $offset, null, true)
        );
        unset($test_array[$unset_key]);
    }

    $time_start = $time_create_middle_after = microtime(true);

    $test_array = [];
    for ($i = 0; $i < $min_count; ++$i) {
        $test_array[] = $i;
        array_unshift($test_array, -$i);
    }

    $time_create = microtime(true);

    foreach ($test_array as $key => $value) {
        $x = [$key => $value];
    }
    $time_foreach = microtime(true);
    reset($test_array);
    $check_3 = 0;

    while (key($test_array) !== null) {
        ++$check_3;
        $x = next($test_array);
        $x = prev($test_array);
        $x = next($test_array);
        $x = next($test_array);
    }

    $time_nextprev = microtime(true);


    $mem = memory_get_usage();
    //dump($test_array);
    $count_array = count($test_array);
    unset($test_array);

    dump(["array: X / $min_delimer" => [
        'mem' => round($mem / 1024 / 1024, 2) . 'mb',
        "time_create_middle_offset: X / $min_delimer" => round($time_create_middle_offset - $time_extra_start, 2),
        "time_create_middle_after: X / $min_delimer" => round($time_create_middle_after - $time_create_middle_offset, 2),
        "time_create: X / $min_delimer" => round($time_create - $time_start, 2),
        "time_foreach: X / $min_delimer" => round($time_foreach - $time_create, 2),
        "time_nextprev: X / $min_delimer" => round($time_nextprev - $time_foreach, 2),
        'time_total' => round($time_nextprev - $time_start, 2) . ' + extra: ' . round($time_start - $time_extra_start, 2),
    ]]);

    if ($count_array * $min_delimer != $count_spl || $count_spl != $count_linked) {
        dd(['check count' => [$count_linked, $count_spl, $count_array]]);
    }
    if ($check_3 * $min_delimer != $check_2 || $check_1 != $check_2) {
        dd(['check filed' => [$check_1, $check_2, $check_3]]);
    }

    echo "\n----------------------------------------\n\n";
}

array:1 [
  "DoubleLinked" => array:7 [
    "mem" => "81.16mb"
    "time_create_middle_offset: X / 10" => 27.78
    "time_create_middle_after" => 0.94
    "time_create" => 0.37
    "time_foreach" => 0.36
    "time_nextprev" => 0.39
    "time_total" => "1.13 + extra: 28.72"
  ]
]
array:1 [
  "SplDoublyLinkedList" => array:7 [
    "mem" => "18.84mb"
    "time_create_middle_offset" => 420.16
    "time_create_middle_after: X / 10" => 5.32
    "time_create" => 0.01
    "time_foreach" => 0.02
    "time_nextprev" => 0.02
    "time_total" => 0.05
  ]
]
array:1 [
  "array: X / 10" => array:7 [
    "mem" => "12.22mb"
    "time_create_middle_offset: X / 10" => 13.69
    "time_create_middle_after: X / 10" => 20.5
    "time_create: X / 10" => 0.78
    "time_foreach: X / 10" => 0.0
    "time_nextprev: X / 10" => 0.0
    "time_total" => "0.78 + extra: 34.19"
  ]
]