| 1 | package com.github.sanity.pav.spline | |
| 2 | ||
| 3 | import com.github.sanity.pav.toArrayList | |
| 4 | import java.lang.Math.pow | |
| 5 | import java.lang.Math.sqrt | |
| 6 | import java.util.* | |
| 7 | ||
| 8 | /** | |
| 9 | * An implementation of the Fritsch-Carlson algorithm for interpolant selection described by | |
| 10 | * [Monotone cubic interpolation](https://en.wikipedia.org/wiki/Monotone_cubic_interpolation). | |
| 11 | **/ | |
| 12 | class FritschCarlsonTangentStrategy : TangentStrategy { | |
| 13 | /* | |
| 14 | * The code is intended to model the description in the Wikipedia article closely (as of 06:26, 14 May 2016), | |
| 15 | * right down to the use of greek letters. | |
| 16 | * | |
| 17 | * I'm sure there are more elegant ways to implement the algorithm, it's not at all functional, but this seemed like | |
| 18 | * the best way to ensure correctness without me having an intuitive understanding of the algorithm, which | |
| 19 | * I haven't bothered to do. | |
| 20 | * | |
| 21 | * - [Ian](https://github.com/sanity) | |
| 22 | */ | |
| 23 | ||
| 24 | override fun compute(points: Iterable<PointWithSecants>): ArrayList<PointWithTangents> { | |
| 25 | val tangents = initTangentsToSecantAverages(points) | |
| 26 |
1
1. compute : mutated return of Object value for com/github/sanity/pav/spline/FritschCarlsonTangentStrategy::compute to ( if (x != null) null else throw new RuntimeException ) → KILLED |
return updateTangentsToEnsureMonotonicity(tangents) |
| 27 | ||
| 28 | } | |
| 29 | ||
| 30 | internal fun initTangentsToSecantAverages(points: Iterable<PointWithSecants>): ArrayList<PointWithTangents> { | |
| 31 | // See steps 1 and 2 | |
| 32 | return points.map { | |
| 33 | /* Wikipedia says that if secant signs differ then set tangent to zero, but how could secant | |
| 34 | * signs differ if input points are monotonic? | |
| 35 | */ | |
| 36 | val tangent: Double = | |
| 37 | when { | |
| 38 |
4
1. initTangentsToSecantAverages$pair_adjacent_violators_compileKotlin : Replaced double addition with subtraction → KILLED 2. initTangentsToSecantAverages$pair_adjacent_violators_compileKotlin : Replaced double division with multiplication → KILLED 3. initTangentsToSecantAverages$pair_adjacent_violators_compileKotlin : negated conditional → KILLED 4. initTangentsToSecantAverages$pair_adjacent_violators_compileKotlin : negated conditional → KILLED |
it.secantBefore != null && it.secantAfter != null -> (it.secantBefore.slope + it.secantAfter.slope) / 2.0 |
| 39 |
1
1. initTangentsToSecantAverages$pair_adjacent_violators_compileKotlin : negated conditional → KILLED |
it.secantBefore != null -> it.secantBefore.slope |
| 40 |
2
1. initTangentsToSecantAverages$pair_adjacent_violators_compileKotlin : removed call to kotlin/jvm/internal/Intrinsics::throwNpe → SURVIVED 2. initTangentsToSecantAverages$pair_adjacent_violators_compileKotlin : negated conditional → KILLED |
else -> it.secantAfter!!.slope // !! shouldn't be necessary, but smartcasting not smart enough yet |
| 41 | } | |
| 42 | PointWithTangents(it, tangent) | |
| 43 |
1
1. initTangentsToSecantAverages$pair_adjacent_violators_compileKotlin : mutated return of Object value for com/github/sanity/pav/spline/FritschCarlsonTangentStrategy::initTangentsToSecantAverages$pair_adjacent_violators_compileKotlin to ( if (x != null) null else throw new RuntimeException ) → KILLED |
}.toArrayList() |
| 44 | } | |
| 45 | ||
| 46 | internal fun updateTangentsToEnsureMonotonicity(pointsWithTangents: List<PointWithTangents>): ArrayList<PointWithTangents> { | |
| 47 | // See steps 3 to 5 | |
| 48 | val m = pointsWithTangents.map { it.tangent }.toArrayList() | |
| 49 | val Δ = pointsWithTangents.map { it.pointWithSecants.secantAfter }.filterNotNull().map { it.slope }.toArrayList() | |
| 50 | val y = pointsWithTangents.map { it.y }.toArrayList() | |
| 51 | val ignoreSteps4and5 = setTangentsTo0WhenTwoSuccessiveYValuesAreTheSame(m, y) | |
| 52 | val α = ArrayList<Double>(m.size) | |
| 53 | val β = ArrayList<Double>(m.size) | |
| 54 |
5
1. updateTangentsToEnsureMonotonicity$pair_adjacent_violators_compileKotlin : changed conditional boundary → SURVIVED 2. updateTangentsToEnsureMonotonicity$pair_adjacent_violators_compileKotlin : negated conditional → SURVIVED 3. updateTangentsToEnsureMonotonicity$pair_adjacent_violators_compileKotlin : negated conditional → SURVIVED 4. updateTangentsToEnsureMonotonicity$pair_adjacent_violators_compileKotlin : Changed increment from 1 to -1 → KILLED 5. updateTangentsToEnsureMonotonicity$pair_adjacent_violators_compileKotlin : Replaced integer subtraction with addition → KILLED |
for (k in 0..(m.size - 2)) { |
| 55 |
1
1. updateTangentsToEnsureMonotonicity$pair_adjacent_violators_compileKotlin : negated conditional → SURVIVED |
if (!ignoreSteps4and5.contains(k)) { |
| 56 |
1
1. updateTangentsToEnsureMonotonicity$pair_adjacent_violators_compileKotlin : Replaced double division with multiplication → SURVIVED |
α.add(m[k] / Δ[k]) |
| 57 |
2
1. updateTangentsToEnsureMonotonicity$pair_adjacent_violators_compileKotlin : Replaced double division with multiplication → SURVIVED 2. updateTangentsToEnsureMonotonicity$pair_adjacent_violators_compileKotlin : Replaced integer addition with subtraction → KILLED |
β.add(m[k + 1] / Δ[k]) |
| 58 |
1
1. updateTangentsToEnsureMonotonicity$pair_adjacent_violators_compileKotlin : removed call to com/github/sanity/pav/spline/FritschCarlsonTangentStrategy::ensureInputDataPointsAreStrictlyMonotone$pair_adjacent_violators_compileKotlin → SURVIVED |
ensureInputDataPointsAreStrictlyMonotone(k, α, β) |
| 59 |
1
1. updateTangentsToEnsureMonotonicity$pair_adjacent_violators_compileKotlin : removed call to com/github/sanity/pav/spline/FritschCarlsonTangentStrategy::ensureTangentsMeetConstraints$pair_adjacent_violators_compileKotlin → SURVIVED |
ensureTangentsMeetConstraints(k, m, Δ, α, β) |
| 60 | } | |
| 61 | } | |
| 62 |
1
1. updateTangentsToEnsureMonotonicity$pair_adjacent_violators_compileKotlin : mutated return of Object value for com/github/sanity/pav/spline/FritschCarlsonTangentStrategy::updateTangentsToEnsureMonotonicity$pair_adjacent_violators_compileKotlin to ( if (x != null) null else throw new RuntimeException ) → KILLED |
return pointsWithTangents.mapIndexed { k, pointWithTangents -> pointWithTangents.copy(tangent = m[k]) }.toArrayList() |
| 63 | } | |
| 64 | ||
| 65 | internal fun setTangentsTo0WhenTwoSuccessiveYValuesAreTheSame(m: ArrayList<Double>, y: ArrayList<Double>): Set<Int> { | |
| 66 | // See Step 3 | |
| 67 | val skipNextSteps = HashSet<Int>() | |
| 68 |
5
1. setTangentsTo0WhenTwoSuccessiveYValuesAreTheSame$pair_adjacent_violators_compileKotlin : changed conditional boundary → SURVIVED 2. setTangentsTo0WhenTwoSuccessiveYValuesAreTheSame$pair_adjacent_violators_compileKotlin : negated conditional → SURVIVED 3. setTangentsTo0WhenTwoSuccessiveYValuesAreTheSame$pair_adjacent_violators_compileKotlin : negated conditional → SURVIVED 4. setTangentsTo0WhenTwoSuccessiveYValuesAreTheSame$pair_adjacent_violators_compileKotlin : Changed increment from 1 to -1 → KILLED 5. setTangentsTo0WhenTwoSuccessiveYValuesAreTheSame$pair_adjacent_violators_compileKotlin : Replaced integer subtraction with addition → KILLED |
for (k in 0..(m.size - 2)) { |
| 69 |
2
1. setTangentsTo0WhenTwoSuccessiveYValuesAreTheSame$pair_adjacent_violators_compileKotlin : negated conditional → SURVIVED 2. setTangentsTo0WhenTwoSuccessiveYValuesAreTheSame$pair_adjacent_violators_compileKotlin : Replaced integer addition with subtraction → KILLED |
if (y[k] == y[k + 1]) { |
| 70 | m[k] = 0.0 | |
| 71 | skipNextSteps.add(k) | |
| 72 |
1
1. setTangentsTo0WhenTwoSuccessiveYValuesAreTheSame$pair_adjacent_violators_compileKotlin : Replaced integer addition with subtraction → NO_COVERAGE |
m[k + 1] = 0.0 |
| 73 |
1
1. setTangentsTo0WhenTwoSuccessiveYValuesAreTheSame$pair_adjacent_violators_compileKotlin : Replaced integer addition with subtraction → NO_COVERAGE |
skipNextSteps.add(k + 1) |
| 74 | } | |
| 75 | } | |
| 76 |
1
1. setTangentsTo0WhenTwoSuccessiveYValuesAreTheSame$pair_adjacent_violators_compileKotlin : mutated return of Object value for com/github/sanity/pav/spline/FritschCarlsonTangentStrategy::setTangentsTo0WhenTwoSuccessiveYValuesAreTheSame$pair_adjacent_violators_compileKotlin to ( if (x != null) null else throw new RuntimeException ) → KILLED |
return skipNextSteps |
| 77 | } | |
| 78 | ||
| 79 | ||
| 80 | internal fun ensureTangentsMeetConstraints(k: Int, m: ArrayList<Double>, Δ: ArrayList<Double>, α: ArrayList<Double>, β: ArrayList<Double>) { | |
| 81 | // See Step 5 | |
| 82 |
1
1. ensureTangentsMeetConstraints$pair_adjacent_violators_compileKotlin : Replaced double addition with subtraction → SURVIVED |
val vectorMagnitude = sqrt(pow(α[k], 2.0) + pow(β[k], 2.0)) |
| 83 |
2
1. ensureTangentsMeetConstraints$pair_adjacent_violators_compileKotlin : changed conditional boundary → SURVIVED 2. ensureTangentsMeetConstraints$pair_adjacent_violators_compileKotlin : negated conditional → KILLED |
if (vectorMagnitude > 3.0) { |
| 84 |
1
1. ensureTangentsMeetConstraints$pair_adjacent_violators_compileKotlin : Replaced double division with multiplication → NO_COVERAGE |
val Γk = 3.0 / vectorMagnitude |
| 85 |
2
1. ensureTangentsMeetConstraints$pair_adjacent_violators_compileKotlin : Replaced double multiplication with division → NO_COVERAGE 2. ensureTangentsMeetConstraints$pair_adjacent_violators_compileKotlin : Replaced double multiplication with division → NO_COVERAGE |
m[k] = Γk * α[k] * Δ[k] |
| 86 |
3
1. ensureTangentsMeetConstraints$pair_adjacent_violators_compileKotlin : Replaced integer addition with subtraction → NO_COVERAGE 2. ensureTangentsMeetConstraints$pair_adjacent_violators_compileKotlin : Replaced double multiplication with division → NO_COVERAGE 3. ensureTangentsMeetConstraints$pair_adjacent_violators_compileKotlin : Replaced double multiplication with division → NO_COVERAGE |
m[k + 1] = Γk * β[k] * Δ[k] |
| 87 | } | |
| 88 | } | |
| 89 | ||
| 90 | internal fun ensureInputDataPointsAreStrictlyMonotone(k: Int, α: ArrayList<Double>, β: ArrayList<Double>) { | |
| 91 |
4
1. ensureInputDataPointsAreStrictlyMonotone$pair_adjacent_violators_compileKotlin : changed conditional boundary → SURVIVED 2. ensureInputDataPointsAreStrictlyMonotone$pair_adjacent_violators_compileKotlin : changed conditional boundary → SURVIVED 3. ensureInputDataPointsAreStrictlyMonotone$pair_adjacent_violators_compileKotlin : negated conditional → KILLED 4. ensureInputDataPointsAreStrictlyMonotone$pair_adjacent_violators_compileKotlin : negated conditional → KILLED |
if ((α[k] < 0.0) || β[k] < 0.0) { |
| 92 | throw IllegalArgumentException("Input datapoints are not strictly monotone") | |
| 93 | } | |
| 94 | } | |
| 95 | } | |
Mutations | ||
| 26 |
1.1 |
|
| 38 |
1.1 2.2 3.3 4.4 |
|
| 39 |
1.1 |
|
| 40 |
1.1 2.2 |
|
| 43 |
1.1 |
|
| 54 |
1.1 2.2 3.3 4.4 5.5 |
|
| 55 |
1.1 |
|
| 56 |
1.1 |
|
| 57 |
1.1 2.2 |
|
| 58 |
1.1 |
|
| 59 |
1.1 |
|
| 62 |
1.1 |
|
| 68 |
1.1 2.2 3.3 4.4 5.5 |
|
| 69 |
1.1 2.2 |
|
| 72 |
1.1 |
|
| 73 |
1.1 |
|
| 76 |
1.1 |
|
| 82 |
1.1 |
|
| 83 |
1.1 2.2 |
|
| 84 |
1.1 |
|
| 85 |
1.1 2.2 |
|
| 86 |
1.1 2.2 3.3 |
|
| 91 |
1.1 2.2 3.3 4.4 |
|
| 98 |
1.1 |
|
| 102 |
1.1 |
|
| 106 |
1.1 |
|
| 110 |
1.1 |
|
| 114 |
1.1 |
|
| 119 |
1.1 |
|
| 120 |
1.1 |