2

Whilst developing simple primary queue in Kotlin I have bumped into an unchecked cast with an unchecked warning that I cannot get rid of:

private val pq: Array<T> = arrayOfNulls<Comparable<T>>(capacity) as Array<T>

Here is the full source code of the Kotlin priority queue:

class UnorderedMaxPQ<T : Comparable<T>>(capacity: Int) {

    private val pq: Array<T> = arrayOfNulls<Comparable<T>>(capacity) as Array<T>

    private var size = 0

    fun isEmpty() = size == 0

    fun size() = size

    fun insert(x: T) {
        pq[size++] = x
    }

    fun delMax(): T {
        var max = 0
        (1..size - 1)
                .asSequence()
                .filter { less(pq[max], pq[it]) }
                .forEach { max = it }
        exchange(pq, max, size - 1)
        return pq[--size]
    }

    fun <T> exchange(a: Array<T>, i: Int, min: Int) {
        val temp = a[i]
        a[i] = a[min]
        a[min] = temp
    }

    fun <T : Comparable<T>> less(c1: T, c2: T) = c1 < c2

}

Any suggestions on how to avoid the unchecked cast when creating an array of nulls?

Here is a simple unit test of the class above:

import org.hamcrest.core.Is.`is`
import org.junit.Assert.assertThat
import org.junit.Test

class UnorderedMaxPQTest {

    @Test
    fun insert_delMax() {
        val pq = UnorderedMaxPQ<Int>(10)
        pq.insert(2)
        pq.insert(3)
        pq.insert(4)
        pq.insert(1)
        assertThat(pq.delMax(), `is`(4))
        assertThat(pq.delMax(), `is`(3))
        assertThat(pq.size(), `is`(2))
        pq.insert(10)
        assertThat(pq.size(), `is`(3))
        assertThat(pq.delMax(), `is`(10))
        assertThat(pq.isEmpty(), `is`(false))
    }
}

Edit 1:

You could re-write this:

private val pq: Array<T> = arrayOfNulls<Comparable<T>>(capacity) as Array<T>

as:

private val pq: Array<T> = Array<Comparable<T>?>(capacity, { null }) as Array<T>

The unchecked cast problem persists though. This variation is based on Andrey Breslav's post: https://stackoverflow.com/a/20297428/2735286

gil.fernandes
  • 12,978
  • 5
  • 63
  • 76

1 Answers1

1

You create an array of consisting of null only (arrayOfNulls<Comparable<T>>(capacity)). That means you have a array with capacity nulls. And then you want to cast the array to a non nullable one? That doesn't make any sense. You don't really have a safe way to get rid of the unchecked cast as it is unsafe and it will cause you problems if you try to force cast it.

Mibac
  • 8,990
  • 5
  • 33
  • 57
  • Yes, the implementation might be clumsy. Yet the idea was to have an array of a fixed size which is initially empty. My thinking is that of a Java coder who would write something like `pq = (T[]) new Comparable[capacity]`. This results in an array of null's. If you can achieve the same with using _arrayOfNull_ that would be great. – gil.fernandes Sep 07 '17 at 18:03
  • If you do know that it results in an array of nulls then why do you want to cast it to a array without nulls? @gil.fernandes – Mibac Sep 07 '17 at 18:04
  • I have tried _private val pq: Array = arrayOfNulls>(capacity)_ but this does not compile. So the cast was necessary. – gil.fernandes Sep 07 '17 at 18:06
  • @gil.fernandes it will work if you change `Array` to `Array` – Mibac Sep 07 '17 at 18:06
  • good point. Yet I do not want to allow the insert method to insert null into the queue. So I want indeed to never have nulls being inserted or retrieved into / from the queue for the operational code. – gil.fernandes Sep 07 '17 at 18:09
  • @gil.fernandes so leave the functions as they are. Your `insert` function won't allow nulls regardless if your array is `T` or `T?` – Mibac Sep 07 '17 at 18:10
  • Ok, let me try _private val pq = arrayOfNulls>(capacity)_ and see where that leads me to. – gil.fernandes Sep 07 '17 at 18:21
  • @gil.fernandes you don't really need to make the `Comparable` have `T?`. `T` will do – Mibac Sep 07 '17 at 18:25