splittableLabels.scala

import scala.math.BigInt

/** Common math utilities */
object MathUtils:
  @annotation.tailrec
  def gcd(a: BigInt, b: BigInt): BigInt =
    if b == 0 then a.abs else gcd(b, a % b)

//////////////////////////////////////////////////////////////
// 1. Rational labels : p / q  ------------------------------------------------
//////////////////////////////////////////////////////////////
final case class RationalLabel private (n: BigInt, d: BigInt):
  require(d > 0, s"denominator must be positive, got $d")

  /** Arithmetic mean strictly between this and that */
  def between(that: RationalLabel): RationalLabel =
    RationalLabel((n * that.d) + (that.n * d), 2 * d * that.d)

  override def toString(): String = s"$n/$d"

object RationalLabel:
  /** Public factory – always returns a reduced fraction */
  def apply(n: BigInt, d: BigInt): RationalLabel =
    val g = MathUtils.gcd(n, d)
    new RationalLabel(n / g, d / g)

  /** Initial sequence 0, 1, 2, … (size = len) */
  def init(len: Int): Vector[RationalLabel] =
    Vector.tabulate(len)(i => RationalLabel(i, 1))


  given Ordering[RationalLabel] with
    def compare(a: RationalLabel, b: RationalLabel): Int =
      (a.n * b.d - b.n * a.d).sign.toInt

//////////////////////////////////////////////////////////////
// 2. Dyadic labels : k / 2^exp  ---------------------------------------------
//////////////////////////////////////////////////////////////
final case class DyadicLabel private (k: BigInt, exp: Int):
  /** Numeric value (for debugging only) */
  def toDouble: Double = k.toDouble / (1L << exp)

  /** Label strictly between this and that */
  def between(that: DyadicLabel): DyadicLabel =
    val m  = math.max(exp, that.exp) + 1           // one more bit of precision
    val k1 = k    << (m - exp)                     // scale to common denominator
    val k2 = that.k << (m - that.exp)
    val mid = (k1 + k2) >> 1                       // divide by 2 (safe: even)
    DyadicLabel(mid, m)

  override def toString(): String =
    s"$k/(2^$exp)"

object DyadicLabel:
  def apply(k: BigInt, exp: Int): DyadicLabel = new DyadicLabel(k, exp) // no reduction needed

  /** Initial sequence 0, 1, 2, … (denominator = 1) */
  def init(len: Int): Vector[DyadicLabel] =
    Vector.tabulate(len)(i => DyadicLabel(i, 0))

  given Ordering[DyadicLabel] with
    def compare(a: DyadicLabel, b: DyadicLabel): Int =
      val m  = math.max(a.exp, b.exp)
      val ka = a.k << (m - a.exp)
      val kb = b.k << (m - b.exp)
      (ka - kb).sign.toInt

//////////////////////////////////////////////////////////////
// 3. Stern–Brocot labels : p / q  -------------------------------------------
//////////////////////////////////////////////////////////////
final case class SBLabel private (p: BigInt, q: BigInt):
  require(q > 0, s"denominator must be positive, got $q")

  /** Mediant (p+p')/(q+q') lies between the two fractions */
  def between(that: SBLabel): SBLabel =
    SBLabel(p + that.p, q + that.q)

  override def toString(): String = s"$p/$q"

object SBLabel:
  def apply(p: BigInt, q: BigInt): SBLabel =
    val g = MathUtils.gcd(p, q)
    new SBLabel(p / g, q / g)

  /** Initial sequence 0/1, 1/1, 2/1, … */
  def init(len: Int): Vector[SBLabel] =
    Vector.tabulate(len)(i => SBLabel(i, 1))

  given Ordering[SBLabel] with
    def compare(a: SBLabel, b: SBLabel): Int =
      (a.p * b.q - b.p * a.q).sign.toInt


//

def splitR(xs: Seq[RationalLabel]): Seq[RationalLabel] =
  (xs :+ xs(0).between(xs(1))).sorted

val xs = RationalLabel.init(2)
println(xs)
val xs2 = splitR(splitR(splitR(xs)))
println(xs2)

def splitD(xs: Seq[DyadicLabel]): Seq[DyadicLabel] =
  (xs :+ xs(0).between(xs(1))).sorted

val ys = DyadicLabel.init(2)
println(ys)
val ys2 = splitD(splitD(splitD(ys)))
println(ys2)


def splitS(xs: Seq[SBLabel]): Seq[SBLabel] =
  (xs :+ xs(0).between(xs(1))).sorted

val zs = SBLabel.init(2)
println(zs)
val zs2 = splitS(splitS(splitS(zs)))
println(zs2)