diff options
author | Morgan Deters <mdeters@gmail.com> | 2011-05-23 21:58:12 +0000 |
---|---|---|
committer | Morgan Deters <mdeters@gmail.com> | 2011-05-23 21:58:12 +0000 |
commit | 3f7f9df5f0c419b7f7dd39e32852161f406a441f (patch) | |
tree | 67ae6454e4496f6370cf8236500946e2c7e926b0 /src/util | |
parent | 91656937b2188f05cdd9b42955c04e6157349285 (diff) |
Merge from arrays2 branch.
Diffstat (limited to 'src/util')
-rw-r--r-- | src/util/Makefile.am | 3 | ||||
-rw-r--r-- | src/util/backtrackable.h | 214 | ||||
-rw-r--r-- | src/util/ntuple.h | 93 | ||||
-rw-r--r-- | src/util/stats.h | 18 | ||||
-rw-r--r-- | src/util/triple.h | 43 |
5 files changed, 327 insertions, 44 deletions
diff --git a/src/util/Makefile.am b/src/util/Makefile.am index 5672d1eb2..b8f336f2d 100644 --- a/src/util/Makefile.am +++ b/src/util/Makefile.am @@ -20,6 +20,7 @@ libutilcudd_la_LIBADD = @CUDD_LDFLAGS@ libutil_la_SOURCES = \ Assert.h \ Assert.cpp \ + backtrackable.h \ Makefile.am \ Makefile.in \ congruence_closure.h \ @@ -47,7 +48,7 @@ libutil_la_SOURCES = \ dynamic_array.h \ language.h \ language.cpp \ - triple.h \ + ntuple.h \ recursion_breaker.h \ subrange_bound.h \ cardinality.h \ diff --git a/src/util/backtrackable.h b/src/util/backtrackable.h new file mode 100644 index 000000000..b11ebf957 --- /dev/null +++ b/src/util/backtrackable.h @@ -0,0 +1,214 @@ +/*! \file backtrackable.h + ** \verbatim + ** Original author: lianah + ** Major contributors: none + ** Minor contributors (to current version): none + ** This file is part of the CVC4 prototype. + ** Copyright (c) 2009, 2010 The Analysis of Computer Systems Group (ACSys) + ** Courant Institute of Mathematical Sciences + ** New York University + ** See the file COPYING in the top-level source directory for licensing + ** information.\endverbatim + ** + ** \brief Contains a backtrackable list + ** + ** + **/ + +#include "cvc4_private.h" +#ifndef __CVC4__UTIL__BACKTRACKABLE_H +#define __CVC4__UTIL__BACKTRACKABLE_H + + +#include <cstdlib> +#include <vector> +#include "context/cdo.h" + +namespace CVC4{ + +template <class T> class List; +template <class T> class List_iterator; +template <class T> class Backtracker; + +template <class T> +class ListNode{ +private: + T data; + ListNode<T>* next; + + bool empty; + ListNode(const T& t, ListNode<T>* n, bool e = false) : data(t), next(n), empty(e) {} + ~ListNode() { + // maybe set to NULL + delete next; + } + + friend class List<T>; + friend class List_iterator<T>; +}; /*class ListNode */ + +template <class T> +class List_iterator: public std::iterator <std::forward_iterator_tag, T> { + friend class List<T>; + +public: + const T& operator*(); + List_iterator<T>& operator++(); + List_iterator<T> operator++(int); + bool operator!=(const List_iterator<T> & other) const; +private: + const ListNode<T>* pointee; + List_iterator(const ListNode<T>* p) : pointee(p) {} + +}; /* class List_iterator */ + +template <class T> const T& List_iterator<T>::operator*() { + return pointee->data; +} + +template <class T> List_iterator<T>& List_iterator<T>::operator++() { + Assert(pointee != NULL); + pointee = pointee->next; + while(pointee != NULL && pointee->empty ) { + pointee = pointee->next; + } + return *this; +} + +template <class T> List_iterator<T> List_iterator<T>::operator++(int) { + List_iterator<T> it = *this; + ++*this; + return it; +} + +template <class T> bool List_iterator<T>::operator!=(const List_iterator<T>& other) const { + return (this->pointee != other.pointee); +} + +// !! for the backtracking to work the lists must be allocated on the heap +// therefore the hashmap from TNode to List<TNode> should store pointers! +template <class T> class List { + ListNode<T>* head; + ListNode<T>* tail; + ListNode<T>* ptr_to_head; + bool uninitialized; + Backtracker<T>* bck; + List (const List&) {} +public: + List(Backtracker<T>* b) : ptr_to_head(NULL), uninitialized(true), bck(b) { + head = tail = (ListNode<T>*)calloc(1,sizeof(ListNode<T>*)); + head->next = NULL; + head->empty = true; + } + ~List() {delete head;} + bool empty() { + bck->checkConsistency(); + return head == NULL; + } + void append(const T& d); + //typedef List_iterator<T> iterator; + typedef List_iterator<T> const_iterator; + + const_iterator begin() { + bck->checkConsistency(); + if(head->empty) { + ListNode<T>* temp = head; + // if the head is empty return the first non-empty element or NULL + while(temp != NULL && temp->empty ) { + temp = temp->next; + } + return List_iterator<T>(temp); + } + return List_iterator<T>(head); + } + + const_iterator end() { + bck->checkConsistency(); + return List_iterator<T>(NULL); + } + void concat(List<T>* other); + void unconcat(List<T>* other); +}; /* class List */ + +template <class T> +void List<T>::append (const T& d) { + bck->checkConsistency(); + + if(uninitialized) { + new(head)ListNode<T> (d, head->next); + //head->data = d; + head->empty = false; + //Assert(tail == head); FIXME: do I need this because this list might be empty but appende to another one + uninitialized = false; + + } else { + ListNode<T>* new_node = new ListNode<T>(d, head); + head = new_node; + } + + if(ptr_to_head != NULL) { + ptr_to_head->next = head; + } +} + +template <class T> +void List<T>::concat (List<T>* other) { + bck->checkConsistency(); + bck->notifyConcat(this, other); + Assert(tail->next==NULL); + tail->next = other->head; + Assert(other->ptr_to_head == NULL); + other->ptr_to_head = tail; + tail = other->tail; +} + +template <class T> +void List<T>::unconcat(List<T>* other) { + // we do not need to check consistency since this is only called by the + //Backtracker when we are inconsistent + Assert(other->ptr_to_head != NULL); + other->ptr_to_head->next = NULL; + tail = other->ptr_to_head; + other->ptr_to_head = NULL; +} + +/* Backtrackable Table */ + +template <class T> class Backtracker { + friend class List<T>; + std::vector<std::pair<List<T>*,List<T>*> > undo_stack; + + int curr_level; + context::CDO<int> pop_level; + + void checkConsistency(); + void notifyConcat(List<T>* a, List<T>* b); +public: + Backtracker(context::Context* c) : undo_stack(), curr_level(0), pop_level(c, 0) {} + ~Backtracker() {} + +}; /*class Backtrackable */ + +template <class T> void Backtracker<T>::notifyConcat(List<T>* a, List<T>* b) { + curr_level++; + pop_level.set(pop_level.get()+1); + undo_stack.push_back( std::make_pair(a, b)); +} + +template <class T> void Backtracker<T>::checkConsistency() { + if( curr_level == pop_level || pop_level == -1) { + return; + } + Assert(curr_level > pop_level); + + while (curr_level > pop_level) { + curr_level--; + List<T>* l1 = undo_stack[curr_level].first; + List<T>* l2 = undo_stack[curr_level].second; + l1->unconcat(l2); + undo_stack.pop_back(); + } + Assert(curr_level == pop_level); +} +} /* CVC4 namespace */ +#endif /* __CVC4__UTIL__BACKTRACKABLE_H */ diff --git a/src/util/ntuple.h b/src/util/ntuple.h new file mode 100644 index 000000000..a3b0dfdf4 --- /dev/null +++ b/src/util/ntuple.h @@ -0,0 +1,93 @@ +/********************* */ +/*! \file ntuple.h + ** \verbatim + ** Original author: mdeters + ** Major contributors: lianah + ** Minor contributors (to current version): none + ** This file is part of the CVC4 prototype. + ** Copyright (c) 2009, 2010, 2011 The Analysis of Computer Systems Group (ACSys) + ** Courant Institute of Mathematical Sciences + ** New York University + ** See the file COPYING in the top-level source directory for licensing + ** information.\endverbatim + ** + ** \brief Similar to std::pair<>, for triples and quadruples + ** + ** Similar to std::pair<>, for triples and quadruples. Once we move to c++0x, this + ** can be removed in favor of (standard-provided) N-ary tuples. + **/ + +#include "cvc4_private.h" + +#ifndef __CVC4__NTUPLE_H +#define __CVC4__NTUPLE_H + +namespace CVC4 { + +template <class T1, class T2, class T3> +class triple { +public: + T1 first; + T2 second; + T3 third; +};/* class triple<> */ + +template <class T1, class T2, class T3> +inline triple<T1, T2, T3> +make_triple(const T1& t1, const T2& t2, const T3& t3) { + return triple<T1, T2, T3>(t1, t2, t3); +}/* make_triple() */ + +template <class T1, class T2, class T3, class T4> +class quad { +public: + T1 first; + T2 second; + T3 third; + T4 fourth; + quad(const T1& t1, const T2& t2, const T3& t3, const T4& t4) { + first = t1; + second = t2; + third = t3; + fourth = t4; + } +};/* class quad<> */ + +template <class T1, class T2, class T3, class T4> +bool operator==(const quad<T1,T2,T3,T4>& x, + const quad<T1,T2,T3,T4>& y) { + return (x.first==y.first && x.second==y.second && + x.third == y.third && x.fourth==y.fourth); +} + +template <class T1, class T2, class T3, class T4> +bool operator<(const quad<T1,T2,T3,T4>& x, + const quad<T1,T2,T3,T4>& y) { + if(x.first< y.first) { + return true; + } + else if (x.first == y.first) { + if(x.second < y.second) { + return true; + } + else if(y.second == y.second) { + if(x.third < y.third) { + return true; + } + else if (x.fourth < y.fourth) { + return true; + } + } + } + return false; +} + +template <class T1, class T2, class T3, class T4> +inline quad<T1, T2, T3, T4> +make_quad(const T1& t1, const T2& t2, const T3& t3, const T4& t4) { + return quad<T1, T2, T3, T4>(t1, t2, t3, t4); +}/* make_quad() */ + +}/* CVC4 namespace */ + +#endif /* __CVC4__NTUPLE_H */ diff --git a/src/util/stats.h b/src/util/stats.h index 882cc1f81..a94733595 100644 --- a/src/util/stats.h +++ b/src/util/stats.h @@ -446,6 +446,24 @@ public: };/* class IntStat */ +template <class T> +class SizeStat : public Stat { +private: + const T& d_sized; +public: + SizeStat(const std::string&name, const T& sized) : + Stat(name), d_sized(sized) {} + ~SizeStat() {} + + void flushInformation(std::ostream& out) const { + out<< d_sized.size(); + } + std::string getValue() const { + std::stringstream ss; + flushInformation(ss); + return ss.str(); + } +};/* class SizeStat */ /** * The value for an AverageStat is the running average of (e1, e_2, ..., e_n), diff --git a/src/util/triple.h b/src/util/triple.h deleted file mode 100644 index 9229a9eee..000000000 --- a/src/util/triple.h +++ /dev/null @@ -1,43 +0,0 @@ -/********************* */ -/*! \file triple.h - ** \verbatim - ** Original author: mdeters - ** Major contributors: none - ** Minor contributors (to current version): none - ** This file is part of the CVC4 prototype. - ** Copyright (c) 2009, 2010, 2011 The Analysis of Computer Systems Group (ACSys) - ** Courant Institute of Mathematical Sciences - ** New York University - ** See the file COPYING in the top-level source directory for licensing - ** information.\endverbatim - ** - ** \brief Similar to std::pair<>, for triples - ** - ** Similar to std::pair<>, for triples. Once we move to c++0x, this - ** can be removed in favor of (standard-provided) N-ary tuples. - **/ - -#include "cvc4_private.h" - -#ifndef __CVC4__TRIPLE_H -#define __CVC4__TRIPLE_H - -namespace CVC4 { - -template <class T1, class T2, class T3> -class triple { -public: - T1 first; - T2 second; - T3 third; -}; - -template <class T1, class T2, class T3> -inline triple<T1, T2, T3> -make_triple(const T1& t1, const T2& t2, const T3& t3) { - return triple<T1, T2, T3>(t1, t2, t3); -} - -}/* CVC4 namespace */ - -#endif /* __CVC4__TRIPLE_H */ |