Lab 09 - Pokémon (11/23/2021)

---

Sets

A std::set is an associative container that contains a sorted set of unique objects of type Key.

• The value of an element in a set is itself the key of type T, and must be unique.
• Sorting is done using the key comparison function Compare.
• Search, removal, and insertion operations have logarithmic complexity.
• The value of an element in a set cannot be modified once in the container (the elements are always const), but they can be inserted or removed from the container.
• C++ STL sets are usually implemented as red-black trees, but can be implemented using any binary search tree or an ordered linked list.

Everywhere the standard library uses the Compare requirements, uniqueness is determined by using the equivalence relation. In imprecise terms, two objects a and b are considered equivalent if neither compares less than the other: !comp(a, b) && !comp(b, a).

Elements in a hash_set are not sorted in any particular order, but are organized into buckets depending on their hash values which allows fast access to individual elements directly by their values (with a constant average time complexity on average). hash_sets are typically implemented using a linked list for each hash table index, which is referred to as bucket hashing or chaining.

Maps

A std::map is an associative container that stores elements formed by a combination of a key value and an associated mapped value.

• The types of the map key and value may differ, and are grouped together in a Pair class.
• The mapped values in a map can be accessed directly by their corresponding key using the bracket operator ((operator[]).
• Ordered maps are typically implemented as binary search trees.
• An iterator is used to access map elements in a sorted order.

A std::hash_map is also an associative container that contains key-value pairs with unique keys, but the keys are not sorted.

• You can use [] operator when you want to set value for a key.
• Search, insertion, and removal of elements have average constant-time complexity.
• Internally, the elements in a hash_map are not sorted in any particular order, but organized into buckets.
• Which bucket an element is placed into depends entirely on the hash of its key.
• Access to individual elements is fast since once the hash is computed, it refers to the exact bucket the element is placed into.
• An iterator is used to access unordered hash map elements, but in no specific order.

For either an ordered or unordered hash map, if you try to access a key value using index operator [], one of two things happen:

1. The map contains this key, so the function will return the corresponding key value.
2. Or, the map doesn't contain the key, in which case, the function will automatically add a key to the map with null value. Map size will increase by one.

Ordered map containers are generally slower than hash_map containers to access individual elements by their key, but they allow the direct iteration on subsets based on their order.

Insertion into a map

1. Assignment using array index notation:

   Foo["Bar"] = 12345;

   Note: [] will replace the old value (if any). Hence, use [] for updating.
2. Assignment using member function insert() and pair:

   Foo.insert(pair("Bar", 12345));

The key values of elements in a hash_map are not sorted in any particular order, but are organized into buckets depending on their hash values which allows fast access to individual elements directly by their values (with a constant average time complexity on average). hash_maps are typically implemented using a linked list for each hash table index, which is referred to as bucket hashing or chaining.

In either type of map, the mapped elements can be accessed directly by their corresponding key using the bracket operator ((operator[]). A common example of the usefulness of a map is in mapping grade letters to their respective GPA values. Try to get this code to compile and mess around with it.

#include <map>               //contains the STL implementation of Map
#include <string>            //contains the STL string
#include <iostream>
int main()
{
   map<string, double> GPAs; //initialization of an empty map;
   GPAs["A"] = 3.0;          // Map "A" to 3.0
   GPAs["A"] = 4.0;          // Overwrite "A" to 4.0
   GPAs["A-"] = 3.7;
   GPAs["B+"] = 3.4;
   ...
   // Print the value mapped to "A-".
   cout << "The GPA value for a A- is: " << GPAs["A-"];
   return 0;
}

Hashing

In computing, a hash table (hash map) is a data structure which implements an associative array abstract data type, a structure that can map keys to values.

• A hash table uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.
• Ideally, the hash function will assign each key to a unique bucket, but most hash table designs employ an imperfect hash function, which might cause hash collisions where the hash function generates the same index for more than one key.
• Such collisions must be accommodated in some way.
• In a well-dimensioned hash table, the average cost (number of instructions) for each lookup is independent of the number of the number of elements stored in the table.
• Well designed hash tables also allow for arbitrary insertions and deletions of key-value pairs, at (amortized) constant average cost per operation.

In many situations, hash tables turn out to be on average more efficient than search trees or any other table lookup structure. For this reason, they are widely used in many kinds of computer software, particularly for associative arrays, database indexing, caches, and sets. Hashed data structures maintain a collection of key–value pairs and return the value associated with a given key. Each cell of a hash table stores a single key–value pair.

Hash Functions:

If all keys were known ahead of time, a perfect hash function could be designed to create a perfect hash table that has no collisions. Fortunately, a good hash function will still distribute the keys uniformly over the buckets, and minimize the clustering of hash values that are consecutive in the probe order.

For string keys, a character polynomial of the form:

s0 × 31n-1 + s1 × 31n-2 + s2 × 31n-3 + ... + sn-1

Probing Technique: Chaining

In the method known as chaining, each bucket is independent, and has some sort of list of entries with the same index. The time for hash table operations is the time to find the bucket (which is constant) plus the time for the list operation. In a good hash table, each bucket has zero or one entries, and sometimes two or three, but rarely more than that. Therefore, structures that are efficient in time and space for these cases are preferred.

Probing Technique: Linear Probing

Linear probing is a scheme in computer programming for resolving collisions in hash tables. When the hash function causes a collision by mapping a new key to a cell of the hash table that is already occupied by another key, linear probing searches the table for the closest following free location and inserts the new key there. Lookups are performed in the same way, by searching the table sequentially starting at the position given by the hash function, until finding a cell with a matching key or an empty cell.

While simple and fast, linear probing tends to form clusters of keys in the hash table, causing longer search chains.

For a given hash value, the indices generated by linear probing are as follows:

hash = (hash + 1) % table_size;

Probing Technique: Quadratic Probing

Quadratic probing is another scheme for resolving collisions in hash tables that minimizes primary clustering of hash table keys. When a key's hash value indicates it should be stored in an already-occupied slot or bucket, quadratic probing operates by taking the original hash index and adding successive values of an arbitrary quadratic polynomial until an open slot is found.

Quadratic probing can be a more efficient algorithm in a closed hashing table, since it better avoids the clustering problem that can occur with linear probing, although it is not immune the the affect. It provide good memory caching because it preserves some locality of reference. An example sequence using quadratic probing is:

Hash + 12, Hash + 22, Hash + 32,..., Hash + k2

Pokémon

Pokémon is a series of video games developed by Game Freak and published by Nintendo as part of the Pokémon media franchise. Review the "Pokémon battles" section of this wikipedia page if you are unfamiliar with the mechanics. We will be simplifying these mechanics down for the purpose of our lab. We will limit the number of types that a Pokémon can be to just one. Instead of Hit Points, we will use a system more closely related to a round of Rock-Paper-Scissors; whichever Pokémon uses the more effective move against the other wins.

Battles:

Battles will be much simpler than they are in the actual games. Each Pokémon has a single type (fire, water, rock). Each move (attack) is a single type.

• Some move types are "super effective" or strong against Pokémon of certain types. For example, water is super effective against fire.
• Some move types are "not very effective" or weak against Pokémon of certain types. For example, fire is not very effective against water.
• Any move type that is neither strong nor weak against a Pokémon of a certain type is "regularly effective. You will read in tables of effectivities and ineffectivities. Any combination not found in either of the two tables is regarded as regularly effective. For example, rock is regularly effective against water because it has no advantage or disadvantage against it (not found in either effective or ineffective maps).
• Move types can have any number of Pokémon types that they are strong or weak against.

In a single battle, two Pokémon are chosen and each Pokémon chooses one move to attack the other one with. Whichever Pokémon attacks with the more effective move wins the battle. If the two moves have equal effectiveness, then the battle ends in a tie.

Requirements:

1. Your Set class inherits from the SetInterface class (SetInterface.h).
   • Implements SetInterface.
   • No duplicates in Set container.
   • Set toString() returns ordered elements.
2. Implement a HashMap class that inherits from the HashMapInterface class (HashMapInterface.h).
   • Use a string hash function for accessing data as explained above with a HASH_CONSTANT equal to 3.
   • Use quadratic probing for collision resolution.
   • Dynamically allocate the array for your hash table.
   • Use DEFAULT_MAP_HASH_TABLE_SIZE as the initial hash table size.
   • Before adding a new key to the hash map, if the load factor (# of elements x 100 / key array size) is greater than REHASH_THRESHOLD, a new array of double the current array size is created, the old keys are rehashed into the new array, and the old array is deleted.
3. Each Pokémon is stored in a HashMap<string,string>.
4. Each Move is stored in a HashMap<string,string>.
5. Each Efficiency is stored in a HashMap<string,Set<string>>.
6. Each Inefficiency is stored in a HashMap<string,Set<string>>.
7. Report who wins each battle.

8. The following summarizes the commands used in the Maps and Sets lab:

INPUT	OUTPUT
Set: <item> { <item>} Example input: Set: dog dog cat cat cat dog	Set: dog dog cat cat cat dog [cat dog]
Pokemon: <pokemon> <AType> Example input: Pokemon: Charmander fire Pokemon: Squirtle water	Pokemon: Charmander fire Pokemon: Squirtle water
Move: <move> <Move_Type> Example input: Move: flamethrower fire Move: water_gun water	Move: flamethrower fire Move: water_gun water
Effective: <attack> <PType>{ <PType>} Example input: Effective: fire grass ice bug steel Effective: water ground rock fire	Effective: fire grass ice bug steel Effective: water ground rock fire
Ineffective: <attack> <PType>{ <PType>} Example input: Ineffective: fire rock fire water Ineffective: water water grass	Ineffective: fire rock fire water Ineffective: water water grass
Pokemon Example input: Pokemon	Pokemon: 2/31 [0:Squirtle->water] [30:Charmander->fire]
Moves Example input: Moves	Moves: 2/31 [29:water_gun->water] [30:flamethrower->fire]
Effectivities Example input: Effectivities	Effectivities: 2/31 [17:water->fire,ground,rock] [19:fire->bug,grass,ice,steel]
Ineffectivities Example input: Ineffectivities	Ineffectivities: 2/31 [17:water->fire,ground,rock] [19:fire->bug,grass,ice,steel]
Battle: <P1> <A1> <P2> <A2> Example input: Battle: Charmander flamethrower Squirtle water_gun	Note: The auto-grader will be checking for the red lines only. Battle: Charmander flamethrower Squirtle water_gun Charmander (flamethrower) vs Squirtle (water_gun) Charmander is a fire type Pokemon. Squirtle is a water type Pokemon. flamethrower is a fire type move. water_gun is a water type move. flamethrower is super effective against [bug,grass,ice,steel] type Pokemon. flamethrower is ineffective against [fire,rock,water] type Pokemon. Charmander's flamethrower is ineffective against Squirtle water_gun is super effective against [fire,ground,rock] type Pokemon. water_gun is ineffective against [grass,water] type Pokemon. Squirtle's water_gun is super effective against Charmander In the battle between Charmander and Squirtle, Squirtle wins!

Steps to Success:

• Step 1 - Design and implement a Set class that inherits from the SetInterface.h interface class.
  • This should be the easiest part of the lab. You have already created a BST class that the Set class could adapt. Adjust your BST toString() method to return elements in sorted (infix) order.
  • You could also use your LinkedList class, but you would need to eliminate duplicates and insert in sorted order. (An ordered linked list has-a singly linked list and delegates all method calls to the linked list except for insertion. Just following the links would be an in-order traversal.)
  • Your Set class must have a deep copy constructor and assignment operator. (Resizing of your HashMap requires deep copies.)
  • Unit test the functionality of your Set implementation.
• Step 2 - Design and implement a HashMap class that inherits from the HashMapInterface.h interface class.
  • Use string hashing as explained above for accessing map values. Use "unsigned long" data type in calculating your string hash to avoid data type overflow. Return a "size_t" hash index.
  • Use quadratic probing for collision resolution.
  • You must use a dynamically allocated array for your hash table that grows if the load factor exceeds the LOAD_THRESHOLD.
  • Use DEFAULT_MAP_HASH_TABLE_SIZE as the initial hash table size.
  • Unit test the functionality of your HashMap implementation.
• Step 3 - Populate pokemon, move, effectivities, and ineffectiveties maps.
  • Read in each Pokémon and store its type in a HashMap<string,string>.
  • Read in each move and store its type in a HashMap<string,string>.
  • Read in the type effectivities and ineffectivities and store them in HashMap<string,Set<string>>s.
  • Report who wins each battle.
  • Check to make sure you've correctly read in this information.
• Step 4 - Implement the battle simulation.
  • For each battle, read in each Pokémon and the move that it is using.
  • Then check which move is the most effective against the other Pokémon and report the winner.
  • Hint: using the Set count member function, a battle winner can be determined as follows:

    int damageAToB = effectivities[moves[pokemonA_attack]].count(pokemons[pokemonB])
                     - ineffectivities[moves[pokemonA_attack]].count(pokemons[pokemonB]);
    int damageBToA = effectivities[moves[pokemonB_attack]].count(pokemons[pokemonA])
                     - ineffectivities[moves[pokemonB_attack]].count(pokemons[pokemonA]);
    // If (damageAToB - damageBToA) is 0, then there is a tie.
    // If (damageAToB - damageBToA) > 0, then pokemonA wins.
    // If (damageAToB - damageBToA) < 0, then pokemonB wins.

Destructors:

In this lab you will need to create maps of key type: string and value type: set. If you're not careful with how you set this up, some crazy things can happen. For example, look at the following code:

Map<string, Set<string>> effectiveTypes;
while(getline(inputFile, line))
{
   Set<string> effectives;
   while(line >> type)
   {
      effectives.insert(type);
   }
   effectiveTypes[baseType] = effectives;
}
cout << effectiveTypes;

To avoid this, you may try the following:

Map<string, Set<string>> effectiveTypes;
while(getline(inputFile, line))
{
   Set<string> effectives;
   while(line >> type)
   {
      effectiveTypes[baseType].insert(type);
   }
}
cout << effectiveTypes;

Pokemon Illiterates:

For us pokemon illiterates, here is a very helpful mapping for Pokemon Battles using the Set count member function:

Given Pokemon1 uses Move1 against Pokemon2 using Move2:

int damage1To2 = effectivities[moves[Move1]].count(pokemon[Pokemon2])
                 - ineffectivities[moves[Move1]].count(pokemon[Pokemon2]);
int damage2To1 = effectivities[moves[Move2]].count(pokemon[Pokemon1])
                 - ineffectivities[moves[Move2]].count(pokemon[Pokemon1]);

// if ((damage1To2 - damage2To1) > 0) Pokemon1 Wins!
// else if ((damage1To2 - damage2To1) < 0) Pokemon2 Wins!
// else Tie!

Understanding Valgrind Output._(collapse)

Instructions for submitting your lab:

• Zip all your lab source files (.cpp, .hpp, .h) into one folder. DO NOT INCLUDE YOUR WHOLE PROJECT!
• Submit your zipped lab source using the "Labs" tab on the class website.
• Your submitted lab source will be compiled and executed using a lab gcc compiler.
• Both input and output files will be specified by command line arguments.
• An auto-grader will compare your output files with expected results and you will shortly receive an accumulative score.
• The auto-grade process may abort on the first error. If so, correct the error and try again.
• You may re-submit your zipped source as many times as you like.

Use the following input and resulting output files in testing the Maps and Sets lab.

The auto-grader will be expecting to find in your output file the following sections:

s0 × 3n-1 + s1 × 3n-2 + s2 × 3n-3 + ... + sn-1

s0 × 3n-1 + s1 × 3n-2 + s2 × 3n-3 + ... + sn-1

The lab source will be peer reviewed using the following rubric: