C++ Data Structures and Algorithms Here are the general project instructions: ht
ID: 665921 • Letter: C
Question
C++ Data Structures and Algorithms
Here are the general project instructions: https://ece.uwaterloo.ca/~dwharder/aads/Projects/2/
Here is the first class isntructions (Dynamic_queue) : https://ece.uwaterloo.ca/~dwharder/aads/Projects/2/Dynamic_queue/
Here are the first class Source Files: https://ece.uwaterloo.ca/~dwharder/aads/Projects/2/Dynamic_queue/src/
Here is the second class instructions (Linked_Stack ): https://ece.uwaterloo.ca/~dwharder/aads/Projects/2/Linked_stack/
Here are the second class source files: https://ece.uwaterloo.ca/~dwharder/aads/Projects/2/Linked_stack/src/
Please answer the question in full!! I appreciate your help!!
try and make everything super clear!
thanks!!
please write the actual program in c++ and label the beginning of each class
Explanation / Answer
5.Linked _Stack
Linked_stack.h
#ifndef LINKED_STACK_H
#define LINKED_STACK_H
#ifndef nullptr
#define nullptr 0
#endif
#include "ece250.h"
#include "Double_sentinel_list.h"
#include "Exception.h"
#include <iostream>
template <typename Type>
class Linked_stack {
private:
static int const ARRAY_CAPACITY = 8;
Double_sentinel_list<Type *> list;
int itop;
int stack_size;
public:
Linked_stack();
Linked_stack( Linked_stack const & );
~Linked_stack();
bool empty() const;
int size() const;
int list_size() const;
Type top() const;
void swap( Linked_stack & );
Linked_stack &operator=( Linked_stack );
void push( Type const &obj );
Type pop();
// Friends
template <typename T>
friend std::ostream &operator<<( std::ostream &, Linked_stack<T> const & );
};
template <typename Type>
Linked_stack<Type>::Linked_stack():
stack_size( 0 ) {
// Empty constructor
}
template <typename Type>
Linked_stack<Type>::Linked_stack( Linked_stack const &stack ):
itop( stack.itop ),
stack_size( stack.stack_size ) {
// enter your implementation here
if (stack.empty()){
return;
}
//iterate through the list copying values in the array to the copy list
//copy only what was saved (upto itop index) in the first node and everything else
//in the other nodes
else {
for ( Double_node<Type *> *ptr = stack.list.head()->next(); ptr != stack.list.tail(); ptr = ptr->next() ) {
if ( ptr == stack.list.head()->next() ) {
Type *cpyArray = new Type[ARRAY_CAPACITY];
for ( int i = 0; i <= stack.itop; ++i ) {
cpyArray[i] = stack.list.front()[i];
}
list.push_back(cpyArray);
} else {
Type *cpyArray = new Type[ARRAY_CAPACITY];
for ( int i = 0; i <= ARRAY_CAPACITY - 1; ++i ) {
cpyArray[i] = ptr->retrieve()[i];
}
}
}
}
}
//pop all the nodes off the list
template <typename Type>
Linked_stack<Type>::~Linked_stack() {
while(!empty()){
pop();
}
}
template <typename Type>
bool Linked_stack<Type>::empty() const {
//empty return boolean:true if stack size is 0
return ( stack_size == 0 );
}
template <typename Type>
int Linked_stack<Type>::size() const {
// return the size of the stack
return stack_size;
}
// Do not change this implementation
template <typename Type>
int Linked_stack<Type>::list_size() const {
return list.size();
}
template <typename Type>
Type Linked_stack<Type>::top() const {
//throw exception if list is empty
if (empty()){
throw underflow();
}
//access array from the front node using itop index
return list.front()[itop];
}
template <typename Type>
void Linked_stack<Type>::swap( Linked_stack<Type> &stack ) {
std::swap( list, stack.list );
std::swap( stack_size, stack.stack_size );
std::swap( itop, stack.itop );
}
template <typename Type>
Linked_stack<Type> &Linked_stack<Type>::operator=( Linked_stack<Type> rhs ) {
swap( rhs );
return *this;
}
template <typename Type>
void Linked_stack<Type>::push( Type const &obj ) {
// if list is empty or the array of the front node is full,
//push in a new array and set itop to 0.
//set obj to index: itop of the array
if(itop == ARRAY_CAPACITY - 1 || empty() ){
list.push_front(new Type[ARRAY_CAPACITY]);
itop = 0;
list.front()[itop] = obj;
++stack_size;
}
//if array isn't full, add obj
else{
itop++;
list.front()[itop] = obj;
++stack_size;
}
}
template <typename Type>
Type Linked_stack<Type>::pop() {
//if list is empty, throw exception
if(empty() ){
throw underflow();
}
//return value at itop
//if itop is 0, delete node, shift itop to next node
//decrease stack size by 1
else if (itop == 0){
Type> delete [] list.front();
list.pop_front();
itop = ARRAY_CAPACITY - 1;
--stack_size;
return onlyEntry;
}
//return value at itop, decrease itop and stack size by 1
else{
Type> itop -= 1;
stack_size -= 1;
return onlyEntry;
}
}
// You will be required to modify this function in order to accomodate
// your implementation of a singly linked list in Project 1.
template <typename T>
std::ostream &operator<<( std::ostream &out, Linked_stack<T> const &stack ) {
if ( stack.list.size() == 0 ) {
out << "->0";
} else if ( stack.list.size() == 1 ) {
out << "->[ ";
for ( int i = 0; i <= stack.itop; ++i ) {
out << stack.list.front()[i] << " ";
}
out << "]->0";
} else {
out << "->";
for ( Double_node<T *> *ptr = stack.list.head()->next(); ptr != stack.list.tail(); ptr = ptr->next() ) {
out << "[ ";
if ( ptr == stack.list.head()->next() ) {
for ( int i = 0; i <= stack.itop; ++i ) {
out << ptr->retrieve()[i] << " ";
}
} else {
for ( int i = 0; i <= Linked_stack<T>::ARRAY_CAPACITY - 1; ++i ) {
out << ptr->retrieve()[i] << " ";
}
}
out << "]->";
}
out << "0";
}
return out;
}
#endif
Linked_stack_driver.cpp
#include <iostream>
#include <cstring>
#include "Linked_stack_tester.h"
int main( int argc, char *argv[] ) {
if ( argc > 2 ) {
std::cerr << "Expecting at most one command-line argument" << std::endl;
return -1;
}
std::cout << "Starting Test Run" << std::endl;
if ( argc == 1 || !std::strcmp( argv[1], "int" ) ) {
if ( argc == 1 ) {
std::cerr << "Expecting a command-line argument of either 'int' or 'double', but got none; using 'int' by default." << std::endl;
}
Linked_stack_tester<int> tester;
tester.run();
} else if ( !std::strcmp( argv[1], "double" ) ) {
Linked_stack_tester<double> tester;
tester.run();
}
std::cout << "Finishing Test Run" << std::endl;
return 0;
}
Linked_stack_tester.h
#ifndef LINKD_STACK_TESTER_H
#define LINKD_STACK_TESTER_H
#ifndef nullptr
#define nullptr 0
#endif
#include "Exception.h"
#include "Tester.h"
#include "Linked_stack.h"
#include <iostream>
template <typename Type>
class Linked_stack_tester:public Tester< Linked_stack<Type> > {
using Tester< Linked_stack<Type> >::object;
using Tester< Linked_stack<Type> >::command;
public:
Linked_stack_tester( Linked_stack<Type> *obj = nullptr ):Tester< Linked_stack<Type> >( obj ) {
// empty
}
void process();
};
template <typename Type>
void Linked_stack_tester<Type>::process() {
if ( command == "new" ) {
object = new Linked_stack<Type>();
std::cout << "Okay" << std::endl;
} else if ( command == "size" ) {
// check if the size equals the next integer read
int expected_size;
std::cin >> expected_size;
int actual_size = object->size();
if ( actual_size == expected_size ) {
std::cout << "Okay" << std::endl;
} else {
std::cout << "Failure in size(): expecting the value '" << expected_size << "' but got '" << actual_size << "'" << std::endl;
}
} else if ( command == "list_size" ) {
// check if the list size equals the next integer read
int expected_list_size;
std::cin >> expected_list_size;
int actual_list_size = object->list_size();
if ( actual_list_size == expected_list_size ) {
std::cout << "Okay" << std::endl;
} else {
std::cout << "Failure in list_size(): expecting the value '" << expected_list_size << "' but got '" << actual_list_size << "'" << std::endl;
}
} else if ( command == "empty" ) {
// check if the empty status equals the next Boolean read
bool expected_empty;
std::cin >> expected_empty;
bool actual_empty = object->empty();
if ( actual_empty == expected_empty ) {
std::cout << "Okay" << std::endl;
} else {
std::cout << "Failure in empty(): expecting the value '" << expected_empty << "' but got '" << actual_empty << "'" << std::endl;
}
} else if ( command == "top" ) {
// checks if the first object in the linked list equals the next object read
Type expected_top;
std::cin >> expected_top;
Type actual_top = object->top();
if ( actual_top == expected_top ) {
std::cout << "Okay" << std::endl;
} else {
std::cout << "Failure in top(): expecting the value '" << expected_top << "' but got '" << actual_top << "'" << std::endl;
}
} else if ( command == "top!" ) {
// top of an empty list - catch an exception
Type actual_top;
try {
actual_top = object->top();
std::cout << "Failure in top(): expecting to catch an exception but got '" << actual_top << "'" << std::endl;
} catch( underflow ) {
std::cout << "Okay" << std::endl;
} catch (...) {
std::cout << "Failure in top(): expecting an underflow exception but caught a different exception" << std::endl;
}
} else if ( command == "push" ) {
// push the next object read to the top of the linked list
Type n;
std::cin >> n;
object->push( n );
std::cout << "Okay" << std::endl;
} else if ( command == "pop" ) {
// pop the first object from the linked list
Type expected_popped_element;
std::cin >> expected_popped_element;
Type actual_popped_element = object->pop();
if ( actual_popped_element == expected_popped_element ) {
std::cout << "Okay" << std::endl;
} else {
std::cout << "Failure in pop(): expecting the value '" << expected_popped_element << "' but got '" << actual_popped_element << "'" << std::endl;
}
} else if ( command == "pop!" ) {
// pop from an empty list - catch an exception
Type actual_popped_element;
try {
actual_popped_element = object->pop();
std::cout << "Failure in pop(): expecting to catch an exception but got '" << actual_popped_element << "'" << std::endl;
} catch( underflow ) {
std::cout << "Okay" << std::endl;
} catch (...) {
std::cout << "Failure in pop(): expecting an underflow exception but caught a different exception" << std::endl;
}
} else if ( command == "assign" ) {
Linked_stack<Type> *new_object = new Linked_stack<Type>();
*new_object = *object;
std::cout << "Okay" << std::endl;
Linked_stack_tester<Type> tester( new_object );
tester.run();
} else if ( command == "cout" ) {
std::cout << *object << std::endl;
} else {
std::cout << command << "Command not found." << std::endl;
}
}
#endif
double.in.txt
double.out.txt
int.in.txt
int.out.txt
Dynamic Queue
Dynamic_queue.h
#ifndef DYNAMIC_QUEUE_H
#define DYNAMIC_QUEUE_H
#ifndef nullptr
#define nullptr 0
#endif
#include <algorithm>
#include "ece250.h"
#include "Exception.h"
template <typename Type>
class Dynamic_queue {
private:
int initial_capacity;
int array_capacity;
Type *array;
int ihead;
int itail;
int entry_count;
// other integer member variables, as necessary
public:
Dynamic_queue( int = 10 );
Dynamic_queue( Dynamic_queue const & );
~Dynamic_queue();
Type head() const;
int size() const;
bool empty() const;
int capacity() const;
void swap( Dynamic_queue & );
Dynamic_queue &operator=( Dynamic_queue );
void enqueue( Type const & );
Type dequeue();
void clear();
// Friends
template <typename T>
friend std::ostream &operator<<( std::ostream &, Dynamic_queue<T> const & );
};
template <typename Type>
Dynamic_queue<Type>::Dynamic_queue( int n ):
initial_capacity( std::max( n, 1 ) ),
array_capacity( initial_capacity ),
array( new Type[initial_capacity] ),
ihead( 0 ),
itail( initial_capacity - 1 ),
entry_count( 0 ) {
//set the itail initially to -1
itail = -1;
}
template <typename Type>
Dynamic_queue<Type>::Dynamic_queue( Dynamic_queue const &queue ):
initial_capacity( queue.initial_capacity ),
array_capacity( queue.array_capacity ),
array( new Type[array_capacity] ),
ihead( queue.ihead ),
itail( queue.itail ),
entry_count( queue.entry_count ) {
// The above initializations copy the values of the appropriate
// member variables and allocate memory for the data structure;
// however, you must still copy the stored objects.
//loop through the array copying objects into the new array
for (int i = 0 ; i < entry_count ; i++){
array[i] = queue.array[i];
}
}
template <typename Type>
Dynamic_queue<Type>::~Dynamic_queue() {
//delete the array
delete [] array;
}
template <typename Type>
int Dynamic_queue<Type>::size() const {
//return the entry count that shows the size
return entry_count;
}
template <typename Type>
int Dynamic_queue<Type>::capacity() const {
return array_capacity;
}
template <typename Type>
bool Dynamic_queue<Type>::empty() const {
// return boolean:True if size is 0
return(size() == 0);
}
template <typename Type>
Type Dynamic_queue<Type>::head() const {
//throw exception if queue is empty else return head
if(empty()){
throw underflow();
}
else {
return array[ihead];
}
}
template <typename Type>
void Dynamic_queue<Type>::swap( Dynamic_queue<Type> &queue ) {
std::swap( initial_capacity, queue.initial_capacity );
std::swap( array_capacity, queue.array_capacity );
std::swap( array, queue.array );
std::swap( ihead, queue.ihead );
std::swap( itail, queue.itail );
std::swap( entry_count, queue.entry_count );
}
template <typename Type>
Dynamic_queue<Type> &Dynamic_queue<Type>::operator=( Dynamic_queue<Type> rhs ) {
swap( rhs );
return *this;
}
template <typename Type>
void Dynamic_queue<Type>::enqueue( Type const &obj ) {
// Insert the argument at the tail of the queue. If the array is full before the argument is placed into the queue,
// the capacity of the array is first doubled.
if (size() == array_capacity){
Type *arrayTemp = new Type[array_capacity*2];
for (int i = 0; i < array_capacity; i++){
arrayTemp[i] = array[i];
}
delete [] array;
array = arrayTemp;
array_capacity *= 2;
}
if (itail == array_capacity - 1 && size() != array_capacity )
{
itail = 0;
}
itail++;
array[itail] = obj;
entry_count++;
}
template <typename Type>
Type Dynamic_queue<Type>::dequeue() {
//Removes the object at the head of the queue. If, after the object is removed,
// the array is one-quarter (1/4) full and the array capacity is greater than the initial capacity,
//the capacity of the array is halved. This will throw the underflow exception if the queue is empty
if (empty()){
throw underflow();
}
Type frontEntry = array[ihead];
ihead++;
entry_count -= 1;
if(entry_count*4 <= array_capacity && array_capacity > initial_capacity){
Type *arrayHalf = new Type[array_capacity/2];
for (int i = 0; i < array_capacity; i++){
arrayHalf[i] = array[i];
}
delete [] array;
array = arrayHalf;
array_capacity /= 2;
}
return frontEntry;
}
template <typename Type>
void Dynamic_queue<Type>::clear() {
}
// You can modify this function however you want: it will not be tested
template <typename Type>
std::ostream &operator<<( std::ostream &out, Dynamic_queue<Type> const &queue ) {
for (int i = queue.ihead; i < queue.size(); i++)
{
out << queue.array[i] << " " ;
}
return out;
}
// Is an error showing up in ece250.h or elsewhere?
// Did you forget a closing '}' ?
#endif
Dynamic_queue_driver.cpp
#include <iostream>
#include <cstring>
#include "Dynamic_queue_tester.h"
int main( int argc, char *argv[] ) {
if ( argc > 2 ) {
std::cerr << "Expecting at most one command-line argument" << std::endl;
return -1;
}
std::cout << "Starting Test Run" << std::endl;
if ( argc == 1 || !std::strcmp( argv[1], "int" ) ) {
if ( argc == 1 ) {
std::cerr << "Expecting a command-line argument of either 'int' or 'double', but got none; using 'int' by default." << std::endl;
}
Dynamic_queue_tester<int> tester;
tester.run();
} else if ( !std::strcmp( argv[1], "double" ) ) {
Dynamic_queue_tester<double> tester;
tester.run();
}
std::cout << "Finishing Test Run" << std::endl;
return 0;
}
Dynamic_queue_tester.h
/*************************************************
* Dynamic_queue_tester
* A class for testing dynamic queues-as-arrays.
*
* Author: Douglas Wilhelm Harder
* Copyright (c) 2006-8 by Douglas Wilhelm Harder. All rights reserved.
*
* DO NOT EDIT THIS FILE
*************************************************/
#ifndef DYNAMIC_QUEUE_TESTER_H
#define DYNAMIC_QUEUE_TESTER_H
#ifndef nullptr
#define nullptr 0
#endif
#include "Exception.h"
#include "Tester.h"
#include "Dynamic_queue.h"
#include <iostream>
template <typename Type>
class Dynamic_queue_tester:public Tester< Dynamic_queue<Type> > {
using Tester< Dynamic_queue<Type> >::object;
using Tester< Dynamic_queue<Type> >::command;
public:
Dynamic_queue_tester( Dynamic_queue<Type> *obj = 0 ):Tester< Dynamic_queue<Type> >( obj ) {
// empty
}
void process();
};
template <typename Type>
void Dynamic_queue_tester<Type>::process() {
if ( command == "new" ) {
object = new Dynamic_queue<Type>();
std::cout << "Okay" << std::endl;
} else if ( command == "new:" ) {
int n;
std::cin >> n;
object = new Dynamic_queue<Type>( n );
std::cout << "Okay" << std::endl;
} else if ( command == "size" ) {
// check if the size equals the next integer read
int expected_size;
std::cin >> expected_size;
int actual_size = object->size();
if ( actual_size == expected_size ) {
std::cout << "Okay" << std::endl;
} else {
std::cout << "Failure in size(): expecting the value '" << expected_size << "' but got '" << actual_size << "'" << std::endl;
}
} else if ( command == "capacity" ) {
// check if the capacity equals the next integer read
int expected_capacity;
std::cin >> expected_capacity;
int actual_capacity = object->capacity();
if ( actual_capacity == expected_capacity ) {
std::cout << "Okay" << std::endl;
} else {
std::cout << "Failure in capacity(): expecting the value '" << expected_capacity << "' but got '" << actual_capacity << "'" << std::endl;
}
} else if ( command == "empty" ) {
// check if the empty status equals the next Boolean read
bool expected_empty;
std::cin >> expected_empty;
bool actual_empty = object->empty();
if ( actual_empty == expected_empty ) {
std::cout << "Okay" << std::endl;
} else {
std::cout << "Failure in empty(): expecting the value '" << expected_empty << "' but got '" << actual_empty << "'" << std::endl;
}
} else if ( command == "head" ) {
// checks if the first integer in the queue equals the next integer read
Type expected_head;
std::cin >> expected_head;
Type actual_head = object->head();
if ( actual_head == expected_head ) {
std::cout << "Okay" << std::endl;
} else {
std::cout << "Failure in head(): expecting the value '" << expected_head << "' but got '" << actual_head << "'" << std::endl;
}
} else if ( command == "head!" ) {
// head of an empty queue - catch an exception
Type actual_head;
try {
actual_head = object->head();
std::cout << "Failure in head(): expecting to catch an exception but got '" << actual_head << "'" << std::endl;
} catch( underflow ) {
std::cout << "Okay" << std::endl;
} catch (...) {
std::cout << "Failure in head(): expecting an underflow exception but caught a different exception" << std::endl;
}
} else if ( command == "enqueue" ) {
// enqueue the next integer read to the front of the queue
Type obj;
std::cin >> obj;
object->enqueue( obj );
std::cout << "Okay" << std::endl;
} else if ( command == "dequeue" ) {
// dequeue the first integer from the queue
Type expected_dequeued_element;
std::cin >> expected_dequeued_element;
Type actual_dequeued_element = object->dequeue();
if ( actual_dequeued_element == expected_dequeued_element ) {
std::cout << "Okay" << std::endl;
} else {
std::cout << "Failure in dequeue(): expecting the value '" << expected_dequeued_element << "' but got '" << actual_dequeued_element << "'" << std::endl;
}
} else if ( command == "dequeue!" ) {
// dequeue from an empty queue - catch an exception
Type actual_dequeued_element;
try {
actual_dequeued_element = object->dequeue();
std::cout << "Failure in dequeue(): expecting to catch an exception but got '" << actual_dequeued_element << "'" << std::endl;
} catch( underflow ) {
std::cout << "Okay" << std::endl;
} catch (...) {
std::cout << "Failure in dequeue(): expecting an underflow exception but caught a different exception" << std::endl;
}
} else if ( command == "clear" ) {
object->clear();
std::cout << "Okay" << std::endl;
} else if ( command == "assign" ) {
Dynamic_queue<Type> *new_object = new Dynamic_queue<Type>();
*new_object = *(object);
std::cout << "Okay" << std::endl;
Dynamic_queue_tester<Type> tester( new_object );
tester.run();
} else if ( command == "cout" ) {
std::cout << *object << std::endl;
} else {
std::cout << command << ": Command not found." << std::endl;
}
}
#endif
Exception.h
#ifndef EXCEPTION_H
#define EXCEPTION_H
class exception {
// empty class
};
class underflow : public exception {
// empty class
};
class overflow : public exception {
// empty class
};
class division_by_zero : public exception {
// emtpy class
};
class illegal_argument : public exception {
// emtpy class
};
class out_of_range : public exception {
// emtpy class
};
#endif
Tester.h
#ifndef TESTER_H
#define TESTER_H
#ifndef nullptr
#define nullptr 0
#endif
#include <iostream>
#include <string>
#include <sstream>
#include "ece250.h"
template <class Class_name>
class Tester {
protected:
Class_name *object;
std::string command;
public:
Tester( Class_name *obj = nullptr ):
object( obj ) {
// emtpy constructor
}
int run();
virtual void process() = 0;
};
template <class Class_name>
int Tester<Class_name>::run() {
// read the flag which indicates the command to be test and
// stop if we have reached the end of the file
ece250::allocation_table.stop_recording();
const static std::string prompt = " % ";
while ( true ) {
// terminate if there is an end-of-file or the user types 'exit'
if ( std::cin.eof() ) {
break;
}
++ece250::count;
std::cout << ece250::count << prompt;
std::cin >> command;
// Remove any comments
if ( command.substr( 0, 2 ) == "//" ) {
char comment[1024];
std::cin.getline( comment, 1024 );
std::cout << command << comment << std::endl;
continue;
}
// terminate if there is an end-of-file or the user types 'exit'
if ( std::cin.eof() ) {
std::cout << "Exiting..." << std::endl;
break;
}
// If the user enters !!,
// set the command to be the last command
// If the user enters !n where n is a number, (1 <= n < count)
// set the command ot be the nth command
if ( command == "!!" ) {
if ( ece250::count == 1 ) {
std::cout << "Event not found" << std::endl;
continue;
}
command = ece250::history[ece250::count - 1];
} else if ( command[0] == '!' ) {
int n;
std::istringstream number( command.substr( 1, command.length() - 1 ) );
number >> n;
if ( n <= 0 || n >= ece250::count || n >= 1000 ) {
std::cout << "Event not found" << std::endl;
continue;
}
command = ece250::history[n];
}
// only track the first 1001 commands
if ( ece250::count < 1000 ) {
ece250::history[ece250::count] = command;
}
// start tracking any memory allocations made
ece250::allocation_table.start_recording();
// There are five key commands
if ( command == "exit" ) {
std::cout << "Okay" << std::endl;
ece250::allocation_table.stop_recording();
break;
} else if ( command == "delete" ) {
delete object;
object = nullptr;
std::cout << "Okay" << std::endl;
} else if ( command == "summary" ) {
ece250::allocation_table.summary();
} else if ( command == "details" ) {
ece250::allocation_table.details();
} else if ( command == "memory" ) {
int n;
std::cin >> n;
if ( n == ece250::allocation_table.memory_alloc() ) {
std::cout << "Okay" << std::endl;
} else {
std::cout << "Failure in memory allocation: expecting "
<< n << " bytes to be allocated, but "
<< ece250::allocation_table.memory_alloc()
<< " bytes were allocated" << std::endl;
}
} else if ( command == "memory_store" ) {
ece250::allocation_table.memory_store();
std::cout << "Okay" << std::endl;
} else if ( command == "memory_change" ) {
int n;
std::cin >> n;
ece250::allocation_table.memory_change( n );
} else {
process();
}
// stop tracking any memory allocations made
ece250::allocation_table.stop_recording();
}
return 0;
}
#endif
ece250.h
#ifndef ECE250
#define ECE250
#include <cstdlib>
#include <iostream>
/* #include <sstream> */
#include <iomanip>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#include "Exception.h"
#ifndef nullptr
#define nullptr 0
#endif
namespace ece250 {
int memory_alloc_store;
const size_t PAD = 16;
class overflow {};
class invalid_deletion {};
class invalid_input {};
// Each time a student calls either new or new[], the
// information about the memory allocation is stored in
// an instance of this class
class Stopwatch {
private:
clock_t start_time;
float duration;
public:
Stopwatch() {
duration = 0;
}
void start() {
start_time = std::clock();
}
void stop() {
clock_t end_time = std::clock();
//this supposed to be milisecond
duration = ((float)end_time - start_time)/CLOCKS_PER_SEC;
}
float get_last_duration() const {
return duration;
}
};
class Allocation {
public:
void *address;
size_t size;
bool is_array;
bool deleted;
Allocation():
address( 0 ),
size( 0 ),
is_array( false ),
deleted( false ) {
// Empty constructor
}
Allocation( void *a, size_t s, bool i ):
address( a ),
size( s ),
is_array( i ),
deleted( false ) {
// Empty constructor
}
};
int to_int( int *ptr ) {
int result = *ptr;
if ( result < 0 ) {
result = result + (1 << (sizeof( int ) - 1));
}
return result >> 3;
}
// All instances of an allocation are stored in this chained hash table
class HashTable {
private:
int array_size;
Allocation *allocated;
int total_memory_alloc;
int total_memory_deleted;
bool record;
public:
// Initialize all of the addresses to 0
HashTable( int as ):
array_size( as ),
total_memory_alloc( 0 ),
total_memory_deleted( 0 ),
record( false ) {
allocated = new Allocation[array_size];
}
void reserve( int N ) {
// N must be a power of 2
if ( (N & ((~N) + 1)) != N ) {
throw illegal_argument();
}
delete [] allocated;
array_size = N;
allocated = new Allocation[array_size];
}
int memory_alloc() const {
return total_memory_alloc - total_memory_deleted;
}
void memory_store() const {
memory_alloc_store = total_memory_alloc - total_memory_deleted;
}
void memory_change( int n ) const {
int memory_alloc_diff = total_memory_alloc - total_memory_deleted - memory_alloc_store;
if ( memory_alloc_diff != n ) {
std::cout << "WARNING: expecting a change in memory allocation of "
<< n << " bytes, but the change was " << memory_alloc_diff
<< std::endl;
}
}
void insert( void *ptr, size_t size, bool is_array ) {
if ( !record ) {
return;
}
// the hash function is the last log[2]( array_size ) bits
int hash = to_int( reinterpret_cast<int *>( &ptr ) ) & (array_size - 1);
for ( int i = 0; i < array_size; ++i ) {
// It may be possible that we are allocated the same memory
// location twice (if there are numerous allocations and
// deallocations of memory. Thus, the second check is necessary,
// otherwise it may introduce session dependant errors.
if ( allocated[hash].address == 0 || allocated[hash].address == ptr ) {
// Store the address, the amount of memory allocated,
// whether or not new[] was used, and set 'deleted' to false.
allocated[hash] = Allocation( ptr, size, is_array );
// Add the memory allocated to the total memory allocated.
total_memory_alloc += size;
return;
}
hash = (hash + 1) & (array_size - 1);
}
std::cout << "WARNING: allocating more memory than is allowed for this project" << std::endl;
throw overflow();
}
size_t remove( void *ptr, bool is_array ) {
if ( !record || ptr == 0 ) {
return 0;
}
// the hash function is the last log[2]( array_size ) bits
int hash = to_int( reinterpret_cast<int *>( &ptr ) ) & ( array_size - 1 );
// Continue searching until we've checked all bins
// or we find an empty bin.
for ( int i = 0; i < array_size && allocated[hash].address != 0; ++i ) {
if ( allocated[hash].address == ptr ) {
// First check if:
// 1. If the wrong delete was called (e.g., delete[] when new was
// used or delete when new[] was used).
// 2. If the memory has already been deallocated previously.
//
// If the deletion is successful, then:
// 1. Set the 'deleted' flag to 'true', and
// 2. Add the memory deallocated ot the total memory deallocated.
if ( allocated[hash].is_array != is_array ) {
if ( allocated[hash].is_array ) {
std::cout << "WARNING: use 'delete [] ptr;' to free memory allocated with 'ptr = new Class[array_size];'" << std::endl;
} else {
std::cout << "WARNING: use 'delete ptr;' to free memory allocated with 'ptr = new Class(...);'" << std::endl;
}
throw invalid_deletion();
} else if ( allocated[hash].deleted ) {
std::cout << "WARNING: calling delete twice on the same memory location: " << ptr << std::endl;
throw invalid_deletion();
}
allocated[hash].deleted = true;
total_memory_deleted += allocated[hash].size;
// zero the memory before it is deallocated
char *cptr = static_cast<char *>( ptr );
for ( size_t j = 0; j < allocated[hash].size; ++j ) {
cptr[j] = 0;
}
return allocated[hash].size;
}
hash = (hash + 1) & (array_size - 1);
}
// If we've gotten this far, this means that the address was
// never allocated, and therefore we are calling delete on
// something which should be deleted.
std::cout << "WARNING: deleting a pointer to which memory was never allocated: " << ptr << std::endl;
throw invalid_deletion();
}
// Print a difference between the memory allocated and the memory deallocated
void summary() {
std::cout << "Memory allocated minus memory deallocated: "
<< total_memory_alloc - total_memory_deleted << std::endl;
}
// Print the difference between total memory allocated and total memory deallocated.
void details() {
std::cout << "SUMMARY OF MEMORY ALLOCATION:" << std::endl;
std::cout << " Memory allocated: " << total_memory_alloc << std::endl;
std::cout << " Memory deallocated: " << total_memory_deleted << std::endl << std::endl;
std::cout << "INDIVIDUAL REPORT OF MEMORY ALLOCATION:" << std::endl;
std::cout << " Address Using Deleted Bytes " << std::endl;
for ( int i = 0; i < array_size; ++i ) {
if ( allocated[i].address != 0 ) {
std::cout << " " << allocated[i].address
<< ( allocated[i].is_array ? " new[] " : " new " )
<< ( allocated[i].deleted ? "Y " : "N " )
<< std::setw( 6 )
<< allocated[i].size << std::endl;
}
}
}
// Start recording memory allocations
void start_recording() {
record = true;
}
// Stop recording memory allocations
void stop_recording() {
record = false;
}
bool is_recording() {
return record;
}
};
bool asymptotic_tester( double *array, int N, int k, bool ln ) {
double *ratios = new double[N];
double *differences = new double[N- 1];
int M = 2;
for ( int i = 0; i < N; ++i ) {
ratios[i] = array[i] / (M*(ln ? std::log( static_cast<double>( M ) ) : 1.0));
M = M*(1 << k);
}
for ( int i = 0; i < N - 1; ++i ) {
differences[i] = ratios[i + 1] - ratios[i];
// std::cout << differences[i] << std::endl;
}
for ( int i = 1; i < N - 1; ++i ) {
if ( !( differences[i] < 0 ) ) {
if ( differences[i] > differences[i - 1] ) {
delete [] ratios;
delete [] differences;
return false;
}
}
}
delete [] ratios;
delete [] differences;
return true;
}
HashTable allocation_table( 8192 );
std::string history[1000];
int count = 0;
void initialize_array_bounds( char *ptr, size_t size ) {
std::memset( ptr, 'U', size );
}
void check_array_bounds( char *ptr, size_t size ) {
for ( size_t i = 0; i < PAD; ++i ) {
if ( ptr[i] != 'U' ) {
std::cout << "Memory before the array located at adderss "
<< static_cast<void *>( ptr + PAD ) << " was overwritten" << std::endl;
throw out_of_range();
}
if ( ptr[size - 1 - i] != 'U' ) {
std::cout << "Memory after the array located at adderss "
<< static_cast<void *>( ptr + PAD ) << " was overwritten" << std::endl;
throw out_of_range();
}
}
bool used = false;
for ( size_t i = 0; i < size - 2*PAD; ++i ) {
if ( ptr[PAD + i] != 'U' ) {
used = true;
break;
}
}
if ( !used ) {
std::cout << "The memory allocated at adderss "
<< static_cast<void *>( ptr + PAD ) << " was not used" << std::endl;
}
std::memset( ptr, 'U', size );
}
/* // Type input<Type>()
//
// Attempt to parse the input as if it is of the given Type
// - If it fails, it prints an error message and throws an exception
template <typename Type>
Type input() {
std::string s;
std::cin >> s;
std::stringstream ss( s );
Type n;
ss >> n;
if ( ss.fail() ) {
std::cerr << "Not expecting the input "" << s << """ << std::endl;
throw invalid_input();
}
return n;
}
// bool input<bool>()
//
// This is a specialization of the input function for Boolean values
// - It will accept the strings 'true' and 'false' as well as 1 and 0
// - If it fails, it prints an error message and throws an exception
template <>
bool input<bool>() {
std::string s;
std::cin >> s;
std::stringstream ss( s );
if ( s == "true" ) {
return 1;
} else if ( s == "false" ) {
return 0;
} else {
bool n;
ss >> n;
if ( ss.fail() ) {
std::cerr << "Not expecting the input "" << s << """ << std::endl;
throw invalid_input();
}
return n;
}
} */
}
void *operator new( size_t size ) throw( std::bad_alloc ) {
void *ptr = malloc( size );
ece250::allocation_table.insert( ptr, size, false );
return static_cast<void *>( ptr );
}
void operator delete( void *ptr ) throw () {
ece250::allocation_table.remove( ptr, false );
free( ptr );
}
void *operator new[]( size_t size ) throw( std::bad_alloc ) {
char *ptr = static_cast<char *>( malloc( size + 2*ece250::PAD ) );
ece250::allocation_table.insert( static_cast<void *>( ptr + ece250::PAD ), size, true );
ece250::initialize_array_bounds( ptr, size + 2*ece250::PAD );
return static_cast<void *>( ptr + ece250::PAD );
}
void operator delete[]( void *ptr ) throw () {
size_t size = ece250::allocation_table.remove( ptr, true );
if ( ece250::allocation_table.is_recording() ) {
ece250::check_array_bounds( static_cast<char *>( ptr ) - ece250::PAD, size + 2*ece250::PAD );
}
free( static_cast<char *>( ptr ) - ece250::PAD );
}
#endif
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.