Skip to content

Instantly share code, notes, and snippets.

@yangweigbh
Created July 14, 2017 10:07
Show Gist options
  • Save yangweigbh/0d62ab9bb31c18b282f681642aaac55e to your computer and use it in GitHub Desktop.
Save yangweigbh/0d62ab9bb31c18b282f681642aaac55e to your computer and use it in GitHub Desktop.
SkipList Implemented in Kotlin
import java.util.*
/**
* Created by yangwei-ms on 2017/7/14.
*/
class SkipList<T>(private val comparator: Comparator<T>) {
private var curHeight: Int = 1
private val head: Node<T> = Node(null, MAX_HEIGHT)
private val rnd: Random = Random(System.currentTimeMillis())
fun insert(value: T): Unit {
val prev: Array<Node<T>> = Array(MAX_HEIGHT, {null as Node<T>})
var x = findGreaterOrEqual(value, prev)
assert(x == null || comparator.compare(x.value, value) >= 0)
val height = randomHeight()
if (height > curHeight) {
for (i in curHeight..(height-1)) {
prev[i] = head
}
curHeight = height
}
x = Node(value, height)
for (i in 0..(height-1)) {
x.next[i] = prev[i].next[i]
prev[i].next[i] = x
}
}
fun contains(value: T): Boolean {
val x = findGreaterOrEqual(value, null)
if (x != null && x.value == value) {
return true
}
return false
}
private fun randomHeight(): Int {
val branching = 4
var level = 1
while (level < MAX_HEIGHT && rnd.nextInt() % branching == 0) {
level++
}
return level
}
private fun valueIsAfterNode(value: T, node: Node<T>): Boolean {
return node != null && comparator.compare(value, node.value) > 0
}
private fun findGreaterOrEqual(value: T, prev: Array<Node<T>>?): Node<T>? {
var x = head
var level = curHeight - 1
while (true) {
val next = x.next[level]
if (valueIsAfterNode(value, next)) {
x = next
} else {
if (prev != null) prev[level] = x
if (level === 0) {
return next
} else {
level--
}
}
}
}
private fun findLessThan(value: T): Node<T> {
var x = head
var level = curHeight - 1
while (true) {
val next = x.next[level]
if (valueIsAfterNode(value, next)) {
x = next
} else {
if (level === 0) {
return x
} else {
level--
}
}
}
}
private fun findLast(): Node<T> {
var x = head
var level = curHeight - 1
while (true) {
val next = x.next[level]
if (next != null) {
x = next
} else {
if (level === 0) {
return x
} else {
level--
}
}
}
}
class Node<T>(val value: T?, height: Int) {
val next: Array<Node<T>> = Array(height, {null as Node<T>})
}
companion object {
val MAX_HEIGHT = 12
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment