20180416:TP:Go:Objects

Introduction

This week we start playing with Go's objects and interfaces. It's also the occasion to play with the command go test.

Yout git repo should follow the same organisation as before, using the directory name tutorial20180416.

A set implementation

• Path: tutorial20180416/ordered_set

For this section we will implement ordered set. This part uses 3 notions: objects, interfaces and automated testing.

Principle

A basic ordered set implementation uses a sorted array and provides the classical set operations (insertion, delete, union, difference … )

Insert and delete use the classical binary search algorithm (the search is supposed to return the position of the first element that is not smaller than the searched element, which is the perfect insertion position.)

The union is a variant of the sorted array merge used in merge sort where we skip duplicate elements.

General structure

We create two files in the package ordered_set

• set.go: the implementation
• set_test.go: test code (warning the suffix _test is important.)

We don't need a main package for the test, the go test will use our tests described in set_test.go.

Interface

Our goal is to implement generic set that work with any ordered type. We use interface for that.

All we need is to define an interface with two operations: less and equal.

Here is the interface definition:

/*
OrderedType interface: describes comparable value
 
Comparable value provides:
  x.Less(y) returns true if x < y
  x.Equals(y) returns true if x == y
*/
type OrderedType interface {
	Less(OrderedType) bool
	Equals(OrderedType) bool
}

Now, any type providing the corresponding operations can be used as an element of interface OrderedType.

A small example with integer (extracted from set_test.go).

Due to typing rules, Equals and Less must accept element of interface OrderedType not just OrderedInt, thus we need the switch type case that try to convert the parameter to the expected type.

type OrderedInt int
 
func (x OrderedInt) Equals(y OrderedType) bool {
	switch y_ := y.(type) {
	case OrderedInt:
		return x == y_
	default:
		return false
	}
}
 
func (x OrderedInt) Less(y OrderedType) bool {
	switch y_ := y.(type) {
	case OrderedInt:
		return x < y_
	default:
		return false
	}
}

Our set implementation will work with vector (slices) of OrderedType and only relies on methods Less and Equals.

Implementation

Here is template for the file set.go:

// ordered_set: a simple generic set implementation
package ordered_set
 
/*
OrderedType interface: describes comparable value
 
Comparable value provides:
  x.Less(y) returns true if x < y
  x.Equals(y) returns true if x == y
*/
type OrderedType interface {
	Less(OrderedType) bool
	Equals(OrderedType) bool
}
 
// uniq_merge(s1, s2) returns a merge of sorted list s1 and s2 without doublon
func uniq_merge(s1, s2 []OrderedType) (r []OrderedType) {
	/* FIX ME */
}
 
// Set: an ordered set of OrderedType elements
type Set []OrderedType
 
// NewSet() creates a new empty set
func NewSet() *Set {
        s := Set(make([]OrderedType, 0))
        return &s
}
 
// s.bfind(x) returns expected position of x
// if x is not present, returns position of first element not smaller than x
func (s *Set) bfind(x OrderedType) (pos int) {
	/* FIX ME */
}
 
// s.Mem(x) returns true if x is in the set
func (s *Set) Mem(x OrderedType) bool {
	p := s.bfind(x)
	return p < len(*s) && x.Equals((*s)[p])
}
 
// s.Add(x) add x to set s, returns true if x wasn't there, false otherwise
func (s *Set) Add(x OrderedType) bool {
	/* FIX ME */
}
 
// s.Remove(x) removes x from s
// returns true if x was in the set, false otherwise
func (s *Set) Remove(x OrderedType) bool {
	/* FIX ME */
}
 
// s.Union(s2) adds elements from s2 to s
func (s *Set) Union(s2 *Set) {
	*s = uniq_merge(*s, *s2)
}
 
// s.Difference(s2) removes all elements of s2 from s
func (s *Set) Difference(s2 *Set) {
	/* FIX ME */
}

For the insertion, you'll use the bfind function in order to find the insertion position (and check for the presence of the element). For shifting the array cells to the right, you can use the following strategy:

	// Shift all cells from position p to the end by 1 cell to the right
	*s = append(*s, nil)                // add an empty cell at the end
	copy((*s)[p+1:], (*s)[p:len(*s)-1]) // shift element with copy

Tests

For the test, we use the automated testing tool of Go. In a package directory, files ending with _test.go are ignored during the package building but are used by the command go test. In that case, Go build your package together with the test files and call one by one the tests functions, theses functions must have a name of the forme TestXxx(t) (uppercase are important.) The only parameter of these functions is a pointer to an element of type testing.T (read the doc) providing some interesting ops for logging and failure notifications. Logs are only displayed in case of failure.

Here are some incomplete tests function, you should complete it in order to correctly cover all the important cases for all operations.

package ordered_set
 
import (
	"math/rand"
	"testing"
)
 
type OrderedInt int
 
func (x OrderedInt) Equals(y OrderedType) bool {
	switch y_ := y.(type) {
	case OrderedInt:
		return x == y_
	default:
		return false
	}
}
 
func (x OrderedInt) Less(y OrderedType) bool {
	switch y_ := y.(type) {
	case OrderedInt:
		return x < y_
	default:
		return false
	}
}
 
func isSet(s Set) bool {
	i := 0
	for ; i < len(s)-1 && s[i].Less(s[i+1]) && !s[i].Equals(s[i+1]); i++ {
	}
	return i >= len(s)-1
}
 
func present(s Set, x OrderedType) bool {
	for _, v := range s {
		if x.Equals(v) {
			return true
		}
	}
	return false
}
 
func TestSet_Add_fixed(t *testing.T) {
	tmp := Set(make([]OrderedType, 0))
	var s *Set
	s = &tmp
	for i := 0; i < 100; i++ {
		n := OrderedInt(i)
		if !s.Add(n) {
			t.Fatal("Adding not present element should not return false")
		}
		if len(*s) != i+1 {
			t.Fatal("Set length does not match")
		}
		if !present(*s, n) {
			t.Fatal("Added element not in the set")
		}
		if !isSet(*s) {
			t.Log("set:", *s)
			t.Fatal("Ill formed set (not sorted or contains doublons)")
		}
	}
	if !isSet(*s) {
		t.Log("set:", *s)
		t.Fatal("Ill formed set (not sorted or contains doublons)")
	}
}
 
func TestSet_Add_random(t *testing.T) {
	tmp := Set(make([]OrderedType, 0))
	var s *Set
	s = &tmp
	size := 0
	for i := 0; i < 100; i++ {
		n := OrderedInt(rand.Intn(1000))
		if s.Add(n) {
			size += 1
		}
		if len(*s) != size {
			t.Fatal("Set length does not match")
		}
		if !present(*s, n) {
			t.Fatal("Added element not in the set")
		}
	}
	if !isSet(*s) {
		t.Log("set:", *s)
		t.Fatal("Ill formed set (not sorted or contains doublons)")
	}
}
 
func TestSet_Mem(t *testing.T) {
	s := Set(make([]OrderedType, 100))
	for i := 0; i < 100; i += 1 {
		n := OrderedInt(2 * i)
		s[i] = n
	}
	for i := 0; i < 100; i += 1 {
		n := OrderedInt(2 * i)
		if !s.Mem(n) {
			t.Log(s)
			t.Errorf("set.Mem(%d): unable to find present value\n", 2*i)
		}
	}
	for i := -1; i < 2; i++ {
		n := OrderedInt(i*201 + 1)
		if s.Mem(n) {
			t.Log(s)
			t.Errorf("set.Mem(%d): found not present value\n", 201*i+1)
		}
 
	}
}

Heap

• Path: tutorial20180416/open_set

Go provides a generic implementation of heap, we will adapt it to provide a usable open set for path finding algorithm.

An open set, is a priority queue with following operations:

• update: add or update an element already in the queue
• get next: retrieve (and remove) the next element (the one with highest priority)

The get next op is pretty straightforward, in a simple FIFO queue it returns the oldest element, in our case it will returns the element with the smallest value used as a priority index (in Dijkstra algorithm this should be the distance to the source, in Prim algorithm the cost of the edge and in A* algorithm the distance to the source extended with the heuristic of the destination.)

update requires a little bit more attention: if the element is not present it's just an insertion in the heap, but if it's already there, we need to find it, update its priority value and move it to its new position.

One nice aspect of the way heap are implemented in Go is that we can easily keep track of the index of each element in the heap, so all we need to do is keep a map of elements in the heap in order to retrieve access them easily and then use the Fix method to update the heap order.

You can find a lot of information in the package documentation [1].

Here is the template of our open_set package:

package open_set
 
import (
	"container/heap"
)
 
/* stored item
 * Vertex: a vertex id, we don't care about it here
 * Dist: our priority value: smaller means higher priority
 * index: used to maintain access to element (private)
 */
type Item struct {
	Vertex int
	Dist   int
	index  int
}
 
/* Set the heap */
type Set []*Item
 
/* OpenSet the open-set container */
type OpenSet struct {
	Heap  Set
	Index map[int]*Item
}
 
/* Operations needed by the heap implementation */
 
func (set Set) Len() int {
        /* FIX ME */
}
 
func (set Set) Less(i, j int) bool {
        /* FIX ME */
}
 
func (set Set) Swap(i, j int) {
        /* FIX ME */
}
 
/* s.Push(x) add element x at the end of the set */
func (set *Set) Push(x interface{}) {
        /* FIX ME */
}
 
/* s.Pop() removes and returns the last element of the heap */
func (set *Set) Pop() interface{} {
        /* FIX ME */
}
 
/* NewOpenSet() creates the OpenSet */
func NewOpenSet() (set *OpenSet) {
	set = &OpenSet{make(Set, 0), make(map[int]*Item)}
	heap.Init(&set.Heap)
	return
}
 
/* s.Update(v, d) update vertex v with distance d */
/* Implementation details: this where s.Index is used to find/add the vertex */
func (set *OpenSet) Update(vertex, dist int) {
        /* FIX ME */
}
 
func (set OpenSet) IsEmpty() bool {
	return len(set.Heap) == 0
}
 
 
/* s.TakeMin() returns the element with minimal distance */
func (set *OpenSet) TakeMin() (item *Item, ok bool) {
	item = nil
	if ok = len(set.Heap) > 0; ok {
		item = heap.Pop(&set.Heap).(*Item)
		delete(set.Index, item.Vertex)
	}
	return
}

• Complete the provided code
• Write a open_set_test.go file with some relevant tests.

Usage example

Just for your information, here is an implementation of the Dijkstra algorithm using our open set implementation (the graph implementation is not provided here but you can guess how it works pretty easily):

func ComputePath(g adj_list.Graph, src int, path, dist map[int]int) {
	open := NewOpenSet()
	open.Update(src, 0)
	dist[src] = 0
	path[src] = src
	for !open.IsEmpty() {
		cur, _ := open.TakeMin()
		cd := dist[cur.Vertex]
		for succ, cost := range g.Successors(cur.Vertex) {
			if sd, ok := dist[succ]; !ok || sd > cd+cost {
				dist[succ] = cd + cost
				path[succ] = cur.Vertex
				open.Update(succ, dist[succ])
			}
		}
	}
}