chdemko / php-bitarray

examples/BitArray.php

Indentation +1 added lines, -1 removed lines

@@ -35,7 +35,7 @@
 
 // Print 0:1;1:1;2:1;3:;4:1;
 foreach ($bits as $index => $value) {
-    echo $index . ':' . $value . ';';
+	echo $index . ':' . $value . ';';
 }
 
 echo PHP_EOL;

src/BitArray/Iterator.php

Indentation +79 added lines, -79 removed lines

@@ -23,90 +23,90 @@
  */
 class Iterator implements \Iterator
 {
-    /**
-     * @var integer  Index
-     *
-     * @since 1.0.0
-     */
-    private $index;
+	/**
+	 * @var integer  Index
+	 *
+	 * @since 1.0.0
+	 */
+	private $index;
 
-    /**
-     * @var BitArray  bits
-     *
-     * @since 1.0.0
-     */
-    private $bits;
+	/**
+	 * @var BitArray  bits
+	 *
+	 * @since 1.0.0
+	 */
+	private $bits;
 
-    /**
-     * Constructor
-     *
-     * @param BitArray $bits BitArray
-     *
-     * @since 1.0.0
-     */
-    public function __construct(BitArray $bits)
-    {
-        $this->bits = $bits;
-        $this->rewind();
-    }
+	/**
+	 * Constructor
+	 *
+	 * @param BitArray $bits BitArray
+	 *
+	 * @since 1.0.0
+	 */
+	public function __construct(BitArray $bits)
+	{
+		$this->bits = $bits;
+		$this->rewind();
+	}
 
-    /**
-     * Rewind the Iterator to the first element
-     *
-     * @return void
-     *
-     * @since 1.0.0
-     */
-    public function rewind()
-    {
-        $this->index = 0;
-    }
+	/**
+	 * Rewind the Iterator to the first element
+	 *
+	 * @return void
+	 *
+	 * @since 1.0.0
+	 */
+	public function rewind()
+	{
+		$this->index = 0;
+	}
 
-    /**
-     * Return the current key
-     *
-     * @return mixed  The current key
-     *
-     * @since 1.0.0
-     */
-    public function key()
-    {
-        return $this->index;
-    }
+	/**
+	 * Return the current key
+	 *
+	 * @return mixed  The current key
+	 *
+	 * @since 1.0.0
+	 */
+	public function key()
+	{
+		return $this->index;
+	}
 
-    /**
-     * Return the current value
-     *
-     * @return mixed  The current value
-     *
-     * @since 1.0.0
-     */
-    public function current()
-    {
-        return $this->bits[$this->index];
-    }
+	/**
+	 * Return the current value
+	 *
+	 * @return mixed  The current value
+	 *
+	 * @since 1.0.0
+	 */
+	public function current()
+	{
+		return $this->bits[$this->index];
+	}
 
-    /**
-     * Move forward to the next element
-     *
-     * @return void
-     *
-     * @since 1.0.0
-     */
-    public function next()
-    {
-        $this->index++;
-    }
+	/**
+	 * Move forward to the next element
+	 *
+	 * @return void
+	 *
+	 * @since 1.0.0
+	 */
+	public function next()
+	{
+		$this->index++;
+	}
 
-    /**
-     * Checks if current position is valid
-     *
-     * @return boolean
-     *
-     * @since 1.0.0
-     */
-    public function valid()
-    {
-        return $this->index < $this->bits->size;
-    }
+	/**
+	 * Checks if current position is valid
+	 *
+	 * @return boolean
+	 *
+	 * @since 1.0.0
+	 */
+	public function valid()
+	{
+		return $this->index < $this->bits->size;
+	}
 }

src/BitArray/BitArray.php

Indentation +736 added lines, -736 removed lines

@@ -26,740 +26,740 @@
  */
 class BitArray implements \ArrayAccess, \Countable, \IteratorAggregate, \JsonSerializable
 {
-    /**
-     * @var integer[]  Number of bits for each value between 0 and 255
-     */
-    private static $count = array(
-        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
-        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
-        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
-        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
-        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
-        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
-        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
-        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
-        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
-        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
-        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
-        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
-        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
-        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
-        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
-        4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
-    );
-
-    /**
-     * @var integer[]  Mask for restricting complements
-     */
-    private static $restrict = array(255, 1, 3, 7, 15, 31, 63, 127);
-
-    /**
-     * @var string  Underlying data
-     *
-     * @since 1.0.0
-     */
-    private $data;
-
-    /**
-     * @var integer  Size of the bit array
-     *
-     * @since 1.0.0
-     */
-    private $size;
-
-    /**
-     * Create a new bit array of the given size
-     *
-     * @param integer $size    The BitArray size
-     * @param boolean $default The default value for bits
-     *
-     * @since 1.0.0
-     */
-    protected function __construct($size = 0, $default = false)
-    {
-        $this->size = (int) $size;
-
-        if ($default) {
-            $this->data = str_repeat(chr(255), (int) ceil($this->size / 8));
-            $this->restrict();
-        } else {
-            $this->data = str_repeat(chr(0), (int) ceil($this->size / 8));
-        }
-    }
-
-    /**
-     * Remove useless bits for simplifying count operation.
-     *
-     * @return BitArray  $this for chaining
-     *
-     * @since 1.2.0
-     */
-    protected function restrict()
-    {
-        $length = strlen($this->data);
-
-        if ($length > 0) {
-            $this->data[$length - 1] = chr(ord($this->data[$length - 1]) & self::$restrict[$this->size % 8]);
-        }
-
-        return $this;
-    }
-
-    /**
-     * Clone a BitArray
-     *
-     * @return void
-     *
-     * @since 1.0.0
-     */
-    public function __clone()
-    {
-        $this->data = str_repeat($this->data, 1);
-    }
-
-    /**
-     * Convert the object to a string
-     *
-     * @return string  String representation of this object
-     *
-     * @since 1.0.0
-     */
-    public function __toString()
-    {
-        $string = str_repeat('0', $this->size);
-
-        for ($offset = 0; $offset < $this->size; $offset++) {
-            if (ord($this->data[(int) ($offset / 8)]) & (1 << $offset % 8)) {
-                $string[$offset] = '1';
-            }
-        }
-
-        return $string;
-    }
-
-    /**
-     * 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 'size':
-                return $this->size;
-            case 'count':
-                return $this->count();
-            default:
-                throw new \RuntimeException('Undefined property');
-        }
-    }
-
-    /**
-     * Test the existence of an index
-     *
-     * @param integer $offset The offset
-     *
-     * @return boolean  The truth value
-     *
-     * @since 1.0.0
-     */
-    public function offsetExists($offset)
-    {
-        return is_int($offset) && $offset >= 0 && $offset < $this->size;
-    }
-
-    /**
-     * Get the truth value for an index
-     *
-     * @param integer $offset The offset
-     *
-     * @return boolean  The truth value
-     *
-     * @throws OutOfRangeException  Argument index must be an positive integer lesser than the size
-     *
-     * @since 1.0.0
-     */
-    public function offsetGet($offset)
-    {
-        if ($this->offsetExists($offset)) {
-            return (bool) (ord($this->data[(int) ($offset / 8)]) & (1 << $offset % 8));
-        } else {
-            throw new \OutOfRangeException('Argument offset must be a positive integer lesser than the size');
-        }
-    }
-
-    /**
-     * Set the truth value for an index
-     *
-     * @param integer $offset The offset
-     * @param boolean $value  The truth value
-     *
-     * @return void
-     *
-     * @throws OutOfRangeException  Argument index must be an positive integer lesser than the size
-     *
-     * @since 1.0.0
-     */
-    public function offsetSet($offset, $value)
-    {
-        if ($this->offsetExists($offset)) {
-            $index = (int) ($offset / 8);
-
-            if ($value) {
-                $this->data[$index] = chr(ord($this->data[$index]) | (1 << $offset % 8));
-            } else {
-                $this->data[$index] = chr(ord($this->data[$index]) & ~(1 << $offset % 8));
-            }
-        } else {
-            throw new \OutOfRangeException('Argument index must be a positive integer lesser than the size');
-        }
-    }
-
-    /**
-     * Unset the existence of an index
-     *
-     * @param integer $offset The index
-     *
-     * @return void
-     *
-     * @throws RuntimeException  Values cannot be unset
-     *
-     * @since 1.0.0
-     */
-    public function offsetUnset($offset)
-    {
-        throw new \RuntimeException('Values cannot be unset');
-    }
-
-    /**
-     * Return the number of true bits
-     *
-     * @return integer  The number of true bits
-     *
-     * @since 1.0.0
-     */
-    public function count()
-    {
-        $count = 0;
-
-        for ($index = 0, $length = strlen($this->data); $index < $length; $index++) {
-            $count += self::$count[ord($this->data[$index])];
-        }
-
-        return $count;
-    }
-
-    /**
-     * Transform the object to an array
-     *
-     * @return array  Array of values
-     *
-     * @since 1.1.0
-     */
-    public function toArray()
-    {
-        $array = array();
-
-        for ($index = 0; $index < $this->size; $index++) {
-            $array[] = (bool) (ord($this->data[(int) ($index / 8)]) & (1 << $index % 8));
-        }
-
-        return $array;
-    }
-
-    /**
-     * Serialize the object
-     *
-     * @return array  Array of values
-     *
-     * @since 1.0.0
-     */
-    public function jsonSerialize()
-    {
-        return $this->toArray();
-    }
-
-    /**
-     * Get an iterator
-     *
-     * @return Iterator  Iterator
-     *
-     * @since 1.0.0
-     */
-    public function getIterator()
-    {
-        return new Iterator($this);
-    }
-
-    /**
-     * Return the size
-     *
-     * @return integer  The size
-     *
-     * @since 1.0.0
-     */
-    public function size()
-    {
-        return $this->size;
-    }
-
-    /**
-     * Copy bits directly from a BitArray
-     *
-     * @param BitArray $bits   A BitArray to copy
-     * @param int      $index  Starting index for destination
-     * @param int      $offset Starting index for copying
-     * @param int      $size   Copy size
-     *
-     * @return BitArray  This object for chaining
-     *
-     * @throws OutOfRangeException  Argument index must be an positive integer lesser than the size
-     *
-     * @since 1.1.0
-     */
-    public function directCopy(BitArray $bits, $index = 0, $offset = 0, $size = 0)
-    {
-        if ($offset > $index) {
-            for ($i = 0; $i < $size; $i++) {
-                $this[$i + $index] = $bits[$i + $offset];
-            }
-        } else {
-            for ($i = $size - 1; $i >= 0; $i--) {
-                $this[$i + $index] = $bits[$i + $offset];
-            }
-        }
-
-        return $this;
-    }
-
-    /**
-     * Copy bits from a BitArray
-     *
-     * * if index is non-negative, the index parameter is used as it is,
-     *   keeping its real value between 0 and size-1;
-     * * if index is negative, the index parameter starts from the end,
-     *   keeping its real value between 0 and size-1.
-     *
-     * * if offset is non-negative, the offset parameter is used as it is,
-     *   keeping its positive value between 0 and size-1;
-     * * if offset is negative, the offset parameter starts from the end,
-     *   keeping its real value between 0 and size-1.
-     *
-     * * if size is given and is positive, then the copy will copy size elements.
-     * * if the bits argument is shorter than the size, then only the available elements will be copied.
-     * * if size is given and is negative, then the copy starts from the end.
-     * * if size is omitted, then the copy will have everything from offset up
-     *   until the end of the bits argument.
-     *
-     * @param BitArray $bits   A BitArray to copy
-     * @param int      $index  Starting index for destination.
-     * @param int      $offset Starting index for copying.
-     * @param mixed    $size   Copy size.
-     *
-     * @return BitArray  This object for chaining
-     *
-     * @since 1.1.0
-     */
-    public function copy(BitArray $bits, $index = 0, $offset = 0, $size = null)
-    {
-        $index = $this->getRealOffset($index);
-        $offset = $bits->getRealOffset($offset);
-        $size = $bits->getRealSize($offset, $size);
-
-        if ($size > $this->size - $index) {
-            $size = $this->size - $index;
-        }
-
-        return $this->directCopy($bits, $index, $offset, $size);
-    }
-
-    /**
-     * Get the real offset using a positive or negative offset
-     *
-     * * If offset is non-negative, the offset parameter is used as it is,
-     *   keeping its real value between 0 and size-1.
-     * * if offset is negative, the offset parameter starts from the end,
-     *   keeping its real value between 0 and size-1.
-     *
-     * @param int $offset The offset
-     *
-     * @return integer  The real offset
-     *
-     * @since 1.1.0
-     */
-    protected function getRealOffset($offset)
-    {
-        $offset = (int) $offset;
-
-        if ($offset < 0) {
-            // Start from the end
-            $offset = $this->size + $offset;
-
-            if ($offset < 0) {
-                $offset = 0;
-            }
-        } elseif ($offset > $this->size) {
-            $offset = $this->size;
-        }
-
-        return $offset;
-    }
-
-    /**
-     * Get the real offset using a positive or negative offset
-     *
-     * * if size is given and is positive, then the real size will be between 0 and the current size-1.
-     * * if size is given and is negative, then the real size starts from the end.
-     * * if size is omitted, then the size goes until the end of the BitArray.
-     *
-     * @param int   $offset The real offset.
-     * @param mixed $size   The size
-     *
-     * @return integer  The real size
-     *
-     * @since 1.1.0
-     */
-    protected function getRealSize($offset, $size)
-    {
-        if ($size === null) {
-            $size = $this->size - $offset;
-        } else {
-            $size = (int) $size;
-
-            if ($size < 0) {
-                $size = $this->size + $size - $offset;
-
-                if ($size < 0) {
-                    $size = 0;
-                }
-            } elseif ($size > $this->size - $offset) {
-                $size = $this->size - $offset;
-            }
-        }
-
-        return $size;
-    }
-
-    /**
-     * Create a new BitArray from an integer
-     *
-     * @param integer $size    Size of the BitArray
-     * @param boolean $default The default value for bits
-     *
-     * @return BitArray  A new BitArray
-     *
-     * @since 1.0.0
-     */
-    public static function fromInteger($size, $default = false)
-    {
-        return new BitArray($size, (bool) $default);
-    }
-
-    /**
-     * Create a new BitArray from a sequence of bits.
-     *
-     * @param integer $size   Size of the BitArray
-     * @param integer $values The values for the bits
-     *
-     * @return BitArray  A new BitArray
-     *
-     * @since 1.2.0
-     */
-    public static function fromDecimal($size, $values = 0)
-    {
-        $php_bit_size = PHP_INT_SIZE * 8;
-        $size = min((int) $size, $php_bit_size);
-        $values <<= ($php_bit_size - $size);
-        $bits = new BitArray($size);
-
-        for ($i = 0; $i < ceil($size / 8); $i++) {
-            $value = ($values & (0xff << ($php_bit_size - 8))) >> ($php_bit_size - 8);
-            $reverse = 0;
-            for ($j = 0; $j < 8; $j++) {
-                if ($value & (1 << $j)) {
-                    $reverse |= 1 << (7 - $j);
-                }
-            }
-            $bits->data[$i] = chr($reverse);
-            $values <<= 8;
-        }
-
-        return $bits;
-    }
-
-    /**
-     * Create a new BitArray from a traversable
-     *
-     * @param mixed $traversable A traversable and countable
-     *
-     * @return BitArray  A new BitArray
-     *
-     * @since 1.0.0
-     */
-    public static function fromTraversable($traversable)
-    {
-        $bits = new BitArray(count($traversable));
-        $offset = 0;
-        $ord = 0;
-
-        foreach ($traversable as $value) {
-            if ($value) {
-                $ord |= 1 << $offset % 8;
-            }
-
-            if ($offset % 8 === 7) {
-                $bits->data[(int) ($offset / 8)] = chr($ord);
-                $ord = 0;
-            }
-
-            $offset++;
-        }
-
-        if ($offset % 8 !== 0) {
-            $bits->data[(int) ($offset / 8)] = chr($ord);
-        }
-
-        return $bits;
-    }
-
-    /**
-     * Create a new BitArray from a bit string
-     *
-     * @param string $string A bit string
-     *
-     * @return BitArray  A new BitArray
-     *
-     * @since 1.0.0
-     */
-    public static function fromString($string)
-    {
-        $bits = new BitArray(strlen($string));
-        $ord = 0;
-
-        for ($offset = 0; $offset < $bits->size; $offset++) {
-            if ($string[$offset] !== '0') {
-                $ord |= 1 << $offset % 8;
-            }
-
-            if ($offset % 8 === 7) {
-                $bits->data[(int) ($offset / 8)] = chr($ord);
-                $ord = 0;
-            }
-        }
-
-        if ($offset % 8 !== 0) {
-            $bits->data[(int) ($offset / 8)] = chr($ord);
-        }
-
-        return $bits;
-    }
-
-    /**
-     * Create a new BitArray from json
-     *
-     * @param string $json A json encoded value
-     *
-     * @return BitArray  A new BitArray
-     *
-     * @since 1.0.0
-     */
-    public static function fromJson($json)
-    {
-        return self::fromTraversable(json_decode($json));
-    }
-
-    /**
-     * Create a new BitArray using a slice
-     *
-     * * if offset is non-negative, the slice will start at that offset in the bits argument.
-     * * if offset is negative, the slice will start from the end of the bits argument.
-     *
-     * * if size is given and is positive, then the slice will have up to that many elements in it.
-     * * if the bits argument is shorter than the size, then only the available elements will be present.
-     * * if size is given and is negative,
-     *   then the slice will stop that many elements from the end of the bits argument.
-     * * if size is omitted,
-     *   then the slice will have everything from offset up until the end of the bits argument.
-     *
-     * @param BitArray $bits   A BitArray to get the slice
-     * @param int      $offset The offset
-     * @param mixed    $size   The size
-     *
-     * @return BitArray  A new BitArray
-     *
-     * @since 1.1.0
-     */
-    public static function fromSlice(BitArray $bits, $offset = 0, $size = null)
-    {
-        $offset = $bits->getRealOffset($offset);
-        $size = $bits->getRealSize($offset, $size);
-        $slice = new BitArray($size);
-
-        return $slice->directCopy($bits, 0, $offset, $size);
-    }
-
-    /**
-     * Create a new BitArray using the concat operation
-     *
-     * @param BitArray $bits1 A BitArray
-     * @param BitArray $bits2 A BitArray
-     *
-     * @return BitArray  A new BitArray
-     *
-     * @since 1.1.0
-     */
-    public static function fromConcat(BitArray $bits1, BitArray $bits2)
-    {
-        $size = $bits1->size + $bits2->size;
-        $concat = new BitArray($size);
-        $concat->directCopy($bits1, 0, 0, $bits1->size);
-        $concat->directCopy($bits2, $bits1->size, 0, $bits2->size);
-
-        return $concat;
-    }
-
-    /**
-     * Complement the bit array
-     *
-     * @return BitArray  This object for chaining
-     *
-     * @since 1.0.0
-     */
-    public function applyComplement()
-    {
-        $length = strlen($this->data);
-
-        for ($index = 0; $index < $length; $index++) {
-            $this->data[$index] = chr(~ ord($this->data[$index]));
-        }
-
-        return $this->restrict();
-    }
-
-    /**
-     * Or with an another bit array
-     *
-     * @param BitArray $bits A bit array
-     *
-     * @return BitArray  This object for chaining
-     *
-     * @throws InvalidArgumentException  Argument must be of equal size
-     *
-     * @since 1.0.0
-     */
-    public function applyOr(BitArray $bits)
-    {
-        if ($this->size == $bits->size) {
-            $length = strlen($this->data);
-
-            for ($index = 0; $index < $length; $index++) {
-                $this->data[$index] = chr(ord($this->data[$index]) | ord($bits->data[$index]));
-            }
-
-            return $this;
-        } else {
-            throw new \InvalidArgumentException('Argument must be of equal size');
-        }
-    }
-
-    /**
-     * And with an another bit array
-     *
-     * @param BitArray $bits A bit array
-     *
-     * @return BitArray  This object for chaining
-     *
-     * @throws InvalidArgumentException  Argument must be of equal size
-     *
-     * @since 1.0.0
-     */
-    public function applyAnd(BitArray $bits)
-    {
-        if ($this->size == $bits->size) {
-            $length = strlen($this->data);
-
-            for ($index = 0; $index < $length; $index++) {
-                $this->data[$index] = chr(ord($this->data[$index]) & ord($bits->data[$index]));
-            }
-
-            return $this;
-        } else {
-            throw new \InvalidArgumentException('Argument must be of equal size');
-        }
-    }
-
-    /**
-     * Xor with an another bit array
-     *
-     * @param BitArray $bits A bit array
-     *
-     * @return BitArray  This object for chaining
-     *
-     * @throws InvalidArgumentException  Argument must be of equal size
-     *
-     * @since 1.0.0
-     */
-    public function applyXor(BitArray $bits)
-    {
-        if ($this->size == $bits->size) {
-            $length = strlen($this->data);
-
-            for ($index = 0; $index < $length; $index++) {
-                $this->data[$index] = chr(ord($this->data[$index]) ^ ord($bits->data[$index]));
-            }
-
-            return $this;
-        } else {
-            throw new \InvalidArgumentException('Argument must be of equal size');
-        }
-    }
-
-    /**
-     * Shift a bit array.
-     *
-     * Negative value means the shifting is done right to left
-     * while positive value means the shifting is done left to right.
-     *
-     * @param int     $size  Size to shift.
-     *
-     * @param boolean $value Value to shift
-     *
-     * @return BitArray  $this for chaining
-     *
-     * @since 1.2.0
-     */
-    public function shift($size = 1, $value = false)
-    {
-        $size = (int) $size;
-
-        if ($size > 0) {
-            $min = min($this->size, $size);
-
-            for ($i = $this->size - 1; $i >= $min; $i--) {
-                $this[$i] = $this[$i - $min];
-            }
-
-            for ($i = 0; $i < $min; $i++) {
-                $this[$i] = $value;
-            }
-        } else {
-            $min = min($this->size, -$size);
-
-            for ($i = 0; $i < $this->size - $min; $i++) {
-                $this[$i] = $this[$i + $min];
-            }
-
-            for ($i = $this->size - $min; $i < $this->size; $i++) {
-                $this[$i] = $value;
-            }
-        }
-
-        return $this;
-    }
+	/**
+	 * @var integer[]  Number of bits for each value between 0 and 255
+	 */
+	private static $count = array(
+		0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
+		1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+		1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+		1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+		3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+		1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+		3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+		3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+		3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+		4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
+	);
+
+	/**
+	 * @var integer[]  Mask for restricting complements
+	 */
+	private static $restrict = array(255, 1, 3, 7, 15, 31, 63, 127);
+
+	/**
+	 * @var string  Underlying data
+	 *
+	 * @since 1.0.0
+	 */
+	private $data;
+
+	/**
+	 * @var integer  Size of the bit array
+	 *
+	 * @since 1.0.0
+	 */
+	private $size;
+
+	/**
+	 * Create a new bit array of the given size
+	 *
+	 * @param integer $size    The BitArray size
+	 * @param boolean $default The default value for bits
+	 *
+	 * @since 1.0.0
+	 */
+	protected function __construct($size = 0, $default = false)
+	{
+		$this->size = (int) $size;
+
+		if ($default) {
+			$this->data = str_repeat(chr(255), (int) ceil($this->size / 8));
+			$this->restrict();
+		} else {
+			$this->data = str_repeat(chr(0), (int) ceil($this->size / 8));
+		}
+	}
+
+	/**
+	 * Remove useless bits for simplifying count operation.
+	 *
+	 * @return BitArray  $this for chaining
+	 *
+	 * @since 1.2.0
+	 */
+	protected function restrict()
+	{
+		$length = strlen($this->data);
+
+		if ($length > 0) {
+			$this->data[$length - 1] = chr(ord($this->data[$length - 1]) & self::$restrict[$this->size % 8]);
+		}
+
+		return $this;
+	}
+
+	/**
+	 * Clone a BitArray
+	 *
+	 * @return void
+	 *
+	 * @since 1.0.0
+	 */
+	public function __clone()
+	{
+		$this->data = str_repeat($this->data, 1);
+	}
+
+	/**
+	 * Convert the object to a string
+	 *
+	 * @return string  String representation of this object
+	 *
+	 * @since 1.0.0
+	 */
+	public function __toString()
+	{
+		$string = str_repeat('0', $this->size);
+
+		for ($offset = 0; $offset < $this->size; $offset++) {
+			if (ord($this->data[(int) ($offset / 8)]) & (1 << $offset % 8)) {
+				$string[$offset] = '1';
+			}
+		}
+
+		return $string;
+	}
+
+	/**
+	 * 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 'size':
+				return $this->size;
+			case 'count':
+				return $this->count();
+			default:
+				throw new \RuntimeException('Undefined property');
+		}
+	}
+
+	/**
+	 * Test the existence of an index
+	 *
+	 * @param integer $offset The offset
+	 *
+	 * @return boolean  The truth value
+	 *
+	 * @since 1.0.0
+	 */
+	public function offsetExists($offset)
+	{
+		return is_int($offset) && $offset >= 0 && $offset < $this->size;
+	}
+
+	/**
+	 * Get the truth value for an index
+	 *
+	 * @param integer $offset The offset
+	 *
+	 * @return boolean  The truth value
+	 *
+	 * @throws OutOfRangeException  Argument index must be an positive integer lesser than the size
+	 *
+	 * @since 1.0.0
+	 */
+	public function offsetGet($offset)
+	{
+		if ($this->offsetExists($offset)) {
+			return (bool) (ord($this->data[(int) ($offset / 8)]) & (1 << $offset % 8));
+		} else {
+			throw new \OutOfRangeException('Argument offset must be a positive integer lesser than the size');
+		}
+	}
+
+	/**
+	 * Set the truth value for an index
+	 *
+	 * @param integer $offset The offset
+	 * @param boolean $value  The truth value
+	 *
+	 * @return void
+	 *
+	 * @throws OutOfRangeException  Argument index must be an positive integer lesser than the size
+	 *
+	 * @since 1.0.0
+	 */
+	public function offsetSet($offset, $value)
+	{
+		if ($this->offsetExists($offset)) {
+			$index = (int) ($offset / 8);
+
+			if ($value) {
+				$this->data[$index] = chr(ord($this->data[$index]) | (1 << $offset % 8));
+			} else {
+				$this->data[$index] = chr(ord($this->data[$index]) & ~(1 << $offset % 8));
+			}
+		} else {
+			throw new \OutOfRangeException('Argument index must be a positive integer lesser than the size');
+		}
+	}
+
+	/**
+	 * Unset the existence of an index
+	 *
+	 * @param integer $offset The index
+	 *
+	 * @return void
+	 *
+	 * @throws RuntimeException  Values cannot be unset
+	 *
+	 * @since 1.0.0
+	 */
+	public function offsetUnset($offset)
+	{
+		throw new \RuntimeException('Values cannot be unset');
+	}
+
+	/**
+	 * Return the number of true bits
+	 *
+	 * @return integer  The number of true bits
+	 *
+	 * @since 1.0.0
+	 */
+	public function count()
+	{
+		$count = 0;
+
+		for ($index = 0, $length = strlen($this->data); $index < $length; $index++) {
+			$count += self::$count[ord($this->data[$index])];
+		}
+
+		return $count;
+	}
+
+	/**
+	 * Transform the object to an array
+	 *
+	 * @return array  Array of values
+	 *
+	 * @since 1.1.0
+	 */
+	public function toArray()
+	{
+		$array = array();
+
+		for ($index = 0; $index < $this->size; $index++) {
+			$array[] = (bool) (ord($this->data[(int) ($index / 8)]) & (1 << $index % 8));
+		}
+
+		return $array;
+	}
+
+	/**
+	 * Serialize the object
+	 *
+	 * @return array  Array of values
+	 *
+	 * @since 1.0.0
+	 */
+	public function jsonSerialize()
+	{
+		return $this->toArray();
+	}
+
+	/**
+	 * Get an iterator
+	 *
+	 * @return Iterator  Iterator
+	 *
+	 * @since 1.0.0
+	 */
+	public function getIterator()
+	{
+		return new Iterator($this);
+	}
+
+	/**
+	 * Return the size
+	 *
+	 * @return integer  The size
+	 *
+	 * @since 1.0.0
+	 */
+	public function size()
+	{
+		return $this->size;
+	}
+
+	/**
+	 * Copy bits directly from a BitArray
+	 *
+	 * @param BitArray $bits   A BitArray to copy
+	 * @param int      $index  Starting index for destination
+	 * @param int      $offset Starting index for copying
+	 * @param int      $size   Copy size
+	 *
+	 * @return BitArray  This object for chaining
+	 *
+	 * @throws OutOfRangeException  Argument index must be an positive integer lesser than the size
+	 *
+	 * @since 1.1.0
+	 */
+	public function directCopy(BitArray $bits, $index = 0, $offset = 0, $size = 0)
+	{
+		if ($offset > $index) {
+			for ($i = 0; $i < $size; $i++) {
+				$this[$i + $index] = $bits[$i + $offset];
+			}
+		} else {
+			for ($i = $size - 1; $i >= 0; $i--) {
+				$this[$i + $index] = $bits[$i + $offset];
+			}
+		}
+
+		return $this;
+	}
+
+	/**
+	 * Copy bits from a BitArray
+	 *
+	 * * if index is non-negative, the index parameter is used as it is,
+	 *   keeping its real value between 0 and size-1;
+	 * * if index is negative, the index parameter starts from the end,
+	 *   keeping its real value between 0 and size-1.
+	 *
+	 * * if offset is non-negative, the offset parameter is used as it is,
+	 *   keeping its positive value between 0 and size-1;
+	 * * if offset is negative, the offset parameter starts from the end,
+	 *   keeping its real value between 0 and size-1.
+	 *
+	 * * if size is given and is positive, then the copy will copy size elements.
+	 * * if the bits argument is shorter than the size, then only the available elements will be copied.
+	 * * if size is given and is negative, then the copy starts from the end.
+	 * * if size is omitted, then the copy will have everything from offset up
+	 *   until the end of the bits argument.
+	 *
+	 * @param BitArray $bits   A BitArray to copy
+	 * @param int      $index  Starting index for destination.
+	 * @param int      $offset Starting index for copying.
+	 * @param mixed    $size   Copy size.
+	 *
+	 * @return BitArray  This object for chaining
+	 *
+	 * @since 1.1.0
+	 */
+	public function copy(BitArray $bits, $index = 0, $offset = 0, $size = null)
+	{
+		$index = $this->getRealOffset($index);
+		$offset = $bits->getRealOffset($offset);
+		$size = $bits->getRealSize($offset, $size);
+
+		if ($size > $this->size - $index) {
+			$size = $this->size - $index;
+		}
+
+		return $this->directCopy($bits, $index, $offset, $size);
+	}
+
+	/**
+	 * Get the real offset using a positive or negative offset
+	 *
+	 * * If offset is non-negative, the offset parameter is used as it is,
+	 *   keeping its real value between 0 and size-1.
+	 * * if offset is negative, the offset parameter starts from the end,
+	 *   keeping its real value between 0 and size-1.
+	 *
+	 * @param int $offset The offset
+	 *
+	 * @return integer  The real offset
+	 *
+	 * @since 1.1.0
+	 */
+	protected function getRealOffset($offset)
+	{
+		$offset = (int) $offset;
+
+		if ($offset < 0) {
+			// Start from the end
+			$offset = $this->size + $offset;
+
+			if ($offset < 0) {
+				$offset = 0;
+			}
+		} elseif ($offset > $this->size) {
+			$offset = $this->size;
+		}
+
+		return $offset;
+	}
+
+	/**
+	 * Get the real offset using a positive or negative offset
+	 *
+	 * * if size is given and is positive, then the real size will be between 0 and the current size-1.
+	 * * if size is given and is negative, then the real size starts from the end.
+	 * * if size is omitted, then the size goes until the end of the BitArray.
+	 *
+	 * @param int   $offset The real offset.
+	 * @param mixed $size   The size
+	 *
+	 * @return integer  The real size
+	 *
+	 * @since 1.1.0
+	 */
+	protected function getRealSize($offset, $size)
+	{
+		if ($size === null) {
+			$size = $this->size - $offset;
+		} else {
+			$size = (int) $size;
+
+			if ($size < 0) {
+				$size = $this->size + $size - $offset;
+
+				if ($size < 0) {
+					$size = 0;
+				}
+			} elseif ($size > $this->size - $offset) {
+				$size = $this->size - $offset;
+			}
+		}
+
+		return $size;
+	}
+
+	/**
+	 * Create a new BitArray from an integer
+	 *
+	 * @param integer $size    Size of the BitArray
+	 * @param boolean $default The default value for bits
+	 *
+	 * @return BitArray  A new BitArray
+	 *
+	 * @since 1.0.0
+	 */
+	public static function fromInteger($size, $default = false)
+	{
+		return new BitArray($size, (bool) $default);
+	}
+
+	/**
+	 * Create a new BitArray from a sequence of bits.
+	 *
+	 * @param integer $size   Size of the BitArray
+	 * @param integer $values The values for the bits
+	 *
+	 * @return BitArray  A new BitArray
+	 *
+	 * @since 1.2.0
+	 */
+	public static function fromDecimal($size, $values = 0)
+	{
+		$php_bit_size = PHP_INT_SIZE * 8;
+		$size = min((int) $size, $php_bit_size);
+		$values <<= ($php_bit_size - $size);
+		$bits = new BitArray($size);
+
+		for ($i = 0; $i < ceil($size / 8); $i++) {
+			$value = ($values & (0xff << ($php_bit_size - 8))) >> ($php_bit_size - 8);
+			$reverse = 0;
+			for ($j = 0; $j < 8; $j++) {
+				if ($value & (1 << $j)) {
+					$reverse |= 1 << (7 - $j);
+				}
+			}
+			$bits->data[$i] = chr($reverse);
+			$values <<= 8;
+		}
+
+		return $bits;
+	}
+
+	/**
+	 * Create a new BitArray from a traversable
+	 *
+	 * @param mixed $traversable A traversable and countable
+	 *
+	 * @return BitArray  A new BitArray
+	 *
+	 * @since 1.0.0
+	 */
+	public static function fromTraversable($traversable)
+	{
+		$bits = new BitArray(count($traversable));
+		$offset = 0;
+		$ord = 0;
+
+		foreach ($traversable as $value) {
+			if ($value) {
+				$ord |= 1 << $offset % 8;
+			}
+
+			if ($offset % 8 === 7) {
+				$bits->data[(int) ($offset / 8)] = chr($ord);
+				$ord = 0;
+			}
+
+			$offset++;
+		}
+
+		if ($offset % 8 !== 0) {
+			$bits->data[(int) ($offset / 8)] = chr($ord);
+		}
+
+		return $bits;
+	}
+
+	/**
+	 * Create a new BitArray from a bit string
+	 *
+	 * @param string $string A bit string
+	 *
+	 * @return BitArray  A new BitArray
+	 *
+	 * @since 1.0.0
+	 */
+	public static function fromString($string)
+	{
+		$bits = new BitArray(strlen($string));
+		$ord = 0;
+
+		for ($offset = 0; $offset < $bits->size; $offset++) {
+			if ($string[$offset] !== '0') {
+				$ord |= 1 << $offset % 8;
+			}
+
+			if ($offset % 8 === 7) {
+				$bits->data[(int) ($offset / 8)] = chr($ord);
+				$ord = 0;
+			}
+		}
+
+		if ($offset % 8 !== 0) {
+			$bits->data[(int) ($offset / 8)] = chr($ord);
+		}
+
+		return $bits;
+	}
+
+	/**
+	 * Create a new BitArray from json
+	 *
+	 * @param string $json A json encoded value
+	 *
+	 * @return BitArray  A new BitArray
+	 *
+	 * @since 1.0.0
+	 */
+	public static function fromJson($json)
+	{
+		return self::fromTraversable(json_decode($json));
+	}
+
+	/**
+	 * Create a new BitArray using a slice
+	 *
+	 * * if offset is non-negative, the slice will start at that offset in the bits argument.
+	 * * if offset is negative, the slice will start from the end of the bits argument.
+	 *
+	 * * if size is given and is positive, then the slice will have up to that many elements in it.
+	 * * if the bits argument is shorter than the size, then only the available elements will be present.
+	 * * if size is given and is negative,
+	 *   then the slice will stop that many elements from the end of the bits argument.
+	 * * if size is omitted,
+	 *   then the slice will have everything from offset up until the end of the bits argument.
+	 *
+	 * @param BitArray $bits   A BitArray to get the slice
+	 * @param int      $offset The offset
+	 * @param mixed    $size   The size
+	 *
+	 * @return BitArray  A new BitArray
+	 *
+	 * @since 1.1.0
+	 */
+	public static function fromSlice(BitArray $bits, $offset = 0, $size = null)
+	{
+		$offset = $bits->getRealOffset($offset);
+		$size = $bits->getRealSize($offset, $size);
+		$slice = new BitArray($size);
+
+		return $slice->directCopy($bits, 0, $offset, $size);
+	}
+
+	/**
+	 * Create a new BitArray using the concat operation
+	 *
+	 * @param BitArray $bits1 A BitArray
+	 * @param BitArray $bits2 A BitArray
+	 *
+	 * @return BitArray  A new BitArray
+	 *
+	 * @since 1.1.0
+	 */
+	public static function fromConcat(BitArray $bits1, BitArray $bits2)
+	{
+		$size = $bits1->size + $bits2->size;
+		$concat = new BitArray($size);
+		$concat->directCopy($bits1, 0, 0, $bits1->size);
+		$concat->directCopy($bits2, $bits1->size, 0, $bits2->size);
+
+		return $concat;
+	}
+
+	/**
+	 * Complement the bit array
+	 *
+	 * @return BitArray  This object for chaining
+	 *
+	 * @since 1.0.0
+	 */
+	public function applyComplement()
+	{
+		$length = strlen($this->data);
+
+		for ($index = 0; $index < $length; $index++) {
+			$this->data[$index] = chr(~ ord($this->data[$index]));
+		}
+
+		return $this->restrict();
+	}
+
+	/**
+	 * Or with an another bit array
+	 *
+	 * @param BitArray $bits A bit array
+	 *
+	 * @return BitArray  This object for chaining
+	 *
+	 * @throws InvalidArgumentException  Argument must be of equal size
+	 *
+	 * @since 1.0.0
+	 */
+	public function applyOr(BitArray $bits)
+	{
+		if ($this->size == $bits->size) {
+			$length = strlen($this->data);
+
+			for ($index = 0; $index < $length; $index++) {
+				$this->data[$index] = chr(ord($this->data[$index]) | ord($bits->data[$index]));
+			}
+
+			return $this;
+		} else {
+			throw new \InvalidArgumentException('Argument must be of equal size');
+		}
+	}
+
+	/**
+	 * And with an another bit array
+	 *
+	 * @param BitArray $bits A bit array
+	 *
+	 * @return BitArray  This object for chaining
+	 *
+	 * @throws InvalidArgumentException  Argument must be of equal size
+	 *
+	 * @since 1.0.0
+	 */
+	public function applyAnd(BitArray $bits)
+	{
+		if ($this->size == $bits->size) {
+			$length = strlen($this->data);
+
+			for ($index = 0; $index < $length; $index++) {
+				$this->data[$index] = chr(ord($this->data[$index]) & ord($bits->data[$index]));
+			}
+
+			return $this;
+		} else {
+			throw new \InvalidArgumentException('Argument must be of equal size');
+		}
+	}
+
+	/**
+	 * Xor with an another bit array
+	 *
+	 * @param BitArray $bits A bit array
+	 *
+	 * @return BitArray  This object for chaining
+	 *
+	 * @throws InvalidArgumentException  Argument must be of equal size
+	 *
+	 * @since 1.0.0
+	 */
+	public function applyXor(BitArray $bits)
+	{
+		if ($this->size == $bits->size) {
+			$length = strlen($this->data);
+
+			for ($index = 0; $index < $length; $index++) {
+				$this->data[$index] = chr(ord($this->data[$index]) ^ ord($bits->data[$index]));
+			}
+
+			return $this;
+		} else {
+			throw new \InvalidArgumentException('Argument must be of equal size');
+		}
+	}
+
+	/**
+	 * Shift a bit array.
+	 *
+	 * Negative value means the shifting is done right to left
+	 * while positive value means the shifting is done left to right.
+	 *
+	 * @param int     $size  Size to shift.
+	 *
+	 * @param boolean $value Value to shift
+	 *
+	 * @return BitArray  $this for chaining
+	 *
+	 * @since 1.2.0
+	 */
+	public function shift($size = 1, $value = false)
+	{
+		$size = (int) $size;
+
+		if ($size > 0) {
+			$min = min($this->size, $size);
+
+			for ($i = $this->size - 1; $i >= $min; $i--) {
+				$this[$i] = $this[$i - $min];
+			}
+
+			for ($i = 0; $i < $min; $i++) {
+				$this[$i] = $value;
+			}
+		} else {
+			$min = min($this->size, -$size);
+
+			for ($i = 0; $i < $this->size - $min; $i++) {
+				$this[$i] = $this[$i + $min];
+			}
+
+			for ($i = $this->size - $min; $i < $this->size; $i++) {
+				$this[$i] = $value;
+			}
+		}
+
+		return $this;
+	}
 }