/* 
* If this thing is worth anything to you please donate
* http://bravelayout.scarabeo.biz/
* mailto:brave1979@o2.pl
*/
var BraveLayout = {}
if(Element == undefined || Element.Methods == undefined || Element.Methods.getElementsBySelector == undefined) {
	var Element = { Methods : { getElementsBySelector : function(parent, selector) { return Selector.findChildElements(parent, [selector]); } } }
}

// ----------- CONFIG
BraveLayout.removeEmpty = true
BraveLayout.everyNodeOnlyOnce = true
BraveLayout.getElementsByCssSelector = Element.Methods.getElementsBySelector
BraveLayout.layoutsHaveCssClass = "bl";
// ----------- END OF: CONFIG


// ----------- PUBLIC
BraveLayout.start = function (layout, options) {
	options = options || {}
	options.width = options.width || '100%'
	options.height = options.height || '100%'
	
	var uid = "bl_"+Math.floor(Math.random()*100000000)+"_BraveLayout";
	document.write('<div style="display:none;" id="'+uid+'">')
	BraveLayout.toMove.push({ uid: uid, items: [] })
	var layoutRoot = BraveLayout.makeNode(layout, BraveLayout.toMove[BraveLayout.toMove.length - 1].items, undefined, undefined, options.width, options.height)
	layoutRoot.style.display = 'none'
	if(BraveLayout.layoutsHaveCssClass) {
		layoutRoot.className += " "+BraveLayout.layoutsHaveCssClass;
	}
	if(options.cls) {
		layoutRoot.className = options.cls;
	}
	if(options.id) {
		layoutRoot.id = options.id;
	}
	BraveLayout.layoutStack.push({uid: uid, root: layoutRoot});		
}
BraveLayout.end = function() {
	document.write('</div>');
	var layout = BraveLayout.layoutStack.pop();
	var layoutContentContainer = document.getElementById(layout.uid)
	layoutContentContainer.parentNode.insertBefore(layout.root, layoutContentContainer);
}
BraveLayout.fill = function() {
	for(var i=BraveLayout.toMove.length-1 ; i>=0 ; --i) {
		var layout = BraveLayout.toMove[i]
		var layoutContentContainer	= document.getElementById(layout.uid)
		var layoutRoot			= layoutContentContainer.previousSibling
	
		BraveLayout.fillOne(layout.items, layoutContentContainer, '');
		
		layoutRoot.style.display=''
		if(layoutContentContainer.parentNode) {
			layoutContentContainer.parentNode.removeChild(layoutContentContainer);
		}
	}
	BraveLayout.toMove = {};
}
// ----------- END OF: PUBLIC

// ----------- PRIVATE
BraveLayout.layoutStack = []
BraveLayout.toMove = []
BraveLayout.position = function(node, element, container) {
	if(node.x) {
		var x = node.x.split(',');
		if(x[1]!='') {
 			element.style.width = x[1];
/* 			if(x[1] == 'auto') {
 			 	var containers = node.cols
				if(containers && containers.length) {
					for(var i = containers.length-1; i>=0; --i) {
						containers[i].dontFillLast = true;
					}
 				}
 			}*/
		}
		if(node.floating) {
			element.style.marginRight = x[2]!=''?x[2]:'0';
			element.style.marginLeft = x[0]!=''?x[0]:'0';
		} else {
			container.style.paddingRight = x[2]!=''?x[2]:'0';
			container.style.paddingLeft = x[0]!=''?x[0]:'0';
		}
		if(x[0]=='') {
			element.style.marginLeft = 'auto';
			if(x[2]=='') {
				container.style.textAlign = 'center';
				element.style.marginRight = 'auto';
			} else {
				container.style.textAlign = 'right';
			}
		} else {
			element.style.marginRight = 'auto';
			container.style.textAlign = 'left';
		}
/*		if(x[1].indexOf("%")!=-1) {
			node.dontFillLast = true;
		}*/
	}
	if(node.y) {
		var y = node.y.split(',');
		if(y[1]!='') {
			element.style.height = y[1];
/* 			if(y[1] == 'auto') {
 			 	var containers = node.rows
				if(containers && containers.length) {
					for(var i = containers.length-1; i>=0; --i) {
						containers[i].dontFillLast = true;
					}
 				}
 			}*/
		}
		if(node.floating) {
			element.style.marginBottom = y[2]!=''?y[2]:'0';
			element.style.marginTop = y[0]!=''?y[0]:'0';
		} else {
			container.style.paddingBottom = y[2]!=''?y[2]:'0';
			container.style.paddingTop = y[0]!=''?y[0]:'0';
		}
		if(y[0]=='') {
			if(y[2]=='') {
				container.style.verticalAlign = 'middle';
			} else {
				container.style.verticalAlign = 'bottom';
			}
		} else {
			container.style.verticalAlign = 'top';
		}
	}
	if(node.size) {
		if(node.size == 'fill') {
			node.size = '100%';
		}
		if(node.isRow) {
			container.style.height = node.size;
//  			container.innerHTML = '<div style="height:'+node.size+'; width: 1px; overflow: hidden; margin-right: -1px; float: right; background: none;"></div>';			
/*			if(node.size.indexOf('%')!==1) {
				element.style.height = node.size;
			}*/
		
/*			if(node.size.indexOf('%')!=-1) {
				node.dontFillLast = true;
			}*/
		} else {
			container.style.width = node.size;
 			container.innerHTML = '<div style="width:'+node.size+'; '+((x!=undefined && x[0]!=undefined)?'margin-left:-'+x[0]+';':'')+((x!=undefined && x[2]!=undefined)?'margin-right:-'+x[2]+';':'')+'line-height: 1px; height: 1px; overflow: hidden; margin-top: -1px; background: none;"></div>'; // possible problem of width of columns too large when they have padding due to settting of 'x'
			
/*			if(node.size.indexOf('%')==-1) {
				element.style.width = node.size;
			}*/
/*			if(node.size.indexOf('%')!=-1) {
				node.dontFillLast = true;
			}*/
		}
	}
}
BraveLayout.makeNode = function(node, listToMove, repeat, parent, width, height) {
	width = width || '100%'
	height = height || '100%'
	var table = document.createElement('table');
	var tbody = document.createElement('tbody');
	var tr = document.createElement('tr');
	var td = document.createElement('td');
	
	tr.appendChild(td);
	tbody.appendChild(tr);
	table.appendChild(tbody);
	
	var x
	if(!parent || (node.x && (x = node.x.split(',')) && (x[0].indexOf('%')!=-1 || x[2].indexOf('%')!=-1))) {
		var outerTable = document.createElement('table');
		var outerTbody = document.createElement('tbody');
		var outerTr = document.createElement('tr');
		var outerTd = document.createElement('td');
		
		outerTable.style.borderCollapse = 'collapse'
		outerTable.style.width = width
		outerTable.style.height = height
		
		outerTd.style.padding = '0';
		outerTd.style.verticalAlign = 'top';
 		outerTd.style.width = '100%'
		outerTd.style.height = '100%'
		
		outerTd.appendChild(table);
		outerTr.appendChild(outerTd);
		outerTbody.appendChild(outerTr);
		outerTable.appendChild(outerTbody);
		
		table.style.width = '100%'
		table.style.height = '100%'
	} else {
		var outerTable = table
		var outerTd = parent
	
		table.style.width = width
		table.style.height = height
		
	}
	
	td.style.padding = '0';
	td.style.verticalAlign = 'top';
// 	td.style.width = '100%'
	td.style.height = '100%'
	
	table.style.borderCollapse = 'collapse'
		
	
	var containers = node.rows || node.cols || node.flow
	if(typeof(node) == 'string' || (node.place != undefined)) {
		listToMove.push({ 
			selector: node.place != undefined ? node.place : node, 
			to: td, 
			repeat: repeat || table,
			subs: containers ? [] : undefined, 
			keepIfEmpty: node.keepIfEmpty, 
			clsOfContainer: node.clsOfContainer && typeof(node.clsOfContainer)!='string' ? node.clsOfContainer : undefined, 
			clsOfPlaced: node.cls && typeof(node.cls)!='string' ? node.cls : undefined, 
			container: node.clsOfContainer && typeof(node.clsOfContainer)!='string' ? outerTd : undefined,
			node: node
		});
	} else if(!containers) {
		var filler = document.createElement("div");
		filler.innerHTML = "&nbsp;"
		filler.style.overflow = "hidden";
		filler.style.height = "0px";
		filler.style.lineHeight = "1px";
		filler.style.width = "0px";
		td.appendChild(filler);
	}
	
	if(node.rows || node.cols) {
		for(var i=0;i<containers.length;++i) {
			if(i>0) {
				if(node.rows) {
					tr = document.createElement('tr');
					tbody.appendChild(tr);
				}
				td = document.createElement('td');
				td.style.padding = '0';
				td.style.verticalAlign = 'top';
//				td.style.width = '100%'
				td.style.height = '100%'
				tr.appendChild(td);
			}
			containers[i].isRow = node.rows
			td.appendChild(BraveLayout.makeNode(containers[i], node.place != undefined ? listToMove[listToMove.length-1].subs : listToMove, node.rows ? tr : td, td));
		}
	} else if(node.flow) {
		for(var i=0;i<node.flow.length;++i) {
			node.flow[i].floating = true;
			var floatedBox = BraveLayout.makeNode(node.flow[i], node.place != undefined ? listToMove[listToMove.length-1].subs : listToMove, undefined, td);
			if(navigator.userAgent.indexOf("MSIE")!=-1) {
				floatedBox.style.display = "inline";
			} else {
				if(navigator.userAgent.indexOf("Gecko")!=-1) {
					floatedBox.style.display = "block";
				}
				floatedBox.style.cssFloat = "left";
				floatedBox.align = "left";
			}
			td.appendChild(floatedBox);
		}
	}
	
	if(typeof(node.cls) == 'string') {
		table.className += ' '+node.cls;
	}
	if(typeof(node.clsOfContainer) == 'string') {
		outerTd.className += ' '+node.clsOfContainer;
	}
	BraveLayout.position(node, table, outerTd);
	
	return outerTable;	
}
BraveLayout.fillOne = function(desc, context) {
	var detached = [], toReattach = [], i, j, k, kmax, item, node, obs, lastAdded, lastPlaced
	for(i=0;i<desc.length;++i) {
		item = desc[i]
		obs = item.selector=='' ? [context] : BraveLayout.getElementsByCssSelector(context, item.selector)
		if(!obs.length) { 
			if(BraveLayout.removeEmpty && !item.keepIfEmpty) {
				detached.push({ item: item.repeat, parent: item.repeat.parentNode, after: item.repeat.previousSibling })
				item.repeat.parentNode.removeChild(item.repeat);
			} else {
				item.to.innerHTML = ''
			}
		} else {
			for(j = obs.length - 1; j >= 0 ; j--) {
				if(item.subs) {
					toReattach = BraveLayout.fillOne(item.subs, lastPlaced = obs[j]);
				} else {
					item.to.innerHTML = ''
					if(BraveLayout.everyNodeOnlyOnce) {
						obs[j].parentNode.removeChild(obs[j])
						item.to.appendChild(lastPlaced = obs[j])
					} else {
						lastPlaced = obs[j].cloneNode(true);
 						item.to.appendChild(lastPlaced)
						if(navigator.userAgent.indexOf('MSIE')!=-1) {	// ie6,ie7 deselects cloned <select>
							var selects = item.to.getElementsByTagName('select');
							for(var k=0;k<selects.length;k++) {
								var t = selects[k];
								var p = new Array();
								var nt = t;
								while(nt != item.to) {
									var nn = nt;
									var ind = 0;
									while(nn = nn.previousSibling) ind++;
									p.unshift(ind);
									nt = nt.parentNode;
								}
								var s = obs[j];
								for(var k = 1; k < p.length; k++) {
									s = s.childNodes[p[k]];
								}
								t.selectedIndex = s.selectedIndex;
							}
						}
 					}
				}
				if(item.clsOfPlaced) {
					for(var cond in item.clsOfPlaced) {
						var ok = false
						switch(cond.charAt(0) == '!' ? cond.substring(1) : cond) {
							case 'first':
								ok = j==0;
							break;
							case 'last':
								ok = j==obs.length-1;
							break;
							case 'odd':
								ok = j%2==0;
							break;
							case 'even':
								ok = j%2==1;
							break;
							case 'all':
								ok = true;
							break;
						}
						if((cond.charAt(0) == '!') ^ ok) {
							lastPlaced.className += ' '+item.clsOfPlaced[cond];
						}
					}
				}
				if(j>0) {
					item.repeat.parentNode.insertBefore(lastAdded = item.repeat.cloneNode(true), item.repeat.nextSibling);
				} else {
					lastAdded = item.repeat
				}
				if(item.repeat.tagName == "TABLE" && navigator.userAgent.indexOf('MSIE')!=-1) {
					item.repeat.parentNode.insertBefore(document.createElement("wbr"), lastAdded.nextSibling);	
				}
				if(item.clsOfContainer) {
					for(var cond in item.clsOfContainer) {
						var ok = false
						switch(cond.charAt(0) == '!' ? cond.substring(1) : cond) {
							case 'first':
								ok = j==0;
							break;
							case 'last':
								ok = j==obs.length-1;
							break;
							case 'odd':
								ok = j%2==0;
							break;
							case 'even':
								ok = j%2==1;
							break;
							case 'all':
								ok = true;
							break;
						}
						if((cond.charAt(0) == '!') ^ ok) {
							if(lastAdded.tagName == 'TR') {
								lastAdded = lastAdded.firstChild;
							}
							lastAdded.className += ' '+item.clsOfContainer[cond];
						}
					}
				}
				if(j>0) {
					for(var k = toReattach.length-1; k >= 0; k--) {
						node = toReattach[k]
						node.parent.insertBefore(node.item, node.after ? node.after.nextSibling : node.parent.firstChild);
					}
				}
			}
			
			
		}
	}
/*	if(!item.node.dontFillLast) {
		var last = item.repeat;
		if(last.tagName == 'TD') {
			if(last.parentNode) {
				console.info(last.parentNode.lastChild.style.width);
				last.parentNode.lastChild.style.width = '100%'
				console.info(last, last.parentNode.lastChild)
			} else {
				last.style.width = '100%'
			}
		} else if(last.tagName == 'TR') {
			if(item.repeat.parentNode) {
				last.parentNode.lastChild.firstChild.style.height = '100%' 
			} else {
				last.firstChild.style.height = '100%'
			}
		}
	} else {
	}*/
	return detached
}
// ----------- END OF: PRIVATE



// ----------- LIBS
function onContent(f){//(C)webreflection.blogspot.com
var a=onContent,b=navigator.userAgent,d=document,w=window,c="onContent",e="addEventListener",o="opera",r="readyState",
s="<scr".concat("ipt defer src='//:' on",r,"change='if(this.",r,"==\"complete\"){this.parentNode.removeChild(this);",c,".",c,"()}'></scr","ipt>");
a[c]=(function(o){return function(){a[c]=function(){};for(a=arguments.callee;!a.done;a.done=1)f(o?o():o)}})(a[c]);
if(d[e])d[e]("DOMContentLoaded",a[c],false);
if(/WebKit|Khtml/i.test(b)||(w[o]&&parseInt(w[o].version())<9))(function(){/loaded|complete/.test(d[r])?a[c]():setTimeout(arguments.callee,1)})();
else if(/MSIE/i.test(b))d.write(s);
};

// Code below is ripped shamelessly from prototype.js

/* Based on Alex Arnell's inheritance implementation. */
Object.extend = function(destination, source) {
  for (var property in source)
    destination[property] = source[property];
  return destination;
};
Object.extend(Object, {
  isString: function(object) {
    return typeof object == "string";
  },
  isFunction: function(object) {
    return typeof object == "function";
  }
});
function prototypeDolarFunction(element) {
  if (arguments.length > 1) {
    for (var i = 0, elements = [], length = arguments.length; i < length; i++)
      elements.push(prototypeDolarFunction(arguments[i]));
    return elements;
  }
  if (Object.isString(element))
    element = document.getElementById(element);
  return element;
}
function $A(iterable) {
  if (!iterable) return [];
  if (iterable.toArray) return iterable.toArray();
  var length = iterable.length, results = new Array(length);
  while (length--) results[length] = iterable[length];
  return results;
}
Object.extend(Function.prototype, {
  bind: function() {
    if (arguments.length < 2 && arguments[0] === undefined) return this;
    var __method = this, args = $A(arguments), object = args.shift();
    return function() {
      return __method.apply(object, args.concat($A(arguments)));
    }
  }


});
var BraveLayout_Prototype = {
  Browser: {
    IE:     !!(window.attachEvent && !window.opera),
    Opera:  !!window.opera,
    WebKit: navigator.userAgent.indexOf('AppleWebKit/') > -1,
    Gecko:  navigator.userAgent.indexOf('Gecko') > -1 && navigator.userAgent.indexOf('KHTML') == -1,
    MobileSafari: !!navigator.userAgent.match(/Apple.*Mobile.*Safari/)
  },
  BrowserFeatures: {
    XPath: !!document.evaluate,
    ElementExtensions: !!window.HTMLElement,
    SpecificElementExtensions:
      document.createElement('div').__proto__ &&
      document.createElement('div').__proto__ !==
        document.createElement('form').__proto__
  }
}
if (BraveLayout_Prototype.BrowserFeatures.XPath) {
  document._getElementsByXPath = function(expression, parentElement) {
    var results = [];
    var query = document.evaluate(expression, prototypeDolarFunction(parentElement) || document,
      null, XPathResult.ORDERED_NODE_SNAPSHOT_TYPE, null);
    for (var i = 0, length = query.snapshotLength; i < length; i++)
      results.push(query.snapshotItem(i));
    return results;
  };
}
String.interpret = function(value) {
    return value == null ? '' : String(value);
}
Object.extend(String.prototype, {
  include: function(pattern) {
    return this.indexOf(pattern) > -1;
  },

  startsWith: function(pattern) {
    return this.indexOf(pattern) === 0;
  },

  gsub: function(pattern, replacement) {
    var result = '', source = this, match;
    replacement = arguments.callee.prepareReplacement(replacement);

    while (source.length > 0) {
      if (match = source.match(pattern)) {
        result += source.slice(0, match.index);
        result += String.interpret(replacement(match));
        source  = source.slice(match.index + match[0].length);
      } else {
        result += source, source = '';
      }
    }
    return result;
  },
  scan: function(pattern, iterator) {
    this.gsub(pattern, iterator);
    return String(this);
  },
  strip: function() {
    return this.replace(/^\s+/, '').replace(/\s+$/, '');
  }
});
String.prototype.gsub.prepareReplacement = function(replacement) {
  if (Object.isFunction(replacement)) return replacement;
  var template = new Template(replacement);
  return function(match) { return template.evaluate(match) };
};
function Template(template, pattern) {
    this.template = template.toString();
    this.pattern = pattern || Template.Pattern;
}
Object.extend(Template.prototype, {
  evaluate: function(object) {
    if (Object.isFunction(object.toTemplateReplacements))
      object = object.toTemplateReplacements();

    return this.template.gsub(this.pattern, function(match) {
      if (object == null) return '';

      var before = match[1] || '';
      if (before == '\\') return match[2];

      var ctx = object, expr = match[3];
      var pattern = /^([^.[]+|\[((?:.*?[^\\])?)\])(\.|\[|$)/, match = pattern.exec(expr);
      if (match == null) return before;

      while (match != null) {
        var comp = match[1].startsWith('[') ? match[2].gsub('\\\\]', ']') : match[1];
        ctx = ctx[comp];
        if (null == ctx || '' == match[3]) break;
        expr = expr.substring('[' == match[3] ? match[1].length : match[0].length);
        match = pattern.exec(expr);
      }

      return before + String.interpret(ctx);
    }.bind(this));
  }
});
Template.Pattern = /(^|.|\r|\n)(#\{(.*?)\})/;
function ObjectRange(start, end, exclusive) {
    this.start = start;
    this.end = end;
    this.exclusive = exclusive;
}
Object.extend(ObjectRange.prototype, {
  _each: function(iterator) {
    var value = this.start;
    while (this.include(value)) {
      iterator(value);
      value = value.succ();
    }
  },

  include: function(value) {
    if (value < this.start)
      return false;
    if (this.exclusive)
      return value < this.end;
    return value <= this.end;
  }
});

var $R = function(start, end, exclusive) {
  return new ObjectRange(start, end, exclusive);
};


/* Portions of the Selector class are derived from Jack Slocum�s DomQuery,
 * part of YUI-Ext version 0.40, distributed under the terms of an MIT-style
 * license.  Please see http://www.yui-ext.com/ for more information. */
function Selector(expression) {
    this.expression = expression.strip();
    this.compileMatcher();
}

Object.extend(Selector.prototype, {
  compileMatcher: function() {
    // Selectors with namespaced attributes can't use the XPath version
    if (BraveLayout_Prototype.BrowserFeatures.XPath && !(/(\[[\w-]*?:|:checked)/).test(this.expression))
      return this.compileXPathMatcher();

    var e = this.expression, ps = Selector.patterns, h = Selector.handlers,
        c = Selector.criteria, le, p, m;

    if (Selector._cache[e]) {
      this.matcher = Selector._cache[e];
      return;
    }

    this.matcher = ["this.matcher = function(root) {",
                    "var r = root, h = Selector.handlers, c = false, n;"];

    while (e && le != e && (/\S/).test(e)) {
      le = e;
      for (var i in ps) {
        p = ps[i];
        if (m = e.match(p)) {
          this.matcher.push(Object.isFunction(c[i]) ? c[i](m) :
    	      new Template(c[i]).evaluate(m));
          e = e.replace(m[0], '');
          break;
        }
      }
    }

    this.matcher.push("return h.unique(n);\n}");
    eval(this.matcher.join('\n'));
    Selector._cache[this.expression] = this.matcher;
  },

  compileXPathMatcher: function() {
    var e = this.expression, ps = Selector.patterns,
        x = Selector.xpath, le, m;

    if (Selector._cache[e]) {
      this.xpath = Selector._cache[e]; return;
    }

    this.matcher = ['.//*'];
    while (e && le != e && (/\S/).test(e)) {
      le = e;
      for (var i in ps) {
        if (m = e.match(ps[i])) {
          this.matcher.push(Object.isFunction(x[i]) ? x[i](m) :
            new Template(x[i]).evaluate(m));
          e = e.replace(m[0], '');
          break;
        }
      }
    }

    this.xpath = this.matcher.join('');
    Selector._cache[this.expression] = this.xpath;
  },

  findElements: function(root) {
    root = root || document;
    if (this.xpath) return document._getElementsByXPath(this.xpath, root);
    return this.matcher(root);
  },

  match: function(element) {
    this.tokens = [];

    var e = this.expression, ps = Selector.patterns, as = Selector.assertions;
    var le, p, m;

    while (e && le !== e && (/\S/).test(e)) {
      le = e;
      for (var i in ps) {
        p = ps[i];
        if (m = e.match(p)) {
          // use the Selector.assertions methods unless the selector
          // is too complex.
          if (as[i]) {
            this.tokens.push([i, Object.clone(m)]);
            e = e.replace(m[0], '');
          } else {
            // reluctantly do a document-wide search
            // and look for a match in the array
            return this.findElements(document).include(element);
          }
        }
      }
    }

    var match = true, name, matches;
    for (var i = 0, token; token = this.tokens[i]; i++) {
      name = token[0], matches = token[1];
      if (!Selector.assertions[name](element, matches)) {
        match = false; break;
      }
    }

    return match;
  },

  toString: function() {
    return this.expression;
  },

  inspect: function() {
    return "#<Selector:" + this.expression.inspect() + ">";
  }
});
Object.extend(Element, {
  descendantOf: function(element, ancestor) {
    element = prototypeDolarFunction(element), ancestor = prototypeDolarFunction(ancestor);
    var originalAncestor = ancestor;

    if (element.compareDocumentPosition)
      return (element.compareDocumentPosition(ancestor) & 8) === 8;
      
    if (element.sourceIndex && ancestor.sourceIndex && !BraveLayout_Prototype.Browser.Opera) {
      var e = element.sourceIndex, a = ancestor.sourceIndex,
       nextAncestor = ancestor.nextSibling;
      if (!nextAncestor) {
        do { ancestor = ancestor.parentNode; }
        while (!(nextAncestor = ancestor.nextSibling) && ancestor.parentNode);
      }
      if (nextAncestor && nextAncestor.sourceIndex) return (e > a && e < nextAncestor.sourceIndex);      
    }
    
    while (element = element.parentNode)
      if (element == originalAncestor) return true;
    return false;
  }
});

Object.extend(Selector, {
  
  _cache: { },

  xpath: {
    descendant:   "//*",
    child:        "/*",
    adjacent:     "/following-sibling::*[1]",
    laterSibling: '/following-sibling::*',
    tagName:      function(m) {
      if (m[1] == '*') return '';
      return "[local-name()='" + m[1].toLowerCase() +
             "' or local-name()='" + m[1].toUpperCase() + "']";
    },
    className:    "[contains(concat(' ', @class, ' '), ' #{1} ')]",
    id:           "[@id='#{1}']",
    attrPresence: "[@#{1}]",
    attr: function(m) {
      m[3] = m[5] || m[6];
      return new Template(Selector.xpath.operators[m[2]]).evaluate(m);
    },
    pseudo: function(m) {
      var h = Selector.xpath.pseudos[m[1]];
      if (!h) return '';
      if (Object.isFunction(h)) return h(m);
      return new Template(Selector.xpath.pseudos[m[1]]).evaluate(m);
    },
    operators: {
      '=':  "[@#{1}='#{3}']",
      '!=': "[@#{1}!='#{3}']",
      '^=': "[starts-with(@#{1}, '#{3}')]",
      '$=': "[substring(@#{1}, (string-length(@#{1}) - string-length('#{3}') + 1))='#{3}']",
      '*=': "[contains(@#{1}, '#{3}')]",
      '~=': "[contains(concat(' ', @#{1}, ' '), ' #{3} ')]",
      '|=': "[contains(concat('-', @#{1}, '-'), '-#{3}-')]"
    },
    pseudos: {
      'first-child': '[not(preceding-sibling::*)]',
      'last-child':  '[not(following-sibling::*)]',
      'only-child':  '[not(preceding-sibling::* or following-sibling::*)]',
      'empty':       "[count(*) = 0 and (count(text()) = 0 or translate(text(), ' \t\r\n', '') = '')]",
      'checked':     "[@checked]",
      'disabled':    "[@disabled]",
      'enabled':     "[not(@disabled)]",
      'not': function(m) {
        var e = m[6], p = Selector.patterns,
            x = Selector.xpath, le, m, v;

        var exclusion = [];
        while (e && le != e && (/\S/).test(e)) {
          le = e;
          for (var i in p) {
            if (m = e.match(p[i])) {
              v = Object.isFunction(x[i]) ? x[i](m) : new Template(x[i]).evaluate(m);
              exclusion.push("(" + v.substring(1, v.length - 1) + ")");
              e = e.replace(m[0], '');
              break;
            }
          }
        }
        return "[not(" + exclusion.join(" and ") + ")]";
      },
      'nth-child':      function(m) {
        return Selector.xpath.pseudos.nth("(count(./preceding-sibling::*) + 1) ", m);
      },
      'nth-last-child': function(m) {
        return Selector.xpath.pseudos.nth("(count(./following-sibling::*) + 1) ", m);
      },
      'nth-of-type':    function(m) {
        return Selector.xpath.pseudos.nth("position() ", m);
      },
      'nth-last-of-type': function(m) {
        return Selector.xpath.pseudos.nth("(last() + 1 - position()) ", m);
      },
      'first-of-type':  function(m) {
        m[6] = "1"; return Selector.xpath.pseudos['nth-of-type'](m);
      },
      'last-of-type':   function(m) {
        m[6] = "1"; return Selector.xpath.pseudos['nth-last-of-type'](m);
      },
      'only-of-type':   function(m) {
        var p = Selector.xpath.pseudos; return p['first-of-type'](m) + p['last-of-type'](m);
      },
      nth: function(fragment, m) {
        var mm, formula = m[6], predicate;
        if (formula == 'even') formula = '2n+0';
        if (formula == 'odd')  formula = '2n+1';
        if (mm = formula.match(/^(\d+)$/)) // digit only
          return '[' + fragment + "= " + mm[1] + ']';
        if (mm = formula.match(/^(-?\d*)?n(([+-])(\d+))?/)) { // an+b
          if (mm[1] == "-") mm[1] = -1;
          var a = mm[1] ? Number(mm[1]) : 1;
          var b = mm[2] ? Number(mm[2]) : 0;
          predicate = "[((#{fragment} - #{b}) mod #{a} = 0) and " +
          "((#{fragment} - #{b}) div #{a} >= 0)]";
          return new Template(predicate).evaluate({
            fragment: fragment, a: a, b: b });
        }
      }
    }
  },

  criteria: {
    tagName:      'n = h.tagName(n, r, "#{1}", c);   c = false;',
    className:    'n = h.className(n, r, "#{1}", c); c = false;',
    id:           'n = h.id(n, r, "#{1}", c);        c = false;',
    attrPresence: 'n = h.attrPresence(n, r, "#{1}"); c = false;',
    attr: function(m) {
      m[3] = (m[5] || m[6]);
      return new Template('n = h.attr(n, r, "#{1}", "#{3}", "#{2}"); c = false;').evaluate(m);
    },
    pseudo: function(m) {
      if (m[6]) m[6] = m[6].replace(/"/g, '\\"');
      return new Template('n = h.pseudo(n, "#{1}", "#{6}", r, c); c = false;').evaluate(m);
    },
    descendant:   'c = "descendant";',
    child:        'c = "child";',
    adjacent:     'c = "adjacent";',
    laterSibling: 'c = "laterSibling";'
  },

  patterns: {
    // combinators must be listed first
    // (and descendant needs to be last combinator)
    laterSibling: /^\s*~\s*/,
    child:        /^\s*>\s*/,
    adjacent:     /^\s*\+\s*/,
    descendant:   /^\s/,

    // selectors follow
    tagName:      /^\s*(\*|[\w\-]+)(\b|$)?/,
    id:           /^#([\w\-\*]+)(\b|$)/,
    className:    /^\.([\w\-\*]+)(\b|$)/,
    pseudo:       /^:((first|last|nth|nth-last|only)(-child|-of-type)|empty|checked|(en|dis)abled|not)(\((.*?)\))?(\b|$|(?=\s)|(?=:))/,
    attrPresence: /^\[([\w]+)\]/,
    attr:         /\[((?:[\w-]*:)?[\w-]+)\s*(?:([!^$*~|]?=)\s*((['"])([^\4]*?)\4|([^'"][^\]]*?)))?\]/
  },

  // for Selector.match and Element#match
  assertions: {
    tagName: function(element, matches) {
      return matches[1].toUpperCase() == element.tagName.toUpperCase();
    },

    className: function(element, matches) {
      return Element.hasClassName(element, matches[1]);
    },

    id: function(element, matches) {
      return element.id === matches[1];
    },

    attrPresence: function(element, matches) {
      return Element.hasAttribute(element, matches[1]);
    },

    attr: function(element, matches) {
      var nodeValue = Element.readAttribute(element, matches[1]);
      return Selector.operators[matches[2]](nodeValue, matches[3]);
    }
  },

  handlers: {
    // UTILITY FUNCTIONS
    // joins two collections
    concat: function(a, b) {
      for (var i = 0, node; node = b[i]; i++)
        a.push(node);
      return a;
    },

    // marks an array of nodes for counting
    mark: function(nodes) {
      for (var i = 0, node; node = nodes[i]; i++)
        node._counted = true;
      return nodes;
    },

    unmark: function(nodes) {
      for (var i = 0, node; node = nodes[i]; i++)
        node._counted = undefined;
      return nodes;
    },

    // mark each child node with its position (for nth calls)
    // "ofType" flag indicates whether we're indexing for nth-of-type
    // rather than nth-child
    index: function(parentNode, reverse, ofType) {
      parentNode._counted = true;
      if (reverse) {
        for (var nodes = parentNode.childNodes, i = nodes.length - 1, j = 1; i >= 0; i--) {
          var node = nodes[i];
          if (node.nodeType == 1 && (!ofType || node._counted)) node.nodeIndex = j++;
        }
      } else {
        for (var i = 0, j = 1, nodes = parentNode.childNodes; node = nodes[i]; i++)
          if (node.nodeType == 1 && (!ofType || node._counted)) node.nodeIndex = j++;
      }
    },

    // filters out duplicates 
    unique: function(nodes) {
      if (nodes.length == 0) return nodes;
      var results = [], n;
      for (var i = 0, l = nodes.length; i < l; i++)
        if (!(n = nodes[i])._counted) {
          n._counted = true;
          results.push(n);
        }
      return Selector.handlers.unmark(results);
    },

    // COMBINATOR FUNCTIONS
    descendant: function(nodes) {
      var h = Selector.handlers;
      for (var i = 0, results = [], node; node = nodes[i]; i++)
        h.concat(results, node.getElementsByTagName('*'));
      return results;
    },

    child: function(nodes) {
      var h = Selector.handlers;
      for (var i = 0, results = [], node; node = nodes[i]; i++) {
        for (var j = 0, children = [], child; child = node.childNodes[j]; j++)
          if (child.nodeType == 1 && child.tagName != '!') results.push(child);
      }
      return results;
    },

    adjacent: function(nodes) {
      for (var i = 0, results = [], node; node = nodes[i]; i++) {
        var next = this.nextElementSibling(node);
        if (next) results.push(next);
      }
      return results;
    },

    laterSibling: function(nodes) {
      var h = Selector.handlers;
      for (var i = 0, results = [], node; node = nodes[i]; i++)
        h.concat(results, Element.nextSiblings(node));
      return results;
    },

    nextElementSibling: function(node) {
      while (node = node.nextSibling)
	      if (node.nodeType == 1) return node;
      return null;
    },

    previousElementSibling: function(node) {
      while (node = node.previousSibling)
        if (node.nodeType == 1) return node;
      return null;
    },

    // TOKEN FUNCTIONS
    tagName: function(nodes, root, tagName, combinator) {
      tagName = tagName.toUpperCase();
      var results = [], h = Selector.handlers;
      if (nodes) {
        if (combinator) {
          // fastlane for ordinary descendant combinators
          if (combinator == "descendant") {
            for (var i = 0, node; node = nodes[i]; i++)
              h.concat(results, node.getElementsByTagName(tagName));
            return results;
          } else nodes = this[combinator](nodes);
          if (tagName == "*") return nodes;
        }
        for (var i = 0, node; node = nodes[i]; i++)
          if (node.tagName.toUpperCase() == tagName) results.push(node);
        return results;
      } else return root.getElementsByTagName(tagName);
    },

    id: function(nodes, root, id, combinator) {
      var targetNode = prototypeDolarFunction(id), h = Selector.handlers;
      if (!targetNode) return [];
      if (!nodes && root == document) return [targetNode];
      if (nodes) {
        if (combinator) {
          if (combinator == 'child') {
            for (var i = 0, node; node = nodes[i]; i++)
              if (targetNode.parentNode == node) return [targetNode];
          } else if (combinator == 'descendant') {
            for (var i = 0, node; node = nodes[i]; i++) {
              if (Element.descendantOf(targetNode, node)) return [targetNode];
            }
          } else if (combinator == 'adjacent') {
            for (var i = 0, node; node = nodes[i]; i++)
              if (Selector.handlers.previousElementSibling(targetNode) == node)
                return [targetNode];
          } else nodes = h[combinator](nodes);
        }
        for (var i = 0, node; node = nodes[i]; i++)
          if (node == targetNode) return [targetNode];
        return [];
      }
      return (targetNode && Element.descendantOf(targetNode, root)) ? [targetNode] : [];
    },

    className: function(nodes, root, className, combinator) {
      if (nodes && combinator) nodes = this[combinator](nodes);
      return Selector.handlers.byClassName(nodes, root, className);
    },

    byClassName: function(nodes, root, className) {
      if (!nodes) nodes = Selector.handlers.descendant([root]);
      var needle = ' ' + className + ' ';
      for (var i = 0, results = [], node, nodeClassName; node = nodes[i]; i++) {
        nodeClassName = node.className;
        if (nodeClassName.length == 0) continue;
        if (nodeClassName == className || (' ' + nodeClassName + ' ').include(needle))
          results.push(node);
      }
      return results;
    },

    attrPresence: function(nodes, root, attr) {
      if (!nodes) nodes = root.getElementsByTagName("*");
      var results = [];
      for (var i = 0, node; node = nodes[i]; i++)
        if (Element.hasAttribute(node, attr)) results.push(node);
      return results;
    },

    attr: function(nodes, root, attr, value, operator) {
      if (!nodes) nodes = root.getElementsByTagName("*");
      var handler = Selector.operators[operator], results = [];
      for (var i = 0, node; node = nodes[i]; i++) {
        var nodeValue = Element.readAttribute(node, attr);
        if (nodeValue === null) continue;
        if (handler(nodeValue, value)) results.push(node);
      }
      return results;
    },

    pseudo: function(nodes, name, value, root, combinator) {
      if (nodes && combinator) nodes = this[combinator](nodes);
      if (!nodes) nodes = root.getElementsByTagName("*");
      return Selector.pseudos[name](nodes, value, root);
    }
  },

  pseudos: {
    'first-child': function(nodes, value, root) {
      for (var i = 0, results = [], node; node = nodes[i]; i++) {
        if (Selector.handlers.previousElementSibling(node)) continue;
          results.push(node);
      }
      return results;
    },
    'last-child': function(nodes, value, root) {
      for (var i = 0, results = [], node; node = nodes[i]; i++) {
        if (Selector.handlers.nextElementSibling(node)) continue;
          results.push(node);
      }
      return results;
    },
    'only-child': function(nodes, value, root) {
      var h = Selector.handlers;
      for (var i = 0, results = [], node; node = nodes[i]; i++)
        if (!h.previousElementSibling(node) && !h.nextElementSibling(node))
          results.push(node);
      return results;
    },
    'nth-child':        function(nodes, formula, root) {
      return Selector.pseudos.nth(nodes, formula, root);
    },
    'nth-last-child':   function(nodes, formula, root) {
      return Selector.pseudos.nth(nodes, formula, root, true);
    },
    'nth-of-type':      function(nodes, formula, root) {
      return Selector.pseudos.nth(nodes, formula, root, false, true);
    },
    'nth-last-of-type': function(nodes, formula, root) {
      return Selector.pseudos.nth(nodes, formula, root, true, true);
    },
    'first-of-type':    function(nodes, formula, root) {
      return Selector.pseudos.nth(nodes, "1", root, false, true);
    },
    'last-of-type':     function(nodes, formula, root) {
      return Selector.pseudos.nth(nodes, "1", root, true, true);
    },
    'only-of-type':     function(nodes, formula, root) {
      var p = Selector.pseudos;
      return p['last-of-type'](p['first-of-type'](nodes, formula, root), formula, root);
    },

    // handles the an+b logic
    getIndices: function(a, b, total) {
      if (a == 0) return b > 0 ? [b] : [];
      return $R(1, total).inject([], function(memo, i) {
        if (0 == (i - b) % a && (i - b) / a >= 0) memo.push(i);
        return memo;
      });
    },

    // handles nth(-last)-child, nth(-last)-of-type, and (first|last)-of-type
    nth: function(nodes, formula, root, reverse, ofType) {
      if (nodes.length == 0) return [];
      if (formula == 'even') formula = '2n+0';
      if (formula == 'odd')  formula = '2n+1';
      var h = Selector.handlers, results = [], indexed = [], m;
      h.mark(nodes);
      for (var i = 0, node; node = nodes[i]; i++) {
        if (!node.parentNode._counted) {
          h.index(node.parentNode, reverse, ofType);
          indexed.push(node.parentNode);
        }
      }
      if (formula.match(/^\d+$/)) { // just a number
        formula = Number(formula);
        for (var i = 0, node; node = nodes[i]; i++)
          if (node.nodeIndex == formula) results.push(node);
      } else if (m = formula.match(/^(-?\d*)?n(([+-])(\d+))?/)) { // an+b
        if (m[1] == "-") m[1] = -1;
        var a = m[1] ? Number(m[1]) : 1;
        var b = m[2] ? Number(m[2]) : 0;
        var indices = Selector.pseudos.getIndices(a, b, nodes.length);
        for (var i = 0, node, l = indices.length; node = nodes[i]; i++) {
          for (var j = 0; j < l; j++)
            if (node.nodeIndex == indices[j]) results.push(node);
        }
      }
      h.unmark(nodes);
      h.unmark(indexed);
      return results;
    },

    'empty': function(nodes, value, root) {
      for (var i = 0, results = [], node; node = nodes[i]; i++) {
        // IE treats comments as element nodes
        if (node.tagName == '!' || (node.firstChild && !node.innerHTML.match(/^\s*$/))) continue;
        results.push(node);
      }
      return results;
    },

    'not': function(nodes, selector, root) {
      var h = Selector.handlers, selectorType, m;
      var exclusions = new Selector(selector).findElements(root);
      h.mark(exclusions);
      for (var i = 0, results = [], node; node = nodes[i]; i++)
        if (!node._counted) results.push(node);
      h.unmark(exclusions);
      return results;
    },

    'enabled': function(nodes, value, root) {
      for (var i = 0, results = [], node; node = nodes[i]; i++)
        if (!node.disabled) results.push(node);
      return results;
    },

    'disabled': function(nodes, value, root) {
      for (var i = 0, results = [], node; node = nodes[i]; i++)
        if (node.disabled) results.push(node);
      return results;
    },

    'checked': function(nodes, value, root) {
      for (var i = 0, results = [], node; node = nodes[i]; i++)
        if (node.checked) results.push(node);
      return results;
    }
  },

  operators: {
    '=':  function(nv, v) { return nv == v; },
    '!=': function(nv, v) { return nv != v; },
    '^=': function(nv, v) { return nv.startsWith(v); },
    '$=': function(nv, v) { return nv.endsWith(v); },
    '*=': function(nv, v) { return nv.include(v); },
    '~=': function(nv, v) { return (' ' + nv + ' ').include(' ' + v + ' '); },
    '|=': function(nv, v) { return ('-' + nv.toUpperCase() + '-').include('-' + v.toUpperCase() + '-'); }
  },

  matchElements: function(elements, expression) {
    var matches = new Selector(expression).findElements(), h = Selector.handlers;
    h.mark(matches);
    for (var i = 0, results = [], element; element = elements[i]; i++)
      if (element._counted) results.push(element);
    h.unmark(matches);
    return results;
  },

  findElement: function(elements, expression, index) {
    if (Object.isNumber(expression)) {
      index = expression; expression = false;
    }
    return Selector.matchElements(elements, expression || '*')[index || 0];
  },

  findChildElements: function(element, expressions) {
    var exprs = expressions.join(','), expressions = [];
    exprs.scan(/(([\w#:.~>+()\s-]+|\*|\[.*?\])+)\s*(,|$)/, function(m) {
      expressions.push(m[1].strip());
    });
    var results = [], h = Selector.handlers;
    for (var i = 0, l = expressions.length, selector; i < l; i++) {
      selector = new Selector(expressions[i].strip());
      h.concat(results, selector.findElements(element));
    }
    return (l > 1) ? h.unique(results) : results;
  }
});
// ----------- END OF: LIBS