1<?php
2
3/**
4 * Hoa
5 *
6 *
7 * @license
8 *
9 * New BSD License
10 *
11 * Copyright © 2007-2017, Hoa community. All rights reserved.
12 *
13 * Redistribution and use in source and binary forms, with or without
14 * modification, are permitted provided that the following conditions are met:
15 *     * Redistributions of source code must retain the above copyright
16 *       notice, this list of conditions and the following disclaimer.
17 *     * Redistributions in binary form must reproduce the above copyright
18 *       notice, this list of conditions and the following disclaimer in the
19 *       documentation and/or other materials provided with the distribution.
20 *     * Neither the name of the Hoa nor the names of its contributors may be
21 *       used to endorse or promote products derived from this software without
22 *       specific prior written permission.
23 *
24 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
25 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS AND CONTRIBUTORS BE
28 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
29 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
30 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
31 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
32 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
33 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
34 * POSSIBILITY OF SUCH DAMAGE.
35 */
36
37namespace Hoa\Compiler\Llk\Sampler;
38
39use Hoa\Compiler;
40use Hoa\Math;
41use Hoa\Visitor;
42
43/**
44 * Class \Hoa\Compiler\Llk\Sampler\Uniform.
45 *
46 * This generator aims at producing random and uniform a sequence of a fixed
47 * size. We use the recursive method to count all possible sub-structures of
48 * size n. The counting helps to compute cumulative distribution functions,
49 * which guide the exploration.
50 * Repetition unfolding: upper bound of + and * is set to n.
51 *
52 * @copyright  Copyright © 2007-2017 Hoa community
53 * @license    New BSD License
54 */
55class Uniform extends Sampler
56{
57    /**
58     * Data (pre-computing).
59     *
60     * @var array
61     */
62    protected $_data   = [];
63
64    /**
65     * Bound.
66     *
67     * @var int
68     */
69    protected $_length = 5;
70
71
72
73    /**
74     * Construct a generator.
75     *
76     * @param   \Hoa\Compiler\Llk\Parser  $compiler        Compiler/parser.
77     * @param   \Hoa\Visitor\Visit        $tokenSampler    Token sampler.
78     */
79    public function __construct(
80        Compiler\Llk\Parser $compiler,
81        Visitor\Visit       $tokenSampler,
82        $length = 5
83    ) {
84        parent::__construct($compiler, $tokenSampler);
85
86        foreach ($this->_rules as $name => $_) {
87            $this->_data[$name] = [];
88        }
89
90        $this->setLength($length);
91        $this->_sampler = new Math\Sampler\Random();
92
93        return;
94    }
95
96    /**
97     * The random and uniform algorithm.
98     *
99     * @param   \Hoa\Compiler\Llk\Rule  $rule    Rule to start.
100     * @param   int                     $n       Size.
101     * @return  string
102     */
103    public function uniform(Compiler\Llk\Rule $rule = null, $n = -1)
104    {
105        if (null === $rule && -1 === $n) {
106            $rule = $this->_rules[$this->_rootRuleName];
107            $n    = $this->getLength();
108        }
109
110        $data     = &$this->_data[$rule->getName()][$n];
111        $computed = $data['n'];
112
113        if (0 === $n || 0 === $computed) {
114            return null;
115        }
116
117        if ($rule instanceof Compiler\Llk\Rule\Choice) {
118            $children = $rule->getChildren();
119            $stat     = [];
120
121            foreach ($children as $c => $child) {
122                $stat[$c] = $this->_data[$child][$n]['n'];
123            }
124
125            $i = $this->_sampler->getInteger(1, $computed);
126
127            for ($e = 0, $b = $stat[$e], $max = count($stat) - 1;
128                $e < $max && $i > $b;
129                $b += $stat[++$e]);
130
131            return $this->uniform($this->_rules[$children[$e]], $n);
132        } elseif ($rule instanceof Compiler\Llk\Rule\Concatenation) {
133            $children  = $rule->getChildren();
134            $out       = null;
135            $Γ         = $data['Γ'];
136            $γ         = $Γ[$this->_sampler->getInteger(0, count($Γ) - 1)];
137
138            foreach ($children as $i => $child) {
139                $out .= $this->uniform($this->_rules[$child], $γ[$i]);
140            }
141
142            return $out;
143        } elseif ($rule instanceof Compiler\Llk\Rule\Repetition) {
144            $out   =  null;
145            $stat  = &$data['xy'];
146            $child =  $this->_rules[$rule->getChildren()];
147            $b     =  0;
148            $i     =  $this->_sampler->getInteger(1, $computed);
149
150            foreach ($stat as $α => $st) {
151                if ($i <= $b += $st['n']) {
152                    break;
153                }
154            }
155
156            $Γ = &$st['Γ'];
157            $γ = &$Γ[$this->_sampler->getInteger(0, count($Γ) - 1)];
158
159            for ($j = 0; $j < $α; ++$j) {
160                $out .= $this->uniform($child, $γ[$j]);
161            }
162
163            return $out;
164        } elseif ($rule instanceof Compiler\Llk\Rule\Token) {
165            return $this->generateToken($rule);
166        }
167
168        return null;
169    }
170
171    /**
172     * Recursive method applied to our problematic.
173     *
174     * @param   \Hoa\Compiler\Llk\Rule  $rule    Rule to start.
175     * @param   int                     $n       Size.
176     * @return  int
177     */
178    public function count(Compiler\Llk\Rule $rule = null, $n = -1)
179    {
180        if (null === $rule || -1 === $n) {
181            return 0;
182        }
183
184        $ruleName = $rule->getName();
185
186        if (isset($this->_data[$ruleName][$n])) {
187            return $this->_data[$ruleName][$n]['n'];
188        }
189
190        $this->_data[$ruleName][$n] =  ['n' => 0];
191        $out                        = &$this->_data[$ruleName][$n]['n'];
192        $rule                       =  $this->_rules[$ruleName];
193
194        if ($rule instanceof Compiler\Llk\Rule\Choice) {
195            foreach ($rule->getChildren() as $child) {
196                $out += $this->count($this->_rules[$child], $n);
197            }
198        } elseif ($rule instanceof Compiler\Llk\Rule\Concatenation) {
199            $children = $rule->getChildren();
200            $Γ        = new Math\Combinatorics\Combination\Gamma(
201                count($children),
202                $n
203            );
204            $this->_data[$ruleName][$n]['Γ'] = [];
205            $handle                          = &$this->_data[$ruleName][$n]['Γ'];
206
207            foreach ($Γ as $γ) {
208                $oout = 1;
209
210                foreach ($γ as $α => $_γ) {
211                    $oout *= $this->count($this->_rules[$children[$α]], $_γ);
212                }
213
214                if (0 !== $oout) {
215                    $handle[] = $γ;
216                }
217
218                $out += $oout;
219            }
220        } elseif ($rule instanceof Compiler\Llk\Rule\Repetition) {
221            $this->_data[$ruleName][$n]['xy'] = [];
222            $handle                           = &$this->_data[$ruleName][$n]['xy'];
223            $child                            =  $this->_rules[$rule->getChildren()];
224            $x                                =  $rule->getMin();
225            $y                                =  $rule->getMax();
226
227            if (-1 === $y) {
228                $y = $n;
229            } else {
230                $y = min($n, $y);
231            }
232
233            if (0 === $x && $x === $y) {
234                $out = 1;
235            } else {
236                for ($α = $x; $α <= $y; ++$α) {
237                    $ut         = 0;
238                    $handle[$α] = ['n' => 0, 'Γ' => []];
239                    $Γ          = new Math\Combinatorics\Combination\Gamma($α, $n);
240
241                    foreach ($Γ as $γ) {
242                        $oout = 1;
243
244                        foreach ($γ as $β => $_γ) {
245                            $oout *= $this->count($child, $_γ);
246                        }
247
248                        if (0 !== $oout) {
249                            $handle[$α]['Γ'][] = $γ;
250                        }
251
252                        $ut += $oout;
253                    }
254
255                    $handle[$α]['n']  = $ut;
256                    $out             += $ut;
257                }
258            }
259        } elseif ($rule instanceof Compiler\Llk\Rule\Token) {
260            $out = Math\Util::δ($n, 1);
261        }
262
263        return $out;
264    }
265
266    /**
267     * Set upper-bound, the maximum data length.
268     *
269     * @param   int  $length    Length.
270     * @return  int
271     * @throws  \Hoa\Compiler\Exception
272     */
273    public function setLength($length)
274    {
275        if (0 >= $length) {
276            throw new Exception(
277                'Length must be greater than 0, given %d.',
278                0,
279                $length
280            );
281        }
282
283        $old           = $this->_length;
284        $this->_length = $length;
285        $this->count(
286            $this->_compiler->getRule($this->_rootRuleName),
287            $length
288        );
289
290        return $old;
291    }
292
293    /**
294     * Get upper-bound.
295     *
296     * @return  int
297     */
298    public function getLength()
299    {
300        return $this->_length;
301    }
302}
303