Last active
January 3, 2016 07:09
-
-
Save lshort/8427405 to your computer and use it in GitHub Desktop.
A bit of code I wrote to get back up to speed on C++
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
}; | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment