pbs.cpp

/* ----------------------------------------------------------------
 *
 * University of Athens
 * Department of Informatics and Telecommunications
 * --------------------------------
 * Class: Object Oriented Programming
 * Professor: Izambo Karali
 * --------------------------------
 * Exercise 1 - Winter semester 2014-2015
 * Description: Simulation of public service building
 * Link: http://cgi.di.uoa.gr/~izambo/OOPassgn1_2015.pdf
 * --------------------------------
 *
 * ----------------------------------------------------------------
 *
 * Developed and tested on: Ubuntu 12.04.5 LTS
 * Compiler used: g++ 4.8.1
 * --------------------------------
 * Compile with: g++ -Wall -o pbs publicservice.cc
 * Run with: ./pbs
 *           ./pbs <N>
 *           ./pbs <N> <Nf>
 *           ...
 *           ./pbs <N> <Nf> <Ng> <No> <Nl> <K> <L>
 * --------------------------------
 * Coding styles followed :
 * -- Linux Kernel
 * Link: http://www.kernel.org/doc/Documentation/CodingStyle
 * -- Google C++
 * Link: http://google-styleguide.googlecode.com/svn/trunk/cppguide.html
 *
 * ----------------------------------------------------------------
 *
 * Valgrind report for 20000 Visitors sim
 * --------------------------------
 * valgrind ./pbs 20000 100 200 5 20 20010 50
 * --------------------------------
 * HEAP SUMMARY:
 * in use at exit: 0 bytes in 0 blocks
 * total heap usage: 1,515 allocs, 1,515 frees, 14,160 bytes allocated
 * All heap blocks were freed -- no leaks are possible
 * ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
 *
 * ----------------------------------------------------------------
 */

/* Libraries */
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <iostream>

/* Constants */
#ifndef PUBLICSERVICE_CONSTANTS
#define NOTSET -1
#define ZERO 0
#define ONE 1
#define TEN 10
#define INIT_CNT 0
#define FLOOR_CNT 4
#define OFFICE_CNT 10
#define NONE NULL
#endif

/* Default Testcase */
#ifndef PUBLICSERVICE_DEFAULT_TESTCASE
#define PBS_DEFAULT_N 10
#define PBS_DEFAULT_K 11
#define PBS_DEFAULT_L 2
#endif

using namespace std;

class Visitor {
	private:
	int priority_no;
	int floor_no;
	int office_no;
	bool serviced;

	public:
	/* Constructor */
	Visitor()
		: priority_no(ZERO)
		, serviced(false) {
		floor_no = rand()%FLOOR_CNT+ONE;
		office_no = rand()%OFFICE_CNT+ONE;
	}
	/* Accessors */
	int get_priority_no() {
		return priority_no;
	}
	int get_floor_no() {
		return floor_no;
	}
	int get_office_no() {
		return office_no;
	}
	bool is_serviced() {
		return serviced;
	}
	/* Mutators */
	void set_priority_no(int priority) {
		priority_no = priority;
	}
	void set_serviced() {
		serviced = not serviced;
	}
};

class VisitorQueueList {
	private:
	int visitor_cnt;
	struct Node	{
		Visitor *visitor;
		Node *next;
        Node(Visitor *visitor, Node *next)
            : visitor(visitor)
            , next(next) {
        }
	};
	Node *head, *tail;
	public:
	/* Constructor */
	VisitorQueueList()
		: visitor_cnt(INIT_CNT)
		, head(NONE)
		, tail(NONE) {
	}
	/* Destructor - Emptys the Queue before destruction */
	~VisitorQueueList() {
		while (not is_empty())
			pop();
	}
	/* Returns # of Queue elements */
	int get_visitor_cnt() {
		return visitor_cnt;
	}
	/* Returns true if Queue contains 0 elements */
	bool is_empty() {
		return visitor_cnt == ZERO;
	}
	/* Appends a Visitor to the Queue */
	void push(Visitor &visitor) {
		/* Create a node to wrap around Visitor */
		Node *pushnode = new(nothrow) Node(&visitor,NONE);
		/* Adjust pointers to maintain Queue structure */
		if (is_empty())
			head = pushnode;
		else
			tail->next = pushnode;
		tail = pushnode;
		++visitor_cnt;
	}
	/* Alias push() to handle pointer type parameter */
	void push(Visitor *visitor) {
		push(*visitor);
	}
	/* Returns the top Visitor of the Queue */
	Visitor& top() {
		return *(head->visitor);
	}
	/* Removes and returns the top Visitor of the Queue */
	Visitor& pop() {
		Visitor &visitor = *(head->visitor);
		/* Adjust the pointers accordingly */
		Node *popnode = head;
		head = head->next;
		/* Free node and return the Visitor */
		delete popnode;
		--visitor_cnt;
		return visitor;
	}
	/* Removes and returns a random Visitor from the Queue */
	Visitor& pop_random() {
		/* Pick a random queue position */
		int random_visitor_queue_position = rand()%visitor_cnt;
		/* Advance the Queue to find that node */
		Node *previous = head, *popnode = head;
		for (int iterator=ZERO ; ;
			/* Step */
			++iterator,
			previous = popnode,
			popnode = popnode->next
		) {
			/* Once the node is found get a reference of the Visitor inside */
			if (iterator==random_visitor_queue_position) {
				Visitor &visitor = *(popnode->visitor);
				/* Adjust the pointers to maintain the Queue structure */
				if (iterator==ZERO)
					head = popnode->next;
				else
					previous->next = popnode->next;
				if (iterator==visitor_cnt-ONE)
					tail = previous;
				/* Free node and return the Visitor */
				delete popnode;
				--visitor_cnt;
				return visitor;
			}
		}
	}
	/* Removes serviced Visitors and returns a new Queue of them */
	VisitorQueueList *pop_serviced() {
		/* Allocate a new Queue to return to the caller */
		VisitorQueueList *queue_serviced = new VisitorQueueList();
		Node *previous = head, *current = head;
		int const_visitor_cnt = visitor_cnt;
		/* Iterate through the Queue */
		for (int iterator=ZERO;iterator<const_visitor_cnt;++iterator) {
			/* When the node contains a serviced Visitor */
			if ((current->visitor)->is_serviced()) {
				/* Push the Visitor into the queue_serviced Queue */
				queue_serviced->push(current->visitor);
				Node *nextnode = current->next;
				/* Adjust the pointers in the original Queue */
				if (iterator==(const_visitor_cnt-visitor_cnt)) {
					head = current->next;
					previous = head;
				} else {
					previous->next = current->next;
				}
				if (iterator==const_visitor_cnt-ONE) {
					tail = previous;
				}
				/* Remove the node from original Queue */
				delete current;
				--visitor_cnt;
				current = nextnode;
			} else {
				previous = current;
				current = current->next;
			}
		}
		return queue_serviced;
	}
};

class EntryHall {
	private:
	int visitor_cnt;

	VisitorQueueList visitors;

	public:
	/* Constructor */
	EntryHall()
		: visitor_cnt(INIT_CNT) {
		cout << "The entrance has been created!" << endl;
	}
	/* Destructor */
	~EntryHall() {
		cout << "End of waiting people!" << endl;
	}
	/* Returns true if EntryHall contains 0 Visitors */
	bool is_empty() {
		return visitor_cnt == ZERO;
	}
	/* Returns the top Visitor of the Queue */
	Visitor& peek() {
		return visitors.top();
	}
	/* Appends a Visitor to the Queue */
	bool enter(Visitor &visitor) {
		visitors.push(visitor);
		++visitor_cnt;
		return true;
	}
	/* Removes and returns the top Visitor of the Queue */
	Visitor& exit() {
		--visitor_cnt;
		return visitors.pop();
	}
};

class GroundFloor {
	private:
	int visitor_cnt;
	int priority_cnt;
	int max_capacity;

	EntryHall *entryhall;

	public:
	/* Constructor */
	GroundFloor(int Ng)
		: visitor_cnt(INIT_CNT)
		, priority_cnt(INIT_CNT)
		, max_capacity(Ng) {
		entryhall = new EntryHall();
		cout << "A floor has been created with number 0" << endl;
	}
	/* Destructor */
	~GroundFloor() {
		delete entryhall;
		cout << "End of service!" << endl;
	}
	/* Returns true if GroundFloor contains 0 Visitors */
	bool is_empty() {
		return visitor_cnt == ZERO;
	}
	/* Returns true if GroundFloor max visitor capacity is reached */
	bool is_full() {
		return visitor_cnt == max_capacity;
	}
	/* Returns the top Visitor of the EntryHall Queue */
	Visitor& peek() {
		return entryhall->peek();
	}
	/* Attempts to append a Visitor to the EntryHall Queue */
	bool enter(Visitor &visitor) {
		if (not is_full()) {
			++visitor_cnt;
			entryhall->enter(visitor);
			wait(visitor);
			return true;
		} else {
			return false;
		}
	}
	/* Removes and returns the top Visitor of the EntryHall Queue */
	Visitor& exit() {
		--visitor_cnt;
		return entryhall->exit();
	}
	/* Assign a priority # to the Visitor */
	void wait(Visitor &visitor) {
		visitor.set_priority_no(++priority_cnt);
		cout << "Waiting for the lift" << endl;
	}
};

class Office {
	private:
	int visitor_cnt;
	int max_capacity;
	int office_no;

	VisitorQueueList visitors;

	public:
	/* Constructor */
	Office(int No, int office_no)
		: visitor_cnt(INIT_CNT)
		, max_capacity(No)
		, office_no(office_no) {
		cout << "Office number " << office_no << " has been created" << endl;
	}
	/* Destructor */
	~Office() {
		cout << "End of the work!" << endl;
	}
	/* Returns true if Office contains 0 Visitors */
	bool is_empty() {
		return visitor_cnt == ZERO;
	}
	/* Returns true if Office max visitor capacity is reached */
	bool is_full() {
		return visitor_cnt == max_capacity;
	}
	/* Attempts to append a Visitor to the Office Queue */
	bool enter(Visitor &visitor) {
		if (not is_full()) {
			visitors.push(visitor);
			++visitor_cnt;
			cout << "Entering office number " << visitor.get_office_no() << " (Priority=" << visitor.get_priority_no() << ")" << endl;
			return true;
		} else {
			cout << "Please, wait outside for entrance in office number " << visitor.get_office_no() << " (Priority=" << visitor.get_priority_no() << ")" << endl;
			return false;
		}
	}
	/* Removes and returns the top Visitor of the Office Queue */
	Visitor& exit() {
		Visitor &visitor = visitors.pop_random();
		/* Visitor is considered serviced after this point */
		visitor.set_serviced();
		--visitor_cnt;
		return visitor;
	}
};

class Floor {
	private:
	int visitor_cnt;
	int max_capacity;
	int floor_no;

	EntryHall *entryhall;
	Office *offices[OFFICE_CNT];

	public:
	/* Constructor */
	Floor(int Nf, int No, int floor_no)
		: visitor_cnt(INIT_CNT)
		, max_capacity(Nf)
		, floor_no(floor_no) {
		entryhall = new EntryHall();
		for (int iterator=ZERO;iterator<OFFICE_CNT;++iterator)
			offices[iterator] = new Office(No,iterator+ONE);
		cout << "A floor has been created with number " << floor_no << endl;
	}
	/* Destructor */
	~Floor() {
		for (int iterator=ZERO;iterator<OFFICE_CNT;++iterator)
			delete offices[iterator];
		delete entryhall;
		cout << "End of service!" << endl;
	}
	/* Returns true if Floor contains 0 Visitors */
	bool is_empty() {
		return visitor_cnt == ZERO;
	}
	/* Returns true if Floor max visitor capacity is reached */
	bool is_full() {
		return visitor_cnt == max_capacity;
	}
	/* Attempts to append a Visitor to the Office Queue he wants */
	bool enter(Visitor &visitor) {
		if (not is_full()) {
			cout << "Entering floor number " << visitor.get_floor_no() << " (Priority=" << visitor.get_priority_no() << ")" << endl;
			/* Floor attempts to place the Visitor inside the Office */
			if (not (offices[visitor.get_office_no()-ONE]->enter(visitor)))
				/* In case of failure he goes directly to Floor.EntryHall */
				entryhall->enter(visitor);
			++visitor_cnt;
			return true;
		} else {
			cout << "Sorry, floor number " << visitor.get_floor_no() << " is full (Priority=" << visitor.get_priority_no() << ")" << endl;
			return false;
		}
	}
	/* Removes and returns a random Visitor from a random Office Queue */
	Visitor &exit() {
		/* Pick a random Office # */
		int office_no = rand()%OFFICE_CNT;
		/* While its empty check next one */
		while (offices[office_no]->is_empty())
			office_no = (office_no + ONE) % OFFICE_CNT;
		/* Remove the Visitor and return it */
		--visitor_cnt;
		return offices[office_no]->exit();
	}
};

class Lift {
	private:
	int visitor_cnt;
	int max_capacity;

	/* Lift contains a Queue for each floor */
	VisitorQueueList visitors[FLOOR_CNT];

	public:
	/* Constructor */
	Lift(int Nl)
		: visitor_cnt(INIT_CNT)
		, max_capacity(Nl) {
		cout << "A lift has been created" << endl;
	}
	/* Destructor */
	~Lift() {
		cout << "No more ups and downs" << endl;
	}
	/* Returns true if Lift max visitor capacity is reached */
	bool is_full() {
		return visitor_cnt == max_capacity;
	}
	/* Returns the top Visitor of the appropriate Lift Queue */
	Visitor &peek(int floor_no) {
		return visitors[floor_no].top();
	}
	/* Attempts to append a Visitor to the appropriate Lift Queue */
	bool enter(Visitor &visitor) {
		if (not is_full()) {
			visitors[visitor.get_floor_no()-ONE].push(visitor);
			++visitor_cnt;
			cout << "Visitor in the lift" << endl;
			return true;
		} else {
			cout << "You are not allowed to enter! (Priority=" << visitor.get_priority_no() << ")" << endl;
			return false;
		}
	}
	/* Removes and returns the top Visitor of the appropriate Lift Queue */
	Visitor &exit(int floor_no) {
		--visitor_cnt;
		return visitors[floor_no].pop();
	}
	/* Move Visitors from the Lift to the Floor until Lift Queue emptys or Floor Queue fills */
	void stop_up(int floor_no, Floor *floor) {
		while (not(visitors[floor_no].is_empty()))
			if (floor->enter(peek(floor_no)))
				exit(floor_no);
			else
				break;
	}
	/* Move Visitors to the Lift from the Floor until Floor Queue emptys or Lift Queue fills */
	void stop_down(int floor_no, Floor *floor) {
		while (not(floor->is_empty()) and not(is_full()))
			enter(floor->exit());
	}
	/* Empty the Lift and return a Queue of the removed Visitors */
	VisitorQueueList *empty_all() {
		VisitorQueueList *queue_merged = new VisitorQueueList();
		for (int floor_no=ZERO;floor_no<FLOOR_CNT;++floor_no) {
			VisitorQueueList *queue_serviced = visitors[floor_no].pop_serviced();
			while(not(queue_serviced->is_empty()))
				queue_merged->push(queue_serviced->pop());
			delete queue_serviced;
		}
		visitor_cnt = ZERO;
		return queue_merged;
	}
	/* Performs the Lift operations and returns a List of serviced Visitors to the caller */
	VisitorQueueList *operate(GroundFloor &groundfloor, Floor **floors) {
		/* Enter Visitors from GroundFloor */
		while (not(groundfloor.is_empty()))
			if (enter(groundfloor.peek()))
				groundfloor.exit();
			else
				break;
		/* Call stop_up for each floor */
		for (int floor_no=ZERO;floor_no<FLOOR_CNT;++floor_no)
			stop_up(floor_no, floors[floor_no]);
		/* Call stop_down for each floor */
		for (int floor_no=FLOOR_CNT-ONE;floor_no>=ZERO;--floor_no)
			stop_down(floor_no, floors[floor_no]);
		/* Return the empty_all Visitor Queue back to the building */
		return empty_all();
	}
};

class Building {
	private:
	int visitor_cnt;
	int max_capacity;

	GroundFloor *groundfloor;
	Floor *floors[FLOOR_CNT];
	Lift *lift;

	public:
	/* Constructor */
	Building(int N, int Nf, int Ng, int No, int Nl)
		: visitor_cnt(INIT_CNT)
		, max_capacity(N) {
		groundfloor = new GroundFloor(Ng);
		for (int iterator=ZERO;iterator<FLOOR_CNT;++iterator)
			floors[iterator] = new Floor(Nf, No, iterator+ONE);
		lift = new Lift(Nl);
		cout << "A new building is ready for serving citizens!" << endl;
	}
	/* Destructor */
	~Building() {
		delete lift;
		for (int iterator=ZERO;iterator<FLOOR_CNT;++iterator)
			delete floors[iterator];
		delete groundfloor;
		cout << "Service not available any longer. Go elsewhere!" << endl;
	}
	/* Returns true if Building max visitor capacity is reached */
	bool is_full() {
		return visitor_cnt == max_capacity;
	}
	/* Appends a Visitor to the Queue of GroundFloor.EntryHall */
	bool enter(Visitor &visitor) {
		if (not is_full()) {
			++visitor_cnt;
			groundfloor->enter(visitor);
			return true;
		} else {
			cout << "Please, come tomorrow" << endl;
			return false;
		}
	}
	/* Removes the Visitors from the Queue returned by Lift.operate */
	void exit(VisitorQueueList *visitors) {
		while (not(visitors->is_empty())) {
			--visitor_cnt;
			cout << "I cannot believe I finished! (Priority=" << (visitors->pop()).get_priority_no() << ")" << endl;
		}
		delete visitors;
	}
	/* Calls Lift.operate() L # of times and calls exit each time with the returned Queue */
	void operate_lift(int L) {
		while (L--) {
			exit(lift->operate(*groundfloor, floors));
		}
	}
};

/* Prints error in case of invalid argument by user */
inline void print_arg_error(int argument_no, string variable, string restriction, int value) {
	cerr
	<< " === Warning === ------------------" << endl
	<< "|   Description : Invalid Argument (" << argument_no << ")" << endl
	<< "|      Variable : " << variable << endl
	<< "|         Value : " << value << endl
	<< "|   Restriction : requires " << restriction << endl
	<< " =============== ------------------" << endl;
}

inline void init(int argc, char *argv[],
	int &N, int &Nf, int &Ng, int &No, int &Nl, int &K, int &L) {
	/* Seed the random number generator */
	srand(time(NULL));
	/* Set some default values in case user does not input some */
	N=PBS_DEFAULT_N;
	Nf=N/3-1;
	Ng=N/2-1;
	No=Nf-1;
	Nl=No+1;
	K=PBS_DEFAULT_K;
	L=PBS_DEFAULT_L;
	/* Input the correct arguments if given */
	if (argc>1 and (not(istringstream(argv[1]) >> N) or N<1)) {
		print_arg_error(1, "N (building max capacity)", "N > 0", N);
		N=PBS_DEFAULT_N;
	}
	if (argc>2 and (not(istringstream(argv[2]) >> Nf) or Nf<1 or !(Nf<N/3))) {
		print_arg_error(2, "Nf (floor max capacity)", "0 < Nf < N/3", Nf);
		Nf=N/3-1;
	}
	if (argc>3 and (not(istringstream(argv[3]) >> Ng) or Ng<1 or !(Ng<N/2))) {
		print_arg_error(3, "Ng (ground floor max capacity)", "0 < Ng < N/2", Ng);
		Ng=N/2-1;
	}
	if (argc>4 and (not(istringstream(argv[4]) >> No) or No<1 or !(No<Nf))) {
		print_arg_error(4, "No (office max capacity)", "0 < No < Nf", No);
		No=Nf-1;
	}
	if (argc>5 and (not(istringstream(argv[5]) >> Nl) or Nl<1 or !(Nl>No))) {
		print_arg_error(5, "Nl (lift max capacity)", "Nl > No", Nl);
		Nl=No+1;
	}
	if (argc>6 and (not(istringstream(argv[6]) >> K) or K<1)) {
		print_arg_error(6, "K (number of visitors)", "K > 0", K);
		K=PBS_DEFAULT_K;
	}
	if (argc>7 and (not(istringstream(argv[7]) >> L) or L<1)) {
		print_arg_error(7, "L (number of lift cycles)", "L > 0", L);
		L=PBS_DEFAULT_L;
	}
	/* Print sim vars */
	cout
	<< " === Public Service simulation variables ===" << endl
	<< "|    N = " << N << endl
	<< "|   Nf = " << Nf << endl
	<< "|   Ng = " << Ng << endl
	<< "|   No = " << No << endl
	<< "|   Nl = " << Nl << endl
	<< "|    K = " << K << endl
	<< "|    L = " << L << endl
	<< " ===========================================" << endl;
}

int main(int argc, char *argv[]) {
	/* Variable Declaration */
	int N, Nf, Ng, No, Nl, K, L;

	/* Init */
	init(argc, argv, N, Nf, Ng, No, Nl, K, L);

	/* Part 1 - Create a building */
	Building building(N, Nf, Ng, No, Nl);

	/* Part 2 - Create K visitors */
	Visitor visitors[K];
	
	/* Part 3 - Attempt to enter the visitors into the building */
	while (K)
		building.enter(visitors[--K]);

	/* Part 4 - Run L number of lift cycles */
	building.operate_lift(L);

	return 0;
}