This is a c++ class utilizing class templates and linked lists. I need to implement the following member function(s) to List.cpp. Node.hpp/cpp should be fine but if you feel like there needs to be a change for compilation or testing, feel free to do so but make sure to comment on why it was done.

/** @pre assumes position is valid, if position is > item_count_ it returns an empty List, also assumes that operators <= and >= are defined on type T @param position contained in the sorted/increasing (first <= position <= last) sublist to be generated @return a sublist containing the item at position consisting of sorted/ increasing items (first <= position <= last) */ List scanSublist(size_t position);

HERE IS THE CODE

Node.hpp

#ifndef NODE_ #define NODE_

template class Node {

public: Node(); Node(const ItemType& an_item); Node(const ItemType& an_item, Node* next_node_ptr); void setItem(const ItemType& an_item); void setNext(Node* next_node_ptr); void setPrevious(Node* previous_node_ptr); ItemType getItem() const ; Node* getNext() const ; Node* getPrevious() const ;

private: ItemType item_; // A data item Node* next_; // Pointer to next node Node* previous_; // Pointer to next node }; // end Node

#include "Node.cpp" #endif

Node.cpp

#include "Node.hpp" //#include

template Node::Node() : next_(nullptr) { } // end default constructor

template Node::Node(const ItemType& an_item) : item_(an_item), next_(nullptr) { } // end constructor

template Node::Node(const ItemType& an_item, Node* next_node_ptr) : item_(an_item), next_(next_node_ptr) { } // end constructor

template void Node::setItem(const ItemType& an_item) { item_ = an_item; } // end setItem

template void Node::setNext(Node* next_node_ptr) { next_ = next_node_ptr; } // end setNext

template void Node::setPrevious(Node* previous_node_ptr) { previous_ = previous_node_ptr; } // end setPrevious

template ItemType Node::getItem() const { return item_; } // end getItem

template Node* Node::getNext() const { return next_; } // end getNext

template Node* Node::getPrevious() const { return previous_; } // end getPrevious

List.hpp

#ifndef LIST_H_ #define LIST_H_ #include #include "Node.hpp"

template class List {

public: List(); // constructor List(const List& a_list); // copy constructor ~List(); // destructor

/**@return true if list is empty - item_count_ == 0 */ bool isEmpty() const;

/**@return the number of items in the list - item_count_ */ size_t getLength() const;

/** @param position indicating point of insertion @param new_element to be inserted in list @post new_element is added at position in list (before the node previously at that position) @return true always - it always inserts, if position > item_count_ it inserts at end of list */ bool insert(size_t position, const T& new_element);

/** @param position indicating point of deletion @post node at position is deleted, if any. List order is retains @return true if ther eis a node at position to be deleted, false otherwise */ bool remove(size_t position);

/** @pre assumes there is an item at position - NO ERROR HANDLING @param position of item to be retrieved @return the item at position in list if there is one, otherwise it returns a dummy UNITIALIZED object of type T -- temporary suboptimal solution in place of error handling to be discussed later in the course */ T getItem(size_t position) const;

/**@post the list is empty and item_count_ == 0*/ void clear();

//*** PROJECT-SPECIFIC METHODS ***//

/** @pre assumes std::cout << is defined for objects of type T (can be sent to standard output) -- This method is not general, thus not appropriate for a templated class, it is provided for project debugging purposes @post traverses the list and prints (std::cout) every item in the list*/ void traverse();

private: Node* first_; // Pointer to first node Node* last_; // Pointer to last node size_t item_count_; // number of items in the list

//if position > item_count_ returns nullptr Node* getPointerTo(size_t position) const;

}; // end List

#include "List.cpp" #endif // LIST_H_

List.cpp

#include "List.hpp" template List::List(): item_count_(0), first_(nullptr), last_(nullptr){} // constructor //copy constructor template List::List(const List& a_list) { item_count_ = a_list.item_count_; Node* orig_chain_ptr = a_list.first_; // Points to nodes in original chain if (orig_chain_ptr == nullptr) {// Original chain is empty first_ = nullptr; last_ = nullptr; } else { // Copy first node first_ = new Node(); first_->setPrevious(nullptr); first_->setItem(orig_chain_ptr->getItem()); // Copy remaining nodes Node* new_chain_ptr = first_; // Points to last node in new chain orig_chain_ptr = orig_chain_ptr->getNext(); // Advance original-chain pointer while (orig_chain_ptr != nullptr) { // Get next item from original chain T next_item = orig_chain_ptr->getItem(); // Create a new node containing the next item Node* new_node_ptr = new Node(next_item); // Link new node to end of new chain new_chain_ptr->setNext(new_node_ptr); new_node_ptr->setPrevious(new_chain_ptr); // Advance pointer to new last node new_chain_ptr = new_chain_ptr->getNext(); // Advance original-chain pointer orig_chain_ptr = orig_chain_ptr->getNext(); } // end while // Flag end of chain new_chain_ptr->setNext(nullptr); last_ = new_chain_ptr; } // end if } // copy constructor // destructor template List::~List(){ clear();} /**@return true if list is empty - item_count_ == 0 */ template bool List::isEmpty() const{ return (item_count_ == 0);} /**@return the number of items in the list - item_count_ */ template size_t List::getLength() const{return item_count_;} /** @param position indicating point of insertion @param new_element to be inserted in list @post new_element is added at position in list (before the node previously at that position) @return true always - it always inserts, if position > item_count_ it inserts at end of list */ template bool List::insert(size_t position, const T& new_element) { // Create a new node containing the new entry and get a pointer to position Node* new_node_ptr = new Node(new_element); Node* pos_ptr = getPointerTo(position); // Attach new node to chain if (first_ == nullptr) { //Chain is empty - Insert first node new_node_ptr->setNext(nullptr); new_node_ptr->setPrevious(nullptr); first_ = new_node_ptr; last_ = new_node_ptr; } else if (pos_ptr == first_) { // Insert new node at beginning of list new_node_ptr->setNext(first_); new_node_ptr->setPrevious(nullptr); first_->setPrevious(new_node_ptr); first_ = new_node_ptr; } else if (pos_ptr == nullptr) { //insert at end of list new_node_ptr->setNext(nullptr); new_node_ptr->setPrevious(last_); last_->setNext(new_node_ptr); last_ = new_node_ptr; } else { // Insert new node before node to which pos_ptr points new_node_ptr->setNext(pos_ptr); new_node_ptr->setPrevious(pos_ptr->getPrevious()); pos_ptr->getPrevious()->setNext(new_node_ptr); pos_ptr->setPrevious(new_node_ptr); } // end if item_count_++; // Increase count of entries return true; //It will always insert, if pos_ptr is nullptr it will insert at end }//end insert /** @param position indicating point of deletion @post node at position is deleted, if any. List order is retains @return true if ther eis a node at position to be deleted, false otherwise */ template bool List::remove(size_t position) { //get pointer to position Node* pos_ptr = getPointerTo(position); if(pos_ptr == nullptr) return false; else { // Remove node from chain if (pos_ptr == first_) { // Remove first node first_ = pos_ptr->getNext(); first_->setPrevious(nullptr); // Return node to the system pos_ptr->setNext(nullptr); delete pos_ptr; pos_ptr = nullptr; } else if (pos_ptr == last_) { //remove last node last_ = pos_ptr->getPrevious(); last_->setNext(nullptr); // Return node to the system pos_ptr->setPrevious(nullptr); delete pos_ptr; pos_ptr = nullptr; } else { //Remove from the middle pos_ptr->getPrevious()->setNext(pos_ptr->getNext()); pos_ptr->getNext()->setPrevious(pos_ptr->getPrevious()); // Return node to the system pos_ptr->setNext(nullptr); pos_ptr->setPrevious(nullptr); delete pos_ptr; pos_ptr = nullptr; } item_count_--; // decrease count of entries return true; } }//end remove /** @pre assumes there is an item at position - NO ERROR HANDLING @param position of item to be retrieved @return the item at position in list if there is one, otherwise it returns a dummy UNITIALIZED object of type T -- temporary suboptimal solution in place of error handling to be discussed later in the course */ template T List::getItem(size_t position) const { T dummy; Node* pos_ptr = getPointerTo(position); if(pos_ptr != nullptr) return pos_ptr->getItem(); else return dummy; } /**@post the list is empty and item_count_ == 0*/ template void List::clear() { Node* node_to_delete = first_; while (first_ != nullptr) { first_ = first_->getNext(); // Return node to the system node_to_delete->setNext(nullptr); node_to_delete->setPrevious(nullptr); delete node_to_delete; node_to_delete = first_; } // end while // head_ptr_ is nullptr; node_to_delete is nullptr last_ = nullptr; item_count_ = 0; }//end clear //position follows classic indexing from 0 to item_count_-1 //if position > item_count it returns nullptr template Node* List::getPointerTo(size_t position) const { Node* find = nullptr; if(position < item_count_) { find = first_; for(size_t i = 0; i < position; ++i) { find = find->getNext(); } } return find; }//end getPointerTo //**** PROJECT-SPECIFIC METHODS ***// /** @pre assumes std::cout << is defined for objects of type T (can be sent to standard output) -- This method is not general, thus not appropriate for a templated class, it is provided for project debugging purposes @post traverses the list and prints (std::cout) every item in the list*/ template void List::traverse() { for(Node* ptr = first_; ptr != nullptr; ptr = ptr->getNext()) { std::cout << ptr->getItem() << " "; } std::cout << std::endl; } 

//endof list.cpp