Generated on Sat Jan 20 2018 22:21:17 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  * Last modified:
10  * $Date: 2016-04-19 17:19:45 +0200 (Tue, 19 Apr 2016) $ by $Author: schulte $
11  * $Revision: 14967 $
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 {
69  ET_STAR
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  void toString(std::ostringstream& os) const;
93  std::string toString(void) 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  void
156  REG::Exp::toString(std::ostringstream& os) const {
157  switch (type) {
158  case ET_SYMBOL:
159  os << "[" << data.symbol << "]";
160  return;
161  case ET_STAR:
162  {
163  bool par = ((data.kids[0] != NULL) &&
164  ((data.kids[0]->type == ET_CONC) ||
165  (data.kids[0]->type == ET_OR)));
166  os << (par ? "*(" : "*");
167  if (data.kids[0]==NULL) {
168  os << "[]";
169  } else {
170  data.kids[0]->toString(os);
171  }
172  os << (par ? ")" : "");
173  return;
174  }
175  case ET_CONC:
176  {
177  bool par0 = ((data.kids[0] != NULL) &&
178  (data.kids[0]->type == ET_OR));
179  os << (par0 ? "(" : "");
180  if (data.kids[0]==NULL) {
181  os << "[]";
182  } else {
183  data.kids[0]->toString(os);
184  }
185  os << (par0 ? ")+" : "+");
186  bool par1 = ((data.kids[1] != NULL) &&
187  (data.kids[1]->type == ET_OR));
188  os << (par1 ? "(" : "");
189  if (data.kids[1]==NULL) {
190  os << "[]";
191  } else {
192  data.kids[1]->toString(os);
193  }
194  os << (par1 ? ")" : "");
195  return;
196  }
197  case ET_OR:
198  if (data.kids[0]==NULL) {
199  os << "[]";
200  } else {
201  data.kids[0]->toString(os);
202  }
203  os << "|";
204  if (data.kids[1]==NULL) {
205  os << "[]";
206  } else {
207  data.kids[1]->toString(os);
208  }
209  return;
210  default: GECODE_NEVER;
211  }
212  GECODE_NEVER;
213  return;
214  }
215 
216  std::string
217  REG::Exp::toString(void) const {
218  std::ostringstream os;
219  toString(os);
220  return os.str();
221  }
222 
223 
224  /*
225  * Regular expressions
226  *
227  */
228 
230  REG::REG(Exp* f) : e(f) {}
231 
232  REG::REG(void) : e(NULL) {}
233 
234  REG::REG(const REG& r) : e(r.e) {
235  REG::Exp::inc(e);
236  }
237 
238  const REG&
240  if (&r != this) {
241  REG::Exp::inc(r.e);
242  REG::Exp::dec(e);
243  e = r.e;
244  }
245  return *this;
246  }
247 
248  REG::~REG(void) {
249  REG::Exp::dec(e);
250  }
251 
252  REG::REG(int s) : e(new Exp) {
253  e->use_cnt = 1;
254  e->_n_pos = 1;
256  e->data.symbol = s;
257  }
258 
259  REG::REG(const IntArgs& x) {
260  int n = x.size();
261  if (n < 1)
262  throw MiniModel::TooFewArguments("REG");
263  Exp** a = heap.alloc<Exp*>(n);
264  // Initialize with symbols
265  for (int i=n; i--; ) {
266  a[i] = new Exp();
267  a[i]->use_cnt = 1;
268  a[i]->_n_pos = 1;
269  a[i]->type = REG::Exp::ET_SYMBOL;
270  a[i]->data.symbol = x[i];
271  }
272  // Build a balanced tree of alternative nodes
273  for (int m=n; m>1; ) {
274  if (m & 1) {
275  m -= 1;
276  Exp* e1 = a[m];
277  Exp* e2 = a[0];
278  a[0] = new Exp;
279  a[0]->use_cnt = 1;
280  a[0]->_n_pos = REG::Exp::n_pos(e1) + REG::Exp::n_pos(e2);
281  a[0]->type = REG::Exp::ET_OR;
282  a[0]->data.kids[0] = e1;
283  a[0]->data.kids[1] = e2;
284  } else {
285  m >>= 1;
286  for (int i=0; i<m; i++) {
287  Exp* e1 = a[2*i];
288  Exp* e2 = a[2*i+1];
289  a[i] = new Exp;
290  a[i]->use_cnt = 1;
291  a[i]->_n_pos = REG::Exp::n_pos(e1) + REG::Exp::n_pos(e2);
292  a[i]->type = REG::Exp::ET_OR;
293  a[i]->data.kids[0] = e1;
294  a[i]->data.kids[1] = e2;
295  }
296  }
297  }
298  e = a[0];
299  heap.free<Exp*>(a,n);
300  }
301 
302  REG
303  REG::operator |(const REG& r2) {
304  if (e == r2.e)
305  return *this;
306  Exp* f = new Exp();
307  f->use_cnt = 1;
308  f->_n_pos = REG::Exp::n_pos(e) + REG::Exp::n_pos(r2.e);
309  f->type = REG::Exp::ET_OR;
310  f->data.kids[0] = e; REG::Exp::inc(e);
311  f->data.kids[1] = r2.e; REG::Exp::inc(r2.e);
312  REG r(f);
313  return r;
314  }
315 
316  REG&
317  REG::operator |=(const REG& r2) {
318  if (e == r2.e)
319  return *this;
320  Exp* f = new Exp();
321  f->use_cnt = 1;
322  f->_n_pos = REG::Exp::n_pos(e) + REG::Exp::n_pos(r2.e);
323  f->type = REG::Exp::ET_OR;
324  f->data.kids[0] = e;
325  f->data.kids[1] = r2.e; REG::Exp::inc(r2.e);
326  e=f;
327  return *this;
328  }
329 
330  REG
331  REG::operator +(const REG& r2) {
332  if (e == NULL) return r2;
333  if (r2.e == NULL) return *this;
334  Exp* f = new Exp();
335  f->use_cnt = 1;
336  f->_n_pos = REG::Exp::n_pos(e) + REG::Exp::n_pos(r2.e);
337  f->type = REG::Exp::ET_CONC;
338  f->data.kids[0] = e; REG::Exp::inc(e);
339  f->data.kids[1] = r2.e; REG::Exp::inc(r2.e);
340  REG r(f);
341  return r;
342  }
343 
344  REG&
345  REG::operator +=(const REG& r2) {
346  if (r2.e == NULL)
347  return *this;
348  if (e == NULL) {
349  e=r2.e; REG::Exp::inc(e);
350  } else {
351  Exp* f = new Exp();
352  f->use_cnt = 1;
353  f->_n_pos = REG::Exp::n_pos(e) + REG::Exp::n_pos(r2.e);
354  f->type = REG::Exp::ET_CONC;
355  f->data.kids[0] = e;
356  f->data.kids[1] = r2.e; REG::Exp::inc(r2.e);
357  e=f;
358  }
359  return *this;
360  }
361 
362  REG
364  if ((e == NULL) || (e->type == REG::Exp::ET_STAR))
365  return *this;
366  Exp* f = new Exp();
367  f->use_cnt = 1;
368  f->_n_pos = REG::Exp::n_pos(e);
369  f->type = REG::Exp::ET_STAR;
370  f->data.kids[0] = e; REG::Exp::inc(e);
371  REG r(f);
372  return r;
373  }
374 
375  REG
376  REG::operator ()(unsigned int n, unsigned int m) {
377  REG r;
378  if ((n>m) || (m == 0))
379  return r;
380  if (n>0) {
381  unsigned int i = n;
382  REG r0 = *this;
383  while (i>0)
384  if (i & 1) {
385  r = r0+r; i--;
386  } else {
387  r0 = r0+r0; i >>= 1;
388  }
389  }
390  if (m > n) {
391  unsigned int i = m-n;
392  REG s0;
393  s0 = s0 | *this;
394  REG s;
395  while (i>0)
396  if (i & 1) {
397  s = s0+s; i--;
398  } else {
399  s0 = s0+s0; i >>= 1;
400  }
401  r = r + s;
402  }
403  return r;
404  }
405 
406  REG
407  REG::operator ()(unsigned int n) {
408  REG r;
409  if (n > 0) {
410  REG r0 = *this;
411  unsigned int i = n;
412  while (i>0)
413  if (i & 1) {
414  r = r0+r; i--;
415  } else {
416  r0 = r0+r0; i >>= 1;
417  }
418  }
419  return r+**this;
420  }
421 
422  REG
424  return this->operator ()(1);
425  }
426 
427  std::string
428  REG::toString(void) const {
429  if (e==NULL) {
430  return "[]";
431  }
432  return e->toString();
433  }
434 
435  namespace MiniModel {
436 
437  /*
438  * Sets of positions
439  *
440  */
441 
445  enum PosSetCmp {
449  };
450 
454  class PosSet : public Support::BlockClient<PosSet,Heap> {
455  // Maintain sets of positions in inverse order
456  // This makes the check whether the last position is included
457  // more efficient.
458  public:
459  int pos; PosSet* next;
460 
461  PosSet(void);
462  PosSet(int);
463 
464  bool in(int) const;
465  static PosSetCmp cmp(PosSet*,PosSet*);
466  static PosSet* cup(PosSetAllocator&,PosSet*,PosSet*);
467  };
468 
469 
471  PosSet::PosSet(void) {}
473  PosSet::PosSet(int p) : pos(p), next(NULL) {}
474 
475 
476  forceinline bool
477  PosSet::in(int p) const {
478  for (const PosSet* ps = this; ps != NULL; ps = ps->next)
479  if (ps->pos == p) {
480  return true;
481  } else if (ps->pos < p) {
482  return false;
483  }
484  return false;
485  }
486 
488  PosSet::cmp(PosSet* ps1, PosSet* ps2) {
489  while ((ps1 != NULL) && (ps2 != NULL)) {
490  if (ps1 == ps2)
491  return PSC_EQ;
492  if (ps1->pos < ps2->pos)
493  return PSC_LE;
494  if (ps1->pos > ps2->pos)
495  return PSC_GR;
496  ps1 = ps1->next; ps2 = ps2->next;
497  }
498  if (ps1 == ps2)
499  return PSC_EQ;
500  return ps1 == NULL ? PSC_LE : PSC_GR;
501  }
502 
503  PosSet*
505  PosSet* ps;
506  PosSet** p = &ps;
507  while ((ps1 != NULL) && (ps2 != NULL)) {
508  if (ps1 == ps2) {
509  *p = ps1; return ps;
510  }
511  PosSet* n = new (psm) PosSet;
512  *p = n; p = &n->next;
513  if (ps1->pos == ps2->pos) {
514  n->pos = ps1->pos;
515  ps1 = ps1->next; ps2 = ps2->next;
516  } else if (ps1->pos > ps2->pos) {
517  n->pos = ps1->pos; ps1 = ps1->next;
518  } else {
519  n->pos = ps2->pos; ps2 = ps2->next;
520  }
521  }
522  *p = (ps1 != NULL) ? ps1 : ps2;
523  return ps;
524  }
525 
526 
528  class NodeInfo {
529  public:
530  bool nullable;
533  NodeInfo(bool n=false, PosSet* fp=NULL, PosSet* lp=NULL);
534  };
535 
537  class ExpInfo {
538  public:
540  bool open;
541  ExpInfo(REG::Exp* e=NULL);
542  };
543 
548  class PosInfo {
549  public:
550  int symbol;
552  };
553 
556  : nullable(n), firstpos(fp), lastpos(lp) {}
557 
560  : exp(e), open(true) {}
561 
562  }
563 
567  int p=0;
568 
569  using MiniModel::PosSet;
570  using MiniModel::NodeInfo;
571  using MiniModel::ExpInfo;
572 
575 
576  // Start with first expression to be processed
577  todo.push(ExpInfo(this));
578 
579  do {
580  if (todo.top().exp == NULL) {
581  todo.pop();
582  done.push(NodeInfo(true,NULL,NULL));
583  } else {
584  switch (todo.top().exp->type) {
585  case ET_SYMBOL:
586  {
587  pi[p].symbol = todo.pop().exp->data.symbol;
588  PosSet* ps = new (psm) PosSet(p++);
589  done.push(NodeInfo(false,ps,ps));
590  }
591  break;
592  case ET_STAR:
593  if (todo.top().open) {
594  // Evaluate subexpression recursively
595  todo.top().open = false;
596  todo.push(todo.top().exp->data.kids[0]);
597  } else {
598  todo.pop();
599  NodeInfo ni = done.pop();
600  for (PosSet* ps = ni.lastpos; ps != NULL; ps = ps->next)
601  pi[ps->pos].followpos =
602  PosSet::cup(psm,pi[ps->pos].followpos,ni.firstpos);
603  done.push(NodeInfo(true,ni.firstpos,ni.lastpos));
604  }
605  break;
606  case ET_CONC:
607  if (todo.top().open) {
608  // Evaluate subexpressions recursively
609  todo.top().open = false;
610  REG::Exp* e = todo.top().exp;
611  todo.push(e->data.kids[1]);
612  todo.push(e->data.kids[0]);
613  } else {
614  todo.pop();
615  NodeInfo ni1 = done.pop();
616  NodeInfo ni0 = done.pop();
617  for (PosSet* ps = ni0.lastpos; ps != NULL; ps = ps->next)
618  pi[ps->pos].followpos =
619  PosSet::cup(psm,pi[ps->pos].followpos,ni1.firstpos);
620  done.push(NodeInfo(ni0.nullable & ni1.nullable,
621  ni0.nullable ?
622  PosSet::cup(psm,ni0.firstpos,ni1.firstpos) : ni0.firstpos,
623  ni1.nullable ?
624  PosSet::cup(psm,ni0.lastpos,ni1.lastpos) : ni1.lastpos));
625  }
626  break;
627  case ET_OR:
628  if (todo.top().open) {
629  // Evaluate subexpressions recursively
630  todo.top().open = false;
631  REG::Exp* e = todo.top().exp;
632  todo.push(e->data.kids[1]);
633  todo.push(e->data.kids[0]);
634  } else {
635  todo.pop();
636  NodeInfo ni1 = done.pop();
637  NodeInfo ni0 = done.pop();
638  done.push(NodeInfo(ni0.nullable | ni1.nullable,
639  PosSet::cup(psm,ni0.firstpos,ni1.firstpos),
640  PosSet::cup(psm,ni0.lastpos,ni1.lastpos)));
641  }
642  break;
643  default: GECODE_NEVER;
644  }
645  }
646  } while (!todo.empty());
647  return done.top().firstpos;
648  }
649 
650 
651  namespace MiniModel {
652 
653  class StateNode;
654 
659 
663  class StateNode : public Support::BlockClient<StateNode,Heap> {
664  public:
666  int state;
670  };
671 
675  class StatePool {
676  public:
677  int n_states;
681 
682  StatePool(PosSet*);
683 
684  StateNode* pop(void);
685  bool empty(void) const;
686 
687  int state(StatePoolAllocator&, PosSet*);
688  };
689 
692  next = &root;
693  all = NULL;
694  n_states = 1;
695  root.pos = ps;
696  root.state = 0;
697  root.next = NULL;
698  root.left = NULL;
699  root.right = NULL;
700  }
701 
704  StateNode* n = next;
705  next = n->next;
706  n->next = all;
707  all = n;
708  return n;
709  }
710 
711  forceinline bool
712  StatePool::empty(void) const {
713  return next == NULL;
714  }
715 
716  forceinline int
717  StatePool::state(StatePoolAllocator& spm, PosSet* ps) {
718  int d = 0;
719  StateNode** p = NULL;
720  StateNode* n = &root;
721  do {
722  switch (PosSet::cmp(ps,n->pos)) {
723  case PSC_EQ: return n->state;
724  case PSC_LE: p = &n->left; n = *p; break;
725  case PSC_GR: p = &n->right; n = *p; break;
726  default: GECODE_NEVER;
727  }
728  d++;
729  } while (n != NULL);
730  n = new (spm) StateNode; *p = n;
731  n->pos = ps;
732  n->state = n_states++;
733  n->next = next;
734  n->left = NULL;
735  n->right = NULL;
736  next = n;
737  return n->state;
738  }
739 
743  class SymbolsInc {
744  public:
745  forceinline bool
746  operator ()(int x, int y) {
747  return x < y;
748  }
749  forceinline static void
750  sort(int s[], int n) {
751  SymbolsInc o;
752  Support::quicksort<int,SymbolsInc>(s,n,o);
753  }
754  };
755 
756 
762  private:
764  int n;
765  public:
766  TransitionBag(void);
767  void add(int,int,int);
768  void finish(void);
769  DFA::Transition* transitions(void);
770  };
771 
774 
775  forceinline void
776  TransitionBag::add(int i_state, int symbol, int o_state) {
777  t[n].i_state = i_state;
778  t[n].symbol = symbol;
779  t[n].o_state = o_state;
780  n++;
781  }
782 
783  forceinline void
785  t[n].i_state = -1;
786  }
787 
790  return &t[0];
791  }
792 
793 
798  class FinalBag {
799  private:
801  int n;
802  public:
803  FinalBag(void);
804  void add(int);
805  void finish(void);
806  int* finals(void);
807  };
808 
810  FinalBag::FinalBag(void) : f(heap), n(0) {}
811 
812  forceinline void
813  FinalBag::add(int state) {
814  f[n++] = state;
815  }
816 
817  forceinline void
819  f[n] = -1;
820  }
821 
822  forceinline int*
824  return &f[0];
825  }
826 
827  }
828 
829  REG::operator DFA(void) {
832  using MiniModel::PosInfo;
833  using MiniModel::PosSet;
834  using MiniModel::NodeInfo;
835 
836  using MiniModel::StatePool;
837  using MiniModel::StateNode;
838 
840  using MiniModel::FinalBag;
841 
842  using MiniModel::SymbolsInc;
843 
844  PosSetAllocator psm(heap);
846  REG r = *this + REG(Int::Limits::max+1);
847  int n_pos = REG::Exp::n_pos(r.e);
848 
849  PosInfo* pi = heap.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 = heap.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  heap.free<PosInfo>(pi,n_pos);
890  heap.free<int>(symbols,n_pos);
891  return DFA(0,tb.transitions(),fb.finals(),true);
892  }
893 
894 }
895 
896 // STATISTICS: minimodel-any
897 
Information on positions collected during traversal.
Definition: reg.cpp:548
int state(StatePoolAllocator &, PosSet *)
Definition: reg.cpp:717
NodeType t
Type of node.
Definition: bool-expr.cpp:234
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1669
union Gecode::@579::NNF::@61 u
Union depending on nodetype t.
PosSetCmp
Order on position sets.
Definition: reg.cpp:445
static PosSet * cup(PosSetAllocator &, PosSet *, PosSet *)
Definition: reg.cpp:504
ExpInfo(REG::Exp *e=NULL)
Definition: reg.cpp:559
static PosSetCmp cmp(PosSet *, PosSet *)
Definition: reg.cpp:488
void rfree(void *p)
Free memory block starting at p.
Definition: heap.hpp:375
Regular expressions over integer values.
Definition: minimodel.hh:1393
Exception: Too few arguments available in argument array
Definition: exception.hpp:49
Support::BlockAllocator< StateNode, Heap > StatePoolAllocator
Allocator for state nodes.
Definition: reg.cpp:653
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:317
Exp * kids[2]
Subexpressions.
Definition: reg.cpp:78
void * ralloc(size_t s)
Allocate s bytes from heap.
Definition: heap.hpp:361
Support::BlockAllocator< PosSet, Heap > PosSetAllocator
Allocator for position sets.
Definition: reg.cpp:44
Array with arbitrary number of elements.
Expression information.
Definition: reg.cpp:537
StateNode * pop(void)
Definition: reg.cpp:703
const int max
Largest allowed integer value.
Definition: int.hh:116
Gecode::IntSet d(v, 7)
struct Gecode::@579::NNF::@61::@63 a
For atomic nodes.
std::string toString(void) const
Print expression.
Definition: reg.cpp:217
Manage memory organized into block lists (allocator)
Deterministic finite automaton (DFA)
Definition: int.hh:2034
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:435
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:239
static void dec(Exp *e)
Decrement use counter of e.
Definition: reg.cpp:144
void add(int, int, int)
Definition: reg.cpp:776
REG & operator+=(const REG &r)
This expression is followed by r.
Definition: reg.cpp:345
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:232
State pool combines a tree of states together with yet unprocessed states
Definition: reg.cpp:675
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:303
Specification of a DFA transition.
Definition: int.hh:2040
static void inc(Exp *e)
Increment use counter of e.
Definition: reg.cpp:139
const int * pi[]
Definition: photo.cpp:14266
unsigned int use_cnt
Reference counter.
Definition: reg.cpp:59
Passing integer arguments.
Definition: int.hh:610
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:784
union Gecode::REG::Exp::@66 data
Symbol or subexpressions.
MiniModel::PosSet * followpos(MiniModel::PosSetAllocator &, MiniModel::PosInfo *)
Compute the follow positions.
Definition: reg.cpp:565
Post propagator for f(x \diamond_{\mathit{op}} y) \sim_r z \f$ void rel(Home home
~REG(void)
Destructor.
Definition: reg.cpp:248
ExpType
Type of regular expression.
Definition: reg.cpp:65
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:784
bool in(int) const
Definition: reg.cpp:477
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:461
DFA::Transition * transitions(void)
Definition: reg.cpp:789
Client for block allocator of type T.
REG operator*(void)
Return expression for: this expression arbitrarily often (Kleene star)
Definition: reg.cpp:363
Heap heap
The single global heap.
Definition: heap.cpp:48
#define forceinline
Definition: config.hpp:173
Stack with arbitrary number of elements.
bool empty(void) const
Definition: reg.cpp:712
Post propagator for SetVar x
Definition: set.hh:784
Implementation of the actual expression tree.
Definition: reg.cpp:56
For collecting transitions while constructing a DFA.
Definition: reg.cpp:761
Sets of positions.
Definition: reg.cpp:454
Node information computed during traversal of the expressions.
Definition: reg.cpp:528
REG operator+(void)
Return expression for: this expression at least once.
Definition: reg.cpp:423
void toString(std::ostringstream &os) const
Print expression to os.
Definition: reg.cpp:156
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:376
void exp(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
NodeInfo(bool n=false, PosSet *fp=NULL, PosSet *lp=NULL)
Definition: reg.cpp:555
bool empty(void) const
Test whether stack is empty.
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60
static void sort(int s[], int n)
Definition: reg.cpp:750
int _n_pos
Number of positions.
Definition: reg.cpp:61
Node together with state information
Definition: reg.cpp:663
void push(const T &x)
Push element x on top of stack.
For collecting final states while constructing a DFA.
Definition: reg.cpp:798
int symbol
Symbol.
Definition: reg.cpp:76