A list of values which can be sorted by dependencies

OrderedList.php

<?php
/**
 * User: Martin Neundorfer
 * Date: 11.03.2018
 * Time: 22:43
 * Vendor: LABOR.digital
 */

namespace Labor\Lists;

class ListException extends \Exception
{
	
}

class CircularDependencyException extends ListException
{
	
}
class MissingDependencyException extends ListException
{
	
}

/**
 * Class DependencyList
 *
 * A list of values which can be sorted by dependencies
 *
 * Heavily inspired by: https://github.com/marcj/topsort.php/blob/master/src/Implementations/ArraySort.php
 *
 * @package Labor\Compiler\Lists\Dependencies
 */
class OrderedList implements \Iterator, \ArrayAccess, \Countable
{
	/**
	 * True if the data has to be sorted
	 * @var bool
	 */
	protected $isDirty = false;
	
	/**
	 * Contains all key of elements which have to be sorted.
	 * If this is empty -> skip the sorting to preserve overhead
	 * @var bool
	 */
	protected $sortableKeys = [];
	
	/**
	 * The internal storage of the data in the list
	 * @var array
	 */
	protected $storage = [];
	
	/**
	 * True if missing dependencies should be ignored
	 * @var bool
	 */
	protected $ignoreMissingDependencies = false;
	
	/**
	 * True if circular dependencies should be ignored
	 * @var bool
	 */
	protected $ignoreCircularDependencies = false;
	
	/**
	 * Returns true if missing dependencies should be ignored
	 * @return bool
	 */
	public function ignoreMissingDependencies(): bool
	{
		return $this->ignoreMissingDependencies;
	}
	
	/**
	 * Sets the state if missing dependencies should be ignored.
	 * When missing dependencies are ignored the sorting will continue as if the dependency wasn't there
	 *
	 * @param bool $ignoreMissingDependencies
	 *
	 * @return OrderedList
	 */
	public function setIgnoreMissingDependencies(bool $ignoreMissingDependencies): OrderedList
	{
		$this->ignoreMissingDependencies = $ignoreMissingDependencies;
		return $this;
	}
	
	/**
	 * Returns true if circular dependencies will be ignored
	 * @return bool
	 */
	public function ignoreCircularDependencies(): bool
	{
		return $this->ignoreCircularDependencies;
	}
	
	/**
	 * Sets the state if circular dependencies should cause an exception or should be handled silently.
	 *
	 * @param bool $ignoreCircularDependencies True: Handle silently False: Throw exception
	 *
	 * @return OrderedList
	 */
	public function setIgnoreCircularDependencies(bool $ignoreCircularDependencies): OrderedList
	{
		$this->ignoreCircularDependencies = $ignoreCircularDependencies;
		return $this;
	}
	
	/**
	 * Clears the current storage and sets the given data as current list data
	 *
	 * @param array $list
	 *
	 * @return OrderedList
	 */
	public function set(array $list): OrderedList
	{
		$this->reset();
		foreach ($list as $k => $v)
			$this->add($k, $v);
		return $this;
	}
	
	/**
	 * Adds a new key => value pair to the list
	 *
	 * @param int|string|mixed      $key      The key of the value to set
	 * @param mixed                 $value    Any value to be set for the key
	 * @param null|int|string|mixed $requires A list of required $keys which will be sorted before this key
	 * @param null|int|string|mixed $before   A list of $keys which should be sorted after this key
	 *
	 * @return OrderedList
	 */
	public function add($key, $value, $requires = null, $before = null): OrderedList
	{
		// Mark as dirty
		$this->isDirty = true;
		
		// Store data
		$preparedKey = $this->prepareKey($key);
		$slot = [
			'key'      => $key,
			'value'    => $value,
			'requires' => $this->prepareDependencyArray($requires),
			'before'   => $this->prepareDependencyArray($before)
		];
		if(!empty($slot['requires']) || !empty($slot['before'])) $this->sortableKeys[$preparedKey] = true;
		$this->storage[$preparedKey] = $slot;
		return $this;
	}
	
	/**
	 * Simply adds a value to the list, will add a numeric index as a key
	 * @param mixed $value Any value to be added to the list
	 *
	 * @return OrderedList
	 */
	public function append($value): OrderedList {
		$c = $this->count();
		while($this->has($c)) $c++;
		return $this->add($this->count(), $value);
	}
	
	/**
	 * Returns either the value of a requested key or the $default value which was given
	 *
	 * @param int|string|mixed $key     The key to retrieve the value for
	 * @param null             $default Default: null An optional default key which is returned if the requested key
	 *                                  was not found
	 *
	 * @return mixed|null
	 */
	public function get($key, $default = null)
	{
		// Check if we know the key
		$key = $this->prepareKey($key);
		if (!isset($this->storage[$key])) return $default;
		
		// Retrieve value
		return $this->storage[$key]['value'];
	}
	
	/**
	 * Removes a given key's from the list
	 *
	 * @param int|string|mixed $key The key of the value to remove from the list
	 *
	 * @return OrderedList
	 */
	public function remove($key): OrderedList
	{
		// Check if we have the key
		$key = $this->prepareKey($key);
		if (!isset($this->storage[$key])) return $this;
		
		// Mark as dirty
		$this->isDirty = true;
		
		// Remove the value
		unset($this->storage[$key]);
		unset($this->sortableKeys[$key]);
		return $this;
	}
	
	/**
	 * Returns true if a given key exists in the list
	 *
	 * @param int|string|mixed $key A key to look for
	 *
	 * @return bool
	 */
	public function has($key): bool
	{
		$key = $this->prepareKey($key);
		return isset($this->storage[$key]);
	}
	
	/**
	 * Replaces a given $oldValue with a $newValue.
	 *
	 * @param mixed $oldValue The value to replace in the list
	 * @param mixed $value The value to replace the old value with
	 * @param mixed $key Can be used to replace the key of the value as well. Note: This might lead to overrides
	 *
	 * @return OrderedList
	 */
	public function replace($oldValue, $value, $key = null): OrderedList {
		$replaceKey = $key !== null;
		$storageFiltered = [];
		foreach($this->storage as $k => $v){
			if($v['value'] !== $oldValue) {
				$storageFiltered[$k] = $v;
				continue;
			}
			if($replaceKey) {
				$k = $this->prepareKey($key);
				$v['key'] = $key;
			}
			$v['value'] = $value;
			$storageFiltered[$k];
		}
		$this->storage = $storageFiltered;
		return $this;
	}
	
	
	/**
	 * Converts the current list data into a simple php array
	 * @return array
	 */
	public function toArray(): array
	{
		$result = [];
		foreach ($this as $k => $v){
			if(!is_string($k) && !is_numeric($k)) $k = is_object($k) ? spl_object_hash($k) : serialize($k);
			$result[$k] = $v;
 		}
			
		return $result;
	}
	
	/**
	 * Returns the number of all currently stored values in the list
	 * @return int
	 */
	public function count(): int
	{
		return count($this->storage);
	}
	
	/**
	 * Clears out the internal storage and resets the list to initial status
	 * @return OrderedList
	 */
	public function reset(): OrderedList
	{
		$this->isDirty = false;
		$this->storage = [];
		$this->sortableKeys = [];
		return $this;
	}
	
	/**
	 * Return the current element
	 * @link  http://php.net/manual/en/iterator.current.php
	 * @return mixed Can return any type.
	 * @since 5.0.0
	 */
	public function current()
	{
		if(empty($this->storage)) return null;
		return current($this->storage)['value'];
	}
	
	/**
	 * Move forward to next element
	 * @link  http://php.net/manual/en/iterator.next.php
	 * @return void Any returned value is ignored.
	 * @since 5.0.0
	 */
	public function next()
	{
		next($this->storage);
	}
	
	/**
	 * Return the key of the current element
	 * @link  http://php.net/manual/en/iterator.key.php
	 * @return mixed scalar on success, or null on failure.
	 * @since 5.0.0
	 */
	public function key()
	{
		if(empty($this->storage)) return null;
		return current($this->storage)['key'];
	}
	
	/**
	 * Checks if current position is valid
	 * @link  http://php.net/manual/en/iterator.valid.php
	 * @return boolean The return value will be casted to boolean and then evaluated.
	 * Returns true on success or false on failure.
	 * @since 5.0.0
	 */
	public function valid()
	{
		return key($this->storage) !== null;
	}
	
	/**
	 * Rewind the Iterator to the first element
	 * @link  http://php.net/manual/en/iterator.rewind.php
	 * @return void Any returned value is ignored.
	 * @since 5.0.0
	 * @throws CircularDependencyException
	 * @throws MissingDependencyException
	 */
	public function rewind()
	{
		// Rewind to first element -> sort the data
		if($this->isDirty) $this->sort();
		reset($this->storage);
	}
	
	/**
	 * Whether a offset exists
	 * @link  http://php.net/manual/en/arrayaccess.offsetexists.php
	 *
	 * @param mixed $offset <p>
	 *                      An offset to check for.
	 *                      </p>
	 *
	 * @return boolean true on success or false on failure.
	 * </p>
	 * <p>
	 * The return value will be casted to boolean if non-boolean was returned.
	 * @since 5.0.0
	 */
	public function offsetExists($offset)
	{
		return $this->has($offset);
	}
	
	/**
	 * Offset to retrieve
	 * @link  http://php.net/manual/en/arrayaccess.offsetget.php
	 *
	 * @param mixed $offset <p>
	 *                      The offset to retrieve.
	 *                      </p>
	 *
	 * @return mixed Can return all value types.
	 * @since 5.0.0
	 */
	public function offsetGet($offset)
	{
		return $this->get($offset);
	}
	
	/**
	 * Offset to set
	 * @link  http://php.net/manual/en/arrayaccess.offsetset.php
	 *
	 * @param mixed $offset <p>
	 *                      The offset to assign the value to.
	 *                      </p>
	 * @param mixed $value  <p>
	 *                      The value to set.
	 *                      </p>
	 *
	 * @return void
	 * @since 5.0.0
	 */
	public function offsetSet($offset, $value)
	{
		$this->add($offset, $value);
	}
	
	/**
	 * Offset to unset
	 * @link  http://php.net/manual/en/arrayaccess.offsetunset.php
	 *
	 * @param mixed $offset <p>
	 *                      The offset to unset.
	 *                      </p>
	 *
	 * @return void
	 * @since 5.0.0
	 */
	public function offsetUnset($offset)
	{
		$this->remove($offset);
	}
	
	/**
	 * Converts every given value into a stringified key
	 *
	 * @param mixed $key Any value to be converted into a key
	 *
	 * @internal
	 * @return string
	 */
	protected function prepareKey($key): string
	{
		// Convert objects into keys
		if (is_object($key))
			return md5('obj'.spl_object_hash($key));
		
		// Serialize keys into md5
		return md5('misc'.serialize($key));
	}
	
	/**
	 * Internal helper to sort the current storage based on the defined dependencies
	 * @internal
	 * @throws CircularDependencyException
	 * @throws MissingDependencyException
	 */
	protected function sort()
	{
		// Mark as clean
		$this->isDirty = false;
		
		// Ignore on empty or single value
		if (empty($this->storage) || empty($this->sortableKeys)) return;
		
		// Build list of real dependencies
		$structure = [];
		foreach ($this->storage as $k => $row)
			$structure[$k] = $row['requires'];
		
		// Inject all "before" requirements into "require" of their target
		foreach ($this->storage as $k => $row)
			foreach ($row['before'] as $bk)
				if (isset($structure[$bk])) $structure[$bk][$k] = $k;
		
		// Run trough structure
		$sorted = [];
		foreach ($structure as $k => $depencencies)
			$this->sortWalker($sorted, $k, $depencencies, $structure);
		
		// Update iterator
		$this->storage = array_replace($sorted, $this->storage);
	}
	
	/**
	 * Internal helper which is used to recursively resolve the dependencies
	 *
	 * @param array  $result       Will contain the ordered result
	 * @param string $key          The current key of the value to sort
	 * @param array  $depencencies The dependencies for the current key
	 * @param array  $structure    The resolved structure as a result of sort()
	 * @param array  $visited      A list of keys which were "visited" or "sorted"
	 * @param array  $parents      A list of parents for the current key -> Used to detect circular dependencies
	 *
	 * @throws CircularDependencyException
	 * @throws MissingDependencyException
	 */
	protected function sortWalker(array &$result, string $key, array $depencencies,
								  array $structure, array &$visited = [], array &$parents = [])
	{
		// Check for circular dependency
		if (isset($parents[$key]))
		{
			// Check if we should ignore circular dependencies
			if($this->ignoreCircularDependencies()){
				return;
			}
			
			// Translate key
			$keyReal = $this->storage[$key]['key'];
			throw new CircularDependencyException('Detected cirlular dependency for: ' . $keyReal . '!');
		}
		
		// Ignore if element was already visited
		if (isset($visited[$key])) return;
		// Mark as visited
		$visited[$key] = true;
		// Mark as parent
		$parents[$key] = true;
		
		// Loop over dependencies
		foreach ($depencencies as $depencencyKey)
		{
			// Check if the dependency exists
			if (isset($structure[$depencencyKey]))
			{
				// Go down deeper
				$_parents = $parents;
				$this->sortWalker($result, $depencencyKey, $structure[$depencencyKey], $structure, $visited, $_parents);
			} else
			{
				// Check if we should ignore missing dependencies
				if ($this->ignoreMissingDependencies())
				{
					continue;
				}
				// Translate key
				$keyReal = $this->storage[$key]['key'];
				throw new MissingDependencyException('One or multiple dependencies are missing for: ' . $keyReal);
			}
		}
		
		// Add to result
		$result[$key] = $key;
	}
	
	/**
	 * Internal helper which is used to convert any given "dependency" array (before, requires)
	 * into an array we can work with.
	 *
	 * @param mixed $array The initial value to convert into a dependency array
	 *
	 * @internal
	 * @return array
	 */
	protected function prepareDependencyArray($array): array
	{
		// Ignore empty
		if (empty($array)) return [];
		
		// Convert into array
		if (!is_array($array) && !$array instanceof \Iterator)
		{
			if (!is_string($array) && !is_int($array))
				throw new \InvalidArgumentException('Invalid dependency definition given!');
			$array = [$array];
		}
		
		// Prepare output
		$output = [];
		
		// Convert values into keys
		foreach ($array as $v)
		{
			$k = $this->prepareKey($v);
			$output[$k] = $k;
		}
		
		// Done
		return $output;
	}
}