Logo Search packages:      
Sourcecode: faust version File versions  Download package

tree.hh

Go to the documentation of this file.
/************************************************************************
 ************************************************************************
    FAUST compiler
      Copyright (C) 2003-2004 GRAME, Centre National de Creation Musicale
    ---------------------------------------------------------------------
    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 ************************************************************************
 ************************************************************************/


/*****************************************************************************
******************************************************************************/

/** \file tree.hh
 * A tree library with hashconsing and maximal sharing capabilities.
 *
 * A tree library with hashconsing and maximal sharing capabilities.
 *
 * <b>API:</b>
 *
 * \li tree (n)                     : tree of node n with no branch
 * \li tree (n, t1)                 : tree of node n with a branch t
 * \li tree (n, t1,...,tm)          : tree of node n with m branches t1,...,tm
 *
 * <b>Useful conversions :</b>
 *
 * \li int              tree2int (t)      : if t has a node of type int, return it otherwise error
 * \li float            tree2float (t)    : if t has a node of type float, return it otherwise error
 * \li const char*      tree2str (t)      : if t has a node of type symbol, return its name otherwise error
 * \li void*            tree2ptr (t)      : if t has a node of type ptr, return it otherwise error
 *
 * <b>Pattern matching :</b>
 *
 * \li if (isTree (t, n))           ...   : t has node n and no branches;
 * \li if (isTree (t, n, &t1)       ... : t has node n and 1 branch, t1 is set accordingly;
 * \li if (isTree (t, n, &t1...&tm)...    : t has node n and m branches, ti's are set accordingly;
 *
 * <b>Accessors :</b>
 *
 * \li t->node()        : the node of t         { return fNode; }
 * \li t->height()            : lambda height such that H(x)=0, H(\x.e)=1+H(e), H(e*f)=max(H(e),H(f))
 * \li t->arity()             : the number of branches of t { return fArity; }
 * \li t->branch(i)     : the ith branch of t
 *
 * <b>Attributs :</b>
 *
 * \li t->attribut()    : return the attribut (also a tree) of t
 * \li t->attribut(t')  : set the attribut of t to t'
 *
 *
 * <b>Properties:</b>
 *
 * If p and q are two CTree pointers  :
 *          p != q  <=>  *p != *q
 *
 **/

/*****************************************************************************
******************************************************************************/



#ifndef     __TREE__
#define     __TREE__

#include "symbol.hh"
#include "node.hh"
#include <vector>
#include <map>
#include <assert.h>

//---------------------------------API---------------------------------------

class       CTree;
typedef CTree* Tree;

typedef map<Tree, Tree> plist;
typedef vector<Tree>    tvec;

/**
 * A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches.
 * A CTree = (Node x [CTree]) is the association of a content Node and a list of subtrees
 * called branches. In order to maximize the sharing of trees, hashconsing techniques are used.
 * Ctrees at different addresses always have a different content. A first consequence of this
 * approach is that a fast equality test on pointers can be used as an equality test on CTrees.
 * A second consequence is that a CTree can NEVER be modified. But a property list is associated
 * to each CTree that can be used to attach arbitrary information to it. Due to the maximal
 * sharing property it is therefore easy to do memoization using these property lists.
 *
 * Means are also provided to do maximal sharing on recursive trees. The idea is to start from
 * a deBruijn representation and progressively build a classical representation such that
 * alpha-equivalent recursive CTrees are necesseraly identical (and therefore shared).
 *
 * WARNING : in the current implementation CTrees are allocated but never deleted
 **/

00109 class CTree
{
 private:
      static const int  kHashTableSize = 2000000; //510511; ///< size of the hash table used for "hash consing"
00113       static Tree             gHashTable[kHashTableSize];   ///< hash table used for "hash consing"

 public:
00116       static bool             gDetails;                           ///< Ctree::print() print with more details when true

 private:
      // fields
00120       Tree        fNext;                        ///< next tree in the same hashtable entry
00121       Node        fNode;                        ///< the node content of the tree
00122       void*       fType;                        ///< the type of a tree 
00123       plist       fProperties;            ///< the properties list attached to the tree
00124       unsigned int            fHashKey;               ///< the hashtable key
00125       int               fAperture;              ///< how "open" is a tree (synthezised field)
00126       tvec        fBranch;                ///< the subtrees

      CTree (unsigned int hk, const Node& n, const tvec& br);                                   ///< construction is private, uses tree::make instead

      bool        equiv                         (const Node& n, const tvec& br) const;    ///< used to check if an equivalent tree already exists
      static unsigned int     calcTreeHash            (const Node& n, const tvec& br);          ///< compute the hash key of a tree according to its node and branches
      static int  calcTreeAperture  (const Node& n, const tvec& br);          ///< compute how open is a tree

 public:
      ~CTree ();

      static Tree make (const Node& n, int ar, Tree br[]);        ///< return a new tree or an existing equivalent one
      static Tree make(const Node& n, const tvec& br);                  ///< return a new tree or an existing equivalent one

      // Accessors
00141       const Node& node() const            { return fNode;         }     ///< return the content of the tree
00142       int         arity() const           { return fBranch.size();}     ///< return the number of branches (subtrees) of a tree
00143       Tree        branch(int i) const     { return fBranch[i];    }     ///< return the ith branch (subtree) of a tree
00144       unsigned int            hashkey() const         { return fHashKey;            }     ///< return the hashkey of the tree
00145       int         aperture() const  { return fAperture;     }     ///< return how "open" is a tree in terms of free variables
00146       void        setAperture(int a)      { fAperture=a;                }     ///< modify the aperture of a tree


      // Print a tree and the hash table (for debugging purposes)
      ostream&    print (ostream& fout) const;                          ///< print recursively the content of a tree on a stream
      static void control ();                                                       ///< print the hash table content (for debug purpose)

      // type information
      void        setType(void* t)  { fType = t; }
      void*       getType()               { return fType; }
      
      // Property list of a tree
      void        setProperty(Tree key, Tree value) { fProperties[key] = value; }
      void        clearProperty(Tree key) { fProperties.erase(key); }
      void        clearProperties()       { fProperties = plist(); }

      void        exportProperties(vector<Tree>& keys, vector<Tree>& values);

      Tree        getProperty(Tree key) {
            plist::iterator i = fProperties.find(key);
            if (i==fProperties.end()) {
                  return 0;
            } else {
                  return i->second;
            }
      }
};

//---------------------------------API---------------------------------------

// to build trees
inline Tree tree (const Node& n) { Tree br[1]; return CTree::make(n, 0, br); }
inline Tree tree (const Node& n, const Tree& a) { Tree br[]= {a}; return CTree::make(n, 1, br); }
inline Tree tree (const Node& n, const Tree& a, const Tree& b) { Tree br[]= {a,b}; return CTree::make(n, 2, br); }
inline Tree tree (const Node& n, const Tree& a, const Tree& b, const Tree& c) { Tree br[]= {a,b,c}; return CTree::make(n, 3, br); }
inline Tree tree (const Node& n, const Tree& a, const Tree& b, const Tree& c, const Tree& d) { Tree br[]= {a,b,c,d}; return CTree::make(n, 4, br); }

inline Tree tree (const Node& n, const Tree& a, const Tree& b, const Tree& c, const Tree& d, const Tree& e) { Tree br[]= {a,b,c,d,e}; return CTree::make(n, 5, br); }

// useful conversions
int         tree2int (Tree t);            ///< if t has a node of type int, return it otherwise error
double      tree2float (Tree t);    ///< if t has a node of type float, return it otherwise error
double      tree2double (Tree t);    ///< if t has a node of type float, return it otherwise error
const char* tree2str (Tree t);            ///< if t has a node of type symbol, return its name otherwise error
void*             tree2ptr (Tree t);            ///< if t has a node of type ptr, return it otherwise error
void*       getUserData(Tree t);    ///< if t has a node of type symbol, return the associated user data

// pattern matching
bool isTree (const Tree& t, const Node& n);
bool isTree (const Tree& t, const Node& n, Tree& a);
bool isTree (const Tree& t, const Node& n, Tree& a, Tree& b);
bool isTree (const Tree& t, const Node& n, Tree& a, Tree& b, Tree& c);
bool isTree (const Tree& t, const Node& n, Tree& a, Tree& b, Tree& c, Tree& d);
bool isTree (const Tree& t, const Node& n, Tree& a, Tree& b, Tree& c, Tree& d, Tree& e);

//printing
inline ostream& operator << (ostream& s, const CTree& t) { return t.print(s); }


//-----------------------------------------------------------------------------
// recursive trees
//-----------------------------------------------------------------------------

// creation a recursive trees

Tree rec(Tree body);                                  ///< create a de Bruijn recursive tree
Tree rec(Tree id, Tree body);                   ///< create a symbolic recursive tree

bool isRec(Tree t, Tree& body);                       ///< is t a de Bruijn recursive tree
bool isRec(Tree t, Tree& id, Tree& body); ///< is t a symbolic recursive tree

// creation of recursive references

Tree ref(int level);                                  ///< create a de Bruijn recursive reference
Tree ref(Tree id);                                          ///< create a symbolic recursive reference

bool isRef(Tree t, int& level);                       ///< is t a de Bruijn recursive reference
bool isRef(Tree t, Tree& id);                   ///< is t a symbolic recursive reference


// Open vs Closed regarding de Bruijn references

00228 inline bool isOpen(Tree t)     { return t->aperture() > 0; }      ///< t contains free de Bruijn references
00229 inline bool isClosed(Tree t) { return t->aperture() <= 0;}  ///< t dont contain free de Bruijn ref

// lift by 1 the free de Bruijn references

Tree lift(Tree t);                                          ////< add 1 to the free de bruijn references of t

Tree deBruijn2Sym (Tree t);                           ////< transform a tree from deBruijn to symbolic notation
void updateAperture (Tree t);                   ////< update aperture field of a tree in symbolic notation

//---------------------------------------------------------------------------

class Tabber
{
      int fIndent;
  public:
      Tabber(int n=0) : fIndent(n)  {}
      Tabber& operator++()                { fIndent++; return *this;}
      Tabber& operator--()                { assert(fIndent > 0); fIndent--; return *this; }

      ostream& print (ostream& fout)
                                    { for (int i=0; i<fIndent; i++) fout << '\t'; return fout; }
};

//printing
inline ostream& operator << (ostream& s, Tabber& t) { return t.print(s); }

extern Tabber TABBER;


#endif

Generated by  Doxygen 1.6.0   Back to index