Hoa central
Public Member Functions | Protected Member Functions | Protected Attributes | List of all members
Hoa\Compiler\Llk\Sampler\BoundedExhaustive Class Reference
Inheritance diagram for Hoa\Compiler\Llk\Sampler\BoundedExhaustive:

Public Member Functions

 __construct (Compiler\Llk\Parser $compiler, Visitor\Visit $tokenSampler, $length=5)
 
 current ()
 
 key ()
 
 next ()
 
 rewind ()
 
 valid ()
 
 setLength ($length)
 
 getLength ()
 
- Public Member Functions inherited from Hoa\Compiler\Llk\Sampler\Sampler
 __construct (Compiler\Llk\Parser $compiler, Visitor\Visit $tokenSampler)
 
 getCompiler ()
 

Protected Member Functions

 unfold ()
 
 boundedExhaustive (Compiler\Llk\Rule $rule, $next)
 
 backtrack ()
 
- Protected Member Functions inherited from Hoa\Compiler\Llk\Sampler\Sampler
 completeToken (Compiler\Llk\Rule\Token $token)
 
 setCurrentNamespace ($namespace)
 
 generateToken (Compiler\Llk\Rule\Token $token)
 

Protected Attributes

 $_todo = null
 
 $_trace = null
 
 $_key = -1
 
 $_current = null
 
 $_length = 5
 
- Protected Attributes inherited from Hoa\Compiler\Llk\Sampler\Sampler
 $_compiler = null
 
 $_tokens = null
 
 $_rules = null
 
 $_tokenSampler = null
 
 $_rootRuleName = null
 
 $_currentNamespace = 'default'
 

Detailed Description

Class .

This generator aims at producing all possible data (exhaustive) up to a given size n (bounded). This algorithm is based on multiset (set with repetition). Repetition unfolding: upper bound of + and * is set to n.

Definition at line 54 of file BoundedExhaustive.php.

Constructor & Destructor Documentation

Hoa\Compiler\Llk\Sampler\BoundedExhaustive::__construct ( Compiler\Llk\Parser  $compiler,
Visitor\Visit  $tokenSampler,
  $length = 5 
)

Construct a generator.

Parameters
\Hoa\Compiler\Llk\Parser$compilerCompiler/parser.
\Hoa\Visitor\Visit$tokenSamplerToken sampler.
Returns
void

Definition at line 102 of file BoundedExhaustive.php.

106  {
107  parent::__construct($compiler, $tokenSampler);
108  $this->setLength($length);
109 
110  return;
111  }

Here is the call graph for this function:

Member Function Documentation

Hoa\Compiler\Llk\Sampler\BoundedExhaustive::backtrack ( )
protected

Backtrack to the previous choice-point.

Returns
bool

Definition at line 348 of file BoundedExhaustive.php.

349  {
350  $found = false;
351 
352  do {
353  $last = array_pop($this->_trace);
354 
355  if ($last instanceof Compiler\Llk\Rule\Entry) {
356  $rule = $this->_rules[$last->getRule()];
357  $found = $rule instanceof Compiler\Llk\Rule\Choice;
358  } elseif ($last instanceof Compiler\Llk\Rule\Ekzit) {
359  $rule = $this->_rules[$last->getRule()];
360  $found = $rule instanceof Compiler\Llk\Rule\Repetition;
361  }
362  } while (0 < count($this->_trace) && false === $found);
363 
364  if (false === $found) {
365  return false;
366  }
367 
368  $rule = $last->getRule();
369  $next = $last->getData() + 1;
370  $this->_todo = $last->getTodo();
371  $this->_todo[] = new Compiler\Llk\Rule\Entry(
372  $rule,
373  $next,
374  $this->_todo
375  );
376 
377  return true;
378  }

Here is the caller graph for this function:

Hoa\Compiler\Llk\Sampler\BoundedExhaustive::boundedExhaustive ( Compiler\Llk\Rule  $rule,
  $next 
)
protected

The bounded-exhaustive algorithm.

Parameters
\Hoa\Compiler\Llk\Rule$ruleRule to cover.
int$nextNext rule.
Returns
bool

Definition at line 222 of file BoundedExhaustive.php.

223  {
224  $content = $rule->getContent();
225 
226  if ($rule instanceof Compiler\Llk\Rule\Repetition) {
227  if (0 === $next) {
228  $this->_trace[] = new Compiler\Llk\Rule\Entry(
229  $rule->getName(),
230  $rule->getMin()
231  );
232 
233  array_pop($this->_todo);
234  $this->_todo[] = new Compiler\Llk\Rule\Ekzit(
235  $rule->getName(),
236  $rule->getMin(),
238  );
239 
240  for ($i = 0, $min = $rule->getMin(); $i < $min; ++$i) {
241  $this->_todo[] = new Compiler\Llk\Rule\Ekzit(
242  $content,
243  0
244  );
245  $this->_todo[] = new Compiler\Llk\Rule\Entry(
246  $content,
247  0
248  );
249  }
250  } else {
251  $nbToken = 0;
252 
253  foreach ($this->_trace as $trace) {
254  if ($trace instanceof Compiler\Llk\Rule\Token) {
255  ++$nbToken;
256  }
257  }
258 
259  $max = $rule->getMax();
260 
261  if (-1 != $max && $next > $max) {
262  return false;
263  }
264 
265  $this->_todo[] = new Compiler\Llk\Rule\Ekzit(
266  $rule->getName(),
267  $next,
269  );
270  $this->_todo[] = new Compiler\Llk\Rule\Ekzit(
271  $content,
272  0
273  );
274  $this->_todo[] = new Compiler\Llk\Rule\Entry(
275  $content,
276  0
277  );
278  }
279 
280  return true;
281  } elseif ($rule instanceof Compiler\Llk\Rule\Choice) {
282  if (count($content) <= $next) {
283  return false;
284  }
285 
286  $this->_trace[] = new Compiler\Llk\Rule\Entry(
287  $rule->getName(),
288  $next,
290  );
291  $nextRule = $content[$next];
292  $this->_todo[] = new Compiler\Llk\Rule\Ekzit(
293  $nextRule,
294  0
295  );
296  $this->_todo[] = new Compiler\Llk\Rule\Entry(
297  $nextRule,
298  0
299  );
300 
301  return true;
302  } elseif ($rule instanceof Compiler\Llk\Rule\Concatenation) {
303  $this->_trace[] = new Compiler\Llk\Rule\Entry(
304  $rule->getName(),
305  $next
306  );
307 
308  for ($i = count($content) - 1; $i >= 0; --$i) {
309  $nextRule = $content[$i];
310  $this->_todo[] = new Compiler\Llk\Rule\Ekzit(
311  $nextRule,
312  0
313  );
314  $this->_todo[] = new Compiler\Llk\Rule\Entry(
315  $nextRule,
316  0
317  );
318  }
319 
320  return true;
321  } elseif ($rule instanceof Compiler\Llk\Rule\Token) {
322  $nbToken = 0;
323 
324  foreach ($this->_trace as $trace) {
325  if ($trace instanceof Compiler\Llk\Rule\Token) {
326  ++$nbToken;
327  }
328  }
329 
330  if ($nbToken >= $this->getLength()) {
331  return false;
332  }
333 
334  $this->_trace[] = $rule;
335  array_pop($this->_todo);
336 
337  return true;
338  }
339 
340  return false;
341  }
$content
Definition: Hoa.php:119

Here is the call graph for this function:

Here is the caller graph for this function:

Hoa\Compiler\Llk\Sampler\BoundedExhaustive::current ( )

Get the current iterator value.

Returns
string

Definition at line 118 of file BoundedExhaustive.php.

Hoa\Compiler\Llk\Sampler\BoundedExhaustive::getLength ( )

Get upper-bound.

Returns
int

Definition at line 408 of file BoundedExhaustive.php.

Here is the caller graph for this function:

Hoa\Compiler\Llk\Sampler\BoundedExhaustive::key ( )

Get the current iterator key.

Returns
int

Definition at line 128 of file BoundedExhaustive.php.

Hoa\Compiler\Llk\Sampler\BoundedExhaustive::next ( )

Useless here.

Returns
void

Definition at line 138 of file BoundedExhaustive.php.

139  {
140  return;
141  }
Hoa\Compiler\Llk\Sampler\BoundedExhaustive::rewind ( )

Rewind the internal iterator pointer.

Returns
void

Definition at line 148 of file BoundedExhaustive.php.

149  {
150  $ruleName = $this->_rootRuleName;
151  $this->_current = null;
152  $this->_key = -1;
153  $this->_trace = [];
154  $handle = new Compiler\Llk\Rule\Ekzit($ruleName, 0);
155  $this->_todo = [
156  $handle,
157  new Compiler\Llk\Rule\Entry($ruleName, 0, [$handle])
158  ];
159 
160  return;
161  }
Hoa\Compiler\Llk\Sampler\BoundedExhaustive::setLength (   $length)

Set upper-bound, the maximum data length.

Parameters
int$lengthLength.
Returns
int
Exceptions

Definition at line 387 of file BoundedExhaustive.php.

388  {
389  if (0 >= $length) {
390  throw new Exception(
391  'Length must be greater than 0, given %d.',
392  0,
393  $length
394  );
395  }
396 
397  $old = $this->_length;
398  $this->_length = $length;
399 
400  return $old;
401  }

Here is the caller graph for this function:

Hoa\Compiler\Llk\Sampler\BoundedExhaustive::unfold ( )
protected

Unfold rules from the todo stack.

Returns
bool

Definition at line 193 of file BoundedExhaustive.php.

194  {
195  while (0 < count($this->_todo)) {
196  $pop = array_pop($this->_todo);
197 
198  if ($pop instanceof Compiler\Llk\Rule\Ekzit) {
199  $this->_trace[] = $pop;
200  } else {
201  $ruleName = $pop->getRule();
202  $next = $pop->getData();
203  $rule = $this->_rules[$ruleName];
204  $out = $this->boundedExhaustive($rule, $next);
205 
206  if (true !== $out && true !== $this->backtrack()) {
207  return false;
208  }
209  }
210  }
211 
212  return true;
213  }
boundedExhaustive(Compiler\Llk\Rule $rule, $next)

Here is the call graph for this function:

Here is the caller graph for this function:

Hoa\Compiler\Llk\Sampler\BoundedExhaustive::valid ( )

Compute the current iterator value, i.e. generate a new solution.

Returns
bool

Definition at line 168 of file BoundedExhaustive.php.

169  {
170  if (false === $this->unfold()) {
171  return false;
172  }
173 
174  $handle = null;
175 
176  foreach ($this->_trace as $trace) {
177  if ($trace instanceof Compiler\Llk\Rule\Token) {
178  $handle .= $this->generateToken($trace);
179  }
180  }
181 
182  ++$this->_key;
183  $this->_current = $handle;
184 
185  return $this->backtrack();
186  }
generateToken(Compiler\Llk\Rule\Token $token)
Definition: Sampler.php:188

Here is the call graph for this function:

Member Data Documentation

Hoa\Compiler\Llk\Sampler\BoundedExhaustive::$_current = null
protected

Definition at line 84 of file BoundedExhaustive.php.

Hoa\Compiler\Llk\Sampler\BoundedExhaustive::$_key = -1
protected

Definition at line 77 of file BoundedExhaustive.php.

Hoa\Compiler\Llk\Sampler\BoundedExhaustive::$_length = 5
protected

Definition at line 91 of file BoundedExhaustive.php.

Hoa\Compiler\Llk\Sampler\BoundedExhaustive::$_todo = null
protected

Definition at line 63 of file BoundedExhaustive.php.

Hoa\Compiler\Llk\Sampler\BoundedExhaustive::$_trace = null
protected

Definition at line 70 of file BoundedExhaustive.php.


The documentation for this class was generated from the following file: