var display_nav = true;
// id of the nav root node
var nav_root_id = "nav-container";
var crumb_root_id = "crumb-container";
var crumb_breaker = " > ";
var page_alternatives = ["index.html", "index.htm"];
var page_alts_string = build_alternatives(page_alternatives, false);
var page_alts_regexp = new RegExp(page_alts_string+"(?:(?:\\?|#).*)?$", "i");

// builds an alternating regex source from the given array
// if capt is false, the expression won't capture
function build_alternatives(alternatives, capt) {
  var str = capt ? "(" : "(?:";
  for (var i=0; i<alternatives.length; i++) {
    if (i > 0) str += "|";
    str += alternatives[i];
  }
  str += ")";
  return str;
}

// given two lists, returns the index of the first element that differs
function findDiffInLists(data1, data2, fromIdx) {
  if (fromIdx == null) fromIdx = 0;
  if (data1 instanceof Array && data2 instanceof Array)
    for (var i = fromIdx; i < data1.length; i++)
      if (data1[i] != data2[i])	return i;
  return null;
}

// tricky way of determining if a variable/property is defined on an object
function isDefined(object, variable) {
  return eval("(typeof(object['"+variable+"']) != 'undefined');");
}

// return the url given, with common implicit names (index.html) removed
var url_clean_regexp = new RegExp("^(.*/)"+page_alts_string);
function url_clean(url) {
  if (url.match("/\/$/")) {
    return url;
  }
  if (url.match(url_clean_regexp)) {
    return RegExp.$1;
  }
  return url;
}

// return the pathname component of a url
// if collapse is true, removes common implicit names like index.html
var url_pathname_regexp = new RegExp("\/\/[^\/]+([^?#]*).*?$");
function url_pathname(url, collapse) {
  if (url.match(url_pathname_regexp)) {
    if (collapse) {
      var pathname = RegExp.$1;
      return pathname.replace(page_alts_regexp, "");
    } else {
      return RegExp.$1;
    }
  }
  return url;
}

// return the host component of a url
var url_host_regexp = new RegExp("\/\/([^\/]+).*$");
function url_host(url) {
  if (url.match(url_host_regexp)) {
    return RegExp.$1;
  } else if (url.match(/^([^\/]+).*$/)) {
    return RegExp.$1;
  }
  return null;
}

// relaxed matching to allow for implicit index pages
// returns boolean indicating match
var url_match_regexp = new RegExp("^(.*/)"+page_alts_string+"$");
function url_match(url, target) {
  if (url == target) {
    return true;
  } else {
    if (url.match(url_match_regexp) && RegExp.$1 == target) {
      return true;
    }
  }
  return false;
}

// what it says (if tag is null will search for tagless nodes)
function firstChildByTagName(node, tag) {
  if (!node) return false;
  if (tag) tag = tag.toUpperCase();
  var child = node.firstChild;
  if (child) {
    do {
      if (child.tagName) {
	if (child.tagName.toUpperCase() == tag) {
	  return child;
	}
      } else if (! tag) {
	return child;
      }
    } while (child = child.nextSibling);
  }
  return null;
} 

// walk from the current node to the top level of the nav, returning
// an array of 'parent' links. If expand is true, expand ULs appropriately
function walkNavToRoot(current, expand) {
  var path = [];
  while (current.parentNode.parentNode &&
	 current.parentNode.parentNode.id != nav_root_id) {
    if (current.tagName == 'UL') {
      if (expand) current.style.display = "";
    } else if (current.tagName == 'LI') {
      path.push(firstChildByTagName(current, 'A'));
    }
    current = current.parentNode;
  }
  if (current.tagName == 'LI') {
    path.push(firstChildByTagName(current, 'A'));
  }
  return path;
}

// find the closest match in the nav by choosing from the given array,
// that which has a parent that most closely matches the path components
// of the current page
function findClosestNavLinkByStructure(links) {
  var pathlist = window.location.pathname.split(/\//);
  var best_link;
  var best_score = 0;
  for (var i=0; i<links.length; i++) {
    var path = walkNavToRoot(links[i]);
    if (! path) continue;
    var max = 0;
    for (var j=0; j<path.length; j++) {
      var current_list = url_clean(path[j].pathname).split(/\//);
      var score = findDiffInLists(current_list, pathlist, 1);
      if (score > max) {
	max = score;
	//konsole.log("pathname %d,%d=> %s, %d",i,j,current_url,max);
      }
    }
    if (max > best_score) {
      best_link = links[i];
      best_score = max;
    }
    //konsole.log("findClosestNavLinkByStructure() %s => %d",link.text,path.length);
  }
  return best_link;
}

// try various strategies to obtain the best link in the nav for this page
function findClosestNavLink(links) {
  var i;
  var pathname = window.location.pathname;
  var href = window.location.href;
  var host = window.location.host;

  var closest = [];
  // exact match
  for (i=0; i<links.length; i++) {
    if (links[i].href == pathname || links[i].href == href) {
      //konsole.log("found by exact match: %d", i);
      closest.push(links[i]);
    }
  }

  if (closest.length == 0) {
    // account for implied index.html etc
    for (i=0; i<links.length; i++) {
      if (url_match(links[i].href, pathname) ||
	  url_match(links[i].href, href)) {
	//konsole.log("found by url_match()");
	closest.push(links[i]);
      }
    }
  }

  if (closest.length > 0) {
    if (closest.length == 1) {
      return closest[0];
    } else {
      // fall back to examining link parentage
      var closest_link = findClosestNavLinkByStructure(closest);
      //konsole.log("best link <a href=\"%s\">%s</a>",closest_link.href,closest_link.text);
      return closest_link;
    }
  }

  // fall back to closest match
  var best_links = [];
  var best_score = 0;
  var path = pathname.split(/\//);

  for (i=0; i<links.length; i++) {
    var current_link = links[i];
    var current_host = url_host(current_link.href);
    if (current_host && current_host != host) {
      //konsole.log("Skipping link to %s", current_host);
      continue;
    }
    var current_href = current_link.href;
    current_href = url_pathname(current_href);
    var linkpath = current_href.split(/\//);
    var current_score = 0;
    for (var j=1; j<linkpath.length; j++) {
      if (j >= path.length) {
	var dec = (linkpath.length - path.length);
	//konsole.log("decrementing score from %d by %d on %s", current_score, dec, current_link.text);
	current_score -= dec;
	break;
      }
      if (linkpath[j] == path[j]) {
	current_score++;
	//konsole.log("link %s matched %s for score %d", current_href, path[j], current_score);
      }
    }
    if (current_score == best_score) {
      //konsole.log("adding link %s with score %s", current_link.text, current_score);
      best_links.push(current_link);
    } else if (current_score > best_score) {
      //konsole.log("ditching previous in favour of %s", current_link.text);
      best_score = current_score;
      best_links = [current_link];
    }
  }
  var bestest_link;
  var bestest_pathname;    
  if (best_links.length > 0) {
    for (var i=0; i<best_links.length; i++) {
      //konsole.log("best link #%d: <a href='"+best_links[i].href+"'>"+best_links[i].innerHTML+"</a>", i);
      if (! bestest_link) {
	bestest_link = best_links[0];
	bestest_pathname = url_pathname(bestest_link.href, true);
	//konsole.log("url_pathname("+bestest_link.href+", true) => "+bestest_pathname);
	continue;
      }
      var current_pathname = url_pathname(best_links[i].href, true);
      //konsole.log("url_pathname("+best_links[i].href+", true) => "+current_pathname);
      if (current_pathname.length < bestest_pathname.length) {
	bestest_link = best_links[i];
	bestsest_pathname = current_pathname;
      }
    }
    //konsole.log("bestest link: <a href='"+bestest_link.href+"'>"+bestest_link.innerHTML+"</a>");
  } else {
    //konsole.log("best link: NULL");
  }
  return bestest_link;
}

// sets display to none on all descendant UL tags
function collapseMenu(node) {
  if (!document.getElementById) return false;
  if (!node) node = document.getElementById(nav_root_id);
  if (!node) return false;

  var nodes = node.getElementsByTagName('UL');
  for (var i=0; i<nodes.length; i++) {
    if (nodes[i].parentNode != node) {
      nodes[i].style.display = "none";
    }
  }
}

// expand the nav appropriately for where we are in the site
function expandMenu(root) {
  if (!document.getElementById || !document.getElementsByTagName) return false;
  if (!root) root = document.getElementById(nav_root_id);
  if (!root) return false;

  if (root.tagName == 'UL') {
    var node = root;
  } else {
    var node = firstChildByTagName(root, 'UL');
    if (!node) return false;
  }

  var links = node.getElementsByTagName('A');
  if (!links) { return false; }
  
  var path;
  var link = findClosestNavLink(links);
  if (link) {
    var current = link;
    var parent = link.parentNode;
    current.className = "current_link";
    parent.className = "current";
    // expand child branch if there
    var children = parent.childNodes;
    for (var j=0; j<children.length; j++) {
      if (children[j].tagName == 'UL') {
	children[j].style.display = "";
      }
    }
    // step back, expanding branches and accumulating path
    path = walkNavToRoot(current, true);
  } else {
    path = [];
  }
  // now pick up the site root if we haven't already
  var li_top = firstChildByTagName(node, 'LI');
  if (li_top) {
    var a_top = firstChildByTagName(li_top, 'A');
    if (a_top) {
      if (path.length) {
	if (a_top != path[path.length-1]) {
	  path.push(a_top);
	}
      } else {
	path.push(a_top);
      }
    }
  }
  path.reverse();
  return path;
}

// creates breadcrumbs from the nav path generated by expandMenu
function makeCrumbs(path, node) {
  if (!path) return false;
  if (!node) node = document.getElementById(crumb_root_id);
  if (!node) return false;

  var ul_elem = document.createElement('ul');
  for (var i=0; i<path.length; i++) {
    if (i > 0) {
      var breaker = document.createElement('li');
      breaker.innerHTML = crumb_breaker;
      ul_elem.appendChild(breaker);
    }
    var li_elem = document.createElement('li');
    li_elem.setAttribute('class', 'crumb');
    var a_elem = document.createElement('a');
    a_elem.setAttribute('href', path[i].href);
    a_elem.innerHTML = path[i].innerHTML;
    li_elem.appendChild(a_elem);
    ul_elem.appendChild(li_elem);
  }
  node.appendChild(ul_elem);
}

// finds the nav, shows the children, expands the menu, leaves crumbs
function pageLoadHandler() {
  var root = document.getElementById(nav_root_id);
  if (root) {
    if (display_nav) {
      var children = root.childNodes;
      for (var i=0; i<children.length; i++) {
	var child = children[i];
	if (child.tagName == 'UL') {
	  child.style.display = "block";
	}
      }
    }
    collapseMenu();
    var path = expandMenu();
    makeCrumbs(path);
  }
}

// politely adds a function to the end of the window.onload chain
function addLoadEvent(func) {
  var oldonload = window.onload;
  if (typeof window.onload != 'function') {
    window.onload = func;
  } else {
    window.onload = function() {
      oldonload();
      func();
    }
  }
}

addLoadEvent(pageLoadHandler);
document.write('<style type="text/css">#nav { display: none; }</style>');