CMSC 214 - Project #3

C M S C 2 1 4
C o m p u t e r S c i e n c e I I
S p r i n g 2 0 0 2

BstMap Specifications

Background

A map class associates elements of one type (called the key type) with elements of a second type (called the data type). This is often known as an associative array. A regular array uses int indexes, while an associative array uses indexes from the key type.

For example, you can associate a person's name (a Name object), with a BankAccount object. Here are some examples of BstMap.

  BstMap<string, float>   list;

  // map "John Doe" to 12000.94
  list.map( "John Doe", 12000.94 ) ;
 
  // map "Mary Deer" to 23411.23
  Pair pair( "Mary Deer", 23411.23 ) ;
  list.addPair( pair ) ;

  if ( list.contains( "John Doe" ) )
     cout << "OK << endl ;

DO NOT CHANGE PARAMETERS OF PUBLIC METHODS. If necessary, call a helper function with additional parameters.

BstMap

This class is templatized using
template <class First, class Second>
It uses a BST containing a Pair and PairComparator.

Data Members

Declaration	Description
BstSortedList< Pair, PairComparator > lookup	A map consisting of Pairs

A pair consists of two types: a key type and a value type. It has one object of each type in it.

Public Methods

BstMap() ;

Creates an empty map of Pairs.

bool map( const First &firstIn, const Second &secondIn ) ;

If a map does NOT exists between firstIn and secondIn, th this method creates a Pair and add it to the BST, and returns true. If a map already exists between firstIn and secondIn, it updates the value of secondIn and return false (since a new map was not created).

bool addPair( const Pair & pair ) ;

Adds a pair to the BST, if it doesn't already exist, and returns true. If it already exists (i.e., there is a pair whose First value is equal to pair's first value, then it returns false, but it does allow the update the pair in the BST (with the new Second value from pair).

bool contains( const First &firstIn ) const ;

Return true if there exists a Pair object in the BST whose first value is equal to firstIn.

Second & operator[]( const First &firstIn ) ; ;

Given a firstIn value, this returns a reference to the Second from a Pair object in the BST with the same First value as firstIn. If such an object does not exist, then a Pair with its First value set to firstIn is created and added to the BST, and a reference to its Second value returned. To implement, you may need to use the const_cast operator to remove the constness.

const Second & operator[]( const First &firstIn ) const ;

In this version, if there is a Pair object in the BST with the same First value as firstIn, then a const reference to that Pair object's second value is returned. However, if there is no such Pair in the BST, then an error occurs. (You can exit, or produce a dummy return value).

int size() const ;

Returns the number of Pair objects in the BST.

void print( std::ostream &out ) const ;

Using the print() method of BST, prints the structure of the BST with the Pair objects.

There is a non-member function for the output operator.

template <class First, class Second> std::ostream & operator<<( std::ostream & out, const BstMap<First, Second> & other ) ;

Using the print() method of BST, prints the structure of the BST with the Pair objects. Returns out.

You may add private helper functions if you wish.

See the class syllabus for policies concerning email
Last Modified: Mon Mar 18 20:37:48 EST 2002

Web Accessibility