<?php
// $Id$

/**
 * @file
 * Taxonomy Node Tree.
 *
 * This module implements functions to build hierarchical
 * term trees including children nodes.
 */

/**
 * Return the parent terms of a given vocabulary.
 *
 * This function takes a vocabulary id and returns a
 * list of it's parent terms.
 */
function taxonomy_node_tree_parents($vid) {
  // Get all terms from a given vocabulary
  $terms = taxonomy_node_tree_taxonomy_get_tree($vid);

  foreach ($terms as $term) {
    // Just show parent terms
    if (taxonomy_get_parents($term->tid) == array()) {
      $menu[] = $term;
    }
  }

  return $menu;
}

/**
 * Setup an index of terms associated with it's children nodes.
 *
 * This function accept a list of nodes and terms and build a
 * tree with the corresponding association between terms and
 * nodes.
 *
 * @TODO: It is assumed that nodes are just associated with
 *        a single term.
 */
function taxonomy_node_tree_index($nodes, $terms) {  
  while ($node = db_fetch_object($nodes)) {
    foreach ($terms as $term) {
      // add nodes into the term
      if ($node->tid == $term->tid) {
        $term->nodes[] = $node;
      }
      // update an index of terms
      $tree[$term->tid] = $term;
    }
  }
  return $tree;
}

/**
 * Add children relationship for terms present in the tree.
 */
function taxonomy_node_tree_relation($tree) {
  foreach ($tree as $term) {
    if ($term->parents[0] != 0 && isset($tree[$term->parents[0]])) {
      $tree[$term->parents[0]]->children[] = $term->tid;
    }
  }
  return $tree;
}

/**
 * Sort terms in the tree.
 *
 * This function add terms on it's right place in the taxonomy tree.
 */
function taxonomy_node_tree_sort(&$tree, $term) {
  if ($term->parents[0] != 0 && isset($tree[$term->parents[0]])) {
    // is child
    if (isset($term->children)) {
      // is also parent, so go down one level
      foreach ($term->children as $child) {
        taxonomy_node_tree_sort($tree, $tree[$child]);
      }
    }
    $tree[$term->parents[0]]->below[] = drupal_clone($term);
    unset($tree[$term->tid]);
  }
}

/**
 * Sort a taxonomy tree to the right hierarchy.
 */
function taxonomy_node_tree_hierarchy($tree) {
  foreach ($tree as $term) {
    taxonomy_node_tree_sort($tree, $term);
  }
  return $tree;
}

function taxonomy_node_tree_build($nodes, $terms) {
  $tree = taxonomy_node_tree_index($nodes, $terms);
  $tree = taxonomy_node_tree_relation($tree);
  $tree = taxonomy_node_tree_hierarchy($tree);
  return $tree;
}

/**
 * Version of taxonomy_get_tree() without caching.
 */
function taxonomy_node_tree_taxonomy_get_tree($vid, $parent = 0, $depth = -1, $max_depth = NULL, $cache = FALSE) {
  static $children, $parents, $terms;

  $depth++;

  // We can cache trees, so it's not CPU-intensive to call get_tree() on a term
  // and its children, too.
  if (!$cache && !isset($children[$vid])) {
    $children[$vid] = array();

    $result = db_query(db_rewrite_sql('SELECT t.tid, t.*, parent FROM {term_data} t INNER JOIN {term_hierarchy} h ON t.tid = h.tid WHERE t.vid = %d ORDER BY weight, name', 't', 'tid'), $vid);
    while ($term = db_fetch_object($result)) {
      $children[$vid][$term->parent][] = $term->tid;
      $parents[$vid][$term->tid][] = $term->parent;
      $terms[$vid][$term->tid] = $term;
    }
  }

  $max_depth = (is_null($max_depth)) ? count($children[$vid]) : $max_depth;
  $tree = array();
  if ($max_depth > $depth && !empty($children[$vid][$parent])) {
    foreach ($children[$vid][$parent] as $child) {
      $term = drupal_clone($terms[$vid][$child]);
      $term->depth = $depth;
      // The "parent" attribute is not useful, as it would show one parent only.
      unset($term->parent);
      $term->parents = $parents[$vid][$child];
      $tree[] = $term;
      if (!empty($children[$vid][$child])) {
        $tree = array_merge($tree, taxonomy_get_tree($vid, $child, $depth, $max_depth));
      }
    }
  }

  return $tree;

}