The goal of this assignment is to reinforce using linear data structures in C++. Specifically, create a dynamic (linked list) implementation of a deque using the provided header file.

I have the code, but the stuff I would like to print in my main file is not printing. Can someone take a look and see why only my first two cout statements print, but none of the rest is printing? The code is below,

----------------------------------------------------------

main.cpp ----------------------------------------------------------

#include "deque.h" #include #include

int main() { std::cout << "Will create two blank deques." << std::endl; deque* di; std::cout << "Created a blank deque and performing a few basic tasks: "; deque* di_empty; int i; int a[] = {8,7,6,21,28,35,42,49,56,63}; int b[] = {0,1,4,9,16,25,36,49,64,81}; di->push_front(7); di->push_back(6); di->push_front(8); for (i = 3; i < 10; i++) di->push_back(i * 7); assert(di->back() == a[9] && di->front() == a[0]); std::cout << "PASSED." << std::endl;

std::cout << "Will now create a new deque using default copy constructor and passing original deque as parameter: "; deque* di2(di); assert(di2->back() == a[9] && di2->front() == a[0]); std::cout << "PASSED." << std::endl; std::cout << "Updating the new deque using pop_back: "; di2->pop_back(); assert(di2->back() == a[8]); std::cout << "PASSED." << std::endl; std::cout << "Verifying original is unchanged: "; assert(di->back() == a[9]); std::cout << "PASSED." << std::endl;

std::cout << "Will now use default assignment operator to assign empty deque to original deque: "; di = di_empty; assert(di->empty()); std::cout << "PASSED." << std::endl; std::cout << "Will now fill deque using push_back: "; for (i = 0; i < 10; i++) di->push_back(i * i); assert(di->front() == b[0] && di->back() == b[9]); std::cout << "PASSED." << std::endl; std::cout << "Removing two items using pop_front: "; di->pop_front(); di->pop_front(); assert(di->front() == b[2]); std::cout << "PASSED." << std::endl;

std::cout << "Creating a deque of doubles to verify template: "; deque dd; assert(dd.empty()); std::cout << "PASSED." << std::endl; std::cout << "Will now fill deque using push_front: "; for (i = 0; i < 10; i++) dd.push_back(i / 13); std::cout << "PASSED." << std::endl; return 0; }

----------------------------------------------------------------------------------- deque.template ---------------------------------------------- #include #include "node2.h"

template deque::deque() { count = 0; first = NULL; last = NULL; }

template deque::~deque() { list_clear(first); }

template deque::deque(const deque& dq) { list_copy(dq.first, first, last); count = dq.count; }

template deque& deque::operator = (const deque& dq) { if (first == dq.first) return *this; list_clear(first); list_copy(dq.first, first, last); count = dq.count; return *this; }

template T& deque::front() { assert(count != 0); return first->data(); }

template T deque::front() const { assert(count != 0); return first->data(); }

template T& deque::back() { assert(count != 0); return last->data(); }

template T deque::back() const { assert(count != 0); return last->data(); }

template void deque::push_front(const T& entry) { list_head_insert(first, entry); count++; }

template void deque::push_back(const T& entry) { assert(!empty()); node* ptr; ptr = last; list_insert(ptr, entry); last = ptr->link(); count++; }

template void deque::pop_front() { assert(!empty()); list_head_remove(first); count--; }

template void deque::pop_back() { assert(!empty()); node* ptr; ptr = first; while (ptr->link() != last) { ptr = ptr->link(); } list_remove(ptr); last = ptr; count--; }

template typename deque::size_type deque::size() const { return count; }

template bool deque::empty() const { return count == 0; }

template bool operator == (const deque& dq1, const deque& dq2) { if (dq1.count != dq2.count || dq1.first != dq2.first || dq1.last != dq2.last) return false; else { typename deque::size_type i; node* ptr1, ptr2; ptr1 = dq1.first; ptr2 = dq2.first; for (i = 0; i < dq1.count; i++) { if (ptr1->data != ptr2->data()) return false; else { ptr1 = ptr1->link(); ptr2 = ptr2->link(); } } } return true; }

template std::ostream& operator<< (std::ostream& out, const deque& dq) { typename deque::size_type i; node* ptr; i = 0; ptr = dq.first; while (i < dq.count) { out << ptr->data() << " "; ptr = ptr->link(); i++; } return out; }

--------------------------------------------------------------------------------- deque.h --------------------------------------------------------------------------------- #ifndef _DEQUE_H_ #define _DEQUE_H_

#include #include #include "node2.h"

using namespace main_savitch_6B;

template class deque { public: typedef std::size_t size_type;

//postcondition: empty deque has been created deque();

// postcondition: all resouroces allocated to the deque // have been deallocated ~deque();

// postcondition: newly created deque is a copy of dq deque(const deque& dq);

// postcondition: current deque is a copy of dq deque& operator = (const deque& dq);

//precondition: deque is not empty // postcondition: reference to element at front of deque // has been returned T& front();

// precondition: deque is not empty // postcondition: copy of element at front of deque // has been returned T front() const;

// precondition: deque is not empty // postcondition: reference to element at front of deque // has been returned T& back();

// precondition: deque is not empty // postcondition: copy of element at back of deque // has been returned T back() const;

// postcondition: entry has been inserted at the front // of the deque void push_front (const T& entry);

// postcondition: entry has been inserted at the back // of the deque void push_back (const T& entry);

// precondition: deque is not empty // postcondition: element at front of deque has been removed void pop_front();

// precondition: deque is not empty // postcondition: element at back of deque has been removed void pop_back();

// postcondition: number of elements in deque has been returned size_type size() const;

// postcondition: whether deque is empty has been returned bool empty() const;

// postcondition: returned whether 2 deques are equal - equal is defined // as the deques have the same number of elements & // corresponding elements are equal template friend bool operator == (const deque& dq1, const deque& dq2);

// postcondition: dq has been display from front to rear on out template friend std::ostream& operator<< (std::ostream& out, const deque& dq);

private: size_type count; // Total number of items in the queue node* first; node* last; };

#include "deque.template"

#endif

---------------------------------------------------------------------------------------------- node2.h ----------------------------------------------------------------------------- #ifndef MAIN_SAVITCH_NODE2_H #define MAIN_SAVITCH_NODE2_H #include // Provides NULL and size_t #include // Provides iterator and forward_iterator_tag

namespace main_savitch_6B { template class node { public: // TYPEDEF typedef Item value_type; // CONSTRUCTOR node(const Item& init_data=Item( ), node* init_link=NULL) { data_field = init_data; link_field = init_link; } // MODIFICATION MEMBER FUNCTIONS Item& data( ) { return data_field; } node* link( ) { return link_field; } void set_data(const Item& new_data) { data_field = new_data; } void set_link(node* new_link) { link_field = new_link; } // CONST MEMBER FUNCTIONS const Item& data( ) const { return data_field; } const node* link( ) const { return link_field; } private: Item data_field; node *link_field; };

// FUNCTIONS to manipulate a linked list: template void list_clear(node*& head_ptr);

template void list_copy (const node* source_ptr, node*& head_ptr, node*& tail_ptr);

template void list_head_insert(node*& head_ptr, const Item& entry);

template void list_head_remove(node*& head_ptr);

template void list_insert(node* previous_ptr, const Item& entry);

template std::size_t list_length(const node* head_ptr);

template NodePtr list_locate(NodePtr head_ptr, SizeType position);

template void list_remove(node* previous_ptr);

template NodePtr list_search(NodePtr head_ptr, const Item& target);

// FORWARD ITERATORS to step through the nodes of a linked list // A node_iterator of can change the underlying linked list through the // * operator, so it may not be used with a const node. The // node_const_iterator cannot change the underlying linked list // through the * operator, so it may be used with a const node. // WARNING: // This classes use std::iterator as its base class; // Older compilers that do not support the std::iterator class can // delete everything after the word iterator in the second line:

template class node_iterator : public std::iterator { public: node_iterator(node* initial = NULL) { current = initial; } Item& operator *( ) const { return current->data( ); } node_iterator& operator ++( ) // Prefix ++ { current = current->link( ); return *this; } node_iterator operator ++(int) // Postfix ++ { node_iterator original(current); current = current->link( ); return original; } bool operator ==(const node_iterator other) const { return current == other.current; } bool operator !=(const node_iterator other) const { return current != other.current; } private: node* current; };

template class const_node_iterator : public std::iterator { public: const_node_iterator(const node* initial = NULL) { current = initial; } const Item& operator *( ) const { return current->data( ); } const_node_iterator& operator ++( ) // Prefix ++ { current = current->link( ); return *this; } const_node_iterator operator ++(int) // Postfix ++ { const_node_iterator original(current); current = current->link( ); return original; } bool operator ==(const const_node_iterator other) const { return current == other.current; } bool operator !=(const const_node_iterator other) const { return current != other.current; } private: const node* current; }; }

#include "node2.template" #endif --------------------------------------------------------------------------------------- node2.template ------------------------------------------------ #include // Provides assert #include // Provides NULL and size_t

namespace main_savitch_6B { template void list_clear(node*& head_ptr) // Library facilities used: cstdlib { while (head_ptr != NULL) list_head_remove(head_ptr); } template void list_copy( const node* source_ptr, node*& head_ptr, node*& tail_ptr ) // Library facilities used: cstdlib { head_ptr = NULL; tail_ptr = NULL; // Handle the case of the empty list if (source_ptr == NULL) return; // Make the head node for the newly created list, and put data in it list_head_insert(head_ptr, source_ptr->data( )); tail_ptr = head_ptr; // Copy rest of the nodes one at a time, adding at the tail of new list source_ptr = source_ptr->link( ); while (source_ptr != NULL) { list_insert(tail_ptr, source_ptr->data( )); tail_ptr = tail_ptr->link( ); source_ptr = source_ptr->link( ); } } template void list_head_insert(node*& head_ptr, const Item& entry) { head_ptr = new node(entry, head_ptr); } template void list_head_remove(node*& head_ptr) { node *remove_ptr; remove_ptr = head_ptr; head_ptr = head_ptr->link( ); delete remove_ptr; } template void list_insert(node* previous_ptr, const Item& entry) { node *insert_ptr; insert_ptr = new node(entry, previous_ptr->link( )); previous_ptr->set_link(insert_ptr); } template std::size_t list_length(const node* head_ptr) // Library facilities used: cstdlib { const node *cursor; std::size_t answer; answer = 0; for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( )) ++answer; return answer; } template NodePtr list_locate(NodePtr head_ptr, SizeType position) // Library facilities used: cassert, cstdlib { NodePtr cursor; SizeType i; assert(0 < position); cursor = head_ptr; for (i = 1; (i < position) && (cursor != NULL); ++i) cursor = cursor->link( ); return cursor; } template void list_remove(node* previous_ptr) { node *remove_ptr; remove_ptr = previous_ptr->link( ); previous_ptr->set_link(remove_ptr->link( )); delete remove_ptr; } template NodePtr list_search(NodePtr head_ptr, const Item& target) // Library facilities used: cstdlib { NodePtr cursor; for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( )) if (target == cursor->data( )) return cursor; return NULL; } }