From 89cf7af9b824efab454edcbc81523b378bd42e86 Mon Sep 17 00:00:00 2001 From: Max Smirnov Date: Sat, 25 May 2024 16:11:26 +0300 Subject: [PATCH 1/7] Simplify removeById --- core/src/main/scala/HasId.scala | 10 ++++------ 1 file changed, 4 insertions(+), 6 deletions(-) diff --git a/core/src/main/scala/HasId.scala b/core/src/main/scala/HasId.scala index d7fa2738e..b11b58390 100644 --- a/core/src/main/scala/HasId.scala +++ b/core/src/main/scala/HasId.scala @@ -15,12 +15,10 @@ trait HasId[A, Id]: xs.removeById(v.id) def removeById(id: Id): List[A] = - xs.foldLeft((false, List.empty[A])) { (acc, v) => - if acc._1 then (acc._1, v :: acc._2) - else if v.hasId(id) then (true, acc._2) - else (false, v :: acc._2) - }._2 - .reverse + xs match + case (v :: vs) if v.hasId(id) => vs + case (v :: vs) => v :: vs.removeById(id) + case Nil => Nil trait Mergeable[A]: From 704252b2446141b619e7f31ad36463cd08e0c4a6 Mon Sep 17 00:00:00 2001 From: Max Smirnov Date: Sat, 25 May 2024 16:22:43 +0300 Subject: [PATCH 2/7] Fix format --- core/src/main/scala/HasId.scala | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/core/src/main/scala/HasId.scala b/core/src/main/scala/HasId.scala index b11b58390..09177e4e0 100644 --- a/core/src/main/scala/HasId.scala +++ b/core/src/main/scala/HasId.scala @@ -17,8 +17,8 @@ trait HasId[A, Id]: def removeById(id: Id): List[A] = xs match case (v :: vs) if v.hasId(id) => vs - case (v :: vs) => v :: vs.removeById(id) - case Nil => Nil + case (v :: vs) => v :: vs.removeById(id) + case Nil => Nil trait Mergeable[A]: From 12339917088597180753d0bb2024b7f987f9a837 Mon Sep 17 00:00:00 2001 From: Thanh Le Date: Sun, 26 May 2024 10:27:21 +0700 Subject: [PATCH 3/7] Add tests for HasId.removeById --- test-kit/src/test/scala/HasIdTest.scala | 17 +++++++++++++---- 1 file changed, 13 insertions(+), 4 deletions(-) diff --git a/test-kit/src/test/scala/HasIdTest.scala b/test-kit/src/test/scala/HasIdTest.scala index 51c7169a0..d6923b115 100644 --- a/test-kit/src/test/scala/HasIdTest.scala +++ b/test-kit/src/test/scala/HasIdTest.scala @@ -1,20 +1,29 @@ package chess import munit.ScalaCheckSuite -import org.scalacheck.Prop.forAll +import org.scalacheck.Prop.{ forAll, propBoolean } class HasIdTest extends ScalaCheckSuite: given HasId[Int, Int] with extension (a: Int) def id: Int = a - test("removeById.size <= size"): + test("if there is no id, removeById does nothing"): forAll: (xs: List[Int], id: Int) => - val removed = xs.removeById(id) - xs.size == removed.size || xs.size == removed.size + 1 + xs.indexOf(id) == -1 ==> (xs.removeById(id) == xs) test("removeById.size <= size"): forAll: (xs: List[Int], id: Int) => val removed = xs.removeById(id) val epsilon = if xs.find(_ == id).isDefined then 1 else 0 xs.size == removed.size + epsilon + + test("removeById reserves order"): + forAll: (xs: List[Int], id: Int) => + val sorted = xs.sorted + val removed = sorted.removeById(id) + removed == removed.sorted + + test("removeById only remove first items"): + val xs = List(1, 1) + xs.removeById(1) == List(1) From ae55f1ae3033cc6477e8572c219ba18338c83eba Mon Sep 17 00:00:00 2001 From: Thanh Le Date: Sun, 26 May 2024 10:28:05 +0700 Subject: [PATCH 4/7] Better test for remove first item --- test-kit/src/test/scala/HasIdTest.scala | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/test-kit/src/test/scala/HasIdTest.scala b/test-kit/src/test/scala/HasIdTest.scala index d6923b115..ae41023a9 100644 --- a/test-kit/src/test/scala/HasIdTest.scala +++ b/test-kit/src/test/scala/HasIdTest.scala @@ -25,5 +25,5 @@ class HasIdTest extends ScalaCheckSuite: removed == removed.sorted test("removeById only remove first items"): - val xs = List(1, 1) - xs.removeById(1) == List(1) + val xs = List(1, 2, 1) + xs.removeById(1) == List(2, 1) From b246088b430ab11a3d2fac45930b985940161e6b Mon Sep 17 00:00:00 2001 From: Thanh Le Date: Sun, 26 May 2024 10:32:18 +0700 Subject: [PATCH 5/7] Add comment to HasId.removeById --- core/src/main/scala/HasId.scala | 4 ++++ 1 file changed, 4 insertions(+) diff --git a/core/src/main/scala/HasId.scala b/core/src/main/scala/HasId.scala index 09177e4e0..0d403cf3f 100644 --- a/core/src/main/scala/HasId.scala +++ b/core/src/main/scala/HasId.scala @@ -14,6 +14,10 @@ trait HasId[A, Id]: def remove(v: A): List[A] = xs.removeById(v.id) + // Remove first item with the given id + // if there is no match return the original list + // This behavior is to accomodate the lila study tree current implementation + // We should change it after We finally migrate it to this new tree def removeById(id: Id): List[A] = xs match case (v :: vs) if v.hasId(id) => vs From c5f9adf701e2cc4cacf55171f6ec702e9e324d5b Mon Sep 17 00:00:00 2001 From: Thanh Le Date: Sun, 26 May 2024 10:34:47 +0700 Subject: [PATCH 6/7] Use tailrec to eliminate recursive --- core/src/main/scala/HasId.scala | 15 +++++++++------ 1 file changed, 9 insertions(+), 6 deletions(-) diff --git a/core/src/main/scala/HasId.scala b/core/src/main/scala/HasId.scala index 0d403cf3f..673d18a8c 100644 --- a/core/src/main/scala/HasId.scala +++ b/core/src/main/scala/HasId.scala @@ -11,18 +11,21 @@ trait HasId[A, Id]: inline def hasId(id: Id): Boolean = a.id == id extension (xs: List[A]) - def remove(v: A): List[A] = + final def remove(v: A): List[A] = xs.removeById(v.id) // Remove first item with the given id // if there is no match return the original list // This behavior is to accomodate the lila study tree current implementation // We should change it after We finally migrate it to this new tree - def removeById(id: Id): List[A] = - xs match - case (v :: vs) if v.hasId(id) => vs - case (v :: vs) => v :: vs.removeById(id) - case Nil => Nil + final def removeById(id: Id): List[A] = + @tailrec + def loop (acc: List[A], rest: List[A]): List[A] = + rest match + case Nil => acc + case (v :: vs) if v.hasId(id) => acc ++ vs + case (v :: vs) => loop(acc :+ v, vs) + loop(Nil, xs) trait Mergeable[A]: From 2ce453745afbc35141de3271ffd014206e787b5d Mon Sep 17 00:00:00 2001 From: Thanh Le Date: Sun, 26 May 2024 10:37:57 +0700 Subject: [PATCH 7/7] Run prepare --- core/src/main/scala/HasId.scala | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/core/src/main/scala/HasId.scala b/core/src/main/scala/HasId.scala index 673d18a8c..cc04cfee9 100644 --- a/core/src/main/scala/HasId.scala +++ b/core/src/main/scala/HasId.scala @@ -20,11 +20,11 @@ trait HasId[A, Id]: // We should change it after We finally migrate it to this new tree final def removeById(id: Id): List[A] = @tailrec - def loop (acc: List[A], rest: List[A]): List[A] = + def loop(acc: List[A], rest: List[A]): List[A] = rest match - case Nil => acc case (v :: vs) if v.hasId(id) => acc ++ vs - case (v :: vs) => loop(acc :+ v, vs) + case (v :: vs) => loop(acc :+ v, vs) + case Nil => acc loop(Nil, xs) trait Mergeable[A]: