Skip to content

Instantly share code, notes, and snippets.

@Pooh3Mobi

Pooh3Mobi/BinHeapTree.kt

Last active July 19, 2018 15:29
Show Gist options
  • Save Pooh3Mobi/1c9e4469a63c9126b7d5584a4993c086 to your computer and use it in GitHub Desktop.
Save Pooh3Mobi/1c9e4469a63c9126b7d5584a4993c086 to your computer and use it in GitHub Desktop.
Download ZIP
The Fun of Programming with Kotlin
Raw
BinHeapTree.kt
package mobi.pooh3.thefun.fp.bitree
import kotlin.test.assertFalse
import kotlin.test.assertTrue
/*
The Fun of Programming 1-1 [IFPH Section 6.3]
Q, 6つのjoinのうち2つは、そのどちらか一方だけを使うと、すべての木が線形になってしまう。どの二つか？
A, 1 & 5
*/
fun main(args: Array<String>) {
val pattern = 0
val a = Fork(1, Null, Null)
val b = Fork(2, Null, Null)
assertFalse(a == b)
assertTrue(a.merge(pattern, Null) == a)
assertTrue(Null.merge(pattern, b) == b)
val c = Fork(3, Null, Null)
val d = Fork(4, Null, Null)
val e = Fork(5, Null, Null)
val f = Fork(6, Null, Null)
val aTree = a.merge(pattern, b).merge(pattern, c).merge(pattern, d).merge(pattern, e).merge(pattern, f)
println(aTree.treeString())
}
// data(Ord a) => Tree a = Null | Fork a (Tree a)(Tree a)
// isEmpty :: Tree a -> Bool
// minElem :: Tree a -> a
// deleteMin :: Tree a -> Tree a
// insert :: a -> Tree a -> Tree a
// merge :: Tree a -> Tree a -> Tree a
// isEmpty Null = True
// isEmpty (Fork x a b) = False
// deleteMin (Fork x a b) = merge a b
// minElem (Fork x a b) = x
// insert x a = merge (Fork x Null, Null) a
fun Int.insert(pattern: Int, other: Tree) : Tree = Fork(this, Null, Null).merge(pattern, other)
sealed class Tree(open val x: Int) {
abstract val isEmpty: Boolean
abstract fun merge(pattern: Int, other: Tree): Tree
abstract fun join(pattern: Int, other: Tree): Tree
abstract fun deleteMin(pattern: Int) : Tree
fun minElm() = x
abstract fun treeString(indent: String = " "): String
}
object Null : Tree(Int.MIN_VALUE) {
override val isEmpty: Boolean get() = true
override fun merge(pattern: Int, other: Tree): Tree = other
override fun join(pattern: Int, other: Tree): Tree = other
override fun deleteMin(pattern: Int): Tree = throw UnsupportedOperationException()
override fun treeString(indent: String): String = "[null]"
}
data class Fork(
override val x: Int,
val a: Tree,
val b: Tree
) : Tree(x) {
override val isEmpty: Boolean get() = false
override fun deleteMin(pattern: Int): Tree = a.merge(pattern, b)
override fun join(pattern: Int, other: Tree): Tree = when(pattern) {
0 -> Fork(x, a , b.merge(pattern, other))
1 -> Fork(x, b , a.merge(pattern, other))
2 -> Fork(x, other , a.merge(pattern, b))
3 -> Fork(x, b.merge(pattern, other) , a)
4 -> Fork(x, a.merge(pattern, other) , b)
else -> Fork(x, a.merge(pattern, b) , other)
}
override fun merge(pattern: Int, other: Tree) : Tree = when {
this.minElm() <= other.minElm() ->
this.join(pattern, other)
else ->
other.join(pattern, this)
}
override fun treeString(indent: String): String =
"[$x" +
" ${if (a === Null) "Null" else a.x.toString()}" +
" ${if (b === Null) "Null" else b.x.toString()}] \n" +
"$indent┗${a.treeString("$indent| ")}\n" +
"$indent┗${b.treeString("$indent| ")}"
}
/* 1
[1 Null 2]
┗[null]
┗[2 Null 3]
| ┗[null]
| ┗[3 Null 4]
| | ┗[null]
| | ┗[4 Null 5]
| | | ┗[null]
| | | ┗[5 Null 6]
| | | | ┗[null]
| | | | ┗[6 Null Null]
| | | | | ┗[null]
| | | | | ┗[null]
*/
/* 2
[1 3 2]
┗[3 Null 5]
| ┗[null]
| ┗[5 Null Null]
| | ┗[null]
| | ┗[null]
┗[2 4 6]
| ┗[4 Null Null]
| | ┗[null]
| | ┗[null]
| ┗[6 Null Null]
| | ┗[null]
| | ┗[null]
*/
/* 3
[1 6 2]
┗[6 Null Null]
| ┗[null]
| ┗[null]
┗[2 5 3]
| ┗[5 Null Null]
| | ┗[null]
| | ┗[null]
| ┗[3 4 Null]
| | ┗[4 Null Null]
| | | ┗[null]
| | | ┗[null]
| | ┗[null]
*/
/* 4
[1 2 3]
┗[2 6 4]
| ┗[6 Null Null]
| | ┗[null]
| | ┗[null]
| ┗[4 Null Null]
| | ┗[null]
| | ┗[null]
┗[3 5 Null]
| ┗[5 Null Null]
| | ┗[null]
| | ┗[null]
| ┗[null]
*/
/* 5
[1 2 Null]
┗[2 3 Null]
| ┗[3 4 Null]
| | ┗[4 5 Null]
| | | ┗[5 6 Null]
| | | | ┗[6 Null Null]
| | | | | ┗[null]
| | | | | ┗[null]
| | | | ┗[null]
| | | ┗[null]
| | ┗[null]
| ┗[null]
┗[null]
*/
/* 6
[1 2 6]
┗[2 3 5]
| ┗[3 Null 4]
| | ┗[null]
| | ┗[4 Null Null]
| | | ┗[null]
| | | ┗[null]
| ┗[5 Null Null]
| | ┗[null]
| | ┗[null]
┗[6 Null Null]
| ┗[null]
| ┗[null]
*/
Raw
MaxiphobicBinaryHeapTrees.kt
package mobi.pooh3.thefun.fp.maxiphobic
/*
The Fun of Programming 1-2 Maxiphobic Binary Heap Trees
*/
// data(Ord a) => Tree a = Null | Fork a (Tree a)(Tree a)
// isEmpty :: Tree a -> Bool
// minElem :: Tree a -> a
// deleteMin :: Tree a -> Tree a
// insert :: a -> Tree a -> Tree a
// merge :: Tree a -> Tree a -> Tree a
// isEmpty Null = True
// isEmpty (Fork n x a b) = False
// minElem (Fork n x a b) = x
// deleteMin (Fork n x a b) = merge a b
// insert x a = merge (Fork 1 x Null, Null) a
// merge a Null = a
// merge Null b = b
// merge a b
// | minElem a <= minElem b = join a b
// | otherwise = join b a
// join(Fork n x a b) c = Fork(n + size c) x aa (merge bb cc)
// where (aa, bb, cc) = oderBySize a b c
// orderBySize a b c
// | size a == biggest = (a, b ,c)
// | size b == biggest = (b, a ,c)
// | size c == biggest = (c, a ,b)
// where
// biggest = size a `max` size b `max` size c
// size Null = 0
// size Fork(n x a b) = n
typealias TreeList = List<Tree>
fun Int.insert(other: Tree) : Tree = Fork(1, this, Null, Null).merge(other)
sealed class Tree(open val x: Int) {
abstract val isEmpty: Boolean
abstract val size: Int
abstract fun join(other: Tree): Tree
abstract fun deleteMin() : Tree
abstract fun treeString(indent: String = " "): String
fun minElm() = x
@Suppress("RedundantObjectTypeCheck")
fun merge(other: Tree) : Tree = when {
this is Null && other is Fork -> other
this is Fork && other is Null -> this
this is Fork && other is Fork -> when {
this.minElm() <= other.minElm() -> this.join(other)
else -> other.join(this)
}
else -> Null
}
}
object Null : Tree(Int.MIN_VALUE) {
override val isEmpty: Boolean get() = true
override val size: Int get() = 0
override fun join(other: Tree): Tree = other
override fun deleteMin(): Tree = throw UnsupportedOperationException()
override fun treeString(indent: String): String = "[null]"
}
data class Fork(
val n: Int,
override val x: Int,
val l: Tree,
val r: Tree
) : Tree(x) {
override val isEmpty: Boolean get() = false
override val size: Int get() = n
override fun deleteMin(): Tree = l.merge(r)
override fun join(other: Tree): Tree = treeListOf(l, r, other)
.orderBySize().let { (aa, bb, cc) -> Fork(n + other.size, x, aa, bb.merge(cc)) }
private fun TreeList.orderBySize(): TreeList = this.let { list ->
/* println("join ${list.filter { it != Null }}") */
val (a: Tree, b: Tree, c: Tree) = list
val biggest = list.maxBy { it.size }?.size ?: Null.size
when (biggest) {
a.size -> treeListOf(a, b, c)
b.size -> treeListOf(b, a, c)
c.size -> treeListOf(c, a, b)
else -> throw IllegalArgumentException()
}
}
override fun treeString(indent: String): String =
"[$x" +
" ${if (l === Null) "Null" else l.x.toString()}" +
" ${if (r === Null) "Null" else r.x.toString()}] \n" +
"$indent┗${l.treeString("$indent| ")}\n" +
"$indent┗${r.treeString("$indent| ")}"
override fun toString(): String =
"Fork(n=$n, x=$x " +
"left=${if(l === Null) "Null" else l.toString()}, " +
"right=${if(r === Null) "Null" else r.toString()})"
}
@Suppress("ReplaceSizeCheckWithIsNotEmpty")
private fun treeListOf(vararg elements: Tree): TreeList = if (elements.size > 0) elements.asList() else emptyList()
/*
* main
*/
fun main(args: Array<String>) {
fun Iterable<Int>.toTree() = this
.map { Fork(n = 1, x = it, l = Null, r = Null) }
.reduce { acc, fork -> acc.merge(fork) as Fork }
fun Iterable<Int>.toTreeRight() = this
.map { Fork(n = 1, x = it, l = Null, r = Null) }
.reduceRight { acc, fork -> acc.merge(fork) as Fork }
println("= 1-2-1 =========================")
val question1_2_1 = (1..7).toTreeRight()
println(question1_2_1.treeString())
// println("--------------------------")
// question1_2_1.merge(Fork(1, 8, Null, Null))
println("= 1-2-2 =========================")
val question1_2_2 = listOf(1, 7, 2, 6, 3, 5, 4).toTree()
println(question1_2_2.treeString())
println("= 1-2-3 =========================")
val aTree = (1..7).toTree()
println(aTree.treeString())
println("--------------------------")
val question1_2_3 = aTree.deleteMin()
// val question1_2_3 = aTree.merge(Fork(1, 8, Null, Null))
println(question1_2_3.treeString())
}
/*
= 1-2-1 =========================
[1 2 Null]
┗[2 3 Null]
| ┗[3 4 Null]
| | ┗[4 5 Null]
| | | ┗[5 6 Null]
| | | | ┗[6 7 Null]
| | | | | ┗[7 Null Null]
| | | | | | ┗[null]
| | | | | | ┗[null]
| | | | | ┗[null]
| | | | ┗[null]
| | | ┗[null]
| | ┗[null]
| ┗[null]
┗[null]
= 1-2-2 =========================
[1 3 2]
┗[3 7 5]
| ┗[7 Null Null]
| | ┗[null]
| | ┗[null]
| ┗[5 Null Null]
| | ┗[null]
| | ┗[null]
┗[2 6 4]
| ┗[6 Null Null]
| | ┗[null]
| | ┗[null]
| ┗[4 Null Null]
| | ┗[null]
| | ┗[null]
= 1-2-3 =========================
[1 2 3]
┗[2 5 6]
| ┗[5 Null Null]
| | ┗[null]
| | ┗[null]
| ┗[6 Null Null]
| | ┗[null]
| | ┗[null]
┗[3 4 7]
| ┗[4 Null Null]
| | ┗[null]
| | ┗[null]
| ┗[7 Null Null]
| | ┗[null]
| | ┗[null]
--------------------------
[2 3 5]
┗[3 4 7]
| ┗[4 Null Null]
| | ┗[null]
| | ┗[null]
| ┗[7 Null Null]
| | ┗[null]
| | ┗[null]
┗[5 6 Null]
| ┗[6 Null Null]
| | ┗[null]
| | ┗[null]
| ┗[null]
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment