CS 245 - Programming Languages

Lab 4

Sorting Go Slices

In this lab you will create and fill a slice containing instances of a struct. Then you will use the sort function in Go to set up sorting on two distinct fields in the struct. (There are other was of sorting slices that contain structs in Go. Use the one described below.)

Setup

  1. Create a struct with 3 fields: an int, a float32 and a string
  2. Define a String method for you struct.
  3. Create a type for a slice that holds instances of the struct you just made.
  4. (in the main function) Create a slice that holds instances of the struct you created and is of the type you created.
  5. Put into the slice about 10 instances of your struct; each instance should have values of the fields that are distinct from any other instance. Also, the values in each field should not be in a sorted order.
  6. Print the contents of your slice. Printing should use a String method defined for your struct.

Sorting

Like Java, Go has interfaces; however, they are differently implemented in Go than in Java. In Go, you do not have to declare that something implements an interface. Rather, at compile time the program is checked for the presence of functions that require implementing an interface. If the required interface is implemented (usually as methods on a type), then the compile succeeds and the program runs. There is no explicit declaration that the methods to implement are defined for a type. The compiler just looks to see that they are implemented and complains if they are not (and other pieces of code require that they are).

Sorting requires implementing 3 methods on a type 

func (p S) Len() int {  }
func (p S) Swap(i, j int) {  }
func (p S) Less(i, j int) bool { }
Importantly the type on which these methods are implemented needs to be one that holds a slice. So, for instance, suppose that you have defined a slice type 
				type IntSlice []int
Just below the definition of IntSlice you write the methods required for sorting. For example: 
				func (item IntSlice) Len() int {
					return len(item)
				}
along with the other methods required for sorting. (I usually put methods I define for a type immediately below the type definition; this is not required but I think it is a good idea). Then to sort aa (where aa is an instance of the slice type (in my example it would be an instance of IntSlice)) just 
				sort.Sort(aa)
All that said, now do this for yourself. Implement the methods and sort your slice instance using the functions in the Go "sort" package. (Do not write your own sort.)

Now, suppose you want to sort on some other field of your struct. You could do this by adding some branching inside the Less method and having a global variable to indicate the branch to use. But that is really ugly. Worse, it will slow down the sort. Instead, define a new type that is just a renaming of your struct/slice type. Then implement the Len, Swap and Less functions on your new type. Finally, cast your slice from the original type to your new type and sort that thing.

Write code that shows that the different sorting actually happened.

What to hand in

Send to gtowell@brynmawr.edu a copy of your go program. The program should include everything described above and a main function, that, when run, shows that different sorts can be done on the same slice by only casting the slice to a different types.