ReplaceConverter::getRoot() - Code Metrics - Riimu/Kit-BaseConversion - Measure and Improve Code Quality continuously with Scrutinizer

ReplaceConverter::getRoot() A
last analyzed 2017-07-15 13:47 UTC

↳ Parent: ReplaceConverter

Complexity

Conditions	4
Paths	3

Size

Total Lines	14
Code Lines	7

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	7
CRAP Score	4

Importance

Changes

Metric	Value
dl	0
loc	14
ccs	7
cts	7
cp	1
rs	9.2
c	0
b	0
f	0
cc	4
eloc	7
nc	3
nop	2
crap	4

<?php

namespace Riimu\Kit\BaseConversion;

/**
 * Converts numbers using character replacement.
 *
 * ReplaceConverter converts numbers from base to another using a simple string
 * replacement strategy. In other words. The digits from one base is simply
 * replaced with digits from the other base. This strategy, however, is only
 * possible if the two number bases share a common root or if the target number
 * base is nth root of the source base. This is required, because it allows
 * a sequence of digits to be simply replaced with an appropriate sequence of
 * digits from the other number base.
 *
 * When possible, the replacement strategy offers considerable speed gains over
 * strategies that employ arbitrary-precision arithmetic as there is no need
 * to calculate anything.
 *
 * Note the replacement conversion strategy can always convert fractions
 * accurately. Setting the precision for ReplaceConverter has no effect at all
 * on the conversion results.
 *
 * @author Riikka Kalliomäki <[email protected]>
 * @copyright Copyright (c) 2014-2017 Riikka Kalliomäki
 * @license http://opensource.org/licenses/mit-license.php MIT License
 */
class ReplaceConverter implements Converter
{
    /** @var NumberBase Number base used by provided numbers */
    private $source;

    /** @var NumberBase Number base used by returned numbers */
    private $target;

    /** @var ReplaceConverter Converter used to convert into common root base */
    private $sourceConverter;

    /** @var ReplaceConverter Converter used to convert from common root base */
    private $targetConverter;

    /** @var array<string,string> String replacement table for converting numbers */
    private $conversionTable;

    /**
     * Create new instance of ReplaceConverter.
     *
     * ReplaceConverter only supports number base combinations that have a
     * common root or if the target base is nth root of the source base. In
     * addition, due to using string replacement, any number base that has
     * conflicting string digits are not supported.
     *
     * @param NumberBase $source Number base used by the provided numbers
     * @param NumberBase $target Number base used by the returned numbers
     * @throws InvalidNumberBaseException If the number bases are not supported
     */
    public function __construct(NumberBase $source, NumberBase $target)
    {
        $root = $this->getRoot($source, $target);

        if ($root !== $source->getRadix() && $root !== $target->getRadix()) {
            $proxy = new NumberBase($root);
            $this->sourceConverter = new self($source, $proxy);
            $this->targetConverter = new self($proxy, $target);
        } else {
            $this->source = $source;
            $this->target = $target;
            $this->conversionTable = $this->buildConversionTable();
        }
    }

    /**
     * Determines the common root for the number bases.
     * @param NumberBase $source Number base used by the provided numbers
     * @param NumberBase $target Number base used by the returned numbers
     * @return int The common root for the number bases
     * @throws InvalidNumberBaseException If the number bases are not supported
     */
    private function getRoot(NumberBase $source, NumberBase $target)
    {
        if ($source->hasStringConflict() || $target->hasStringConflict()) {
            throw new InvalidNumberBaseException('Number bases do not support string presentation');
        }

        $root = $source->findCommonRadixRoot($target);

        if ($root === false) {
            throw new InvalidNumberBaseException('No common root exists between number bases');
        }

        return $root;
    }

    /**
     * Creates string replacement table between source base and target base.
     * @return array<string,string> String replacement table for converting numbers
     */
    private function buildConversionTable()
    {
        if ($this->source->getRadix() > $this->target->getRadix()) {
            return $this->createTable($this->source->getDigitList(), $this->target->getDigitList());
        }

        return array_flip($this->createTable($this->target->getDigitList(), $this->source->getDigitList()));
    }

    /**
     * Creates a conversion table between two lists of digits.
     * @param string[] $source Digits for the number base with larger number of digits
     * @param string[] $target Digits for the number base with smaller number of digits
     * @return array<string,string> String replacement table for converting numbers
     */
    private function createTable($source, $target)
    {
        $last = count($target) - 1;
        $size = (int) log(count($source), count($target));
        $number = array_fill(0, $size, $target[0]);
        $next = array_fill(0, $size, 0);
        $limit = count($source);
        $table = [$source[0] => implode('', $number)];

        for ($i = 1; $i < $limit; $i++) {
            for ($j = $size - 1; $next[$j] === $last; $j--) {
                $number[$j] = $target[0];
                $next[$j] = 0;
            }

            $number[$j] = $target[++$next[$j]];
            $table[$source[$i]] = implode('', $number);
        }

        return $table;
    }

    public function setPrecision($precision)
    {
        // Replace converter always converts accurately
    }

    public function convertInteger(array $number)
    {
        return $this->convert($number, false);
    }

    public function convertFractions(array $number)
    {
        return $this->convert($number, true);
    }

    /**
     * Converts the digits from source base to target base.
     * @param array $number The digits to convert
     * @param bool $fractions True if converting fractions, false if not
     * @return array The digits converted to target base
     */
    private function convert(array $number, $fractions = false)
    {
        if (!isset($this->conversionTable)) {
            return $this->targetConverter->replace(
                $this->sourceConverter->replace($number, $fractions),
                $fractions
            );
        }

        return $this->replace($number, $fractions);
    }

    /**
     * Replace digits using string replacement.
     * @param array $number The digits to convert
     * @param bool $fractions True if converting fractions, false if not
     * @return array The digits converted to target base
     */
    private function replace(array $number, $fractions = false)
    {
        return $this->zeroTrim($this->target->splitString(strtr(implode('', $this->zeroPad(
            $this->source->canonizeDigits($number),
            $fractions
        )), $this->conversionTable)), $fractions);
    }

    /**
     * Pads the digits to correct count for string replacement.
     * @param array $number Array of digits to pad
     * @param bool $right True to pad from right, false to pad from left
     * @return array Padded array of digits
     */
    private function zeroPad(array $number, $right)
    {
        $log = (int) log($this->target->getRadix(), $this->source->getRadix());

        if ($log > 1 && count($number) % $log) {
            $pad = count($number) + ($log - count($number) % $log);
            $number = array_pad($number, $right ? $pad : -$pad, $this->source->getDigit(0));
        }

        return $number;
    }

    /**
     * Trims extraneous zeroes from the digit list.
     * @param array $number Array of digits to trim
     * @param bool $right True to trim from right, false to trim from left
     * @return array Trimmed array of digits
     */
    private function zeroTrim(array $number, $right)
    {
        $zero = $this->target->getDigit(0);

        while (($right ? end($number) : reset($number)) === $zero) {
            unset($number[key($number)]);
        }

        return empty($number) ? [$zero] : array_values($number);
    }
}


1		<?php
2
3		namespace Riimu\Kit\BaseConversion;
4
5		/**
6		* Converts numbers using character replacement.
7		*
8		* ReplaceConverter converts numbers from base to another using a simple string
9		* replacement strategy. In other words. The digits from one base is simply
10		* replaced with digits from the other base. This strategy, however, is only
11		* possible if the two number bases share a common root or if the target number
12		* base is nth root of the source base. This is required, because it allows
13		* a sequence of digits to be simply replaced with an appropriate sequence of
14		* digits from the other number base.
15		*
16		* When possible, the replacement strategy offers considerable speed gains over
17		* strategies that employ arbitrary-precision arithmetic as there is no need
18		* to calculate anything.
19		*
20		* Note the replacement conversion strategy can always convert fractions
21		* accurately. Setting the precision for ReplaceConverter has no effect at all
22		* on the conversion results.
23		*
24		* @author Riikka Kalliomäki <[email protected]>
25		* @copyright Copyright (c) 2014-2017 Riikka Kalliomäki
26		* @license http://opensource.org/licenses/mit-license.php MIT License
27		*/
28		class ReplaceConverter implements Converter
29		{
30		/** @var NumberBase Number base used by provided numbers */
31		private $source;
32
33		/** @var NumberBase Number base used by returned numbers */
34		private $target;
35
36		/** @var ReplaceConverter Converter used to convert into common root base */
37		private $sourceConverter;
38
39		/** @var ReplaceConverter Converter used to convert from common root base */
40		private $targetConverter;
41
42		/** @var array<string,string> String replacement table for converting numbers */
43		private $conversionTable;
44
45		/**
46		* Create new instance of ReplaceConverter.
47		*
48		* ReplaceConverter only supports number base combinations that have a
49		* common root or if the target base is nth root of the source base. In
50		* addition, due to using string replacement, any number base that has
51		* conflicting string digits are not supported.
52		*
53		* @param NumberBase $source Number base used by the provided numbers
54		* @param NumberBase $target Number base used by the returned numbers
55		* @throws InvalidNumberBaseException If the number bases are not supported
56		*/
57	126	public function __construct(NumberBase $source, NumberBase $target)
58		{
59	126	$root = $this->getRoot($source, $target);
60
61	108	if ($root !== $source->getRadix() && $root !== $target->getRadix()) {
62	45	$proxy = new NumberBase($root);
63	45	$this->sourceConverter = new self($source, $proxy);
64	45	$this->targetConverter = new self($proxy, $target);
65	15	} else {
66	108	$this->source = $source;
67	108	$this->target = $target;
68	108	$this->conversionTable = $this->buildConversionTable();
69		}
70	108	}
71
72		/**
73		* Determines the common root for the number bases.
74		* @param NumberBase $source Number base used by the provided numbers
75		* @param NumberBase $target Number base used by the returned numbers
76		* @return int The common root for the number bases
77		* @throws InvalidNumberBaseException If the number bases are not supported
78		*/
79	126	private function getRoot(NumberBase $source, NumberBase $target)
80		{
81	126	if ($source->hasStringConflict() \|\| $target->hasStringConflict()) {
82	3	throw new InvalidNumberBaseException('Number bases do not support string presentation');
83		}
84
85	123	$root = $source->findCommonRadixRoot($target);
86
87	123	if ($root === false) {
88	21	throw new InvalidNumberBaseException('No common root exists between number bases');
89		}
90
91	108	return $root;
92		}
93
94		/**
95		* Creates string replacement table between source base and target base.
96		* @return array<string,string> String replacement table for converting numbers
97		*/
98	108	private function buildConversionTable()
99		{
100	108	if ($this->source->getRadix() > $this->target->getRadix()) {
101	78	return $this->createTable($this->source->getDigitList(), $this->target->getDigitList());
102		}
103
104	99	return array_flip($this->createTable($this->target->getDigitList(), $this->source->getDigitList()));
105		}
106
107		/**
108		* Creates a conversion table between two lists of digits.
109		* @param string[] $source Digits for the number base with larger number of digits
110		* @param string[] $target Digits for the number base with smaller number of digits
111		* @return array<string,string> String replacement table for converting numbers
112		*/
113	108	private function createTable($source, $target)
114		{
115	108	$last = count($target) - 1;
116	108	$size = (int) log(count($source), count($target));
117	108	$number = array_fill(0, $size, $target[0]);
118	108	$next = array_fill(0, $size, 0);
119	108	$limit = count($source);
120	108	$table = [$source[0] => implode('', $number)];
121
122	108	for ($i = 1; $i < $limit; $i++) {
123	108	for ($j = $size - 1; $next[$j] === $last; $j--) {
124	93	$number[$j] = $target[0];
125	93	$next[$j] = 0;
126	31	}
127
128	108	$number[$j] = $target[++$next[$j]];
129	108	$table[$source[$i]] = implode('', $number);
130	36	}
131
132	108	return $table;
133		}
134
135	12	public function setPrecision($precision)
136		{
137		// Replace converter always converts accurately
138	12	}
139
140	75	public function convertInteger(array $number)
141		{
142	75	return $this->convert($number, false);
143		}
144
145	45	public function convertFractions(array $number)
146		{
147	45	return $this->convert($number, true);
148		}
149
150		/**
151		* Converts the digits from source base to target base.
152		* @param array $number The digits to convert
153		* @param bool $fractions True if converting fractions, false if not
154		* @return array The digits converted to target base
155		*/
156	93	private function convert(array $number, $fractions = false)
157		{
158	93	if (!isset($this->conversionTable)) {
159	39	return $this->targetConverter->replace(
160	39	$this->sourceConverter->replace($number, $fractions),
161	13	$fractions
162	13	);
163		}
164
165	54	return $this->replace($number, $fractions);
166		}
167
168		/**
169		* Replace digits using string replacement.
170		* @param array $number The digits to convert
171		* @param bool $fractions True if converting fractions, false if not
172		* @return array The digits converted to target base
173		*/
174	93	private function replace(array $number, $fractions = false)
175		{
176	93	return $this->zeroTrim($this->target->splitString(strtr(implode('', $this->zeroPad(
177	93	$this->source->canonizeDigits($number),
178	29	$fractions
179	87	)), $this->conversionTable)), $fractions);
180		}
181
182		/**
183		* Pads the digits to correct count for string replacement.
184		* @param array $number Array of digits to pad
185		* @param bool $right True to pad from right, false to pad from left
186		* @return array Padded array of digits
187		*/
188	87	private function zeroPad(array $number, $right)
189		{
190	87	$log = (int) log($this->target->getRadix(), $this->source->getRadix());
191
192	87	if ($log > 1 && count($number) % $log) {
193	48	$pad = count($number) + ($log - count($number) % $log);
194	48	$number = array_pad($number, $right ? $pad : -$pad, $this->source->getDigit(0));
195	16	}
196
197	87	return $number;
198		}
199
200		/**
201		* Trims extraneous zeroes from the digit list.
202		* @param array $number Array of digits to trim
203		* @param bool $right True to trim from right, false to trim from left
204		* @return array Trimmed array of digits
205		*/
206	87	private function zeroTrim(array $number, $right)
207		{
208	87	$zero = $this->target->getDigit(0);
209
210	87	while (($right ? end($number) : reset($number)) === $zero) {
211	60	unset($number[key($number)]);
212	20	}
213
214	87	return empty($number) ? [$zero] : array_values($number);
215		}
216		}
217

Riimu / Kit-BaseConversion

ReplaceConverter::getRoot() A last analyzed 2017-07-15 13:47 UTC

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like

ReplaceConverter::getRoot() A
last analyzed 2017-07-15 13:47 UTC