Lexorank orderer function in PHP. With helper trait for Laravel.

lexorank.php

<?php

namespace App\Functions; // Remove if using outside Laravel

use function strlen; // Micro-optimization

const LEXORANK_NUM_SET = '0123456789';
const LEXORANK_LOWER_ALPHA_SET = 'abcdefghijklmnopqrstuvwxyz';
const LEXORANK_UPPER_ALPHA_SET = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
const LEXORANK_ALPHANUM_SET = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz';
const LEXORANK_SET = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz';

/**
 * lexorank_between allows you to generate a lexorank value between two other
 * values.
 * 
 * The $set param allows you to customize the lexorank set to be used. If using
 * a custom set, make sure to check if it's properly sorted and have no
 * duplicate values, since the function does not check for that. This can be
 * done splitting the set into an array of chars and calling
 * sort($set, SORT_STRING) on it.
 * 
 * @param mixed $upper The rank value that is closer to the top of the list
 * @param mixed $lower The rank value that is closer to the bottom of the list
 * @param string $set
 * @return string
 */
function lexorank_between(?string $upper, ?string $lower, string $set = LEXORANK_SET): string
{
    $setSize = strlen($set);
    $start = $set[0];
    $end = $set[-1];
    $middle = $set[(int) floor(($setSize - 1) / 2) + ($setSize - 1) % 2];

    if ($upper === null && $lower === null)
        return $middle;
    if ($upper === null)
        return lexorank_between($start, $lower);
    if ($lower === null)
        return lexorank_between($upper, $end);

    if (strcmp($upper, $lower) > 0) {
        [$upper, $lower] = [$lower, $upper];
    }

    $length = max(strlen($upper), strlen($lower));
    $upperP = str_pad($upper, $length, $start);
    $lowerP = str_pad($lower, $length, $end);

    $path = '';

    for ($i = 0; $i < $length; $i++) {
        $upperN = strpos($set, $upperP[$i]);
        $lowerN = strpos($set, $lowerP[$i]);

        $distance = abs($upperN - $lowerN);
        if ($distance > 1) {
            return $path . $set[min($upperN, $lowerN) + (int) floor($distance / 2) + $distance % 2];
        }

        $path .= $upperP[$i];
    }

    if (strlen($path) > 1 && $upper === $start)
        return substr($path, 0, -1) . lexorank_between($start, $path[-1]);
    if (strlen($path) > 1 && $lower === $end)
        return substr($path, 0, -1) . lexorank_between($path[-1], $end);

    return $path . $middle;
}

LexorankOrdering.php

<?php

/**
 * Trait LexorankOrdering to be used with Laravel framework.
 * 
 * It must be used (`use LexorankOrdering;`) inside the model that supports the
 * lexorank ordering, attaching helper methods to it.
 * 
 * The lexorank column must be a varchar, with enough space to store the
 * lexorank. `varchar(32)` is recomended.
 */

namespace App;

use Illuminate\Database\Eloquent\Model;
use function App\Functions\lexorank_between;
use const App\Functions\LEXORANK_SET;

/**
 * @phpstan-require-extends Model
 */
trait LexorankOrdering
{
    #region Configuration

    /**
     * The name of the ordering column.
     * 
     * This column must be varchar.
     * 
     * @return string
     */
    public function getLexorankColumn(): string
    {
        return 'order';
    }

    /**
     * The names of the columns that can scope the ordering. They will be
     * compared using `equals` comparisson.
     * 
     * @return string[]
     */
    public function getLexorankScopeColumns(): array
    {
        return [];
    }

    /**
     * The default ordering when inserting a new records.
     * 
     * Determines if, during the creation event, the `lexorankComputeFirst()` or
     * `lexorankComputeLast()` will be used.
     * 
     * @return 'first'|'last'
     */
    public function getLexorankDefaultInsertOrder(): string
    {
        return 'first';
    }

    /**
     * The set of characters that will be used to generate the lexorank ordering.
     * 
     * The lexorank function already declares the ones bellow:
     * 
     * - `LEXORANK_NUM_SET`: `'0123456789'`;
     * - `LEXORANK_LOWER_ALPHA_SET`: `'abcdefghijklmnopqrstuvwxyz'`;
     * - `LEXORANK_UPPER_ALPHA_SET`: `'ABCDEFGHIJKLMNOPQRSTUVWXYZ'`;
     * - `LEXORANK_FULL_ALPHA_SET`: `'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'`;
     * - `LEXORANK_SET`: `'0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'`.
     * 
     * If declaring one yourself, follow the instructions at the
     * lexorank_between function.
     * 
     * @return string
     */
    public function getLexorankSet(): string
    {
        return LEXORANK_SET;
    }

    #endregion

    public static function bootLexorankOrdering()
    {
        self::creating(static function (self $model) {
            if (isset($model->{$model->getLexorankColumn()}))
                return;

            $model->{$model->getLexorankColumn()} = $model->getLexorankDefaultInsertOrder() === 'last'
                ? $model->lexorankComputeLast()
                : $model->lexorankComputeFirst();
        });
    }

    /**
     * Place the item at the top of the list.
     * 
     * @return string The new lexorank
     */
    public function lexorankPlaceFirst(): string
    {
        $this->{$this->getLexorankColumn()} = $this->lexorankComputeFirst();
        $this->save();

        return $this->{$this->getLexorankColumn()};
    }

    /**
     * Place the item at the bottom of the list.
     * 
     * @return string The new lexorank
     */
    public function lexorankPlaceLast(): string
    {
        $this->{$this->getLexorankColumn()} = $this->lexorankComputeLast();
        $this->save();

        return $this->{$this->getLexorankColumn()};
    }

    /**
     * Place the item above another item.
     * 
     * @param self $item The item that will stay below
     * @return string The new lexorank value
     */
    public function lexorankPlaceAbove(self $item): string
    {
        $this->{$this->getLexorankColumn()} = $this->lexorankComputeAbove($item);
        $this->save();

        return $this->{$this->getLexorankColumn()};
    }

    /**
     * Place the item below another item.
     * 
     * @param self $item The item that will stay above
     * @return string The new lexorank value
     */
    public function lexorankPlaceBelow(self $item): string
    {
        $this->{$this->getLexorankColumn()} = $this->lexorankComputeBelow($item);
        $this->save();

        return $this->{$this->getLexorankColumn()};
    }

    /**
     * Compute the lexorank to place the item at the top of the list.
     * 
     * @return string The lexorank value
     */
    public function lexorankComputeFirst(): string
    {
        return $this->lexorankComputeBelow(null);
    }

    /**
     * Compute the lexorank to place the item at the bottom of the list.
     * 
     * @return string The lexorank value
     */
    public function lexorankComputeLast(): string
    {
        return $this->lexorankComputeAbove(null);
    }

    /**
     * Compute the lexorank to place the item above $item. If $item is null,
     * will act like `lexorankComputeLast()`.
     * 
     * @param ?self $item The item that will stay below
     * @return string The lexorank value
     */
    public function lexorankComputeAbove(?self $item): string
    {
        // Position of variables:
        // ^ $above
        // - $item
        // v $this

        $above = self::query();

        foreach ($this->getLexorankScopeColumns() as $column) {
            if (isset($item->{$column})) {
                $above = $above->where($column, '=', $item->{$column});
            }
        }

        if (isset($item)) {
            $above->where($this->getLexorankColumn(), '<', self::whereKey($item->id)->limit(1)->select($this->getLexorankColumn()));
        }

        $above = $above
            ->orderBy($this->getLexorankColumn(), 'desc')
            ->limit(1)
            ->first([$this->getLexorankColumn()]);

        return lexorank_between(
            $above?->{$this->getLexorankColumn()},
            $item?->{$this->getLexorankColumn()},
            $this->getLexorankSet(),
        );
    }

    /**
     * Compute the lexorank to place the item below $item. If $item is null,
     * will act like `lexorankComputeFirst()`.
     * 
     * @param ?self $item The item that will stay above
     * @return string The lexorank value
     */
    public function lexorankComputeBelow(?self $item): string
    {
        // Position of variables:
        // ^ $this
        // - $item
        // v $below

        $below = self::query();

        foreach ($this->getLexorankScopeColumns() as $column) {
            if (isset($item->{$column})) {
                $below = $below->where($column, '=', $item->{$column});
            }
        }

        if (isset($item)) {
            $below->where($this->getLexorankColumn(), '>=', self::whereKey($item->id)->limit(1)->select($this->getLexorankColumn()));
        }

        $below = $below
            ->orderBy($this->getLexorankColumn(), 'asc')
            ->limit(1)
            ->first([$this->getLexorankColumn()]);

        return lexorank_between(
            $item?->{$this->getLexorankColumn()},
            $below?->{$this->getLexorankColumn()},
            $this->getLexorankSet(),
        );
    }
}