<?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.
 *
 * @param $vid
 *   Taxonomy id.
 *
 * @return
 *   Array with parent terms of the vocabulary.
 */
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.
 *
 * @param $nodes
 *   Array with node objects.
 *    
 * @param $terms 
 *   Array with term objects.
 *
 * @return
 *  Term tree with nodes at their parent terms.
 *
 * @TODO: It is assumed that nodes are just associated with
 *        a single term. This could be changed to support
 *        multiple relationships.
 */
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.
 *
 * @param
 *   Tree with term objects.
 *
 * @return
 *   Term tree with parent/children relation.
 */
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.
 *
 * @param $tree
 *   Tree with term objects to be changed (by reference).
 *
 * @param $term
 *   Term object.
 */
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.
 *
 * @param $tree
 *   Tree with term objects.
 *
 * @return
 *   Hierarchical term tree.
 */
function taxonomy_node_tree_hierarchy($tree) {
  foreach ($tree as $term) {
    taxonomy_node_tree_sort($tree, $term);
  }
  return $tree;
}

/**
 * Setup a full taxonomy node hierarchical tree.
 *
 * Build a tree with taxonomy terms with full dept
 * and add child node information at each level.
 *
 * @param $nodes
 *   Array with node objects.
 *
 * @param $terms
 *   Array with term objects.
 *
 * @return
 *  Hierarchical 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;
}

/**
 * Create a hierarchical representation of a vocabulary.
 *
 * Version of taxonomy_get_tree() without caching.
 *
 * @param $vid
 *   Which vocabulary to generate the tree for.
 *
 * @param $parent
 *   The term ID under which to generate the tree. If 0, generate the tree
 *   for the entire vocabulary.
 *
 * @param $depth
 *   Internal use only.
 *
 * @param $max_depth
 *   The number of levels of the tree to return. Leave NULL to return all levels.
 *
 * @param $cache
 *   Whether to use cache results.
 *
 * @return
 *   An array of all term objects in the tree. Each term object is extended
 *   to have "depth" and "parents" attributes in addition to its normal ones.
 *   Results are statically cached.
 */ 
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;

}

/**
 * Recursively build an HTML taxonomy node tree.
 *
 * @ingroup themeable
 * @TODO: usage with hook_theme();
 */
function taxonomy_node_tree_list($term, $id, $class, $baselink = NULL, &$level = NULL) {

  if ($level == NULL) {
    $level = 0;
  }

  $level++;

  if (isset($term->tid)) {
    $output .= '<li>';
    $output .= $term->name;
    if (isset($term->below)) {
      $output .= '<ul id="' . $id .'[ul]["'. $level .']" class="'. $class .'">';
      foreach ($term->below as $child) {
        $output .= taxonomy_node_tree_list($child, $id, $class, $baselink, $level);
      }
      $output .= '</ul>';
    }
    else if (isset($term->nodes)) {
      $output .= '<ul id="' . $id .'[ul]["'. $level .']" class="'. $class .'">';
      foreach ($term->nodes as $node) {
        $output .= '<li>';
        $output .= '<a href="'. $GLOBALS['base_url'] .'/'. $baselink .'/'. $node->nid .'">'. $node->title .'</a>';
      }
      $output .= '</ul>';
      $output .= '</li>';
    }
    $output .= '</li>';
  }

  return $output;

}