Implementing a Iterator class:

We are given a class called EntryList.cpp based from the header file EntryList.h. Some functions of the .cpp file need to be defined and there is also a main() function given wherin you can check whether those functions you wrote are running in your program. Please use only Dynamic Arrays and not Linked Lists or anything else in the EntryList.cpp file.

If any functions are needed for the .cpp file you can declare them in EntryList.h in the space provided right before the end of the .h file. For your convenience I've added a statement :- ** Your code goes in here ** wherever you have to write the code in the EntryList.cpp file. Be sure to test/run the .cpp file with the main() function that is provided in the .cpp file.

EntryList.h: DO NOT MODIFY // Header file for EntryList class // // An EntryList is a dynamically-resized array storing Entry objects. // The Entry objects are stored in ascending order by vertex. // // EntryList has one nested class, Entry, which defines the objects // stored in an EntryList.

#ifndef _ENTRY_LIST #define _ENTRY_LIST

#include // Standard screen i/o stuff

using std::ostream;

typedef float weight_t; // typedef for edge weights

class EntryList {

friend class Grader; public:

// Default (initial) size of _array. The array starts at this size // and should never be "shrunk" below this size. const int DEFAULT_SIZE = 10;

// Nested Entry class. EntryList stores an array of Entry objects. // An Entry object stores a vertex number and an edge weight; it has // basic getter/setter methods. class Entry { friend EntryList; public: Entry(int vertex = 0, weight_t weight = 0) { _vertex = vertex; _weight = weight; } int getVertex() const { return _vertex; } weight_t getWeight() const { return _weight; } void setWeight(weight_t w) { _weight = w; } friend ostream& operator<<(ostream& sout, const Entry& e); private: int _vertex; // A vertex number weight_t _weight; // An edge weight };

// // Constructors and memory management //

// Default constructor. Creates an EntryList with capacity // DEFAULT_SIZE. EntryList();

// Copy constructor, assignment operator, destructor EntryList(const EntryList& rhs); const EntryList& operator=(const EntryList& rhs); ~EntryList();

// // Basic operations //

// Insert the entry e. The elements of the list must be kept in // increasing order by vertex. If inserting the new element would // exceed the capacity of the EntryList, then the array must be // expanded, doubling the capacity. Returns 'true' if new entry // inserted, 'false' if there is already an entry with the same // vertex as e. bool insert(const Entry& e);

// Update the entry e; return 'true' if an entry with the same // vertex as e exists and was updated, 'false' if there is not entry // with the same vertex as e. bool update(const Entry& e);

// Get the entry with given vertex value; return the entry in ret. // Returns 'true' if an entry with the specified vertex was found, // 'false' if there is no entry with the specified vertex. bool getEntry(int vertex, Entry &ret);

// Remove the entry with given vertex value; return the entry that // was removed in ret. If, after successfully removing an Entry, the // number of Entries is *less than* 1/4 of the capacity, then the // EntryList array must be shrunk, halving its capacity. The // capacity must never be reduced below DEFAULT_SIZE, a constant // defined EntryList.h. Returns 'true' if an entry with the same // vertex as e exists and was removed, returns 'false' if there is // no entry with the specified vertex. bool remove(int vertex, Entry &ret);

// Access an element of the EntryList by index. Throws range_error // if indx is not a valid index into the EntryList's array. // // WARNING: at() allows modification of an Entry, but changing the // vertex value could ruin the ordering of the entries! Entry& at(int indx) const;

// Get the size (numer of Entries actually stored) int size() const { return _size; }

// Get the capacity (size of _array; number of Entries that could be // stored without resizing). int capacity() const { return _capacity; }

// Dump the contents of _array. For debugging. void dump();

// EntryList Iterator class class Iterator { public: // Constructor for iterator for vertices adjacent to vertex v; // indx can be used to set _indx for begin and end iterators. Iterator(EntryList *EList = nullptr, int indx = 0);

// Comparison operators for EntryList iterators bool operator!=(const Iterator& rhs); bool operator==(const Iterator& rhs);

// Advance iterator to next neighbor; if the iterator is already // at the end, leave it unchanged void operator++(int dummy);

// Return neighbor (Entry) at the current iterator position EntryList::Entry operator*(); private: EntryList *_ELptr; // pointer to the associated EntryList int _indx; // current index in the EntryList };

// Create an initial iterator EntryList::Iterator begin();

// Create an end iterator EntryList::Iterator end(); private: Entry *_array; int _capacity; int _size;

// ***************************************** // Private function declarations belong here // ***************************************** };

#endif

EntryList.cpp:

#include "EntryList.h" using std::cout; using std::endl; using std::range_error; // Constructor - DO NOT MODIFY EntryList::EntryList() { _array = new Entry[DEFAULT_SIZE]; _capacity = DEFAULT_SIZE; _size = 0; } EntryList::EntryList(const EntryList& rhs) { ** Your code goes in here ** } const EntryList& EntryList::operator=(const EntryList& rhs) { ** Your code goes in here ** } EntryList::~EntryList() { ** Your code goes in here ** } bool EntryList::insert(const Entry& e) { ** Your code goes in here ** } bool EntryList::update(const Entry& e) { ** Your code goes in here ** } bool EntryList::getEntry(int vertex, Entry &ret) { ** Your code goes in here ** } bool EntryList::remove(int vertex, Entry &ret) { ** Your code goes in here ** } EntryList::Entry& EntryList::at(int indx) const { ** Your code goes in here ** } // dump data structure - DO NOT MODIFY void EntryList::dump() { for (int i = 0; i < _size; i++) { cout << " " << _array[i] << endl; } } EntryList::Iterator::Iterator(EntryList *EList, int indx) { ** Your code goes in here ** } bool EntryList::Iterator::operator!=(const EntryList::Iterator& rhs) { ** Your code goes in here ** } bool EntryList::Iterator::operator==(const EntryList::Iterator& rhs) { ** Your code goes in here ** } void EntryList::Iterator::operator++(int dummy) { ** Your code goes in here ** } EntryList::Entry EntryList::Iterator::operator*() { ** Your code goes in here ** } EntryList::Iterator EntryList::begin() { ** Your code goes in here ** } EntryList::Iterator EntryList::end() { ** Your code goes in here ** } // Insertion operator for Entry objects - DO NOT MODIFY ostream& operator<<(ostream& sout, const EntryList::Entry& e) { sout << e._vertex << ": " << e._weight; return sout; } // A convenient way to write test code for a single class is to write // a main() function at the bottom of the .cpp file. Just be sure to // comment-out main() once you are done testing! // Following is example test code. There is no guarantee that it is // complete -- you are responsible for thoroughly testing your code. // In particular, passing these tests does not mean your // implementation will pass all grading tests. // int main() { // EntryList el; // EntryList::Entry e; // cout << "size: " << el.size() << ", capacity: " << el.capacity() << endl; // el.dump(); // cout << endl; // for (int i = 1; i < 13; i++) { // el.insert( EntryList::Entry((i*5)%13, i) ); // } // cout << "size: " << el.size() << ", capacity: " << el.capacity() << endl; // el.dump(); // cout << endl; // for (int i = 1; i < 13; i+=2) { // el.remove(i, e); // } // cout << "size: " << el.size() << ", capacity: " << el.capacity() << endl; // el.dump(); // cout << endl; // for (int i = 2; i < 13; i+=2) { // el.update( EntryList::Entry(i, 2*i) ); // } // cout << "size: " << el.size() << ", capacity: " << el.capacity() << endl; // el.dump(); // cout << endl; // for (int i = 3; i < 13; i*=2) { // el.remove(i, e); // } // cout << "size: " << el.size() << ", capacity: " << el.capacity() << endl; // el.dump(); // cout << endl; // cout << " Print using iterator: "; // for (auto itr = el.begin(); itr != el.end(); itr++) { // cout << *itr << endl; // } // return 0; // }