Rewrite logic to make better use of Interface

[theodesp]

For example https://github.com/google/btree/blob/master/btree.go#L59

• Create Item Interface
• We need to remove Comparator
• Modify Interface to include Item
• We need to restore support for the Interface
• Replace all returns in Pairing heap with Item

[mb-14]

I would like to work on this

[mb-14]

@theodesp Is there any specific reason why you want to implement an Item interface? In the current implementation we set the comparator only once during initialisation. If we move to the Item interface implementation we will need to initialise a custom struct which conforms to the interface definition (i.e. the struct has a Compare method) for every Insert command. We will have to do this for primitives as well:

// Item is the basic interface 
type Item interface {
    // Should return a number:
    //    negative , if a < b
    //    zero     , if a == b
    //    positive , if a > b
    Compare(than Item) int
}

type Integer struct {
    Value int
}

func (a Integer) Compare(b Item) int {
    a1 := a.Value
    a2 := b.(Integer).Value
    switch {
    case a1 > a2:
        return 1
    case a1 < a2:
        return -1
    default:
        return 0
    }
}

heap.Insert(Integer{1})
heap.Insert(Integer{2})

Compared to this the current implementation seems more simple

[theodesp]

I was thinking something like:

// Item represents a single object in the heap.
type Item interface {
    // Less tests whether the current item is less than the given argument.
    //
    // This must provide a strict weak ordering.
    // If !a.Less(b) && !b.Less(a), we treat this to mean a == b (i.e. we can only
    // hold one of either a or b in the tree).
    Less(than Item) bool
}
// Int implements the Item interface for integers.
type Int int

// Less returns true if int(a) < int(b).
func (a Int) Less(b Item) bool {
    return a < b.(Int)
}

and the check for equality would be:

heapNode.Value.Less(item) && !item.Less(heapNode.Value)

The idea is to balance the input types with the implementation details. We want a simple HeapNode structure, items that conform to a particular interface,just as Sort.Interface works and a way to easier generalize the heap.Interface

[theodesp]

and then in the heap.Interface can be rewritten as:

// Interface is basic interface that all Heaps implement.
type Interface interface {
    // Inserts an item to the heap and returns it
    Insert(item Item) Item

    // DeleteMin deletes and returns the smallest element
    DeleteMin() Item

    // FindMin returns the minimum element
    FindMin() Item

    // Clear removes all items from the heap.
    Clear()
}

then update the Pairing heap to conform to that interface

[theodesp]

Ta