<?php
// $Id: hierarchical_select.module,v 1.40 2008-03-03 16:44:26 wimleers Exp $

/**
 * @file
 * This module defines the "hierarchical_select" form element, which is a
 * greatly enhanced way for letting the user select an option in a hierarchy.
 */


// Enable default support for some modules, if they are enabled.
$modules = array('taxonomy', 'content_taxonomy', 'subscriptions_taxonomy');
foreach ($modules as $module) {
  if (module_exists($module)) {
    require_once drupal_get_path('module', 'hierarchical_select') ."/modules/$module.inc";
  }
}

//----------------------------------------------------------------------------
// Drupal core hooks.

/**
 * Implementation of hook_menu().
 */
function hierarchical_select_menu($may_cache) {
  if (!$maycache) {
    $items[] = array(
      'path' => 'hierarchical_select_json',
      'callback' => 'hierarchical_select_json',
      'type' => MENU_CALLBACK,
      // TODO: Needs improvements. Ideally, this would inherit the permissions
      // of the form the Hierarchical Select was in.
      'access' => user_access('access content'),
    );
    $items[] = array(
      'path' => 'admin/settings/hierarchical_select',
      'title' => t('Hierarchical Select'),
      'description' => t('Configure site-wide settings for the Hierarchical Select form element.'),
      'callback' => 'drupal_get_form',
      'callback arguments' => array('hierarchical_select_admin_settings'),
      'type' => MENU_NORMAL_ITEM,
    );
  }
  return $items;
}

/**
 * Implementation of hook_form_alter().
 */
function hierarchical_select_form_alter($form_id, &$form) {
  foreach (module_implements('hierarchical_select_form_alter') as $module) {
    $function = $module .'_hierarchical_select_form_alter';
    $function($form_id, $form);
  }
}

/**
 * Implementation of hook_elements().
 */
function hierarchical_select_elements() {
  $type['hierarchical_select'] = array(
    '#input' => TRUE, 
    '#process' => array('hierarchical_select_process' => array()),
    '#hierarchical_select_settings' => array(
      'save_lineage' => FALSE,
      'enforce_deepest' => FALSE,
      'all_option' => FALSE,
      'level_labels' => array(),
      'params' => array(),
      'animation_delay' => variable_get('hierarchical_select_animation_delay', 400),
      'dropbox_title' => t('All selections'),
      'dropbox_limit' => 0,
    ),
    '#default_value' => -1,
  );
  return $type;
}


//----------------------------------------------------------------------------
// Menu callbacks.

/**
 * Menu callback; JSON callback: generates and outputs the appropriate HTML.
 */
function hierarchical_select_json() {
  // We are returning JavaScript, so tell the browser. Ripped from Drupal 6's
  // drupal_json() function.
  drupal_set_header('Content-Type: text/javascript; charset=utf-8');

  // Extract the common parameters.
  $hsid              = $_POST['hsid'];
  $module            = $_POST['module'];
  $selection         = (!strstr($_POST['selection'], '|')) ? $_POST['selection'] : explode('|', $_POST['selection']);
  $dropbox_selection = (!strstr($_POST['dropbox_selection'], '|')) ? $_POST['dropbox_selection'] : explode('|', $_POST['dropbox_selection']);
  $save_lineage      = _hierarchical_select_str_to_bool($_POST['save_lineage']);
  $enforce_deepest   = _hierarchical_select_str_to_bool($_POST['enforce_deepest']);
  $all_option        = _hierarchical_select_str_to_bool($_POST['all_option']);
  $level_labels      = explode('|', $_POST['level_labels']);
  $params            = unserialize($_POST['params']);
  $dropbox_title     = $_POST['dropbox_title'];
  $required          = _hierarchical_select_str_to_bool($_POST['required']);

  switch ($_POST['type']) {
    case 'hierarchical-select':
      $hierarchy = hierarchical_select_get_hierarchy(
        $module,
        $selection,
        $save_lineage, 
        $enforce_deepest,
        $all_option,
        $level_labels,
        $params,
        $required,
        FALSE // No dropbox when only updating the hierarchical select!
      );   
      $hierarchical_select_html = theme('hierarchical_select_render_selects', $hsid, $hierarchy);

      // Return output as JSON.
      print drupal_to_js(array(
        'hierarchicalSelect' => $hierarchical_select_html,
      ));
      break;

    case 'dropbox-add':
      // We want to render an empty select.
      $selection = -1;
    case 'dropbox-remove':
    default:
      $dropbox = hierarchical_select_get_dropbox(
        $module,
        $dropbox_selection,
        $save_lineage,
        $level_labels,
        $params,
        $dropbox_title
      );
      $dropbox_html = theme('hierarchical_select_render_dropbox', $hsid, $dropbox);

      $hierarchy = hierarchical_select_get_hierarchy(
        $module,
        $selection,
        $save_lineage, 
        $enforce_deepest,
        $all_option,
        $level_labels,
        $params,
        $required,
        $dropbox
      );   
      $hierarchical_select_html = theme('hierarchical_select_render_selects', $hsid, $hierarchy);

      // Return output as JSON.
      print drupal_to_js(array(
        'hierarchicalSelect' => $hierarchical_select_html,
        'dropbox' => $dropbox_html,
        'dropboxLineagesSelections' => $dropbox->lineages_selections
      ));
      break;
  }

  exit;
}


//----------------------------------------------------------------------------
// Forms API callbacks.

/**
 * Hierarchical select form element processing function.
 */
function hierarchical_select_process($element) {
  static $hsid;

  // Render a hierarchical select as a normal select, it's the JavaScript that
  // will turn it into a hierarchical select.
  $element['#type'] = 'select';

  if (!isset($hsid)) {
    $hsid = 0;

    $url = base_path();
    $url .= variable_get('clean_url', 0) ? '' : 'index.php?q=';
    $url .= 'hierarchical_select_json';

    // Add the CSS and JS, set the URL that should be used by all hierarchical
    // selects.
    drupal_add_css(drupal_get_path('module', 'hierarchical_select') .'/hierarchical_select.css');
    jquery_interface_add();
    drupal_add_js(drupal_get_path('module', 'hierarchical_select') .'/hierarchical_select.js');
    drupal_add_js(array('hierarchical_select' => array('url' => $url)), 'setting');
  }
  else {
    $hsid++;
  }

  extract(_hierarchical_select_extract_settings($element));

  // If the form item is not required, then we must ensure we have a "<none>"
  // option in the original select. If one exists already, we overwrite it: we
  // want exactly the same text here as in the hierarchical select.
  if (!$required) {
    $element['#options'] = array('' => '<'. t('none') .'>') + $element['#options'];
  }
  
  // Render the initial HTML.
  $dropbox = (!$multiple) ? FALSE : hierarchical_select_get_dropbox($module, $selection, $save_lineage, $level_labels, $params, $dropbox_title);
  $hierarchy = hierarchical_select_get_hierarchy($module, ($multiple) ? -1 : $selection, $save_lineage, $enforce_deepest, $all_option, $level_labels, $params, $required, $dropbox);
  $initial = theme('hierarchical_select_render_initial_html', $hsid, $hierarchy, $dropbox);

  drupal_add_js(
    array(
      'hierarchical_select' => array(
        'settings' => array(
          $hsid => array(
            'animationDelay' => ($animation_delay == 0) ? variable_get('hierarchical_select_animation_delay', 400) : $animation_delay,
            'initial' => $initial,
            'initialDropboxLineagesSelections' => (!$dropbox) ? NULL : $dropbox->lineages_selections,
            'addButton' => theme('hierarchical_select_dropbox_add_button', $hsid),
            'module' => $module,
            'enforceDeepest' => $enforce_deepest,
            'saveLineage' => $save_lineage,
            'allOption' => $all_option,
            'levelLabels' => implode('|', $level_labels),
            'params' => serialize($params),
            'dropboxTitle' => $dropbox_title,
            'dropboxLimit' => $dropbox_limit,
            'required' => $required,
            'multiple' => $multiple, // Enables the dropbox.
          ),
        ),
      )
    ),
    'setting'
  );

  // If the "save lineage" option is enabled, make the select a multiple select.
  if ($save_lineage) {
    $element['#multiple'] = TRUE;
  }

  // If multiple select is enabled, then add a validate callback that will
  // ensure the dropbox limit won't be exceeded.
  $element['#validate'] = array('_hierarchical_select_validate' => array(_hierarchical_select_extract_settings($element)));

  // Set the unique class.
  $element['#attributes']['class'] .= " hierarchical-select-original-select hierarchical-select-$hsid-original-select";

  return $element;
}

/**
 * Hierarchical select form element validate callback.
 */
function _hierarchical_select_validate($element, $settings) {
  // Extract the settings for this hierarchical select from the settings we're
  // receiving via the extra parameter.
  extract($settings);

  // Generate the dropbox again and use it to count the number of lineages
  // that the user selected. This must be below the dropbox limit.
  if ($dropbox_limit > 0) { // Zero as dropbox limit means no limit.
    $dropbox = (!$multiple) ? FALSE : hierarchical_select_get_dropbox($module, $selection, $save_lineage, array(), $params, '');
    if (count($dropbox->lineages) > $dropbox_limit) {
      form_error($element, t("You've selected %select-count items, but you're only allowed to select %dropbox-limit items.", array('%select-count' => count($dropbox->lineages), '%dropbox-limit' => $dropbox_limit)));
    }
  }
}

/**
 * Form definition; admin settings.
 */
function hierarchical_select_admin_settings() {
  $form['description'] = array(
    '#value' => t('All settings below will be used as site-wide defaults.'),
    '#prefix' => '<div>',
    '#suffix' => '</div>',
  );
  $form['hierarchical_select_animation_delay'] = array(
    '#type' => 'textfield',
    '#title' => t('Animation delay'),
    '#description' => t(
      'The delay that will be used for the "drop in/out" effect when a
      hierarchical select is being updated (in milliseconds).'
    ),
    '#size' => 5,
    '#maxlength' => 5,
    '#default_value' => variable_get('hierarchical_select_animation_delay', 400),
  );
  $form['hierarchical_select_level_labels_style'] = array(
    '#type' => 'select',
    '#title' => t('Level labels style'),
    '#description' => t(
      'The style that will be used for level labels. This is not supported by
      all browsers! If you want a consistent interface, choose to use no
      style.'
    ),
    '#options' => array(
      'none' => t('No style'),
      'bold' => t('Bold'),
      'inversed' => t('Inversed'),
      'underlined' => t('Underlined'),
    ),
    '#default_value' => variable_get('hierarchical_select_level_labels_style', 'none'),
  );

  return system_settings_form($form);
}


//----------------------------------------------------------------------------
// Private functions.
 
/**
 * Generate the hierarchy object.
 *
 * @param $module
 *   The module that should be used for HS hooks.
 * @param $selection
 *   The selection based on which a HS should be rendered.
 * @param $save_lineage
 *   Whether the "save lineage" option is enabled or not.
 * @param $enforce_deepest
 *   Whether the "enforce deepest" option is enabled or not.
 * @param $all_option
 *   Prepends a new option, that allows you to select all items at once.
 * @param $level_labels
 *   An array of labels, one per level. Optional.
 * @param $params
 *   An array of parameters, which may be necessary for some implementations.
 *   Optional.
 * @param $required
 *   Whether the form item is required or not. (#required Forms API property)
 * @param $dropbox
 *   A dropbox object, or FALSE.
 * @return
 *   A hierarchy object.
 */
function hierarchical_select_get_hierarchy($module, $selection, $save_lineage, $enforce_deepest, $all_option, $level_labels = array(), $params = array(), $required, $dropbox = FALSE) {
  $hierarchy = new stdClass();

  //
  // Build the lineage.
  //

  // Validate and clean up the selection.
  $selection = _hierarchical_select_validate_selection($selection, $module, $params);

  // If save_linage is enabled, reconstruct the lineage. This is necessary
  // because e.g. the taxonomy module stores the terms by order of weight and
  // lexicography, rather than by hierarchy.
  if ($save_lineage && is_array($selection) && count($selection) >= 2) {
    // Ensure the item in the root level is the first item in the selection.
    $root_level = array_keys(module_invoke($module, 'hierarchical_select_root_level', $params));

    for ($i = 0; $i < count($selection); $i++) {
      if (in_array($selection[$i], $root_level)) {
        if ($i != 0) { // Don't swap if it's already the first item.
          list($selection[0], $selection[$i]) = array($selection[$i], $selection[0]);
        }
        break;
      }
    }
    // Reconstruct all sublevels.
    for ($i = 0; $i < count($selection); $i++) {
      $children = array_keys(module_invoke($module, 'hierarchical_select_children', $selection[$i], $params));

      // Ensure the next item in the selection is a child of the current item.
      for ($j = $i + 1; $j < count($selection); $j++) {
        if (in_array($selection[$j], $children)) {
          list($selection[$j], $selection[$i + 1]) = array($selection[$i + 1], $selection[$j]);
        }
      }
    }
  }

  // When nothing is currently selected, the dropbox is enabled and at least
  // one selection has been added to the dropbox, then set the root level to
  // "<none>". Otherwise, default to the root level label.
  if ($selection == -1) {
    $hierarchy->lineage[0] = ($dropbox && count($dropbox->lineages) > 0) ? 'none' : 'label_0';
  }
  else {
    // If save_lineage option is enabled, then the selection *is* a lineage.
    // If it's disabled, we have to generate one ourselves based on the
    // (deepest) selected item.
    if ($save_lineage) {
      // When the form item is optional, the "<none>" option can be selected,
      // thus only the first level will be displayed. As a result, we won't
      // receive an array as the selection, but only a single item. We convert
      // this into an array.
      $hierarchy->lineage = (is_array($selection)) ? $selection : array(0 => $selection);
    }
    else {
      $selection = (is_array($selection)) ? $selection[0] : $selection;
      if (module_invoke($module, 'hierarchical_select_valid_item', $selection, $params)) {
        $hierarchy->lineage = module_invoke($module, 'hierarchical_select_lineage', $selection, $params);
      }
      else {
        // If the selected item is invalid, then start with an empty lineage.
        $hierarchy->lineage = array();
      }
    }
  }

  // If enforce_deepest is enabled, ensure that the lineage goes as deep as
  // possible: append values of items that will be selected by default.
  if ($enforce_deepest && !in_array($hierarchy->lineage[0], array('none', 'label_0'))) {
    $hierarchy->lineage = _hierarchial_select_enforce_deepest_selection($hierarchy->lineage, $hierarchy->levels[0], $module, $params);
  }

  //
  // Build the levels.
  //

  // Start building the levels, initialize with the root level.
  $hierarchy->levels[0] = module_invoke($module, 'hierarchical_select_root_level', $params);

  // Prepend an "all" option to the root level when a dropbox is in use.
  if ($dropbox && $all_option) {
    $hierarchy->levels[0] = array('all' => '<'. t('all') .'>') + $hierarchy->levels[0];
  }

  // Prepend a "<none>" option to the root level when:
  // - the form item is optional.
  // - enforce_deepest is enabled (use case: when level labels are disabled,
  //   this will be the initial value when the form item is required, so that
  //   the user /can/ select nothing, but will get a validation error)
  // - a dropbox is in use and at least one item has been selected.
  if (!$required || $enforce_deepest || ($dropbox && count($dropbox->lineages) > 0)) {
    $hierarchy->levels[0] = array('none' => '<'. t('none') .'>') + $hierarchy->levels[0];
  } 

  // Calculate the lineage's depth (starting from 0).
  $max_depth = count($hierarchy->lineage) - 1;

  // Build all sublevels, based on the lineage.
  for ($depth = 1; $depth <= $max_depth; $depth++) {
    $hierarchy->levels[$depth] = module_invoke($module, 'hierarchical_select_children', $hierarchy->lineage[$depth - 1], $params);
  }

  // If enforce_deepest is enabled and the root label is set, prepend it.
  if ($enforce_deepest && isset($level_labels[0]) && strlen($level_labels[0]) > 0) {
    $hierarchy->levels[0] = array('label_0' => $level_labels[0]) + $hierarchy->levels[0];  
  }
  // If enforce_deepest is disabled …
  else if (!$enforce_deepest) {
    // … prepend labels to every level …
    for ($depth = 0; $depth <= $max_depth; $depth++) {
      $hierarchy->levels[$depth] = array('label_'. $depth => $level_labels[$depth]) + $hierarchy->levels[$depth];
    }

    // … and have to add one more level if appropriate.
    $parent = $hierarchy->lineage[$max_depth];
    if (module_invoke($module, 'hierarchical_select_valid_item', $parent, $params)) {
      $children = module_invoke($module, 'hierarchical_select_children', $parent, $params);
      if (count($children)) {
        // We're good, let's add one level!
        $max_depth++;
        $first_child = reset(array_keys($children));
        $hierarchy->lineage[$max_depth] = 'label_'. $max_depth;
        $hierarchy->levels[$max_depth] = array('label_'. $max_depth => $level_labels[$max_depth]) + $children;
      }
    }
  }

  return $hierarchy;
}

/**
 * Generate the dropbox object.
 *
 * @param $module
 *   The module that should be used for HS hooks.
 * @param $selection
 *   The selection based on which a dropbox should be generated.
 * @param $save_lineage
 *   Whether the "save lineage" option is enabled or not.
 * @param $level_labels
 *   An array of labels, one per level. Optional.
 * @param $params
 *   An array of parameters, which may be necessary for some implementations.
 *   Optional.
 * @param $title
 *   A title that should be displayed above the dropbox. Optional.
 * @return
 *   A dropbox object.
 */
function hierarchical_select_get_dropbox($module, $selection, $save_lineage, $level_labels = array(), $params = array(), $title = '') {
  $dropbox = new stdClass();

  $dropbox->title = (!empty($title)) ? $title : t('All selections');
  $dropbox->lineages = array();
  $dropbox->lineages_selections = array();
  
  // Clean selection.
  if (is_array($selection)) {
    foreach ($selection as $key => $item) {
      if (!module_invoke($module, 'hierarchical_select_valid_item', $item, $params)) {
        unset($selection[$key]);
      }
    }
  }
  else {
    if (!module_invoke($module, 'hierarchical_select_valid_item', $selection, $params)) {
      $selection = array();
    }
  }

  if (!empty($selection)) {
    // Remove all duplicate values from the selection. We'll work with this
    // *set* (repeating values don't matter) of selected items in the code.
    $selection = (is_array($selection)) ? array_unique($selection) : array($selection);

    // Store the "save lineage" setting, needed in the theming layer.
    $dropbox->save_lineage = $save_lineage;

    if ($save_lineage) {
      $dropbox->lineages = _hierarchical_select_reconstruct_lineages_save_lineage_enabled($module, $selection, $params);
    }
    else {
      // Retrieve the lineage of each item. Ignore invalid items.
      foreach ($selection as $item) {
        if (module_invoke($module, 'hierarchical_select_valid_item', $item, $params)) {
          $dropbox->lineages[] = module_invoke($module, 'hierarchical_select_lineage', $item, $params);
        }
      }
      foreach ($dropbox->lineages as $id => $lineage) {
        foreach ($lineage as $level => $item) {
          $dropbox->lineages[$id][$level] = array('value' => $item, 'label' => module_invoke($module, 'hierarchical_select_item_get_label', $item, $params));
        }
      }
    }

    usort($dropbox->lineages, '_hierarchical_select_dropbox_sort');

    // Now store each lineage's selection too. This is needed on the client side
    // to enable the remove button to let the server know which selected items
    // should be removed.
    foreach ($dropbox->lineages as $id => $lineage) {
      if ($save_lineage) {
        // Store the entire lineage.
        $dropbox->lineages_selections[$id] = array_map('_hierarchical_select_dropbox_lineage_item_get_value', $lineage);
      }
      else {
        // Store only the last (aka the deepest) value of the lineage.
        $dropbox->lineages_selections[$id][0] = $lineage[count($lineage) - 1]['value'];
      }
    }
  }

  return $dropbox;
}


/**
 * Helper function to extract the settings from a form item.
 *
 * @param $element
 *   A form item.
 * @return
 *   An array of setting name - setting value pairs.
 */
function _hierarchical_select_extract_settings($element) {
  return array(
    'module'          => $element['#hierarchical_select_settings']['module'],
    'enforce_deepest' => (bool) $element['#hierarchical_select_settings']['enforce_deepest'],
    'save_lineage'    => (bool) $element['#hierarchical_select_settings']['save_lineage'],
    'level_labels'    => (array) $element['#hierarchical_select_settings']['level_labels'],
    'animation_delay' => (int) $element['#hierarchical_select_settings']['animation_delay'],
    'dropbox_title'   => $element['#hierarchical_select_settings']['dropbox_title'],
    'dropbox_limit'   => (int) $element['#hierarchical_select_settings']['dropbox_limit'],
    'params'          => $element['#hierarchical_select_settings']['params'],
    'all_option'      => (bool) $element['#hierarchical_select_settings']['all_option'],
    'required'        => (bool) $element['#required'],
    'multiple'        => (bool) $element['#multiple'],
    // When the #value property is empty, we're rendering this form (and thus
    // the form element) for the first time. When it's no longer empty, this
    // means that the validation failed and that we must keep the option that
    // was selected by the user.
    'selection'       => (!empty($element['#value'])) ? $element['#value'] : $element['#default_value'],
  );
}

/**
 * Helper function to reconstruct the lineages given a set of selected items
 * and the fact that the "save lineage" option is enabled.
 *
 * Note that it's impossible to predict how many lineages if we know the
 * number of selected items, exactly because the "save lineage" option is
 * enabled.
 *
 * Worst case time complexity is O(n^3), optimizations are still possible.
 *
 * @param $module
 *   The module that should be used for HS hooks.
 * @param $selection
 *   The selection based on which a dropbox should be generated.
 * @param $params
 *   An array of parameters, which may be necessary for some implementations.
 *   Optional.
 * @return
 *   An array of dropbox lineages.
 */
function _hierarchical_select_reconstruct_lineages_save_lineage_enabled($module, $selection, $params) {
  // We have to reconstruct all lineages from the given set of selected
  // items. That means: we have to reconstruct every possible combination!
  $lineages = array();
  $root_level = module_invoke($module, 'hierarchical_select_root_level', $params);
  foreach ($selection as $key => $item) {
    // Create new lineage if the item can be found in the root level.
    if (in_array($item, array_keys($root_level))) {
      $lineages[][0] = array('value' => $item, 'label' => $root_level[$item]);
      unset($selection[$key]);
    }
  }

  // Keep on trying as long as at least one lineage has been extended.
  $at_least_one = TRUE;
  for ($i = 0; $at_least_one; $i++) {
    $at_least_one = FALSE;
    $num = count($lineages);

    // Try to improve every lineage. Make sure we don't iterate over
    // possibly new lineages.
    for ($id = 0; $id < $num; $id++) {
      $children = module_invoke($module, 'hierarchical_select_children', $lineages[$id][$i]['value'], $params);

      $child_added_to_lineage = FALSE;
      foreach (array_keys($children) as $child) {
        if (in_array($child, $selection)) {
          if (!$child_added_to_lineage) {
            // Add the child to the lineage.
            $lineages[$id][$i + 1] = array('value' => $child, 'label' => $children[$child]);
            $child_added_to_lineage = TRUE;
            $at_least_one = TRUE;
          }
          else {
            // Create new lineage based on current one and add the child.
            $lineage = $lineages[$id];
            $lineage[$i + 1] = array('value' => $child, 'label' => $children[$child]);;

            // Add the new lineage to the set of lineages
            $lineages[] = $lineage;
          }
        }
      }
    }
  } 

  return $lineages;
}

/**
 * Helper function to update the lineage of the hierarchy to ensure that the
 * user selects an item in the deepest level of the hierarchy.
 *
 * @param $lineage
 *   The lineage up to the deepest selection the user has made so far.
 * @param $root_level
 *   The options in the root level.
 * @param $module
 *   The module that should be used for HS hooks.
 * @param $params
 *   The params that should be passed to HS hooks.
 * @return
 *   The updated lineage.
 */
function _hierarchial_select_enforce_deepest_selection($lineage, $root_level, $module, $params) {
  // Use the deepest item as the first parent. Then apply this algorithm:
  // 1) get the parent's children, stop if no children
  // 2) choose the first child as the option that is selected by default, by
  //    adding it to the lineage of the hierarchy
  // 3) make this child the parent, go to step 1.
  $parent = end($lineage); // The last item in the lineage is the deepest one.
  $children = module_invoke($module, 'hierarchical_select_children', $parent, $params);
  while (count($children)) {
    $first_child = reset(array_keys($children));
    $lineage[] = $first_child;
    $parent = $first_child;
    $children = module_invoke($module, 'hierarchical_select_children', $parent, $params);
  }

  return $lineage;
}

/**
 * Reset the selection if no valid item was selected. If an array is passed
 * (this happens when the "save lineage" option is enabled), then the first
 * item in the array corresponds to the first selected term. As soon as an
 * invalid item is encountered, the lineage from that level to the deeper
 * levels should be unset. This is so to ignore selection of a level label.
 *
 * @param $selection
 *   Either a single item id or an array of item ids.
 * @param $module
 *   The module that should be used for HS hooks.
 * @param $params
 *   The module that should be passed to HS hooks.
 * @return
 *   The updated selection.
 */
function _hierarchical_select_validate_selection($selection, $module, $params) {
  // Reset if no item was selected or the item's id could not be validated.
  $selection = (empty($selection)) ? -1 : $selection;
  if (is_array($selection)) {
    // The "save lineage" option is enabled because $selection is an array.
    $valid = TRUE;
    for ($i = 0; $i < count($selection); $i++) {
      if ($valid) {
        $valid = module_invoke($module, 'hierarchical_select_valid_item', $selection[$i], $params);
      }
      if (!$valid) {
        unset($selection[$i]);
      }
    }
    if (empty($selection)) {
      $selection = -1;
    }
  }
  elseif ($selection != 'none' && !module_invoke($module, 'hierarchical_select_valid_item', $selection, $params)) {
    $selection = -1;
  }
  return $selection;
}

/**
 * Helper function that adds the JS to reposition the exposed filters of a
 * View just once.
 */
function _hierarchical_select_views_exposed_filters_reposition() {
  static $js_added;
  
  if (!isset($js_added)) {
    drupal_add_js(drupal_get_path('module', 'hierarchical_select') .'/modules/views.js', 'module');
  }
}

/**
 * Convert a "true" or "false" string into the corresponding boolean value,
 * while ignoring the case.
 *
 * @param $string
 *   The string to convert.
 * @return
 *   The boolean value.
 */
function _hierarchical_select_str_to_bool($string) {
  return (strcasecmp($string, 'TRUE') == 0);
}

/**
 * Dropbox lineages sorting callback.
 *
 * @param $lineage_a
 *   The first lineage.
 * @param $lineage_b
 *   The second lineage.
 * @return
 *   An integer that determines which of the two lineages comes first.
 */
function _hierarchical_select_dropbox_sort($lineage_a, $lineage_b) {
  $string_a = implode('', array_map('_hierarchical_select_dropbox_lineage_item_get_label', $lineage_a));
  $string_b = implode('', array_map('_hierarchical_select_dropbox_lineage_item_get_label', $lineage_b));
  return strcmp($string_a, $string_b);
}

/**
 * Helper function needed for the array_map() call in the dropbox sorting
 * callback.
 *
 * @param $item
 *   An item in a dropbox lineage.
 * @return
 *   The value associated with the "label" key of the item.
 */
function _hierarchical_select_dropbox_lineage_item_get_label($item) {
  return $item['label'];
}

/**
 * Helper function needed for the array_map() call in the dropbox lineages
 * selections creation.
 *
 * @param $item
 *   An item in a dropbox lineage.
 * @return
 *   The value associated with the "value" key of the item.
 */
function _hierarchical_select_dropbox_lineage_item_get_value($item) {
  return $item['value'];
}


//----------------------------------------------------------------------------
// Theming callbacks.

/**
 * @ingroup themeable
 * @{
 */

/**
 * Render the selects.
 *
 * @param $hsid
 *   A hierarchical select id.
 * @param $hierarchy
 *   A hierarchy object.
 * @return
 *   The rendered HTML.
 */
function theme_hierarchical_select_render_selects($hsid, $hierarchy) {
  $output = '';
  $level_labels_style = variable_get('hierarchical_select_level_labels_style', 'none');

  for ($depth = 0; $depth < count($hierarchy->lineage); $depth++) {
    $output .= '<select id="hierarchical-select-'. $hsid .'-select-level-'. $depth .'" class="form-select hierarchical-select-select hierarchical-select-'. $hsid .'-select">';
    foreach ($hierarchy->levels[$depth] as $value => $label) {
      $output .= '<option';
      if (preg_match('/^label_\d+$/', $value) && $level_labels_style != 'none') {
        $output .= ' class="hierarchical-select-level-label-'. $level_labels_style .'"';
      }
      if ($value == $hierarchy->lineage[$depth]) {
        $output .= ' selected="selected" value="'. check_plain($value) .'"><strong>'. check_plain($label) .'</strong></option>';
      }
      else {
        $output .= ' value="'. check_plain($value) .'">'. check_plain($label) .'</option>';
      }
    }
    $output .= '</select>';
  }

  return $output;
}

/**
 * Render the dropbox.
 *
 * @param $hsid
 *   A hierarchical select id.
 * @param $dropbox
 *   A dropbox object.
 * @return
 *   The rendered HTML.
 */
function theme_hierarchical_select_render_dropbox($hsid, $dropbox) {
  $output = '';

  $separator = '›';
  $separator_html = '<span class="dropbox-item-separator">'. $separator .'</span>';

  $output .= '<tbody>';
    
  if (!empty($dropbox->lineages)) {
    foreach ($dropbox->lineages as $id => $lineage) {
      // Preparation: get the labels of the lineage.
      $lineage_labels = array();
      for ($level = 0; $level < count($lineage); $level++) {
        $lineage_labels[] = $lineage[$level]['label'];
      }

      $zebra = (($id + 1) % 2 == 0) ? 'even' : 'odd';
      $first = ($id == 0) ? 'first' : '';
      $last = ($id == count($dropbox->lineages) - 1) ? 'last' : '';

      $output .= '<tr class="dropbox-entry '. $first .' '. $last .' '. $zebra .'">';

      // If the "save lineage" option is enabled: select every item. Otherwise
      // only select the last item.
      $output .= '<td>';
      if ($dropbox->save_lineage) {
        $output .= '<span class="dropbox-selected-item">'. implode('</span>'. $separator_html .'<span class="dropbox-selected-item">', $lineage_labels) .'</span>';
      }
      else {
        $output .= '<span class="dropbox-item">'. implode('</span>'. $separator_html .'<span class="dropbox-item">', array_slice($lineage_labels, 0, count($lineage_labels) - 1)) .'</span>';
        if (count($lineage_labels) > 1) {
          $output .= $separator_html;
        }
        $output .= '<span class="dropbox-selected-item">'. $lineage_labels[count($lineage_labels) - 1] .'</span>';
      }
      $output .= '</td>';

      // Add a column with a "Remove" link.
      $output .= '<td><a id="hierarchical-select-'. $hsid .'-remove-'. $id .'-from-dropbox" class="hierarchical-select-remove-from-dropbox hierarchical-select-'. $hsid .'-remove-from-dropbox">'. t('Remove') .'</a></td>';

      $output .= '</tr>';
    }
  }
  else {
    $output .= '<tr class="dropbox-entry first last dropbox-is-empty"><td>'. t('Nothing has been selected yet.') .'</td></tr>';
  }

  // Add the dropbox title as a table caption.
  $output .= '<caption class="dropbox-title">'. check_plain($dropbox->title) .'</caption>';

  $output .= '</tbody>';

  return $output;
}

/**
 * Render the initial hierarchical select.
 *
 * @param $hsid
 *   A hierarchical select id.
 * @param $hierarchy
 *   A hierarchy object.
 * @param $dropbox
 *   A dropbox object.
 * @return
 *   The rendered HTML.
 */
function theme_hierarchical_select_render_initial_html($hsid, $hierarchy, $dropbox) {
  $output = '';

  $output .= '<div class="hierarchical-select-input clear-block">';
  $output .= theme('hierarchical_select_render_selects', $hsid, $hierarchy);
  $output .= '</div>';

  if ($dropbox) {
    $output .= '<table class="hierarchical-select-dropbox">';
    $output .= theme('hierarchical_select_render_dropbox', $hsid, $dropbox);
    $output .= '</table>';
  }

  return $output;
}

/**
 * Render the add button.
 *
 * @param $hsid
 *   A hierarchical select id.
 * @return
 *   The rendered HTML.
 */
function theme_hierarchical_select_dropbox_add_button($hsid) {
  $output = '';

  $output .= '<input id="hierarchical-select-'. $hsid .'-add-to-dropbox"';
  $output .= ' class="hierarchical-select-add-to-dropbox form-submit"';
  $output .= ' type="button"';
  $output .= ' value="'. t('Add') .'" />';

  return $output;
}

/**
 * @} End of "ingroup themeable".
 */