/************************************************************************
 ************************************************************************
    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.
 ************************************************************************
 ************************************************************************/
 
 
 
/*****************************************************************************
******************************************************************************
								TREE 
						Y. Orlarey, (c) Grame 2002
------------------------------------------------------------------------------
Trees are made of a Node associated with a list of branches : (Node x [CTree]).
Up to 4 branches are allowed in this implementation. A hash table is used to 
maximize the sharing of trees during construction : trees at different 
addresses always have a different content. Reference counting is used for 
garbage collection, and smart pointers P<CTree> should be used for permanent
storage of trees.

 API:
 ----
 tree (n) 				: tree of node n with no branch				
 tree (n, t1) 			: tree of node n with a branch t
 tree (n, t1,...,tm)	: tree of node n with m branches t1,...,tm
 
 Pattern matching :
 
 if (isTree (t, n)) 		... : t has node n and no branches; 
 if (isTree (t, n, &t1)		... : t has node n and 1 branch, t1 is set accordingly; 
 if (isTree (t, n, &t1...&tm)...: t has node n and m branches, ti's are set accordingly; 
 
 Accessors :
		 
 t->node()			: the node of t		{ return fNode; }
 t->arity() 		: the number of branches of t return fArity; }
 t->branch(i) 		: the ith branch of t

 Attributs :
		 
 t->attribut() 		: return the attribut (also a tree) of t
 t->attribut(t')	: set the attribut of t to t' 
		 
 Warning :
 ---------
 Since reference counters are used for garbage collecting, one must be careful not to 
 create cycles in trees The only possible source of cycles is by setting the attribut
 of a tree t to a tree t' that contains t as a subtree.  
	
 Properties:
 -----------
	If p and q are two CTree pointers  : 
		p != q  <=>  *p != *q

 History :
 ---------
 	2002-02-08 : First version
	2002-10-14 : counts for height and recursiveness added
	
******************************************************************************
*****************************************************************************/

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include "tree.hh"
#include <fstream>
#include <cstdlib>

Tabber TABBER(1);	
extern Tabber TABBER;


static void error(const char * s, Tree t)
{
	//fprintf(stderr, "ERROR : %s (%p)\n", s, t);
	cerr << "ERROR : " << s << " : " << *t << endl;
}

#define ERROR(s,t) { error(s,t); exit(1); }


Tree CTree::gHashTable[kHashTableSize];
bool CTree::gDetails = false;
unsigned int  CTree::gVisitTime = 0;

// Constructor : add the tree to the hash table
CTree::CTree (unsigned int hk, const Node& n, const tvec& br) 
	:	fNode(n), 
		fType(0),
		fHashKey(hk), 
	 	fAperture(calcTreeAperture(n,br)), 
        fVisitTime(0),
		fBranch(br) 
{ 
	// link dans la hash table
   	int j = hk % kHashTableSize;
	fNext = gHashTable[j];
	gHashTable[j] = this;

}

// Destructor : remove the tree form the hash table
CTree::~CTree () 
{
	int		i = fHashKey % kHashTableSize;
	Tree	t = gHashTable[i];
	
	//printf("Delete of "); this->print(); printf("\n");
	if (t == this) {
		gHashTable[i] = fNext;
	} else {
		Tree p;
		while (t != this) {
			p = t;
			t = t->fNext;
		}
		p->fNext = fNext;
	}
}

// equivalence 
bool CTree::equiv (const Node& n, const tvec& br) const
{
	return (fNode == n) && (fBranch == br);
}

Sym PROCESS = symbol("process"); 

		


unsigned int CTree::calcTreeHash( const Node& n, const tvec& br )
{
	unsigned int 			hk = n.type() ^ n.getInt();
	tvec::const_iterator  b = br.begin();
	tvec::const_iterator  z = br.end();
	
	while (b != z) {
    	hk = (hk << 1) ^ (hk >> 20) ^ ((*b)->fHashKey);
		++b;
	}
	return hk;
}


Tree CTree::make(const Node& n, int ar, Tree* tbl)
{
	tvec	br(ar); 
	
	for (int i=0; i<ar; i++)  br[i] = tbl[i];
	
	unsigned int 	hk  = calcTreeHash(n, br);
	Tree	t = gHashTable[hk % kHashTableSize];
	
	while (t && !t->equiv(n, br)) {
		t = t->fNext;
	}
	return (t) ? t : new CTree(hk, n, br);
}


Tree CTree::make(const Node& n, const tvec& br)
{
	unsigned int 	hk  = calcTreeHash(n, br);
	Tree	t = gHashTable[hk % kHashTableSize];
	
	while (t && !t->equiv(n, br)) {
		t = t->fNext;
	}
	return (t) ? t : new CTree(hk, n, br);
}

ostream& CTree::print (ostream& fout) const
{
    if (gDetails) {
        // print the adresse of the tree
		fout << "<" << this << ">@"; 
    }
	fout << node();
	int a = arity();
	if (a > 0) {
		int i; char sep;
		for (sep = '[', i = 0; i < a; sep = ',', i++) {
			fout << sep; branch(i)->print(fout); 
		}
		fout << ']';
	} 
	
	return fout;
}


void CTree::control ()
{
	printf("\ngHashTable Content :\n\n");
	for (int i = 0; i < kHashTableSize; i++) {
		Tree t = gHashTable[i];
		if (t) {
			printf ("%4d = ", i);
			while (t) {
				/*t->print();*/
				printf(" => ");
				t = t->fNext;
			}
			printf("VOID\n");
		}
	}
	printf("\nEnd gHashTable\n");

}

// if t has a node of type int, return it otherwise error
int tree2int (Tree t)
{
	double	x;
	int		i;

	if (isInt(t->node(), &i)) {
		// nothing to do
	} else if (isDouble(t->node(), &x)) {
		i = int(x);
	} else {
		ERROR("the node of the tree is not an int nor a float", t);
	}
	return i;
}	
    
// if t has a node of type float, return it otherwise error
double tree2float (Tree t)
{
    double   x;
    int     i;

    if (isInt(t->node(), &i)) {
        x = double(i);
    } else if (isDouble(t->node(), &x)) {
        //nothing to do
    } else {
        ERROR("the node of the tree is not a float nor an int", t);
    }
    return x;
}   
    
// if t has a node of type float, return it as a double otherwise error
double tree2double (Tree t)
{
    double   x;
    int     i;

    if (isInt(t->node(), &i)) {
        x = double(i);
    } else if (isDouble(t->node(), &x)) {
        //nothing to do
    } else {
        ERROR("the node of the tree is not a float nor an int", t);
    }
    return double(x);
}   
	
// if t has a node of type symbol, return its name otherwise error		
const char* tree2str (Tree t)
{
	Sym s;
	if (!isSym(t->node(), &s)) {
		ERROR("the node of the tree is not a symbol", t);
	}
	return name(s);
}	

// if t has a node of type ptr, return it otherwise error			
void* tree2ptr (Tree t)
{
	void*	x;
	if (! isPointer(t->node(), &x)) {
		ERROR("the node of the tree is not a pointer", t);
	}
	return x;
}	
			
/*
bool isTree (const Tree& t, const Node& n) 
{ 
	return (t->node() == n) && (t->arity() == 0);
}
*/

// Si ca ne pose pas de probl�es, c'est plus pratique	
bool isTree (const Tree& t, const Node& n) 
{ 
	return (t->node() == n);
}

bool isTree (const Tree& t, const Node& n, Tree& a) 
{ 
	if ((t->node() == n) && (t->arity() == 1)) { 
		a=t->branch(0); 
		return true; 
	} else {
		return false;
	}
}

bool isTree (const Tree& t, const Node& n, Tree& a, Tree& b)
{ 
	if ((t->node() == n) && (t->arity() == 2)) { 
		a=t->branch(0); 
		b=t->branch(1); 
		return true; 
	} else {
		return false;
	}
}

bool isTree (const Tree& t, const Node& n, Tree& a, Tree& b, Tree& c) 
{ 
	if ((t->node() == n) && (t->arity() == 3)) { 
		a=t->branch(0); 
		b=t->branch(1); 
		c=t->branch(2); 
		return true; 
	} else {
		return false;
	}
}

bool isTree (const Tree& t, const Node& n, Tree& a, Tree& b, Tree& c, Tree& d)  
{ 
	if ((t->node() == n) && (t->arity() == 4)) { 
		a=t->branch(0); 
		b=t->branch(1); 
		c=t->branch(2); 
		d=t->branch(3); 
		return true; 
	} else {
		return false;
	}
}

bool isTree (const Tree& t, const Node& n, Tree& a, Tree& b, Tree& c, Tree& d, Tree& e)  
{ 
	if ((t->node() == n) && (t->arity() == 5)) { 
		a=t->branch(0); 
		b=t->branch(1); 
		c=t->branch(2); 
		d=t->branch(3); 
		e=t->branch(4); 
		return true; 
	} else {
		return false;
	}
}

// July 2005, support for symbol user data

void* getUserData(Tree t)
{
	Sym s;
	if (isSym(t->node(), &s)) {
		return getUserData(s);
	} else {
		return 0;
	}
}


/**
 * export the properties of a CTree as two vectors, one for the keys
 * and one for the associated values
 */

void CTree::exportProperties(vector<Tree>& keys, vector<Tree>& values)
{
    for (plist::const_iterator p = fProperties.begin(); p != fProperties.end(); p++) {
        keys.push_back(p->first);
        values.push_back(p->second);
    }
}