Voir la source de 20170320:TP:Go:Objects

[[category:EPITA:TP:20162017]]

== Introduction ==

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

Yout git repo should follow the same organisation as before, using the directory name <tt>tutorial20170320</tt>.

== A set implementation ==

* '''Path:''' <tt>tutorial20170320/ordered_set</tt>

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 <tt>ordered_set</tt>

* <tt>set.go</tt>: the implementation
* <tt>set_test.go</tt>: test code (warning the suffix <tt>_test</tt> is important.)

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

=== 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:

<source lang="go">
/*
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
}
</source>

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

A small example with integer (extracted from <tt>set_test.go</tt>).

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

<source lang="go">
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
	}
}
</source>

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


=== Implementation ===

Here is template for the file <tt>set.go</tt>:

<source lang="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 */
}
</source>

For the insertion, you'll use the <tt>bfind</tt> 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:

<source lang="go">
	// 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
</source>

=== Tests ===

For the test, we use the automated testing tool of Go. In a package directory, files ending with <tt>_test.go</tt> are ignored during the package building but are used by the command <tt>go test</tt>. 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 <tt>TestXxx(t)</tt> (uppercase are important.) The only parameter of these functions is a pointer to an element of type <tt>testing.T</tt> (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.

<source lang="go">
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)
		}

	}
}
</source>

== Heap ==

* '''Path:''' <tt>tutorial20170320/open_set</tt>

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 <tt>Fix</tt> method to update the heap order.

You can find a lot of information in the package documentation [https://golang.org/pkg/container/heap/].

Here is the template of our <tt>open_set</tt> package:

<source lang="go">
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
}
</source>

* '''Complete the provided code'''
* '''Write a <tt>open_set_test.go</tt> 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):

<source lang="go">
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])
			}
		}
	}
}
</source>