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.
 ************************************************************************
 ************************************************************************/


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

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



#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;

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

 public:
    static bool         gDetails;                   
    static unsigned int gVisitTime;                 

 private:
    // fields
    Tree            fNext;              
    Node            fNode;              
    void*           fType;              
    plist           fProperties;        
    unsigned int    fHashKey;           
    int             fAperture;          
    unsigned int    fVisitTime;         
    tvec            fBranch;            

    CTree (unsigned int hk, const Node& n, const tvec& br);                         

    bool        equiv               (const Node& n, const tvec& br) const;  
    static unsigned int calcTreeHash        (const Node& n, const tvec& br);        
    static int  calcTreeAperture    (const Node& n, const tvec& br);        

 public:
    ~CTree ();

    static Tree make (const Node& n, int ar, Tree br[]);        
    static Tree make(const Node& n, const tvec& br);            

    // Accessors
    const Node& node() const        { return fNode;         }   
    int         arity() const       { return (int)fBranch.size();}  
    Tree        branch(int i) const { return fBranch[i];    }   
    const tvec& branches() const    { return fBranch;   }       
    unsigned int        hashkey() const     { return fHashKey;      }   
    int         aperture() const    { return fAperture;     }   
    void        setAperture(int a)  { fAperture=a;          }   


    // Print a tree and the hash table (for debugging purposes)
    ostream&    print (ostream& fout) const;                    
    static void control ();                                     

    // type information
    void        setType(void* t)    { fType = t; }
    void*       getType()           { return fType; }
    
    // Keep track of visited trees (WARNING : non reentrant)
    static void     startNewVisit()                 { ++gVisitTime; }
    bool            isAlreadyVisited()              { return fVisitTime==gVisitTime; }
    void            setVisited()                    { /*assert(fVisitTime!=gVisitTime);*/ fVisitTime=gVisitTime; }


    // 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); }
inline Tree tree (const Node& n, const tvec& br) { return CTree::make(n, br); }

// useful conversions
int         tree2int (Tree t);      
double      tree2float (Tree t);    
double      tree2double (Tree t);    
const char* tree2str (Tree t);      
void*       tree2ptr (Tree t);      
void*       getUserData(Tree t);    

// 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);                        
Tree rec(Tree id, Tree body);               

bool isRec(Tree t, Tree& body);             
bool isRec(Tree t, Tree& id, Tree& body);   

// creation of recursive references

Tree ref(int level);                        
Tree ref(Tree id);                          

bool isRef(Tree t, int& level);             
bool isRef(Tree t, Tree& id);               


// Open vs Closed regarding de Bruijn references

inline bool isOpen(Tree t)   { return t->aperture() > 0; }  
inline bool isClosed(Tree t) { return t->aperture() <= 0;}  

// lift by 1 the free de Bruijn references

Tree lift(Tree t);                          

Tree deBruijn2Sym (Tree t);                 
void updateAperture (Tree t);               

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

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

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

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

extern Tabber TABBER;


#endif