DDD  1.9.0.20240826145154
DDD.h
Go to the documentation of this file.
1 /****************************************************************************/
2 /* */
3 /* This file is part of libDDD, a library for manipulation of DDD and SDD. */
4 /* */
5 /* Copyright (C) 2001-2008 Yann Thierry-Mieg, Jean-Michel Couvreur */
6 /* and Denis Poitrenaud */
7 /* */
8 /* This program is free software; you can redistribute it and/or modify */
9 /* it under the terms of the GNU Lesser General Public License as */
10 /* published by the Free Software Foundation; either version 3 of the */
11 /* License, or (at your option) any later version. */
12 /* This program is distributed in the hope that it will be useful, */
13 /* but WITHOUT ANY WARRANTY; without even the implied warranty of */
14 /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
15 /* GNU LEsserGeneral Public License for more details. */
16 /* */
17 /* You should have received a copy of the GNU Lesser General Public License */
18 /* along with this program; if not, write to the Free Software */
19 /*Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
20 /* */
21 /****************************************************************************/
22 
23 /* -*- C++ -*- */
24 #ifndef DDD_H
25 #define DDD_H
26 
27 #include <iosfwd>
28 #include <string>
29 #include <vector>
30 
31 #include "ddd/DataSet.h"
32 #include "ddd/hashfunc.hh"
33 
35 class _GDDD;
36 
38 class DDD;
39 
48 class GDDD
49 {
50 public:
51  typedef unsigned int id_t;
52 private:
55  friend std::ostream& operator<<(std::ostream &os,const GDDD &g);
57  friend class DDD;
58 
64  GDDD(const id_t &_g);
67  GDDD(_GDDD *_g);
69  void print(std::ostream& os,std::string s) const;
71  void saveNode(std::ostream&, std::vector<id_t>& )const;
73  unsigned long int nodeIndex(const std::vector<id_t> &)const;
74 
75 public:
77 
78  typedef short val_t;
81  typedef unsigned short valsz_t;
83  typedef std::pair<val_t,GDDD> edge_t;
85  typedef std::vector<edge_t > Valuation;
88  typedef const edge_t * const_iterator;
90  int variable() const;
91 
98  const_iterator begin() const;
105  const_iterator end() const;
107 
109 
110  GDDD(int variable,const Valuation & value);
125  GDDD(int var,val_t val,const GDDD &d=one );
133  GDDD(int var,val_t val1,val_t val2,const GDDD &d=one); //var-[val1,var2]->d
135 
136 
138 
139  static const GDDD one;
143  static const GDDD null;
146  static const GDDD top;
148 
150 
151  bool operator==(const GDDD& g) const{return concret==g.concret;};
158  bool operator!=(const GDDD& g) const{return concret!=g.concret;};
163  bool operator<(const GDDD& g) const;
165 
166  /* Accessors */
170  unsigned int refCounter() const;
172  unsigned long int size() const;
174  size_t nbsons () const;
176  long double nbStates() const;
178  long double noSharedSize() const;
179 #ifdef EVDDD
181  int getMinDistance () const;
182  GDDD normalizeDistance (int n) const;
183 #endif
184 
185 
187 
188  static void varName( int var, const std::string& name );
197  static const std::string getvarName( int var );
199 
201 
202  static unsigned int statistics();
206  void mark() const;
208  size_t hash () const {
209  return ddd::int32_hash(concret);
210  }
213  static void garbage();
217  static void pstats(bool reinit=true);
219  static size_t peak();
221 
223  friend void saveDDD(std::ostream&, std::vector<DDD>);
226  friend void loadDDD(std::istream&, std::vector<DDD>&);
228 };
229 
230 
232 std::ostream& operator<<(std::ostream &,const GDDD &);
233 /* Binary operators */
236 GDDD operator^(const GDDD&,const GDDD&);
239 GDDD operator+(const GDDD&,const GDDD&);
242 GDDD operator*(const GDDD&,const GDDD&);
245 GDDD operator-(const GDDD&,const GDDD&);
246 
247 
248 
254 class DDD : public GDDD, public DataSet
255 {
256 public:
257  /* Constructors */
260  DDD(const DDD &);
263  DDD(const GDDD &g=GDDD::null);
264 
273  DDD(int var,val_t val,const GDDD &d=one );
281  DDD(int var,val_t val1,val_t val2,const GDDD &d=one);
285  ~DDD();
286 
288 
289  DDD &operator=(const GDDD&);
292  DDD &operator=(const DDD&);
294 
302 
303 
305  DataSet *newcopy () const { return new DDD(*this); }
307  DataSet *set_intersect (const DataSet & b) const ;
309  DataSet *set_union (const DataSet & b) const;
311  DataSet *set_minus (const DataSet & b) const;
313  bool empty() const;
315  DataSet *empty_set() const;
317  bool set_equal(const DataSet & b) const;
319  bool set_less_than (const DataSet & b) const ;
321  long double set_size() const;
323  size_t set_hash() const;
325  void set_print (std::ostream &os) const { os << *this; }
327  void mark() const { GDDD::mark(); }
328 #ifdef EVDDD
329  DataSet *normalizeDistance(int n) const { return new DDD(GDDD::normalizeDistance(n)); }
330  int getMinDistance() const { return GDDD::getMinDistance();}
331 #endif
332 
334 
335 
336 }; // DDD class
337 
338 
339 
340 namespace std {
343  template<>
344  struct less<GDDD> {
345  bool operator()(const GDDD &g1,const GDDD &g2) const{
346  return g1<g2;
347  }
348  };
349 }
350 
351 
352 #ifdef EVDDD
353 // the variable id of distance nodes
354 #define DISTANCE -3
355 #endif
356 
357 #endif
358 
359 
360 
361 
362 
363 
GDDD operator-(const GDDD &, const GDDD &)
Operator for set difference of DDD.
Definition: DED.cpp:663
GDDD operator*(const GDDD &, const GDDD &)
Operator for intersection of DDD.
Definition: DED.cpp:655
GDDD operator^(const GDDD &, const GDDD &)
Operator for concatenation of DDD.
Definition: DED.cpp:659
std::ostream & operator<<(std::ostream &, const GDDD &)
Textual output of DDD into a stream in (relatively) human readable format.
Definition: DDD.cpp:352
GDDD operator+(const GDDD &, const GDDD &)
Operator for union of DDD.
Definition: DED.cpp:648
This class is the public interface for manipulating Data Decision Diagrams.
Definition: DDD.h:255
DataSet * empty_set() const
Returns a pointer to GDDD::null.
Definition: DDD.cpp:649
bool empty() const
Return true if this is the empty set.
Definition: DDD.cpp:645
DDD & operator=(const GDDD &)
Overloaded behavior for assignment operator, maintains reference counting.
Definition: DDD.cpp:573
bool set_less_than(const DataSet &b) const
Compares two sets with a total order.
Definition: DDD.cpp:657
long double set_size() const
Compares to DataSet for equality.
Definition: DDD.cpp:662
void set_print(std::ostream &os) const
Textual (human readable) output of a DDD.
Definition: DDD.h:325
DataSet * set_union(const DataSet &b) const
Compute union of two DDD.
Definition: DDD.cpp:638
DataSet * set_minus(const DataSet &b) const
Compute set difference of two DDD.
Definition: DDD.cpp:641
bool set_equal(const DataSet &b) const
Compares to DataSet for equality.
Definition: DDD.cpp:653
DataSet * newcopy() const
Return a new copy of a DDD.
Definition: DDD.h:305
~DDD()
Destructor, maintains refCount.
Definition: DDD.cpp:569
size_t set_hash() const
Returns a hash key for the DDD.
Definition: DDD.cpp:664
void mark() const
mark() from DataSet interface
Definition: DDD.h:327
DataSet * set_intersect(const DataSet &b) const
Compute intersection of two DDD.
Definition: DDD.cpp:635
This class is an abstraction of a set of data.
Definition: DataSet.h:44
This class is the base class representing a Data Decision Diagram.
Definition: DDD.h:49
static const GDDD top
The approximation terminal.
Definition: DDD.h:146
bool operator==(const GDDD &g) const
Comparison between DDD.
Definition: DDD.h:154
friend void loadDDD(std::istream &, std::vector< DDD > &)
Function for deserialization. Load a set of DDD from a stream.
Definition: DDD.cpp:734
void print(std::ostream &os, std::string s) const
Internal function used in recursion for textual printing of GDDD.
Definition: DDD.cpp:335
void mark() const
For garbage collection internals.
Definition: DDD.cpp:308
static unsigned int statistics()
Returns unicity table current size. Gives the number of different nodes created and not yet destroyed...
Definition: DDD.cpp:303
static void garbage()
For garbage collection, do not call this directly, use MemoryManager::garbage() instead.
Definition: DDD.cpp:498
unsigned short valsz_t
A type wide enough to count how many outgoing edges a DDD node has, should be congruent to val_t.
Definition: DDD.h:81
static const GDDD one
The accepting terminal. This is the basic leaf for accepted sequences.
Definition: DDD.h:140
unsigned int refCounter() const
Returns current reference count of a node.
unsigned long int size() const
Returns the size in number of nodes of a DDD structure.
Definition: DDD.cpp:428
const_iterator begin() const
API for iterating over the arcs of a DDD manually.
Definition: DDD.cpp:386
std::vector< edge_t > Valuation
To hide how arcs are actually stored. Use GDDD::Valuation to refer to arcs type.
Definition: DDD.h:85
const_iterator end() const
API for iterating over the arcs of a DDD manually.
Definition: DDD.cpp:390
static void varName(int var, const std::string &name)
Sets a variable's name.
Definition: DDD.cpp:588
const edge_t * const_iterator
To hide how arcs are stored.
Definition: DDD.h:88
size_t nbsons() const
Returns the number of successors of a given node. This is the size of the arc array of the node.
Definition: DDD.cpp:382
friend class DDD
Open access to concret for reference counting in DDD.
Definition: DDD.h:57
long double noSharedSize() const
Returns the number of nodes that would be used to represent a DDD if no unicity table was used.
Definition: DDD.cpp:492
unsigned int id_t
Definition: DDD.h:51
GDDD()
Default constructor creates the empty set DDD.
Definition: DDD.h:117
unsigned long int nodeIndex(const std::vector< id_t > &) const
Another function used in serialization.
Definition: DDD.cpp:673
friend void saveDDD(std::ostream &, std::vector< DDD >)
Function for serialization. Save a set of DDD to a stream.
Definition: DDD.cpp:706
GDDD(_GDDD *_g)
UNIMPLEMENTED DELIBERATELY: see SHom.h for details.
static size_t peak()
Returns the peak size of the DDD unicity table. This value is maintained up to date upon GarbageColle...
Definition: DDD.cpp:313
bool operator!=(const GDDD &g) const
Comparison between DDD.
Definition: DDD.h:158
int variable() const
Returns a node's variable.
Definition: DDD.cpp:378
static const GDDD null
The non-accepting terminal.
Definition: DDD.h:143
friend std::ostream & operator<<(std::ostream &os, const GDDD &g)
A textual output.
Definition: DDD.cpp:352
static void pstats(bool reinit=true)
Prints some statistics to std::cout.
Definition: DDD.cpp:318
long double nbStates() const
Returns the number of states or paths represented by a given node.
Definition: DDD.cpp:482
void saveNode(std::ostream &, std::vector< id_t > &) const
A function for DDD serialization (beta).
Definition: DDD.cpp:683
id_t concret
The real implementation class.
Definition: DDD.h:61
short val_t
The type used as values of variables in a DDD.
Definition: DDD.h:79
size_t hash() const
For storage in a hash table.
Definition: DDD.h:208
static const std::string getvarName(int var)
Gets a variable's name.
Definition: DDD.cpp:592
bool operator<(const GDDD &g) const
Total ordering function between DDD.
Definition: DDD.cpp:375
std::pair< val_t, GDDD > edge_t
An edge is a pair <value,child node>
Definition: DDD.h:83
Definition: DDD.cpp:57
uint32_t int32_hash(uint32_t a)
Another of Wang's fast hash with a magic number.
Definition: hashfunc.hh:56
Definition: DDD.h:340
bool operator()(const GDDD &g1, const GDDD &g2) const
Definition: DDD.h:345

Please comment this page and report errors about it on the RefDocComments page.
Generated on Mon Aug 26 2024 14:54:00 for DDD by doxygen 1.9.1