Editors Note, February 14th 2022: This project is now ABANDONED and no longer supported or updated.

asherwunk/phabstractic now has lists that sort themselves according to a given user method

Self-Sorting Lists

I’ve written previously about the Restricted List data type.  Self-Sorting Lists inherit from Restricted Lists so that the list can be sure that it only holds values that are comparable using the comparison function.  First, let’s review the structure of a list in the phabstractic library.  Every list implements the ListInterface (github):

namespace Phabstractic\Data\Types\Resource
{
    interface ListInterface extends \Countable {
        
        public function top(); 
        
        public function &topReference();
        
        public function push();
        
        public function pushReference(&$a); 
        
        public function pop();
        
        public function &popReference(); 
        
        public function index($i);
        
        public function &indexReference($i); 
        
        public function count();
        
        public function isEmpty();
        
        public function clear();

        public function getList();
        
    }
    
}

We add and remove elements onto the list using ->push() and ->pop(), and we index into the list using ->index() and ->indexReference().  In our implementation we’re going to have more methods than this, in fact, we inherit from AbstractList (github):

namespace Phabstractic\Data\Types\Resource
{    
    abstract class AbstractList implements ListInterface
    {
        protected $list = array();
        
        public function __construct($data = null) 
        {
            if (is_array($data)) { 
                $this->list = $data; 
            } elseif ($data instanceof AbstractList) { 
                $this->list = $data->getList(); 
            } elseif ( $data ) { 
                $this->list = array($data);
            } else { 
                $this->list = array();
            }
            
        } 
        
        abstract public function top();
        
        abstract public function &topReference();
        
        abstract public function push();
        
        abstract public function pushReference( &$a );
        
        abstract public function pop();
        
        abstract public function &popReference();
        
        abstract public function index($i);
        
        abstract public function &indexReference($i); 
        
        public function count()
        {
            return count($this->list);
        }
        
        public function isEmpty()
        { 
            return empty($this->list); 
        } 
    
        public function clear()
        { 
            $this->list = array();
            return $this;
        }
        
        public function remove($value)
        {
            if ($key = array_search($value, $this->list)) {
                unset($this->list[$key]);
            }
            
            // resets indices
            $this->list = array_merge($this->list, array());
            return $this->list;
        }
        
        public function getList()
        {
            return $this->list;
        }
        
        abstract public function exchange();
         
        abstract public function duplicate();
        
        abstract function roll($i);
    }     
}

For this particular list implementation, it doesn’t really matter if we’re a Stack or a Queue, since we just worry about everything being in order.  Self-sorting lists actually inherit from AbstractRestrictedList in order to ensure proper data types are stored and compared (github):

namespace Phabstractic\Data\Types\Resource
{
    use Phabstractic\Data\Types;
    use Phabstractic\Data\Types\Exception as TypesException;
    use Phabstractic\Features;
    
    abstract class AbstractRestrictedList extends AbstractList
    {
        use Features\ConfigurationTrait;
        
        protected $restrictions = null;
        
        public function getRestrictions()
        {
            return $this->restrictions;
        }
        
        public function __construct(
            $data = null,
            FilterInterface $restrictions = null,
            $options = array()) 
        {
            $this->configure($options);
            
            // If there are no restrictions given, build basic free form restrictions
            // Default doesn't allow Type::TYPED_OBJECT    
            if (!$restrictions) {
                $restrictions = Types\Restrictions::getDefaultRestrictions();
            }
            
            $this->restrictions = $restrictions;
            if ( is_array( $data ) ) {
                // Plain Array
                
                /* Check input values for any illegal types
                   If false, throw error because this is a constructor and can't
                   really return anything. */
                if (!$this->restrictions::checkElements(
                        $data,
                        $this->restrictions,
                        $this->conf->strict)) {
                    throw new TypesException\InvalidArgumentException(
                        'Phabstractic\\Data\\Types\\Resource\\' .
                        'AbstractRestrictedList->__construct: Illegal Value');
                }
            } else if ($data instanceof AbstractList) {
                // Phabstractic\Data\Types\Resource\AbstractList
                    
                /* Check input values for any illegal types
                   If false, throw error because this is a constructor and can't
                   really return anything. */
                if (!$this->restrictions::checkElements(
                        $data->getList(),
                        $this->restrictions,
                        $this->conf->strict)) {
                    throw new TypesException\InvalidArgumentException(
                        'Phabstractic\\Data\\Types\\Resource\\' .
                        'AbstractRestrictedList->__construct: Illegal Value');
                }
            } else if ($data) {
                // A scalar value
                
                /* Check input values for any illegal types
                   If false, throw error because this is a constructor and can't
                   really return nothing */
                if (!$this->restrictions::checkElements(
                        array($data),
                        $this->restrictions,
                        $this->conf->strict)) {
                    throw new TypesException\InvalidArgumentException(
                        'Phabstractic\\Data\\Types\\Resource\\' .
                        'AbstractRestrictedList->__construct: Illegal Value');
                }
            }
            
            parent::__construct($data);
        }
        
        protected function check()
        {
            if (!$this->restrictions::checkElements(
                    func_get_args(),
                    $this->restrictions,
                    $this->conf->strict)) {
                if ($this->conf->strict) {
                    throw new TypesException\InvalidArgumentException(
                        'Phabstractic\\Data\\Types\\Resource\\' .
                        'AbstractRestrictedList->check: Value not in ' .
                        'restrictions' );
                } else {
                    return false;
                }
                
            }
            
            return true;
        }
        
        public function push()
        {
            $args = func_get_args();
            return call_user_func_array(array($this, 'check'), $args);
        }
        
        public function pushReference(&$a)
        {
            return $this->check($a);
        }
    }
}

Remember that these implemented abstract methods are meant to be called using parent:: to check certain values, but the actual addition of the data to the list should be done in the implementation.

The thing about a self-sorting list is that you’d expect to sort the list every time someone adds something to the list, however, though that makes sense intuitively it doesn’t make as much sense practically.  What happens if something outside the list edits the data in the list?  This can happen if we allow the data in the list to be set using a reference, which we do.  So if we change the value of a referenced piece of data in the list we might be out of order.  There’s no way to monitor the contents of the list variables so that it updates on a change, that would be odd.

The solution?  Sort the list every time it is requested and make sure you can only request the list through the object (thus ensuring the sorting code can be done).

As well, a self-sorting list has to have some way that it knows how to put things in order.  As well, just because a list has restrictions, doesn’t mean that the list may only have one data type in it.  We’ve demonstrated in the past that a restricted list can specify multiple classes or data types.

What makes this class really useful is that you can specify the method by which things are sorted.  You do this by implementing the compare function in the implementation of the class.  We set all this up, the automatic sorting, and the placeholder for the sorting code in AbstractSortedList (github):

namespace Phabstractic\Data\Types\Resource
{
    use Phabstractic\Features;
    
    abstract class AbstractSortedList extends AbstractRestrictedList
    {
        use Features\ConfigurationTrait;
        
        public function __construct(
            $data = null,
            FilterInterface $restrictions = null,
            $options = array()
        ) {
            $this->configure($options);
            
            parent::__construct($data, $restrictions, $options);
            
            // Auto sort according to comparison function provided by child
            usort($this->list, array($this, 'cmp'));
        }
    
        /**
         * The comparison function.
         * 
         * Returns -1 if $l is 'less than'/before $r
         *         0  if $l and $r are equal
         *         +1 if $l is 'greater than'/after $r
         */
        abstract protected function cmp($l, $r);
        
        public function top()
        {
            // Auto sort according to comparison function provided by child
            usort($this->list, array($this, 'cmp'));
            
        }
        
        public function &topReference()
        {
            // Auto sort according to comparison function provided by child
            usort($this->list, array($this, 'cmp'));
            
        }
        
        public function index($i)
        {
            // Auto sort according to comparison function provided by child
            usort($this->list, array($this, 'cmp'));
            
        }
        
        public function &indexReference($i)
        {
            // Auto sort according to comparison function provided by child
            usort($this->list, array($this, 'cmp'));
            
        }
        
        public function pop()
        {
            // Auto sort according to comparison function provided by child
            usort($this->list, array($this, 'cmp'));
            
        }
        
        public function &popReference()
        {
            // Auto sort according to comparison function provided by child
            usort($this->list, array($this, 'cmp'));
            
        }
        
        public function getList()
        {
            // Auto sort according to comparison function provided by child
            usort($this->list, array($this, 'cmp'));
            
            return $this->list;
        }
    }
}

Much like the Restricted List abstract class (above) most of these methods that are implemented in the abstract class are meant to be called through parent::  Note that these methods are for ‘getting’ the list, not when someone puts things on the list, otherwise, we’d also call parent:: to access the RestrictedList functionality.

Lexicographic List

An example self-sorting list is a Lexicographic List.  The idea behind a lexicographic list is that it is a list of strings sorted lexicographically (as PHP puts it).  Pretty much, this means, that they are sorted alphabetically.  The comparison function is very simple:

protected function cmp( $l, $r )
{
    // check against restrictions, v3
    if (!$this->restrictions->isAllowed(Type\getValueType($l)) ||
            !$this->restrictions->isAllowed(Type\getValueType($r))) {
        throw new TypesException\InvalidArgumentException(
            'Phabstractic\\Data\\Types\\LexicographicalList->cmp: ' .
            'Comparison types not allowed');
    }
    
    // version 2:
    /* if (!is_string($l) || !is_string($r)) {
        throw new Exception\InvalidArgumentException(
            'LexicographicalList->cmp: Comparison must be string');
    } */
    
    if ($l > $r) {
        return 1;
    } else if ($l < $r) {
        return -1;
    } else {
        return 0;
    }
    
}

Essentially it is a wrapper around the built-in PHP comparison for strings.  We can rest assured that they’re all strings because of the constructor:

public function __construct(
    $data = null,
    TypesResource\FilterInterface $restrictions = null,
    $options = array()
) {
    $this->configure($options);
    
    if (!$restrictions) {
       $this->restrictions = new Restrictions(array(Type::BASIC_STRING));
    } else {
        $this->restrictions = $restrictions;
    }
    
    parent::__construct($data, $this->restrictions, $options);
}

Note here that we do allow other types to be substituted in.  This works as long as the type of data substituted can be compared using the built-in PHP comparison functions as above.

One thing we MUST note about an implementation such as LexicographicList is that if we do implement \ArrayAccess we MUST include the sorting functionality manually:

public function offsetSet($key, $value)
{
    if (is_numeric($key)) {
        if ($this->offsetExists($key)) {
            if (!$this->check($value)) {
                if ($this->conf->strict) {
                    throw new TypesException\InvalidArgumentException(
                        'Phabstractic\\Data\\Types\\LexicographicList->offsetSet: ' .
                        'Value not in restrictions' );
                } else {
                    return null;
                }
            }
            // encapsulate indexing logic in indexing function
            $r = &$this->indexReference($key);
            $r = $value;
            usort($this->list, array($this, 'cmp'));
            return count($this->list);
        }
        
    }
    
    // If the key is empty: stack[], push value
    if (!$key) {
        return $this->push($value);
    }
    
    // At this point, we should have returned, or something is wrong
    // Such as treating the stack as an associative variable
    
    if ($this->conf->strict) {
        throw new TypesException\RangeException(
            'Phabstractic\\Data\\Types\\LexicographicList->offsetSet: ' .
            'offsetSet key ' . $key . ' out of range.');
    }
    
}

public function offsetGet($key) {
    usort($this->list, array($this, 'cmp'));
    
    if (!is_numeric($key)) {
        if ($this->conf->strict) {
            throw new Exception\InvalidArgumentException(
                'Phabstractic\\Data\\Types\\LexicographicList->offsetGet: ' .
                'Invalid argument key');
        } else {
            return new None();
        }
        
    }
    
    // Can return Types\Null()
    return $this->index($key);
} 

public function offsetUnset($key) {
    usort($this->list, array($this, 'cmp'));
    
    if (!is_numeric($key)) {
        return false;
    } else {
        unset($this->list[$key]);
        // reset keys
        $this->list = array_merge($this->list, array());
        usort($this->list, array($this, 'cmp'));
        return true;
    }
    
    return false;
} 

public function offsetExists( $key ) {
    usort($this->list, array($this, 'cmp'));
    
    if (!is_numeric($key)) {
        return false;
    } else {
        return isset($this->list[$key]);
    }
}

You can see the entire LexicographicList on github if you want to see the full implementation.

Usage

AbstractSortedList is meant to be implemented, and can’t actually be instantiated on its own.  A simple and straightforward implementation is LexicographicList as shown above.  To use the LexicographicList you simply use it like any other list:

<?php

use Phabstractic\Data\Types;

$lexList = new Types\LexicographicList();

$lexList->push('one');
$lexList->push('two');
$lexList->push('three');

But here’s where things get a little tricky, when we retrieve the list it’s different than how we started:

<?php

var_dump($lexList->getList());

// array('one', 'three', 'two');

You’ll note that three comes before two.  This is because ‘three’ comes before the word ‘two’ alphabetically.  But what happens if we retrieve a reference and then change the data?  Turns out, because we sort by request, that doesn’t matter:

<?php

$ref = &$lexList->indexReference(1);

$ref = 'modified';

var_dump($lexList->getList());

// array('modified', 'one', 'two');

Conclusion

Self-sorting lists can be very handy.  For instance, we could easily implement a priority queue by utilizing a sorted list, and that’s something we’re going to do, simply using the comparison method on competing priorities.  PriorityQueue’s are usually implemented with a heap and a binary tree and so on, but I thought it would be easier to implement using a self-sorting array.  Self-sorting arrays make putting everything in order in a messaging queue fairly simple.

This is part of the Phabstractic Library.

photo credit: Day 092/366 – To Do List via photopin (license)

Asher Wolfstein

Metaverse Resident

About the Author

A metaverse resident, you can find me on Second Life (kadar.talbot) and other online platforms. I write about my digital life, my musings, and my projects as a programmer, webmaster, artist, and game designer. (exist (be wunk) (use rational imagination) (import artist coder maker furry) (conditional (if (eq you asshole) (me (block you))))

View Articles