EECS268:Lab6

Navigation
Home
Information
Syllabus Schedule
Classwork
Labs Submitting Work

Due time

This lab is due Friday July 17th by 11:59pm

Lab conduct

• Do not use any unauthorized aid, such sites like rentacoder or chegg to obtain answers
• Do not use code provided by another student
• Do not reuse code (by you or anyone) from prior semesters
• If you need help, seek it from:
  • Your lab TA.
  • Me, Dr. Gibbons, my email is jwgibbo@ku.edu / jwgibbo@gmail.com
• If equipment you don't own (e.g. cycle servers) needs attention or you're having account issues put in a ticket!

Overview

In this lab you will make a "Pokedex" that will allow users to look up a Pokemon by it's pokedex number (basically an id) and retrieve all information about that pokemon. You read in the Pokemon's name and their corresponding Japanese translation from a file. Then, you will allow the user to query your "Pokedex".

Binary Search Trees

See home page for video lectures and notes.

Remember, you'll need to update (maybe upgrade?) your Node class to be BinaryNodes with left and right pointers.

Pokemon File

You can download a sample file here. Each line is organized in the following manner (white-space delimited):

<american pokemon name> <pokedex number> <japanese pokemon name>

American Name	What the pokemon is called in the U.S.A.
pokedex number	A number associated with a particular pokemon. Think of it as a pokemon's SSN
Japanese pokemon name	What the pokemon is called in Japan

Example entries:

Abra	63	Casey
Aerodactyl	142	Ptera
Alakazam	65	Foodin
Arbok	24	Arbok
Arcanine	59	Windie
Articuno	144	Freezer
Beedrill	15	Spear
Bellsprout	69	Madatsubomi
Blastoise	9	Kamex
Bulbasaur	1	Fushigidane

This lab you won't be told how many entries are in the file, but reading until the end of a file isn't hard:

Example:

//assume we've opened the file an have some temp variables for reading

while( myInFile >> tempUS >> tempID >> tempJP )
{
    //do something with temp variables, perhaps build a Pokemon object and add it to the BST
}

I know that looks weird, but essentially ifstream is overloaded to return false when it hits the end of the file.

Requirements

The next two labs will involve Binary Search Trees. The table lists the functionality that you can accomplish by loading the Pokedex entries into a single Binary Search Tree. Get everything from this lab working and tested before moving on to next week's lab.

Notes:

• The user will provide the name of an input file formatted in the way described above from the command line
• Using that file, create and load a BST full of Pokemon
• Until the user wants to quit, let them use your pokedex in the ways listed in the table below:
  • The table list the menus labels and desired outcomes, but you will need to the BinarySearchTree method that accomplishes the task
  • Example: If the user wants to Search you will need to call the contains(key) method from the BinarySearchTree class to verify whether or the word is in the pokedex

Phase 1

Search	Given pokedex number (id) print all information (US name, Japanese name, pokedex number) to the user
Add	Prompt the user for a new Pokemon name (US), then new Japanese name and Pokedex number and add the entry to the tree. Duplicates should not be allowed. Make your add method throw an exception (std::runtime_error) if a duplicated is attempted to be added.

BST Interface

tempate <typename ItemType, typename KeyType>
class BinarySearchTreeInterface
{
    public:
    virtual ~BinarySearchTreeInterface(){}
    virtual void add(ItemType entry) = 0;
    virtual ItemType search(KeyType key) const = 0;
    virtual void clear() = 0;
    //More methods to come in next lab
};

Implementation Details

• We ask that your BST be templated with two types, and ItemType and a KeyType
  • The ItemType would be the type returned from a search
  • The KeyType would be the type that you can search on
  • For example, if I search for the Pokemon with ID 25 I should get back the whole entry for that word when I search.
• The BST should only use the default comparison operators, and not be coupled to the methods of any specific class
  • Overload the needed comparison operators for your class
  • We will order them alphanumerically (case-insensitive) based off their IDs
• If a copy is made and edits are performed, the original should remain unchanged.

Rubric

• 75% Pokedex Interaction
  • 25% Searching
  • 30% Adding entry
  • 20% Clearing the tree (and memory leaks as a whole)
• 10% Program stability
• 5% logical user interface
• 10% Needed Operators overloaded

Emailing Your Submission

Once you have created the tarball with your submission files, email it to your TA. The email subject line must look like "[EECS 268] SubmissionName":

[EECS 268] Lab 0#

Note that the subject should be exactly like the line above. Do not leave out any of the spaces, or the bracket characters ("[" and "]"). In the body of your email, include your name and student ID.