Voir la source de 20160321:TP:Go:Map:Objects

[[category:EPITA:TP:20152016]]
== Introduction ==

Dans la session d'aujourd'hui nous allons travailler sur les hashmap et les
objets.

Pour l'architecture nous prendrons les mêmes conventions que pour le TP de la semaine dernière, nous allons juste créer un nouveau répertoire <tt>tutorial20160321</tt> sous le répertoire <tt>gowork/src</tt>.

== Compter les mots ==

* '''Cible:''' <tt>tutorial20160321/word_count</tt>

Ce premier exercice consiste à utiliser une hashmap pour compter les mots d'un
text.

=== Compter avec une hashmap ===

* '''écrire la fonction suivante:'''

<source lang="go">
/*
   WordCount(words) build a map of each distinct words appearing in the string
   slice words and attach the number of occurrences of each words.
*/
func WordCount(words []string) (wc map[string]int)
</source>

=== Ouvrir un fichier et le découper ===

Pour tester notre fonction, il nous faut un text déjà découper en mot. Pour ça
nous allons charger le comptenu d'un fichier et le découper sur les ''espaces''.
Les fonctions suivantes nous serons fortement utiles (voir la doc … )

* <tt>os.Open(fname)</tt>
* <tt>ioutils.ReadAll(reader)</tt>
* <tt>strings.Fields(str)</tt>

* '''écrire la fonction suivante:'''

<source lang="go">
/*
   LoadFile(fname) opens the file fname, reads the content and split it into
   words.
*/
func LoadFile(fname string) (words []string)
</source>

=== Aller plus loin (bonus) ===

La fonction <tt>strings.Fields(str)</tt/> divise notre string sur les caractères
considérés comme des espaces mais elle ne gère pas la ponctuation. Vous pouvez
essayer d'améliorer le découpage des mots en tenant compte de la ponctuation.

=== Tester ===

Pour tester, vous allez regrouper votre code dans un seul fichier sous la forme suivante:

<source lang="go">
package main

import (
	"fmt"
	"io/ioutil"
	"os"
	"strings"
)

func WordCount(words []string) (wc map[string]int) {
	/* FIX ME */
}

func LoadFile(fname string) (words []string) {
	/* FIX ME */
}

func main() {
	if len(os.Args) < 2 {
		panic("Missing argument")
	}
	wc := WordCount(LoadFile(os.Args[1]))
	fmt.Println(wc)
}
</source>

== Objets et interfaces ==

* '''Cible:''' <tt>tutorial20160321/ordered_set</tt>

Pour cette partie nous allons implémenter des ensembles triés (''ordered set''.) Nous allons en profiter pour aborder 3 notions: les objets, les interfaces et les tests semi-automatiques de go (avec la commande <tt>go test</tt>).

=== Principe ===

Une implémentation simple d'ensembles triés s'appuie sur un vecteur trié accompagné des opérations classiques d'ajout, suppression et quelques opérations ensemblistes comme l'union ou la différence.

Les opérations d'ajout, de suppression et de recherche s'appuie sur une implémentation de la recherche par dichotomie (''binary search'') qui renvoie la position de l'élément s'il est présent et renvoie la position du plus petit élément plus grand que l'élément recherché sinon. Cette opération nous permet d'effectuer plus simplement et plus efficacement une insertion triée.

L'union s'appuie sur une variante de la fusion de tableaux triés qui n'ajoute qu'une fois les éléments présents dans les deux tableaux.

=== Structure globale ===

Nous allons créer 2 fichiers dans le package <tt>ordered_set</tt>

* <tt>set.go</tt>: le code concret de nos ensembles
* <tt>set_test.go</tt>: le code des tests (attention le suffix <tt>_test</tt> est important.)

Nous n'utiliserons pas de package <tt>main</tt> pour les tests, mais la commande <tt>go test</tt> qui va exploiter le code dans <tt>set_test.go</tt> pour ça.

=== Interface ===

Nous voulons des ensembles ''génériques'' qui ne soient pas spécifiques à un type donné. Pour ça nous allons utiliser la notion d'interface de Go.

Pour faire un ensemble trié, nous avons juste besoin d'une fonction qui dit si un élément est plus petit qu'un autre et une fonction qui dit si deux éléments sont égaux.

On définit donc l'interface suivante:

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

Maintenant, si on définit un type et qu'on lui attache les opérations <tt>Less</tt> et <tt>Equals</tt> il pourra être vu comme respectant cette interface.

Voici juste un petit exemple avec des entiers (issue de <tt>set_test.go</tt>.)

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

Notre implémentation d'ensemble travaillera donc avec un vecteur de <tt>OrderedType</tt> et utilisera les méthodes <tt>Less</tt> et <tt>Equals</tt>.

=== Implémentation ===

Voici le squelette pour le fichier <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 {
	var s *Set
	*s = 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>

Pour la fonction d'ajout: vous utiliserez <tt>bfind</tt> pour trouvez la position d'insertion de l'élément (et vérifier au passage s'il n'est pas déjà présent et pour décaller les cases vers la droite, vous pourrez utiliser la stratégie suivante:

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

Pour les tests, nous allons utiliser les possibilités de tests automatisés de Go. Dans le répertoire d'un package, les fichiers finissants par <tt>_test.go</tt> sont ignorés lors de la compilation du package, par contre ils vont être utilisés si vous appelez <tt>go test</tt>. Dans ce cas là, Go compile votre package avec les fichiers de tests et appelle une par une toutes les fonctions dont le nom a la forme suivante: <tt>TestXxx(t)</tt> (noter l'emplois des majuscule qui est important.) Le paramètre des ces fonctions est un pointeur sur le type <tt>testing.T</tt> (voir la doc du package en question) qui fournit des opérations vous permettant de construire des logs pour votre tests et d'indiquer qu'un test à échouer. Notons que les logs ne sont affichés que si le test échoue.

Je vous fourni un début de tests, à vous de le compléter pour tester toutes les opérations.

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