chdemko / php-sorted-collections

examples/SubSet.php

Spacing +4 added lines, -4 removed lines

@@ -14,7 +14,7 @@ 
  * This file is part of the php-sorted-collections package https://github.com/chdemko/php-sorted-collections
  */
 
-require __DIR__ . '/../vendor/autoload.php';
+require __DIR__.'/../vendor/autoload.php';
 
 use chdemko\SortedCollection\TreeSet;
 use chdemko\SortedCollection\ReversedSet;
@@ -25,12 +25,12 @@ 
 $sub = SubSet::create($reversed, 7, 2);
 
 // Print [7,6,5,4,3]
-echo $sub . PHP_EOL;
+echo $sub.PHP_EOL;
 
 // Print [7,6,5,3]
 unset($set[4]);
-echo $sub . PHP_EOL;
+echo $sub.PHP_EOL;
 
 // Print [9,8,7,6,5,3]
 unset($sub->from);
-echo $sub . PHP_EOL;
+echo $sub.PHP_EOL;

examples/ReversedSet.php

Spacing +3 added lines, -3 removed lines

@@ -14,7 +14,7 @@ 
  * This file is part of the php-sorted-collections package https://github.com/chdemko/php-sorted-collections
  */
 
-require __DIR__ . '/../vendor/autoload.php';
+require __DIR__.'/../vendor/autoload.php';
 
 use chdemko\SortedCollection\TreeSet;
 use chdemko\SortedCollection\ReversedSet;
@@ -23,8 +23,8 @@ 
 $reversed = ReversedSet::create($set);
 
 // Print [9,8,7,6,5,4,3,2,1,0]
-echo $reversed . PHP_EOL;
+echo $reversed.PHP_EOL;
 
 // Print [8,7,6,5,4,3,2,1,0]
 unset($set[9]);
-echo $reversed . PHP_EOL;
+echo $reversed.PHP_EOL;

examples/ReversedMap.php

Spacing +3 added lines, -3 removed lines

@@ -14,7 +14,7 @@ 
  * This file is part of the php-sorted-collections package https://github.com/chdemko/php-sorted-collections
  */
 
-require __DIR__ . '/../vendor/autoload.php';
+require __DIR__.'/../vendor/autoload.php';
 
 use chdemko\SortedCollection\TreeMap;
 use chdemko\SortedCollection\ReversedMap;
@@ -23,8 +23,8 @@ 
 $reversed = ReversedMap::create($tree);
 
 // Print {"9":9,"8":8,"7":7,"6":6,"5":5,"4":4,"3":3,"2":2,"1":1,"0":0}
-echo $reversed . PHP_EOL;
+echo $reversed.PHP_EOL;
 
 // Print {"8":8,"7":7,"6":6,"5":5,"4":4,"3":3,"2":2,"1":1,"0":0}
 unset($tree[9]);
-echo $reversed . PHP_EOL;
+echo $reversed.PHP_EOL;

examples/SubMap.php

Spacing +4 added lines, -4 removed lines

@@ -14,7 +14,7 @@ 
  * This file is part of the php-sorted-collections package https://github.com/chdemko/php-sorted-collections
  */
 
-require __DIR__ . '/../vendor/autoload.php';
+require __DIR__.'/../vendor/autoload.php';
 
 use chdemko\SortedCollection\TreeMap;
 use chdemko\SortedCollection\ReversedMap;
@@ -25,12 +25,12 @@ 
 $sub = SubMap::create($reversed, 7, 2);
 
 // Print {"7":7,"6":6,"5":5,"4":4,"3":3}
-echo $sub . PHP_EOL;
+echo $sub.PHP_EOL;
 
 // Print {"7":7,"6":6,"5":5,"3":3}
 unset($tree[4]);
-echo $sub . PHP_EOL;
+echo $sub.PHP_EOL;
 
 // Print {"9":9,"8":8,"7":7,"6":6,"5":5,"3":3}
 unset($sub->fromKey);
-echo $sub . PHP_EOL;
+echo $sub.PHP_EOL;

src/SortedCollection/SubSet.php

Indentation +276 added lines, -276 removed lines

@@ -34,294 +34,294 @@
  */
 class SubSet extends AbstractSet
 {
-    /**
-     * When the from or to value is unused
-     *
-     * @since 1.0.0
-     */
-    private const UNUSED = 0;
+	/**
+	 * When the from or to value is unused
+	 *
+	 * @since 1.0.0
+	 */
+	private const UNUSED = 0;
 
-    /**
-     * When the from or to value is inclusive
-     *
-     * @since 1.0.0
-     */
-    private const INCLUSIVE = 1;
+	/**
+	 * When the from or to value is inclusive
+	 *
+	 * @since 1.0.0
+	 */
+	private const INCLUSIVE = 1;
 
-    /**
-     * When the from or to value is exclusive
-     *
-     * @since 1.0.0
-     */
-    private const EXCLUSIVE = 2;
+	/**
+	 * When the from or to value is exclusive
+	 *
+	 * @since 1.0.0
+	 */
+	private const EXCLUSIVE = 2;
 
-    /**
-     * @var SortedSet  Internal set
-     *
-     * @since 1.0.0
-     */
-    private $set;
+	/**
+	 * @var SortedSet  Internal set
+	 *
+	 * @since 1.0.0
+	 */
+	private $set;
 
-    /**
-     * Magic get method
-     *
-     * @param string $property The property
-     *
-     * @return mixed The value associated to the property
-     *
-     * @since 1.0.0
-     */
-    public function __get($property)
-    {
-        switch ($property) {
-            case 'from':
-                return $this->getMap()->fromKey;
-            case 'to':
-                return $this->getMap()->toKey;
-            case 'fromInclusive':
-                return $this->getMap()->fromInclusive;
-            case 'toInclusive':
-                return $this->getMap()->toInclusive;
-            case 'set':
-                return $this->set;
-            default:
-                return parent::__get($property);
-        }
-    }
+	/**
+	 * Magic get method
+	 *
+	 * @param string $property The property
+	 *
+	 * @return mixed The value associated to the property
+	 *
+	 * @since 1.0.0
+	 */
+	public function __get($property)
+	{
+		switch ($property) {
+			case 'from':
+				return $this->getMap()->fromKey;
+			case 'to':
+				return $this->getMap()->toKey;
+			case 'fromInclusive':
+				return $this->getMap()->fromInclusive;
+			case 'toInclusive':
+				return $this->getMap()->toInclusive;
+			case 'set':
+				return $this->set;
+			default:
+				return parent::__get($property);
+		}
+	}
 
-    /**
-     * Magic set method
-     *
-     * @param string $property The property
-     * @param mixed  $value    The new value
-     *
-     * @throws \RuntimeException If the property does not exist
-     *
-     * @return void
-     *
-     * @since 1.0.0
-     */
-    public function __set($property, $value)
-    {
-        switch ($property) {
-            case 'from':
-                $this->getMap()->fromKey = $value;
-                break;
-            case 'to':
-                $this->getMap()->toKey = $value;
-                break;
-            case 'fromInclusive':
-                $this->getMap()->fromInclusive = $value;
-                break;
-            case 'toInclusive':
-                $this->getMap()->toInclusive = $value;
-                break;
-            default:
-                throw new \RuntimeException('Undefined property');
-        }
-    }
+	/**
+	 * Magic set method
+	 *
+	 * @param string $property The property
+	 * @param mixed  $value    The new value
+	 *
+	 * @throws \RuntimeException If the property does not exist
+	 *
+	 * @return void
+	 *
+	 * @since 1.0.0
+	 */
+	public function __set($property, $value)
+	{
+		switch ($property) {
+			case 'from':
+				$this->getMap()->fromKey = $value;
+				break;
+			case 'to':
+				$this->getMap()->toKey = $value;
+				break;
+			case 'fromInclusive':
+				$this->getMap()->fromInclusive = $value;
+				break;
+			case 'toInclusive':
+				$this->getMap()->toInclusive = $value;
+				break;
+			default:
+				throw new \RuntimeException('Undefined property');
+		}
+	}
 
-    /**
-     * Magic unset method
-     *
-     * @param string $property The property
-     *
-     * @throws \RuntimeException If the property does not exist
-     *
-     * @return void
-     *
-     * @since 1.0.0
-     */
-    public function __unset($property)
-    {
-        switch ($property) {
-            case 'from':
-                unset($this->getMap()->fromKey);
-                break;
-            case 'to':
-                unset($this->getMap()->toKey);
-                break;
-            case 'fromInclusive':
-                unset($this->getMap()->fromInclusive);
-                break;
-            case 'toInclusive':
-                unset($this->getMap()->toInclusive);
-                break;
-            default:
-                throw new \RuntimeException('Undefined property');
-        }
-    }
+	/**
+	 * Magic unset method
+	 *
+	 * @param string $property The property
+	 *
+	 * @throws \RuntimeException If the property does not exist
+	 *
+	 * @return void
+	 *
+	 * @since 1.0.0
+	 */
+	public function __unset($property)
+	{
+		switch ($property) {
+			case 'from':
+				unset($this->getMap()->fromKey);
+				break;
+			case 'to':
+				unset($this->getMap()->toKey);
+				break;
+			case 'fromInclusive':
+				unset($this->getMap()->fromInclusive);
+				break;
+			case 'toInclusive':
+				unset($this->getMap()->toInclusive);
+				break;
+			default:
+				throw new \RuntimeException('Undefined property');
+		}
+	}
 
-    /**
-     * Magic isset method
-     *
-     * @param string $property The property
-     *
-     * @return boolean
-     *
-     * @since 1.0.0
-     */
-    public function __isset($property)
-    {
-        switch ($property) {
-            case 'from':
-                return isset($this->getMap()->fromKey);
-            case 'to':
-                return isset($this->getMap()->toKey);
-            case 'fromInclusive':
-                return isset($this->getMap()->fromInclusive);
-            case 'toInclusive':
-                return isset($this->getMap()->toInclusive);
-            default:
-                return false;
-        }
-    }
+	/**
+	 * Magic isset method
+	 *
+	 * @param string $property The property
+	 *
+	 * @return boolean
+	 *
+	 * @since 1.0.0
+	 */
+	public function __isset($property)
+	{
+		switch ($property) {
+			case 'from':
+				return isset($this->getMap()->fromKey);
+			case 'to':
+				return isset($this->getMap()->toKey);
+			case 'fromInclusive':
+				return isset($this->getMap()->fromInclusive);
+			case 'toInclusive':
+				return isset($this->getMap()->toInclusive);
+			default:
+				return false;
+		}
+	}
 
-    /**
-     * Constructor
-     *
-     * @param SortedSet $set        Internal set
-     * @param mixed     $from       The from element
-     * @param integer   $fromOption The option for from (SubSet::UNUSED, SubSet::INCLUSIVE or SubSet::EXCLUSIVE)
-     * @param mixed     $to         The to element
-     * @param integer   $toOption   The option for to (SubSet::UNUSED, SubSet::INCLUSIVE or SubSet::EXCLUSIVE)
-     *
-     * @since 1.0.0
-     */
-    protected function __construct(SortedSet $set, $from, $fromOption, $to, $toOption)
-    {
-        if ($fromOption == self::UNUSED) {
-            if ($toOption == self::UNUSED) {
-                $this->setMap(SubMap::view($set->getMap()));
-            } else {
-                $this->setMap(SubMap::head($set->getMap(), $to, $toOption == self::INCLUSIVE));
-            }
-        } elseif ($toOption == self::UNUSED) {
-            $this->setMap(SubMap::tail($set->getMap(), $from, $fromOption == self::INCLUSIVE));
-        } else {
-            $this->setMap(
-                SubMap::create($set->getMap(), $from, $to, $fromOption == self::INCLUSIVE, $toOption == self::INCLUSIVE)
-            );
-        }
+	/**
+	 * Constructor
+	 *
+	 * @param SortedSet $set        Internal set
+	 * @param mixed     $from       The from element
+	 * @param integer   $fromOption The option for from (SubSet::UNUSED, SubSet::INCLUSIVE or SubSet::EXCLUSIVE)
+	 * @param mixed     $to         The to element
+	 * @param integer   $toOption   The option for to (SubSet::UNUSED, SubSet::INCLUSIVE or SubSet::EXCLUSIVE)
+	 *
+	 * @since 1.0.0
+	 */
+	protected function __construct(SortedSet $set, $from, $fromOption, $to, $toOption)
+	{
+		if ($fromOption == self::UNUSED) {
+			if ($toOption == self::UNUSED) {
+				$this->setMap(SubMap::view($set->getMap()));
+			} else {
+				$this->setMap(SubMap::head($set->getMap(), $to, $toOption == self::INCLUSIVE));
+			}
+		} elseif ($toOption == self::UNUSED) {
+			$this->setMap(SubMap::tail($set->getMap(), $from, $fromOption == self::INCLUSIVE));
+		} else {
+			$this->setMap(
+				SubMap::create($set->getMap(), $from, $to, $fromOption == self::INCLUSIVE, $toOption == self::INCLUSIVE)
+			);
+		}
 
-        $this->set = $set;
-    }
+		$this->set = $set;
+	}
 
-    /**
-     * Create
-     *
-     * @param SortedSet $set           Internal set
-     * @param mixed     $from          The from element
-     * @param mixed     $to            The to element
-     * @param boolean   $fromInclusive The inclusive flag for from
-     * @param boolean   $toInclusive   The inclusive flag for to
-     *
-     * @return SubSet A new sub set
-     *
-     * @since 1.0.0
-     */
-    public static function create(SortedSet $set, $from, $to, $fromInclusive = true, $toInclusive = false)
-    {
-        return new static(
-            $set,
-            $from,
-            $fromInclusive ? self::INCLUSIVE : self::EXCLUSIVE,
-            $to,
-            $toInclusive ? self::INCLUSIVE : self::EXCLUSIVE
-        );
-    }
+	/**
+	 * Create
+	 *
+	 * @param SortedSet $set           Internal set
+	 * @param mixed     $from          The from element
+	 * @param mixed     $to            The to element
+	 * @param boolean   $fromInclusive The inclusive flag for from
+	 * @param boolean   $toInclusive   The inclusive flag for to
+	 *
+	 * @return SubSet A new sub set
+	 *
+	 * @since 1.0.0
+	 */
+	public static function create(SortedSet $set, $from, $to, $fromInclusive = true, $toInclusive = false)
+	{
+		return new static(
+			$set,
+			$from,
+			$fromInclusive ? self::INCLUSIVE : self::EXCLUSIVE,
+			$to,
+			$toInclusive ? self::INCLUSIVE : self::EXCLUSIVE
+		);
+	}
 
-    /**
-     * Head
-     *
-     * @param SortedSet $set         Internal set
-     * @param mixed     $to          The to element
-     * @param boolean   $toInclusive The inclusive flag for to
-     *
-     * @return SubSet A new head set
-     *
-     * @since 1.0.0
-     */
-    public static function head(SortedSet $set, $to, $toInclusive = false)
-    {
-        return new static($set, null, self::UNUSED, $to, $toInclusive ? self::INCLUSIVE : self::EXCLUSIVE);
-    }
+	/**
+	 * Head
+	 *
+	 * @param SortedSet $set         Internal set
+	 * @param mixed     $to          The to element
+	 * @param boolean   $toInclusive The inclusive flag for to
+	 *
+	 * @return SubSet A new head set
+	 *
+	 * @since 1.0.0
+	 */
+	public static function head(SortedSet $set, $to, $toInclusive = false)
+	{
+		return new static($set, null, self::UNUSED, $to, $toInclusive ? self::INCLUSIVE : self::EXCLUSIVE);
+	}
 
-    /**
-     * Tail
-     *
-     * @param SortedSet $set           Internal set
-     * @param mixed     $from          The from element
-     * @param boolean   $fromInclusive The inclusive flag for from
-     *
-     * @return SubSet A new tail set
-     *
-     * @since 1.0.0
-     */
-    public static function tail(SortedSet $set, $from, $fromInclusive = true)
-    {
-        return new static($set, $from, $fromInclusive ? self::INCLUSIVE : self::EXCLUSIVE, null, self::UNUSED);
-    }
+	/**
+	 * Tail
+	 *
+	 * @param SortedSet $set           Internal set
+	 * @param mixed     $from          The from element
+	 * @param boolean   $fromInclusive The inclusive flag for from
+	 *
+	 * @return SubSet A new tail set
+	 *
+	 * @since 1.0.0
+	 */
+	public static function tail(SortedSet $set, $from, $fromInclusive = true)
+	{
+		return new static($set, $from, $fromInclusive ? self::INCLUSIVE : self::EXCLUSIVE, null, self::UNUSED);
+	}
 
-    /**
-     * View
-     *
-     * @param SortedSet $set Internal set
-     *
-     * @return SubSet A new sub set
-     *
-     * @since 1.0.0
-     */
-    public static function view(SortedSet $set)
-    {
-        return new static($set, null, self::UNUSED, null, self::UNUSED);
-    }
+	/**
+	 * View
+	 *
+	 * @param SortedSet $set Internal set
+	 *
+	 * @return SubSet A new sub set
+	 *
+	 * @since 1.0.0
+	 */
+	public static function view(SortedSet $set)
+	{
+		return new static($set, null, self::UNUSED, null, self::UNUSED);
+	}
 
-    /**
-     * Serialize the object
-     *
-     * @return array Array of values
-     *
-     * @since 1.0.0
-     */
-    public function jsonSerialize()
-    {
-        if (isset($this->from)) {
-            if (isset($this->to)) {
-                return array(
-                 'SubSet' => array(
-                  'set' => $this->set->jsonSerialize(),
-                  'from' => $this->from,
-                  'fromInclusive' => $this->fromInclusive,
-                  'to' => $this->to,
-                  'toInclusive' => $this->toInclusive,
-                 )
-                );
-            } else {
-                return array(
-                'TailSet' => array(
-                'set' => $this->set->jsonSerialize(),
-                'from' => $this->from,
-                'fromInclusive' => $this->fromInclusive,
-                )
-                );
-            }
-        } else {
-            if (isset($this->to)) {
-                return array(
-                'HeadSet' => array(
-                'set' => $this->set->jsonSerialize(),
-                'to' => $this->to,
-                'toInclusive' => $this->toInclusive,
-                )
-                );
-            } else {
-                return array(
-                'ViewSet' => array(
-                'set' => $this->set->jsonSerialize(),
-                )
-                );
-            }
-        }
-    }
+	/**
+	 * Serialize the object
+	 *
+	 * @return array Array of values
+	 *
+	 * @since 1.0.0
+	 */
+	public function jsonSerialize()
+	{
+		if (isset($this->from)) {
+			if (isset($this->to)) {
+				return array(
+				 'SubSet' => array(
+				  'set' => $this->set->jsonSerialize(),
+				  'from' => $this->from,
+				  'fromInclusive' => $this->fromInclusive,
+				  'to' => $this->to,
+				  'toInclusive' => $this->toInclusive,
+				 )
+				);
+			} else {
+				return array(
+				'TailSet' => array(
+				'set' => $this->set->jsonSerialize(),
+				'from' => $this->from,
+				'fromInclusive' => $this->fromInclusive,
+				)
+				);
+			}
+		} else {
+			if (isset($this->to)) {
+				return array(
+				'HeadSet' => array(
+				'set' => $this->set->jsonSerialize(),
+				'to' => $this->to,
+				'toInclusive' => $this->toInclusive,
+				)
+				);
+			} else {
+				return array(
+				'ViewSet' => array(
+				'set' => $this->set->jsonSerialize(),
+				)
+				);
+			}
+		}
+	}
 }

src/SortedCollection/TreeSet.php

Indentation +137 added lines, -137 removed lines

@@ -29,141 +29,141 @@
  */
 class TreeSet extends AbstractSet
 {
-    /**
-     * Constructor
-     *
-     * @param callable $comparator Comparison function
-     *
-     * @since 1.0.0
-     */
-    protected function __construct($comparator = null)
-    {
-        $this->setMap(TreeMap::create($comparator));
-    }
-
-    /**
-     * Create
-     *
-     * @param callable $comparator Comparison function
-     *
-     * @return TreeSet A new TreeSet
-     *
-     * @since 1.0.0
-     */
-    public static function create($comparator = null)
-    {
-        return new static($comparator);
-    }
-
-    /**
-     * Put values in the set
-     *
-     * @param \Traversable $traversable Values to put in the set
-     *
-     * @return TreeSet $this for chaining
-     *
-     * @since 1.0.0
-     */
-    public function put($traversable = array())
-    {
-        foreach ($traversable as $value) {
-            $this[$value] = true;
-        }
-
-        return $this;
-    }
-
-    /**
-     * Clear the set
-     *
-     * @return TreeSet $this for chaining
-     *
-     * @since 1.0.0
-     */
-    public function clear()
-    {
-        $this->getMap()->clear();
-
-        return $this;
-    }
-
-    /**
-     * Initialise the set
-     *
-     * @param \Traversable $traversable Values to initialise the set
-     *
-     * @return TreeSet $this for chaining
-     *
-     * @since 1.0.0
-     */
-    public function initialise($traversable = array())
-    {
-        return $this->clear()->put($traversable);
-    }
-
-    /**
-     * Clone the set
-     *
-     * @return void
-     *
-     * @since 1.0.0
-     */
-    public function __clone()
-    {
-        $this->setMap(clone $this->getMap());
-    }
-
-    /**
-     * Set the value for an element
-     *
-     * @param mixed $element The element
-     * @param mixed $value   The value
-     *
-     * @return void
-     *
-     * @since 1.0.0
-     */
-    public function offsetSet($element, $value)
-    {
-        $map = $this->getMap();
-
-        if ($value) {
-            $map[$element] = true;
-        } else {
-            unset($map[$element]);
-        }
-    }
-
-    /**
-     * Serialize the object
-     *
-     * @return array Array of values
-     *
-     * @since 1.0.0
-     */
-    public function jsonSerialize()
-    {
-        $array = array();
-
-        foreach ($this as $value) {
-            $array[] = $value;
-        }
-
-        return array('TreeSet' => $array);
-    }
-
-    /**
-     * Unset the existence of an element
-     *
-     * @param mixed $element The element
-     *
-     * @return void
-     *
-     * @since 1.0.0
-     */
-    public function offsetUnset($element)
-    {
-        $map = $this->getMap();
-        unset($map[$element]);
-    }
+	/**
+	 * Constructor
+	 *
+	 * @param callable $comparator Comparison function
+	 *
+	 * @since 1.0.0
+	 */
+	protected function __construct($comparator = null)
+	{
+		$this->setMap(TreeMap::create($comparator));
+	}
+
+	/**
+	 * Create
+	 *
+	 * @param callable $comparator Comparison function
+	 *
+	 * @return TreeSet A new TreeSet
+	 *
+	 * @since 1.0.0
+	 */
+	public static function create($comparator = null)
+	{
+		return new static($comparator);
+	}
+
+	/**
+	 * Put values in the set
+	 *
+	 * @param \Traversable $traversable Values to put in the set
+	 *
+	 * @return TreeSet $this for chaining
+	 *
+	 * @since 1.0.0
+	 */
+	public function put($traversable = array())
+	{
+		foreach ($traversable as $value) {
+			$this[$value] = true;
+		}
+
+		return $this;
+	}
+
+	/**
+	 * Clear the set
+	 *
+	 * @return TreeSet $this for chaining
+	 *
+	 * @since 1.0.0
+	 */
+	public function clear()
+	{
+		$this->getMap()->clear();
+
+		return $this;
+	}
+
+	/**
+	 * Initialise the set
+	 *
+	 * @param \Traversable $traversable Values to initialise the set
+	 *
+	 * @return TreeSet $this for chaining
+	 *
+	 * @since 1.0.0
+	 */
+	public function initialise($traversable = array())
+	{
+		return $this->clear()->put($traversable);
+	}
+
+	/**
+	 * Clone the set
+	 *
+	 * @return void
+	 *
+	 * @since 1.0.0
+	 */
+	public function __clone()
+	{
+		$this->setMap(clone $this->getMap());
+	}
+
+	/**
+	 * Set the value for an element
+	 *
+	 * @param mixed $element The element
+	 * @param mixed $value   The value
+	 *
+	 * @return void
+	 *
+	 * @since 1.0.0
+	 */
+	public function offsetSet($element, $value)
+	{
+		$map = $this->getMap();
+
+		if ($value) {
+			$map[$element] = true;
+		} else {
+			unset($map[$element]);
+		}
+	}
+
+	/**
+	 * Serialize the object
+	 *
+	 * @return array Array of values
+	 *
+	 * @since 1.0.0
+	 */
+	public function jsonSerialize()
+	{
+		$array = array();
+
+		foreach ($this as $value) {
+			$array[] = $value;
+		}
+
+		return array('TreeSet' => $array);
+	}
+
+	/**
+	 * Unset the existence of an element
+	 *
+	 * @param mixed $element The element
+	 *
+	 * @return void
+	 *
+	 * @since 1.0.0
+	 */
+	public function offsetUnset($element)
+	{
+		$map = $this->getMap();
+		unset($map[$element]);
+	}
 }

src/SortedCollection/AbstractMap.php

Indentation +366 added lines, -366 removed lines

@@ -35,395 +35,395 @@
  */
 abstract class AbstractMap implements SortedMap
 {
-    /**
-     * Magic get method
-     *
-     * @param string $property The property
-     *
-     * @throws \RuntimeException If the property does not exist
-     *
-     * @return mixed The value associated to the property
-     *
-     * @since 1.0.0
-     */
-    public function __get($property)
-    {
-        switch ($property) {
-            case 'comparator':
-                return $this->comparator();
-            case 'firstKey':
-                return $this->firstKey();
-            case 'lastKey':
-                return $this->lastKey();
-            case 'firstValue':
-                return $this->firstValue();
-            case 'lastValue':
-                return $this->lastValue();
-            case 'first':
-                return $this->first();
-            case 'last':
-                return $this->last();
-            case 'keys':
-                return $this->keys();
-            case 'values':
-                return $this->values();
-            case 'count':
-                return $this->count();
-            default:
-                throw new \RuntimeException('Undefined property');
-        }
-    }
+	/**
+	 * Magic get method
+	 *
+	 * @param string $property The property
+	 *
+	 * @throws \RuntimeException If the property does not exist
+	 *
+	 * @return mixed The value associated to the property
+	 *
+	 * @since 1.0.0
+	 */
+	public function __get($property)
+	{
+		switch ($property) {
+			case 'comparator':
+				return $this->comparator();
+			case 'firstKey':
+				return $this->firstKey();
+			case 'lastKey':
+				return $this->lastKey();
+			case 'firstValue':
+				return $this->firstValue();
+			case 'lastValue':
+				return $this->lastValue();
+			case 'first':
+				return $this->first();
+			case 'last':
+				return $this->last();
+			case 'keys':
+				return $this->keys();
+			case 'values':
+				return $this->values();
+			case 'count':
+				return $this->count();
+			default:
+				throw new \RuntimeException('Undefined property');
+		}
+	}
 
-    /**
-     * Get the first key
-     *
-     * @return mixed The first key
-     *
-     * @throws \OutOfBoundsException If there is no element
-     *
-     * @since 1.0.0
-     */
-    public function firstKey()
-    {
-        return $this->first()->key;
-    }
+	/**
+	 * Get the first key
+	 *
+	 * @return mixed The first key
+	 *
+	 * @throws \OutOfBoundsException If there is no element
+	 *
+	 * @since 1.0.0
+	 */
+	public function firstKey()
+	{
+		return $this->first()->key;
+	}
 
-    /**
-     * Get the first value
-     *
-     * @return mixed The first value
-     *
-     * @throws \OutOfBoundsException If there is no element
-     *
-     * @since 1.0.0
-     */
-    public function firstValue()
-    {
-        return $this->first()->value;
-    }
+	/**
+	 * Get the first value
+	 *
+	 * @return mixed The first value
+	 *
+	 * @throws \OutOfBoundsException If there is no element
+	 *
+	 * @since 1.0.0
+	 */
+	public function firstValue()
+	{
+		return $this->first()->value;
+	}
 
-    /**
-     * Get the last key
-     *
-     * @return mixed The last key
-     *
-     * @throws \OutOfBoundsException If there is no element
-     *
-     * @since 1.0.0
-     */
-    public function lastKey()
-    {
-        return $this->last()->key;
-    }
+	/**
+	 * Get the last key
+	 *
+	 * @return mixed The last key
+	 *
+	 * @throws \OutOfBoundsException If there is no element
+	 *
+	 * @since 1.0.0
+	 */
+	public function lastKey()
+	{
+		return $this->last()->key;
+	}
 
-    /**
-     * Get the last value
-     *
-     * @return mixed The last value
-     *
-     * @throws \OutOfBoundsException If there is no element
-     *
-     * @since 1.0.0
-     */
-    public function lastValue()
-    {
-        return $this->last()->value;
-    }
+	/**
+	 * Get the last value
+	 *
+	 * @return mixed The last value
+	 *
+	 * @throws \OutOfBoundsException If there is no element
+	 *
+	 * @since 1.0.0
+	 */
+	public function lastValue()
+	{
+		return $this->last()->value;
+	}
 
-    /**
-     * Returns the greatest key lesser than the given key
-     *
-     * @param mixed $key The searched key
-     *
-     * @return mixed The found key
-     *
-     * @throws \OutOfBoundsException If there is no lower element
-     *
-     * @since 1.0.0
-     */
-    public function lowerKey($key)
-    {
-        return $this->lower($key)->key;
-    }
+	/**
+	 * Returns the greatest key lesser than the given key
+	 *
+	 * @param mixed $key The searched key
+	 *
+	 * @return mixed The found key
+	 *
+	 * @throws \OutOfBoundsException If there is no lower element
+	 *
+	 * @since 1.0.0
+	 */
+	public function lowerKey($key)
+	{
+		return $this->lower($key)->key;
+	}
 
-    /**
-     * Returns the value whose key is the greatest key lesser than the given key
-     *
-     * @param mixed $key The searched key
-     *
-     * @return mixed The found value
-     *
-     * @throws \OutOfBoundsException If there is no lower element
-     *
-     * @since 1.0.0
-     */
-    public function lowerValue($key)
-    {
-        return $this->lower($key)->value;
-    }
+	/**
+	 * Returns the value whose key is the greatest key lesser than the given key
+	 *
+	 * @param mixed $key The searched key
+	 *
+	 * @return mixed The found value
+	 *
+	 * @throws \OutOfBoundsException If there is no lower element
+	 *
+	 * @since 1.0.0
+	 */
+	public function lowerValue($key)
+	{
+		return $this->lower($key)->value;
+	}
 
-    /**
-     * Returns the greatest key lesser than or equal to the given key
-     *
-     * @param mixed $key The searched key
-     *
-     * @return mixed The found key
-     *
-     * @throws \OutOfBoundsException If there is no floor element
-     *
-     * @since 1.0.0
-     */
-    public function floorKey($key)
-    {
-        return $this->floor($key)->key;
-    }
+	/**
+	 * Returns the greatest key lesser than or equal to the given key
+	 *
+	 * @param mixed $key The searched key
+	 *
+	 * @return mixed The found key
+	 *
+	 * @throws \OutOfBoundsException If there is no floor element
+	 *
+	 * @since 1.0.0
+	 */
+	public function floorKey($key)
+	{
+		return $this->floor($key)->key;
+	}
 
-    /**
-     * Returns the value whose key is the greatest key lesser than or equal to the given key
-     *
-     * @param mixed $key The searched key
-     *
-     * @return mixed The found value
-     *
-     * @throws \OutOfBoundsException If there is no floor element
-     *
-     * @since 1.0.0
-     */
-    public function floorValue($key)
-    {
-        return $this->floor($key)->value;
-    }
+	/**
+	 * Returns the value whose key is the greatest key lesser than or equal to the given key
+	 *
+	 * @param mixed $key The searched key
+	 *
+	 * @return mixed The found value
+	 *
+	 * @throws \OutOfBoundsException If there is no floor element
+	 *
+	 * @since 1.0.0
+	 */
+	public function floorValue($key)
+	{
+		return $this->floor($key)->value;
+	}
 
-    /**
-     * Returns the key equal to the given key
-     *
-     * @param mixed $key The searched key
-     *
-     * @return mixed The found key
-     *
-     * @throws \OutOfBoundsException If there is no such element
-     *
-     * @since 1.0.0
-     */
-    public function findKey($key)
-    {
-        return $this->find($key)->key;
-    }
+	/**
+	 * Returns the key equal to the given key
+	 *
+	 * @param mixed $key The searched key
+	 *
+	 * @return mixed The found key
+	 *
+	 * @throws \OutOfBoundsException If there is no such element
+	 *
+	 * @since 1.0.0
+	 */
+	public function findKey($key)
+	{
+		return $this->find($key)->key;
+	}
 
-    /**
-     * Returns the value whose key equal to the given key
-     *
-     * @param mixed $key The searched key
-     *
-     * @return mixed The found value
-     *
-     * @throws \OutOfBoundsException If there is no such element
-     *
-     * @since 1.0.0
-     */
-    public function findValue($key)
-    {
-        return $this->find($key)->value;
-    }
+	/**
+	 * Returns the value whose key equal to the given key
+	 *
+	 * @param mixed $key The searched key
+	 *
+	 * @return mixed The found value
+	 *
+	 * @throws \OutOfBoundsException If there is no such element
+	 *
+	 * @since 1.0.0
+	 */
+	public function findValue($key)
+	{
+		return $this->find($key)->value;
+	}
 
-    /**
-     * Returns the lowest key greater than or equal to the given key
-     *
-     * @param mixed $key The searched key
-     *
-     * @return mixed The found key
-     *
-     * @throws \OutOfBoundsException If there is no ceiling element
-     *
-     * @since 1.0.0
-     */
-    public function ceilingKey($key)
-    {
-        return $this->ceiling($key)->key;
-    }
+	/**
+	 * Returns the lowest key greater than or equal to the given key
+	 *
+	 * @param mixed $key The searched key
+	 *
+	 * @return mixed The found key
+	 *
+	 * @throws \OutOfBoundsException If there is no ceiling element
+	 *
+	 * @since 1.0.0
+	 */
+	public function ceilingKey($key)
+	{
+		return $this->ceiling($key)->key;
+	}
 
-    /**
-     * Returns the value whose key is the lowest key greater than or equal to the given key
-     *
-     * @param mixed $key The searched key
-     *
-     * @return mixed The found value
-     *
-     * @throws \OutOfBoundsException If there is no ceiling element
-     *
-     * @since 1.0.0
-     */
-    public function ceilingValue($key)
-    {
-        return $this->ceiling($key)->value;
-    }
+	/**
+	 * Returns the value whose key is the lowest key greater than or equal to the given key
+	 *
+	 * @param mixed $key The searched key
+	 *
+	 * @return mixed The found value
+	 *
+	 * @throws \OutOfBoundsException If there is no ceiling element
+	 *
+	 * @since 1.0.0
+	 */
+	public function ceilingValue($key)
+	{
+		return $this->ceiling($key)->value;
+	}
 
-    /**
-     * Returns the lowest key greater than to the given key
-     *
-     * @param mixed $key The searched key
-     *
-     * @return mixed The found key
-     *
-     * @throws \OutOfBoundsException If there is no higher element
-     *
-     * @since 1.0.0
-     */
-    public function higherKey($key)
-    {
-        return $this->higher($key)->key;
-    }
+	/**
+	 * Returns the lowest key greater than to the given key
+	 *
+	 * @param mixed $key The searched key
+	 *
+	 * @return mixed The found key
+	 *
+	 * @throws \OutOfBoundsException If there is no higher element
+	 *
+	 * @since 1.0.0
+	 */
+	public function higherKey($key)
+	{
+		return $this->higher($key)->key;
+	}
 
-    /**
-     * Returns the value whose key is the lowest key greater than to the given key
-     *
-     * @param mixed $key The searched key
-     *
-     * @return mixed The found value
-     *
-     * @throws \OutOfBoundsException If there is no higher element
-     *
-     * @since 1.0.0
-     */
-    public function higherValue($key)
-    {
-        return $this->higher($key)->value;
-    }
+	/**
+	 * Returns the value whose key is the lowest key greater than to the given key
+	 *
+	 * @param mixed $key The searched key
+	 *
+	 * @return mixed The found value
+	 *
+	 * @throws \OutOfBoundsException If there is no higher element
+	 *
+	 * @since 1.0.0
+	 */
+	public function higherValue($key)
+	{
+		return $this->higher($key)->value;
+	}
 
-    /**
-     * Keys iterator
-     *
-     * @return Iterator The keys iterator
-     *
-     * @since 1.0.0
-     */
-    public function keys()
-    {
-        return Iterator::keys($this);
-    }
+	/**
+	 * Keys iterator
+	 *
+	 * @return Iterator The keys iterator
+	 *
+	 * @since 1.0.0
+	 */
+	public function keys()
+	{
+		return Iterator::keys($this);
+	}
 
-    /**
-     * Values iterator
-     *
-     * @return Iterator The values iterator
-     *
-     * @since 1.0.0
-     */
-    public function values()
-    {
-        return Iterator::values($this);
-    }
+	/**
+	 * Values iterator
+	 *
+	 * @return Iterator The values iterator
+	 *
+	 * @since 1.0.0
+	 */
+	public function values()
+	{
+		return Iterator::values($this);
+	}
 
-    /**
-     * Convert the object to a string
-     *
-     * @return string String representation of the object
-     *
-     * @since 1.0.0
-     */
-    public function __toString()
-    {
-        return json_encode($this->toArray());
-    }
+	/**
+	 * Convert the object to a string
+	 *
+	 * @return string String representation of the object
+	 *
+	 * @since 1.0.0
+	 */
+	public function __toString()
+	{
+		return json_encode($this->toArray());
+	}
 
-    /**
-     * Convert the object to an array
-     *
-     * @return array Array representation of the object
-     *
-     * @since 1.0.0
-     */
-    public function toArray()
-    {
-        $array = array();
+	/**
+	 * Convert the object to an array
+	 *
+	 * @return array Array representation of the object
+	 *
+	 * @since 1.0.0
+	 */
+	public function toArray()
+	{
+		$array = array();
 
-        foreach ($this as $key => $value) {
-            $array[$key] = $value;
-        }
+		foreach ($this as $key => $value) {
+			$array[$key] = $value;
+		}
 
-        return $array;
-    }
+		return $array;
+	}
 
-    /**
-     * Create an iterator
-     *
-     * @return Iterator A new iterator
-     *
-     * @since 1.0.0
-     */
-    public function getIterator()
-    {
-        return Iterator::create($this);
-    }
+	/**
+	 * Create an iterator
+	 *
+	 * @return Iterator A new iterator
+	 *
+	 * @since 1.0.0
+	 */
+	public function getIterator()
+	{
+		return Iterator::create($this);
+	}
 
-    /**
-     * Get the value for a key
-     *
-     * @param mixed $key The key
-     *
-     * @return mixed The found value
-     *
-     * @throws \OutOfRangeException If there is no such element
-     *
-     * @since 1.0.0
-     */
-    public function offsetGet($key)
-    {
-        try {
-            return $this->find($key)->value;
-        } catch (\OutOfBoundsException $e) {
-            throw new \OutOfRangeException('Undefined offset');
-        }
-    }
+	/**
+	 * Get the value for a key
+	 *
+	 * @param mixed $key The key
+	 *
+	 * @return mixed The found value
+	 *
+	 * @throws \OutOfRangeException If there is no such element
+	 *
+	 * @since 1.0.0
+	 */
+	public function offsetGet($key)
+	{
+		try {
+			return $this->find($key)->value;
+		} catch (\OutOfBoundsException $e) {
+			throw new \OutOfRangeException('Undefined offset');
+		}
+	}
 
-    /**
-     * Test the existence of a key
-     *
-     * @param mixed $key The key
-     *
-     * @return boolean TRUE if the key exists, false otherwise
-     *
-     * @since 1.0.0
-     */
-    public function offsetExists($key)
-    {
-        try {
-            return (bool) $this->find($key);
-        } catch (\OutOfBoundsException $e) {
-            return false;
-        }
-    }
+	/**
+	 * Test the existence of a key
+	 *
+	 * @param mixed $key The key
+	 *
+	 * @return boolean TRUE if the key exists, false otherwise
+	 *
+	 * @since 1.0.0
+	 */
+	public function offsetExists($key)
+	{
+		try {
+			return (bool) $this->find($key);
+		} catch (\OutOfBoundsException $e) {
+			return false;
+		}
+	}
 
-    /**
-     * Set the value for a key
-     *
-     * @param mixed $key   The key
-     * @param mixed $value The value
-     *
-     * @return void
-     *
-     * @throws \RuntimeOperation The operation is not supported by this class
-     *
-     * @since 1.0.0
-     */
-    public function offsetSet($key, $value)
-    {
-        throw new \RuntimeException('Unsupported operation');
-    }
+	/**
+	 * Set the value for a key
+	 *
+	 * @param mixed $key   The key
+	 * @param mixed $value The value
+	 *
+	 * @return void
+	 *
+	 * @throws \RuntimeOperation The operation is not supported by this class
+	 *
+	 * @since 1.0.0
+	 */
+	public function offsetSet($key, $value)
+	{
+		throw new \RuntimeException('Unsupported operation');
+	}
 
-    /**
-     * Unset the existence of a key
-     *
-     * @param mixed $key The key
-     *
-     * @return void
-     *
-     * @throws \RuntimeOperation The operation is not supported by this class
-     *
-     * @since 1.0.0
-     */
-    public function offsetUnset($key)
-    {
-        throw new \RuntimeException('Unsupported operation');
-    }
+	/**
+	 * Unset the existence of a key
+	 *
+	 * @param mixed $key The key
+	 *
+	 * @return void
+	 *
+	 * @throws \RuntimeOperation The operation is not supported by this class
+	 *
+	 * @since 1.0.0
+	 */
+	public function offsetUnset($key)
+	{
+		throw new \RuntimeException('Unsupported operation');
+	}
 }

src/SortedCollection/TreeNode.php

Indentation +539 added lines, -539 removed lines

@@ -30,543 +30,543 @@
  */
 class TreeNode implements \Countable
 {
-    /**
-     * @var integer  Information associated to that node.
-     *                   Bits of order 0 and 1 are reserved for the existence of left and right tree.
-     *                   Other bits are for the balance
-     *
-     * @since 1.0.0
-     */
-    private $information = 0;
-
-    /**
-     * @var TreeNode  Left|Predecessor node
-     *
-     * @since 1.0.0
-     */
-    private $left;
-
-    /**
-     * @var TreeNode  Right|Successor node
-     *
-     * @since 1.0.0
-     */
-    private $right;
-
-    /**
-     * @var mixed  Node key
-     *
-     * @since 1.0.0
-     */
-    private $key;
-
-    /**
-     * @var mixed  Node value
-     *
-     * @since 1.0.0
-     */
-    public $value;
-
-    /**
-     * Create a node
-     *
-     * @param mixed $key   The node key
-     * @param mixed $value The node value
-     *
-     * @return A new node
-     *
-     * @since 1.0.0
-     */
-    public static function create($key, $value)
-    {
-        return new static($key, $value);
-    }
-
-    /**
-     * Constructor
-     *
-     * @param mixed    $key         The node key
-     * @param mixed    $value       The node value
-     * @param TreeNode $predecessor The left node
-     * @param TreeNode $successor   The right node
-     *
-     * @since 1.0.0
-     */
-    protected function __construct($key, $value, $predecessor = null, $successor = null)
-    {
-        $this->key = $key;
-        $this->value = $value;
-        $this->left = $predecessor;
-        $this->right = $successor;
-    }
-
-    /**
-     * Magic get method
-     *
-     * @param string $property The node property
-     *
-     * @return mixed The value associated to the property
-     *
-     * @throws \RuntimeException If the property is undefined
-     *
-     * @since 1.0.0
-     */
-    public function __get($property)
-    {
-        switch ($property) {
-            case 'first':
-                return $this->first();
-            case 'last':
-                return $this->last();
-            case 'predecessor':
-                return $this->predecessor();
-            case 'successor':
-                return $this->successor();
-            case 'key':
-                return $this->key;
-            case 'count':
-                return $this->count();
-            default:
-                throw new \RuntimeException('Undefined property');
-        }
-    }
-
-    /**
-     * Get the first node
-     *
-     * @return the first node
-     *
-     * @since 1.0.0
-     */
-    public function first()
-    {
-        $node = $this;
-
-        while ($node->information & 2) {
-            $node = $node->left;
-        }
-
-        return $node;
-    }
-
-    /**
-     * Get the last node
-     *
-     * @return the last node
-     *
-     * @since 1.0.0
-     */
-    public function last()
-    {
-        $node = $this;
-
-        while ($node->information & 1) {
-            $node = $node->right;
-        }
-
-        return $node;
-    }
-
-    /**
-     * Get the predecessor
-     *
-     * @return the predecessor node
-     *
-     * @since 1.0.0
-     */
-    public function predecessor()
-    {
-        if ($this->information & 2) {
-            $node = $this->left;
-
-            while ($node->information & 1) {
-                $node = $node->right;
-            }
-
-            return $node;
-        } else {
-            return $this->left;
-        }
-    }
-
-    /**
-     * Get the successor
-     *
-     * @return the successor node
-     *
-     * @since 1.0.0
-     */
-    public function successor()
-    {
-        if ($this->information & 1) {
-            $node = $this->right;
-
-            while ($node->information & 2) {
-                $node = $node->left;
-            }
-
-            return $node;
-        } else {
-            return $this->right;
-        }
-    }
-
-    /**
-     * Count the number of key/value pair
-     *
-     * @return integer
-     *
-     * @since 1.0.0
-     */
-    public function count()
-    {
-        $count = 1;
-
-        if ($this->information & 2) {
-            $count += $this->left->count;
-        }
-
-        if ($this->information & 1) {
-            $count += $this->right->count;
-        }
-
-        return $count;
-    }
-
-    /**
-     * Get the node for a key
-     *
-     * @param mixed    $key        The key
-     * @param callable $comparator The comparator function
-     * @param integer  $type       The operation type
-     *                             -2 for the
-     *                             greatest key
-     *                             lesser than the
-     *                             given key -1 for
-     *                             the greatest key
-     *                             lesser than or
-     *                             equal to the given
-     *                             key 0 for the
-     *                             given key +1 for
-     *                             the lowest key
-     *                             greater than or
-     *                             equal to the given
-     *                             key +2 for the
-     *                             lowest key greater
-     *                             than the given key
-     *
-     * @return mixed The node or null if not found
-     *
-     * @since 1.0.0
-     */
-    public function find($key, $comparator, $type = 0)
-    {
-        $node = $this;
-
-        while (true) {
-            $cmp = call_user_func($comparator, $key, $node->key);
-
-            if ($cmp < 0 && $node->information & 2) {
-                $node = $node->left;
-            } elseif ($cmp > 0 && $node->information & 1) {
-                $node = $node->right;
-            } else {
-                break;
-            }
-        }
-
-        if ($cmp < 0) {
-            if ($type < 0) {
-                return $node->left;
-            } elseif ($type > 0) {
-                return $node;
-            } else {
-                return null;
-            }
-        } elseif ($cmp > 0) {
-            if ($type < 0) {
-                return $node;
-            } elseif ($type > 0) {
-                return $node->right;
-            } else {
-                return null;
-            }
-        } else {
-            if ($type < -1) {
-                return $node->predecessor;
-            } elseif ($type > 1) {
-                return $node->successor;
-            } else {
-                return $node;
-            }
-        }
-    }
-
-    /**
-     * Rotate the node to the left
-     *
-     * @return TreeNode The rotated node
-     *
-     * @since 1.0.0
-     */
-    private function rotateLeft()
-    {
-        $right = $this->right;
-
-        if ($right->information & 2) {
-            $this->right = $right->left;
-            $right->left = $this;
-        } else {
-            $right->information |= 2;
-            $this->information &= ~ 1;
-        }
-
-        $this->information -= 4;
-
-        if ($right->information >= 4) {
-            $this->information -= $right->information & ~3;
-        }
-
-        $right->information -= 4;
-
-        if ($this->information < 0) {
-            $right->information += $this->information & ~3;
-        }
-
-        return $right;
-    }
-
-    /**
-     * Rotate the node to the right
-     *
-     * @return TreeNode The rotated node
-     *
-     * @since 1.0.0
-     */
-    private function rotateRight()
-    {
-        $left = $this->left;
-
-        if ($left->information & 1) {
-            $this->left = $left->right;
-            $left->right = $this;
-        } else {
-            $this->information &= ~ 2;
-            $left->information |= 1;
-        }
-
-        $this->information += 4;
-
-        if ($left->information < 0) {
-            $this->information -= $left->information & ~3;
-        }
-
-        $left->information += 4;
-
-        if ($this->information >= 4) {
-            $left->information += $this->information & ~3;
-        }
-
-        return $left;
-    }
-
-    /**
-     * Increment the balance of the node
-     *
-     * @return TreeNode $this or a rotated version of $this
-     *
-     * @since 1.0.0
-     */
-    private function incBalance()
-    {
-        $this->information += 4;
-
-        if ($this->information >= 8) {
-            if ($this->right->information < 0) {
-                $this->right = $this->right->rotateRight();
-            }
-
-            return $this->rotateLeft();
-        }
-
-        return $this;
-    }
-
-    /**
-     * Decrement the balance of the node
-     *
-     * @return TreeNode $this or a rotated version of $this
-     *
-     * @since 1.0.0
-     */
-    private function decBalance()
-    {
-        $this->information -= 4;
-
-        if ($this->information < - 4) {
-            if ($this->left->information >= 4) {
-                $this->left = $this->left->rotateLeft();
-            }
-
-            return $this->rotateRight();
-        }
-
-        return $this;
-    }
-
-    /**
-     * Insert a key/value pair
-     *
-     * @param mixed    $key        The key
-     * @param mixed    $value      The value
-     * @param callable $comparator The comparator function
-     *
-     * @return TreeNode The new root
-     *
-     * @since 1.0.0
-     */
-    public function insert($key, $value, $comparator)
-    {
-        $node = $this;
-        $cmp = call_user_func($comparator, $key, $this->key);
-
-        if ($cmp < 0) {
-            if ($this->information & 2) {
-                $leftBalance = $this->left->information & ~3;
-                $this->left = $this->left->insert($key, $value, $comparator);
-
-                if (($this->left->information & ~3) && ($this->left->information & ~3) != $leftBalance) {
-                    $node = $this->decBalance();
-                }
-            } else {
-                $this->left = new static($key, $value, $this->left, $this);
-                $this->information |= 2;
-                $node = $this->decBalance();
-            }
-        } elseif ($cmp > 0) {
-            if ($this->information & 1) {
-                $rightBalance = $this->right->information & ~3;
-                $this->right = $this->right->insert($key, $value, $comparator);
-
-                if (($this->right->information & ~3) && ($this->right->information & ~3) != $rightBalance) {
-                    $node = $this->incBalance();
-                }
-            } else {
-                $this->right = new static($key, $value, $this, $this->right);
-                $this->information |= 1;
-                $node = $this->incBalance();
-            }
-        } else {
-            $this->value = $value;
-        }
-
-        return $node;
-    }
-
-    /**
-     * Pull up the left most node of a node
-     *
-     * @return TreeNode The new root
-     *
-     * @since 1.0.0
-     */
-    private function pullUpLeftMost()
-    {
-        if ($this->information & 2) {
-            $leftBalance = $this->left->information & ~3;
-            $this->left = $this->left->pullUpLeftMost();
-
-            if (!($this->information & 2) || $leftBalance != 0 && ($this->left->information & ~3) == 0) {
-                return $this->incBalance();
-            } else {
-                return $this;
-            }
-        } else {
-            $this->left->key = $this->key;
-            $this->left->value = $this->value;
-
-            if ($this->information & 1) {
-                $this->right->left = $this->left;
-
-                return $this->right;
-            } else {
-                if ($this->left->right == $this) {
-                    $this->left->information &= ~ 1;
-
-                    return $this->right;
-                } else {
-                    $this->right->information &= ~ 2;
-
-                    return $this->left;
-                }
-            }
-        }
-    }
-
-    /**
-     * Remove a key
-     *
-     * @param mixed    $key        The key
-     * @param callable $comparator The comparator function
-     *
-     * @return TreeNode The new root
-     *
-     * @since 1.0.0
-     */
-    public function remove($key, $comparator)
-    {
-        $cmp = call_user_func($comparator, $key, $this->key);
-
-        if ($cmp < 0) {
-            if ($this->information & 2) {
-                $leftBalance = $this->left->information & ~3;
-                $this->left = $this->left->remove($key, $comparator);
-
-                if (!($this->information & 2) || $leftBalance != 0 && ($this->left->information & ~3) == 0) {
-                    return $this->incBalance();
-                }
-            }
-        } elseif ($cmp > 0) {
-            if ($this->information & 1) {
-                $rightBalance = $this->right->information & ~3;
-                $this->right = $this->right->remove($key, $comparator);
-
-                if (!($this->information & 1) || $rightBalance != 0 && ($this->right->information & ~3) == 0) {
-                    return $this->decBalance();
-                }
-            }
-        } else {
-            if ($this->information & 1) {
-                $rightBalance = $this->right->information & ~3;
-                $this->right = $this->right->pullUpLeftMost();
-
-                if (!($this->information & 1) || $rightBalance != 0 && ($this->right->information & ~3) == 0) {
-                    return $this->decBalance();
-                }
-            } else {
-                $left = $this->left;
-                $right = $this->right;
-
-                if ($this->information & 2) {
-                    $left->right = $right;
-
-                    return $left;
-                } else {
-                    if ($left && $left->right == $this) {
-                        $left->information &= ~ 1;
-
-                        return $right;
-                    } elseif ($right && $right->left == $this) {
-                        $right->information &= ~ 2;
-
-                        return $left;
-                    } else {
-                        return null;
-                    }
-                }
-            }
-        }
-
-        return $this;
-    }
+	/**
+	 * @var integer  Information associated to that node.
+	 *                   Bits of order 0 and 1 are reserved for the existence of left and right tree.
+	 *                   Other bits are for the balance
+	 *
+	 * @since 1.0.0
+	 */
+	private $information = 0;
+
+	/**
+	 * @var TreeNode  Left|Predecessor node
+	 *
+	 * @since 1.0.0
+	 */
+	private $left;
+
+	/**
+	 * @var TreeNode  Right|Successor node
+	 *
+	 * @since 1.0.0
+	 */
+	private $right;
+
+	/**
+	 * @var mixed  Node key
+	 *
+	 * @since 1.0.0
+	 */
+	private $key;
+
+	/**
+	 * @var mixed  Node value
+	 *
+	 * @since 1.0.0
+	 */
+	public $value;
+
+	/**
+	 * Create a node
+	 *
+	 * @param mixed $key   The node key
+	 * @param mixed $value The node value
+	 *
+	 * @return A new node
+	 *
+	 * @since 1.0.0
+	 */
+	public static function create($key, $value)
+	{
+		return new static($key, $value);
+	}
+
+	/**
+	 * Constructor
+	 *
+	 * @param mixed    $key         The node key
+	 * @param mixed    $value       The node value
+	 * @param TreeNode $predecessor The left node
+	 * @param TreeNode $successor   The right node
+	 *
+	 * @since 1.0.0
+	 */
+	protected function __construct($key, $value, $predecessor = null, $successor = null)
+	{
+		$this->key = $key;
+		$this->value = $value;
+		$this->left = $predecessor;
+		$this->right = $successor;
+	}
+
+	/**
+	 * Magic get method
+	 *
+	 * @param string $property The node property
+	 *
+	 * @return mixed The value associated to the property
+	 *
+	 * @throws \RuntimeException If the property is undefined
+	 *
+	 * @since 1.0.0
+	 */
+	public function __get($property)
+	{
+		switch ($property) {
+			case 'first':
+				return $this->first();
+			case 'last':
+				return $this->last();
+			case 'predecessor':
+				return $this->predecessor();
+			case 'successor':
+				return $this->successor();
+			case 'key':
+				return $this->key;
+			case 'count':
+				return $this->count();
+			default:
+				throw new \RuntimeException('Undefined property');
+		}
+	}
+
+	/**
+	 * Get the first node
+	 *
+	 * @return the first node
+	 *
+	 * @since 1.0.0
+	 */
+	public function first()
+	{
+		$node = $this;
+
+		while ($node->information & 2) {
+			$node = $node->left;
+		}
+
+		return $node;
+	}
+
+	/**
+	 * Get the last node
+	 *
+	 * @return the last node
+	 *
+	 * @since 1.0.0
+	 */
+	public function last()
+	{
+		$node = $this;
+
+		while ($node->information & 1) {
+			$node = $node->right;
+		}
+
+		return $node;
+	}
+
+	/**
+	 * Get the predecessor
+	 *
+	 * @return the predecessor node
+	 *
+	 * @since 1.0.0
+	 */
+	public function predecessor()
+	{
+		if ($this->information & 2) {
+			$node = $this->left;
+
+			while ($node->information & 1) {
+				$node = $node->right;
+			}
+
+			return $node;
+		} else {
+			return $this->left;
+		}
+	}
+
+	/**
+	 * Get the successor
+	 *
+	 * @return the successor node
+	 *
+	 * @since 1.0.0
+	 */
+	public function successor()
+	{
+		if ($this->information & 1) {
+			$node = $this->right;
+
+			while ($node->information & 2) {
+				$node = $node->left;
+			}
+
+			return $node;
+		} else {
+			return $this->right;
+		}
+	}
+
+	/**
+	 * Count the number of key/value pair
+	 *
+	 * @return integer
+	 *
+	 * @since 1.0.0
+	 */
+	public function count()
+	{
+		$count = 1;
+
+		if ($this->information & 2) {
+			$count += $this->left->count;
+		}
+
+		if ($this->information & 1) {
+			$count += $this->right->count;
+		}
+
+		return $count;
+	}
+
+	/**
+	 * Get the node for a key
+	 *
+	 * @param mixed    $key        The key
+	 * @param callable $comparator The comparator function
+	 * @param integer  $type       The operation type
+	 *                             -2 for the
+	 *                             greatest key
+	 *                             lesser than the
+	 *                             given key -1 for
+	 *                             the greatest key
+	 *                             lesser than or
+	 *                             equal to the given
+	 *                             key 0 for the
+	 *                             given key +1 for
+	 *                             the lowest key
+	 *                             greater than or
+	 *                             equal to the given
+	 *                             key +2 for the
+	 *                             lowest key greater
+	 *                             than the given key
+	 *
+	 * @return mixed The node or null if not found
+	 *
+	 * @since 1.0.0
+	 */
+	public function find($key, $comparator, $type = 0)
+	{
+		$node = $this;
+
+		while (true) {
+			$cmp = call_user_func($comparator, $key, $node->key);
+
+			if ($cmp < 0 && $node->information & 2) {
+				$node = $node->left;
+			} elseif ($cmp > 0 && $node->information & 1) {
+				$node = $node->right;
+			} else {
+				break;
+			}
+		}
+
+		if ($cmp < 0) {
+			if ($type < 0) {
+				return $node->left;
+			} elseif ($type > 0) {
+				return $node;
+			} else {
+				return null;
+			}
+		} elseif ($cmp > 0) {
+			if ($type < 0) {
+				return $node;
+			} elseif ($type > 0) {
+				return $node->right;
+			} else {
+				return null;
+			}
+		} else {
+			if ($type < -1) {
+				return $node->predecessor;
+			} elseif ($type > 1) {
+				return $node->successor;
+			} else {
+				return $node;
+			}
+		}
+	}
+
+	/**
+	 * Rotate the node to the left
+	 *
+	 * @return TreeNode The rotated node
+	 *
+	 * @since 1.0.0
+	 */
+	private function rotateLeft()
+	{
+		$right = $this->right;
+
+		if ($right->information & 2) {
+			$this->right = $right->left;
+			$right->left = $this;
+		} else {
+			$right->information |= 2;
+			$this->information &= ~ 1;
+		}
+
+		$this->information -= 4;
+
+		if ($right->information >= 4) {
+			$this->information -= $right->information & ~3;
+		}
+
+		$right->information -= 4;
+
+		if ($this->information < 0) {
+			$right->information += $this->information & ~3;
+		}
+
+		return $right;
+	}
+
+	/**
+	 * Rotate the node to the right
+	 *
+	 * @return TreeNode The rotated node
+	 *
+	 * @since 1.0.0
+	 */
+	private function rotateRight()
+	{
+		$left = $this->left;
+
+		if ($left->information & 1) {
+			$this->left = $left->right;
+			$left->right = $this;
+		} else {
+			$this->information &= ~ 2;
+			$left->information |= 1;
+		}
+
+		$this->information += 4;
+
+		if ($left->information < 0) {
+			$this->information -= $left->information & ~3;
+		}
+
+		$left->information += 4;
+
+		if ($this->information >= 4) {
+			$left->information += $this->information & ~3;
+		}
+
+		return $left;
+	}
+
+	/**
+	 * Increment the balance of the node
+	 *
+	 * @return TreeNode $this or a rotated version of $this
+	 *
+	 * @since 1.0.0
+	 */
+	private function incBalance()
+	{
+		$this->information += 4;
+
+		if ($this->information >= 8) {
+			if ($this->right->information < 0) {
+				$this->right = $this->right->rotateRight();
+			}
+
+			return $this->rotateLeft();
+		}
+
+		return $this;
+	}
+
+	/**
+	 * Decrement the balance of the node
+	 *
+	 * @return TreeNode $this or a rotated version of $this
+	 *
+	 * @since 1.0.0
+	 */
+	private function decBalance()
+	{
+		$this->information -= 4;
+
+		if ($this->information < - 4) {
+			if ($this->left->information >= 4) {
+				$this->left = $this->left->rotateLeft();
+			}
+
+			return $this->rotateRight();
+		}
+
+		return $this;
+	}
+
+	/**
+	 * Insert a key/value pair
+	 *
+	 * @param mixed    $key        The key
+	 * @param mixed    $value      The value
+	 * @param callable $comparator The comparator function
+	 *
+	 * @return TreeNode The new root
+	 *
+	 * @since 1.0.0
+	 */
+	public function insert($key, $value, $comparator)
+	{
+		$node = $this;
+		$cmp = call_user_func($comparator, $key, $this->key);
+
+		if ($cmp < 0) {
+			if ($this->information & 2) {
+				$leftBalance = $this->left->information & ~3;
+				$this->left = $this->left->insert($key, $value, $comparator);
+
+				if (($this->left->information & ~3) && ($this->left->information & ~3) != $leftBalance) {
+					$node = $this->decBalance();
+				}
+			} else {
+				$this->left = new static($key, $value, $this->left, $this);
+				$this->information |= 2;
+				$node = $this->decBalance();
+			}
+		} elseif ($cmp > 0) {
+			if ($this->information & 1) {
+				$rightBalance = $this->right->information & ~3;
+				$this->right = $this->right->insert($key, $value, $comparator);
+
+				if (($this->right->information & ~3) && ($this->right->information & ~3) != $rightBalance) {
+					$node = $this->incBalance();
+				}
+			} else {
+				$this->right = new static($key, $value, $this, $this->right);
+				$this->information |= 1;
+				$node = $this->incBalance();
+			}
+		} else {
+			$this->value = $value;
+		}
+
+		return $node;
+	}
+
+	/**
+	 * Pull up the left most node of a node
+	 *
+	 * @return TreeNode The new root
+	 *
+	 * @since 1.0.0
+	 */
+	private function pullUpLeftMost()
+	{
+		if ($this->information & 2) {
+			$leftBalance = $this->left->information & ~3;
+			$this->left = $this->left->pullUpLeftMost();
+
+			if (!($this->information & 2) || $leftBalance != 0 && ($this->left->information & ~3) == 0) {
+				return $this->incBalance();
+			} else {
+				return $this;
+			}
+		} else {
+			$this->left->key = $this->key;
+			$this->left->value = $this->value;
+
+			if ($this->information & 1) {
+				$this->right->left = $this->left;
+
+				return $this->right;
+			} else {
+				if ($this->left->right == $this) {
+					$this->left->information &= ~ 1;
+
+					return $this->right;
+				} else {
+					$this->right->information &= ~ 2;
+
+					return $this->left;
+				}
+			}
+		}
+	}
+
+	/**
+	 * Remove a key
+	 *
+	 * @param mixed    $key        The key
+	 * @param callable $comparator The comparator function
+	 *
+	 * @return TreeNode The new root
+	 *
+	 * @since 1.0.0
+	 */
+	public function remove($key, $comparator)
+	{
+		$cmp = call_user_func($comparator, $key, $this->key);
+
+		if ($cmp < 0) {
+			if ($this->information & 2) {
+				$leftBalance = $this->left->information & ~3;
+				$this->left = $this->left->remove($key, $comparator);
+
+				if (!($this->information & 2) || $leftBalance != 0 && ($this->left->information & ~3) == 0) {
+					return $this->incBalance();
+				}
+			}
+		} elseif ($cmp > 0) {
+			if ($this->information & 1) {
+				$rightBalance = $this->right->information & ~3;
+				$this->right = $this->right->remove($key, $comparator);
+
+				if (!($this->information & 1) || $rightBalance != 0 && ($this->right->information & ~3) == 0) {
+					return $this->decBalance();
+				}
+			}
+		} else {
+			if ($this->information & 1) {
+				$rightBalance = $this->right->information & ~3;
+				$this->right = $this->right->pullUpLeftMost();
+
+				if (!($this->information & 1) || $rightBalance != 0 && ($this->right->information & ~3) == 0) {
+					return $this->decBalance();
+				}
+			} else {
+				$left = $this->left;
+				$right = $this->right;
+
+				if ($this->information & 2) {
+					$left->right = $right;
+
+					return $left;
+				} else {
+					if ($left && $left->right == $this) {
+						$left->information &= ~ 1;
+
+						return $right;
+					} elseif ($right && $right->left == $this) {
+						$right->information &= ~ 2;
+
+						return $left;
+					} else {
+						return null;
+					}
+				}
+			}
+		}
+
+		return $this;
+	}
 }

src/SortedCollection/SortedMap.php

Indentation +116 added lines, -116 removed lines

@@ -24,130 +24,130 @@
  */
 interface SortedMap extends SortedCollection
 {
-    /**
-     * Get the first key or throw an exception if there is no element
-     *
-     * @return mixed The first key
-     *
-     * @throws \OutOfBoundsException If there is no element
-     *
-     * @since 1.0.0
-     */
-    public function firstKey();
+	/**
+	 * Get the first key or throw an exception if there is no element
+	 *
+	 * @return mixed The first key
+	 *
+	 * @throws \OutOfBoundsException If there is no element
+	 *
+	 * @since 1.0.0
+	 */
+	public function firstKey();
 
-    /**
-     * Get the last key or throw an exception if there is no element
-     *
-     * @return mixed The last key
-     *
-     * @throws \OutOfBoundsException If there is no element
-     *
-     * @since 1.0.0
-     */
-    public function lastKey();
+	/**
+	 * Get the last key or throw an exception if there is no element
+	 *
+	 * @return mixed The last key
+	 *
+	 * @throws \OutOfBoundsException If there is no element
+	 *
+	 * @since 1.0.0
+	 */
+	public function lastKey();
 
-    /**
-     * Returns the greatest key lesser than the given key or throw an exception if there is no such key
-     *
-     * @param mixed $key The searched key
-     *
-     * @return mixed The found key
-     *
-     * @throws \OutOfBoundsException If there is no lower element
-     *
-     * @since 1.0.0
-     */
-    public function lowerKey($key);
+	/**
+	 * Returns the greatest key lesser than the given key or throw an exception if there is no such key
+	 *
+	 * @param mixed $key The searched key
+	 *
+	 * @return mixed The found key
+	 *
+	 * @throws \OutOfBoundsException If there is no lower element
+	 *
+	 * @since 1.0.0
+	 */
+	public function lowerKey($key);
 
-    /**
-     * Returns the greatest key lesser than or equal to the given key or throw an exception if there is no such key
-     *
-     * @param mixed $key The searched key
-     *
-     * @return mixed The found key
-     *
-     * @throws \OutOfBoundsException If there is no floor element
-     *
-     * @since 1.0.0
-     */
-    public function floorKey($key);
+	/**
+	 * Returns the greatest key lesser than or equal to the given key or throw an exception if there is no such key
+	 *
+	 * @param mixed $key The searched key
+	 *
+	 * @return mixed The found key
+	 *
+	 * @throws \OutOfBoundsException If there is no floor element
+	 *
+	 * @since 1.0.0
+	 */
+	public function floorKey($key);
 
-    /**
-     * Returns the key equal to the given key or throw an exception if there is no such key
-     *
-     * @param mixed $key The searched key
-     *
-     * @return mixed The found key
-     *
-     * @throws \OutOfBoundsException If there is no such element
-     *
-     * @since 1.0.0
-     */
-    public function findKey($key);
+	/**
+	 * Returns the key equal to the given key or throw an exception if there is no such key
+	 *
+	 * @param mixed $key The searched key
+	 *
+	 * @return mixed The found key
+	 *
+	 * @throws \OutOfBoundsException If there is no such element
+	 *
+	 * @since 1.0.0
+	 */
+	public function findKey($key);
 
-    /**
-     * Returns the lowest key greater than or equal to the given key or throw an exception if there is no such key
-     *
-     * @param mixed $key The searched key
-     *
-     * @return mixed The found key
-     *
-     * @throws \OutOfBoundsException If there is no ceiling element
-     *
-     * @since 1.0.0
-     */
-    public function ceilingKey($key);
+	/**
+	 * Returns the lowest key greater than or equal to the given key or throw an exception if there is no such key
+	 *
+	 * @param mixed $key The searched key
+	 *
+	 * @return mixed The found key
+	 *
+	 * @throws \OutOfBoundsException If there is no ceiling element
+	 *
+	 * @since 1.0.0
+	 */
+	public function ceilingKey($key);
 
-    /**
-     * Returns the lowest key greater than to the given key or throw an exception if there is no such key
-     *
-     * @param mixed $key The searched key
-     *
-     * @return mixed The found key
-     *
-     * @throws \OutOfBoundsException If there is no higher element
-     *
-     * @since 1.0.0
-     */
-    public function higherKey($key);
+	/**
+	 * Returns the lowest key greater than to the given key or throw an exception if there is no such key
+	 *
+	 * @param mixed $key The searched key
+	 *
+	 * @return mixed The found key
+	 *
+	 * @throws \OutOfBoundsException If there is no higher element
+	 *
+	 * @since 1.0.0
+	 */
+	public function higherKey($key);
 
-    /**
-     * Get the predecessor node
-     *
-     * @param TreeNode $node A tree node member of the underlying TreeMap
-     *
-     * @return mixed The predecessor node
-     *
-     * @since 1.0.0
-     */
-    public function predecessor($node);
+	/**
+	 * Get the predecessor node
+	 *
+	 * @param TreeNode $node A tree node member of the underlying TreeMap
+	 *
+	 * @return mixed The predecessor node
+	 *
+	 * @since 1.0.0
+	 */
+	public function predecessor($node);
 
-    /**
-     * Get the successor node
-     *
-     * @param TreeNode $node A tree node member of the underlying TreeMap
-     *
-     * @return mixed The successor node
-     *
-     * @since 1.0.0
-     */
-    public function successor($node);
+	/**
+	 * Get the successor node
+	 *
+	 * @param TreeNode $node A tree node member of the underlying TreeMap
+	 *
+	 * @return mixed The successor node
+	 *
+	 * @since 1.0.0
+	 */
+	public function successor($node);
 
-    /**
-     * Keys generator
-     *
-     * @return mixed The keys generator
-     *
-     * @since 1.0.0
-     */
-    public function keys();
+	/**
+	 * Keys generator
+	 *
+	 * @return mixed The keys generator
+	 *
+	 * @since 1.0.0
+	 */
+	public function keys();
 
-    /**
-     * Values generator
-     *
-     * @return mixed The values generator
-     *
-     * @since 1.0.0
-     */
-    public function values();
+	/**
+	 * Values generator
+	 *
+	 * @return mixed The values generator
+	 *
+	 * @since 1.0.0
+	 */
+	public function values();
 }