/*
  ** package de structure de données
  ** nice le 21/08/2002
  ** auteur:ibowili henri
  */
  
  //structures permettant de rendre plus générique le code avec les arbres
  
  function Atom(val){
    this.property=val
  }
  function AtomXY(id,x,y){
    this.property=id
	this.x=x
	this.y=y
  }
  
// structure de base pour la construction est les opérations sur les arbres
/*remarque importante:
**la propriété value prend un objet qui doit avoir une propriété property,
**afin qu'une valeur puisse être retournée si necessaire
*/
function Node(val){
 this.value=val
 this.liberty=0
 this.child=null
 this.brother=null
 this.test=null
 this.equals=equals
 this.isEmpty=isEmpty
 this.getValue=getValue
 this.getChild=getChild
 this.getAllChilds=getAllChilds
 this.getBrother=getBrother
 this.getAllBrothers=getAllBrothers
 this.setValue=setValue
 this.setChild=setChild
 this.setBrother=setBrother
 this.setLiberty=setLiberty
 this.skimDepth=skimDepth
 this.getNumberOfBrother=getNumberOfBrother
 this.getNumberOfChild=getNumberOfChild
}
function equals(n){
  var result;
  this.test=1;
  result=n.test==1;
  this.test=null;
  return result;
}
function isEmpty(n){

}
function getValue(){
  return this.value.property;
}
function getChild(){
  return this.child;
}
function getBrother(){
 return this.brother;
}
function setValue(v){
 this.value=v;
}
function setChild(n){
 var inter=this.child;
 var last=this.child;
 if(inter!=null){
  inter=inter.getBrother();
  while(inter!=null){
    last=inter;
    inter=inter.getBrother();
  }
  last.brother=n;
 }
 else this.child=n;
}
function setBrother(n){
 var inter=this.brother;
 if(inter!=null){
   var last=inter;
   while(inter!=null){
    last=inter;
    inter=inter.brother;
   }
   last.brother=n;
 }
 else this.brother=n;
}
function getNumberOfBrother(){
 var inter=this;
 var count=0;
 while((inter=inter.getBrother())!=null){
   count++;
  }
  return count;
}
function getNumberOfChild(){
 var inter=this.getChild();
 var count=0;
 if(inter!=null)
  count=inter.getNumberOfBrother()+1;
  return count;
}

function setLiberty(val){
 this.liberty=val;
}
function getAllChilds(){
  var family=new Stack(null);
  var inter=this.getChild();
  if(inter!=null){
    do{
	  family.push(inter);
	  inter=inter.getBrother();
	}while(inter!=null);
   }
   return family;
}
function getAllBrothers(){
}
function skimDepth(out){
  var fin=false;
  var way=new Stack(this);
  var reserve=new Stack(null);
  var inter=null;
  while(!way.isEmpty() && !reserve.isEmpty()){
    way.top.liberty=way.top.getNumberOfChild();
	if(way.top.liberty>0){
	   reserve=newWay(reserve,way.top.getAllChilds());
	}
	else{
	  while(!fin && way.top.liberty==0){
	     inter=way.pop();
	    if(way.top==null)fin=true;
	   }
	  }
	 if(!fin){
	   way.top.liberty--;
	   way.push(reserve.pop());
	   if(way.top.getValue()==out)return way;
	  }
	 else break;
   }
   return null;
}
function newWay(way,insert){
   insert.bottom.next=way.top;
   insert.bottom=way.bottom;
   return insert;
}
function afficheChemin(way){
  var inter=way;
  var result="";
  while(inter.top!=null){
   alert(inter.top.getValue());
   result+=inter.top.getValue();
   inter.pop();
   }
   alert(result); 
}