<?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;
    }
  }

  // Rewind result so it can be used again.
  if (is_object($nodes)) {
    $nodes->data_seek(0);
  }

  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) {
  if (is_array($tree) && $tree != NULL) {
    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) {
  if (is_array($tree) && $tree != NULL) {
    foreach ($tree as &$term) {
      taxonomy_node_tree_sort($tree, $term);
    }
  }
  return $tree;
}

/**
 * Count descendant nodes.
 *
 * @param $term
 *   Term object.
 *
 * @param $count
 *   Optional initial count offset. Also used for recursion.
 *
 * @return
 *   Number of descendant nodes.
 */
function taxonomy_node_tree_count($term, &$count = 0) {
  if (isset($term->below)) {
    foreach ($term->below as &$below) {
      taxonomy_node_tree_count($below, $count);
    }
  }

  if (isset($term->nodes)) {
    $count += count($term->nodes);
  }

  return $count;
}

/**
 * Build a list of empty terms.
 *
 * @param $term
 *   Term object.
 *
 * @param $clean
 *   Set to true to cleanup term before adding to list.
 *
 * @param $list
 *   Array to store term list.
 *
 * @return
 *   Array with terms without descendant nodes.
 *
 * @todo
 *   Skip parents should be controlled by a parameter.
 */
function taxonomy_node_tree_get_empty($term, $clean = FALSE, &$list = array()) {
  if (taxonomy_node_tree_count($term) == 0) {
    // Skip parents.
    if ($term->parents[0] != 0) {
      $save = drupal_clone($term);

      if ($clean == TRUE) {
        unset($save->nodes);
        unset($save->below);
        unset($save->children);
      }

      $list[] = $save;
    }
  }
  else if (isset($term->below)) {
    foreach ($term->below as $below) {
      taxonomy_node_tree_get_empty($below, $clean, $list);
    }
  }

  return $list;
}

/**
 * Build a list of no-nempty terms.
 *
 * @param $term
 *   Term object.
 *
 * @param $clean
 *   Set to true to cleanup term before adding to list.
 *
 * @param $list
 *   Array to store term list.
 *
 * @return
 *   Array with terms with descendant nodes.
 *
 * @todo
 *   Skip parents should be controlled by a parameter.
 */
function taxonomy_node_tree_get_non_empty($term, $clean = FALSE, &$list = array()) {
  // Add parents and terms with descendant nodes.
  if ($term->parents[0] == 0 || taxonomy_node_tree_count($term) > 0) {
    $save = drupal_clone($term);

    if ($clean == TRUE) {
      unset($save->nodes);
      unset($save->below);
      unset($save->children);
    }

    $list[] = $save;
  }

  if (is_array($term->below)) {
    foreach ($term->below as $below) {
      taxonomy_node_tree_get_non_empty($below, $clean, $list);
    }
  }

  return $list;
}

/**
 * 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.
 *
 * @param $clean
 *   Set to TRUE to remove branches without descendant nodes.
 *
 * @return
 *  Hierarchical tree.
 */
function taxonomy_node_tree_build($nodes, $terms, $clean = FALSE) {
  $tree = taxonomy_node_tree_index($nodes, $terms);
  $tree = taxonomy_node_tree_relation($tree);
  $tree = taxonomy_node_tree_hierarchy($tree);

  if ($clean == TRUE && is_array($tree)) {
    $terms = array();
    foreach ($tree as $term) {
      $list  = taxonomy_node_tree_get_non_empty($term, TRUE);
      $terms = array_merge($terms, $list);
    }

    $tree = taxonomy_node_tree_build($nodes, $terms, FALSE);
  }

  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.
 */
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;
}

/**
 * Implementation of hook_theme().
 */
function taxonomy_node_tree_theme() {
  return array(
      'taxonomy_node_tree_list' => array(
        'arguments'             => array(
          'term'                => NULL,
          'id'                  => NULL,
          'class'               => NULL,
          'baselink'            => NULL,
          'level'               => NULL,
          ),
        'function'              => 'theme_taxonomy_node_tree_list',
        ),
      );
}

/**
 * Recursively build an HTML taxonomy node tree.
 *
 * @ingroup themeable
 *
 * @param $term
 *   Current of starting term.
 *
 * @param $id
 *   Base id for list elements.
 *
 * @param $class
 *   Class for list elements.
 *
 * @param $baselink
 *   Base link for urls.
 *
 * @param $level
 *   Nesting level user for recursion.
 *
 * @return
 *   Rendered HTML tree.
 */
function theme_taxonomy_node_tree_list($term, $id, $class, $baselink = NULL, &$level = NULL) {

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

  $level++;

  if (isset($term->tid)) {
    $output  = '<li>';

    if (isset($term->below)) {
      $output .= $term->name;
      $output .= '<ul id="' . $id .'-ul-'. $level .'" class="'. $class .'">';
      foreach ($term->below as $child) {
        $output .= theme_taxonomy_node_tree_list($child, $id, $class, $baselink, $level);
      }
      $output .= '</ul>';
    }
    elseif (isset($term->nodes)) {
      $output .= $term->name;
      $output .= '<ul id="' . $id .'-ul-'. $level .'" class="'. $class .'">';
      foreach ($term->nodes as $node) {
        $output .= '<li>';
        $output .= l($node->title, "$baselink/$node->nid");
        $output .= '</li>';
      }
      $output .= '</ul>';
    }
    else {
      $output .= '<span>'. $term->name .'</span>';
    }

    $output .= '</li>';
  }

  return $output;
}

/**
 * Build an array with a node and it's parent terms.
 *
 * @param $parents
 *   Direct or all parent terms.
 *
 * @return
 *   Array with node and parent terms.
 */
function taxonomy_node_tree_trail($nid, $tid, $parents = 'direct') {
  $trail = array();

  // Add term hierarchy
  if ($parents == 'direct') {
    $function = 'taxonomy_get_parents';
  }
  else {
    $function = 'taxonomy_get_parents_all';
  }

  // Build array
  foreach (array_reverse($function($tid)) as $term) {
    $trail[] = $term->name;
  }

  // Add node title
  $node    = node_load($nid);
  $trail[] = $node->title;

  return $trail;
}