source: gs3-extensions/seaweed-debug/trunk/src/Cursor.js@ 25160

Last change on this file since 25160 was 25160, checked in by sjm84, 12 years ago

Initial cut at a version of seaweed for debugging purposes. Check it out live into the web/ext folder
File size: 83.7 KB
Line 
1/*
2 * file: Cursor.js
3 *
4 * @BEGINLICENSE
5 * Copyright 2010 Brook Novak (email : [email protected])
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
17 * @ENDLICENSE
18 */
19bootstrap.provides("Cursor");
20
21(function(){
22
23 // TODO: REFACTOR de.cursor ro de.Cursor ... do when refactor de prefix to chosen name
24
25 /* A cursor descriptor that represents the current cursor that is showing. Null if no cursor showing */
26 var currentCursorDesc,
27
28 /* The visual representation for the cursor on the actual web page */
29 cursorDiv,
30
31 /* A Constant defining the time in ms between cursor blinks */
32 CURSOR_BLINK_MS_TIME = 460,
33
34 /* The cursor blinker timeout ID */
35 cursorBlinkTOId,
36
37 /* The x position which the cursor should realign to when moving up/down the content */
38 cursorXAlign,
39
40 /* Used for measurement purposes */
41 measureSpanEl,
42 measureSpanTextNode,
43 measurePreTextNode,
44 measurePostTextNode,
45 measureFullText,
46
47 // ------------- Define lookup maps according to the DirectEdit DOM-based Web Editor Specification 1.0 -------------
48
49 /*
50 * Refer to specification 2.2.2
51 * Elements which the cursor can appear directly before
52 */
53 beforeElements = $createLookupMap("img,table,input,select,button,textarea,object"),
54
55 /*
56 * Refer to specification 2.2.3
57 * Elements which the cursor can appear directly after
58 */
59 afterElements = $createLookupMap("img,table,input,select,button,textarea,object,br");
60
61
62 $enqueueInit("Cursor", function() {
63
64 // Create elements for measurement purposes
65 measureSpanEl = $createElement("span");
66 measureSpanTextNode = document.createTextNode("");
67 measureSpanEl.appendChild(measureSpanTextNode);
68 measurePreTextNode = document.createTextNode("");
69
70 // Create cursor div and add it to the document
71 cursorDiv = $createElement("div");
72 _setClassName(cursorDiv, _PROTECTED_CLASS + " sw-cursor"); // Avoid the cursor from being edited
73 docBody.appendChild(cursorDiv);
74
75 // Set cursor background and z-index to defaults if css sheets don't supply them
76 var cursorStyle = "",
77 cssVal = _getComputedStyle(cursorDiv, 'z-index');
78
79 if (!cssVal || cssVal == "0" || cssVal == "auto");
80 cursorStyle += "z-index:100";
81
82 _setFullStyle(cursorDiv, "position:absolute; width:2px;visibility:hidden;" + cursorStyle);
83
84 // Register to events
85 _addHandler(window, "resize", onWindowResized);
86 _addHandler(document, "keystroke", onKeyStroke);
87
88 // Make as subject
89 _model(de.cursor);
90
91 // Keep cursor in view after actions are executed
92 de.UndoMan.addObserver({
93 onAfterExec : scrollToCursor,
94 onAfterUndo : scrollToCursor,
95 onAfterRedo : scrollToCursor
96 });
97
98 }, "UndoMan");
99
100 /**
101 * @namespace The cursor namespace packages cursor specific operations.
102 */
103 de.cursor = {
104
105 /**
106 * @class
107 * Provides flag constants for describing the cursor relation to the dom node.
108 */
109 PlacementFlag : {
110
111 /**
112 * Read Only: Refer to specification 2.2.1. AKA Text nodes (containing least one renderable symbol)
113 * @type Number
114 */
115 INSIDE : 1, // @REPLACE de.cursor.PlacementFlag.INSIDE 1
116
117 /**
118 * Read Only: Refer to specification 2.2.2
119 * @type Number
120 */
121 BEFORE : 2, // @REPLACE de.cursor.PlacementFlag.BEFORE 2
122
123 /**
124 * Read Only: Refer to specification 2.2.3
125 * @type Number
126 */
127 AFTER : 4 // @REPLACE de.cursor.PlacementFlag.AFTER 4
128 },
129
130 /**
131 * @param {Node} domNode a dom node to test
132 * @return {Boolean} True iff the dom node can support a cursor placed by it.
133 */
134 doesNodeSupportCursor : function(domNode) {
135 return !de.doc.isProtectedNode(domNode) && de.doc.isNodeEditable(domNode);
136 },
137
138 /**
139 * Sets the new cursor. The position is updated immediatly.
140 * Set to null to hide/destroy the cursor.
141 *
142 * If the cursor is not in an editable area, then it will be set to null
143 *
144 * @param {de.cursor.CursorDescriptor} cursorDesc The new cursor. Null for no cursor.
145 *
146 * @return {Boolean} True if there is a cursor after the operation. False if the
147 * operation resulted in no cursor.
148 */
149 setCursor: function(cursorDesc){
150
151 // Dissallow cursor placement at protected nodes
152 if (cursorDesc && !this.doesNodeSupportCursor(cursorDesc.domNode))
153 cursorDesc = null;
154
155 // Set the new cursor info
156 currentCursorDesc = cursorDesc;
157
158 // Stop and hide the cursor blink
159 cursorBlink(false);
160
161 // Update cursor GUI
162 if (currentCursorDesc) {
163
164 // Update cursor position
165 cursorDiv.style.left = (currentCursorDesc.docLeft +
166 (currentCursorDesc.isRightOf ? currentCursorDesc.width : 0)) + "px";
167 cursorDiv.style.top = currentCursorDesc.docTop + "px";
168 cursorDiv.style.height = currentCursorDesc.height + "px";
169
170 // Determine color for the cursor.
171 var color = _getComputedStyle(currentCursorDesc.domNode, "color");
172 cursorDiv.style.backgroundColor = color ? color : "black";
173
174 // Begin cursor blink
175 cursorBlink(true);
176 }
177
178 // Always reset cursorXAlign
179 cursorXAlign = null;
180
181 // Notify observers of cursor change
182 this.fireEvent("CursorChanged", this.getCurrentCursorDesc());
183
184 return currentCursorDesc != null;
185
186 },
187
188
189 /**
190 * Discovers the closest matching cursor descriptor for a given position.
191 *
192 * @param {Number} targetX The X coordinate in the window from where to find the closest
193 * cursor position.
194 *
195 * @param {Number} targetY The Y coordinate in the window from where to find the closest
196 * cursor position.
197 *
198 * @param {Node} targetNode (optional) The node at the given position. If not provided this will be determined for you.
199 *
200 * @return {de.cursor.CursorDescriptor} A CursorInfo object containing the closest cursor position
201 * to the given target coordinates. Null if there are no valid nearby
202 * cursor positions.
203 */
204 getCursorDescAtXY: getCursorDescAtXY,
205
206 /**
207 * @return {de.cursor.CursorDescriptor} The clone of the current cursor info object.
208 * Null if there is none.
209 */
210 getCurrentCursorDesc: function(){
211 return currentCursorDesc ? _clone(currentCursorDesc) : null;
212 },
213
214 /**
215 * Updates the cursor GUI.
216 */
217 refreshCursor: function(){
218 if (!currentCursorDesc)
219 return;
220
221 // IE Has this annoying event-threading model where when querrying some
222 // dom objects' properties IE instantly raises an event on the same trace of execution!
223 // This causes a nasty bug when using any of the cursor alrgorithms, this function
224 // is 'randomly' invoked during critical sections which depend on the measuring nodes -
225 // since a resize event is invoked due to querrying various spatial information on dom objects,
226 // such as getting the document.scrollLeft for rereiving a elements absolute position in the window.
227 // Work around:
228 if (measurePostTextNode) return ;
229
230 // Get new position
231 setSpatialMembers(currentCursorDesc);
232
233 // Update the gui
234 cursorDiv.style.left = (currentCursorDesc.docLeft +
235 (currentCursorDesc.isRightOf ? currentCursorDesc.width : 0)) + "px";
236 cursorDiv.style.top = currentCursorDesc.docTop + "px";
237 cursorDiv.style.height = currentCursorDesc.height + "px";
238
239 },
240
241 /**
242 * Scrolls the document to view the current cursor
243 */
244 scrollToCursor : scrollToCursor,
245
246 /**
247 * @return {Boolean} True if the cursor is shown. False if no cursor exists.
248 */
249 exists: function(){
250 return currentCursorDesc != null;
251 },
252
253 /**
254 * @param {Node} node A DOM node to test
255 * @return {Boolean} True if node is the cursor blinker element.
256 */
257 isCursorEle : function (node) {
258 return node == cursorDiv;
259 },
260
261 /**
262 * A wrapper function for _getRenderedNodeAtXY - excludes
263 * @param {Number} x The x pixel coordinate relative to the window.
264 * @param {Number} y The x pixel coordinate relative to the window.
265 * @return {Node} The node at the given window position - gauranteed not to be the cursor blinker.
266 */
267 getNonCursorNodeAtXY : function(x,y) {
268 var dval = cursorDiv.style.display;
269 cursorDiv.style.display = "none"; // Ensure not visible
270 var targetNode = _getRenderedNodeAtXY(x, y);
271 cursorDiv.style.display = dval; // Restore original value
272 return targetNode;
273 },
274
275 /**
276 * Gets the next cursor descriptor before or after a given cursor descriptor. I.E. The next physical
277 * move of the cursor.
278 *
279 * @param {de.cursor.CursorDescriptor} cursorDesc The cursor descriptor to reference from.
280 * it does not have to be a valid cursor descriptor, that is, a
281 * node which the cursor cannot be place in/next to.
282 *
283 * @param {Boolean} left True to get cursor desc left of reference point, false for right.
284 *
285 * @return {de.cursor.CursorDescriptor} The next cursor move from the reference point. Null if there is none.
286 * Note that it might be outside of an editable section.
287 *
288 */
289 getNextCursorMovement : getNextCursorMovement,
290
291 /**
292 * Note: only uses y and height members
293 *
294 * @param {de.cursor.CursorDescriptor} desc1 A cursor to compare
295 *
296 * @param {de.cursor.CursorDescriptor} desc2 A cursor to compare
297 *
298 * @return {Boolean} True iff desc1 and desc2 are on the same line.
299 */
300 isOnSameLine: isOnSameLine,
301
302 /**
303 * Builds a cursor descriptor (provides the spatial information).
304 *
305 * @param {Node} domNode The dom node
306 *
307 * @param {Number} relIndex The index within the dom node (only applies for text nodes)
308 *
309 * @param {Boolean} isRightOf True if the cursor is to the right of index position.
310 *
311 * @return {de.cursor.CursorDescriptor} The cursor descriptor. Null If a cursor cannot be placed at the given position.
312 * Note: if the dom not is a text node but the index is not rendered then null will be returned.
313 *
314 */
315 createCursorDesc: function(domNode, relIndex, isRightOf){
316
317 var placement = getPlacementFlags(domNode);
318
319 if (placement == 0 || (placement != de.cursor.PlacementFlag.INSIDE &&
320 ((isRightOf && !(placement & de.cursor.PlacementFlag.AFTER))
321 || (!isRightOf && !(placement & de.cursor.PlacementFlag.BEFORE)))))
322 return null;
323
324 var desc = {
325 domNode: domNode,
326 relIndex: relIndex,
327 isRightOf: isRightOf,
328 placement: placement
329 };
330
331 setSpatialMembers(desc);
332
333 // If the text node / index is not rendered then return null
334 if (placement == de.cursor.PlacementFlag.INSIDE && (desc.width == 0 || desc.height == 0))
335 return null;
336
337 return desc;
338
339 },
340
341 /**
342 * Note: even if de.cursor.PlacementFlag.INSIDE is returned, the text node may
343 * not be able to support a cursor being placed inside if it contains nothing but
344 * non-renderable symbols.
345 *
346 * @param {Node} node A dom node to get the placement flags for
347 *
348 * @return {Number} A bitwise or combination of de.cursor.PlacementFlag's.
349 * Zero if it is not a candidate for supporting a cursor placement.
350 */
351 getPlacementFlags : getPlacementFlags,
352
353 /**
354 * Gets the nearest cursor descriptor to the given position information.
355 *
356 * @param {Node} domNode A dom node in the document
357 *
358 * @param {Number} relIndex A relative index in the dom node
359 *
360 * @param {Boolean} isRightOf True if the cursor is placed to the right of the node/index.
361 * False for left placement.
362 *
363 * @param {Boolean} searchLeft True to search for nearest cursor to the left of the given position.
364 * False to search right.
365 *
366 * @return {de.cursor.CursorDescriptor} A cursor descriptor nearest to the given position. Null if there is none.
367 */
368 getNearestCursorDesc: function(domNode, relIndex, isRightOf, searchLeft){
369
370 if (_nodeName(domNode) == "br")
371 isRightOf = true;
372
373 var cDesc = de.cursor.createCursorDesc(domNode, relIndex, isRightOf); // Gives null if invalid request
374
375 // Special case: line breaks
376 if (cDesc && _nodeName(domNode) == "br") {
377
378 // Get the cursor pos to the left and right of this line break
379 var leftCDesc = getNextCursorMovement(cDesc, true),
380 rightCDesc = getNextCursorMovement(cDesc, false);
381
382 // If this line break is on its own line then return it
383 if ((!leftCDesc || !isOnSameLine(leftCDesc, cDesc)) && (!rightCDesc || !isOnSameLine(rightCDesc, cDesc)))
384 return cDesc;
385
386 // Otherwise return the cursor pos to the left/right of the break - if it exists
387 return (searchLeft ? leftCDesc : rightCDesc) || cDesc;
388 }
389
390 return cDesc || getNextCursorMovement({
391 domNode: domNode,
392 isRightOf: isRightOf,
393 relIndex: relIndex,
394 y : _getPositionInWindow(domNode).y}, searchLeft);
395
396 } // End getNearestCursorDesc function
397
398 }; // End Cursor Namespace
399
400 /* -------------------------------------------------------------------------------------- */
401 // Events
402 /* -------------------------------------------------------------------------------------- */
403
404 function onKeyStroke(e, normalizedKey) {
405
406 if (!currentCursorDesc || e.ctrlKey || e.metaKey || e.altKey) return;
407
408 var moveAction = 0;
409
410 switch(normalizedKey) {
411 case "Left": // Arrow left
412 case "Right": // Arrow right
413
414 moveAction = 1;
415
416 // Attempt to move the cursor left/right
417 var neighbour = getNextCursorMovement(currentCursorDesc, normalizedKey == "Left");
418
419 // If the neighbour is null, then reached end point
420 if (!neighbour) neighbour = currentCursorDesc;
421
422 var oldCDesc = currentCursorDesc;
423
424 if (!de.cursor.setCursor(neighbour) && oldCDesc)
425 // If failed to set the cursor (probably due to it being outside
426 // of editable section) then set back to the old cursor position
427 de.cursor.setCursor(oldCDesc)
428
429 break;
430
431 case "Up": // Arrow up
432 case "Down": // Arrow down
433
434 moveAction = 1;
435
436 var isUpward = normalizedKey == "Up";
437
438 var docScrollPos = _getDocumentScrollPos();
439
440 var xAlign = cursorXAlign ? cursorXAlign : (currentCursorDesc.docLeft - docScrollPos.left) +
441 (currentCursorDesc.isRightOf ? currentCursorDesc.width : 0);
442
443 var searchSpace = getUpDownSearchSpace();
444 var cDesc;
445
446 if (searchSpace) {
447 // Perform specialized/narrowed dual binary search to discover cursor position directly above/below
448 cDesc = searchBestCursorPos(xAlign, currentCursorDesc.docTop - docScrollPos.top, searchSpace, currentCursorDesc, isUpward);
449 restoreMeasuringNodes();
450 }
451
452 if (!cDesc) cDesc = currentCursorDesc;
453
454 var oldCDesc = currentCursorDesc;
455
456 if (!de.cursor.setCursor(cDesc) && oldCDesc)
457 // If failed to set the cursor (probably due to it being outside
458 // of editable section) then set back to the old cursor position
459 de.cursor.setCursor(oldCDesc)
460
461 // Remember for next up/down movement
462 cursorXAlign = xAlign;
463
464 break;
465
466 } // End case
467
468 if (moveAction) {
469 scrollToCursor(); // Auto scroll
470 return false; // Consume key event
471 }
472
473 return true;
474
475 // Inner support functions to follow
476
477 /**
478 * An inner supporting function.
479 *
480 * @return {Object} The search space for a dual binary search
481 */
482 function getUpDownSearchSpace(){
483
484 // Build array of all nodes to search inside of targetEl
485 var nodesToSearch = [];
486 var pendingBANodes = [];
487 var nextLine;
488
489 _visitAllNodes(docBody, currentCursorDesc.domNode, !isUpward, function(domNode) {
490
491 // Add in any pending before/after nodes
492 appendPendingBAnodes(domNode);
493
494 var placementFlags = getPlacementFlags(domNode);
495
496 if (placementFlags == 0)
497 return true; // Cursor cannot be placed in this node
498
499 // Check to see if found a new line
500 var pos, height;
501 if (domNode.nodeType == Node.TEXT_NODE) {
502 pos = _getPositionInWindow(domNode.parentNode);
503 height = domNode.parentNode.offsetHeight;
504 } else if (_nodeName(domNode) == "br") {
505 pos = measureLineBreak(domNode)
506 height = pos.height;
507 } else {
508 pos = _getPositionInWindow(domNode);
509 height = domNode.offsetHeight;
510 }
511
512 if (!isOnSameLine(nextLine ? nextLine : currentCursorDesc, {y : pos.y, height : height})) {
513 // If already found the next line then the searchspace can end here
514 if (nextLine) return false;
515
516 // If this is the first node that is in the next line, then remeber line information
517 nextLine = {y : pos.y, height : height};
518 }
519
520 if (placementFlags == de.cursor.PlacementFlag.INSIDE) { // AKA a text node
521 nodesToSearch.push({
522 domNode: domNode,
523 placement: de.cursor.PlacementFlag.INSIDE
524 });
525
526 } else { // Before and/or After
527
528 if (placementFlags & de.cursor.PlacementFlag.BEFORE) {
529 if (isUpward) {
530 pendingBANodes.push(domNode);
531 } else {
532 nodesToSearch.push({
533 domNode: domNode,
534 placement: de.cursor.PlacementFlag.BEFORE // Only store before flag
535 });
536 }
537 }
538
539 if (placementFlags & de.cursor.PlacementFlag.AFTER) {
540 if (isUpward) {
541 nodesToSearch.push({
542 domNode: domNode,
543 placement: de.cursor.PlacementFlag.AFTER // Only store before flag
544 });
545 } else {
546 pendingBANodes.push(domNode);
547 }
548 }
549
550 }
551
552 });
553
554 // Was the next line even found?
555 if (!nextLine) return null;
556
557 // Append any pending before/after nodes
558 appendPendingBAnodes(null);
559
560 // Make sure search space is top-down
561 if (isUpward) nodesToSearch.reverse();
562
563 // Suppliment search space with index information
564 var totalPlacementLength = 0;
565 for (var i in nodesToSearch) {
566 var node = nodesToSearch[i];
567 var len = _nodeLength(node.domNode, 1);
568 node.startIndex = totalPlacementLength;
569 node.endIndex = node.startIndex + (len - 1);
570 node.length = len;
571 totalPlacementLength += len;
572 }
573
574 return {
575 nodes: nodesToSearch,
576 totalLength: totalPlacementLength
577 };
578
579 /**
580 * Adds pending before/after nodes to the nodesToSearch
581 * @param {Node} domNode the current dom node or null
582 */
583 function appendPendingBAnodes(domNode){
584
585 while (pendingBANodes.length > 0) {
586
587 if (!domNode || !_isAncestor(pendingBANodes[pendingBANodes.length - 1], domNode)) {
588 nodesToSearch.push({
589 domNode: pendingBANodes.pop(),
590 placement: isUpward ? de.cursor.PlacementFlag.BEFORE : de.cursor.PlacementFlag.AFTER
591 });
592
593 } else
594 break;
595 }
596
597 } // End inner appendPendingBAnodes
598
599 } // End inner getUpDownSearchSpace
600
601
602 } // End onKeyStroke
603
604 /**
605 * If the window resized, the cursor must be re-positioned.
606 *
607 * @param {Event} e
608 */
609 function onWindowResized(e) {
610 de.cursor.refreshCursor();
611 }
612
613
614 /* -------------------------------------------------------------------------------------- */
615 // Support functions for cursor GUI
616 /* -------------------------------------------------------------------------------------- */
617
618 /**
619 * @param {Boolean} visible True to toggle cursor div to visible, false to hidden.
620 */
621 function setCursorVisible(visible) {
622 cursorDiv.style.visibility = visible ? "visible" : "hidden";
623 }
624 /**
625 * @return {Boolean} True if the cursor div is visisble.
626 */
627 function isCursorVisible() {
628 return cursorDiv.style.visibility == "visible";
629 }
630
631 /**
632 * Continuously toggles the cursor div's visibility over time
633 * @param {Boolean} on True to turn it on, false to turn it off and hide it.
634 */
635 function cursorBlink(on) {
636
637 if (typeof on != "undefined")
638 cursorBlink.on = on;
639
640 if (cursorBlink.on) {
641 setCursorVisible(!isCursorVisible());
642 cursorBlinkTOId = setTimeout(cursorBlink, CURSOR_BLINK_MS_TIME, 1); // NB: IE does not pass arguments
643 } else if (cursorBlinkTOId) {
644 clearTimeout(cursorBlinkTOId);
645 cursorBlinkTOId = null;
646 setCursorVisible(false);
647 }
648 }
649
650
651 /**
652 * Scrolls the document to the current cursor's position
653 */
654 function scrollToCursor() {
655
656 if (!currentCursorDesc) return;
657
658 var viewPortSize = _getViewPortSize(),
659 dx = 0,
660 dy = 0;
661
662 // Get dy
663 if ((currentCursorDesc.y + currentCursorDesc.height) >= viewPortSize.height) {
664 dy = (currentCursorDesc.y + currentCursorDesc.height) - viewPortSize.height;
665 } else if (currentCursorDesc.y < 0) {
666 dy = currentCursorDesc.y;
667 }
668
669 // get dx
670 var xpos = currentCursorDesc.x + (currentCursorDesc.isRightOf ? currentCursorDesc.width : 0) + parseInt(cursorDiv.style.width);
671 if (xpos >= viewPortSize.width) {
672 dx = xpos - viewPortSize.width;
673 } else if (currentCursorDesc.x < 0) {
674 dx = currentCursorDesc.x;
675 }
676
677 if (dx || dy) window.scrollBy(dx, dy);
678
679 }
680
681 /* -------------------------------------------------------------------------------------- */
682 // Support functions for locating cursor information
683 /* -------------------------------------------------------------------------------------- */
684
685 // See de.cursor.getPlacementFlags doc
686 function getPlacementFlags(node) {
687
688 // Always place cursor after the packages.
689 // NOTE: Testing this first to avoid placing cursor in placeholders within the packaged nodes.
690 var pcon = de.doc.getPackageContainer(node);
691 if (pcon) {
692 var pflags = 0;
693 if (pcon == node)
694 pflags = de.cursor.PlacementFlag.BEFORE | de.cursor.PlacementFlag.AFTER;
695 return pflags;
696 }
697
698 // Cursors can be placed before placeholders, but not inside of them
699 if (de.doc.isESPlaceHolder(node, false))
700 return (de.doc.isESPlaceHolder(node, true)) ? de.cursor.PlacementFlag.BEFORE : 0;
701
702 if (de.doc.isMNPlaceHolder(node, false))
703 return (de.doc.isMNPlaceHolder(node, true)) ? de.cursor.PlacementFlag.BEFORE : 0;
704
705 if (node.nodeType == Node.TEXT_NODE) {
706
707 if (_doesTextSupportNonWS(node))
708 return de.cursor.PlacementFlag.INSIDE;
709
710 return 0;
711 }
712
713 var flags = 0;
714
715 // TODO: REFACTOR/DOCUMENT
716 // Apply user flag funciton if specified
717 if (de.cursor.usrGetPlacementFlags) {
718 flags = de.cursor.usrGetPlacementFlags(node);
719 if (flags === $undefined)
720 flags = 0;
721 else return flags;
722 }
723
724 if (beforeElements[_nodeName(node)])
725 flags = de.cursor.PlacementFlag.BEFORE;
726
727 if (afterElements[_nodeName(node)])
728 flags |= de.cursor.PlacementFlag.AFTER;
729
730 return flags;
731 }
732
733 /**
734 * Determines whether cinf1 is closer to target than cinf2. Uses adx/ady information
735 *
736 * @param {de.cursor.CursorDescriptor} desc1 A cursor to compare
737 * @param {de.cursor.CursorDescriptor} desc2 A cursor to compare
738 * @param {Number} targetY The target Y (used for boundry cases)
739 *
740 * @return True if desc1 is closer than desc2.
741 */
742 function isCloserToTarget(desc1, desc2, targetY){
743
744 // If they are on the same line...
745 if (isOnSameLine(desc1, desc2)) {
746 // Then compare there absolute delta x's
747 return desc1.adx < desc2.adx;
748 } else if (desc1.ady == desc2.ady) {
749 // Else if not on the same line AND they have the same absolute delta y's
750 // then choose the closest to target Y from in the middle of their height
751 return Math.abs((desc1.y + (desc1.height / 2)) - targetY) < Math.abs((desc2.y + (desc2.height / 2)) - targetY);
752 }
753
754 // They do not accur on the same line, and have diffent ady's... so pick closest to target Y
755 return desc1.ady < desc2.ady;
756 }
757
758
759 /**
760 * Determines whether desc1 is closer to (x, y) than desc2.
761 *
762 * @param {de.cursor.CursorDescriptor} desc1 A cursor to compare
763 * @param {de.cursor.CursorDescriptor} desc2 A cursor to compare
764 * @param {Number} tx The target x-coord
765 * @param {Number} ty The target y-coor
766 *
767 * @return True if desc1 is closer than desc2.
768 */
769 function isCloserToXY(desc1, desc2, x, y){
770
771 // If they are on the same line then compare there absolute delta x's
772 if (isOnSameLine(desc1, desc2))
773 return Math.abs(desc1.x - x) < Math.abs(desc2.x - x);
774
775 var ady1 = Math.min(Math.abs(desc1.y - y), Math.abs((desc1.y + desc1.height) - y));
776 var ady2 = Math.min(Math.abs(desc2.y - y), Math.abs((desc2.y + desc2.height) - y));
777
778 // Else if not on the same line AND they have the same absolute delta y's
779 // then choose the closest to target Y from in the middle of their height
780 if (ady1 == ady2)
781 return Math.abs((desc1.y + (desc1.height / 2)) - y) < Math.abs((desc2.y + (desc2.height / 2)) - y);
782
783 // They do not accur on the same line, and have diffent ady's... so pick closest to target Y
784 return ady1 < ady2;
785 }
786
787 // See de.cursor.isOnSameLine jsdoc
788 function isOnSameLine(desc1, desc2){
789 return (desc1.y >= desc2.y && desc1.y < (desc2.y + desc2.height)) ||
790 (desc2.y >= desc1.y && desc2.y < (desc1.y + desc1.height));
791 }
792
793 /**
794 * If there are any elements/nodes in the document that were used for measurement
795 * purposes (via setupMeasuringNodes).
796 */
797 function restoreMeasuringNodes() {
798 if (measurePostTextNode) {
799 measurePostTextNode.parentNode.removeChild(measureSpanEl);
800 measurePostTextNode.parentNode.removeChild(measurePreTextNode);
801 measurePostTextNode.nodeValue = measureFullText;
802 measurePostTextNode = null;
803 }
804 }
805
806 /**
807 * Lazily sets up measuring elements/nodes in document.
808 * Be sure to call restoreMeasuringNodes if you want the nodes to be removed
809 * (i.e. The DOM document to return to it's original state)
810 *
811 * @param {Node} textNode The text-node for which measurements are to take place.
812 */
813 function setupMeasuringNodes(textNode){
814
815 if (measurePostTextNode == textNode)
816 return;
817 if (measurePostTextNode)
818 restoreMeasuringNodes();
819
820 measurePostTextNode = textNode;
821 measureFullText = textNode.nodeValue;
822
823 // Split the text node into 3 nodes (including self)
824 textNode.parentNode.insertBefore(measureSpanEl, textNode);
825 textNode.parentNode.insertBefore(measurePreTextNode, measureSpanEl);
826 }
827
828 /**
829 * Requires that setupMeasuringNodes has been invoked.
830 * Isolates measure nodes so that the measureSpanEl encapsulates a single charactor
831 * at a given index.
832 *
833 * @param {Number} index The index of the charactor to isolate.
834 * @return True if the isolated charactor is a renderable symbol.
835 */
836 function measureCharactor(index) {
837 measurePreTextNode.nodeValue = measureFullText.substr(0, index);
838 measureSpanTextNode.nodeValue = measureFullText.charAt(index);
839 measurePostTextNode.nodeValue = measureFullText.substr(index + 1);
840 return measureSpanEl.offsetHeight != 0 && measureSpanEl.offsetWidth != 0;
841 }
842
843 /**
844 * Measures a line break element.
845 * Restores any measuring nodes before and after operation.
846 *
847 * @param {Node} lb A line break element to measure.
848 * @return {Object} A tuple containing the position of the
849 * line break in the window, and its height.
850 */
851 function measureLineBreak(lb) {
852
853 restoreMeasuringNodes();
854
855 // Flag this to signify that meaure nodes are occupied.
856 measurePostTextNode = {};
857
858 measureSpanTextNode.nodeValue = _NBSP;
859 _insertAfter(measureSpanEl, lb);
860
861 var spatInf = _getPositionInWindow(measureSpanEl);
862 spatInf.height = measureSpanEl.offsetHeight;
863
864 measureSpanEl.parentNode.removeChild(measureSpanEl);
865
866 // Reset flag
867 measurePostTextNode = null;
868
869 return spatInf;
870 }
871
872 /**
873 * Remeasures a cInfo's position (window and document) at its given
874 * textnode / charactor, index - and updates the info's properties
875 * accordingly.
876 *
877 * @param {de.cursor.CursorDescriptor} cursorDesc
878 */
879 function setSpatialMembers(cursorDesc) {
880
881 if (!cursorDesc) return;
882
883 if (_nodeName(cursorDesc.domNode) == "br") {
884 var inf = measureLineBreak(cursorDesc.domNode);
885 cursorDesc.x = inf.x;
886 cursorDesc.y = inf.y;
887 cursorDesc.height = inf.height;
888 cursorDesc.width = 0;
889
890 } else {
891
892 var spatEl;
893
894 // Determine which element to get the spatial info from
895 if (cursorDesc.placement == de.cursor.PlacementFlag.INSIDE) {
896
897 setupMeasuringNodes(cursorDesc.domNode);
898
899 measureCharactor(cursorDesc.relIndex);
900
901 spatEl = measureSpanEl;
902
903 } else
904 spatEl = cursorDesc.domNode;
905
906 var pos = _getPositionInWindow(spatEl);
907 cursorDesc.x = pos.x;
908 cursorDesc.y = pos.y;
909 cursorDesc.width = spatEl.offsetWidth;
910 cursorDesc.height = spatEl.offsetHeight;
911
912 }
913
914 var docScrollPos = _getDocumentScrollPos();
915 cursorDesc.docLeft = docScrollPos.left + cursorDesc.x;
916 cursorDesc.docTop = docScrollPos.top + cursorDesc.y;
917
918 restoreMeasuringNodes();
919 }
920
921 // see de.cursor.getNextCursorMovement
922 function getNextCursorMovement(srcCDesc, left) {
923
924 var startNode = srcCDesc.domNode,
925 startIndex = srcCDesc.relIndex,
926 startIsRightOf = srcCDesc.isRightOf,
927 nextNode,
928 nextIndex,
929 nextIsRightOf,
930 placementFlags = getPlacementFlags(srcCDesc.domNode),
931 lastVisitedNode,
932 pendingLineBreak,
933 seenBlockElement = false,
934 prevTextInfo;
935
936 if (placementFlags == de.cursor.PlacementFlag.INSIDE) {
937
938 // If needs simple flip of is rightof flag then return a flipped version
939 if (srcCDesc.isRightOf == left) {
940 var cDesc = de.cursor.createCursorDesc(srcCDesc.domNode, srcCDesc.relIndex, !srcCDesc.isRightOf);
941 if (cDesc) return cDesc;
942 }
943
944 } else if (srcCDesc.isRightOf && placementFlags != de.cursor.PlacementFlag.INSIDE) {
945
946 if (left) {
947
948 // If scanning left but source cursor is to the right of an element, then need to start the
949 // traversal within the elements deepest-right descendant
950 while (startNode.lastChild) {
951 startNode = startNode.lastChild;
952 }
953 if (startNode != srcCDesc.domNode) {
954 startIndex = _nodeLength(startNode, 2) - 1;
955 startIsRightOf = true;
956 }
957
958 }
959 }
960
961 // Begin traversing from source point inclusive
962 _visitAllNodes(docBody, startNode, !left, function(domNode) {
963
964 var firstVisit = domNode == startNode;
965
966 // Skip node that are not displayed / is protected
967 if (!_isNodeDisplayed(domNode) || de.doc.isProtectedNode(domNode)) {
968 lastVisitedNode = domNode;
969 return true;
970 }
971
972 if (!seenBlockElement && !firstVisit)
973 seenBlockElement = _isBlockLevel(domNode);
974
975 placementFlags = getPlacementFlags(domNode);
976
977 // Check after nodes
978 if (lastVisitedNode) {
979 var commonAncestor = _getCommonAncestor(domNode, lastVisitedNode, true);
980 var checkANodes = _getAncestors(left ? domNode : lastVisitedNode, commonAncestor, false);
981 if (left) { // Need to search from top-down in left search
982 checkANodes.reverse();
983 // Include the current node in the search if it is an after node - except for line breaks
984 if ((placementFlags & de.cursor.PlacementFlag.AFTER)
985 && !_isAncestor(domNode, lastVisitedNode)
986 && _nodeName(domNode) != "br")
987 checkANodes.push(domNode);
988 } else {
989 if (!_isAncestor(lastVisitedNode, domNode)
990 && _nodeName(lastVisitedNode) != "br"
991 && !de.doc.isProtectedNode(lastVisitedNode)
992 && !(lastVisitedNode == startNode && startIsRightOf))
993 checkANodes.push(lastVisitedNode);
994 }
995
996 for (var i in checkANodes) {
997 var node = checkANodes[i];
998
999 // Is this node an actual after node?
1000 if (getPlacementFlags(node) & de.cursor.PlacementFlag.AFTER) {
1001
1002 // Check for pending line break
1003 if (checkLineBreak(node))
1004 return false;
1005
1006 // Found the next move
1007 nextNode = node;
1008 nextIndex = 1;
1009 nextIsRightOf = true;
1010 return false;
1011 }
1012
1013 // Update block level flag
1014 seenBlockElement |= _isBlockLevel(node);
1015 }
1016 }
1017
1018 // Is a dom node which is needing a placeholder?
1019 if (placementFlags == 0) {
1020
1021 if (!de.doc.isNodePackaged(domNode)) {
1022 var phType = 0
1023 if (_doesNeedESPlaceholder(domNode))
1024 phType = 1;
1025 else if (_doesNeedMNPlaceholder(domNode)) phType = 2;
1026
1027 if (phType) {
1028
1029 // Create missing placeholder and add it.. prevent the undo manager
1030 // from setting the cursor and if there is any undo history then
1031 // group this with the last action... and if the dontStoreInsertPHOps option is set then
1032 // prevent the undo manager from storing the operations all together
1033 de.UndoMan.execute(de.UndoMan.hasUndo() ? de.UndoMan.ExecFlag.GROUP : 0, "InsertHTML", _getOuterHTML(phType == 1 ? de.doc.createESPlaceholder(domNode) : de.doc.createMNPlaceholder()), domNode, domNode.firstChild, 0);
1034
1035 // Check for pending linebreak first
1036 if (!checkLineBreak(domNode.firstChild)) {
1037 // Set next cursor point to the created placeholder
1038 nextNode = domNode.firstChild;
1039 nextIndex = 0;
1040 nextIsRightOf = false;
1041 }
1042 return false;
1043
1044 }
1045 }
1046
1047 } else if (placementFlags == de.cursor.PlacementFlag.INSIDE) { // AKA A text node
1048
1049 setupMeasuringNodes(domNode);
1050
1051 var relIndex = firstVisit ? startIndex : (left ? _nodeLength(domNode) - 1 : 0),
1052 isRightOf;
1053
1054 // Determine is rightof flag
1055 if (firstVisit)
1056 isRightOf = startIsRightOf;
1057 else if (prevTextInfo) {
1058 // If measured a text position (start point was a text node),
1059 // use its isrightof flag, unless seen a block level
1060 // element.
1061 if (seenBlockElement) {
1062 prevTextInfo = null; // Reset to void checking for a line wrap
1063 isRightOf = left;
1064 } else isRightOf = prevTextInfo.isRightOf;
1065 } else isRightOf = left;
1066
1067 // For each charactor in the run of text
1068 for (; (left && relIndex >= 0) ||
1069 (!left && relIndex < measureFullText.length); relIndex += left ? -1 : 1) {
1070
1071 // Measure the charactor. Skip non renderable charactors
1072 if (!measureCharactor(relIndex)) {
1073 if (firstVisit)
1074 isRightOf = !isRightOf;
1075 firstVisit = false;
1076 continue;
1077 }
1078
1079 // Determine the charactor position
1080 var inf = _getPositionInWindow(measureSpanEl);
1081 inf.height = measureSpanEl.offsetHeight;
1082
1083 // If there is a pending line break, check to see if it
1084 // occurs on the same line as the measured renderable charactor
1085 if (checkLineBreak(measureSpanEl, inf))
1086 return false;
1087
1088 // Check if the charactor is at the start or end of a line (line wrap start/end)
1089 if (prevTextInfo) {
1090 debug.assert(!firstVisit);
1091 if (!isOnSameLine(inf, prevTextInfo)) {
1092 nextNode = domNode;
1093 nextIndex = relIndex;
1094 nextIsRightOf = !isRightOf;
1095 return false;
1096 }
1097 }
1098
1099 // If this isnt the starting point then found the next pos
1100 if (!firstVisit || startNode != srcCDesc.domNode) {
1101 nextNode = domNode;
1102 nextIndex = relIndex;
1103 nextIsRightOf = isRightOf;
1104 return false;
1105 }
1106 // Note: no need to check to flip isRightOf flag since this is checked before traversal
1107
1108 // Re-setup the measuring nodes (if needs to) due to line break measurements above
1109 setupMeasuringNodes(domNode);
1110 firstVisit = false;
1111
1112 // Set prevTextInfo for testing for line wraps on next text measure
1113 prevTextInfo = {
1114 domNode : domNode,
1115 isRightOf: isRightOf,
1116 y: inf.y,
1117 height: inf.height
1118 };
1119
1120 // If the node is a placeholder, only count one movement
1121 if (de.doc.isMNPlaceHolder(domNode) || de.doc.isESPlaceHolder(domNode)) {
1122 prevDesc.isRightOf = false;
1123 break;
1124 }
1125
1126 } // End loop: measuring each char in the run of text
1127
1128 // Must restore nodes to avoid traversal going into measure nodes themselves
1129 restoreMeasuringNodes();
1130
1131 } else if (placementFlags & de.cursor.PlacementFlag.BEFORE) {
1132
1133 // Only set as before node if not the first visit or if searching left and began to right of the node.
1134 if(!firstVisit || (left && domNode == startNode && startIsRightOf)) {
1135 if (!checkLineBreak(domNode)) {
1136 nextNode = domNode;
1137 nextIsRightOf = false;
1138 nextIndex = 0;
1139 }
1140 return false;
1141 }
1142
1143 } else if (_nodeName(domNode) == "br") { // Check for line breaks (Pure AFTER nodes)
1144
1145 if (!firstVisit) {
1146
1147 // Check for any pending line breaks
1148 if (checkLineBreak(domNode))
1149 return false;
1150
1151 if (left) {
1152 // For LEFT searches check for pending line breaks right away since the
1153 // right-node information is always available
1154 pendingLineBreak = domNode;
1155 if (checkLineBreak(lastVisitedNode, prevTextInfo && prevTextInfo.domNode == lastVisitedNode ? prevTextInfo : null))
1156 return false;
1157
1158 } else { // Right
1159 // Set new pending line break
1160 pendingLineBreak = domNode;
1161 }
1162
1163 }
1164 }
1165
1166 lastVisitedNode = domNode;
1167
1168 // For right searches, if the cursor begins to the right on an element then avoid
1169 // traversing inside the descendants
1170 if (!left && firstVisit && srcCDesc.isRightOf && placementFlags != de.cursor.PlacementFlag.INSIDE)
1171 return 1;
1172
1173 }); // End traversal
1174
1175 restoreMeasuringNodes();
1176
1177 // Found a cursor?
1178 return nextNode ? de.cursor.createCursorDesc(nextNode, nextIndex, nextIsRightOf) : null;
1179
1180 /**
1181 * An inner support function. Determines whether a pending line break
1182 * should be the next cursor position
1183 *
1184 * WARNING: This may restore any current measuring nodes!
1185 *
1186 * @param {Node} ele The current element to check pending line breaks against
1187 *
1188 * @param {Object} eleDesc Optional (created if not provided). A descriptor, with at least the y and height members set
1189 *
1190 * @return {Boolean} True iff the next move is a pending line break (in which case next node/index will be set).
1191 *
1192 */
1193 function checkLineBreak(ele, eleDesc) {
1194
1195 // If there is a pending line break, check to see if it
1196 // occurs on the same line as this
1197 if (pendingLineBreak) {
1198
1199 // Measure pending line break and element spatial qaulties
1200 var lbMeas = measureLineBreak(pendingLineBreak),
1201 eleDesc = eleDesc || (_nodeName(ele) == "br" ? measureLineBreak(ele) : {
1202 y: _getPositionInWindow(ele).y,
1203 height: ele.offsetHeight
1204 });
1205
1206 if (!isOnSameLine(lbMeas, eleDesc)) {
1207 // If this before after node is not on the same line as the pending
1208 // line break, then count the line break as part of the move.
1209 nextNode = pendingLineBreak;
1210 nextIndex = 1;
1211 nextIsRightOf = true;
1212 return true;
1213 }
1214
1215 pendingLineBreak = null;
1216 }
1217
1218 return false;
1219
1220 } // End inner checkLineBreak function
1221
1222 } // End getNextCursorMovement
1223
1224
1225 // See de.cursor.getCursorDescAtXY
1226 function getCursorDescAtXY(targetX, targetY, targetNode){
1227
1228 if (!targetNode)
1229 targetNode = _getRenderedNodeAtXY(targetX, targetY);
1230
1231 // If the target was the cursor - recalc the target to the node behind the cursor.
1232 if (targetNode == cursorDiv) {
1233 cursorDiv.style.display = "none";
1234 targetNode = _getRenderedNodeAtXY(targetX, targetY);
1235 cursorDiv.style.display = "";
1236 }
1237
1238 if (!targetNode) return null;
1239
1240 // Get the searchspace for the bin search
1241 var searchSpace = getBinSearchSpace();
1242
1243 // Perform the dual binary search
1244 var cDesc = searchBestCursorPos(targetX, targetY, searchSpace);
1245
1246 // Restore the DOM structure
1247 restoreMeasuringNodes();
1248
1249 return cDesc;
1250
1251 /**
1252 * An inner supporting function.
1253 *
1254 * @return The search space for the binary search
1255 */
1256 function getBinSearchSpace(){
1257
1258 // Build array of all nodes to search inside of targetEl
1259 var nodesToSearch = [],
1260 totalPlacementLength = 0,
1261 wndSize = _getWindowSize();
1262
1263 (function traverse(domNode) {
1264
1265 var placementFlags = getPlacementFlags(domNode),
1266 checkElement,
1267 posInWindow;
1268
1269 // Avoid adding nodes which are not in the viewport
1270 if (domNode.nodeType == Node.ELEMENT_NODE) {
1271 checkElement = domNode;
1272 } else if (domNode.nodeType == Node.TEXT_NODE && placementFlags != 0) {
1273 setupMeasuringNodes(domNode);
1274 measurePreTextNode.nodeValue = "";
1275 measureSpanTextNode.nodeValue = measureFullText;
1276 measurePostTextNode.nodeValue = "";
1277 checkElement = measureSpanEl;
1278 }
1279
1280 if (checkElement) {
1281
1282 posInWindow = _nodeName(checkElement) == "br" ?
1283 measureLineBreak(checkElement) :
1284 _getPositionInWindow(checkElement);
1285
1286 // Is this element above the veiw port?
1287 if ((posInWindow.y + checkElement.offsetHeight) <= 0) {
1288 restoreMeasuringNodes();
1289 return true;
1290 }
1291
1292 // Is this element below the veiw port?
1293 if (posInWindow.y > wndSize.height) {
1294 restoreMeasuringNodes();
1295 return false;
1296 }
1297
1298 restoreMeasuringNodes();
1299 }
1300
1301 if (placementFlags == de.cursor.PlacementFlag.INSIDE) { // AKA a text node
1302 nodesToSearch.push({
1303 domNode: domNode,
1304 startIndex: totalPlacementLength,
1305 endIndex: totalPlacementLength + _nodeLength(domNode) - 1,
1306 length: _nodeLength(domNode),
1307 placement: de.cursor.PlacementFlag.INSIDE
1308 });
1309
1310 totalPlacementLength += _nodeLength(domNode);
1311
1312 } else if (placementFlags & de.cursor.PlacementFlag.BEFORE) {
1313 nodesToSearch.push({
1314 domNode: domNode,
1315 startIndex: totalPlacementLength,
1316 endIndex: totalPlacementLength + 1,
1317 length: 1,
1318 placement: de.cursor.PlacementFlag.BEFORE, // Only store before flag
1319 posInWnd : posInWindow // cache this
1320 });
1321 totalPlacementLength++;
1322 }
1323
1324 // Recurse in order traversal
1325 var child = domNode.firstChild;
1326 var continueTrav = true;
1327 while(child) {
1328 if (!traverse(child)) {
1329 continueTrav = false; // Started to traverse in node below the viewport
1330 break;
1331 }
1332 child = child.nextSibling;
1333 }
1334
1335 // Add after nodes (event if aborting traversal)
1336 if (placementFlags & de.cursor.PlacementFlag.AFTER) {
1337 nodesToSearch.push({
1338 domNode: domNode,
1339 startIndex: totalPlacementLength,
1340 endIndex: totalPlacementLength + 1,
1341 length: 1,
1342 placement: de.cursor.PlacementFlag.AFTER, // Only store after flag
1343 posInWnd : posInWindow // cache this
1344 });
1345 totalPlacementLength++;
1346
1347 }
1348
1349 return continueTrav;
1350
1351 })(targetNode);
1352
1353 return {
1354 nodes: nodesToSearch,
1355 totalLength: totalPlacementLength
1356 };
1357
1358 } // End inner getBinSearchSpace
1359
1360 } // End getCursorDescAtXY
1361
1362 /**
1363 * IMPORTANT: Measurement nodes are left un-restored after this operation
1364 * Call restoreMeasuringNodes if you want to restore the dom.
1365 *
1366 * @param {Number} targetX The x coord to get the closest cusor pos to
1367 * @param {Number} targetY The y coord to get the closest cusor pos to
1368 * @param {Object} A dual bin search space to search.
1369 * @param {de.cursor.CursorDescriptor} targetLineRef A reference point to search for a best position directly above or
1370 * below the line. Null for full search.
1371 *
1372 * @param {Boolean} aboveLine If given targetLineRef then set to true to search for best position above the reference point.
1373 * Other false will search below the reference point.
1374 *
1375 * @return {de.cursor.CursorDescriptor} The closest cursor position it can find. Null if could not find one.
1376 *
1377 */
1378 function searchBestCursorPos(targetX, targetY, searchSpace, targetLineRef, aboveLine){
1379
1380 // Hash table as an associative array, caches measurements
1381 var nonRenderables = {};
1382
1383 if (searchSpace.totalLength == 0)
1384 return null;
1385
1386 // Sample first position in target element
1387 var startDesc = getCursorDescFrom(0, 0, 2);
1388 if (!startDesc)
1389 return null;
1390
1391 // Sample last charactor in target element
1392 var endDesc = getCursorDescFrom(searchSpace.nodes.length - 1, searchSpace.nodes[searchSpace.nodes.length - 1].length - 1, 1);
1393
1394 debug.assert(endDesc != null);
1395
1396 // Check to see if first and last samples are the same
1397 if (startDesc.domNode == endDesc.domNode &&
1398 startDesc.absIndex == endDesc.absIndex) {
1399 // There must be only 1 renderable charactor in the target element
1400 return validDescriptor(startDesc);
1401 }
1402
1403 // Store the first samples
1404 var samples = [startDesc, endDesc];
1405
1406 var best = null;
1407
1408 // Determine closest sample and set as the current best
1409 best = isCloserToTarget(startDesc, endDesc, targetY) ? startDesc : endDesc;
1410
1411 // Upper and lower are the bounds of the search space in the form of cursor descriptors
1412 var upper, lower;
1413
1414 // This algorithm has two passes: The first pass is a binary search to discover the line, or closest line,
1415 // that the target is on. The second pass is a binary search to home in on the closest charactor to the target
1416 // on the line that was found to be the best.
1417 for (var pass = 1; pass <= 2; pass++) { // dual binary search
1418 if (pass == 1) { // setup first pass: Y DOMAIN
1419
1420 if (targetLineRef) {
1421
1422 // If the binary search should find best matching position above or below a line reference point,
1423 // then discover all lines within the search space
1424 discoverAllLines(startDesc, getNodeIndex(startDesc.absIndex), endDesc, getNodeIndex(endDesc.absIndex));
1425
1426 // Select the closest sample that does not fall on the line reference point
1427 selectBest();
1428
1429 // Now the the target line has been discovered, set the target Y
1430 targetY = best.y + (best.height / 2);
1431
1432 // Re-calc best abs delta y
1433 best.ady = Math.abs(best.y - targetY);
1434
1435 // Move to X-bin-search
1436 continue;
1437
1438 } else {
1439 // Select the upper and low for the Y range - goto next pass if already on target line
1440 if (!selectYRange()) continue;
1441 }
1442
1443 } else { // setup second pass: X DOMAIN
1444 var res = selectXRange();
1445
1446 if (typeof res == "boolean") {
1447 if (!res) break; // Else the upper and lower range has been selected
1448 } else break; // the best was found
1449 }
1450
1451 // Enter binary search for quickly locating closest line, or charactor
1452 while (true) {
1453
1454 debug.assert(lower.absIndex < upper.absIndex);
1455
1456 // If lower is next to upper and was doing the line search, then the line search is done... an exact match wasn't found
1457 // and the binary search verged towards two charactors side by side but on different lines.
1458 // ...and if was doing the charactor search, then the search has verged at the final point
1459 if (lower.absIndex == (upper.absIndex - 1)) break;
1460
1461 // Determine current index by halving the search space
1462 var curAbsIndex = lower.absIndex + Math.floor((upper.absIndex - lower.absIndex) / 2);
1463
1464 // Ensure that the index is not out of bounds
1465 if (curAbsIndex == lower.absIndex)
1466 curAbsIndex++;
1467 else if (curAbsIndex == upper.absIndex) curAbsIndex--;
1468
1469 // Locate which node within the target element that the current absolute index is in
1470 var curNodeIndex = getNodeIndex(curAbsIndex);
1471
1472 // Get the cursor desc at the current node/rel-index
1473 var current = getCursorDescFrom(curNodeIndex, curAbsIndex - searchSpace.nodes[curNodeIndex].startIndex, 0);
1474
1475 // Upper and Lower are next to each other
1476 if (!current) break;
1477
1478 // In the first pass all samples are recorded - the initial upper and lower bounds of the next pass
1479 // will be salvaged from these samples.
1480 if (pass == 1) samples.push(current);
1481
1482 // Check to see if current is the new best
1483 if (isCloserToTarget(current, best, targetY)) best = current;
1484
1485 if (pass == 1) { // Line search
1486 // Check to see if current matches line.
1487 if (targetY >= current.y && targetY <= (current.y + current.height))
1488 break; // finished since found a match
1489
1490 // Narrow search
1491 else if (current.y > targetY)
1492 upper = current;
1493 else
1494 lower = current;
1495
1496 } else { // Charactor search
1497 // Determine if current is on the same line as the best
1498 if (isOnSameLine(current, best)) {
1499
1500 // See if target X is on top of current
1501 if (targetX >= current.x && targetX <= (current.x + current.width))
1502 break; // If so, then search complete
1503
1504 // Otherwise narrow search based on x position
1505 else if (current.x > targetX)
1506 upper = current;
1507 else
1508 lower = current;
1509
1510 } // If not on same line, then narrow search based on Y coordinates
1511 else if (current.y > targetY)
1512 upper = current;
1513 else
1514 lower = current;
1515
1516 }
1517
1518 } // End loop: core binary search for finding line and charactor
1519 } // End passes
1520 // FINISHED
1521 return validDescriptor(best);
1522
1523 // Support functions to follow...
1524
1525 /**
1526 * @param {Number} absIndex The abs index in the search-space
1527 *
1528 * @return {Number} The index within nodes that absIndex resides
1529 */
1530 function getNodeIndex(absIndex){
1531
1532 var nodes = searchSpace.nodes;
1533
1534 // If there is one text node, then clearly the current index is that node.
1535 if (nodes.length == 1)
1536 return 0;
1537
1538 // Is it in the first text node?
1539 if (absIndex >= nodes[0].startIndex && absIndex <= nodes[0].endIndex)
1540 return 0;
1541
1542 // Is in last text node?
1543 if (absIndex >= nodes[nodes.length - 1].startIndex &&
1544 absIndex <= nodes[nodes.length - 1].endIndex)
1545 return nodes.length - 1;
1546
1547 // begin a little binary search to quickely find the node in the search space
1548 var lo = 0;
1549 var up = nodes.length - 1;
1550 var nodeIndex;
1551
1552 while (true) {
1553
1554 var cur = lo + Math.floor((up - lo) / 2);
1555 if (cur == lo)
1556 cur++;
1557 else if (cur == up) cur--;
1558
1559 if (absIndex >= nodes[cur].startIndex &&
1560 absIndex <= nodes[cur].endIndex) {
1561 nodeIndex = cur;
1562 break;
1563
1564
1565 } else if (absIndex < nodes[cur].startIndex)
1566 up = cur; // search downward
1567
1568 else
1569 lo = cur; // search upward
1570 } // End loop: binary search for locating #text node
1571 return nodeIndex;
1572
1573 } // End inner getNodeIndex
1574
1575 /**
1576 * Gets a cursor descriptor from a given position in the search space.
1577 *
1578 * Some text nodes in the search space may not support a cursor placement since
1579 * they can contain only non-renderable symbols. Therefore the returned cursor
1580 * desc may not be at the given node/index.
1581 *
1582 * @param {Number} dir 0 = Both, within upper and lower bounds, 1 = Left only, 2 = Right only.
1583 * @param {Number} relIndex The relative index
1584 * @param {Number} nodeIndex The index within the search space nodes
1585 *
1586 * @return {Object} the cursor descriptor or NULL if did not find a cursor at the given position that is in bounds.
1587 */
1588 function getCursorDescFrom(nodeIndex, relIndex, dir){
1589
1590 var nodes = searchSpace.nodes,
1591
1592 searchLeft = dir == 0 || dir == 1,
1593
1594 // Store the current relative/node index
1595 // for restoring when switching scan direction
1596 origialRelIndex = relIndex,
1597 originalNodeIndex = nodeIndex,
1598
1599 // Ideally we would directly measure spatial info at the current node / relative index.
1600 // However some charactors in text nodes aren't renderable, and thus we must scan left and/or right
1601 // to find next renderable charactor
1602 measureEl = null,
1603 node; // the node within the searchspace nodes
1604
1605 // Find first renderable symbol. 1 pass for non-text nodes,
1606 // 1-2 pass for text nodes and searching both dirs: 1st pass search left, 2nd pass search right.
1607 do {
1608
1609 if (!searchLeft && dir == 0) { // 2nd pass?
1610 // Switching direction...
1611 nodeIndex = originalNodeIndex;
1612 relIndex = origialRelIndex + 1; // exclusive
1613 // Check to see if the right of the starting point is in a different node
1614 if (relIndex > nodes[nodeIndex].endIndex) {
1615 nodeIndex++;
1616 relIndex = 0;
1617 // Note: If the nodeIndex is out of bounds, the next loop will instantly break
1618 }
1619 }
1620
1621 var reachedSSBounds = false; // refers to search-space upper/lower bounds
1622
1623 // Scan through the nodes
1624 while (nodeIndex >= 0 && nodeIndex < nodes.length) {
1625
1626 node = nodes[nodeIndex];
1627
1628 // Ignore non-diplayed nodes
1629 if (_isNodeDisplayed(node.domNode)) {
1630
1631 // Discover the type of node
1632 if (node.placement == de.cursor.PlacementFlag.INSIDE) { // AKA Text node
1633 // Setup measurement nodes for this text node we are about to search in
1634 setupMeasuringNodes(node.domNode);
1635
1636 // Scan through charactors.. looking for the first renderable symbol
1637 while (relIndex >= 0 && relIndex < measureFullText.length) {
1638
1639 // Is the text node/index out of bounds (only when scanning both ways)?
1640 if (dir == 0 &&
1641 ((lower.domNode == node.domNode && lower.relIndex == relIndex) ||
1642 (upper.domNode == node.domNode && upper.relIndex == relIndex))) {
1643 reachedSSBounds = true;
1644 break;
1645 }
1646
1647 // or have we measured this before and found it was not a renderable char?
1648 if (nonRenderables["_" + nodeIndex + '_' + relIndex]) {
1649 relIndex += (searchLeft ? -1 : 1);
1650 continue; // avoid re-measuring unrenderable node
1651 }
1652
1653 // Measure the current node / index.
1654 if (!measureCharactor(relIndex)) {
1655 // Char is not renderable, note the element and store in the
1656 // hash table (using an accoiative array)
1657 nonRenderables["_" + nodeIndex + '_' + relIndex] = true;
1658 relIndex += (searchLeft ? -1 : 1);
1659 continue;
1660 }
1661
1662 // Determine position of the charactor. This will be used as a flag
1663 // for ending the search for the first non-renderable charactor
1664 measureEl = measureSpanEl;
1665 break;
1666
1667 } // End loop: Searching for renderable charactor
1668
1669
1670 } else { // BEFORE and AFTER nodes
1671 // Is the text node/index out of bounds (only when scanning both ways)?
1672 if (dir == 0 &&
1673 ((lower.domNode == node.domNode && lower.placement == node.placement) ||
1674 (upper.domNode == node.domNode && upper.placement == node.placement))) {
1675 reachedSSBounds = true;
1676 break;
1677 }
1678
1679 measureEl = node.domNode;
1680 break;
1681 }
1682 }
1683
1684 // Have we found the next sample, or has the right-scan reached the upper search-space bound?
1685 if (measureEl || reachedSSBounds) break;
1686
1687 // Setup current node index for scanning the next node
1688 nodeIndex += (searchLeft ? -1 : 1);
1689
1690 // Setup relative index for searching for next renderable char
1691 relIndex = (searchLeft &&
1692 nodeIndex >= 0 &&
1693 nodeIndex < nodes.length) ?
1694 (nodes[nodeIndex].placement == de.cursor.PlacementFlag.INSIDE ? nodes[nodeIndex].length - 1 : 1) : 0;
1695
1696 } // End loop: scanning nodes in a particular direction
1697
1698 // Was a sample found?
1699 if (measureEl) break;
1700
1701 } while (dir == 0 && !(searchLeft = !searchLeft)); // End loop: scanning left and/or right
1702
1703 // If there were no places where the cursor can be placed between lower and upper,
1704 // then the search is done.
1705 if (!measureEl)
1706 return null;
1707
1708 var pos, width, height;
1709
1710 // Is their cached spatial calculations for this node?
1711 if (node.posInWnd)
1712 pos = node.posInWnd;
1713
1714 if (_nodeName(measureEl) == "br") {
1715 pos = pos || measureLineBreak(measureEl);
1716 height = pos.height;
1717 width = 0;
1718 } else {
1719 pos = pos || _getPositionInWindow(measureEl);
1720 width = measureEl.offsetWidth;
1721 height = measureEl.offsetHeight;
1722 }
1723
1724 var adxl = Math.abs(pos.x - targetX),
1725 adxr = Math.abs(pos.x + width - targetX),
1726 isRightOf;
1727
1728 switch (node.placement) { // searchspace placement flags are separated (cannot have combined flags)
1729 case de.cursor.PlacementFlag.BEFORE:
1730 isRightOf = false;
1731 break;
1732
1733 case de.cursor.PlacementFlag.AFTER:
1734 isRightOf = true;
1735 break;
1736
1737 default: // INSIDE/TEXT
1738 isRightOf = adxr < adxl;
1739 }
1740
1741 return {
1742 domNode: node.domNode,
1743 relIndex: relIndex,
1744 absIndex: node.startIndex + relIndex,
1745 placement: node.placement,
1746 isRightOf: isRightOf,
1747 x: pos.x,
1748 y: pos.y,
1749 adx: isRightOf ? adxr : adxl,
1750 ady: Math.min(Math.abs(pos.y - targetY), Math.abs(pos.y + measureEl.offsetHeight - targetY)),
1751 width: width,
1752 height: height
1753 };
1754
1755 } // End inner getCursorDescFrom
1756
1757 /**
1758 * @return {Boolean}
1759 * True if the range is set.
1760 * False if the start or end sample is on the targets line
1761 */
1762 function selectYRange(){
1763
1764 // If the start or end sample is not on the target line, and the target is within the samples y-range,
1765 // then find the best line
1766 if (!((targetY >= startDesc.y && targetY <= (startDesc.y + startDesc.height)) ||
1767 (targetY >= endDesc.y && targetY <= (endDesc.y + endDesc.height))) &&
1768 targetY >= startDesc.y &&
1769 targetY <= (endDesc.y + endDesc.height)) {
1770
1771 // If the target Y does not occur on the start or end sample's line:
1772 lower = startDesc;
1773 upper = endDesc;
1774
1775 return true;
1776 }
1777
1778 return false; // Otherwise, the line-search is done! Next pass...
1779 } // End inner selectYRange
1780 /**
1781 * @return {Boolean, de.cursor.CursorDescriptor}
1782 * False if the best is right at the target.
1783 * Or True if the range has been selected.
1784 * Or A cursor descriptor of the best match if found while setting the range -
1785 * in which case the best var is set
1786 *
1787 */
1788 function selectXRange(){
1789
1790 // Determine the lower and upper bounds to start the charactor binary search with
1791 if (targetX >= best.x && targetX < (best.x + best.width)) {
1792 // If the best is right at the target, then the search is done
1793 return false;
1794
1795 } else if (best.x > targetX) { // search to left of best
1796 upper = best;
1797 lower = null;
1798 for (i in samples) {
1799 current = samples[i];
1800 /*
1801
1802 if (current == best) continue;
1803
1804
1805 var isLeftOrAbove;
1806
1807 // Check if this sample (current) is to the left or above of best
1808 if (isOnSameLine(current, best)) {
1809 // If sample is on sample line as best, then check X coords
1810 isLeftOrAbove = current.x < best.x;
1811
1812 } else
1813 isLeftOrAbove = current.y < best.y; // Check Y coords if not on same line
1814 // If the sample is to the left, or above, of best. Then check to see if the sample
1815 // is closer than the current lower to best.
1816 if (isLeftOrAbove && (!lower || isCloserToXY(current, lower, best.x, best.y)) && current.absIndex < upper.absIndex) {
1817 lower = current;
1818 }*/
1819
1820 // Select preceeding sample to best in sample set
1821 if (current.absIndex < best.absIndex && (!lower || current.absIndex > lower.absIndex))
1822 lower = current;
1823
1824 }
1825
1826 if (!lower) {
1827 // The best line must have been the starting sample, thus the best charactor is
1828 // the first renderable charactor.
1829 return best;
1830 }
1831
1832
1833 } else { // Search to the right of best
1834 lower = best;
1835 upper = null;
1836 for (i in samples) {
1837
1838 current = samples[i];
1839
1840 /*var isRightOrBelow;
1841
1842 // Check if this sample (current) is to the right or below of best
1843 if (isOnSameLine(current, best)) {
1844 // If sample is on sample line as best, then check X coords
1845 isRightOrBelow = current.x > best.x;
1846
1847 } else
1848 isRightOrBelow = current.y > best.y; // Check Y coords if not on same line
1849 // If the sample is to the right, or below, of best. Then check to see if the sample
1850 // is closer than the current upper to best.
1851 if (isRightOrBelow && (!upper || isCloserToXY(current, upper, (best.x + best.width), best.y)) && current.absIndex > lower.absIndex) {
1852 upper = current;
1853 }*/
1854
1855 if (current.absIndex > best.absIndex && (!upper || current.absIndex < upper.absIndex))
1856 upper = current;
1857
1858 }
1859
1860 if (!upper) {
1861 // The best line must have been the ending sample, thus the best charactor is
1862 // the first renderable charactor.
1863 return best;
1864 }
1865
1866 }
1867
1868 return true;
1869
1870 } // End inner selectXRange
1871
1872 /**
1873 * Sets the best local for searching for the closest cursor position before/after a line reference point.
1874 */
1875 function selectBest() {
1876
1877 // Begin with the search space bounds... depending on whether the search should
1878 // look above or below the line reference point
1879 best = aboveLine ? startDesc : endDesc;
1880
1881 // Look in all samples... which contain all lines
1882 for (var i in samples) {
1883
1884 var sample = samples[i];
1885
1886 // Skip samples that are either on the same line as the reference line, or
1887 // is out of bounds...
1888 if (isOnSameLine(sample, targetLineRef) ||
1889 (aboveLine && sample.y > targetLineRef.y) ||
1890 (!aboveLine && sample.y < targetLineRef.y)) continue;
1891
1892 // Set new best if sample is better
1893 if (isCloserToTarget(sample, best, targetY)) {
1894 best = sample;
1895 }
1896
1897 }
1898
1899 } // End inner selectBest
1900
1901 /**
1902 * Samples the search space to discover all lines.
1903 *
1904 * @param {de.cursor.CursorDescriptor} lo A cursor desc
1905 * @param {de.cursor.CursorDescriptor} up A cursor desc
1906 *
1907 * @param {Number} lni Lower node index in search space
1908 * @param {Number} uni Upper node index in search space
1909 */
1910 function discoverAllLines(lo, lni, up, uni){
1911
1912 var stack = [[lo, lni, up, uni]];
1913
1914 while(stack.length > 0) { // simulating recursion - faster and avoids stack overflows
1915
1916 var args = stack.pop();
1917 lo = args[0];
1918 lni = args[1];
1919 up = args[2];
1920 uni = args[3];
1921
1922 // Special attention must be payed to tables. They contain inner lines.
1923 var ni = lni;
1924
1925 // Shrink lower range if lower is a table
1926 while (ni < searchSpace.nodes.length && _nodeName(searchSpace.nodes[ni].domNode) == "table") {
1927 ni++;
1928 }
1929
1930 if (ni == searchSpace.nodes.length) continue;
1931
1932 if (ni != lni) {
1933 lo = getCursorDescFrom(ni, 0, 2);
1934 lni = ni;
1935 samples.push(lo); // duplicates are ok
1936 }
1937
1938 ni = uni;
1939
1940 // Shrink upper range if upper is a table
1941 while (ni >= 0 && _nodeName(searchSpace.nodes[ni].domNode) == "table") {
1942 ni--;
1943 }
1944
1945 if (ni == -1) continue;
1946
1947 if (ni != uni) {
1948 up = getCursorDescFrom(ni, searchSpace.nodes[ni].length - 1, 1);
1949 uni = ni;
1950 samples.push(up); // duplicates are ok
1951 }
1952
1953 // If lower is directly next to upper or they are on the same line
1954 // then the line discovery between these two points is complete
1955 if (lo.absIndex >= (up.absIndex - 1) || isOnSameLine(up, lo)) continue;
1956
1957 // Determine middle index by halving the search space
1958 var midIndex = lo.absIndex + Math.floor((up.absIndex - lo.absIndex) / 2);
1959
1960 // Ensure that the index is not out of bounds
1961 if (midIndex == lo.absIndex)
1962 midIndex++;
1963 else if (midIndex == up.absIndex) midIndex--;
1964
1965 // Locate which node within the target element that the current absolute index is in
1966 var midNodeIndex = getNodeIndex(midIndex);
1967
1968 // Get the cursor desc at the mid point
1969 lower = lo; // getCursorDescFrom uses this for boundry checks
1970 upper = up; // getCursorDescFrom uses this for boundry checks
1971 var mid = getCursorDescFrom(midNodeIndex, midIndex - searchSpace.nodes[midNodeIndex].startIndex, 0);
1972
1973 // Upper and Lower are next to each other
1974 if (!mid) continue;
1975
1976 // Record the sample
1977 samples.push(mid);
1978
1979 // Simulate recursion using a local stack
1980 stack.push([lo, lni, mid, midNodeIndex]); // left side
1981 stack.push([mid, midNodeIndex, up, uni]); // right side
1982
1983 } // Next
1984
1985
1986 } // End inner discoverAllLines
1987
1988 /**
1989 * Esnures that the given descriptor is valid.
1990 * @param {de.cursor.CursorDescriptor} cDesc A desciptor
1991 *
1992 * @return If the given descriptor wasn't valid, it returns a neighbouring cursor placement,
1993 * otherwise the given descriptor is returned.
1994 */
1995 function validDescriptor(cDesc) {
1996 if (!cDesc) return null;
1997
1998 // If the search ended on a line break, then check to make sure
1999 // that the line break has no cursor placements to the left or right of it...
2000 if (_nodeName(cDesc.domNode) == "br") {
2001 var prevDesc = getNextCursorMovement(cDesc,true);
2002 if (prevDesc && isOnSameLine(cDesc, prevDesc)) {
2003 cDesc = prevDesc;
2004 cDesc.isRightOf = true;
2005 } else {
2006 var nextDesc = getNextCursorMovement(cDesc,false);
2007 if (nextDesc && isOnSameLine(cDesc, nextDesc)) {
2008 cDesc = nextDesc;
2009 cDesc.isRightOf = false;
2010 }
2011 }
2012 } else if (de.doc.isMNPlaceHolder(cDesc.domNode))
2013 cDesc.isRightOf = false;
2014
2015 cDesc.placement = getPlacementFlags(cDesc.domNode);
2016
2017 // Supply the position of the cursor in the actual document
2018 // rather than just within the window.
2019 var docScrollPos = _getDocumentScrollPos();
2020
2021 cDesc.docLeft = docScrollPos.left + cDesc.x;
2022 cDesc.docTop = docScrollPos.top + cDesc.y;
2023
2024 return cDesc;
2025 } // End inner validDescriptor
2026
2027 } // End searchBestCursorPos
2028
2029
2030})();
Note: See TracBrowser for help on using the repository browser.