WebCore/page/SpatialNavigation.cpp - WebKit - Git at Google

 /*
  * Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies)
  * Copyright (C) 2009 Antonio Gomes <tonikitoo@webkit.org>
  *
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
  * 2. Redistributions in binary form must reproduce the above copyright
  *    notice, this list of conditions and the following disclaimer in the
  *    documentation and/or other materials provided with the distribution.
  *
  * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY
  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR
  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */

 #include "config.h"
 #include "SpatialNavigation.h"

 #include "Frame.h"
 #include "FrameTree.h"
 #include "FrameView.h"
 #include "HTMLFrameOwnerElement.h"
 #include "IntRect.h"
 #include "Node.h"
 #include "RenderLayer.h"
 #include "Page.h"

 namespace WebCore {

 static long long spatialDistance(FocusDirection, const IntRect&, const IntRect&);
 static IntRect renderRectRelativeToRootDocument(RenderObject*);
 static RectsAlignment alignmentForRects(FocusDirection, const IntRect&, const IntRect&);
 static bool areRectsFullyAligned(FocusDirection, const IntRect&, const IntRect&);
 static bool areRectsPartiallyAligned(FocusDirection, const IntRect&, const IntRect&);
 static bool isRectInDirection(FocusDirection, const IntRect&, const IntRect&);
 static void deflateIfOverlapped(IntRect&, IntRect&);
 static bool checkNegativeCoordsForNode(Node*, const IntRect&);

 void distanceDataForNode(FocusDirection direction, Node* start, FocusCandidate& candidate)
 {
     RenderObject* startRender = start->renderer();
     if (!startRender) {
         candidate.distance = maxDistance();
         return;
     }

     RenderObject* destRender = candidate.node->renderer();
     if (!destRender) {
         candidate.distance = maxDistance();
         return;
     }

     IntRect curRect = renderRectRelativeToRootDocument(startRender);
     IntRect targetRect  = renderRectRelativeToRootDocument(destRender);

     // The bounding rectangle of two consecutive nodes can overlap. In such cases,
     // deflate both.
     deflateIfOverlapped(curRect, targetRect);

     // If empty rects or negative width or height, bail out.
     if (curRect.isEmpty() || targetRect.isEmpty()
      || targetRect.width() <= 0 || targetRect.height() <= 0) {
         candidate.distance = maxDistance();
         return;
     }

     // Negative coordinates can be used if node is scrolled up offscreen.
     if (!checkNegativeCoordsForNode(start, curRect)) {
         candidate.distance = maxDistance();
         return;
     }

     if (!checkNegativeCoordsForNode(candidate.node, targetRect)) {
         candidate.distance = maxDistance();
         return;
     }

     if (!isRectInDirection(direction, curRect, targetRect)) {
         candidate.distance = maxDistance();
         return;
     }

     // The distance between two nodes is not to be considered alone when evaluating/looking
     // for the best focus candidate node. Alignment of rects can be also a good point to be
     // considered in order to make the algorithm to behavior in a more intuitive way.
     candidate.alignment = alignmentForRects(direction, curRect, targetRect);
     candidate.distance = spatialDistance(direction, curRect, targetRect);
 }

 // FIXME: This function does not behave correctly with transformed frames.
 static IntRect renderRectRelativeToRootDocument(RenderObject* render)
 {
     ASSERT(render && render->node());

     IntRect rect = render->node()->getRect();

     // In cases when the |render|'s associated node is in a scrollable inner
     // document, we only consider its scrollOffset if it is not offscreen.
     Node* node = render->node();
     Document* mainDocument = node->document()->page()->mainFrame()->document();
     bool considerScrollOffset = !(hasOffscreenRect(node) && node->document() != mainDocument);

     if (considerScrollOffset) {
         if (FrameView* frameView = render->node()->document()->view())
             rect.move(-frameView->scrollOffset());
     }

     // Handle nested frames.
     for (Frame* frame = render->document()->frame(); frame; frame = frame->tree()->parent()) {
         if (Element* element = static_cast<Element*>(frame->ownerElement())) {
             do {
                 rect.move(element->offsetLeft(), element->offsetTop());
             } while ((element = element->offsetParent()));
         }
     }

     return rect;
 }

 static RectsAlignment alignmentForRects(FocusDirection direction, const IntRect& curRect, const IntRect& targetRect)
 {
     if (areRectsFullyAligned(direction, curRect, targetRect))
         return Full;

     if (areRectsPartiallyAligned(direction, curRect, targetRect))
         return Partial;

     return None;
 }

 static inline bool isHorizontalMove(FocusDirection direction)
 {
     return direction == FocusDirectionLeft || direction == FocusDirectionRight;
 }

 static inline int start(FocusDirection direction, const IntRect& rect)
 {
     return isHorizontalMove(direction) ? rect.y() : rect.x();
 }

 static inline int middle(FocusDirection direction, const IntRect& rect)
 {
     IntPoint center(rect.center());
     return isHorizontalMove(direction) ? center.y(): center.x();
 }

 static inline int end(FocusDirection direction, const IntRect& rect)
 {
     return isHorizontalMove(direction) ? rect.bottom() : rect.right();
 }

 // This method checks if rects |a| and |b| are fully aligned either vertically or
 // horizontally. In general, rects whose central point falls between the top or
 // bottom of each other are considered fully aligned.
 // Rects that match this criteria are preferable target nodes in move focus changing
 // operations.
 // * a = Current focused node's rect.
 // * b = Focus candidate node's rect.
 static bool areRectsFullyAligned(FocusDirection direction, const IntRect& a, const IntRect& b)
 {
     int aStart, bStart, aEnd, bEnd;

     switch (direction) {
     case FocusDirectionLeft:
         aStart = a.x();
         bEnd = b.right();
         break;
     case FocusDirectionRight:
         aStart = b.x();
         bEnd = a.right();
         break;
     case FocusDirectionUp:
         aStart = a.y();
         bEnd = b.y();
         break;
     case FocusDirectionDown:
         aStart = b.y();
         bEnd = a.y();
         break;
     default:
         ASSERT_NOT_REACHED();
         return false;
     }

     if (aStart < bEnd)
         return false;

     aStart = start(direction, a);
     bStart = start(direction, b);

     int aMiddle = middle(direction, a);
     int bMiddle = middle(direction, b);

     aEnd = end(direction, a);
     bEnd = end(direction, b);

     // Picture of the totally aligned logic:
     //
     //     Horizontal    Vertical        Horizontal     Vertical
     //  ****************************  *****************************
     //  *  _          *   _ _ _ _  *  *         _   *      _ _    *
     //  * |_|     _   *  |_|_|_|_| *  *  _     |_|  *     |_|_|   *
     //  * |_|....|_|  *      .     *  * |_|....|_|  *       .     *
     //  * |_|    |_| (1)     .     *  * |_|    |_| (2)      .     *
     //  * |_|         *     _._    *  *        |_|  *    _ _._ _  *
     //  *             *    |_|_|   *  *             *   |_|_|_|_| *
     //  *             *            *  *             *             *
     //  ****************************  *****************************

     //     Horizontal    Vertical        Horizontal     Vertical
     //  ****************************  *****************************
     //  *  _......_   *   _ _ _ _  *  *  _          *    _ _ _ _  *
     //  * |_|    |_|  *  |_|_|_|_| *  * |_|     _   *   |_|_|_|_| *
     //  * |_|    |_|  *  .         *  * |_|    |_|  *           . *
     //  * |_|        (3) .         *  * |_|....|_| (4)          . *
     //  *             *  ._ _      *  *             *        _ _. *
     //  *             *  |_|_|     *  *             *       |_|_| *
     //  *             *            *  *             *             *
     //  ****************************  *****************************

     return ((bMiddle >= aStart && bMiddle <= aEnd) // (1)
             || (aMiddle >= bStart && aMiddle <= bEnd) // (2)
             || (bStart == aStart) // (3)
             || (bEnd == aEnd)); // (4)
 }

 // This method checks if |start| and |dest| have a partial intersection, either
 // horizontally or vertically.
 // * a = Current focused node's rect.
 // * b = Focus candidate node's rect.
 static bool areRectsPartiallyAligned(FocusDirection direction, const IntRect& a, const IntRect& b)
 {
     int aStart  = start(direction, a);
     int bStart  = start(direction, b);
     int bMiddle = middle(direction, b);
     int aEnd = end(direction, a);
     int bEnd = end(direction, b);

     // Picture of the partially aligned logic:
     //
     //    Horizontal       Vertical
     // ********************************
     // *  _            *   _ _ _      *
     // * |_|           *  |_|_|_|     *
     // * |_|.... _     *      . .     *
     // * |_|    |_|    *      . .     *
     // * |_|....|_|    *      ._._ _  *
     // *        |_|    *      |_|_|_| *
     // *        |_|    *              *
     // *               *              *
     // ********************************
     //
     // ... and variants of the above cases.
     return ((bStart >= aStart && bStart <= aEnd)
             || (bStart >= aStart && bStart <= aEnd)
             || (bEnd >= aStart && bEnd <= aEnd)
             || (bMiddle >= aStart && bMiddle <= aEnd)
             || (bEnd >= aStart && bEnd <= aEnd));
 }

 // Return true if rect |a| is below |b|. False otherwise.
 static inline bool below(const IntRect& a, const IntRect& b)
 {
     return a.y() > b.bottom();
 }

 // Return true if rect |a| is on the right of |b|. False otherwise.
 static inline bool rightOf(const IntRect& a, const IntRect& b)
 {
     return a.x() > b.right();
 }

 // * a = Current focused node's rect.
 // * b = Focus candidate node's rect.
 static long long spatialDistance(FocusDirection direction, const IntRect& a, const IntRect& b)
 {
     int x1 = 0, y1 = 0, x2 = 0, y2 = 0;

     if (direction == FocusDirectionLeft) {
         // #1  |--|
         //
         // #2  |--|  |--|
         //
         // #3  |--|

         x1 = a.x();
         x2 = b.right();

         if (below(a, b)) {
             // #1 The a rect is below b.
             y1 = a.y();
             y2 = b.bottom();
         } else if (below(b, a)) {
             // #3 The b rect is below a.
             y1 = a.bottom();
             y2 = b.y();
         } else {
             // #2 Both b and a share some common y's.
             y1 = 0;
             y2 = 0;
         }
     } else if (direction == FocusDirectionRight) {
         //        |--|  #1
         //
         //  |--|  |--|  #2
         //
         //        |--|  #3

         x1 = a.right();
         x2 = b.x();

         if (below(a, b)) {
             // #1 The b rect is above a.
             y1 = a.y();
             y2 = b.bottom();
         } else if (below(b, a)) {
             // #3 The b rect is below a.
             y1 = a.bottom();
             y2 = b.y();
         } else {
             // #2 Both b and a share some common y's.
             y1 = 0;
             y2 = 0;
         }
     } else if (direction == FocusDirectionUp) {
         //
         //   #1    #2    #3
         //
         //  |--|  |--|  |--|
         //
         //        |--|

         y1 = a.y();
         y2 = b.bottom();

         if (rightOf(a, b)) {
             // #1 The b rect is to the left of a.
             x1 = a.x();
             x2 = b.right();
         } else if (rightOf(b, a)) {
             // #3 The b rect is to the right of a.
             x1 = a.right();
             x2 = b.x();
         } else {
             // #2 Both b and a share some common x's.
             x1 = 0;
             x2 = 0;
         }
     } else if (direction == FocusDirectionDown) {
         //        |--|
         //
         //  |--|  |--|  |--|
         //
         //   #1    #2    #3

         y1 = a.bottom();
         y2 = b.y();

         if (rightOf(a, b)) {
             // #1 The b rect is to the left of a.
             x1 = a.x();
             x2 = b.right();
         } else if (rightOf(b, a)) {
             // #3 The b rect is to the right of a
             x1 = a.right();
             x2 = b.x();
         } else {
             // #2 Both b and a share some common x's.
             x1 = 0;
             x2 = 0;
         }
     }

     long long dx = x1 - x2;
     long long dy = y1 - y2;

     long long distance = (dx * dx) + (dy * dy);

     if (distance < 0)
         distance *= -1;

     return distance;
 }

 static bool isRectInDirection(FocusDirection direction, const IntRect& curRect, const IntRect& targetRect)
 {
     IntPoint center(targetRect.center());
     int targetMiddle = isHorizontalMove(direction) ? center.x() : center.y();

     switch (direction) {
     case FocusDirectionLeft:
         return targetMiddle < curRect.x();
     case FocusDirectionRight:
         return targetMiddle > curRect.right();
     case FocusDirectionUp:
         return targetMiddle < curRect.y();
     case FocusDirectionDown:
         return targetMiddle > curRect.bottom();
     default:
         ASSERT_NOT_REACHED();
     }

     return false;
 }

 // Checks if |node| is offscreen the visible area (viewport) of its container
 // document. In case it is, one can scroll in direction or take any different
 // desired action later on.
 bool hasOffscreenRect(Node* node)
 {
     // Get the FrameView in which |node| is (which means the current viewport if |node|
     // is not in an inner document), so we can check if its content rect is visible
     // before we actually move the focus to it.
     FrameView* frameView = node->document()->view();
     if (!frameView)
         return true;

     IntRect containerViewportRect = frameView->visibleContentRect();

     RenderObject* render = node->renderer();
     if (!render)
         return true;

     IntRect rect(render->absoluteClippedOverflowRect());
     if (rect.isEmpty())
         return true;

     return !containerViewportRect.intersects(rect);
 }

 // In a bottom-up way, this method tries to scroll |frame| in a given direction
 // |direction|, going up in the frame tree hierarchy in case it does not succeed.
 bool scrollInDirection(Frame* frame, FocusDirection direction, const FocusCandidate& candidate)
 {
     if (!frame)
         return false;

     ScrollDirection scrollDirection;

     switch (direction) {
     case FocusDirectionLeft:
         scrollDirection = ScrollLeft;
         break;
     case FocusDirectionRight:
         scrollDirection = ScrollRight;
         break;
     case FocusDirectionUp:
         scrollDirection = ScrollUp;
         break;
     case FocusDirectionDown:
         scrollDirection = ScrollDown;
         break;
     default:
         return false;
     }

     if (!candidate.isNull() && isScrollableContainerNode(candidate.enclosingScrollableBox))
         return frame->eventHandler()->scrollRecursively(scrollDirection, ScrollByLine, candidate.enclosingScrollableBox);

     return frame->eventHandler()->scrollRecursively(scrollDirection, ScrollByLine);
 }

 void scrollIntoView(Element* element)
 {
     // NOTE: Element's scrollIntoView method could had been used here, but
     // it is preferable to inflate |element|'s bounding rect a bit before
     // scrolling it for accurate reason.
     // Element's scrollIntoView method does not provide this flexibility.
     IntRect bounds = element->getRect();
     bounds.inflate(fudgeFactor());
     element->renderer()->enclosingLayer()->scrollRectToVisible(bounds);
 }

 bool isInRootDocument(Node* node)
 {
     if (!node)
         return false;

     Document* rootDocument = node->document()->page()->mainFrame()->document();
     return node->document() == rootDocument;
 }

 static void deflateIfOverlapped(IntRect& a, IntRect& b)
 {
     if (!a.intersects(b) || a.contains(b) || b.contains(a))
         return;

     int deflateFactor = -fudgeFactor();

     // Avoid negative width or height values.
     if ((a.width() + 2 * deflateFactor > 0) && (a.height() + 2 * deflateFactor > 0))
         a.inflate(deflateFactor);

     if ((b.width() + 2 * deflateFactor > 0) && (b.height() + 2 * deflateFactor > 0))
         b.inflate(deflateFactor);
 }

 static bool checkNegativeCoordsForNode(Node* node, const IntRect& curRect)
 {
     ASSERT(node || node->renderer());

     if (curRect.x() >= 0 && curRect.y() >= 0)
         return true;

     bool canBeScrolled = false;

     RenderObject* renderer = node->renderer();
     for (; renderer; renderer = renderer->parent()) {
         if (renderer->isBox() && toRenderBox(renderer)->canBeScrolledAndHasScrollableArea()) {
             canBeScrolled = true;
             break;
         }
     }

     return canBeScrolled;
 }

 bool isScrollableContainerNode(Node* node)
 {
     if (!node)
         return false;

     if (RenderObject* renderer = node->renderer()) {
         return (renderer->isBox() && toRenderBox(renderer)->canBeScrolledAndHasScrollableArea()
              && node->hasChildNodes() && !node->isDocumentNode());
     }

     return false;
 }

 bool isNodeDeepDescendantOfDocument(Node* node, Document* baseDocument)
 {
     if (!node || !baseDocument)
         return false;

     bool descendant = baseDocument == node->document();

     Element* currentElement = static_cast<Element*>(node);
     while (!descendant) {
         Element* documentOwner = currentElement->document()->ownerElement();
         if (!documentOwner)
             break;

         descendant = documentOwner->document() == baseDocument;
         currentElement = documentOwner;
     }

     return descendant;
 }

 } // namespace WebCore
	/*
	* Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies)
	* Copyright (C) 2009 Antonio Gomes <tonikitoo@webkit.org>
	*
	* All rights reserved.
	*
	* Redistribution and use in source and binary forms, with or without
	* modification, are permitted provided that the following conditions
	* are met:
	* 1. Redistributions of source code must retain the above copyright
	* notice, this list of conditions and the following disclaimer.
	* 2. Redistributions in binary form must reproduce the above copyright
	* notice, this list of conditions and the following disclaimer in the
	* documentation and/or other materials provided with the distribution.
	*
	* THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY
	* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
	* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE COMPUTER, INC. OR
	* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
	* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
	* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
	* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
	* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
	* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
	*/

	#include "config.h"
	#include "SpatialNavigation.h"

	#include "Frame.h"
	#include "FrameTree.h"
	#include "FrameView.h"
	#include "HTMLFrameOwnerElement.h"
	#include "IntRect.h"
	#include "Node.h"
	#include "RenderLayer.h"
	#include "Page.h"

	namespace WebCore {

	static long long spatialDistance(FocusDirection, const IntRect&, const IntRect&);
	static IntRect renderRectRelativeToRootDocument(RenderObject*);
	static RectsAlignment alignmentForRects(FocusDirection, const IntRect&, const IntRect&);
	static bool areRectsFullyAligned(FocusDirection, const IntRect&, const IntRect&);
	static bool areRectsPartiallyAligned(FocusDirection, const IntRect&, const IntRect&);
	static bool isRectInDirection(FocusDirection, const IntRect&, const IntRect&);
	static void deflateIfOverlapped(IntRect&, IntRect&);
	static bool checkNegativeCoordsForNode(Node*, const IntRect&);

	void distanceDataForNode(FocusDirection direction, Node* start, FocusCandidate& candidate)
	{
	RenderObject* startRender = start->renderer();
	if (!startRender) {
	candidate.distance = maxDistance();
	return;
	}

	RenderObject* destRender = candidate.node->renderer();
	if (!destRender) {
	candidate.distance = maxDistance();
	return;
	}

	IntRect curRect = renderRectRelativeToRootDocument(startRender);
	IntRect targetRect = renderRectRelativeToRootDocument(destRender);

	// The bounding rectangle of two consecutive nodes can overlap. In such cases,
	// deflate both.
	deflateIfOverlapped(curRect, targetRect);

	// If empty rects or negative width or height, bail out.
	if (curRect.isEmpty() \|\| targetRect.isEmpty()
	\|\| targetRect.width() <= 0 \|\| targetRect.height() <= 0) {
	candidate.distance = maxDistance();
	return;
	}

	// Negative coordinates can be used if node is scrolled up offscreen.
	if (!checkNegativeCoordsForNode(start, curRect)) {
	candidate.distance = maxDistance();
	return;
	}

	if (!checkNegativeCoordsForNode(candidate.node, targetRect)) {
	candidate.distance = maxDistance();
	return;
	}

	if (!isRectInDirection(direction, curRect, targetRect)) {
	candidate.distance = maxDistance();
	return;
	}

	// The distance between two nodes is not to be considered alone when evaluating/looking
	// for the best focus candidate node. Alignment of rects can be also a good point to be
	// considered in order to make the algorithm to behavior in a more intuitive way.
	candidate.alignment = alignmentForRects(direction, curRect, targetRect);
	candidate.distance = spatialDistance(direction, curRect, targetRect);
	}

	// FIXME: This function does not behave correctly with transformed frames.
	static IntRect renderRectRelativeToRootDocument(RenderObject* render)
	{
	ASSERT(render && render->node());

	IntRect rect = render->node()->getRect();

	// In cases when the \|render\|'s associated node is in a scrollable inner
	// document, we only consider its scrollOffset if it is not offscreen.
	Node* node = render->node();
	Document* mainDocument = node->document()->page()->mainFrame()->document();
	bool considerScrollOffset = !(hasOffscreenRect(node) && node->document() != mainDocument);

	if (considerScrollOffset) {
	if (FrameView* frameView = render->node()->document()->view())
	rect.move(-frameView->scrollOffset());
	}

	// Handle nested frames.
	for (Frame* frame = render->document()->frame(); frame; frame = frame->tree()->parent()) {
	if (Element* element = static_cast<Element*>(frame->ownerElement())) {
	do {
	rect.move(element->offsetLeft(), element->offsetTop());
	} while ((element = element->offsetParent()));
	}
	}

	return rect;
	}

	static RectsAlignment alignmentForRects(FocusDirection direction, const IntRect& curRect, const IntRect& targetRect)
	{
	if (areRectsFullyAligned(direction, curRect, targetRect))
	return Full;

	if (areRectsPartiallyAligned(direction, curRect, targetRect))
	return Partial;

	return None;
	}

	static inline bool isHorizontalMove(FocusDirection direction)
	{
	return direction == FocusDirectionLeft \|\| direction == FocusDirectionRight;
	}

	static inline int start(FocusDirection direction, const IntRect& rect)
	{
	return isHorizontalMove(direction) ? rect.y() : rect.x();
	}

	static inline int middle(FocusDirection direction, const IntRect& rect)
	{
	IntPoint center(rect.center());
	return isHorizontalMove(direction) ? center.y(): center.x();
	}

	static inline int end(FocusDirection direction, const IntRect& rect)
	{
	return isHorizontalMove(direction) ? rect.bottom() : rect.right();
	}

	// This method checks if rects \|a\| and \|b\| are fully aligned either vertically or
	// horizontally. In general, rects whose central point falls between the top or
	// bottom of each other are considered fully aligned.
	// Rects that match this criteria are preferable target nodes in move focus changing
	// operations.
	// * a = Current focused node's rect.
	// * b = Focus candidate node's rect.
	static bool areRectsFullyAligned(FocusDirection direction, const IntRect& a, const IntRect& b)
	{
	int aStart, bStart, aEnd, bEnd;

	switch (direction) {
	case FocusDirectionLeft:
	aStart = a.x();
	bEnd = b.right();
	break;
	case FocusDirectionRight:
	aStart = b.x();
	bEnd = a.right();
	break;
	case FocusDirectionUp:
	aStart = a.y();
	bEnd = b.y();
	break;
	case FocusDirectionDown:
	aStart = b.y();
	bEnd = a.y();
	break;
	default:
	ASSERT_NOT_REACHED();
	return false;
	}

	if (aStart < bEnd)
	return false;

	aStart = start(direction, a);
	bStart = start(direction, b);

	int aMiddle = middle(direction, a);
	int bMiddle = middle(direction, b);

	aEnd = end(direction, a);
	bEnd = end(direction, b);

	// Picture of the totally aligned logic:
	//
	// Horizontal Vertical Horizontal Vertical
	// ************************** ***************************
	// * _ * _ _ _ _ * * _ * _ _ *
	// * \|_\| _ * \|_\|_\|_\|_\| * * _ \|_\| * \|_\|_\| *
	// * \|_\|....\|_\| * . * * \|_\|....\|_\| * . *
	// * \|_\| \|_\| (1) . * * \|_\| \|_\| (2) . *
	// * \|_\| * _._ * * \|_\| * _ _._ _ *
	// * * \|_\|_\| * * * \|_\|_\|_\|_\| *
	// * * * * * *
	// ************************** ***************************

	// Horizontal Vertical Horizontal Vertical
	// ************************** ***************************
	// * _......_ * _ _ _ _ * * _ * _ _ _ _ *
	// * \|_\| \|_\| * \|_\|_\|_\|_\| * * \|_\| _ * \|_\|_\|_\|_\| *
	// * \|_\| \|_\| * . * * \|_\| \|_\| * . *
	// * \|_\| (3) . * * \|_\|....\|_\| (4) . *
	// * * ._ _ * * * _ _. *
	// * * \|_\|_\| * * * \|_\|_\| *
	// * * * * * *
	// ************************** ***************************

	return ((bMiddle >= aStart && bMiddle <= aEnd) // (1)
	\|\| (aMiddle >= bStart && aMiddle <= bEnd) // (2)
	\|\| (bStart == aStart) // (3)
	\|\| (bEnd == aEnd)); // (4)
	}

	// This method checks if \|start\| and \|dest\| have a partial intersection, either
	// horizontally or vertically.
	// * a = Current focused node's rect.
	// * b = Focus candidate node's rect.
	static bool areRectsPartiallyAligned(FocusDirection direction, const IntRect& a, const IntRect& b)
	{
	int aStart = start(direction, a);
	int bStart = start(direction, b);
	int bMiddle = middle(direction, b);
	int aEnd = end(direction, a);
	int bEnd = end(direction, b);

	// Picture of the partially aligned logic:
	//
	// Horizontal Vertical
	// ********************************
	// * _ * _ _ _ *
	// * \|_\| * \|_\|_\|_\| *
	// * \|_\|.... _ * . . *
	// * \|_\| \|_\| * . . *
	// * \|_\|....\|_\| * ._._ _ *
	// * \|_\| * \|_\|_\|_\| *
	// * \|_\| * *
	// * * *
	// ********************************
	//
	// ... and variants of the above cases.
	return ((bStart >= aStart && bStart <= aEnd)
	\|\| (bStart >= aStart && bStart <= aEnd)
	\|\| (bEnd >= aStart && bEnd <= aEnd)
	\|\| (bMiddle >= aStart && bMiddle <= aEnd)
	\|\| (bEnd >= aStart && bEnd <= aEnd));
	}

	// Return true if rect \|a\| is below \|b\|. False otherwise.
	static inline bool below(const IntRect& a, const IntRect& b)
	{
	return a.y() > b.bottom();
	}

	// Return true if rect \|a\| is on the right of \|b\|. False otherwise.
	static inline bool rightOf(const IntRect& a, const IntRect& b)
	{
	return a.x() > b.right();
	}

	// * a = Current focused node's rect.
	// * b = Focus candidate node's rect.
	static long long spatialDistance(FocusDirection direction, const IntRect& a, const IntRect& b)
	{
	int x1 = 0, y1 = 0, x2 = 0, y2 = 0;

	if (direction == FocusDirectionLeft) {
	// #1 \|--\|
	//
	// #2 \|--\| \|--\|
	//
	// #3 \|--\|

	x1 = a.x();
	x2 = b.right();

	if (below(a, b)) {
	// #1 The a rect is below b.
	y1 = a.y();
	y2 = b.bottom();
	} else if (below(b, a)) {
	// #3 The b rect is below a.
	y1 = a.bottom();
	y2 = b.y();
	} else {
	// #2 Both b and a share some common y's.
	y1 = 0;
	y2 = 0;
	}
	} else if (direction == FocusDirectionRight) {
	// \|--\| #1
	//
	// \|--\| \|--\| #2
	//
	// \|--\| #3

	x1 = a.right();
	x2 = b.x();

	if (below(a, b)) {
	// #1 The b rect is above a.
	y1 = a.y();
	y2 = b.bottom();
	} else if (below(b, a)) {
	// #3 The b rect is below a.
	y1 = a.bottom();
	y2 = b.y();
	} else {
	// #2 Both b and a share some common y's.
	y1 = 0;
	y2 = 0;
	}
	} else if (direction == FocusDirectionUp) {
	//
	// #1 #2 #3
	//
	// \|--\| \|--\| \|--\|
	//
	// \|--\|

	y1 = a.y();
	y2 = b.bottom();

	if (rightOf(a, b)) {
	// #1 The b rect is to the left of a.
	x1 = a.x();
	x2 = b.right();
	} else if (rightOf(b, a)) {
	// #3 The b rect is to the right of a.
	x1 = a.right();
	x2 = b.x();
	} else {
	// #2 Both b and a share some common x's.
	x1 = 0;
	x2 = 0;
	}
	} else if (direction == FocusDirectionDown) {
	// \|--\|
	//
	// \|--\| \|--\| \|--\|
	//
	// #1 #2 #3

	y1 = a.bottom();
	y2 = b.y();

	if (rightOf(a, b)) {
	// #1 The b rect is to the left of a.
	x1 = a.x();
	x2 = b.right();
	} else if (rightOf(b, a)) {
	// #3 The b rect is to the right of a
	x1 = a.right();
	x2 = b.x();
	} else {
	// #2 Both b and a share some common x's.
	x1 = 0;
	x2 = 0;
	}
	}

	long long dx = x1 - x2;
	long long dy = y1 - y2;

	long long distance = (dx * dx) + (dy * dy);

	if (distance < 0)
	distance *= -1;

	return distance;
	}

	static bool isRectInDirection(FocusDirection direction, const IntRect& curRect, const IntRect& targetRect)
	{
	IntPoint center(targetRect.center());
	int targetMiddle = isHorizontalMove(direction) ? center.x() : center.y();

	switch (direction) {
	case FocusDirectionLeft:
	return targetMiddle < curRect.x();
	case FocusDirectionRight:
	return targetMiddle > curRect.right();
	case FocusDirectionUp:
	return targetMiddle < curRect.y();
	case FocusDirectionDown:
	return targetMiddle > curRect.bottom();
	default:
	ASSERT_NOT_REACHED();
	}

	return false;
	}

	// Checks if \|node\| is offscreen the visible area (viewport) of its container
	// document. In case it is, one can scroll in direction or take any different
	// desired action later on.
	bool hasOffscreenRect(Node* node)
	{
	// Get the FrameView in which \|node\| is (which means the current viewport if \|node\|
	// is not in an inner document), so we can check if its content rect is visible
	// before we actually move the focus to it.
	FrameView* frameView = node->document()->view();
	if (!frameView)
	return true;

	IntRect containerViewportRect = frameView->visibleContentRect();

	RenderObject* render = node->renderer();
	if (!render)
	return true;

	IntRect rect(render->absoluteClippedOverflowRect());
	if (rect.isEmpty())
	return true;

	return !containerViewportRect.intersects(rect);
	}

	// In a bottom-up way, this method tries to scroll \|frame\| in a given direction
	// \|direction\|, going up in the frame tree hierarchy in case it does not succeed.
	bool scrollInDirection(Frame* frame, FocusDirection direction, const FocusCandidate& candidate)
	{
	if (!frame)
	return false;

	ScrollDirection scrollDirection;

	switch (direction) {
	case FocusDirectionLeft:
	scrollDirection = ScrollLeft;
	break;
	case FocusDirectionRight:
	scrollDirection = ScrollRight;
	break;
	case FocusDirectionUp:
	scrollDirection = ScrollUp;
	break;
	case FocusDirectionDown:
	scrollDirection = ScrollDown;
	break;
	default:
	return false;
	}

	if (!candidate.isNull() && isScrollableContainerNode(candidate.enclosingScrollableBox))
	return frame->eventHandler()->scrollRecursively(scrollDirection, ScrollByLine, candidate.enclosingScrollableBox);

	return frame->eventHandler()->scrollRecursively(scrollDirection, ScrollByLine);
	}

	void scrollIntoView(Element* element)
	{
	// NOTE: Element's scrollIntoView method could had been used here, but
	// it is preferable to inflate \|element\|'s bounding rect a bit before
	// scrolling it for accurate reason.
	// Element's scrollIntoView method does not provide this flexibility.
	IntRect bounds = element->getRect();
	bounds.inflate(fudgeFactor());
	element->renderer()->enclosingLayer()->scrollRectToVisible(bounds);
	}

	bool isInRootDocument(Node* node)
	{
	if (!node)
	return false;

	Document* rootDocument = node->document()->page()->mainFrame()->document();
	return node->document() == rootDocument;
	}

	static void deflateIfOverlapped(IntRect& a, IntRect& b)
	{
	if (!a.intersects(b) \|\| a.contains(b) \|\| b.contains(a))
	return;

	int deflateFactor = -fudgeFactor();

	// Avoid negative width or height values.
	if ((a.width() + 2 * deflateFactor > 0) && (a.height() + 2 * deflateFactor > 0))
	a.inflate(deflateFactor);

	if ((b.width() + 2 * deflateFactor > 0) && (b.height() + 2 * deflateFactor > 0))
	b.inflate(deflateFactor);
	}

	static bool checkNegativeCoordsForNode(Node* node, const IntRect& curRect)
	{
	ASSERT(node \|\| node->renderer());

	if (curRect.x() >= 0 && curRect.y() >= 0)
	return true;

	bool canBeScrolled = false;

	RenderObject* renderer = node->renderer();
	for (; renderer; renderer = renderer->parent()) {
	if (renderer->isBox() && toRenderBox(renderer)->canBeScrolledAndHasScrollableArea()) {
	canBeScrolled = true;
	break;
	}
	}

	return canBeScrolled;
	}

	bool isScrollableContainerNode(Node* node)
	{
	if (!node)
	return false;

	if (RenderObject* renderer = node->renderer()) {
	return (renderer->isBox() && toRenderBox(renderer)->canBeScrolledAndHasScrollableArea()
	&& node->hasChildNodes() && !node->isDocumentNode());
	}

	return false;
	}

	bool isNodeDeepDescendantOfDocument(Node* node, Document* baseDocument)
	{
	if (!node \|\| !baseDocument)
	return false;

	bool descendant = baseDocument == node->document();

	Element* currentElement = static_cast<Element*>(node);
	while (!descendant) {
	Element* documentOwner = currentElement->document()->ownerElement();
	if (!documentOwner)
	break;

	descendant = documentOwner->document() == baseDocument;
	currentElement = documentOwner;
	}

	return descendant;
	}

	} // namespace WebCore