/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */

/* vim: set ts=8 sts=2 et sw=2 tw=80: */

/* This Source Code Form is subject to the terms of the Mozilla Public

 * License, v. 2.0. If a copy of the MPL was not distributed with this

 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#include "DottedCornerFinder.h"

#include "mozilla/Move.h"

#include "BorderCache.h"

#include "BorderConsts.h"

namespace mozilla {

using namespace gfx;

static inline Float

Square(Float x)

{

  return x * x;

}

static Point

PointRotateCCW90(const Point& aP)

{

  return Point(aP.y, -aP.x);

}

struct BestOverlap

{

  Float overlap;

  size_t count;

  BestOverlap()

    : overlap(0.0f)

    , count(0)

  {

  }

  BestOverlap(Float aOverlap, size_t aCount)

    : overlap(aOverlap)

    , count(aCount)

  {

  }

};

static const size_t DottedCornerCacheSize = 256;

nsDataHashtable<FourFloatsHashKey, BestOverlap> DottedCornerCache;

DottedCornerFinder::DottedCornerFinder(const Bezier& aOuterBezier,

                                       const Bezier& aInnerBezier,

                                       Corner aCorner,

                                       Float aBorderRadiusX,

                                       Float aBorderRadiusY,

                                       const Point& aC0,

                                       Float aR0,

                                       const Point& aCn,

                                       Float aRn,

                                       const Size& aCornerDim)

  : mOuterBezier(aOuterBezier)

  , mInnerBezier(aInnerBezier)

  , mCorner(aCorner)

  , mNormalSign((aCorner == C_TL || aCorner == C_BR) ? -1.0f : 1.0f)

  , mC0(aC0)

  , mCn(aCn)

  , mR0(aR0)

  , mRn(aRn)

  , mMaxR(std::max(aR0, aRn))

  , mCenterCurveOrigin(mC0.x, mCn.y)

  , mCenterCurveR(0.0)

  , mInnerCurveOrigin(mInnerBezier.mPoints[0].x, mInnerBezier.mPoints[3].y)

  , mBestOverlap(0.0f)

  , mHasZeroBorderWidth(false)

  , mHasMore(true)

  , mMaxCount(aCornerDim.width + aCornerDim.height)

  , mType(OTHER)

  , mI(0)

  , mCount(0)

{

  NS_ASSERTION(mR0 > 0.0f || mRn > 0.0f,

               "At least one side should have non-zero radius.");

  mInnerWidth = fabs(mInnerBezier.mPoints[0].x - mInnerBezier.mPoints[3].x);

  mInnerHeight = fabs(mInnerBezier.mPoints[0].y - mInnerBezier.mPoints[3].y);

  DetermineType(aBorderRadiusX, aBorderRadiusY);

  Reset();

}

static bool

IsSingleCurve(Float aMinR,

              Float aMaxR,

              Float aMinBorderRadius,

              Float aMaxBorderRadius)

{

  return aMinR > 0.0f && aMinBorderRadius > aMaxR * 4.0f &&

         aMinBorderRadius / aMaxBorderRadius > 0.5f;

}

void

DottedCornerFinder::DetermineType(Float aBorderRadiusX, Float aBorderRadiusY)

{

  // Calculate parameters for the center curve before swap.

  Float centerCurveWidth = fabs(mC0.x - mCn.x);

  Float centerCurveHeight = fabs(mC0.y - mCn.y);

  Point cornerPoint(mCn.x, mC0.y);

  bool swapped = false;

  if (mR0 < mRn) {

    // Always draw from wider side to thinner side.

    Swap(mC0, mCn);

    Swap(mR0, mRn);

    Swap(mInnerBezier.mPoints[0], mInnerBezier.mPoints[3]);

    Swap(mInnerBezier.mPoints[1], mInnerBezier.mPoints[2]);

    Swap(mOuterBezier.mPoints[0], mOuterBezier.mPoints[3]);

    Swap(mOuterBezier.mPoints[1], mOuterBezier.mPoints[2]);

    mNormalSign = -mNormalSign;

    swapped = true;

  }

  // See the comment at mType declaration for each condition.

  Float minR = std::min(mR0, mRn);

  Float minBorderRadius = std::min(aBorderRadiusX, aBorderRadiusY);

  Float maxBorderRadius = std::max(aBorderRadiusX, aBorderRadiusY);

  if (IsSingleCurve(minR, mMaxR, minBorderRadius, maxBorderRadius)) {

    if (mR0 == mRn) {

      Float borderLength;

      if (minBorderRadius == maxBorderRadius) {

        mType = PERFECT;

        borderLength = M_PI * centerCurveHeight / 2.0f;

        mCenterCurveR = centerCurveWidth;

      } else {

        mType = SINGLE_CURVE_AND_RADIUS;

        borderLength =

          GetQuarterEllipticArcLength(centerCurveWidth, centerCurveHeight);

      }

      Float diameter = mR0 * 2.0f;

      size_t count = round(borderLength / diameter);

      if (count % 2) {

        count++;

      }

      mCount = count / 2 - 1;

      if (mCount > 0) {

        mBestOverlap = 1.0f - borderLength / (diameter * count);

      }

    } else {

      mType = SINGLE_CURVE;

    }

  }

  if (mType == SINGLE_CURVE_AND_RADIUS || mType == SINGLE_CURVE) {

    Size cornerSize(centerCurveWidth, centerCurveHeight);

    GetBezierPointsForCorner(&mCenterBezier, mCorner, cornerPoint, cornerSize);

    if (swapped) {

      Swap(mCenterBezier.mPoints[0], mCenterBezier.mPoints[3]);

      Swap(mCenterBezier.mPoints[1], mCenterBezier.mPoints[2]);

    }

  }

  if (minR == 0.0f) {

    mHasZeroBorderWidth = true;

  }

  if ((mType == SINGLE_CURVE || mType == OTHER) && !mHasZeroBorderWidth) {

    FindBestOverlap(minR, minBorderRadius, maxBorderRadius);

  }

}

bool

DottedCornerFinder::HasMore(void) const

{

  if (mHasZeroBorderWidth) {

    return mI < mMaxCount && mHasMore;

  }

  return mI < mCount;

}

DottedCornerFinder::Result

DottedCornerFinder::Next(void)

{

  mI++;

  if (mType == PERFECT) {

    Float phi = mI * 4.0f * mR0 * (1 - mBestOverlap) / mCenterCurveR;

    if (mCorner == C_TL) {

      phi = -M_PI / 2.0f - phi;

    } else if (mCorner == C_TR) {

      phi = -M_PI / 2.0f + phi;

    } else if (mCorner == C_BR) {

      phi = M_PI / 2.0f - phi;

    } else {

      phi = M_PI / 2.0f + phi;

    }

    Point C(mCenterCurveOrigin.x + mCenterCurveR * cos(phi),

            mCenterCurveOrigin.y + mCenterCurveR * sin(phi));

    return DottedCornerFinder::Result(C, mR0);

  }

  // Find unfilled and filled circles.

  (void)FindNext(mBestOverlap);

  if (mHasMore) {

    (void)FindNext(mBestOverlap);

  }

  return Result(mLastC, mLastR);

}

void

DottedCornerFinder::Reset(void)

{

  mLastC = mC0;

  mLastR = mR0;

  mLastT = 0.0f;

  mHasMore = true;

}

void

DottedCornerFinder::FindPointAndRadius(Point& C,

                                       Float& r,

                                       const Point& innerTangent,

                                       const Point& normal,

                                       Float t)

{

  // Find radius for the given tangent point on the inner curve such that the

  // circle is also tangent to the outer curve.

  NS_ASSERTION(mType == OTHER, "Wrong mType");

  Float lower = 0.0f;

  Float upper = mMaxR;

  const Float DIST_MARGIN = 0.1f;

  for (size_t i = 0; i < MAX_LOOP; i++) {

    r = (upper + lower) / 2.0f;

    C = innerTangent + normal * r;

    Point Near = FindBezierNearestPoint(mOuterBezier, C, t);

    Float distSquare = (C - Near).LengthSquare();

    if (distSquare > Square(r + DIST_MARGIN)) {

      lower = r;

    } else if (distSquare < Square(r - DIST_MARGIN)) {

      upper = r;

    } else {

      break;

    }

  }

}

Float

DottedCornerFinder::FindNext(Float overlap)

{

  Float lower = mLastT;

  Float upper = 1.0f;

  Float t;

  Point C = mLastC;

  Float r = 0.0f;

  Float factor = (1.0f - overlap);

  Float circlesDist = 0.0f;

  Float expectedDist = 0.0f;

  const Float DIST_MARGIN = 0.1f;

  if (mType == SINGLE_CURVE_AND_RADIUS) {

    r = mR0;

    expectedDist = (r + mLastR) * factor;

    // Find C_i on the center curve.

    for (size_t i = 0; i < MAX_LOOP; i++) {

      t = (upper + lower) / 2.0f;

      C = GetBezierPoint(mCenterBezier, t);

      // Check overlap along arc.

      circlesDist = GetBezierLength(mCenterBezier, mLastT, t);

      if (circlesDist < expectedDist - DIST_MARGIN) {

        lower = t;

      } else if (circlesDist > expectedDist + DIST_MARGIN) {

        upper = t;

      } else {

        break;

      }

    }

  } else if (mType == SINGLE_CURVE) {

    // Find C_i on the center curve, and calculate r_i.

    for (size_t i = 0; i < MAX_LOOP; i++) {

      t = (upper + lower) / 2.0f;

      C = GetBezierPoint(mCenterBezier, t);

      Point Diff = GetBezierDifferential(mCenterBezier, t);

      Float DiffLength = Diff.Length();

      if (DiffLength == 0.0f) {

        // Basically this shouldn't happen.

        // If differential is 0, we cannot calculate tangent circle,

        // skip this point.

        t = (t + upper) / 2.0f;

        continue;

      }

      Point normal = PointRotateCCW90(Diff / DiffLength) * (-mNormalSign);

      r = CalculateDistanceToEllipticArc(

        C, normal, mInnerCurveOrigin, mInnerWidth, mInnerHeight);

      // Check overlap along arc.

      circlesDist = GetBezierLength(mCenterBezier, mLastT, t);

      expectedDist = (r + mLastR) * factor;

      if (circlesDist < expectedDist - DIST_MARGIN) {

        lower = t;

      } else if (circlesDist > expectedDist + DIST_MARGIN) {

        upper = t;

      } else {

        break;

      }

    }

  } else {

    Float distSquareMax = Square(mMaxR * 3.0f);

    Float circlesDistSquare = 0.0f;

    // Find C_i and r_i.

    for (size_t i = 0; i < MAX_LOOP; i++) {

      t = (upper + lower) / 2.0f;

      Point innerTangent = GetBezierPoint(mInnerBezier, t);

      if ((innerTangent - mLastC).LengthSquare() > distSquareMax) {

        // It's clear that this tangent point is too far, skip it.

        upper = t;

        continue;

      }

      Point Diff = GetBezierDifferential(mInnerBezier, t);

      Float DiffLength = Diff.Length();

      if (DiffLength == 0.0f) {

        // Basically this shouldn't happen.

        // If differential is 0, we cannot calculate tangent circle,

        // skip this point.

        t = (t + upper) / 2.0f;

        continue;

      }

      Point normal = PointRotateCCW90(Diff / DiffLength) * mNormalSign;

      FindPointAndRadius(C, r, innerTangent, normal, t);

      // Check overlap with direct distance.

      circlesDistSquare = (C - mLastC).LengthSquare();

      expectedDist = (r + mLastR) * factor;

      if (circlesDistSquare < Square(expectedDist - DIST_MARGIN)) {

        lower = t;

      } else if (circlesDistSquare > Square(expectedDist + DIST_MARGIN)) {

        upper = t;

      } else {

        break;

      }

    }

    circlesDist = sqrt(circlesDistSquare);

  }

  if (mHasZeroBorderWidth) {

    // When calculating circle around r=0, it may result in wrong radius that

    // is bigger than previous circle.  Detect it and stop calculating.

    const Float R_MARGIN = 0.1f;

    if (mLastR < R_MARGIN && r > mLastR) {

      mHasMore = false;

      mLastR = 0.0f;

      return 0.0f;

    }

  }

  mLastT = t;

  mLastC = C;

  mLastR = r;

  if (mHasZeroBorderWidth) {

    const Float T_MARGIN = 0.001f;

    if (mLastT >= 1.0f - T_MARGIN ||

        (mLastC - mCn).LengthSquare() < Square(mLastR)) {

      mHasMore = false;

    }

  }

  if (expectedDist == 0.0f) {

    return 0.0f;

  }

  return 1.0f - circlesDist * factor / expectedDist;

}

void

DottedCornerFinder::FindBestOverlap(Float aMinR,

                                    Float aMinBorderRadius,

                                    Float aMaxBorderRadius)

{

  // If overlap is not calculateable, find it with binary search,

  // such that there exists i that C_i == C_n with the given overlap.

  FourFloats key(aMinR, mMaxR, aMinBorderRadius, aMaxBorderRadius);

  BestOverlap best;

  if (DottedCornerCache.Get(key, &best)) {

    mCount = best.count;

    mBestOverlap = best.overlap;

    return;

  }

  Float lower = 0.0f;

  Float upper = 0.5f;

  // Start from lower bound to find the minimum number of circles.

  Float overlap = 0.0f;

  mBestOverlap = overlap;

  size_t targetCount = 0;

  const Float OVERLAP_MARGIN = 0.1f;

  for (size_t j = 0; j < MAX_LOOP; j++) {

    Reset();

    size_t count;

    Float actualOverlap;

    if (!GetCountAndLastOverlap(overlap, &count, &actualOverlap)) {

      if (j == 0) {

        mCount = mMaxCount;

        break;

      }

    }

    if (j == 0) {

      if (count < 3 || (count == 3 && actualOverlap > 0.5f)) {

        // |count == 3 && actualOverlap > 0.5f| means there could be

        // a circle but it is too near from both ends.

        //

        // if actualOverlap == 0.0

        //               1       2       3

        //   +-------+-------+-------+-------+

        //   | ##### | ***** | ##### | ##### |

        //   |#######|*******|#######|#######|

        //   |###+###|***+***|###+###|###+###|

        //   |# C_0 #|* C_1 *|# C_2 #|# C_n #|

        //   | ##### | ***** | ##### | ##### |

        //   +-------+-------+-------+-------+

        //                   |

        //                   V

        //   +-------+---+-------+---+-------+

        //   | ##### |   | ##### |   | ##### |

        //   |#######|   |#######|   |#######|

        //   |###+###|   |###+###|   |###+###| Find the best overlap to place

        //   |# C_0 #|   |# C_1 #|   |# C_n #| C_1 at the middle of them

        //   | ##### |   | ##### |   | ##### |

        //   +-------+---+-------+---|-------+

        //

        // if actualOverlap == 0.5

        //               1       2     3

        //   +-------+-------+-------+---+

        //   | ##### | ***** | ##### |## |

        //   |#######|*******|##### C_n #|

        //   |###+###|***+***|###+###+###|

        //   |# C_0 #|* C_1 *|# C_2 #|###|

        //   | ##### | ***** | ##### |## |

        //   +-------+-------+-------+---+

        //                 |

        //                 V

        //   +-------+-+-------+-+-------+

        //   | ##### | | ##### | | ##### |

        //   |#######| |#######| |#######|

        //   |###+###| |###+###| |###+###| Even if we place C_1 at the middle

        //   |# C_0 #| |# C_1 #| |# C_n #| of them, it's too near from them

        //   | ##### | | ##### | | ##### |

        //   +-------+-+-------+-|-------+

        //                 |

        //                 V

        //   +-------+-----------+-------+

        //   | ##### |           | ##### |

        //   |#######|           |#######|

        //   |###+###|           |###+###| Do not draw any circle

        //   |# C_0 #|           |# C_n #|

        //   | ##### |           | ##### |

        //   +-------+-----------+-------+

        mCount = 0;

        break;

      }

      // targetCount should be 2n, as we're searching C_1 to C_n.

      //

      //   targetCount = 4

      //   mCount = 1

      //               1       2       3       4

      //   +-------+-------+-------+-------+-------+

      //   | ##### | ***** | ##### | ***** | ##### |

      //   |#######|*******|#######|*******|#######|

      //   |###+###|***+***|###+###|***+***|###+###|

      //   |# C_0 #|* C_1 *|# C_2 #|* C_3 *|# C_n #|

      //   | ##### | ***** | ##### | ***** | ##### |

      //   +-------+-------+-------+-------+-------+

      //                       1

      //

      //   targetCount = 6

      //   mCount = 2

      //               1       2       3       4       5       6

      //   +-------+-------+-------+-------+-------+-------+-------+

      //   | ##### | ***** | ##### | ***** | ##### | ***** | ##### |

      //   |#######|*******|#######|*******|#######|*******|#######|

      //   |###+###|***+***|###+###|***+***|###+###|***+***|###+###|

      //   |# C_0 #|* C_1 *|# C_2 #|* C_3 *|# C_4 #|* C_5 *|# C_n #|

      //   | ##### | ***** | ##### | ***** | ##### | ***** | ##### |

      //   +-------+-------+-------+-------+-------+-------+-------+

      //                       1               2

      if (count % 2) {

        targetCount = count + 1;

      } else {

        targetCount = count;

      }

      mCount = targetCount / 2 - 1;

    }

    if (count == targetCount) {

      mBestOverlap = overlap;

      if (fabs(actualOverlap - overlap) < OVERLAP_MARGIN) {

        break;

      }

      // We started from upper bound, no need to update range when j == 0.

      if (j > 0) {

        if (actualOverlap > overlap) {

          lower = overlap;

        } else {

          upper = overlap;

        }

      }

    } else {

      // |j == 0 && count != targetCount| means that |targetCount = count + 1|,

      // and we started from upper bound, no need to update range when j == 0.

      if (j > 0) {

        if (count > targetCount) {

          upper = overlap;

        } else {

          lower = overlap;

        }

      }

    }

    overlap = (upper + lower) / 2.0f;

  }

  if (DottedCornerCache.Count() > DottedCornerCacheSize) {

    DottedCornerCache.Clear();

  }

  DottedCornerCache.Put(key, BestOverlap(mBestOverlap, mCount));

}

bool

DottedCornerFinder::GetCountAndLastOverlap(Float aOverlap,

                                           size_t* aCount,

                                           Float* aActualOverlap)

{

  // Return the number of circles and the last circles' overlap for the

  // given overlap.

  Reset();

  const Float T_MARGIN = 0.001f;

  const Float DIST_MARGIN = 0.1f;

  const Float DIST_MARGIN_SQUARE = Square(DIST_MARGIN);

  for (size_t i = 0; i < mMaxCount; i++) {

    Float actualOverlap = FindNext(aOverlap);

    if (mLastT >= 1.0f - T_MARGIN ||

        (mLastC - mCn).LengthSquare() < DIST_MARGIN_SQUARE) {

      *aCount = i + 1;

      *aActualOverlap = actualOverlap;

      return true;

    }

  }

  return false;

}

} // namespace mozilla