Replace the tables and linked lists with binary search trees. below is the given

ID: 3845296 • Letter: R

Question

Replace the tables and linked lists with binary search trees.

below is the given code that need modification.

CARGO.H

#pragma once

#include <iostream>
#include <limits.h>
#include <string>
using namespace std;

class Cargo
{
public:
   static int read(void);
   static int charToCargo(char);
   static char cargoToChar(int);
   static bool isCargo(char);

   static const int BADCARGO = -1;
   static const int CABBAGES = 0;
   static const int GOAT = 1;
   static const int SHOWMAN = 2;
   static const int WOLF = 3;
   static const int NOCARGO = 4;
   static const int CARGO_AND_SHOWMAN = 5;
};

RIVER.H

#pragma once
#include <math.h>
#include "cargo.h"

class River
{
public:
   River(void);
   void show(void);
   void cross(int);
   bool stop(void);

private:
struct Transition { unsigned this_side; unsigned that_side; unsigned type; };

   static const unsigned start_state = 0;
   static const unsigned stop_state = 15;
   bool _far_side[Cargo::CARGO_AND_SHOWMAN];
   bool _near_side[Cargo::CARGO_AND_SHOWMAN];
   void copy(bool[], bool[]);
   unsigned state(bool[]);
   bool goodCrossing(bool [], bool []);
   bool badCrossing(bool[], bool[]);
};

CARGO.CPP

#include "Cargo.h"

int Cargo::charToCargo(char cargo)
{
   switch(cargo)
   {
   case 'w': case 'W':
       return WOLF;
   case 's': case 'S':
       return SHOWMAN;
   case 'g': case 'G':
       return GOAT;
   case 'c': case 'C':
       return CABBAGES;
   default:
       return NOCARGO;
   }
}
char Cargo::cargoToChar(int cargo)
{
   switch(cargo)
   {
   case WOLF:
       return 'W';
   case SHOWMAN:
       return 'S';
   case GOAT:
       return 'G';
   case CABBAGES:
       return 'C';
   case NOCARGO:
       return 'N';
   default:
       return 'B';
   }
}
bool Cargo::isCargo(char candidate)
{
   switch(candidate)
   {
   case 'w': case 'W':
   case 's': case 'S':
   case 'g': case 'G':
   case 'C': case 'c':
   case 'N': case 'n':
       return true;
   default:
       return false;
   }
}
int Cargo::read(void)
{
   char cargo;
   do
   {
       cout << "Enter W for Wolf" << endl;
       cout << "Enter N for no cargo" << endl;
       cout << "Enter G for Goat" << endl;
       cout << "Enter C for cabbages" << endl;
       cout << "Enter cargo - ";
       cin.get(cargo);
       cin.ignore(numeric_limits<int>::max(), ' ');
   }
   while(!isCargo(cargo));
   return charToCargo(cargo);
}

RIVER.CPP

#include "River.h"

River::River(void)
{
   for (int pos = Cargo::CABBAGES; pos <= Cargo::WOLF; pos++)
       _far_side[pos] = false;
}
void River::show(void)
{
   for(int pos = Cargo::CABBAGES; pos <= Cargo::WOLF; pos++)
       if(_far_side[pos])
           cout << "- | " << Cargo::cargoToChar(pos) << endl;
       else
           cout << Cargo::cargoToChar(pos) << " | -" << endl;
   cout << endl;
}
void River::cross(int cargo)
{
   copy(_far_side, _near_side);
   _far_side[Cargo::SHOWMAN] = !_near_side[Cargo::SHOWMAN];
   _far_side[cargo] = !_near_side[cargo];
   if(!goodCrossing(_near_side, _far_side))
       copy(_near_side, _far_side);
}
void River::copy(bool source[], bool sink[])
{
   for(int pos = Cargo::CABBAGES; pos <= Cargo::WOLF; pos++)
       sink[pos] = source[pos];
}
unsigned River::state(bool river[])
{
   unsigned _state = 0;
   for(unsigned pos = Cargo::CABBAGES; pos <= Cargo::WOLF; pos++)
       _state = _state + river[pos] * (int)pow(2, pos);
   return _state;
}
bool River::goodCrossing(bool this_side[], bool that_side[])
{
   static const unsigned I = 0;
   static const unsigned B = 1;
   static const unsigned G = 2;
   static const unsigned n_transitions = 20;
   //The first list containing only good state pairs
   //Function searches the list and matches only good state pairs
   //If not found moves on to badCrossing function.
   static Transition transit[] =
   { {0,6,G},
   {1,7,G},{1,13,G},
   {2,6,G},{2,7,G},{2,14,G},
   {6,0,G},{6,2,G},
   {7,1,G},{7,2,G},
   {8,13,G},{8,14,G},
   {9,13,G},{9,15,G},
   {13,1,G},{13,8,G},{13,9,G},
   {14,2,G},{14,8,G},
   {15,9,G} };

   unsigned this_side_state = state(this_side);
   unsigned that_side_state = state(that_side);
   unsigned id = 0;
   while (id < n_transitions && (transit[id].this_side != this_side_state || transit[id].that_side != that_side_state))
       id++;
   return transit[id].type == G;
}

bool River::badCrossing(bool this_side[], bool that_side[])
{
static const unsigned B = 1;
static const unsigned g_transitions = 20;

static Transition transit[] =

       //The second list containing only bad state pairs.
       //create an array of error messages.
       //associate error message with each bad state pair.
       { {0,4,B},{0,5,B},{0,12,B},
       {1,5,B},
       {3,7,B},{3,15,B},
       {4,0,B},
       {5,0,B},{5,1,B},
       {7,3,B},
       {8,12,B},
       {10,14,B},{10,15,B},
       {11,15,B},
       {12,0,B},{12,8,B},
       {14,10,B},
       {15,3,B}, {15,10,B},{15,11,B} };

   unsigned this_side_state = state(this_side);
   unsigned that_side_state = state(that_side);
   unsigned id = 0;
   while (id < g_transitions && (transit[id].this_side != this_side_state || transit[id].that_side != that_side_state))
       id++;
   return transit[id].type == B;
}

bool River::stop(void)
{
return state(_far_side) == stop_state;
}

SOURCE.CPP

#include <iostream>
#include <string>
#include "cargo.h"
#include "river.h"
using namespace std;

int main()
{
   River river;
   river.show();
   do
   {
       int cargo = Cargo::read();
       river.cross(cargo);
       river.show();
   }
   while(!river.stop());

system("pause");
return 0;
}

Explanation / Answer