Generated on Sat Jun 2 2018 07:17:44 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) {
117  todo.push(this);
118  while (!todo.empty()) {
119  Exp* e = todo.pop();
120  switch (e->type) {
121  case ET_OR:
122  case ET_CONC:
123  if ((e->data.kids[1] != NULL) && (--e->data.kids[1]->use_cnt == 0))
124  todo.push(e->data.kids[1]);
125  case ET_STAR:
126  if ((e->data.kids[0] != NULL) && (--e->data.kids[0]->use_cnt == 0))
127  todo.push(e->data.kids[0]);
128  default: ;
129  }
130  heap.rfree(e);
131  }
132  }
133 
134  forceinline void
136  if (e != NULL)
137  e->use_cnt++;
138  }
139  forceinline void
141  if ((e != NULL) && (--e->use_cnt == 0))
142  e->dispose();
143  }
144 
145 
146  forceinline int
148  return (e != NULL) ? e->_n_pos : 0;
149  }
150 
151  void
152  REG::Exp::toString(std::ostringstream& os) const {
153  switch (type) {
154  case ET_SYMBOL:
155  os << "[" << data.symbol << "]";
156  return;
157  case ET_STAR:
158  {
159  bool par = ((data.kids[0] != NULL) &&
160  ((data.kids[0]->type == ET_CONC) ||
161  (data.kids[0]->type == ET_OR)));
162  os << (par ? "*(" : "*");
163  if (data.kids[0]==NULL) {
164  os << "[]";
165  } else {
166  data.kids[0]->toString(os);
167  }
168  os << (par ? ")" : "");
169  return;
170  }
171  case ET_CONC:
172  {
173  bool par0 = ((data.kids[0] != NULL) &&
174  (data.kids[0]->type == ET_OR));
175  os << (par0 ? "(" : "");
176  if (data.kids[0]==NULL) {
177  os << "[]";
178  } else {
179  data.kids[0]->toString(os);
180  }
181  os << (par0 ? ")+" : "+");
182  bool par1 = ((data.kids[1] != NULL) &&
183  (data.kids[1]->type == ET_OR));
184  os << (par1 ? "(" : "");
185  if (data.kids[1]==NULL) {
186  os << "[]";
187  } else {
188  data.kids[1]->toString(os);
189  }
190  os << (par1 ? ")" : "");
191  return;
192  }
193  case ET_OR:
194  if (data.kids[0]==NULL) {
195  os << "[]";
196  } else {
197  data.kids[0]->toString(os);
198  }
199  os << "|";
200  if (data.kids[1]==NULL) {
201  os << "[]";
202  } else {
203  data.kids[1]->toString(os);
204  }
205  return;
206  default: GECODE_NEVER;
207  }
208  GECODE_NEVER;
209  return;
210  }
211 
212  std::string
213  REG::Exp::toString(void) const {
214  std::ostringstream os;
215  toString(os);
216  return os.str();
217  }
218 
219 
220  /*
221  * Regular expressions
222  *
223  */
224 
226  REG::REG(Exp* f) : e(f) {}
227 
228  REG::REG(void) : e(NULL) {}
229 
230  REG::REG(const REG& r) : e(r.e) {
231  REG::Exp::inc(e);
232  }
233 
234  const REG&
236  if (&r != this) {
237  REG::Exp::inc(r.e);
238  REG::Exp::dec(e);
239  e = r.e;
240  }
241  return *this;
242  }
243 
244  REG::~REG(void) {
245  REG::Exp::dec(e);
246  }
247 
248  REG::REG(int s) : e(new Exp) {
249  e->use_cnt = 1;
250  e->_n_pos = 1;
252  e->data.symbol = s;
253  }
254 
255  REG::REG(const IntArgs& x) {
256  int n = x.size();
257  if (n < 1)
258  throw MiniModel::TooFewArguments("REG");
259  Exp** a = heap.alloc<Exp*>(n);
260  // Initialize with symbols
261  for (int i=n; i--; ) {
262  a[i] = new Exp();
263  a[i]->use_cnt = 1;
264  a[i]->_n_pos = 1;
265  a[i]->type = REG::Exp::ET_SYMBOL;
266  a[i]->data.symbol = x[i];
267  }
268  // Build a balanced tree of alternative nodes
269  for (int m=n; m>1; ) {
270  if (m & 1) {
271  m -= 1;
272  Exp* e1 = a[m];
273  Exp* e2 = a[0];
274  a[0] = new Exp;
275  a[0]->use_cnt = 1;
276  a[0]->_n_pos = REG::Exp::n_pos(e1) + REG::Exp::n_pos(e2);
277  a[0]->type = REG::Exp::ET_OR;
278  a[0]->data.kids[0] = e1;
279  a[0]->data.kids[1] = e2;
280  } else {
281  m >>= 1;
282  for (int i=0; i<m; i++) {
283  Exp* e1 = a[2*i];
284  Exp* e2 = a[2*i+1];
285  a[i] = new Exp;
286  a[i]->use_cnt = 1;
287  a[i]->_n_pos = REG::Exp::n_pos(e1) + REG::Exp::n_pos(e2);
288  a[i]->type = REG::Exp::ET_OR;
289  a[i]->data.kids[0] = e1;
290  a[i]->data.kids[1] = e2;
291  }
292  }
293  }
294  e = a[0];
295  heap.free<Exp*>(a,n);
296  }
297 
298  REG
299  REG::operator |(const REG& r2) {
300  if (e == r2.e)
301  return *this;
302  Exp* f = new Exp();
303  f->use_cnt = 1;
304  f->_n_pos = REG::Exp::n_pos(e) + REG::Exp::n_pos(r2.e);
305  f->type = REG::Exp::ET_OR;
306  f->data.kids[0] = e; REG::Exp::inc(e);
307  f->data.kids[1] = r2.e; REG::Exp::inc(r2.e);
308  REG r(f);
309  return r;
310  }
311 
312  REG&
313  REG::operator |=(const REG& r2) {
314  if (e == r2.e)
315  return *this;
316  Exp* f = new Exp();
317  f->use_cnt = 1;
318  f->_n_pos = REG::Exp::n_pos(e) + REG::Exp::n_pos(r2.e);
319  f->type = REG::Exp::ET_OR;
320  f->data.kids[0] = e;
321  f->data.kids[1] = r2.e; REG::Exp::inc(r2.e);
322  e=f;
323  return *this;
324  }
325 
326  REG
327  REG::operator +(const REG& r2) {
328  if (e == NULL) return r2;
329  if (r2.e == NULL) return *this;
330  Exp* f = new Exp();
331  f->use_cnt = 1;
332  f->_n_pos = REG::Exp::n_pos(e) + REG::Exp::n_pos(r2.e);
333  f->type = REG::Exp::ET_CONC;
334  f->data.kids[0] = e; REG::Exp::inc(e);
335  f->data.kids[1] = r2.e; REG::Exp::inc(r2.e);
336  REG r(f);
337  return r;
338  }
339 
340  REG&
341  REG::operator +=(const REG& r2) {
342  if (r2.e == NULL)
343  return *this;
344  if (e == NULL) {
345  e=r2.e; REG::Exp::inc(e);
346  } else {
347  Exp* f = new Exp();
348  f->use_cnt = 1;
349  f->_n_pos = REG::Exp::n_pos(e) + REG::Exp::n_pos(r2.e);
350  f->type = REG::Exp::ET_CONC;
351  f->data.kids[0] = e;
352  f->data.kids[1] = r2.e; REG::Exp::inc(r2.e);
353  e=f;
354  }
355  return *this;
356  }
357 
358  REG
360  if ((e == NULL) || (e->type == REG::Exp::ET_STAR))
361  return *this;
362  Exp* f = new Exp();
363  f->use_cnt = 1;
364  f->_n_pos = REG::Exp::n_pos(e);
365  f->type = REG::Exp::ET_STAR;
366  f->data.kids[0] = e; REG::Exp::inc(e);
367  REG r(f);
368  return r;
369  }
370 
371  REG
372  REG::operator ()(unsigned int n, unsigned int m) {
373  REG r;
374  if ((n>m) || (m == 0))
375  return r;
376  if (n>0) {
377  unsigned int i = n;
378  REG r0 = *this;
379  while (i>0)
380  if (i & 1) {
381  r = r0+r; i--;
382  } else {
383  r0 = r0+r0; i >>= 1;
384  }
385  }
386  if (m > n) {
387  unsigned int i = m-n;
388  REG s0;
389  s0 = s0 | *this;
390  REG s;
391  while (i>0)
392  if (i & 1) {
393  s = s0+s; i--;
394  } else {
395  s0 = s0+s0; i >>= 1;
396  }
397  r = r + s;
398  }
399  return r;
400  }
401 
402  REG
403  REG::operator ()(unsigned int n) {
404  REG r;
405  if (n > 0) {
406  REG r0 = *this;
407  unsigned int i = n;
408  while (i>0)
409  if (i & 1) {
410  r = r0+r; i--;
411  } else {
412  r0 = r0+r0; i >>= 1;
413  }
414  }
415  return r+**this;
416  }
417 
418  REG
420  return this->operator ()(1);
421  }
422 
423  std::string
424  REG::toString(void) const {
425  if (e==NULL) {
426  return "[]";
427  }
428  return e->toString();
429  }
430 
431  namespace MiniModel {
432 
433  /*
434  * Sets of positions
435  *
436  */
437 
441  enum PosSetCmp {
445  };
446 
450  class PosSet : public Support::BlockClient<PosSet,Heap> {
451  // Maintain sets of positions in inverse order
452  // This makes the check whether the last position is included
453  // more efficient.
454  public:
455  int pos; PosSet* next;
456 
457  PosSet(void);
458  PosSet(int);
459 
460  bool in(int) const;
461  static PosSetCmp cmp(PosSet*,PosSet*);
462  static PosSet* cup(PosSetAllocator&,PosSet*,PosSet*);
463  };
464 
465 
467  PosSet::PosSet(void) {}
469  PosSet::PosSet(int p) : pos(p), next(NULL) {}
470 
471 
472  forceinline bool
473  PosSet::in(int p) const {
474  for (const PosSet* ps = this; ps != NULL; ps = ps->next)
475  if (ps->pos == p) {
476  return true;
477  } else if (ps->pos < p) {
478  return false;
479  }
480  return false;
481  }
482 
484  PosSet::cmp(PosSet* ps1, PosSet* ps2) {
485  while ((ps1 != NULL) && (ps2 != NULL)) {
486  if (ps1 == ps2)
487  return PSC_EQ;
488  if (ps1->pos < ps2->pos)
489  return PSC_LE;
490  if (ps1->pos > ps2->pos)
491  return PSC_GR;
492  ps1 = ps1->next; ps2 = ps2->next;
493  }
494  if (ps1 == ps2)
495  return PSC_EQ;
496  return ps1 == NULL ? PSC_LE : PSC_GR;
497  }
498 
499  PosSet*
501  PosSet* ps;
502  PosSet** p = &ps;
503  while ((ps1 != NULL) && (ps2 != NULL)) {
504  if (ps1 == ps2) {
505  *p = ps1; return ps;
506  }
507  PosSet* n = new (psm) PosSet;
508  *p = n; p = &n->next;
509  if (ps1->pos == ps2->pos) {
510  n->pos = ps1->pos;
511  ps1 = ps1->next; ps2 = ps2->next;
512  } else if (ps1->pos > ps2->pos) {
513  n->pos = ps1->pos; ps1 = ps1->next;
514  } else {
515  n->pos = ps2->pos; ps2 = ps2->next;
516  }
517  }
518  *p = (ps1 != NULL) ? ps1 : ps2;
519  return ps;
520  }
521 
522 
524  class NodeInfo {
525  public:
526  bool nullable;
529  NodeInfo(bool n=false, PosSet* fp=NULL, PosSet* lp=NULL);
530  };
531 
533  class ExpInfo {
534  public:
536  bool open;
537  ExpInfo(REG::Exp* e=NULL);
538  };
539 
544  class PosInfo {
545  public:
546  int symbol;
548  };
549 
552  : nullable(n), firstpos(fp), lastpos(lp) {}
553 
556  : exp(e), open(true) {}
557 
558  }
559 
563  int p=0;
564 
565  using MiniModel::PosSet;
566  using MiniModel::NodeInfo;
567  using MiniModel::ExpInfo;
568 
571 
572  // Start with first expression to be processed
573  todo.push(ExpInfo(this));
574 
575  do {
576  if (todo.top().exp == NULL) {
577  todo.pop();
578  done.push(NodeInfo(true,NULL,NULL));
579  } else {
580  switch (todo.top().exp->type) {
581  case ET_SYMBOL:
582  {
583  pi[p].symbol = todo.pop().exp->data.symbol;
584  PosSet* ps = new (psm) PosSet(p++);
585  done.push(NodeInfo(false,ps,ps));
586  }
587  break;
588  case ET_STAR:
589  if (todo.top().open) {
590  // Evaluate subexpression recursively
591  todo.top().open = false;
592  todo.push(todo.top().exp->data.kids[0]);
593  } else {
594  todo.pop();
595  NodeInfo ni = done.pop();
596  for (PosSet* ps = ni.lastpos; ps != NULL; ps = ps->next)
597  pi[ps->pos].followpos =
598  PosSet::cup(psm,pi[ps->pos].followpos,ni.firstpos);
599  done.push(NodeInfo(true,ni.firstpos,ni.lastpos));
600  }
601  break;
602  case ET_CONC:
603  if (todo.top().open) {
604  // Evaluate subexpressions recursively
605  todo.top().open = false;
606  REG::Exp* e = todo.top().exp;
607  todo.push(e->data.kids[1]);
608  todo.push(e->data.kids[0]);
609  } else {
610  todo.pop();
611  NodeInfo ni1 = done.pop();
612  NodeInfo ni0 = done.pop();
613  for (PosSet* ps = ni0.lastpos; ps != NULL; ps = ps->next)
614  pi[ps->pos].followpos =
615  PosSet::cup(psm,pi[ps->pos].followpos,ni1.firstpos);
616  done.push(NodeInfo(ni0.nullable & ni1.nullable,
617  ni0.nullable ?
618  PosSet::cup(psm,ni0.firstpos,ni1.firstpos) : ni0.firstpos,
619  ni1.nullable ?
620  PosSet::cup(psm,ni0.lastpos,ni1.lastpos) : ni1.lastpos));
621  }
622  break;
623  case ET_OR:
624  if (todo.top().open) {
625  // Evaluate subexpressions recursively
626  todo.top().open = false;
627  REG::Exp* e = todo.top().exp;
628  todo.push(e->data.kids[1]);
629  todo.push(e->data.kids[0]);
630  } else {
631  todo.pop();
632  NodeInfo ni1 = done.pop();
633  NodeInfo ni0 = done.pop();
634  done.push(NodeInfo(ni0.nullable | ni1.nullable,
635  PosSet::cup(psm,ni0.firstpos,ni1.firstpos),
636  PosSet::cup(psm,ni0.lastpos,ni1.lastpos)));
637  }
638  break;
639  default: GECODE_NEVER;
640  }
641  }
642  } while (!todo.empty());
643  return done.top().firstpos;
644  }
645 
646 
647  namespace MiniModel {
648 
649  class StateNode;
650 
655 
659  class StateNode : public Support::BlockClient<StateNode,Heap> {
660  public:
662  int state;
666  };
667 
671  class StatePool {
672  public:
673  int n_states;
677 
678  StatePool(PosSet*);
679 
680  StateNode* pop(void);
681  bool empty(void) const;
682 
683  int state(StatePoolAllocator&, PosSet*);
684  };
685 
688  next = &root;
689  all = NULL;
690  n_states = 1;
691  root.pos = ps;
692  root.state = 0;
693  root.next = NULL;
694  root.left = NULL;
695  root.right = NULL;
696  }
697 
700  StateNode* n = next;
701  next = n->next;
702  n->next = all;
703  all = n;
704  return n;
705  }
706 
707  forceinline bool
708  StatePool::empty(void) const {
709  return next == NULL;
710  }
711 
712  forceinline int
713  StatePool::state(StatePoolAllocator& spm, PosSet* ps) {
714  int d = 0;
715  StateNode** p = NULL;
716  StateNode* n = &root;
717  do {
718  switch (PosSet::cmp(ps,n->pos)) {
719  case PSC_EQ: return n->state;
720  case PSC_LE: p = &n->left; n = *p; break;
721  case PSC_GR: p = &n->right; n = *p; break;
722  default: GECODE_NEVER;
723  }
724  d++;
725  } while (n != NULL);
726  n = new (spm) StateNode; *p = n;
727  n->pos = ps;
728  n->state = n_states++;
729  n->next = next;
730  n->left = NULL;
731  n->right = NULL;
732  next = n;
733  return n->state;
734  }
735 
739  class SymbolsInc {
740  public:
741  forceinline bool
742  operator ()(int x, int y) {
743  return x < y;
744  }
745  forceinline static void
746  sort(int s[], int n) {
747  SymbolsInc o;
748  Support::quicksort<int,SymbolsInc>(s,n,o);
749  }
750  };
751 
752 
758  private:
760  int n;
761  public:
762  TransitionBag(void);
763  void add(int,int,int);
764  void finish(void);
765  DFA::Transition* transitions(void);
766  };
767 
770 
771  forceinline void
772  TransitionBag::add(int i_state, int symbol, int o_state) {
773  t[n].i_state = i_state;
774  t[n].symbol = symbol;
775  t[n].o_state = o_state;
776  n++;
777  }
778 
779  forceinline void
781  t[n].i_state = -1;
782  }
783 
786  return &t[0];
787  }
788 
789 
794  class FinalBag {
795  private:
797  int n;
798  public:
799  FinalBag(void);
800  void add(int);
801  void finish(void);
802  int* finals(void);
803  };
804 
806  FinalBag::FinalBag(void) : f(heap), n(0) {}
807 
808  forceinline void
809  FinalBag::add(int state) {
810  f[n++] = state;
811  }
812 
813  forceinline void
815  f[n] = -1;
816  }
817 
818  forceinline int*
820  return &f[0];
821  }
822 
823  }
824 
825  REG::operator DFA(void) {
828  using MiniModel::PosInfo;
829  using MiniModel::PosSet;
830  using MiniModel::NodeInfo;
831 
832  using MiniModel::StatePool;
833  using MiniModel::StateNode;
834 
836  using MiniModel::FinalBag;
837 
838  using MiniModel::SymbolsInc;
839 
840  PosSetAllocator psm(heap);
842  REG r = *this + REG(Int::Limits::max+1);
843  int n_pos = REG::Exp::n_pos(r.e);
844 
845  PosInfo* pi = heap.alloc<PosInfo>(n_pos);
846  for (int i=n_pos; i--; )
847  pi[i].followpos = NULL;
848 
849  PosSet* firstpos = r.e->followpos(psm,&pi[0]);
850 
851  // Compute symbols
852  int* symbols = heap.alloc<int>(n_pos);
853  for (int i=n_pos; i--; )
854  symbols[i] = pi[i].symbol;
855 
856  SymbolsInc::sort(&symbols[0],n_pos-1);
857  int n_symbols = 1;
858  for (int i = 1; i<n_pos-1; i++)
859  if (symbols[i-1] != symbols[i])
860  symbols[n_symbols++] = symbols[i];
861 
862  // Compute states and transitions
863  TransitionBag tb;
864  StatePool sp(firstpos);
865  while (!sp.empty()) {
866  StateNode* sn = sp.pop();
867  for (int i = n_symbols; i--; ) {
868  PosSet* u = NULL;
869  for (PosSet* ps = sn->pos; ps != NULL; ps = ps->next)
870  if (pi[ps->pos].symbol == symbols[i])
871  u = PosSet::cup(psm,u,pi[ps->pos].followpos);
872  if (u != NULL)
873  tb.add(sn->state,symbols[i],sp.state(spm,u));
874  }
875  }
876  tb.finish();
877 
878  // Compute final states
879  FinalBag fb;
880  for (StateNode* n = sp.all; n != NULL; n = n->next)
881  if (n->pos->in(n_pos-1))
882  fb.add(n->state);
883  fb.finish();
884 
885  heap.free<PosInfo>(pi,n_pos);
886  heap.free<int>(symbols,n_pos);
887  return DFA(0,tb.transitions(),fb.finals(),true);
888  }
889 
890 }
891 
892 // STATISTICS: minimodel-any
893 
Information on positions collected during traversal.
Definition: reg.cpp:544
int state(StatePoolAllocator &, PosSet *)
Definition: reg.cpp:713
NodeType t
Type of node.
Definition: bool-expr.cpp:230
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1653
PosSetCmp
Order on position sets.
Definition: reg.cpp:441
static PosSet * cup(PosSetAllocator &, PosSet *, PosSet *)
Definition: reg.cpp:500
ExpInfo(REG::Exp *e=NULL)
Definition: reg.cpp:555
static PosSetCmp cmp(PosSet *, PosSet *)
Definition: reg.cpp:484
void rfree(void *p)
Free memory block starting at p.
Definition: heap.hpp:371
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:649
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:313
Exp * kids[2]
Subexpressions.
Definition: reg.cpp:74
void * ralloc(size_t s)
Allocate s bytes from heap.
Definition: heap.hpp:357
Support::BlockAllocator< PosSet, Heap > PosSetAllocator
Allocator for position sets.
Definition: reg.cpp:40
Array with arbitrary number of elements.
Expression information.
Definition: reg.cpp:533
StateNode * pop(void)
Definition: reg.cpp:699
#define forceinline
Definition: config.hpp:185
const int max
Largest allowed integer value.
Definition: int.hh:112
Gecode::IntSet d(v, 7)
std::string toString(void) const
Print expression.
Definition: reg.cpp:213
Manage memory organized into block lists (allocator)
Deterministic finite automaton (DFA)
Definition: int.hh:2023
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
T * alloc(long unsigned int n)
Allocate block of n objects of type T from heap.
Definition: heap.hpp:431
Gecode::IntArgs i(4, 1, 2, 3, 4)
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:235
static void dec(Exp *e)
Decrement use counter of e.
Definition: reg.cpp:140
void add(int, int, int)
Definition: reg.cpp:772
REG & operator+=(const REG &r)
This expression is followed by r.
Definition: reg.cpp:341
static int n_pos(Exp *e)
Return number of positions of e.
Definition: reg.cpp:147
REG(void)
Initialize as empty sequence (epsilon)
Definition: reg.cpp:228
State pool combines a tree of states together with yet unprocessed states
Definition: reg.cpp:671
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:299
Specification of a DFA transition.
Definition: int.hh:2032
static void inc(Exp *e)
Increment use counter of e.
Definition: reg.cpp:135
union Gecode::@585::NNF::@62 u
Union depending on nodetype t.
const int * pi[]
Definition: photo.cpp:14262
unsigned int use_cnt
Reference counter.
Definition: reg.cpp:55
Passing integer arguments.
Definition: int.hh:604
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:765
MiniModel::PosSet * followpos(MiniModel::PosSetAllocator &, MiniModel::PosInfo *)
Compute the follow positions.
Definition: reg.cpp:561
Post propagator for f(x \diamond_{\mathit{op}} y) \sim_r z \f$ void rel(Home home
~REG(void)
Destructor.
Definition: reg.cpp:244
ExpType
Type of regular expression.
Definition: reg.cpp:61
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:765
bool in(int) const
Definition: reg.cpp:473
T & top(void) const
Return element on top of stack.
void free(T *b, long unsigned int n)
Delete n objects starting at b.
Definition: heap.hpp:457
struct Gecode::@585::NNF::@62::@64 a
For atomic nodes.
DFA::Transition * transitions(void)
Definition: reg.cpp:785
Client for block allocator of type T.
REG operator*(void)
Return expression for: this expression arbitrarily often (Kleene star)
Definition: reg.cpp:359
Heap heap
The single global heap.
Definition: heap.cpp:44
Stack with arbitrary number of elements.
bool empty(void) const
Definition: reg.cpp:708
Post propagator for SetVar x
Definition: set.hh:765
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:757
Sets of positions.
Definition: reg.cpp:450
Node information computed during traversal of the expressions.
Definition: reg.cpp:524
REG operator+(void)
Return expression for: this expression at least once.
Definition: reg.cpp:419
void toString(std::ostringstream &os) const
Print expression to os.
Definition: reg.cpp:152
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:372
void exp(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
NodeInfo(bool n=false, PosSet *fp=NULL, PosSet *lp=NULL)
Definition: reg.cpp:551
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:746
int _n_pos
Number of positions.
Definition: reg.cpp:57
Node together with state information
Definition: reg.cpp:659
void push(const T &x)
Push element x on top of stack.
For collecting final states while constructing a DFA.
Definition: reg.cpp:794
int symbol
Symbol.
Definition: reg.cpp:72