/*
 * Tree structure width dynamic child generation
 * 2009
 * Henri Bourcereau henri.bourcereau@gmail.com
 */

var jQuery, $, asyncWhile, echo;
/*jslint
 browser:true
*/

function TreeNode() {
  var parent = null;
  var leftchild = null;
  var rightbrother = null;
  var childs_computed = false;

  //Pour fonctions asynchrones
  this.subcourse_found = [];
}

TreeNode.prototype.addNode = function (node, pos) { 
  //On interdit le déplacement d'un noeud dans sa sous-arborescence (boucle infinie)
  if (jQuery.inArray(node, this.ancestors()) > -1) {
    throw new Error("Impossible move");
  }

  if (!this.leftchild){
    this.leftchild = node;
    node.parent = this;
  }
  else if (typeof pos == 'undefined' )  {
    var rightchild = this.get_rightchild();
    rightchild.rightbrother = node;
    node.parent = this;
  }
  else if (pos === 0) {
    node.rightbrother = this.leftchild;
    this.leftchild = node;
    node.parent = this;
  }
  else {
    var curnode = this.leftchild;
    var curpos = 0;
    while (curpos < (pos-1) && curnode.rightbrother ) {
      curnode = curnode.rightbrother;
      curpos = curpos + 1;
    }
    node.rightbrother = curnode.rightbrother;
    node.parent = this;
    curnode.rightbrother = node;
  }
};

TreeNode.prototype.get_rightchild = function() {
  var child = null;
  if (this.leftchild) {
    child = this.leftchild;
    var nextchild = child.rightbrother;
    while (nextchild ) {
      child = nextchild;
      nextchild = child.rightbrother;
    }
  }
  return child;
};

TreeNode.prototype.childs = function() {
  var tabChilds = Array();
  var node = this.leftchild;
  while (node){
    tabChilds.push(node);
    node = node.rightbrother;
  }
  return tabChilds;
};

TreeNode.prototype.ancestors = function() {
  var tabAncestors = Array();
  var node = this.parent;
  while (node) {
    tabAncestors.push(node);
    node = node.parent;
  }
  return tabAncestors;
};



//Add a node to the node of path path
TreeNode.prototype.insert_node = function (path, node){
  var parentNode = this.getNode(path);
  parentNode.addNode(node);
};

TreeNode.prototype.move_to = function (new_parent, pos){
  //On interdit le déplacement d'un noeud dans sa sous-arborescence (boucle infinie)
  if (jQuery.inArray(this, new_parent.ancestors()) > -1) {
    throw new Error("Impossible move");
  }
  this.detach();
  new_parent.addNode(this, pos);
};

TreeNode.prototype.move_node = function(pathIni, pathFin){
  //On interdit le déplacement d'un noeud dans sa sous-arborescence (boucle infinie)
  if (pathFin.index(pathIni)===0){
    throw new Error("Impossible move");
  }

  //Noeud à déplacer
  var node = this.getNode(pathIni);
  //Noeud de destination
  var newParentNode = this.getNode(pathFin);

  //On détache le noeud de son emplacement actuel
  node.detach();

  //On ajoute le noeud à son nouveau père
  newParentNode.addNode(node);
};

TreeNode.prototype.remove = function(path){
  var node = this.getNode(path);
  node.detach();
  node = null;
};

TreeNode.prototype.getNode = function(pathNode){
  var currentNode = this;
  var path = pathNode.split(':');
  jQuery.each(path, function(index, nodePos) { 
      currentNode = currentNode.leftchild;
      for (var i=0;i< nodePos;i++){
      currentNode = currentNode.rightbrother;
      }
      });
  return currentNode;
};

TreeNode.prototype.root = function() {
  var node = this;
  while (node.parent){
    node = node.parent;
  }
  return node;
};

  TreeNode.prototype.path = function() {
    var tabPath = Array();
    var node = this;
    while (node.parent) {
      tabPath.push(node.pos());
      node = node.parent;
    }
    return tabPath.reverse().join(":");
  };

TreeNode.prototype.pos = function() {
  var position = 0;
  var brother = this.parent.leftchild;
  while (brother!= this){
    brother = brother.rightbrother;
    position = position + 1;
  }
  return position;
};

TreeNode.prototype.detach = function() {
  //On détache le noeud de son emplacement actuel
  if (this.parent.leftchild == this){
    this.parent.leftchild = this.rightbrother;
  }
  else {
    var leftbrother = this.parent.leftchild;
    while (leftbrother.rightbrother != this){
      leftbrother = leftbrother.rightbrother;
    }
    leftbrother.rightbrother = this.rightbrother;
  }
  this.rightbrother = null;
};

// Génération dynamique des fils
TreeNode.prototype.compute_childs = function(computer) {
  if (! this.childs_computed ) {
    var computedchilds = computer(this);
    var node_actuel = this;
    jQuery.each(computedchilds, function(){
        node_actuel.addNode(this);
        });
    this.childs_computed = true;
  }
};

// Recherche d'une suite de noeuds (= extration d'un parcours)
TreeNode.prototype.findcourse = function (property, depth, computer){
  if (typeof depth == 'undefined' ){ depth = -1;}
  var course_found = Array();
  if (property(this)){
    if (depth > 1 ){
      if (typeof(computer) != 'undefined') {
        this.compute_childs(computer); 
      }
      this.current_child = this.leftchild;
      this.subcourse_found = [];
      while (this.subcourse_found.length === 0 && this.current_child ){
        this.subcourse_found = this.current_child.findcourse(property, depth -1, computer);
        this.current_child = this.current_child.rightbrother;
      }
      this.course_found = this.subcourse_found;
    }
    course_found.unshift(this);
  }
  return (course_found.length == depth) ? course_found : Array();
};

/**********************************************************
 * Méthodes asynchrones pour permettre l'utilisation d'AJAX
 * dans le calcul des enfants
 * ********************************************************/
TreeNode.prototype.compute_childsAsync = function(computer, callback) {
  if (this.childs_computed ) {
    callback();//XXX 1 this? 
  }
  else {
    var node_actuel = this;
    computer(this, function(computedchilds){
      jQuery.each(computedchilds, function(){
        node_actuel.addNode(this);
      });
      node_actuel.childs_computed = true;
      callback.call(this);
    });
  }
};
var treenodes;
// Recherche d'une suite de noeuds (= extration d'un parcours)
TreeNode.prototype.findcourseAsync = function (property, depth, computer, callback, treenodes){
  if (typeof treenodes == 'undefined' ){ treenodes = Array();}
//  var thisnode = this;
  if (typeof depth == 'undefined' ) { depth = -1;}
  this.course_found = [];
  if (!property(this)){
    callback.call(treenodes[treenodes.length -1], []);//XXX 4 this?
  }
  else{
    if (depth < 1 ){
      this.course_found.unshift(this);
      callback.call(treenodes[treenodes.length -1],(this.course_found.length == depth) ? this.course_found : []);//XXX 5
    }
    else {
      if (typeof(computer) != 'undefined') {
        treenodes.push(this);
        
        var after_compute_childs =  function(){
          this.current_child = treenodes[treenodes.length -1].leftchild;
          //            current_child = this.leftchild;
          //            var current_child = thisnode.leftchild;
          this.subcourse_found = [];

          var testWhile = function(){ 
            var ok = (this.subcourse_found.length === 0) && (this.current_child !== undefined);
            return  ok;
          };
          var traitementWhile = function(whilecallback){
            this.current_child.findcourseAsync(
              property,
              depth -1,
              computer,
              function(subcourse_found){
                this.subcourse_found = subcourse_found;
                this.current_child = this.current_child.rightbrother;
                whilecallback.call(treenodes[treenodes.length -1]);//XXX 2 this ?
              },
              treenodes);
          };
          var finWhile = function(){ 
            this.course_found = this.subcourse_found;
            //On remonte d'un niveau
            this.current_child = treenodes.pop();
            //                current_child = thisnode.parent;
            this.course_found.unshift(this.current_child);
            callback.call(treenodes[treenodes.length -1], (this.course_found.length == depth) ? this.course_found :[]);//XXX 3 this ?
          };
          asyncWhile(treenodes[treenodes.length -1], testWhile, traitementWhile, finWhile);
        };

       /* (function(){
            var after_compute_childsOld = after_compute_childs;
            after_compute_childs = function(){
              var result = after_compute_childsOld.apply(this, arguments);
              return result;
            };
          })();
          */


        this.compute_childsAsync( computer, after_compute_childs);//fin compute_childAsync
      }
    }
  }
};

/******************************************************
 * EXEMPLES 
 * ****************************************************/

/*
// quick-n-dirty logger
echo = function(msg) {
    var m = document.createElement('DIV');
    m.innerHTML = msg;
    document.body.appendChild( m );
  }; 

function TreeTexte(texte){
  this.superclass = TreeNode;
  this.superclass();
  this.texte = texte;
}

TreeTexte.prototype = new TreeNode();
  
TreeTexte.prototype.addNode = function (node, pos) { 
  echo('Adding ' + node.texte + ' to ' + this.texte);
  TreeNode.prototype.addNode.call(this, node, pos);
};

TreeTexte.prototype.print = function (level){
  if (typeof level == 'undefined' ){ level = 0;}
  var str = "";
  for(var i=0;i<level;i++){str = str + "-";}
  str += this.texte;
  var tabChilds = this.childs();
  jQuery.each(tabChilds, function() {
      str = str + "<br>" + this.print(level+1);
  });
  return str;
};


$(document).ready(function(){
    var arbre = new TreeTexte('racine');
    /*fils1 = new TreeTexte('fils1');
    fils2 = new TreeTexte('fils2a');
    fifils = new TreeTexte('fifils');
    fifils2 = new TreeTexte('fifils2');
    arbre.addNode(fils1);
    arbre.addNode(fils2);
    fils1.addNode(fifils);
    fils1.addNode(fifils2);

    computer = function(node){
      var compchilds = new Array();
      for (var i = 2; i< 5; i++){
       compchilds.push(new TreeTexte(node.texte + "_" + i));
      }
      return compchilds;
    }

    //Exemple génération dynamique
    echo("<h1>Exemple génération dynamique</h1>");


    fils2.compute_childs(computer); 
    fifils2.compute_childs(computer);

    echo(arbre.print());

    //Exemple extraction de chemin
    echo("<h1>Exemple extraction de chemin</h1>");
    has2 = function(node)  { return node.texte.match(/a/); }

    strCourse = "";
    jQuery.each(arbre.findcourse(has2, 4, computer), function() {
        strCourse += this.texte + "::" 
        });
    echo(strCourse);
*/
    //Exemple extraction de chemin asynchrone
 /*   echo("<h1>Exemple extraction de chemin asynchrone</h1>");
      
    var computerAsync = function(node, callback){
      var compchilds = [];
      for (var i = 2; i< 5; i++){
       compchilds.push(new TreeTexte(node.texte + "_" + i));
      }
      callback.call(node, compchilds);
    };

    var has2 = function(node)  { return node.texte.match(/a/); };

    var strCourse = "";
    arbre.findcourseAsync.call(arbre, has2, 4, computerAsync, function(nodes){
      jQuery.each(nodes, function() {
          strCourse += this.texte + "::" ;
      });
      echo(strCourse);
    });
});
//*/