0

Okay, so to try to learn the kotlin language, I am trying to implement a heap.

class Heap <T : Comparable<T>>(private var heap: Array<T>, private var size: Int){

I am having some difficulties with how the nullable types behave. In the beginning I gave a array of elements, but I started having difficulties when I wanted to allocate more elements

private fun increaseSize(){
    if(size == heap.size){
        //okay this is garbage
        var enlargedHeap = arrayOfNulls<Comparable<*>>(heap.size * 2) as Array<T> 
        System.arraycopy(heap, 0, enlargedHeap, 0, size)
        heap = enlargedHeap
    }
}

So here I am guessing I am changing the heap from Array<T> to Array<T?> which makes sense. So I changed the constructor as well, to take Array<T?> and it suggests some pretty interesting things wherever I try to access heap[x]

else heap[pos1].compareTo(heap[pos2]) < 0

to

else heap[pos2]?.let { heap[pos1]?.compareTo(it) }!! < 0

then I looked at a tooltip stating that arrayOfNulls<Comparable<*>>(heap.size * 2) as Array<T> returned Array<T>

But when doing the arrayOfNulls it indeed returns an array with null values. However I get an error if I try to heap[x] = null

stating

Null cannot be a value of non-null type T

If I change the constructor to take a Array<T?>, then input arrays have to explicitly nullable too.

Which I fixed with

class Heap <T : Comparable<T>>{

private var heap: Array<T?>
private var size = 0

constructor(heap: Array<T>, size){
    this.heap = heap as Array<T?>
    this.size = size
}

But now it does not accept arrays that has null values when I try to instantiate it with an array with nullable values

var arr = arrayOfNulls<String>(9)
var heap = Heap(arr, arr.size-1)

So now I need two constructors? What is going on

Type mismatch. Required: Comparable Found:String?

Even with Àrray<T?> there is errors with the compareTo's not accepting nullable values.

Even with checks it still gives an error

return  if(pos2 > size || (heap[pos1] == null || heap[pos2] == null)) false
        else heap[pos1].compareTo(heap[pos2]) < 0

Type mismatch. Required:T Found: T?

How do I allow the array to contain null values?

Hopefully without making Array<T> nullable since it breaks the compareTo's and multiple constructors seems like bad design.

Improve this question

2 Answers 2

Reset to default
1

Arrays are tricky to work with in a generic class because they have reified types.

I think you need to move the backing array property out of the constructor so the constructor won't be ambiguous about nullability. Otherwise type inference won't work with the constructor, and you would also be forced to use a nullable-typed array as the constructor parameter even if you want the heap to have a non-nullable type. Anyway, it's good that you copy the array from the constructor rather than using it directly as a backing array, because otherwise there is the possibility that some outside object could still be modifying that backing array.

Since Arrays always have reified type, I think you also need to use a backing array of type Any?. This will mean you have to cast objects that are passed out of the heap in the public functions. You can make a single get function for that, and use it internally with this[] to avoid having to put casts all over your class. The unchecked casting is safe as long as you don't put anything besides a T in the part of the array below size, and you don't try to get values above size, since they're always null and T might not be nullable.

class Heap <T : Comparable<T>>(initialValues: Array<T>, private var size: Int) {
    init {
        if (size > initialValues.size) 
            error("Initial array is too small for initial size.")
    }
    private var heap = Array<Any?>(size){ initialValues[it] }

    @Suppress("UNCHECKED_CAST")
    private operator fun get(index: Int) = heap[index] as T

    private fun increaseSize(){
        var enlargedHeap = arrayOfNulls<Any>(heap.size * 2)
        System.arraycopy(heap, 0, enlargedHeap, 0, size)
        heap = enlargedHeap
    }

    fun pop(): T {
        if (size == 0)
            error("Cannot pop when size is 0")
        size--
        val out = this[size] // Use this class's getter to avoid having to cast
        heap[size] = null
        return out
    }

    fun push(value: T) {
        if (size == heap.size)
            increaseSize()
        heap[size] = value
        size++
    }

}

You might also consider moving the size parameter out of the constructor to make usage simpler and avoid the ambiguous case of what happens if the input size is smaller than the array you pass in. 

class Heap <T : Comparable<T>>(initialValues: Array<T>) {
    private var size = initialValues.size
    private var heap = Array<Any?>(size){ initialValues[it] }
    //...
Improve this answer
Sign up to request clarification or add additional context in comments.

8 Comments

Somehow I cannot use compareTo with the Any type? Which is a big issue because I use ADT's implementing the interface in the heap
I don't know what ADT is. But if you want to do a comparison, cast the values first. Which is what the get function above does for you.
You can't cast arrays to use different types because they use reified types. You'll get a ClassCastException. And if you just make your backing array an Array <Comparable<*>?>, you will still have to cast what you get out of the array because of the star projection.
I don't know what your comparisons are being used for, but if you use the getter that casts, it just works: fun secondMoreThanFirst(): Boolean = this[1] > this[0]
How should I convert the elements from Any? back to T?
|
1

Please use Array<T?>, instead of Array<T>.

E.g. in your class signature, properties should be:

class Heap <T : Comparable<T>>(private var heap: Array<T?>, private var size: Int) {

If you need input with not null values, please use something like this:

     private var heap = initialHeap.toArray(); // copy input parameter to internal array
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.