Maps
====

Maps are a very useful data structure that store (key, value) pairs in a way
that lets you efficiently retrieve any pair if you know its key.


Creating a Map
--------------

Here is a map that stores the names of candidates for an election and the
number of votes they've received so far::

	votes := map[string]int{"Yan":4, "Jones":2, "White":2}

On the right side of ``:=`` is a map literal. Its type is ``map[string]int``,
and the map itself is specified using *key*:*value* pairs (similar to the
notation used in languages like Python, JavaScript, and JSON).

You can also create a map using the ``make`` function. Here is an alternative
way to create the ``votes`` map::

	votes := make(map[string]int)  // creates an empty map
	votes["Yan"] = 4
	votes["Jones"] = 2
	votes["White"] = 2


Accessing Elements of a Map
---------------------------

You access a particular value using a key, e.g. ``votes["yan"]`` evaluates to
4. If you want to add 1 vote for Jones, you can do it like this::

	votes["Jones"]++  // add 1 to the value associated with "Jones"

To add a new item to the map, assign it like this::

	votes["Harper"] = 3

If the key ``"Harper"`` already happened to be in ``votes``, then this
statement would just set its value to 3.


Missing Keys
------------

If you try to access the value for a key that doesn't exist, then the zero-
value associated with the value's type is returned. For example::

	fmt.Println(votes["Kennedy"])   // prints 0, because "Kennedy" is not a key

This presents a problem: how can you distinguish between a key that doesn't
exist, and a key that is paired with 0? The solution Go_ provides is to return
an optional flag indicating whether or not the key was found::

	k, ok := votes["Kennedy"]
	if ok {
		fmt.Printf("%v\n", k)
	} else {
		fmt.Println("no candidate by that name")	
	}

It's entirely up to the programmer to check this flag!

A common use of this is to test if a given key is in a map. For instance::

	_, present := votes["Kennedy"]  // _ is the blank identifier; we use it
	                                // here because we don't care about the
	                                // associated value

If ``present`` is ``true``, they ``"Kennedy"`` is a key in the list. If it's
``false``, then ``Kennedy`` is not in the list.


Deleting Items in a Map
-----------------------

To delete a key and its associated value from a map, use the built-in
``delete`` function::

	delete(votes, "Yan")

If ``"Yan"`` happened to not be a key in ``votes``, then this statement
doesn't modify the map.


Limitations on Keys
-------------------

Not all data types are allowed to be keys in a map. Any data type that
supports equality, such as integers, floats, strings, pointers, structs, and
arrays **can** be used as a key. But, slices and other maps **cannot** be keys
because they do not have equality defined for them.


Processing a Map with a For-loop
--------------------------------

It's easy to process every element of a map using a ranged for-loop::

	for key, value := range votes {
		fmt.Printf("votes[\"%s\"] = %d\n", key, value)
	}

Or if you just want the keys::

	for key := range votes {
		fmt.Printf("votes[\"%s\"] = %d\n", key, votes[key])
	}


Questions
---------

#. White is the type of a map whose keys are integers and whose values are 
   booleans.

#. What are two different data types that *cannot* be used as keys in a map?

#. Can ``nil`` be a key in a map? If no, why not? If yes, then what is the 
   type for a map that can have ``nil`` as a key?

#. Write a function that takes a map of type ``map[string]int`` as input, and
   returns the key *and* value of the pair with the greatest key.

#. Write a function that takes a map of type ``map[string]int`` as input along
   with a target string ``val``, and returns a slice containing all the keys
   whose value equals ``val``.


Sample Program
--------------

The following program is based on an idea from the `XKCD <https://xkcd.com/>`_
comic strip. It asks the user to type in some words, and then it checks to see
which of those words are in
:download:`xkcdWordlist.text <_downloads/xkcdWordlist.text>`, a file of the 3000
or so most common English words.

A map is a good data structure for this problem because testing if a word is
in it can be done in O(1) time, on average. If, instead, you used a slice,
then the retrieval would take O(n) time on average.

::

	package main

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

	func main() {
		//
		// load all the words into a map
		//
		var dictionary map[string]bool = make(map[string]bool)

		// read entire file into one slice of bytes
		allBytes, err := ioutil.ReadFile("xkcdWordlist.text")
		if err != nil {
			panic("no word file to read!")
		}

		// convert the byte slice to a string
		bigString := string(allBytes)

		// split the string into words
		words := strings.Split(bigString, " ")

		// add the words to the dictionary
		for _, w := range words {
			dictionary[w] = true
		}
		fmt.Printf("%v words in dictionary\n", len(dictionary))

		//
		// check words typed by the user
		//
		console := bufio.NewReader(os.Stdin)
		for {
			// print a prompt
			fmt.Print("--> ")

			// read, as a slice of bytes, the entire line of text entered by the user
			lineBytes, _, _ := console.ReadLine()
			// fmt.Printf("(input=\"%v\")\n", lineBytes)

			// convert the line to a string
			line := string(lineBytes)

			// split the string into words
			userWords := strings.Split(line, " ")
			// fmt.Printf("(%v)\n", userWords)

			// check each word to see if it is in the dictionary
			for _, w := range userWords {
				if _, exists := dictionary[w]; !exists {
					fmt.Printf("\"%v\" is too complex!\n", w)
				}
			}
		} // for
	}