/*

getElementsBySelector
Version 0.1
Copyright (C) 2005 Greg Methvin (greg@methvin.net)

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are
met:

* Redistributions of source code must retain the above copyright
  notice, this list of conditions and the following disclaimer.

* Redistributions in binary form must reproduce the above copyright
  notice, this list of conditions and the following disclaimer in the
  documentation and/or other materials provided with the distribution.

* The name of the author may not be used to endorse or promote
  products derived from this software without specific prior written
  permission

THIS SOFTWARE IS PROVIDED BY THE AUTHOR "AS IS" AND ANY EXPRESS OR
IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
POSSIBILITY OF SUCH DAMAGE.

--

This function allows you to use CSS selectors to select elements in
the DOM. It currently supports these selectors:

 *  Type selectors (tag)
 *  Universal selector (*)
 *  ID selectors (#id)
 *  Class selectors (.class)
 *  Descendant combinator ( )
 *  Child combinator (>)
 *  Direct adjacent-sibling combinator (+)
 *  Indirect adjacent-sibling combinator (~)
 *  :root, :first-child, :last-child, and :only-child pseudo-classes
 *  :first-of-type, :last-of-type, and :only-of-type pseudo-classes
 *  :nth-child(an+b) and :nth-last-child(an+b) pseudo-classes
 *  :nth-of-type(an+b) and :nth-last-of-type(an+b) pseudo-classes
 *  :empty pseudo-class
 *  :target pseudo-class
 *  attribute selectors

--

Please note that I am no longer actively maintaining this code. Feel
free to improve upon it if you are interested; let me know if you do
so I can introduce any changes you make and credit you here. Since
this code has not been extensively tested, I would not recommend that
anyone use it in production applications.

*/

// Make sure arrays have the push and pop methods

Array.prototype.push = Array.prototype.push || function()
{
  for (var i = 0; i < arguments.length; i++)
    this[this.length] = arguments[i];
};

Array.prototype.pop = Array.prototype.pop || function()
{
  return this[this.length-1];
  this.length--;
};

document.getElementsBySelector = function(selector, srcElement)
{
  if (!selector || !document.getElementsByTagName)
    return [];
  srcElement = srcElement || document;

  // regular expression to match combinators
  var combinator_re = /([\,\s\+>~])/g;

  // select new elements based on an array of elements and a combinator
  // filters are functions used to provide additional validation; they should return true if valid, false otherwise.
  var getSelectedElements = function(elements, combinator, filters)
  {
    var found = [];
    var check = function(e) { for (var i = 0; i < filters.length; i++) if (!filters[i](e)) return false; return true; };
    switch (combinator)
    {
      case ' ': // descendant selector
        for (var i = 0; i < elements.length; i++)
        {
          var els = elements[i].all || elements[i].getElementsByTagName('*');
          for (var j = 0; j < els.length; j++)
            if (check(els[j]))
              found.push(els[j]);
        }
        break;
      case '>': // child selector
        for (var i = 0; i < elements.length; i++)
        {
          var nodes = elements[i].childNodes;
          for (var j = 0; j < nodes.length; j++)
            if (nodes[j].nodeType == 1 && check(nodes[j])) 
              found.push(nodes[j]);
        }
        break;
      case '+': // direct adjacent sibling selector
        for (var i = 0; i < elements.length; i++)
        {
          var nodes = elements[i].parentNode.childNodes;
          var els = [];
          for (var j = 0; j < nodes.length; j++)
            if (nodes[j].nodeType == 1)
              els.push(nodes[j]);
          for (var j = 1; j < els.length; j++)
            if (els[j-1] == elements[i])
              if (els[j] && check(els[j]))
                found.push(els[j]);
        }
        break;
      case '~': // indirect adjacent sibling selector
        for (var i = 0; i < elements.length; i++)
        {
          var nodes = elements[i].parentNode.childNodes;
          var index = nodes.length;
          for (var j = 0; j < nodes.length; j++)
          {
            if (nodes[j] == elements[i])
              index = j;
            if (nodes[j].nodeType == 1 && j > index && nodes[j] && check(nodes[j]))
              found.push(nodes[j]);
          }
        }
        break;
    }
    return found;
  };
  // place whitespace between tokens
  var combinator_pattern = combinator_re.toString().replace(/^\//g,'').replace(/\/[gim]{0,3}$/g,'');
  var recursiveReplace = function(str, re, repl) { while (str.match(re)) str = str.replace(re, repl); return str; };
  selector = recursiveReplace(selector.replace(combinator_re,'\n$1\n').replace(/\s*\n\s*/g,'\n'),
    new RegExp('([\\(\\[])([^\\1]*)\\n+'+combinator_pattern+'\\n+([^\\1]*)', 'gm'), '$1$2$3$4');
  
  var elements = [];
  // split up comma-separated selectors and process them separately
  if (selector.match(/\n\,\n/m))
  {
    var selectors = selector.split(/\n\,\n/m);
    for (var i = 0; i < selectors.length; i++)
    {
      var selected = document.getElementsBySelector(selectors[i]);
      for (var j = 0; j < selected.length; j++)
      {
        var k;
        for (k = 0; k < elements.length; k++)
          if (elements[k] == selected[j])
            break;
        elements[k] = selected[j];
      }
    }
    return elements;
  }
  
  // get the filter functions for the simple selector
  var getFilters = function(token)
  {
    var filters = [];
    // attribute selectors
    var attrNames = [], attrPatterns = [];
    var attr_re = /\[([\w\-:]+)([=~\|\^\$\*]?)=?([\"\']?)(([^\]]|\\\3)*)\3\]/i;
    while (token.match(attr_re))
    {
      var attrName = RegExp.$1;
      var attrOperator = RegExp.$2;
      var attrValue = RegExp.$4.replace(/\\([\\\"\'])/, '$1');
      var attrPattern = null;
      switch (attrOperator)
      {
        case '=':
          attrPattern = '^'+attrValue+'$';
          break;
        case '~':
          attrPattern = '\\b'+attrValue+'\\b';
          break;
        case '|':
          attrPattern = '^'+attrValue+'-?';
          break;
        case '^':
          attrPattern = '^'+attrValue;
          break;
        case '$':
          attrPattern = attrValue+'$';
          break;
        case '*':
          attrPattern = attrValue;
          break;
      }
      attrNames.push(attrName);
      attrPatterns.push(attrPattern);
      token = token.replace(attr_re, ' ').replace(/\s([\[\.:#]|$)/,'$1');
    }
    // filter tags for attribute selectors
    if (attrNames && attrPatterns)
      filters.push(function(e) {
        for (var i = 0; i < attrNames.length; i++)
        {
          var attr = e.getAttribute(attrNames[i]);
          var pattern = attrPatterns[i];
          if (attr == null || (pattern != null && !attr.match(new RegExp(pattern))))
            return false;
        }
        return true;
      });

    // pseudo-classes
    var pseudoClasses = [];
    var pc_re = /:(([^:]*)(\(([^\)]*)\))?)/;
    while (token.match(pc_re))
    {
      pseudoClasses.push(RegExp.$1);
      token = token.replace(pc_re, ' ').replace(/\s([\[\.:#]|$)/,'$1');
    }
    if (pseudoClasses)
      filters.push(function(e)
      {
        for (var i = 0; i < pseudoClasses.length; i++)
        {
          var pc = pseudoClasses[i];
          var tagName = e.nodeName;
          if (pc.match(/^root$/i))
          {
            if (e != document.documentElement)
              return false;
          }
          else if(pc.match(/^empty$/i))
          {
            if (e.childNodes.length)
              return false;
          }
          else if(pc.match(/^target$/i))
          {
            var hash = window.location.hash && window.location.hash.toString().replace(/^#/,'');
            if (!hash || (e.id != hash && e.name != hash))
              return false;
          }
          else if (pc.match(/^(first|last|only)-(child|of-type)$/i))
          {
            var re1 = RegExp.$1, re2 = RegExp.$2;
            var fromTop = !!re1.match(/first|only/i);
            // for only, just check both first and last
            if (re1.match(/only/i))
              pseudoClasses.push('last-'+re2);
            var ofType = !!re2.match(/of-type/i);
            var nodes = e.parentNode.childNodes;
            var n = fromTop? -1 : nodes.length;
            // loop until you find an element, then check it against the current element
            while (nodes[fromTop? ++n:--n].nodeType != 1 || (ofType && nodes[n].nodeName != tagName));
            if (e != nodes[n])
              return false;
          }
          else if (pc.match(/^nth-(last-)?(child|of-type)\(([n\s\d\+\-]+|even|odd)\)$/i))
          {
            var re1 = RegExp.$1, re2 = RegExp.$2, re3 = RegExp.$3;
            var reversed = !!re1;
            var ofType = !!re2.match(/of-type/i);
            var expr = re3.replace(/even/i,'2n').replace(/odd/i,'2n+1').replace(/(\d+)n/i,'$1*n');
            var nodes = e.parentNode.childNodes;
            // make an array of all the elements
            var els = [];
            for (var n = 0; n < nodes.length; n++)
              if (nodes[n].nodeType == 1 && (!ofType || nodes[n].nodeName == tagName))
                els.push(nodes[n]);
            // find out the child number of this element
            var child_num = 0;
            while (els[child_num++] != e);
            if (reversed)
              child_num = els.length + 1 - child_num;
            // check to see if the child number matches the given expression
            var matched = false;
            for (var n = 0; n <= els.length; n++)
              if (child_num == eval(expr))
              {
                matched = true;
                break;
              }
            if (!matched)
              return false;
          }
          else 
          {
            // This pseudo-class cannot be recognized
            return false;
          }
        }
        return true;
      });

    // ID selectors
    var matches = [];
    var id_re = /#[\w\-]+/gi;
    if (matches = token.match(id_re))
    {
      var id = matches[0].replace(/^#/,'');
      // filter for id selector
      filters.push(function(e) { return e.id == id; });
      token = token.replace(id_re,'');
    }
    // class selectors
    var class_re = /\.[\w\-]+/gi;
    if (matches = token.match(class_re))
    {
      var classNames = [];
      for (var j = 0; j < matches.length; j++)
        classNames[j] = matches[j].replace(/^\./,'');   
      // filter for class selector
      filters.push(function(e) {
        for (var i = 0; i < classNames.length; i++)
          if (!classNames[i] || !e.className.match(new RegExp('\\b'+classNames[i]+'\\b')))
            return false;
        return true;
      });
      token = token.replace(class_re,'');
    }
    // tag names
    var tagName = token.toLowerCase() || '*';
    if (tagName != '*')
      filters.push(function(e) {
        return e.nodeName.toLowerCase() == tagName;
      });
    return filters;
  }
  
  elements = [srcElement];
  // Split selector into tokens
  var tokens = selector.split(/\n+/gm);
  
  for (var i = 0; i < tokens.length; i++)
  {    
    // check for a combinator
    // if none is found, default to descendant combinator
    var combinator = ' ';
    if (i > 0 && tokens[i].match(combinator_re))
      combinator = tokens[i++];

    var token = tokens[i];
    if (!token)
      return [];

    // run the filters
    elements = getSelectedElements(elements, combinator, getFilters(token));
  }
  return elements;
}