Generated on Sat Feb 7 2015 02:01:29 for Gecode by doxygen 1.8.9.1
reg.cpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  *
6  * Copyright:
7  * Christian Schulte, 2004
8  *
9  * Last modified:
10  * $Date: 2014-10-03 11:23:08 +0200 (Fri, 03 Oct 2014) $ by $Author: schulte $
11  * $Revision: 14236 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #include <gecode/minimodel.hh>
39 
40 namespace Gecode {
41 
42  namespace MiniModel {
43 
44  class PosSet;
49 
50  class NodeInfo;
51  class PosInfo;
52 
53  }
54 
56  class REG::Exp {
57  public:
59  unsigned int use_cnt;
61  int _n_pos;
65  enum ExpType {
70  };
74  union {
76  int symbol;
78  Exp* kids[2];
79  } data;
80 
85  static void inc(Exp* e);
87  static void dec(Exp* e);
89  static int n_pos(Exp* e);
91  template<class Char, class Traits>
92  std::basic_ostream<Char,Traits>&
93  print(std::basic_ostream<Char,Traits>& os) const;
94 
95  static void* operator new(size_t);
96  static void operator delete(void*);
97  private:
99  void dispose(void);
100  };
101 
102 
103  /*
104  * Operations on expression nodes
105  *
106  */
107 
108 
109  forceinline void*
110  REG::Exp::operator new(size_t s) {
111  return heap.ralloc(s);
112  }
113  forceinline void
114  REG::Exp::operator delete(void*) {
115  // Deallocation happens in dispose
116  }
117 
118  void
119  REG::Exp::dispose(void) {
121  todo.push(this);
122  while (!todo.empty()) {
123  Exp* e = todo.pop();
124  switch (e->type) {
125  case ET_OR:
126  case ET_CONC:
127  if ((e->data.kids[1] != NULL) && (--e->data.kids[1]->use_cnt == 0))
128  todo.push(e->data.kids[1]);
129  case ET_STAR:
130  if ((e->data.kids[0] != NULL) && (--e->data.kids[0]->use_cnt == 0))
131  todo.push(e->data.kids[0]);
132  default: ;
133  }
134  heap.rfree(e);
135  }
136  }
137 
138  forceinline void
140  if (e != NULL)
141  e->use_cnt++;
142  }
143  forceinline void
145  if ((e != NULL) && (--e->use_cnt == 0))
146  e->dispose();
147  }
148 
149 
150  forceinline int
152  return (e != NULL) ? e->_n_pos : 0;
153  }
154 
155 
156  /*
157  * Regular expressions
158  *
159  */
160 
162  REG::REG(Exp* f) : e(f) {}
163 
164  REG::REG(void) : e(NULL) {}
165 
166  REG::REG(const REG& r) : e(r.e) {
167  REG::Exp::inc(e);
168  }
169 
170  const REG&
172  if (&r != this) {
173  REG::Exp::inc(r.e);
174  REG::Exp::dec(e);
175  e = r.e;
176  }
177  return *this;
178  }
179 
180  REG::~REG(void) {
181  REG::Exp::dec(e);
182  }
183 
184  REG::REG(int s) : e(new Exp) {
185  e->use_cnt = 1;
186  e->_n_pos = 1;
188  e->data.symbol = s;
189  }
190 
191  REG::REG(const IntArgs& x) {
192  int n = x.size();
193  if (n < 1)
194  throw MiniModel::TooFewArguments("REG");
195  Exp** a = heap.alloc<Exp*>(n);
196  // Initialize with symbols
197  for (int i=n; i--; ) {
198  a[i] = new Exp();
199  a[i]->use_cnt = 1;
200  a[i]->_n_pos = 1;
201  a[i]->type = REG::Exp::ET_SYMBOL;
202  a[i]->data.symbol = x[i];
203  }
204  // Build a balanced tree of alternative nodes
205  for (int m=n; m>1; ) {
206  if (m & 1) {
207  m -= 1;
208  Exp* e1 = a[m];
209  Exp* e2 = a[0];
210  a[0] = new Exp;
211  a[0]->use_cnt = 1;
212  a[0]->_n_pos = REG::Exp::n_pos(e1) + REG::Exp::n_pos(e2);
213  a[0]->type = REG::Exp::ET_OR;
214  a[0]->data.kids[0] = e1;
215  a[0]->data.kids[1] = e2;
216  } else {
217  m >>= 1;
218  for (int i=0; i<m; i++) {
219  Exp* e1 = a[2*i];
220  Exp* e2 = a[2*i+1];
221  a[i] = new Exp;
222  a[i]->use_cnt = 1;
223  a[i]->_n_pos = REG::Exp::n_pos(e1) + REG::Exp::n_pos(e2);
224  a[i]->type = REG::Exp::ET_OR;
225  a[i]->data.kids[0] = e1;
226  a[i]->data.kids[1] = e2;
227  }
228  }
229  }
230  e = a[0];
231  heap.free<Exp*>(a,n);
232  }
233 
234  REG
235  REG::operator |(const REG& r2) {
236  if (e == r2.e)
237  return *this;
238  Exp* f = new Exp();
239  f->use_cnt = 1;
240  f->_n_pos = REG::Exp::n_pos(e) + REG::Exp::n_pos(r2.e);
241  f->type = REG::Exp::ET_OR;
242  f->data.kids[0] = e; REG::Exp::inc(e);
243  f->data.kids[1] = r2.e; REG::Exp::inc(r2.e);
244  REG r(f);
245  return r;
246  }
247 
248  REG&
249  REG::operator |=(const REG& r2) {
250  if (e == r2.e)
251  return *this;
252  Exp* f = new Exp();
253  f->use_cnt = 1;
254  f->_n_pos = REG::Exp::n_pos(e) + REG::Exp::n_pos(r2.e);
255  f->type = REG::Exp::ET_OR;
256  f->data.kids[0] = e;
257  f->data.kids[1] = r2.e; REG::Exp::inc(r2.e);
258  e=f;
259  return *this;
260  }
261 
262  REG
263  REG::operator +(const REG& r2) {
264  if (e == NULL) return r2;
265  if (r2.e == NULL) return *this;
266  Exp* f = new Exp();
267  f->use_cnt = 1;
268  f->_n_pos = REG::Exp::n_pos(e) + REG::Exp::n_pos(r2.e);
269  f->type = REG::Exp::ET_CONC;
270  f->data.kids[0] = e; REG::Exp::inc(e);
271  f->data.kids[1] = r2.e; REG::Exp::inc(r2.e);
272  REG r(f);
273  return r;
274  }
275 
276  REG&
277  REG::operator +=(const REG& r2) {
278  if (r2.e == NULL)
279  return *this;
280  if (e == NULL) {
281  e=r2.e; REG::Exp::inc(e);
282  } else {
283  Exp* f = new Exp();
284  f->use_cnt = 1;
285  f->_n_pos = REG::Exp::n_pos(e) + REG::Exp::n_pos(r2.e);
286  f->type = REG::Exp::ET_CONC;
287  f->data.kids[0] = e;
288  f->data.kids[1] = r2.e; REG::Exp::inc(r2.e);
289  e=f;
290  }
291  return *this;
292  }
293 
294  REG
296  if ((e == NULL) || (e->type == REG::Exp::ET_STAR))
297  return *this;
298  Exp* f = new Exp();
299  f->use_cnt = 1;
300  f->_n_pos = REG::Exp::n_pos(e);
301  f->type = REG::Exp::ET_STAR;
302  f->data.kids[0] = e; REG::Exp::inc(e);
303  REG r(f);
304  return r;
305  }
306 
307  REG
308  REG::operator ()(unsigned int n, unsigned int m) {
309  REG r;
310  if ((n>m) || (m == 0))
311  return r;
312  if (n>0) {
313  unsigned int i = n;
314  REG r0 = *this;
315  while (i>0)
316  if (i & 1) {
317  r = r0+r; i--;
318  } else {
319  r0 = r0+r0; i >>= 1;
320  }
321  }
322  if (m > n) {
323  unsigned int i = m-n;
324  REG s0;
325  s0 = s0 | *this;
326  REG s;
327  while (i>0)
328  if (i & 1) {
329  s = s0+s; i--;
330  } else {
331  s0 = s0+s0; i >>= 1;
332  }
333  r = r + s;
334  }
335  return r;
336  }
337 
338  REG
339  REG::operator ()(unsigned int n) {
340  REG r;
341  if (n > 0) {
342  REG r0 = *this;
343  unsigned int i = n;
344  while (i>0)
345  if (i & 1) {
346  r = r0+r; i--;
347  } else {
348  r0 = r0+r0; i >>= 1;
349  }
350  }
351  return r+**this;
352  }
353 
354  REG
356  return this->operator ()(1);
357  }
358 
359 
360  namespace MiniModel {
361 
362  /*
363  * Sets of positions
364  *
365  */
366 
370  enum PosSetCmp {
374  };
375 
379  class PosSet : public Support::BlockClient<PosSet,Heap> {
380  // Maintain sets of positions in inverse order
381  // This makes the check whether the last position is included
382  // more efficient.
383  public:
384  int pos; PosSet* next;
385 
386  PosSet(void);
387  PosSet(int);
388 
389  bool in(int) const;
390  static PosSetCmp cmp(PosSet*,PosSet*);
391  static PosSet* cup(PosSetAllocator&,PosSet*,PosSet*);
392  };
393 
394 
396  PosSet::PosSet(void) {}
398  PosSet::PosSet(int p) : pos(p), next(NULL) {}
399 
400 
401  forceinline bool
402  PosSet::in(int p) const {
403  for (const PosSet* ps = this; ps != NULL; ps = ps->next)
404  if (ps->pos == p) {
405  return true;
406  } else if (ps->pos < p) {
407  return false;
408  }
409  return false;
410  }
411 
413  PosSet::cmp(PosSet* ps1, PosSet* ps2) {
414  while ((ps1 != NULL) && (ps2 != NULL)) {
415  if (ps1 == ps2)
416  return PSC_EQ;
417  if (ps1->pos < ps2->pos)
418  return PSC_LE;
419  if (ps1->pos > ps2->pos)
420  return PSC_GR;
421  ps1 = ps1->next; ps2 = ps2->next;
422  }
423  if (ps1 == ps2)
424  return PSC_EQ;
425  return ps1 == NULL ? PSC_LE : PSC_GR;
426  }
427 
428  PosSet*
430  PosSet* ps;
431  PosSet** p = &ps;
432  while ((ps1 != NULL) && (ps2 != NULL)) {
433  if (ps1 == ps2) {
434  *p = ps1; return ps;
435  }
436  PosSet* n = new (psm) PosSet;
437  *p = n; p = &n->next;
438  if (ps1->pos == ps2->pos) {
439  n->pos = ps1->pos;
440  ps1 = ps1->next; ps2 = ps2->next;
441  } else if (ps1->pos > ps2->pos) {
442  n->pos = ps1->pos; ps1 = ps1->next;
443  } else {
444  n->pos = ps2->pos; ps2 = ps2->next;
445  }
446  }
447  *p = (ps1 != NULL) ? ps1 : ps2;
448  return ps;
449  }
450 
451 
453  class NodeInfo {
454  public:
455  bool nullable;
458  NodeInfo(bool n=false, PosSet* fp=NULL, PosSet* lp=NULL);
459  };
460 
462  class ExpInfo {
463  public:
465  bool open;
466  ExpInfo(REG::Exp* e=NULL);
467  };
468 
473  class PosInfo {
474  public:
475  int symbol;
477  };
478 
481  : nullable(n), firstpos(fp), lastpos(lp) {}
482 
485  : exp(e), open(true) {}
486 
487  }
488 
491  MiniModel::PosInfo* pi) {
492  int p=0;
493 
494  using MiniModel::PosSet;
495  using MiniModel::NodeInfo;
496  using MiniModel::ExpInfo;
497 
500 
501  // Start with first expression to be processed
502  todo.push(ExpInfo(this));
503 
504  do {
505  if (todo.top().exp == NULL) {
506  todo.pop();
507  done.push(NodeInfo(true,NULL,NULL));
508  } else {
509  switch (todo.top().exp->type) {
510  case ET_SYMBOL:
511  {
512  pi[p].symbol = todo.pop().exp->data.symbol;
513  PosSet* ps = new (psm) PosSet(p++);
514  done.push(NodeInfo(false,ps,ps));
515  }
516  break;
517  case ET_STAR:
518  if (todo.top().open) {
519  // Evaluate subexpression recursively
520  todo.top().open = false;
521  todo.push(todo.top().exp->data.kids[0]);
522  } else {
523  todo.pop();
524  NodeInfo ni = done.pop();
525  for (PosSet* ps = ni.lastpos; ps != NULL; ps = ps->next)
526  pi[ps->pos].followpos =
527  PosSet::cup(psm,pi[ps->pos].followpos,ni.firstpos);
528  done.push(NodeInfo(true,ni.firstpos,ni.lastpos));
529  }
530  break;
531  case ET_CONC:
532  if (todo.top().open) {
533  // Evaluate subexpressions recursively
534  todo.top().open = false;
535  REG::Exp* e = todo.top().exp;
536  todo.push(e->data.kids[1]);
537  todo.push(e->data.kids[0]);
538  } else {
539  todo.pop();
540  NodeInfo ni1 = done.pop();
541  NodeInfo ni0 = done.pop();
542  for (PosSet* ps = ni0.lastpos; ps != NULL; ps = ps->next)
543  pi[ps->pos].followpos =
544  PosSet::cup(psm,pi[ps->pos].followpos,ni1.firstpos);
545  done.push(NodeInfo(ni0.nullable & ni1.nullable,
546  ni0.nullable ?
547  PosSet::cup(psm,ni0.firstpos,ni1.firstpos) : ni0.firstpos,
548  ni1.nullable ?
549  PosSet::cup(psm,ni0.lastpos,ni1.lastpos) : ni1.lastpos));
550  }
551  break;
552  case ET_OR:
553  if (todo.top().open) {
554  // Evaluate subexpressions recursively
555  todo.top().open = false;
556  REG::Exp* e = todo.top().exp;
557  todo.push(e->data.kids[1]);
558  todo.push(e->data.kids[0]);
559  } else {
560  todo.pop();
561  NodeInfo ni1 = done.pop();
562  NodeInfo ni0 = done.pop();
563  done.push(NodeInfo(ni0.nullable | ni1.nullable,
564  PosSet::cup(psm,ni0.firstpos,ni1.firstpos),
565  PosSet::cup(psm,ni0.lastpos,ni1.lastpos)));
566  }
567  break;
568  default: GECODE_NEVER;
569  }
570  }
571  } while (!todo.empty());
572  return done.top().firstpos;
573  }
574 
575 
576  namespace MiniModel {
577 
578  class StateNode;
579 
584 
588  class StateNode : public Support::BlockClient<StateNode,Heap> {
589  public:
591  int state;
595  };
596 
600  class StatePool {
601  public:
602  int n_states;
606 
607  StatePool(PosSet*);
608 
609  StateNode* pop(void);
610  bool empty(void) const;
611 
612  int state(StatePoolAllocator&, PosSet*);
613  };
614 
616  StatePool::StatePool(PosSet* ps) {
617  next = &root;
618  all = NULL;
619  n_states = 1;
620  root.pos = ps;
621  root.state = 0;
622  root.next = NULL;
623  root.left = NULL;
624  root.right = NULL;
625  }
626 
628  StatePool::pop(void) {
629  StateNode* n = next;
630  next = n->next;
631  n->next = all;
632  all = n;
633  return n;
634  }
635 
636  forceinline bool
637  StatePool::empty(void) const {
638  return next == NULL;
639  }
640 
641  forceinline int
642  StatePool::state(StatePoolAllocator& spm, PosSet* ps) {
643  int d = 0;
644  StateNode** p = NULL;
645  StateNode* n = &root;
646  do {
647  switch (PosSet::cmp(ps,n->pos)) {
648  case PSC_EQ: return n->state;
649  case PSC_LE: p = &n->left; n = *p; break;
650  case PSC_GR: p = &n->right; n = *p; break;
651  default: GECODE_NEVER;
652  }
653  d++;
654  } while (n != NULL);
655  n = new (spm) StateNode; *p = n;
656  n->pos = ps;
657  n->state = n_states++;
658  n->next = next;
659  n->left = NULL;
660  n->right = NULL;
661  next = n;
662  return n->state;
663  }
664 
668  class SymbolsInc {
669  public:
670  forceinline bool
671  operator ()(int x, int y) {
672  return x < y;
673  }
674  forceinline static void
675  sort(int s[], int n) {
676  SymbolsInc o;
677  Support::quicksort<int,SymbolsInc>(s,n,o);
678  }
679  };
680 
681 
687  private:
689  int n;
690  public:
691  TransitionBag(void);
692  void add(int,int,int);
693  void finish(void);
694  DFA::Transition* transitions(void);
695  };
696 
698  TransitionBag::TransitionBag(void) : t(heap), n(0) {}
699 
700  forceinline void
701  TransitionBag::add(int i_state, int symbol, int o_state) {
702  t[n].i_state = i_state;
703  t[n].symbol = symbol;
704  t[n].o_state = o_state;
705  n++;
706  }
707 
708  forceinline void
710  t[n].i_state = -1;
711  }
712 
715  return &t[0];
716  }
717 
718 
723  class FinalBag {
724  private:
726  int n;
727  public:
728  FinalBag(void);
729  void add(int);
730  void finish(void);
731  int* finals(void);
732  };
733 
735  FinalBag::FinalBag(void) : f(heap), n(0) {}
736 
737  forceinline void
738  FinalBag::add(int state) {
739  f[n++] = state;
740  }
741 
742  forceinline void
744  f[n] = -1;
745  }
746 
747  forceinline int*
749  return &f[0];
750  }
751 
752  }
753 
754  REG::operator DFA(void) {
757  using MiniModel::PosInfo;
758  using MiniModel::PosSet;
759  using MiniModel::NodeInfo;
760 
761  using MiniModel::StatePool;
762  using MiniModel::StateNode;
763 
765  using MiniModel::FinalBag;
766 
767  using MiniModel::SymbolsInc;
768 
769  PosSetAllocator psm(heap);
771  REG r = *this + REG(Int::Limits::max+1);
772  int n_pos = REG::Exp::n_pos(r.e);
773 
774  PosInfo* pi = heap.alloc<PosInfo>(n_pos);
775  for (int i=n_pos; i--; )
776  pi[i].followpos = NULL;
777 
778  PosSet* firstpos = r.e->followpos(psm,&pi[0]);
779 
780  // Compute symbols
781  int* symbols = heap.alloc<int>(n_pos);
782  for (int i=n_pos; i--; )
783  symbols[i] = pi[i].symbol;
784 
785  SymbolsInc::sort(&symbols[0],n_pos-1);
786  int n_symbols = 1;
787  for (int i = 1; i<n_pos-1; i++)
788  if (symbols[i-1] != symbols[i])
789  symbols[n_symbols++] = symbols[i];
790 
791  // Compute states and transitions
792  TransitionBag tb;
793  StatePool sp(firstpos);
794  while (!sp.empty()) {
795  StateNode* sn = sp.pop();
796  for (int i = n_symbols; i--; ) {
797  PosSet* u = NULL;
798  for (PosSet* ps = sn->pos; ps != NULL; ps = ps->next)
799  if (pi[ps->pos].symbol == symbols[i])
800  u = PosSet::cup(psm,u,pi[ps->pos].followpos);
801  if (u != NULL)
802  tb.add(sn->state,symbols[i],sp.state(spm,u));
803  }
804  }
805  tb.finish();
806 
807  // Compute final states
808  FinalBag fb;
809  for (StateNode* n = sp.all; n != NULL; n = n->next)
810  if (n->pos->in(n_pos-1))
811  fb.add(n->state);
812  fb.finish();
813 
814  heap.free<PosInfo>(pi,n_pos);
815  heap.free<int>(symbols,n_pos);
816  return DFA(0,tb.transitions(),fb.finals(),true);
817  }
818 
819 }
820 
821 // STATISTICS: minimodel-any
822 
Information on positions collected during traversal.
Definition: reg.cpp:473
union Gecode::REG::Exp::@62 data
Symbol or subexpressions.
NodeType t
Type of node.
Definition: bool-expr.cpp:234
PosSetCmp
Order on position sets.
Definition: reg.cpp:370
static PosSet * cup(PosSetAllocator &, PosSet *, PosSet *)
Definition: reg.cpp:429
ExpInfo(REG::Exp *e=NULL)
Definition: reg.cpp:484
static PosSetCmp cmp(PosSet *, PosSet *)
Definition: reg.cpp:413
void rfree(void *p)
Free memory block starting at p.
Definition: heap.hpp:355
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1662
Regular expressions over integer values.
Definition: minimodel.hh:1401
Exception: Too few arguments available in argument array
Definition: exception.hpp:49
Support::BlockAllocator< StateNode, Heap > StatePoolAllocator
Allocator for state nodes.
Definition: reg.cpp:578
bool pos(const View &x)
Test whether x is postive.
Definition: mult.hpp:45
REG & operator|=(const REG &r)
This expression or r.
Definition: reg.cpp:249
Exp * kids[2]
Subexpressions.
Definition: reg.cpp:78
void * ralloc(size_t s)
Allocate s bytes from heap.
Definition: heap.hpp:341
Support::BlockAllocator< PosSet, Heap > PosSetAllocator
Allocator for position sets.
Definition: reg.cpp:44
Array with arbitrary number of elements.
Expression information.
Definition: reg.cpp:462
const int max
Largest allowed integer value.
Definition: int.hh:113
bool in(int) const
Definition: reg.cpp:402
T & top(void) const
Return element on top of stack.
Heap heap
The single global heap.
Definition: heap.cpp:49
Gecode::IntSet d(v, 7)
Manage memory organized into block lists (allocator)
void sort(TaskViewArray< TaskView > &t)
Sort task view array t according to sto and inc (increasing or decreasing)
Definition: sort.hpp:137
Deterministic finite automaton (DFA)
Definition: int.hh:1881
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
T * alloc(long unsigned int n)
Allocate block of n objects of type T from heap.
Definition: heap.hpp:400
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
const REG & operator=(const REG &r)
Assign to regular expression r.
Definition: reg.cpp:171
static void dec(Exp *e)
Decrement use counter of e.
Definition: reg.cpp:144
void add(int, int, int)
Definition: reg.cpp:701
REG & operator+=(const REG &r)
This expression is followed by r.
Definition: reg.cpp:277
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
static int n_pos(Exp *e)
Return number of positions of e.
Definition: reg.cpp:151
REG(void)
Initialize as empty sequence (epsilon)
Definition: reg.cpp:164
State pool combines a tree of states together with yet unprocessed states
Definition: reg.cpp:600
T pop(void)
Pop topmost element from stack and return it.
ExpType type
Type of regular expression.
Definition: reg.cpp:72
REG operator|(const REG &r)
Return expression for: this expression or r.
Definition: reg.cpp:235
std::basic_ostream< Char, Traits > & print(std::basic_ostream< Char, Traits > &os) const
Print expression.
Definition: reg.hpp:42
Specification of a DFA transition.
Definition: int.hh:1887
static void inc(Exp *e)
Increment use counter of e.
Definition: reg.cpp:139
bool empty(void) const
Test whether stack is empty.
unsigned int use_cnt
Reference counter.
Definition: reg.cpp:59
Passing integer arguments.
Definition: int.hh:607
union Gecode::@518::NNF::@57 u
Union depending on nodetype t.
MiniModel::PosSet * followpos(MiniModel::PosSetAllocator &, MiniModel::PosInfo *)
Compute the follow positions.
Definition: reg.cpp:490
~REG(void)
Destructor.
Definition: reg.cpp:180
ExpType
Type of regular expression.
Definition: reg.cpp:65
void free(T *b, long unsigned int n)
Delete n objects starting at b.
Definition: heap.hpp:426
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
DFA::Transition * transitions(void)
Definition: reg.cpp:714
Client for block allocator of type T.
REG operator*(void)
Return expression for: this expression arbitrarily often (Kleene star)
Definition: reg.cpp:295
#define forceinline
Definition: config.hpp:132
Stack with arbitrary number of elements.
Implementation of the actual expression tree.
Definition: reg.cpp:56
For collecting transitions while constructing a DFA.
Definition: reg.cpp:686
Sets of positions.
Definition: reg.cpp:379
Node information computed during traversal of the expressions.
Definition: reg.cpp:453
REG operator+(void)
Return expression for: this expression at least once.
Definition: reg.cpp:355
Gecode toplevel namespace
REG operator()(unsigned int n, unsigned int m)
Return expression for: this expression at least n and at most m times.
Definition: reg.cpp:308
void exp(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
Definition: arithmetic.cpp:144
NodeInfo(bool n=false, PosSet *fp=NULL, PosSet *lp=NULL)
Definition: reg.cpp:480
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60
static void sort(int s[], int n)
Definition: reg.cpp:675
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.
int _n_pos
Number of positions.
Definition: reg.cpp:61
Node together with state information
Definition: reg.cpp:588
void push(const T &x)
Push element x on top of stack.
For collecting final states while constructing a DFA.
Definition: reg.cpp:723
int symbol
Symbol.
Definition: reg.cpp:76