EECE 352: PS7

Problem 1 (40%): For the first part of this PS you will take the List implementation below (which is a slightly improved version of the one I presented in class) and modify so that it implements a doubly-linked list.

Double-linked lists are explained in the textbook (page 498). To implement them you will need to modify the Node class so that it keeps pointers to the next and previous nodes, you should also modify all the other functions to work well with these new nodes.

Now that you have a doubly linked list, you need a way to add elements to it. Therefore, you implement push_front() and push_back() (their signatures are provided below, curiously, they are the same as used in the STL). Notice that an efficient (i.e. O(1)) implementation of push_back() will require you to make some additions/modifications to the existing code. Of course, you are all about efficiency, so you jump on the chance to make your code as efficient as possible.

Once that is done, you should now feel empowered enough to implement operator-- (both prefix and postfix) with a couple of casual keystrokes. Look at operator++ for guidance in writing its signature.

Problem 2 (35%) You will now consult your textbook and class notes for a quick review of the proper way of inserting and deleting elements from a linked list. After this brisk exercise you will feel compelled to implement these functions in order to verify your understanding of the material.

Namely, you will implement insert() and erase() functions. Their signatures are provided below.

Problem 3 (15%) Not satisfied by the ease with which you solve these toy problems, you decide to challenge yourself by further implementing some of the more advanced member functions of the STL list container. Namely, you decide to implement the merge() function.

The merge() function (signature provided below) assumes that both the objects in its list and the objects in the list given to it as an argument, are already sorted. The function then merges the argument list into the local list while preserving the order (as defined by T::operator< ).

Problem 4 (10%) Finally, you recall from a couple of weeks ago our discussion of mergesort, which used a merge function just like this one. "Hmmm", you ponder, "now that I have a merge it should not be too hard to write a mergesort", you naively conclude.

So, you then implement a sort() function that sorts the elements on the list, using a mergesort implementation (along with calls to the merge() you already defined). Hint: this requires a lot of copying of lists.

#include<iostream>
#include<string>
#include"List.h"
using namespace std;

int main(){
	List<string> s;
    s.push_front("T"); s.push_front("N"); s.push_front("G"); s.push_front("A");
	
    for (List<string>::Iterator si = s.begin(); si != s.end(); ++si) //prints AGNT
         cout << *si;  
	cout << endl;

	List<string>::Iterator sj = s.end(); //points to one after last element
	//To get the next line to work you must modify operator-- to return an
	// Iterator & (i.e. *this).
	cout << *(sj--); 
	cout << *(sj--);
	cout << *(sj--);
	cout << *(sj--)<< endl; //they print TNGA


	List<string> t;
	t.push_back("A"); t.push_back("G"); t.push_back("N"); t.push_back("T");
	
	List<string>::Iterator ti;
	for (ti = t.begin(); ti != t.end(); ++ti) //prints AGNT
         cout << *ti; 
	cout << endl;	


	ti = t.begin();
	ti++; ti++;
	t.insert(ti, "E");
	cout << t << endl; 	//prints A G E N T

	for (ti =t.begin(); ti != t.end(); ++ti)
		t.insert(ti, "-");
	t.insert(ti, "-");
	cout << t << endl; //prints - A - G - E - N - T -


	for (ti =t.begin(); ti != t.end(); ++ti){
		ti = t.erase(ti);
	}
	cout << t << endl;	//prints A G E N T


	List<int> i1;
	i1.push_back(5); i1.push_back(7); i1.push_back(15); i1.push_back(28);
	List<int> i2;
	i2.push_back(2); i2.push_back(6); i2.push_back(8); i2.push_back(21);
	i1.merge(i2); //i1 and i2 are sorted, the new i1 should also be sorted.
	cout << i1 << endl; //prints 2 5 6 7 8 15 21 28 
	cout << i2 << endl; //prints 2 6 8 21

	List<int> x;
	x.push_back(3); x.push_back(1); x.push_back(33); x.push_back(13);
	x.push_back(15); x.push_back(28); x.push_back(21); x.push_back(2);
	x.sort();
	cout << x << endl; //prints 1 2 3 13 15 21 28 33



    return 0;
}

//A list class with iterators.
//It implements a small subset of the functionality found in
//the STL list container. 

#include<iostream>

using namespace std;

template<class T>
class List {
  
  class Node {
  public:
    T element;
    Node * next;
    Node() : next(0) {};
    Node(const T & e, Node * n = 0): 
      element(e), next(n){};
    ~Node(){}
  };
  
  Node * head;

 public:
  class Iterator {
    Node * ihead;
    Node * current;
  public:
    Iterator() : ihead(0), current(0) {};
    Iterator(Node * h, Node * c) : ihead(h), current(c){};
    ~Iterator(){};
    Iterator & operator++() { 
      if (current != 0)
	current = current->next;
      return *this;};
    Iterator & operator++(int) {
      return operator++();};
    T & operator*() {
      return current->element;}
    bool operator!=(const Iterator & i) const{
      return current != i.current;}
    bool operator==(const Iterator & i) const{
      return current == i.current;}
    bool isNull() const{
      return current == 0;} //returns true if Iterator is not pointing to anyone
    Node * getCurrent() const {
      return current;}
    //operator- lets you substract these Iterators just like in the STL
    int operator-(const Iterator & i) const{ 
      int j = 0;
      Node * c = i.current;
      while (c != current && c != 0){
	c = c->next;
	j++;
      }
      return j;
      
    }
    //operator+ lets you add an int to an Iterator, the same as doing
    //  operator++ n times
    Iterator operator+(const int n){
      Node * c = current;
      for (int i=0; i<n && c != 0; i++)
	c = c->next;
      return Iterator(ihead, c);
    }
    Iterator & operator--() {  //implement this
    };
    Iterator & operator--(int) {  //implement this
    };
  };
  
  List() {
    head = new Node;
    };
  ~List() {
    MakeEmpty(); 
    delete head;}
  bool IsEmpty(){return head->next == 0 };
  void MakeEmpty(){
    Node * nextNode;
    for (Node * c = head->next; c != 0; c = nextNode){
      nextNode = c->next;
      delete c;
    }
  };
  
  friend ostream & operator<<(ostream & os, const List<T> & l){
    Node * nextNode;
    for (Node * c = l.head->next; c != 0; c = nextNode){
      os << c->element << " ";
      nextNode = c->next;
    }
    return os;
  }
  Iterator begin() const{
    return Iterator(head, head->next);
  };
  Iterator end() const{
    return Iterator(head, 0);
  };
  
  //adds element at the front of the list
  void push_front(T x){ //implement this
  }
  
  //adds element to the back of the list
  void push_back(T x){ //implement this
  };
  
  //Insert element x right before the one pointed to by i.
  //  and return the position of the new element
  //If i points to 0 (one beyond end) then add it at the end.
  Iterator insert(const Iterator & i, const T & x){ //implement this
  }
  
  //Removes the element at position i and returns the position
  // of the next element
  //If i points to 0 then return iterator that points to 0 on this list.
  // and do not remove anything.
  Iterator erase(const Iterator & i){ //implement this
  }
  
  //merges l into this list. It assumes that both lists are already
  // sorted using T::operator< 
  void merge(const List<T> & l){ //implement this
  }
  
  //Sorts this list, using mergesort (and the merge we just defined above)
  // HINT: You will need to make copies of the list. Also, use the
  //  functions you have already defined.
  void sort(){ //implement this, if you dare.
  }

};