/*
 * range.js
 *
 * Requires domutil.js 
 *
 * Support for different kinds of text range (including the W3C Range object
 * and the TextRange object in IE)
 *
 * Marginalia has been developed with funding and support from
 * BC Campus, Simon Fraser University, and the Government of
 * Canada, the UNDESA Africa i-Parliaments Action Plan, and  
 * units and individuals within those organizations.  Many 
 * thanks to all of them.  See CREDITS.html for details.
 * Copyright (C) 2005-2007 Geoffrey Glass; the United Nations
 * http://www.geof.net/code/annotation
 * 
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 *
 * $Id: ranges.js 366 2008-12-09 09:48:27Z geof.glass $
 */
function getTextRangeLength(a,b){var c=a.startContainer;if(b(c))c=walkNextNode(c,b);var d=0;while(null!=c){if(TEXT_NODE==c.nodeType){if(c==a.startContainer&&c==a.endContainer)return a.endOffset-a.startOffset;else if(c==a.startContainer)d=c.length-a.startOffset;else if(c==a.endContainer)return d+a.endOffset}c=walkNextNode(c,b)}return-1}function getTextRangeContent(a,b){var c;if(a.startContainer==a.endContainer)c=a.startContainer.nodeValue.substring(a.startOffset,a.endOffset);else{c=a.startContainer.nodeValue.substring(a.startOffset,a.startContainer.length);var d=new DOMWalker(a.startContainer);d.walk();while(null!=d.node&&d.node!=a.endContainer){if(TEXT_NODE==d.node.nodeType)c+=d.node.nodeValue;else if(ELEMENT_NODE==d.node.nodeType&&domutil.isBreakingElement(d.node.tagName))c+=" ";d.walk(!b(d.node))}c+=a.endContainer.nodeValue.substring(0,a.endOffset);d.destroy()}c=c.replace(/(\s|\u00a0)\s*/g,"$1");c=c.replace(/(\s|\u00a0)$/,"");c=c.replace(/^(\s|\u00a0)/,"");return c}function NormalizedRange(a,b,c){var d=new Object;d.container=b;d.offset=getContentOffset(b,a.startContainer,a.startOffset,c);d.length=getContentOffset(b,a.endContainer,a.endOffset,c)-d.offset;return d}function getSelectionRangeIE(a){if(document.selection.type=="None")return null;var b=new Object;var c=document.selection.createRange();var d=c.text.length;var e=c.text.replace(/(\s|\u00a0)/g,"").length;c.moveEnd("character",1-d);var f=c.htmlText;c.pasteHTML('<span id="rangeStart"></span>'+f);var g=document.getElementById("rangeStart");if(g.previousSibling){b.startContainer=g.previousSibling;b.startOffset=getContentOffset(b.startContainer,g,0,null)}else{b.startContainer=g.parentNode;b.startOffset=0}if(f.substr(0,1)==" ")g.parentNode.insertBefore(document.createTextNode(" "),g);g.parentNode.removeChild(g);domutil.portableNormalize(g.parentNode);var h;if(TEXT_NODE!=b.startContainer.nodeType){h=new DOMWalker(b.startContainer);while(null!=h.node&&TEXT_NODE!=h.node.nodeType)h.walk(!a||!a(h.node));b.startContainer=h.node}var i=e;h=new DOMWalker(b.startContainer);while(null!=h.node&&i>0){if(TEXT_NODE==h.node.nodeType){var j=h.node.nodeValue.replace(/\s/g," ");j=j.replace(/\u00a0/g," ");var k=h.node==b.startContainer?b.startOffset:0;while(k<j.length){if(" "!=j.charAt(k))--i;if(0==i){b.endContainer=h.node;b.endOffset=k+1;break}++k}}h.walk(!a||!a(h.node))}return b}function getPortableSelectionRange(){var a;if(window.getSelection){var b=window.getSelection();if(null==b.rangeCount||0==b.rangeCount)return null;return b.getRangeAt(0)}else if(document.selection){return getSelectionRangeIE();if(null==a)return null}else return null}function getContentOffset(a,b,c,d){var e=0;var f=a;while(f!=b&&f!=null){if(TEXT_NODE==f.nodeType||CDATA_SECTION_NODE==f.nodeType)e+=f.length;f=domutil.walkNextNode(f,d)}if(null==f)return 0;if(TEXT_NODE==f.nodeType||CDATA_SECTION_NODE==f.nodeType){return e+c}else{f=f.firstChild;for(var g=0;g<c;++g){if(null==f)debug("Error in getContentOffset:  invalid element offset");e+=domutil.nodeTextLength(f);f=f.nextSibling}return e}}function WordOffsetToCharOffset(a,b,c,d){if(d){if(" "!=a.charAt(c))c=a.indexOf(" ",c)}while(true){while(" "==a.charAt(c)&&c<a.length)++c;if(a.length==c)return a.length;if(b==1)return c;--b;c=a.indexOf(" ",c);if(-1==c)return a.length}}function WordPointWalker(a,b){this.walker=new DOMWalker(a);this.fskip=b;this.targetRel=null;this.targetWord=0;this.targetChar=0;this.currNode=a;this.currChars=0;this.inTargetRel=false;this.inTargetWord=false;this.targetWords=0;this.targetWordChar=0;this.inWord=false;this.endTag=false;this.atNodeEnd=false;this.eof=false;trace("WordPointWalker","WordPointWalker INIT");return this}function wordPointToNodePoint(a,b,c){var d=b.resolveLines();var e=new WordPointWalker(d,c);if(!e.walkToTarget(b.resolveLines(),b.words,b.chars)){trace("word-range","Unable to find point "+b.toString(document.documentElement));return null}return new NodePoint(e.currNode,e.currChars)}function NodePoint(a,b){this.container=a;this.offset=b;return this}function NodeToWordPoint_Machine(a,b,c,d){this.targetContainer=a;this.targetOffset=b;this.fallForward=d;this.container=c;this.words=0;this.chars=0;this.state=STATE_SPACE;this.offset=0;return this}function RecurseOnElement(a,b,c){if(null==b)throw"RecurseOnElement: node is null";if(ELEMENT_NODE==b.nodeType&&(null==c||!c(b))){var d=a.startElement(b);if(STATE_DONE==a.state)return true;if(d){for(var e=b.firstChild;null!=e;e=e.nextSibling){RecurseOnElement(a,e,c);if(STATE_DONE==a.state)return true}a.endElement(b)}if(STATE_DONE==a.state)return true}else if(TEXT_NODE==b.nodeType||CDATA_SECTION_NODE==b.nodeType){a.text(b);if(STATE_DONE==a.state)return true}return false}function WordRange(a,b){this.start=a;this.end=b}function WordPoint(a,b,c,d){this.rel=a;this.lines=b;this.words=c;this.chars=d;this.lineNode=null;return this}function TextRange(a,b,c,d){this.startContainer=a;this.startOffset=b;this.endContainer=c;this.endOffset=d}STATE_SPACE=0;STATE_WORD=1;STATE_TARGET_SPACE=2;STATE_TARGET_WORD=3;STATE_FALL_FORWARD=4;STATE_DONE=5;TextRange.fromW3C=function(a){return new TextRange(a.startContainer,a.startOffset,a.endContainer,a.endOffset)};TextRange.prototype.shrinkwrap=function(a){var b=this.startContainer;var c=this.startOffset;var d=this.endContainer;var e=this.endOffset;var f=b;if(TEXT_NODE!=f.nodeType&&c>0)f=f.childNodes.item(c);var g=false;var h=new DOMWalker(f);do{var f=h.node;if(f==d)g=true;else if(g)return null;if((!a||!a(f))&&TEXT_NODE==f.nodeType){if(!f.nodeValue.match(/^(\s|\u00a0)*$/)){if(f!=b){b=f;c=0}break}}}while(h.walk(!a||!a(f)));var f=d;if(TEXT_NODE!=d.nodeType&&e>0)f=f.childNodes.item(e);var g=false;var h=new DOMWalker(f,true);if(f==d&&e==0)h.walk();do{var f=h.node;if(f==b)g=true;else if(g)return false;if((!a||!a(f))&&TEXT_NODE==f.nodeType){var i=f.nodeValue.match(/^(\s|\u00a0)*/);var j=i[1]?i[1].length:0;if(j!=f.nodeValue.length){if(f==d){if(j<e)break}else{d=h.node;e=f.nodeValue.length;break}}}}while(h.walk(!a||!a(f),true));return new TextRange(b,c,d,e)};TextRange.fromWordRange=function(a,b){trace("word-range","wordRangeToTextRange");var c=a.start.resolveLines();var d=new WordPointWalker(c,b);if(!d.walkToTarget(c,a.start.words,a.start.chars)){trace("word-range","Unable to find point ");throw"Unable to find point"}var e=new NodePoint(d.currNode,d.currChars);c=a.end.resolveLines();trace(null,"lineNode(end): "+c.tagName+"#"+c.id);if(!d.walkToTarget(c,a.end.words,a.end.chars)){trace("word-range","Unable to find point ");throw"Unable to find point"}var f=new NodePoint(d.currNode,d.currChars);var g=new TextRange(e.container,e.offset,f.container,f.offset);d.destroy();d=null;e.destroy();e=null;f.destroy();f=null;return g};TextRange.prototype.destroy=function(){this.startContainer=null;this.endContainer=null};WordPoint.countLines=function(a,b){if(ELEMENT_NODE==b.nodeType&&domutil.isBlockElement(b.tagName))return[b,1];var c=1;var d=null;var e=a;var f=0;var g=new DOMWalker(b);while(g.walk(true,true)){if(g.node==a)break;else if(ELEMENT_NODE==g.node.nodeType){if(g.startTag&&domutil.isBlockElement(g.node.tagName)){var h=true;for(var i=g.node;i&&i!=a;i=i.parentNode){if(!domutil.isBlockElement(i.tagName)){h=false;break}}if(h){e=g.node;break}}else if(g.startTag&&"br"==g.node.tagName.toLowerCase()){if(null==d)d=g.node;c+=1}}}return{block:e,line:d?d:e,count:c}};WordPoint.prototype.countLines=function(a){return WordPoint.countLines(this.rel)};WordPoint.prototype.resolveLines=function(){var a=this.rel;var b=this.lines;if(true||!this.lineNode){if(!b||1==b)this.lineNode=a;else if(a.ownerDocument.evaluate){var c=domutil.isXhtml(a.ownerDocument)?"(descendant::html:br | following::html:br)["+(b-1)+"]":"(descendant::br | following::br)["+(b-1)+"]";var d=a.ownerDocument.evaluate(c,a,domutil.nsPrefixResolver,XPathResult.ANY_TYPE,null);this.lineNode=d.iterateNext()}else{var e=a;var f=new DOMWalker(a);do{if(b==1)break;else if(ELEMENT_NODE==f.node.nodeType&&"br"==f.node.tagName.toLowerCase())b-=1}while(f.walk(true));this.lineNode=f.node}}return this.lineNode};WordPoint.prototype.toSequencePoint=function(a){return SequencePoint.fromNode(a,this.rel,this.lines,this.words,this.chars)};WordPoint.fromSequencePoint=function(a,b,c){var d=a.getReferenceElement(b,c);return d==null?null:new WordPoint(d,a.lines,a.words,a.chars)};WordPoint.prototype.toXPathPoint=function(a){return XPathPoint.fromNode(a,this.rel,this.lines,this.words,this.chars)};WordPoint.fromXPathPoint=function(a,b,c){var d=a.getReferenceElement(b,c);return d==null?null:new WordPoint(d,a.lines,a.words,a.chars)};WordPoint.prototype.equals=function(a){return this.rel==a.rel&&this.lines==a.lines&&this.words==a.words&&this.chars==a.chars};WordPoint.prototype.destroy=function(){delete this.root;this.rel=null};WordRange.fromTextRange=function(a,b,c){var d=WordPoint.fromNodePoint(a.startContainer,a.startOffset,b,true,c);var e=WordPoint.fromNodePoint(a.endContainer,a.endOffset,b,false,c);if(null==d||null==e){if(d)d.destroy();if(e)e.destroy();throw"WordRange.fromTextRange failed"}return new WordRange(d,e)};WordRange.prototype.toSequenceRange=function(a){var b=this.start.toSequencePoint(a);var c=this.end.toSequencePoint(a);return b&&c?new SequenceRange(b,c):null};WordRange.fromSequenceRange=function(a,b,c){var d=WordPoint.fromSequencePoint(a.start,b,c);var e=WordPoint.fromSequencePoint(a.end,b,c);return d&&e?new WordRange(d,e):null};WordRange.prototype.toXPathRange=function(a){var b=new XPathRange(this.start.toXPathPoint(a),this.end.toXPathPoint(a));return b};WordRange.fromXPathRange=function(a,b,c){var d=WordPoint.fromXPathPoint(a.start,b,c);var e=WordPoint.fromXPathPoint(a.end,b,c);return d&&e?new WordRange(d,e):null};WordRange.prototype.partition=function(a){var b=this.start.resolveLines();var c=new WordPointWalker(b,a);var d=this.start.resolveLines();trace(null,"Partition from "+d.tagName+(d.id?"#"+d.id:"")+" "+this.start.words+" "+this.start.chars);c.walkToTarget(d,this.start.words,this.start.chars);var e=c.currChars;var f=c.currNode;trace(null,"initialOffset="+e);var g=new Array;d=this.end.resolveLines();trace(null,"-> partition to "+d.tagName+(d.id?"#"+d.id:"")+" "+this.end.words+" "+this.end.chars);c.setTarget(d,this.end.words,this.end.chars);var h=0;var i=false;var j="";while(!i){i=c.walk();if(0==h){g[h]=new TextRange(c.currNode,e,c.currNode,c.currChars);var k=c.currNode.nodeValue;j+=k.substring(e,c.currChars);trace(null,"Current node text: "+k);trace(null,"Add text: "+k.substring(e,c.currChars)+" ("+e+" + "+c.currChars+")")}else{g[h]=new TextRange(c.currNode,0,c.currNode,c.currChars);var k=c.currNode.nodeValue;j+=(c.breakBefore?" ":"")+k.substring(0,c.currChars);trace(null,"Current node text: "+k);trace(null,"Add text: "+k.substring(0,c.currChars)+" (0+ "+c.currChars+")")}h+=1}c.destroy();j=j.replace(/(\s|\u00a0)+/g," ");return{quote:j,ranges:g}};WordRange.prototype.equals=function(a){return this.start.equals(a.start)&&this.end.equals(a.end)};WordRange.prototype.destroy=function(){if(null!=this.start)this.start.destroy();if(null!=this.end)this.end.destroy()};WordPoint.fromNodePoint=function(a,b,c,d,e){trace("word-range","WordPoint.fromNodePoint( "+a+","+b+")");var f=WordPoint.countLines(c,a);var g=new NodeToWordPoint_Machine(a,b,f.line,d);RecurseOnElement(g,f.line,e);var h=f.line;while(STATE_DONE!=g.state){while(!h.nextSibling)h=h.parentNode;if(null==h){g.destroy();return null}h=h.nextSibling;RecurseOnElement(g,h,e)}g.destroy();return new WordPoint(f.block,f.count,g.words,g.chars)};NodeToWordPoint_Machine.prototype.trace=function(a){trace("word-range","State "+this.state+" at "+this.words+"."+this.chars+" ("+this.offset+' offset) input "'+a+'"')};NodeToWordPoint_Machine.prototype.destroy=function(){this.targetContainer=null;this.container=null};NodeToWordPoint_Machine.prototype.startElement=NodeToWordPoint_Machine.prototype.endElement=function(a){this.trace("<"+a.tagName+">");if(domutil.isBreakingElement(a.tagName)){if(STATE_WORD==this.state)this.state=STATE_SPACE;else if(STATE_FALL_FORWARD==this.state){this.state=STATE_DONE;return false}}return true};NodeToWordPoint_Machine.prototype.text=function(a){if(a==this.targetContainer||STATE_TARGET_WORD==this.state||STATE_TARGET_SPACE==this.state){if(0==this.targetOffset){if(this.fallForward){if(STATE_SPACE==this.state||STATE_TARGET_SPACE==this.state){this.words+=1;this.chars=0;this.state=STATE_DONE;return}else this.state=STATE_FALL_FORWARD}else{this.state=STATE_DONE;return}}else{if(STATE_SPACE==this.state)this.state=STATE_TARGET_SPACE;else if(STATE_WORD==this.state)this.state=STATE_TARGET_WORD}trace("word-range","In container, state "+this.state+" at "+this.words+"."+this.chars+" looking for offset "+this.targetOffset)}var b=a.nodeValue.replace(/(\s|\u00a0)/g," ");trace("word-range","Searching in:\n"+b);for(var c=0;c<b.length;++c){var d=b.charAt(c);this.trace(d);if(STATE_SPACE==this.state){if(" "!=d){this.chars=1;this.words+=1;this.state=STATE_WORD}}else if(STATE_WORD==this.state){if(" "==d)this.state=STATE_SPACE;else{var e=b.indexOf(" ",c);if(-1==e)this.chars+=1;else{c=e;this.chars+=e-c;this.state=STATE_SPACE}}}else if(STATE_TARGET_SPACE==this.state){if(" "!=d){this.chars=1;this.words+=1;this.state=STATE_TARGET_WORD;trace("word-range","TARGET_SPACE -> TARGET_WORD, offset="+(this.offset+1))}this.offset+=1;if(this.offset==this.targetOffset){if(this.fallForward){if(this.state==STATE_TARGET_SPACE){this.words+=1;this.chars=0;this.state=STATE_DONE;return}else this.state=STATE_FALL_FORWARD}else{this.state=STATE_DONE;return}}}else if(STATE_TARGET_WORD==this.state){this.offset+=1;if(" "==d)this.state=STATE_TARGET_SPACE;else this.chars+=1;if(this.offset==this.targetOffset){if(this.fallForward){if(" "==d){this.words+=1;this.chars=0;this.state=STATE_DONE;return}else this.state=STATE_FALL_FORWARD}else{trace("word-range","Success at "+this.words+"."+this.chars);this.state=STATE_DONE;return}}}else if(STATE_FALL_FORWARD==this.state){if(" "==d){this.words+=1;this.chars=0}trace("word-range","Success: fall forward to "+this.words+"."+this.chars);this.state=STATE_DONE;return}}if(a==this.targetContainer&&this.fallForward&&this.offset==this.targetOffset)this.state=STATE_FALL_FORWARD;return};NodePoint.prototype.destroy=function(){this.container=null};WordPointWalker.prototype.setTarget=function(a,b,c){trace("WordPointWalker"," WordPointWalker setTarget("+a.tagName+(a.id?"#"+a.id:"")+", "+b+", "+c+")");if(this.currNode==a||a==this.targetRel){this.inTargetRel=true;if(this.targetWords==b){trace("WordPointWalker"," WordPointWalker - start in target word");this.inTargetWord=true}else{trace("WordPointWalker"," WordPointWalker - start in target node ("+this.targetWords+" != "+b+")");this.inTargetWord=false;this.targetWordChar=0}}else{this.inTargetRel=false;this.targetWords=this.targetWordChar=0}this.targetRel=a;this.targetWord=b;this.targetChar=c};WordPointWalker.prototype.walkToTarget=function(a,b,c){this.setTarget(a,b,c);while(!this.walk());return!this.eof};WordPointWalker.prototype.walk=function(){this.breakBefore=false;while(true){if(this.atNodeEnd){if(this.fskip?!this.walker.walk(!this.fskip(this.walker.node)):!this.walker.walk(true)){this.eof=true;trace("WordPointWalker"," WordWalker DONE(1)");return true}this.currNode=this.walker.node;this.endTag=this.walker.endTag;this.currChars=0;this.atNodeEnd=false;if(this.currNode==this.targetRel){this.inTargetRel=true;if(!this.walker.endTag)this.targetWords=0}if(ELEMENT_NODE==this.currNode.nodeType&&domutil.isBreakingElement(this.currNode.tagName))this.breakBefore=true;trace("WordPointWalker"," WordPointWalker in <"+this.currNode.tagName+">"+(this.currNode==this.targetRel&&!this.endTag?" (target rel)":""))}if(this.inTargetRel){if(TEXT_NODE==this.currNode.nodeType){var a=this.currNode.nodeValue.replace(/(\s|\u00a0)/g," ");if(this.inWord){if(this.inTargetWord){if(a.length-this.currChars>=this.targetChar-this.targetWordChars){this.currChars+=this.targetChar-this.targetWordChars;this.targetWordChars=this.targetChar;trace("WordPointWalker"," WordWalker DONE(2) at "+this.targetWords+"/"+this.currChars);return true}else{this.targetWordChars+=a.length-this.currChars;this.currChars=a.length;this.atNodeEnd=true;trace("WordPointWalker"," WordWalker node end(3) at "+this.targetWords+"/"+this.currChars);return false}}else{if(" "!=a.charAt(this.currChars)){var b=a.indexOf(" ",this.currChars);if(-1==b){this.currChars=a.length;this.atNodeEnd=true;trace("WordPointWalker"," WordWalker node end(4) at "+this.targetWords+"/"+this.currChars);return false}else this.currChars=b}this.inWord=false}}else this.currChars=0;while(true){while(" "==a.charAt(this.currChars)&&this.currChars<a.length)++this.currChars;this.inWord=false;if(a.length==this.currChars){this.atNodeEnd=true;trace("WordPointWalker"," WordWalker node end(5) at "+this.targetWords+"/"+this.currChars);return false}++this.targetWords;this.inWord=true;if(this.targetWords==this.targetWord){if(a.length-this.currChars>=this.targetChar){this.targetWordChars=this.targetChar;this.currChars+=this.targetChar;trace("WordPointWalker"," WordWalker DONE(6) at "+this.targetWords+"/"+this.currChars);return true}else{this.targetWordChars=a.length-this.currChars;this.currChars+=this.targetWordChars;this.inTargetWord=true;this.atNodeEnd=true;trace("WordPointWalker"," WordWalker node end(7) at "+this.targetWords+"/"+this.currChars);return false}}var c=a.indexOf(" ",this.currChars);if(-1==c){this.inWord=true;this.atNodeEnd=true;this.currChars=a.length;trace("WordPointWalker"," WordPointWalker node end(8) at "+this.targetWords+"/"+this.currChars);return false}else{this.currChars=c;this.inWord=false}}}else if(ELEMENT_NODE==this.currNode.nodeType){if(domutil.isBreakingElement(this.currNode.tagName)){this.inWord=false;this.breakBefore=true}this.atNodeEnd=true}}else{trace("WordPointWalker"," WordPointWalker - still looking for target node");this.atNodeEnd=true;if(TEXT_NODE==this.currNode.nodeType){var a=this.currNode.nodeValue.replace(/(\s|\u00a0)/g," ");this.currChars=a.length;trace("WordPointWalker"," WordPointWalker node end(9)");return false}}}};WordPointWalker.prototype.destroy=function(){this.currNode=null;this.walker.destroy();this.walker=null}