General Set
This assignment has two parts.
Part One
First,
create a Go package named genset to implement a generalized set based
on a plain BST. It will be a set of elements which implement an
interface Comparable which must look exactly like this:
type Comparable interface {
Cmp(Comparable) int
}
As you see, it contains a single method which compares it to another
Comparable method. Much like the Java
CompareTo method,
it must return a negative number if the containing object is less than the
the parameter, zero if they are equal, or a positive number if greater.
Much of the code is similar to the
assignment 4
solution, and you are free to adapt your own solution or
either
posted
key.
The interface is similar, with different naming:
import "packs/genset"
The package must be imported. The package name should be genset, but the
path might differ depending on what you can talk Go into.
genset.Comparable
This is the above interface, which must be part of the package.
User code must create some type which implements it to use the set.
var gs genset.GenSet
This declares gs (or any other name) as a set of Comparable.
The name GenSet is required.
gs.Contains(g)
Return true if the set gs contains g, false if not.
gs.Add(g)
Add the Comparable
g to the set gs. Of course, if g is
already present, gs does not change. The function also should
return a boolen value that is true if add changed the set, or
false if it did not. (The value returned is the inverse of what
contains would have returned before add was called.)
gs.Remove(g)
Remove the Comparable
g from the set gs if present. Like add,
remove returns true if it actually changes the set, and false
if it does not.
gs.Contents()
This method returns type []Comparable, which is a slice that contains the
contents of the set, in ascending order.
You may create any number of
additional methods or functions as helpers, as needed.
Helper functions should be named starting with lower-case so they
are effectively private.
Implementation using a binary search tree is a requirement.
A plain BST that can become unbalanced is quite sufficient. If you just want
to do five times the work to create some kind of
balanced one, and you can make it
work, more power to you.
Here is a trival driver:
package main
import (
"fmt"
"packs/genset"
)
type Int struct {
val int
}
// This cmp function will allow int to satisfy the Comparable interface,
// but it will panic if you try to compare an int with something else.
func (x Int) Cmp(c genset.Comparable) int {
return x.val - c.(Int).val
}
func main() {
var gs genset.GenSet;
gs.Add(Int{17})
fmt.Println(gs.Contains(Int{17}),gs.Contains(Int{19}),gs.Contents())
}
It outputs:
true false [{17}]
Part Two
The second thing is to create a small driver which can use the
package, and creates a set containing both integers and strings.
This requires creating two classes that each implement Comparable,
each having cmp methods which can compare to other objects of the same
type, or to the other type. When the objects are the same type, they should
compare in the normal way. When they are different types, strings should
always be smaller than integers. That way, any two objects can be ordered.
Each of your cmp methods will probably want to use a type switch.
Your program doesn't need to do much but compile, create a stack with at least
three integers and three strings at the same time, and print the contents.
Doing more is fine.
Submission
When your program works, is well-commented, and nicely indented,
submit over the web
here.