What is the comparable interface called?
I'm working on a simple linked list implementation in Go for learning purposes. The definition of an element is below:
type Element struct {
next, prev *Element
Value interface{}
}
As you can see, the Value can be anything that satisfies the empty interface. Now, as a new feature, I would like to make it so that when you insert a new element into the list, it inserts it in a sorted manner - each element will be <= the next.
In order to do this, I wrote the following method:
func (l *LinkedList) Add(val interface{}) *Element {
this := &l.Root
e := Element{Value: val}
for {
if this.next.Value != nil && this.next.Value < val { // <-comparison here
this = this.next
} else {
return l.insert(&e, this)
}
}
}
The compiler complains operator < not defined on interface which is fair. So I understand that in my Element typedef, I should restrict Value to types that can be compared using the < operator. I learned this while researching this problem that Go does not support operator overloading - I am not trying to do that. Instead, I am just trying to make sure that Element.Value is a type that can be compared using the < operator. How do I do this?
Update:
It occurs to me that it might not be too difficult to simple define a new type, based on a built-in, that can be compared through some function. so I wrote this mess (as well as a bunch of other ways of trying to do the same thing):
type Comparable interface {
LessThan(j interface{}) bool // tried (j Comparable), (j MyInt), etc
EqualTo(j interface{}) bool // tried (j Comparable), (j MyInt), etc
}
type MyInt int
func (i MyInt) LessThan(j MyInt) bool {
return i < j
}
func (i MyInt) EqualTo(j MyInt) bool {
return i == j
}
type Element struct {
next, prev *Element
Value Comparable
}
What I would really like is to define an interface, which, if implemented for a type, provides functions LessThan and EqualTo that operate on two instances of that type and provides a bool - something like LessThan(i, j WhatEvers) bool which can be used in place of <. I realize below it's implemented as an instance method - I've tried both ways but no success. With the above, I would use it something like: this.next.Value.LessThan(val) in the Add function. I get either:
linkedlist.MyInt does not implement linkedlist.Comparable (wrong type for EqualTo method)
have EqualTo(linkedlist.MyInt) bool
want EqualTo(interface {}) bool
or
linkedlist.MyInt does not implement linkedlist.Comparable (wrong type for EqualTo method)
have EqualTo(linkedlist.MyInt) bool
want EqualTo(linkedlist.Comparable) bool
Is this possible to use an interface to require that a certain function must exist that operates on two instances of a custom type, or is it only for Methods?
Answer
Edit:
consider this user type:
type userType struct {
frequency int
value rune
}
and suppose you want to add this types to your Linked List:
and It should be sorted by frequency first, then if the frequencies are the same, look at the char value. so the Compare function will be:
func (a userType) Compare(b userType) int {
if a.frequency > b.frequency {
return 1
}
if a.frequency < b.frequency {
return -1
}
if a.value > b.value {
return 1
}
if a.value < b.value {
return -1
}
return 0
}
which satisfies this interface:
type Comparer interface {
Compare(b userType) int
}
now add these {1,'d'} {2,'b'} {3,'c'} {4,'a'} {4,'b'} {4,'c'} types to LinkeList:
sample code:
package main
import (
"container/list"
"fmt"
)
type Comparer interface {
Compare(b userType) int
}
type userType struct {
frequency int
value rune
}
// it should sort by frequency first, then if the frequencies are the same, look at the char value.
func (a userType) Compare(b userType) int {
if a.frequency > b.frequency {
return 1
}
if a.frequency < b.frequency {
return -1
}
if a.value > b.value {
return 1
}
if a.value < b.value {
return -1
}
return 0
}
func Insert(val userType, l *list.List) {
e := l.Front()
if e == nil {
l.PushFront(val)
return
}
for ; e != nil; e = e.Next() {
var ut userType = e.Value.(userType)
if val.Compare(ut) < 0 {
l.InsertBefore(val, e)
return
}
}
l.PushBack(val)
}
func main() {
l := list.New()
Insert(userType{4, 'c'}, l)
Insert(userType{4, 'a'}, l)
Insert(userType{4, 'b'}, l)
Insert(userType{2, 'b'}, l)
Insert(userType{3, 'c'}, l)
Insert(userType{1, 'd'}, l)
for e := l.Front(); e != nil; e = e.Next() {
ut := e.Value.(userType)
fmt.Printf("{%d,%q} ", ut.frequency, ut.value)
}
fmt.Println()
var t interface{} = userType{4, 'c'}
i, ok := t.(Comparer)
fmt.Println(i, ok)
}
and output:
{1,'d'} {2,'b'} {3,'c'} {4,'a'} {4,'b'} {4,'c'}
{4 99} true
so if you ready to use known type (e.g. int), see this sample:
package main
import (
"container/list"
"fmt"
)
func Insert(val int, l *list.List) {
e := l.Front()
if e == nil {
l.PushFront(val)
return
}
for ; e != nil; e = e.Next() {
v := e.Value.(int)
if val < v {
l.InsertBefore(val, e)
return
}
}
l.PushBack(val)
}
func main() {
l := list.New()
Insert(4, l)
Insert(2, l)
Insert(3, l)
Insert(1, l)
for e := l.Front(); e != nil; e = e.Next() {
fmt.Print(e.Value, " ") // 1 2 3 4
}
fmt.Println()
}
old:
There is no such interface in Go. You may write this Less function to compare your types:
func Less(a, b interface{}) bool {
switch a.(type) {
case int:
if ai, ok := a.(int); ok {
if bi, ok := b.(int); ok {
return ai < bi
}
}
case string:
if ai, ok := a.(string); ok {
if bi, ok := b.(string); ok {
return ai < bi
}
}
// ...
default:
panic("Unknown")
}
return false
}
test sample code:
package main
import (
"container/list"
"fmt"
)
func Less(a, b interface{}) bool {
switch a.(type) {
case int:
if ai, ok := a.(int); ok {
if bi, ok := b.(int); ok {
return ai < bi
}
}
case string:
if ai, ok := a.(string); ok {
if bi, ok := b.(string); ok {
return ai < bi
}
}
default:
panic("Unknown")
}
return false
}
func Insert(val interface{}, l *list.List) *list.Element {
e := l.Front()
if e == nil {
return l.PushFront(val)
}
for ; e != nil; e = e.Next() {
if Less(val, e.Value) {
return l.InsertBefore(val, e)
}
}
return l.PushBack(val)
}
func main() {
l := list.New()
Insert(4, l)
Insert(2, l)
Insert(3, l)
Insert(1, l)
for e := l.Front(); e != nil; e = e.Next() {
fmt.Print(e.Value, " ")
}
fmt.Println()
Insert("C", l)
Insert("A", l)
Insert("AB", l)
Insert("C", l)
Insert("C2", l)
Insert("C1", l)
for e := l.Front(); e != nil; e = e.Next() {
fmt.Print(e.Value, " ")
}
fmt.Println()
}
output:
1 2 3 4
1 2 3 4 A AB C C C1 C2