Skip to content

Instantly share code, notes, and snippets.

@okumin
Last active August 29, 2015 14:20
Show Gist options
  • Save okumin/1f9b4378a6c0931ac214 to your computer and use it in GitHub Desktop.
Save okumin/1f9b4378a6c0931ac214 to your computer and use it in GitHub Desktop.
class MofuSpec extends WordSpec with GeneratorDrivenPropertyChecks {
def measure(seq: Seq[Int], heap: Heap[Int]): Unit = {
val h = seq.foldLeft(heap) { (h, x) => h.insert(x) }
val h2 = seq.foldLeft(h) { (h, x) => h.deleteMin() }
assert(h2.isEmpty)
}
"mofu" should {
"fumo" in {
val initial = 300000
val cases = Seq(initial, initial * 2, initial * 4, initial * 8)
//val factory = LeftistHeap
val factory = PairingHeap
// warm up のつもり
measure(1 to cases.last, factory.empty)
cases.foreach { i =>
val seq = (1 to i).map(_ => Random.nextInt())
//val seq = 1 to i
//val seq = (1 to i).reverse
//val heap = LeftistHeap(seq: _*)
//val queue = Queue(seq: _*)
//val deque = Deque(seq: _*)
val start = System.currentTimeMillis()
measure(seq, factory.empty)
//heap ++ seq
println(System.currentTimeMillis() - start)
}
fail()
}
}
}
@SerialVersionUID(6347333177234854462L)
sealed abstract class PairingHeap[A](implicit protected[this] val ord: Ordering[A])
extends Heap[A]
with Heap.Meldable[A, PairingHeap]
with Serializable {
final override def orderedCompanion: GenericOrderedCompanion[PairingHeap] = PairingHeap
final override protected[this] def newBuilder: mutable.Builder[A, PairingHeap[A]] = {
PairingHeap.newBuilder
}
final override def findMin: A = this match {
case Branch(v, _) => v
case Leaf() => throw new NoSuchElementException("This heap is empty.")
}
// 本のやつだとスタオバするので書き換えた。
// 1. リストの要素をマージ
// 2. マージ結果を畳み込んで1つの ParingHeapに
final override def deleteMin(): PairingHeap[A] = {
@tailrec
def mergePairs(heaps: List[Branch[A]], paired: List[PairingHeap[A]]): List[PairingHeap[A]] = {
heaps match {
case Nil => paired
case h :: Nil => h :: paired
case h1 :: h2 :: hs => mergePairs(hs, h1.meld(h2) :: paired)
}
}
this match {
case Leaf() => throw new NoSuchElementException("This heap is empty.")
case Branch(_, Nil) => Leaf()
case Branch(_, heaps) =>
mergePairs(heaps, Nil).foldLeft[PairingHeap[A]](Leaf()) { (acc, pair) => acc.meld(pair) }
}
}
final override def meld(that: PairingHeap[A]): PairingHeap[A] = (this, that) match {
case (Leaf(), h) => h
case (h, Leaf()) => h
case (Branch(v1, hs1), h2 @ Branch(v2, _)) if v1 <= v2 => Branch(v1, h2 :: hs1)
case (h1 @ Branch(_, _), Branch(v2, hs2)) => Branch(v2, h1 :: hs2)
}
}
object PairingHeap extends OrderedTraversableFactory[PairingHeap] {
implicit def canBuildFrom[A: Ordering]: CanBuildFrom[Coll, A, PairingHeap[A]] = {
new GenericCanBuildFrom[A]()
}
override def newBuilder[A](implicit ord: Ordering[A]): mutable.Builder[A, PairingHeap[A]] = {
ArrayBuffer.empty[A].mapResult { buffer =>
buffer.foldLeft[PairingHeap[A]](Leaf()) { (acc, x) => acc.meld(Branch(x, Nil)) }
}
}
@SerialVersionUID(6697530614353255528L)
private final case class Leaf[A: Ordering]() extends PairingHeap[A] {
override def isEmpty: Boolean = true
}
@SerialVersionUID(8881977291093735346L)
private final case class Branch[A: Ordering](value: A,
heaps: List[Branch[A]]) extends PairingHeap[A] {
override def isEmpty: Boolean = false
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment