Generated on Fri Aug 24 2012 04:52:13 for Gecode by doxygen 1.8.1.2
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: 2010-07-26 20:53:58 +1000 (Mon, 26 Jul 2010) $ by $Author: schulte $
11  * $Revision: 11279 $
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 
83  void inc(void);
84  void dec(void);
85  int n_pos(void) const;
87  template<class Char, class Traits>
88  std::basic_ostream<Char,Traits>&
89  print(std::basic_ostream<Char,Traits>& os) const;
90 
91  static void* operator new(size_t);
92  static void operator delete(void*);
93  private:
94  void dispose(void);
95  };
96 
97 
98  /*
99  * Operations on expression nodes
100  *
101  */
102 
103 
104  forceinline void*
105  REG::Exp::operator new(size_t s) {
106  return heap.ralloc(s);
107  }
108  forceinline void
109  REG::Exp::operator delete(void*) {
110  // Deallocation happens in dispose
111  }
112 
113  void
114  REG::Exp::dispose(void) {
116  todo.push(this);
117  while (!todo.empty()) {
118  Exp* e = todo.pop();
119  switch (e->type) {
120  case ET_OR:
121  case ET_CONC:
122  if ((e->data.kids[1] != NULL) && (--e->data.kids[1]->use_cnt == 0))
123  todo.push(e->data.kids[1]);
124  case ET_STAR:
125  if ((e->data.kids[0] != NULL) && (--e->data.kids[0]->use_cnt == 0))
126  todo.push(e->data.kids[0]);
127  default: ;
128  }
129  heap.rfree(e);
130  }
131  }
132 
133  forceinline void
135  if (this != NULL)
136  use_cnt++;
137  }
138  forceinline void
140  if ((this != NULL) && (--use_cnt == 0))
141  dispose();
142  }
143 
144 
145  forceinline int
146  REG::Exp::n_pos(void) const {
147  return (this != NULL) ? _n_pos : 0;
148  }
149 
150 
151  /*
152  * Regular expressions
153  *
154  */
155 
157  REG::REG(Exp* f) : e(f) {}
158 
159  REG::REG(void) : e(NULL) {}
160 
161  REG::REG(const REG& r) : e(r.e) {
162  e->inc();
163  }
164 
165  const REG&
167  if (&r != this) {
168  r.e->inc();
169  e->dec();
170  e = r.e;
171  }
172  return *this;
173  }
174 
175  REG::~REG(void) {
176  e->dec();
177  }
178 
179  REG::REG(int s) : e(new Exp) {
180  e->use_cnt = 1;
181  e->_n_pos = 1;
183  e->data.symbol = s;
184  }
185 
186  REG::REG(const IntArgs& x) {
187  int n = x.size();
188  if (n < 1)
189  throw MiniModel::TooFewArguments("REG");
190  Exp** a = heap.alloc<Exp*>(n);
191  // Initialize with symbols
192  for (int i=n; i--; ) {
193  a[i] = new Exp();
194  a[i]->use_cnt = 1;
195  a[i]->_n_pos = 1;
196  a[i]->type = REG::Exp::ET_SYMBOL;
197  a[i]->data.symbol = x[i];
198  }
199  // Build a balanced tree of alternative nodes
200  for (int m=n; m>1; ) {
201  if (m & 1) {
202  m -= 1;
203  Exp* e1 = a[m];
204  Exp* e2 = a[0];
205  a[0] = new Exp;
206  a[0]->use_cnt = 1;
207  a[0]->_n_pos = e1->n_pos() + e2->n_pos();
208  a[0]->type = REG::Exp::ET_OR;
209  a[0]->data.kids[0] = e1;
210  a[0]->data.kids[1] = e2;
211  } else {
212  m >>= 1;
213  for (int i=0; i<m; i++) {
214  Exp* e1 = a[2*i];
215  Exp* e2 = a[2*i+1];
216  a[i] = new Exp;
217  a[i]->use_cnt = 1;
218  a[i]->_n_pos = e1->n_pos() + e2->n_pos();
219  a[i]->type = REG::Exp::ET_OR;
220  a[i]->data.kids[0] = e1;
221  a[i]->data.kids[1] = e2;
222  }
223  }
224  }
225  e = a[0];
226  heap.free<Exp*>(a,n);
227  }
228 
229  REG
230  REG::operator |(const REG& r2) {
231  if (e == r2.e)
232  return *this;
233  Exp* f = new Exp();
234  f->use_cnt = 1;
235  f->_n_pos = e->n_pos() + r2.e->n_pos();
236  f->type = REG::Exp::ET_OR;
237  f->data.kids[0] = e; e->inc();
238  f->data.kids[1] = r2.e; r2.e->inc();
239  REG r(f);
240  return r;
241  }
242 
243  REG&
244  REG::operator |=(const REG& r2) {
245  if (e == r2.e)
246  return *this;
247  Exp* f = new Exp();
248  f->use_cnt = 1;
249  f->_n_pos = e->n_pos() + r2.e->n_pos();
250  f->type = REG::Exp::ET_OR;
251  f->data.kids[0] = e;
252  f->data.kids[1] = r2.e; r2.e->inc();
253  e=f;
254  return *this;
255  }
256 
257  REG
258  REG::operator +(const REG& r2) {
259  if (e == NULL) return r2;
260  if (r2.e == NULL) return *this;
261  Exp* f = new Exp();
262  f->use_cnt = 1;
263  f->_n_pos = e->n_pos() + r2.e->n_pos();
264  f->type = REG::Exp::ET_CONC;
265  f->data.kids[0] = e; e->inc();
266  f->data.kids[1] = r2.e; r2.e->inc();
267  REG r(f);
268  return r;
269  }
270 
271  REG&
272  REG::operator +=(const REG& r2) {
273  if (r2.e == NULL)
274  return *this;
275  if (e == NULL) {
276  e=r2.e; e->inc();
277  } else {
278  Exp* f = new Exp();
279  f->use_cnt = 1;
280  f->_n_pos = e->n_pos() + r2.e->n_pos();
281  f->type = REG::Exp::ET_CONC;
282  f->data.kids[0] = e;
283  f->data.kids[1] = r2.e; r2.e->inc();
284  e=f;
285  }
286  return *this;
287  }
288 
289  REG
291  if ((e == NULL) || (e->type == REG::Exp::ET_STAR))
292  return *this;
293  Exp* f = new Exp();
294  f->use_cnt = 1;
295  f->_n_pos = e->n_pos();
296  f->type = REG::Exp::ET_STAR;
297  f->data.kids[0] = e; e->inc();
298  REG r(f);
299  return r;
300  }
301 
302  REG
303  REG::operator ()(unsigned int n, unsigned int m) {
304  REG r;
305  if ((n>m) || (m == 0))
306  return r;
307  if (n>0) {
308  unsigned int i = n;
309  REG r0 = *this;
310  while (i>0)
311  if (i & 1) {
312  r = r0+r; i--;
313  } else {
314  r0 = r0+r0; i >>= 1;
315  }
316  }
317  if (m > n) {
318  unsigned int i = m-n;
319  REG s0;
320  s0 = s0 | *this;
321  REG s;
322  while (i>0)
323  if (i & 1) {
324  s = s0+s; i--;
325  } else {
326  s0 = s0+s0; i >>= 1;
327  }
328  r = r + s;
329  }
330  return r;
331  }
332 
333  REG
334  REG::operator ()(unsigned int n) {
335  REG r;
336  if (n > 0) {
337  REG r0 = *this;
338  unsigned int i = n;
339  while (i>0)
340  if (i & 1) {
341  r = r0+r; i--;
342  } else {
343  r0 = r0+r0; i >>= 1;
344  }
345  }
346  return r+**this;
347  }
348 
349  REG
351  return this->operator ()(1);
352  }
353 
354 
355  namespace MiniModel {
356 
357  /*
358  * Sets of positions
359  *
360  */
361 
365  enum PosSetCmp {
369  };
370 
374  class PosSet : public Support::BlockClient<PosSet,Heap> {
375  // Maintain sets of positions in inverse order
376  // This makes the check whether the last position is included
377  // more efficient.
378  public:
379  int pos; PosSet* next;
380 
381  PosSet(void);
382  PosSet(int);
383 
384  bool in(int) const;
385  static PosSetCmp cmp(PosSet*,PosSet*);
386  static PosSet* cup(PosSetAllocator&,PosSet*,PosSet*);
387  };
388 
389 
391  PosSet::PosSet(void) {}
393  PosSet::PosSet(int p) : pos(p), next(NULL) {}
394 
395 
396  forceinline bool
397  PosSet::in(int p) const {
398  for (const PosSet* ps = this; ps != NULL; ps = ps->next)
399  if (ps->pos == p) {
400  return true;
401  } else if (ps->pos < p) {
402  return false;
403  }
404  return false;
405  }
406 
408  PosSet::cmp(PosSet* ps1, PosSet* ps2) {
409  while ((ps1 != NULL) && (ps2 != NULL)) {
410  if (ps1 == ps2)
411  return PSC_EQ;
412  if (ps1->pos < ps2->pos)
413  return PSC_LE;
414  if (ps1->pos > ps2->pos)
415  return PSC_GR;
416  ps1 = ps1->next; ps2 = ps2->next;
417  }
418  if (ps1 == ps2)
419  return PSC_EQ;
420  return ps1 == NULL ? PSC_LE : PSC_GR;
421  }
422 
423  PosSet*
425  PosSet* ps;
426  PosSet** p = &ps;
427  while ((ps1 != NULL) && (ps2 != NULL)) {
428  if (ps1 == ps2) {
429  *p = ps1; return ps;
430  }
431  PosSet* n = new (psm) PosSet;
432  *p = n; p = &n->next;
433  if (ps1->pos == ps2->pos) {
434  n->pos = ps1->pos;
435  ps1 = ps1->next; ps2 = ps2->next;
436  } else if (ps1->pos > ps2->pos) {
437  n->pos = ps1->pos; ps1 = ps1->next;
438  } else {
439  n->pos = ps2->pos; ps2 = ps2->next;
440  }
441  }
442  *p = (ps1 != NULL) ? ps1 : ps2;
443  return ps;
444  }
445 
446 
448  class NodeInfo {
449  public:
450  bool nullable;
453  NodeInfo(bool n=false, PosSet* fp=NULL, PosSet* lp=NULL);
454  };
455 
457  class ExpInfo {
458  public:
460  bool open;
461  ExpInfo(REG::Exp* e=NULL);
462  };
463 
468  class PosInfo {
469  public:
470  int symbol;
472  };
473 
475  NodeInfo::NodeInfo(bool n, PosSet* fp, PosSet* lp)
476  : nullable(n), firstpos(fp), lastpos(lp) {}
477 
480  : exp(e), open(true) {}
481 
482  }
483 
486  MiniModel::PosInfo* pi) {
487  int p=0;
488 
489  using MiniModel::PosSet;
490  using MiniModel::NodeInfo;
491  using MiniModel::ExpInfo;
492 
495 
496  // Start with first expression to be processed
497  todo.push(ExpInfo(this));
498 
499  do {
500  if (todo.top().exp == NULL) {
501  todo.pop();
502  done.push(NodeInfo(true,NULL,NULL));
503  } else {
504  switch (todo.top().exp->type) {
505  case ET_SYMBOL:
506  {
507  pi[p].symbol = todo.pop().exp->data.symbol;
508  PosSet* ps = new (psm) PosSet(p++);
509  done.push(NodeInfo(false,ps,ps));
510  }
511  break;
512  case ET_STAR:
513  if (todo.top().open) {
514  // Evaluate subexpression recursively
515  todo.top().open = false;
516  todo.push(todo.top().exp->data.kids[0]);
517  } else {
518  todo.pop();
519  NodeInfo ni = done.pop();
520  for (PosSet* ps = ni.lastpos; ps != NULL; ps = ps->next)
521  pi[ps->pos].followpos =
522  PosSet::cup(psm,pi[ps->pos].followpos,ni.firstpos);
523  done.push(NodeInfo(true,ni.firstpos,ni.lastpos));
524  }
525  break;
526  case ET_CONC:
527  if (todo.top().open) {
528  // Evaluate subexpressions recursively
529  todo.top().open = false;
530  REG::Exp* e = todo.top().exp;
531  todo.push(e->data.kids[1]);
532  todo.push(e->data.kids[0]);
533  } else {
534  todo.pop();
535  NodeInfo ni1 = done.pop();
536  NodeInfo ni0 = done.pop();
537  for (PosSet* ps = ni0.lastpos; ps != NULL; ps = ps->next)
538  pi[ps->pos].followpos =
539  PosSet::cup(psm,pi[ps->pos].followpos,ni1.firstpos);
540  done.push(NodeInfo(ni0.nullable & ni1.nullable,
541  ni0.nullable ?
542  PosSet::cup(psm,ni0.firstpos,ni1.firstpos) : ni0.firstpos,
543  ni1.nullable ?
544  PosSet::cup(psm,ni0.lastpos,ni1.lastpos) : ni1.lastpos));
545  }
546  break;
547  case ET_OR:
548  if (todo.top().open) {
549  // Evaluate subexpressions recursively
550  todo.top().open = false;
551  REG::Exp* e = todo.top().exp;
552  todo.push(e->data.kids[1]);
553  todo.push(e->data.kids[0]);
554  } else {
555  todo.pop();
556  NodeInfo ni1 = done.pop();
557  NodeInfo ni0 = done.pop();
558  done.push(NodeInfo(ni0.nullable | ni1.nullable,
559  PosSet::cup(psm,ni0.firstpos,ni1.firstpos),
560  PosSet::cup(psm,ni0.lastpos,ni1.lastpos)));
561  }
562  break;
563  default: GECODE_NEVER;
564  }
565  }
566  } while (!todo.empty());
567  return done.top().firstpos;
568  }
569 
570 
571  namespace MiniModel {
572 
573  class StateNode;
574 
579 
583  class StateNode : public Support::BlockClient<StateNode,Heap> {
584  public:
586  int state;
590  };
591 
595  class StatePool {
596  public:
597  int n_states;
601 
602  StatePool(PosSet*);
603 
604  StateNode* pop(void);
605  bool empty(void) const;
606 
607  int state(StatePoolAllocator&, PosSet*);
608  };
609 
612  next = &root;
613  all = NULL;
614  n_states = 1;
615  root.pos = ps;
616  root.state = 0;
617  root.next = NULL;
618  root.left = NULL;
619  root.right = NULL;
620  }
621 
624  StateNode* n = next;
625  next = n->next;
626  n->next = all;
627  all = n;
628  return n;
629  }
630 
631  forceinline bool
632  StatePool::empty(void) const {
633  return next == NULL;
634  }
635 
636  forceinline int
638  int d = 0;
639  StateNode** p = NULL;
640  StateNode* n = &root;
641  do {
642  switch (PosSet::cmp(ps,n->pos)) {
643  case PSC_EQ: return n->state;
644  case PSC_LE: p = &n->left; n = *p; break;
645  case PSC_GR: p = &n->right; n = *p; break;
646  default: GECODE_NEVER;
647  }
648  d++;
649  } while (n != NULL);
650  n = new (spm) StateNode; *p = n;
651  n->pos = ps;
652  n->state = n_states++;
653  n->next = next;
654  n->left = NULL;
655  n->right = NULL;
656  next = n;
657  return n->state;
658  }
659 
663  class SymbolsInc {
664  public:
665  forceinline bool
666  operator ()(int x, int y) {
667  return x < y;
668  }
669  forceinline static void
670  sort(int s[], int n) {
671  SymbolsInc o;
672  Support::quicksort<int,SymbolsInc>(s,n,o);
673  }
674  };
675 
676 
682  private:
684  int n;
685  public:
686  TransitionBag(void);
687  void add(int,int,int);
688  void finish(void);
689  DFA::Transition* transitions(void);
690  };
691 
693  TransitionBag::TransitionBag(void) : t(heap), n(0) {}
694 
695  forceinline void
696  TransitionBag::add(int i_state, int symbol, int o_state) {
697  t[n].i_state = i_state;
698  t[n].symbol = symbol;
699  t[n].o_state = o_state;
700  n++;
701  }
702 
703  forceinline void
705  t[n].i_state = -1;
706  }
707 
710  return &t[0];
711  }
712 
713 
718  class FinalBag {
719  private:
721  int n;
722  public:
723  FinalBag(void);
724  void add(int);
725  void finish(void);
726  int* finals(void);
727  };
728 
730  FinalBag::FinalBag(void) : f(heap), n(0) {}
731 
732  forceinline void
733  FinalBag::add(int state) {
734  f[n++] = state;
735  }
736 
737  forceinline void
739  f[n] = -1;
740  }
741 
742  forceinline int*
744  return &f[0];
745  }
746 
747  }
748 
749  REG::operator DFA(void) {
752  using MiniModel::PosInfo;
753  using MiniModel::PosSet;
754  using MiniModel::NodeInfo;
755 
756  using MiniModel::StatePool;
757  using MiniModel::StateNode;
758 
760  using MiniModel::FinalBag;
761 
762  using MiniModel::SymbolsInc;
763 
764  PosSetAllocator psm(heap);
766  REG r = *this + REG(Int::Limits::max+1);
767  int n_pos = r.e->n_pos();
768 
769  PosInfo* pi = heap.alloc<PosInfo>(n_pos);
770  for (int i=n_pos; i--; )
771  pi[i].followpos = NULL;
772 
773  PosSet* firstpos = r.e->followpos(psm,&pi[0]);
774 
775  // Compute symbols
776  int* symbols = heap.alloc<int>(n_pos);
777  for (int i=n_pos; i--; )
778  symbols[i] = pi[i].symbol;
779 
780  SymbolsInc::sort(&symbols[0],n_pos-1);
781  int n_symbols = 1;
782  for (int i = 1; i<n_pos-1; i++)
783  if (symbols[i-1] != symbols[i])
784  symbols[n_symbols++] = symbols[i];
785 
786  // Compute states and transitions
787  TransitionBag tb;
788  StatePool sp(firstpos);
789  while (!sp.empty()) {
790  StateNode* sn = sp.pop();
791  for (int i = n_symbols; i--; ) {
792  PosSet* u = NULL;
793  for (PosSet* ps = sn->pos; ps != NULL; ps = ps->next)
794  if (pi[ps->pos].symbol == symbols[i])
795  u = PosSet::cup(psm,u,pi[ps->pos].followpos);
796  if (u != NULL)
797  tb.add(sn->state,symbols[i],sp.state(spm,u));
798  }
799  }
800  tb.finish();
801 
802  // Compute final states
803  FinalBag fb;
804  for (StateNode* n = sp.all; n != NULL; n = n->next)
805  if (n->pos->in(n_pos-1))
806  fb.add(n->state);
807  fb.finish();
808 
809  heap.free<PosInfo>(pi,n_pos);
810  heap.free<int>(symbols,n_pos);
811  return DFA(0,tb.transitions(),fb.finals(),true);
812  }
813 
814 }
815 
816 // STATISTICS: minimodel-any
817