ParkingLot.cpp

using namespace std;
using boost::optional;

//  Implements a parking lot utility: you can ask it for an available space for 
//  a car of a certain size, ask it to find a car's parking spot given its license
//  plate, ask what car is parked in a specific spot, etc.  

//  This code is organized top down: first the parking_lot class, then 
//  the distance class ('dist') and some functions to compare IEEE doubles, then
//  the structs 'car' and 'parking_space'.  I made some assumptions, like that each 
//  space is identified by a single letter for the row and an integer for the number
//  within that row, that there is only one level for the parking lot, etc.  

// a constant to represent that a parking space is empty
const optional<car> no_car = optional<car>();

//  ****** instances represent a single-level parking lot ******
//
class parking_lot {
public:
  parking_lot() {};
  void add_space( const dist& w, const dist& l, char row, unsigned int no );
  void add_to_row( const dist& w, const dist& l, char row,   // add multiple
                   unsigned int first, unsigned int count ); // spaces
  bool park_car( const car & veh );
  bool remove_car( const string & license );
  const parking_space & find_car( const string & license ) const;
  optional<car> find_occupant( char row, unsigned int no ) const;
  void print_report() const;
private:
  // stores all the parking spaces in a single row
  typedef map<char, vector<parking_space>> row_data;
  row_data spaces_by_row;
  // parking_space_ref allows us to efficiently point to entries in
  // the vector of row_data.  we can't use a direct pointer to the
  // individual parking_spaces, the vector could be reallocated and
  // moved  and then the individual pointers would be invalid
  typedef pair<vector<parking_space>*,int> parking_space_ref;
  unordered_map<string, parking_space_ref>  license_plate_map;
  deque<parking_space_ref> available_spaces;
  static parking_space & get_space( parking_space_ref r ) 
    { return  (*get<0>(r))[get<1>(r)]; };
};

void parking_lot::add_space(const dist& w, const dist& l, char row, unsigned int no ) {
  add_to_row( w, l, row, no, 1 ); 
}

void parking_lot::add_to_row(const dist& w, const dist& l, char row, 
                             unsigned int first, unsigned int count ) {
  auto mypair = spaces_by_row.find(row);
  if ( spaces_by_row.end() == mypair )  {
    spaces_by_row[row] = vector<parking_space>();
    mypair = spaces_by_row.find(row);
  }
  vector<parking_space>& vec = get<1>(*mypair);
  for (unsigned int i=first; i<first+count; ++i)  {
    vec.push_back( parking_space{ w, l, row, i, no_car } ); 
    available_spaces.push_back( make_pair(&vec,vec.size()-1) );
  }
}

bool parking_lot::park_car( const car & veh ) {
  dist  l = veh.length;
  dist  w = veh.width;
  auto spaceref = find_if( available_spaces.begin(), available_spaces.end(), 
             [&l,&w, this] (parking_space_ref ref)  {
             parking_space &p = get_space(ref);
             return (   is_greater(p.length,l)
                     && is_greater(p.width,w)  ); });
  if ( available_spaces.end() != spaceref ) {
    auto & space = get_space( *spaceref );
    space.occupant = optional<car>(veh);
    license_plate_map[veh.license_plate] = *spaceref;
    available_spaces.erase(spaceref);
    return true;
  } else {
    return false;
  }
}

bool parking_lot::remove_car( const string & license )  {
  auto entry = license_plate_map.find(license);
  if ( entry == license_plate_map.end() )  {
    return false;
  }
  parking_space &space = get_space(get<1>(*entry));
  space.occupant = no_car;
  license_plate_map.erase(license);
  available_spaces.push_back(get<1>(*entry));
  return true;
}

void parking_lot::print_report() const {
  cout << endl << endl << "Parking Lot Report" << endl;
  for ( auto& mypair : spaces_by_row ) {
    cout << "  Row " << get<0>(mypair) << endl;
    for ( auto& space : get<1>(mypair) )  {
      cout << "    Space " << space.number << " : ";
      if ( !space.occupant )  {
        cout << "empty" << endl;
      }  else  {
        cout << space.occupant.get().license_plate << endl;
      }
    }
  }
  cout << endl;
}

optional<car> parking_lot::find_occupant( char row, unsigned int no ) const {
  auto mypair = spaces_by_row.find(row);
  if ( spaces_by_row.end() != mypair )  {
    const vector<parking_space>& vec = get<1>(*mypair);
    for (auto& space : vec)  
      if ( space.number == no )
        return space.occupant;
  }
  return no_car;
}

const parking_space & parking_lot::find_car( const string & license ) const {
  const parking_space_ref &  ref = license_plate_map.at(license);
  vector<parking_space> * vec = get<0>(ref);
  int index = get<1>(ref);
  return (*vec)[index];
}


//  ****** instances denote a distance, including units of measurement ******
//
class dist {
public:
  enum dst_units { CM = 0, INCH = 1, FOOT = 2, METER = 3, YARD = 4 };
  dist( dst_units u, double d ) : units(u),distance(d) {};
  double get_dist( dst_units u ) const { return distance*conversion(units, u); };
  void set_dist( dst_units u, double d )  { units = u; distance = d; };
  static double conversion( dst_units from, dst_units to );
private:
  dst_units units;
  double    distance;
};

bool is_greater( const dist & a, const dist & b )  {
  return double_greater( a.get_dist(dist::CM), b.get_dist(dist::CM) );
};

constexpr static double ft = 2.54*12.0;
constexpr static double yd = ft * 3.0;
static map<dist::dst_units, double> conversions = 
  {  {dist::CM, 1.0}, {dist::INCH,2.54}, {dist::FOOT,ft}, 
     {dist::METER,100.0}, {dist::YARD, yd} };

double dist::conversion( dst_units from, dst_units to )  {
  return conversions[from] / conversions[to];
}


//  ****** functions to compare IEEE double precision numbers ******
//  IEEE double has 52 bits of mantissa.  This gives 15 digits.  
//  Don't see any constants in math.h that help us here.
const int MAX_DBL_SIG_FIG=15;

bool double_equal( double a, double b, 
                   unsigned int sig_figs = MAX_DBL_SIG_FIG )  {
  int exponent = -min( (unsigned int)MAX_DBL_SIG_FIG, sig_figs );
  double allowable_delta = a * pow( 10.0d, exponent );
  return ( abs(a-b) < allowable_delta );
}

bool double_greater( double a, double b, 
                     unsigned int sig_figs = MAX_DBL_SIG_FIG )  {
  return ( a > b && !double_equal(a,b,sig_figs) );
}


//  ****** instances represent a car, within the context of a parking lot
//  _for our purposes here_, this can be a POD struct, so it is
//
struct car {
  dist width, length, height;
  string license_plate;
};


//  ****** instances represent a single uncovered parking space
//  also POD, for our purposes here
//
struct parking_space {
  dist width, length;    // uncovered, so no height
  char row;
  unsigned int number;
  optional<car> occupant;
};