Generated on Sat Jan 12 2019 20:58:51 for Gecode by doxygen 1.8.13
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  * This file is part of Gecode, the generic constraint
10  * development environment:
11  * http://www.gecode.org
12  *
13  * Permission is hereby granted, free of charge, to any person obtaining
14  * a copy of this software and associated documentation files (the
15  * "Software"), to deal in the Software without restriction, including
16  * without limitation the rights to use, copy, modify, merge, publish,
17  * distribute, sublicense, and/or sell copies of the Software, and to
18  * permit persons to whom the Software is furnished to do so, subject to
19  * the following conditions:
20  *
21  * The above copyright notice and this permission notice shall be
22  * included in all copies or substantial portions of the Software.
23  *
24  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31  *
32  */
33 
34 #include <gecode/minimodel.hh>
35 
36 namespace Gecode {
37 
38  namespace MiniModel {
39 
40  class PosSet;
45 
46  class NodeInfo;
47  class PosInfo;
48 
49  }
50 
52  class REG::Exp {
53  public:
55  unsigned int use_cnt;
57  int _n_pos;
61  enum ExpType {
65  ET_STAR
66  };
70  union {
72  int symbol;
74  Exp* kids[2];
75  } data;
76 
81  static void inc(Exp* e);
83  static void dec(Exp* e);
85  static int n_pos(Exp* e);
87  void toString(std::ostringstream& os) const;
89  std::string toString(void) const;
90 
91  static void* operator new(size_t);
92  static void operator delete(void*);
93  private:
95  void dispose(void);
96  };
97 
98 
99  /*
100  * Operations on expression nodes
101  *
102  */
103 
104 
105  forceinline void*
106  REG::Exp::operator new(size_t s) {
107  return heap.ralloc(s);
108  }
109  forceinline void
110  REG::Exp::operator delete(void*) {
111  // Deallocation happens in dispose
112  }
113 
114  void
115  REG::Exp::dispose(void) {
116  Region region;
118  todo.push(this);
119  while (!todo.empty()) {
120  Exp* e = todo.pop();
121  switch (e->type) {
122  case ET_OR:
123  case ET_CONC:
124  if ((e->data.kids[1] != NULL) && (--e->data.kids[1]->use_cnt == 0))
125  todo.push(e->data.kids[1]);
126  case ET_STAR:
127  if ((e->data.kids[0] != NULL) && (--e->data.kids[0]->use_cnt == 0))
128  todo.push(e->data.kids[0]);
129  default: ;
130  }
131  heap.rfree(e);
132  }
133  }
134 
135  forceinline void
137  if (e != NULL)
138  e->use_cnt++;
139  }
140  forceinline void
142  if ((e != NULL) && (--e->use_cnt == 0))
143  e->dispose();
144  }
145 
146 
147  forceinline int
149  return (e != NULL) ? e->_n_pos : 0;
150  }
151 
152  void
153  REG::Exp::toString(std::ostringstream& os) const {
154  switch (type) {
155  case ET_SYMBOL:
156  os << "[" << data.symbol << "]";
157  return;
158  case ET_STAR:
159  {
160  bool par = ((data.kids[0] != NULL) &&
161  ((data.kids[0]->type == ET_CONC) ||
162  (data.kids[0]->type == ET_OR)));
163  os << (par ? "*(" : "*");
164  if (data.kids[0]==NULL) {
165  os << "[]";
166  } else {
167  data.kids[0]->toString(os);
168  }
169  os << (par ? ")" : "");
170  return;
171  }
172  case ET_CONC:
173  {
174  bool par0 = ((data.kids[0] != NULL) &&
175  (data.kids[0]->type == ET_OR));
176  os << (par0 ? "(" : "");
177  if (data.kids[0]==NULL) {
178  os << "[]";
179  } else {
180  data.kids[0]->toString(os);
181  }
182  os << (par0 ? ")+" : "+");
183  bool par1 = ((data.kids[1] != NULL) &&
184  (data.kids[1]->type == ET_OR));
185  os << (par1 ? "(" : "");
186  if (data.kids[1]==NULL) {
187  os << "[]";
188  } else {
189  data.kids[1]->toString(os);
190  }
191  os << (par1 ? ")" : "");
192  return;
193  }
194  case ET_OR:
195  if (data.kids[0]==NULL) {
196  os << "[]";
197  } else {
198  data.kids[0]->toString(os);
199  }
200  os << "|";
201  if (data.kids[1]==NULL) {
202  os << "[]";
203  } else {
204  data.kids[1]->toString(os);
205  }
206  return;
207  default: GECODE_NEVER;
208  }
209  GECODE_NEVER;
210  return;
211  }
212 
213  std::string
214  REG::Exp::toString(void) const {
215  std::ostringstream os;
216  toString(os);
217  return os.str();
218  }
219 
220 
221  /*
222  * Regular expressions
223  *
224  */
225 
227  REG::REG(Exp* f) : e(f) {}
228 
229  REG::REG(void) : e(NULL) {}
230 
231  REG::REG(const REG& r) : e(r.e) {
232  REG::Exp::inc(e);
233  }
234 
235  const REG&
237  if (&r != this) {
238  REG::Exp::inc(r.e);
239  REG::Exp::dec(e);
240  e = r.e;
241  }
242  return *this;
243  }
244 
245  REG::~REG(void) {
246  REG::Exp::dec(e);
247  }
248 
249  REG::REG(int s) : e(new Exp) {
250  e->use_cnt = 1;
251  e->_n_pos = 1;
253  e->data.symbol = s;
254  }
255 
256  REG::REG(const IntArgs& x) {
257  int n = x.size();
258  if (n < 1)
259  throw MiniModel::TooFewArguments("REG");
260  Region region;
261  Exp** a = region.alloc<Exp*>(n);
262  // Initialize with symbols
263  for (int i=n; i--; ) {
264  a[i] = new Exp();
265  a[i]->use_cnt = 1;
266  a[i]->_n_pos = 1;
267  a[i]->type = REG::Exp::ET_SYMBOL;
268  a[i]->data.symbol = x[i];
269  }
270  // Build a balanced tree of alternative nodes
271  for (int m=n; m>1; ) {
272  if (m & 1) {
273  m -= 1;
274  Exp* e1 = a[m];
275  Exp* e2 = a[0];
276  a[0] = new Exp;
277  a[0]->use_cnt = 1;
278  a[0]->_n_pos = REG::Exp::n_pos(e1) + REG::Exp::n_pos(e2);
279  a[0]->type = REG::Exp::ET_OR;
280  a[0]->data.kids[0] = e1;
281  a[0]->data.kids[1] = e2;
282  } else {
283  m >>= 1;
284  for (int i=0; i<m; i++) {
285  Exp* e1 = a[2*i];
286  Exp* e2 = a[2*i+1];
287  a[i] = new Exp;
288  a[i]->use_cnt = 1;
289  a[i]->_n_pos = REG::Exp::n_pos(e1) + REG::Exp::n_pos(e2);
290  a[i]->type = REG::Exp::ET_OR;
291  a[i]->data.kids[0] = e1;
292  a[i]->data.kids[1] = e2;
293  }
294  }
295  }
296  e = a[0];
297  }
298 
299  REG
300  REG::operator |(const REG& r2) {
301  if (e == r2.e)
302  return *this;
303  Exp* f = new Exp();
304  f->use_cnt = 1;
305  f->_n_pos = REG::Exp::n_pos(e) + REG::Exp::n_pos(r2.e);
306  f->type = REG::Exp::ET_OR;
307  f->data.kids[0] = e; REG::Exp::inc(e);
308  f->data.kids[1] = r2.e; REG::Exp::inc(r2.e);
309  REG r(f);
310  return r;
311  }
312 
313  REG&
314  REG::operator |=(const REG& r2) {
315  if (e == r2.e)
316  return *this;
317  Exp* f = new Exp();
318  f->use_cnt = 1;
319  f->_n_pos = REG::Exp::n_pos(e) + REG::Exp::n_pos(r2.e);
320  f->type = REG::Exp::ET_OR;
321  f->data.kids[0] = e;
322  f->data.kids[1] = r2.e; REG::Exp::inc(r2.e);
323  e=f;
324  return *this;
325  }
326 
327  REG
328  REG::operator +(const REG& r2) {
329  if (e == NULL) return r2;
330  if (r2.e == NULL) return *this;
331  Exp* f = new Exp();
332  f->use_cnt = 1;
333  f->_n_pos = REG::Exp::n_pos(e) + REG::Exp::n_pos(r2.e);
334  f->type = REG::Exp::ET_CONC;
335  f->data.kids[0] = e; REG::Exp::inc(e);
336  f->data.kids[1] = r2.e; REG::Exp::inc(r2.e);
337  REG r(f);
338  return r;
339  }
340 
341  REG&
342  REG::operator +=(const REG& r2) {
343  if (r2.e == NULL)
344  return *this;
345  if (e == NULL) {
346  e=r2.e; REG::Exp::inc(e);
347  } else {
348  Exp* f = new Exp();
349  f->use_cnt = 1;
350  f->_n_pos = REG::Exp::n_pos(e) + REG::Exp::n_pos(r2.e);
351  f->type = REG::Exp::ET_CONC;
352  f->data.kids[0] = e;
353  f->data.kids[1] = r2.e; REG::Exp::inc(r2.e);
354  e=f;
355  }
356  return *this;
357  }
358 
359  REG
361  if ((e == NULL) || (e->type == REG::Exp::ET_STAR))
362  return *this;
363  Exp* f = new Exp();
364  f->use_cnt = 1;
365  f->_n_pos = REG::Exp::n_pos(e);
366  f->type = REG::Exp::ET_STAR;
367  f->data.kids[0] = e; REG::Exp::inc(e);
368  REG r(f);
369  return r;
370  }
371 
372  REG
373  REG::operator ()(unsigned int n, unsigned int m) {
374  REG r;
375  if ((n>m) || (m == 0))
376  return r;
377  if (n>0) {
378  unsigned int i = n;
379  REG r0 = *this;
380  while (i>0)
381  if (i & 1) {
382  r = r0+r; i--;
383  } else {
384  r0 = r0+r0; i >>= 1;
385  }
386  }
387  if (m > n) {
388  unsigned int i = m-n;
389  REG s0;
390  s0 = s0 | *this;
391  REG s;
392  while (i>0)
393  if (i & 1) {
394  s = s0+s; i--;
395  } else {
396  s0 = s0+s0; i >>= 1;
397  }
398  r = r + s;
399  }
400  return r;
401  }
402 
403  REG
404  REG::operator ()(unsigned int n) {
405  REG r;
406  if (n > 0) {
407  REG r0 = *this;
408  unsigned int i = n;
409  while (i>0)
410  if (i & 1) {
411  r = r0+r; i--;
412  } else {
413  r0 = r0+r0; i >>= 1;
414  }
415  }
416  return r+**this;
417  }
418 
419  REG
421  return this->operator ()(1);
422  }
423 
424  std::string
425  REG::toString(void) const {
426  if (e==NULL) {
427  return "[]";
428  }
429  return e->toString();
430  }
431 
432  namespace MiniModel {
433 
434  /*
435  * Sets of positions
436  *
437  */
438 
442  enum PosSetCmp {
446  };
447 
451  class PosSet : public Support::BlockClient<PosSet,Region> {
452  // Maintain sets of positions in inverse order
453  // This makes the check whether the last position is included
454  // more efficient.
455  public:
456  int pos; PosSet* next;
457 
458  PosSet(void);
459  PosSet(int);
460 
461  bool in(int) const;
462  static PosSetCmp cmp(PosSet*,PosSet*);
463  static PosSet* cup(PosSetAllocator&,PosSet*,PosSet*);
464  };
465 
466 
468  PosSet::PosSet(void) {}
470  PosSet::PosSet(int p) : pos(p), next(NULL) {}
471 
472 
473  forceinline bool
474  PosSet::in(int p) const {
475  for (const PosSet* ps = this; ps != NULL; ps = ps->next)
476  if (ps->pos == p) {
477  return true;
478  } else if (ps->pos < p) {
479  return false;
480  }
481  return false;
482  }
483 
485  PosSet::cmp(PosSet* ps1, PosSet* ps2) {
486  while ((ps1 != NULL) && (ps2 != NULL)) {
487  if (ps1 == ps2)
488  return PSC_EQ;
489  if (ps1->pos < ps2->pos)
490  return PSC_LE;
491  if (ps1->pos > ps2->pos)
492  return PSC_GR;
493  ps1 = ps1->next; ps2 = ps2->next;
494  }
495  if (ps1 == ps2)
496  return PSC_EQ;
497  return ps1 == NULL ? PSC_LE : PSC_GR;
498  }
499 
500  PosSet*
502  PosSet* ps;
503  PosSet** p = &ps;
504  while ((ps1 != NULL) && (ps2 != NULL)) {
505  if (ps1 == ps2) {
506  *p = ps1; return ps;
507  }
508  PosSet* n = new (psm) PosSet;
509  *p = n; p = &n->next;
510  if (ps1->pos == ps2->pos) {
511  n->pos = ps1->pos;
512  ps1 = ps1->next; ps2 = ps2->next;
513  } else if (ps1->pos > ps2->pos) {
514  n->pos = ps1->pos; ps1 = ps1->next;
515  } else {
516  n->pos = ps2->pos; ps2 = ps2->next;
517  }
518  }
519  *p = (ps1 != NULL) ? ps1 : ps2;
520  return ps;
521  }
522 
523 
525  class NodeInfo {
526  public:
527  bool nullable;
530  NodeInfo(bool n=false, PosSet* fp=NULL, PosSet* lp=NULL);
531  };
532 
534  class ExpInfo {
535  public:
537  bool open;
538  ExpInfo(REG::Exp* e=NULL);
539  };
540 
545  class PosInfo {
546  public:
547  int symbol;
549  };
550 
553  : nullable(n), firstpos(fp), lastpos(lp) {}
554 
557  : exp(e), open(true) {}
558 
559  }
560 
564  int p=0;
565 
566  using MiniModel::PosSet;
567  using MiniModel::NodeInfo;
568  using MiniModel::ExpInfo;
569 
570  Region region;
571 
574 
575  // Start with first expression to be processed
576  todo.push(ExpInfo(this));
577 
578  do {
579  if (todo.top().exp == NULL) {
580  todo.pop();
581  done.push(NodeInfo(true,NULL,NULL));
582  } else {
583  switch (todo.top().exp->type) {
584  case ET_SYMBOL:
585  {
586  pi[p].symbol = todo.pop().exp->data.symbol;
587  PosSet* ps = new (psm) PosSet(p++);
588  done.push(NodeInfo(false,ps,ps));
589  }
590  break;
591  case ET_STAR:
592  if (todo.top().open) {
593  // Evaluate subexpression recursively
594  todo.top().open = false;
595  todo.push(todo.top().exp->data.kids[0]);
596  } else {
597  todo.pop();
598  NodeInfo ni = done.pop();
599  for (PosSet* ps = ni.lastpos; ps != NULL; ps = ps->next)
600  pi[ps->pos].followpos =
601  PosSet::cup(psm,pi[ps->pos].followpos,ni.firstpos);
602  done.push(NodeInfo(true,ni.firstpos,ni.lastpos));
603  }
604  break;
605  case ET_CONC:
606  if (todo.top().open) {
607  // Evaluate subexpressions recursively
608  todo.top().open = false;
609  REG::Exp* e = todo.top().exp;
610  todo.push(e->data.kids[1]);
611  todo.push(e->data.kids[0]);
612  } else {
613  todo.pop();
614  NodeInfo ni1 = done.pop();
615  NodeInfo ni0 = done.pop();
616  for (PosSet* ps = ni0.lastpos; ps != NULL; ps = ps->next)
617  pi[ps->pos].followpos =
618  PosSet::cup(psm,pi[ps->pos].followpos,ni1.firstpos);
619  done.push(NodeInfo(ni0.nullable & ni1.nullable,
620  ni0.nullable ?
621  PosSet::cup(psm,ni0.firstpos,ni1.firstpos) : ni0.firstpos,
622  ni1.nullable ?
623  PosSet::cup(psm,ni0.lastpos,ni1.lastpos) : ni1.lastpos));
624  }
625  break;
626  case ET_OR:
627  if (todo.top().open) {
628  // Evaluate subexpressions recursively
629  todo.top().open = false;
630  REG::Exp* e = todo.top().exp;
631  todo.push(e->data.kids[1]);
632  todo.push(e->data.kids[0]);
633  } else {
634  todo.pop();
635  NodeInfo ni1 = done.pop();
636  NodeInfo ni0 = done.pop();
637  done.push(NodeInfo(ni0.nullable | ni1.nullable,
638  PosSet::cup(psm,ni0.firstpos,ni1.firstpos),
639  PosSet::cup(psm,ni0.lastpos,ni1.lastpos)));
640  }
641  break;
642  default: GECODE_NEVER;
643  }
644  }
645  } while (!todo.empty());
646  return done.top().firstpos;
647  }
648 
649 
650  namespace MiniModel {
651 
652  class StateNode;
653 
658 
662  class StateNode : public Support::BlockClient<StateNode,Heap> {
663  public:
665  int state;
669  };
670 
674  class StatePool {
675  public:
676  int n_states;
680 
681  StatePool(PosSet*);
682 
683  StateNode* pop(void);
684  bool empty(void) const;
685 
686  int state(StatePoolAllocator&, PosSet*);
687  };
688 
691  next = &root;
692  all = NULL;
693  n_states = 1;
694  root.pos = ps;
695  root.state = 0;
696  root.next = NULL;
697  root.left = NULL;
698  root.right = NULL;
699  }
700 
703  StateNode* n = next;
704  next = n->next;
705  n->next = all;
706  all = n;
707  return n;
708  }
709 
710  forceinline bool
711  StatePool::empty(void) const {
712  return next == NULL;
713  }
714 
715  forceinline int
716  StatePool::state(StatePoolAllocator& spm, PosSet* ps) {
717  int d = 0;
718  StateNode** p = NULL;
719  StateNode* n = &root;
720  do {
721  switch (PosSet::cmp(ps,n->pos)) {
722  case PSC_EQ: return n->state;
723  case PSC_LE: p = &n->left; n = *p; break;
724  case PSC_GR: p = &n->right; n = *p; break;
725  default: GECODE_NEVER;
726  }
727  d++;
728  } while (n != NULL);
729  n = new (spm) StateNode; *p = n;
730  n->pos = ps;
731  n->state = n_states++;
732  n->next = next;
733  n->left = NULL;
734  n->right = NULL;
735  next = n;
736  return n->state;
737  }
738 
742  class SymbolsInc {
743  public:
744  forceinline bool
745  operator ()(int x, int y) {
746  return x < y;
747  }
748  forceinline static void
749  sort(int s[], int n) {
750  SymbolsInc o;
751  Support::quicksort<int,SymbolsInc>(s,n,o);
752  }
753  };
754 
755 
761  private:
763  int n;
764  public:
765  TransitionBag(void);
766  void add(int,int,int);
767  void finish(void);
768  DFA::Transition* transitions(void);
769  };
770 
773 
774  forceinline void
775  TransitionBag::add(int i_state, int symbol, int o_state) {
776  t[n].i_state = i_state;
777  t[n].symbol = symbol;
778  t[n].o_state = o_state;
779  n++;
780  }
781 
782  forceinline void
784  t[n].i_state = -1;
785  }
786 
789  return &t[0];
790  }
791 
792 
797  class FinalBag {
798  private:
800  int n;
801  public:
802  FinalBag(void);
803  void add(int);
804  void finish(void);
805  int* finals(void);
806  };
807 
809  FinalBag::FinalBag(void) : f(heap), n(0) {}
810 
811  forceinline void
812  FinalBag::add(int state) {
813  f[n++] = state;
814  }
815 
816  forceinline void
818  f[n] = -1;
819  }
820 
821  forceinline int*
823  return &f[0];
824  }
825 
826  }
827 
828  REG::operator DFA(void) {
831  using MiniModel::PosInfo;
832  using MiniModel::PosSet;
833  using MiniModel::NodeInfo;
834 
835  using MiniModel::StatePool;
836  using MiniModel::StateNode;
837 
839  using MiniModel::FinalBag;
840 
841  using MiniModel::SymbolsInc;
842 
843  Region region;
844  PosSetAllocator psm(region);
846  REG r = *this + REG(Int::Limits::max+1);
847  int n_pos = REG::Exp::n_pos(r.e);
848 
849  PosInfo* pi = region.alloc<PosInfo>(n_pos);
850  for (int i=n_pos; i--; )
851  pi[i].followpos = NULL;
852 
853  PosSet* firstpos = r.e->followpos(psm,&pi[0]);
854 
855  // Compute symbols
856  int* symbols = region.alloc<int>(n_pos);
857  for (int i=n_pos; i--; )
858  symbols[i] = pi[i].symbol;
859 
860  SymbolsInc::sort(&symbols[0],n_pos-1);
861  int n_symbols = 1;
862  for (int i = 1; i<n_pos-1; i++)
863  if (symbols[i-1] != symbols[i])
864  symbols[n_symbols++] = symbols[i];
865 
866  // Compute states and transitions
867  TransitionBag tb;
868  StatePool sp(firstpos);
869  while (!sp.empty()) {
870  StateNode* sn = sp.pop();
871  for (int i = n_symbols; i--; ) {
872  PosSet* u = NULL;
873  for (PosSet* ps = sn->pos; ps != NULL; ps = ps->next)
874  if (pi[ps->pos].symbol == symbols[i])
875  u = PosSet::cup(psm,u,pi[ps->pos].followpos);
876  if (u != NULL)
877  tb.add(sn->state,symbols[i],sp.state(spm,u));
878  }
879  }
880  tb.finish();
881 
882  // Compute final states
883  FinalBag fb;
884  for (StateNode* n = sp.all; n != NULL; n = n->next)
885  if (n->pos->in(n_pos-1))
886  fb.add(n->state);
887  fb.finish();
888 
889  return DFA(0,tb.transitions(),fb.finals(),true);
890  }
891 
892 }
893 
894 // STATISTICS: minimodel-any
895 
Information on positions collected during traversal.
Definition: reg.cpp:545
int state(StatePoolAllocator &, PosSet *)
Definition: reg.cpp:716
NodeType t
Type of node.
Definition: bool-expr.cpp:230
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1569
PosSetCmp
Order on position sets.
Definition: reg.cpp:442
static PosSet * cup(PosSetAllocator &, PosSet *, PosSet *)
Definition: reg.cpp:501
ExpInfo(REG::Exp *e=NULL)
Definition: reg.cpp:556
static PosSetCmp cmp(PosSet *, PosSet *)
Definition: reg.cpp:485
void rfree(void *p)
Free memory block starting at p.
Definition: heap.hpp:371
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition: region.hpp:386
Regular expressions over integer values.
Definition: minimodel.hh:1518
Exception: Too few arguments available in argument array
Definition: exception.hpp:45
Support::BlockAllocator< StateNode, Heap > StatePoolAllocator
Allocator for state nodes.
Definition: reg.cpp:652
bool pos(const View &x)
Test whether x is postive.
Definition: mult.hpp:41
REG & operator|=(const REG &r)
This expression or r.
Definition: reg.cpp:314
Exp * kids[2]
Subexpressions.
Definition: reg.cpp:74
void * ralloc(size_t s)
Allocate s bytes from heap.
Definition: heap.hpp:357
Array with arbitrary number of elements.
Expression information.
Definition: reg.cpp:534
Handle to region.
Definition: region.hpp:55
StateNode * pop(void)
Definition: reg.cpp:702
#define forceinline
Definition: config.hpp:185
const int max
Largest allowed integer value.
Definition: int.hh:116
Gecode::IntSet d(v, 7)
std::string toString(void) const
Print expression.
Definition: reg.cpp:214
Manage memory organized into block lists (allocator)
Deterministic finite automaton (DFA)
Definition: int.hh:2048
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
const REG & operator=(const REG &r)
Assign to regular expression r.
Definition: reg.cpp:236
static void dec(Exp *e)
Decrement use counter of e.
Definition: reg.cpp:141
Gecode::IntArgs i({1, 2, 3, 4})
void add(int, int, int)
Definition: reg.cpp:775
REG & operator+=(const REG &r)
This expression is followed by r.
Definition: reg.cpp:342
static int n_pos(Exp *e)
Return number of positions of e.
Definition: reg.cpp:148
REG(void)
Initialize as empty sequence (epsilon)
Definition: reg.cpp:229
State pool combines a tree of states together with yet unprocessed states
Definition: reg.cpp:674
T pop(void)
Pop topmost element from stack and return it.
ExpType type
Type of regular expression.
Definition: reg.cpp:68
REG operator|(const REG &r)
Return expression for: this expression or r.
Definition: reg.cpp:300
Specification of a DFA transition.
Definition: int.hh:2057
static void inc(Exp *e)
Increment use counter of e.
Definition: reg.cpp:136
const int * pi[]
Definition: photo.cpp:14262
unsigned int use_cnt
Reference counter.
Definition: reg.cpp:55
Passing integer arguments.
Definition: int.hh:628
union Gecode::@593::NNF::@62 u
Union depending on nodetype t.
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
MiniModel::PosSet * followpos(MiniModel::PosSetAllocator &, MiniModel::PosInfo *)
Compute the follow positions.
Definition: reg.cpp:562
Post propagator for f(x \diamond_{\mathit{op}} y) \sim_r z \f$ void rel(Home home
~REG(void)
Destructor.
Definition: reg.cpp:245
ExpType
Type of regular expression.
Definition: reg.cpp:61
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
bool in(int) const
Definition: reg.cpp:474
T & top(void) const
Return element on top of stack.
DFA::Transition * transitions(void)
Definition: reg.cpp:788
Client for block allocator of type T.
REG operator*(void)
Return expression for: this expression arbitrarily often (Kleene star)
Definition: reg.cpp:360
Heap heap
The single global heap.
Definition: heap.cpp:44
Stack with arbitrary number of elements.
bool empty(void) const
Definition: reg.cpp:711
Post propagator for SetVar x
Definition: set.hh:767
Implementation of the actual expression tree.
Definition: reg.cpp:52
union Gecode::REG::Exp::@67 data
Symbol or subexpressions.
For collecting transitions while constructing a DFA.
Definition: reg.cpp:760
Sets of positions.
Definition: reg.cpp:451
Node information computed during traversal of the expressions.
Definition: reg.cpp:525
REG operator+(void)
Return expression for: this expression at least once.
Definition: reg.cpp:420
void toString(std::ostringstream &os) const
Print expression to os.
Definition: reg.cpp:153
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:373
Support::BlockAllocator< PosSet, Region > PosSetAllocator
Allocator for position sets.
Definition: reg.cpp:40
void exp(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
NodeInfo(bool n=false, PosSet *fp=NULL, PosSet *lp=NULL)
Definition: reg.cpp:552
bool empty(void) const
Test whether stack is empty.
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:56
static void sort(int s[], int n)
Definition: reg.cpp:749
struct Gecode::@593::NNF::@62::@64 a
For atomic nodes.
int _n_pos
Number of positions.
Definition: reg.cpp:57
Node together with state information
Definition: reg.cpp:662
void push(const T &x)
Push element x on top of stack.
For collecting final states while constructing a DFA.
Definition: reg.cpp:797
int symbol
Symbol.
Definition: reg.cpp:72