DDD 1.9.0.20250409152518
SDD.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 SDD_H
25#define SDD_H
26
27
28#include <string>
29
30#include "ddd/UniqueTable.h"
31#include "ddd/DataSet.h"
32
33
34// #define HEIGHTSDD
35
37class _GSDD;
38
39/******************************************************************************/
49class GSDD :public DataSet {
50private:
53 friend std::ostream& operator<<(std::ostream &os,const GSDD &g);
55 friend class SDD;
57 friend class _GSDD;
60 const _GSDD *concret;
62 void print(std::ostream& os,std::string s) const;
63public:
65
66
67 typedef std::vector<std::pair<DataSet *,GSDD> > Valuation;
70 typedef Valuation::const_iterator const_iterator;
72 int variable() const;
79 const_iterator begin() const;
86 const_iterator end() const;
87
89
90
91
92
93 /* Constructeurs */
95
96
99 GSDD(int variable,Valuation value);
109 GSDD(int var,const DataSet & val,const GSDD &d=one ); //var-val->d
117 GSDD(int var,const GSDD & val,const GSDD &d=one ); //var-val->d
118 GSDD(int var,const class SDD & val,const GSDD &d=one ); //var-val->d
121 GSDD(const _GSDD &_g);
124 GSDD(_GSDD *_g);
126 GSDD(const _GSDD *_g);
128
129 /* Constants */
131
132
133 static const GSDD one;
136 static const GSDD null;
140 static const GSDD top;
142
143
144 /* Compare */
146
147
150 bool operator==(const GSDD& g) const{return concret==g.concret;};
154 bool operator!=(const GSDD& g) const{return concret!=g.concret;};
159 bool operator<(const GSDD& g) const ;
160
162
163 /* Visualisation */
164 /* Accessors */
168 unsigned int refCounter() const;
170 unsigned long int size() const;
171 // Returns the size in number of nodes of a SDD + DDD mixed structure.
172 // \return a pair <number of SDD nodes,number of DDD nodes>
173 std::pair<unsigned long int,unsigned long int> node_size() const;
175 size_t nbsons () const;
177 long double nbStates() const;
178#ifdef HEIGHTSDD
181 short int getHeight () const;
182#endif
183
184#ifdef EVDDD
186 int getMinDistance () const;
187 GSDD normalizeDistance (int n) const;
188#endif
189
192 // long double GSDD::noSharedSize() const;
193
194
195 /* Memory Manager */
197
198
199 static unsigned int statistics();
202 void mark()const;
204 size_t hash () const {
205 return ddd::knuth32_hash(reinterpret_cast<size_t>(concret));
206 }
209 static void garbage();
213 static void pstats(bool reinit=true);
215 static size_t peak();
216
218
226
227 // DataSet interface
229 DataSet *newcopy () const { return new GSDD(*this); }
231 DataSet *set_intersect (const DataSet & b) const ;
233 DataSet *set_union (const DataSet & b) const;
235 DataSet *set_minus (const DataSet & b) const;
237 bool empty() const;
239 DataSet *empty_set() const;
241 bool set_equal(const DataSet & b) const;
243 bool set_less_than (const DataSet & b) const ;
245 long double set_size() const;
247 size_t set_hash() const;
249 void set_print (std::ostream &os) const { os << *this; }
250
252
253};
254
255
257std::ostream& operator<<(std::ostream &,const GSDD &);
258/* Binary operators */
261GSDD operator^(const GSDD&,const GSDD&); // concatenation
264GSDD operator+(const GSDD&,const GSDD&); // union
267GSDD operator*(const GSDD&,const GSDD&); // intersection
270GSDD operator-(const GSDD&,const GSDD&); // difference
271
272
273/******************************************************************************/
279class SDD:public GSDD {
280public:
281 /* Constructeur */
284 SDD(const SDD &);
287 SDD(const GSDD &g=GSDD::null);
296 SDD(int var,const DataSet& val,const GSDD &d=one ); //var-val->d
297 SDD(int var,const GSDD& val,const GSDD &d=one ); //var-val->d
298 // to disambiguate when using SDD as referenced type
299 SDD(int var,const SDD& val,const GSDD &d=one ); //var-val->d
303 virtual ~SDD();
304
305 /* Set */
307
308
309 SDD &operator=(const GSDD&);
311 SDD &operator=(const SDD&);
313
314#ifdef EVDDD
315 virtual DataSet *normalizeDistance(int n) const { return new SDD(GSDD::normalizeDistance(n)); }
316 virtual int getMinDistance() const { return GSDD::getMinDistance();}
317#endif
318
320
321};
322
325namespace SDDutil {
331 void foreachTable (void (*foo) (const GSDD & g));
332}
333
334
335namespace std {
338 template<>
339 struct less<GSDD> {
340 bool operator()(const GSDD &g1,const GSDD &g2) const{
341 return g1<g2;
342 }
343 };
344}
345
346
347
348
349#endif
350
351
GSDD operator+(const GSDD &, const GSDD &)
Operator for union of DDD.
Definition SDED.cpp:717
GSDD operator*(const GSDD &, const GSDD &)
Operator for intersection of DDD.
Definition SDED.cpp:721
GSDD operator-(const GSDD &, const GSDD &)
Operator for set difference of DDD.
Definition SDED.cpp:729
GSDD operator^(const GSDD &, const GSDD &)
Operator for concatenation of two SDD.
Definition SDED.cpp:725
std::ostream & operator<<(std::ostream &, const GSDD &)
Textual output of SDD into a stream in (relatively) human readable format.
Definition SDD.cpp:319
This class is an abstraction of a set of data.
Definition DataSet.h:44
This class is the base class representing a hierarchical Set Decision Diagram.
Definition SDD.h:49
friend class SDD
Open access to concret for reference counting in DDD.
Definition SDD.h:55
DataSet * set_intersect(const DataSet &b) const
Compute intersection of two SDD.
Definition SDD.cpp:663
std::pair< unsigned long int, unsigned long int > node_size() const
Definition SDD.cpp:490
GSDD(int var, const class SDD &val, const GSDD &d=one)
DataSet * set_minus(const DataSet &b) const
Compute set difference of two SDD.
Definition SDD.cpp:669
static unsigned int statistics()
Returns unicity table current size. Gives the number of different nodes created and not yet destroyed...
Definition SDD.cpp:255
bool set_equal(const DataSet &b) const
Compares to DataSet for equality.
Definition SDD.cpp:681
DataSet * newcopy() const
Return a new copy of a SDD.
Definition SDD.h:229
void print(std::ostream &os, std::string s) const
Internal function used in recursion for textual printing of GDDD.
Definition SDD.cpp:296
bool operator!=(const GSDD &g) const
Comparison between DDD.
Definition SDD.h:154
static void pstats(bool reinit=true)
Prints some statistics to std::cout.
Definition SDD.cpp:281
bool set_less_than(const DataSet &b) const
Compares two sets with a total order.
Definition SDD.cpp:685
unsigned long int size() const
Returns the size in number of nodes of a SDD structure.
Definition SDD.cpp:501
GSDD()
Default constructor creates the empty set SDD.
Definition SDD.h:101
static const GSDD one
The accepting terminal. This is the basic leaf for accepted sequences.
Definition SDD.h:133
DataSet * empty_set() const
Returns a pointer to GSDD::null.
Definition SDD.cpp:677
const_iterator end() const
API for iterating over the arcs of a DDD manually.
Definition SDD.cpp:400
int variable() const
Returns a node's variable.
Definition SDD.cpp:377
Valuation::const_iterator const_iterator
To hide how arcs are stored.
Definition SDD.h:70
const_iterator begin() const
API for iterating over the arcs of a DDD manually.
Definition SDD.cpp:396
long double nbStates() const
Returns the number of states or paths represented by a given node.
Definition SDD.cpp:552
bool empty() const
Return true if this is the empty set.
Definition SDD.cpp:673
GSDD(_GSDD *_g)
UNIMPLEMENTED DELIBERATELY: see SHom.h for details.
friend std::ostream & operator<<(std::ostream &os, const GSDD &g)
A textual output.
Definition SDD.cpp:319
static size_t peak()
Returns the peak size of the DDD unicity table. This value is maintained up to date upon GarbageColle...
Definition SDD.cpp:274
void set_print(std::ostream &os) const
Textual (human readable) output of a SDD.
Definition SDD.h:249
long double set_size() const
Compares to DataSet for equality.
Definition SDD.cpp:689
bool operator<(const GSDD &g) const
Total ordering function between DDD.
Definition SDD.cpp:381
bool operator==(const GSDD &g) const
Comparison between DDD.
Definition SDD.h:150
static void garbage()
For garbage collection, do not call this directly, use MemoryManager::garbage() instead.
Definition SDD.cpp:558
unsigned int refCounter() const
Returns current reference count of a node.
Definition SDD.cpp:405
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 SDD.cpp:386
const _GSDD * concret
The real implementation class.
Definition SDD.h:60
size_t set_hash() const
Returns a hash key for the SDD.
Definition SDD.cpp:691
std::vector< std::pair< DataSet *, GSDD > > Valuation
To hide how arcs are actually stored. Use GSDD::Valuation to refer to arcs type.
Definition SDD.h:67
size_t hash() const
For storage in a hash table.
Definition SDD.h:204
DataSet * set_union(const DataSet &b) const
Compute union of two SDD.
Definition SDD.cpp:666
static const GSDD top
The approximation terminal.
Definition SDD.h:140
void mark() const
For garbage collection internals.
Definition SDD.cpp:260
static const GSDD null
The non-accepting terminal.
Definition SDD.h:136
This class is the public interface for manipulating Data Decision Diagrams.
Definition SDD.h:279
virtual ~SDD()
Destructor, maintains refCount.
Definition SDD.cpp:622
SDD & operator=(const GSDD &)
Overloaded behavior for assignment operator, maintains reference counting.
Definition SDD.cpp:628
This class implements a unicity table mechanism, based on an STL hash_set.
Definition UniqueTable.h:43
Definition SDD.cpp:59
size_t knuth32_hash(size_t key)
Knuth's Multiplicative hash function.
Definition hashfunc.hh:73
Namespace declared to hide these functions.
Definition SDD.cpp:222
void foreachTable(void(*foo)(const GSDD &g))
Iterator over the entries of the table, applies foo to each entry in the table.
Definition SDD.cpp:228
UniqueTable< _GSDD > * getTable()
accessor to UniqueTable instance declared in cpp file, (hem, please don't touch it).
Definition SDD.cpp:224
Definition DDD.h:340
bool operator()(const GSDD &g1, const GSDD &g2) const
Definition SDD.h:340

Please comment this page and report errors about it on the RefDocComments page.
Generated on Wed Apr 9 2025 15:27:42 for DDD by doxygen 1.9.8