View difference between Paste ID: rKezGsjP and 6Pu2YE1P

-/*
+/*
- *  LinkedList.h
+ *  LinkedList.h
- *  Project 1
+ *  Project 1
- *
+ *
- *  Created by Sean Allred on 2/1/12.
+ *  Created by Sean Allred on 2/1/12.
- *  Copyright 2012 St. Mary's College of Maryland. All rights reserved.
+ *  Copyright 2012 St. Mary's College of Maryland. All rights reserved.
- *
+ *
- */
+ */
-
+
-#include <cstdlib>
+#include <cstdlib>
-#include <iostream>
+#include <iostream>
-
+
-using namespace std;
+using namespace std;
-
+
-const bool VERBOSE = true;
+const bool VERBOSE = true;
-const bool SUPERVERBOSE = VERBOSE && false;
+const bool SUPERVERBOSE = VERBOSE && false;
-
+
-template <typename T> class LinkedList;
+template <typename T> class LinkedList;
-template <typename T> ostream& operator << (ostream&, LinkedList<T>&);
+template <typename T> ostream& operator << (ostream&, LinkedList<T>&);
-template <typename T> istream& operator >> (istream&, LinkedList<T>&);
+template <typename T> istream& operator >> (istream&, LinkedList<T>&);
-
+
-template <typename T>
+template <typename T>
-struct Node {
+struct Node {
-	Node<T>(T v) : value(v), used(true) {}
+	Node<T>(T v) : value(v), used(true) {}
-	Node<T>(T v, bool u) : value(v), used(u) {}
+	Node<T>(T v, bool u) : value(v), used(u) {}
-	Node<T> *prev;
+	Node<T> *prev;
-	Node<T> *next;
+	Node<T> *next;
-	T value;
+	T value;
-
+
-	bool used;
+	bool used;
-};
+};
-
+
-template <typename T>
+template <typename T>
-class LinkedList {
+class LinkedList {
-
+
-	friend ostream& operator << <T>(ostream&, LinkedList<T>&);
+	friend ostream& operator << <T>(ostream&, LinkedList<T>&);
-	friend istream& operator >> <T>(istream&, LinkedList<T>&);
+	friend istream& operator >> <T>(istream&, LinkedList<T>&);
-
+
-public:
+public:
-	/* (CON)(DE)STRUCTORS */
+	/* (CON)(DE)STRUCTORS */
-	/* LinkedList()
+	/* LinkedList()
-	  Creates an empty LinkedList and
+	  Creates an empty LinkedList and
-	  initializes 'head' and 'tail'.
+	  initializes 'head' and 'tail'.
-	 */
+	 */
-	LinkedList();
+	LinkedList();
-
+
-	/* LinkedList(int)
+	/* LinkedList(int)
-	  Creates an 'empty' LinkedList with
+	  Creates an 'empty' LinkedList with
-	  however many nodes are specified.
+	  however many nodes are specified.
-
+
-	  Note that each node is *supposed* to be
+	  Note that each node is *supposed* to be
-	  rubbish, but Xcode seems to automagically
+	  rubbish, but Xcode seems to automagically
-	  initialize primitives for you.
+	  initialize primitives for you.
-	 */
+	 */
-	LinkedList(int);
+	LinkedList(int);
-
+
-	/*
+	/*
-	  Copy constructor
+	  Copy constructor
-	 */
+	 */
-	LinkedList(const LinkedList&);
+	LinkedList(const LinkedList&);
-
+
-	/* ~LinkedList()
+	/* ~LinkedList()
-	  Frees all memory used by the object
+	  Frees all memory used by the object
-	  by removing literally every last node.
+	  by removing literally every last node.
-
+
-	  The method trim() is called until the
+	  The method trim() is called until the
-	  size is zero, then 'head' and 'tail'
+	  size is zero, then 'head' and 'tail'
-	  are deleted.
+	  are deleted.
-	 */
+	 */
-	~LinkedList();
+	~LinkedList();
-	/* END (CON)(DE)STRUCTORS */
+	/* END (CON)(DE)STRUCTORS */
-
+
-	/*
+	/*
-	  public interface to 's', which denotes
+	  public interface to 's', which denotes
-	  how many nodes are in the LinkedList
+	  how many nodes are in the LinkedList
-	 */
+	 */
-	int size();
+	int size();
-
+
-	/*
+	/*
-	   Deletes the cell at the
+	   Deletes the cell at the
-	   ith index
+	   ith index
-	 */
+	 */
-	T delCell(int);
+	T delCell(int);
-
+
-	void trimEmpty();
+	void trimEmpty();
-
+
-	/*
+	/*
-	   Inserts a value (T) such that
+	   Inserts a value (T) such that
-	   its index is (int)
+	   its index is (int)
-	 */
+	 */
-	int insert(T, int);
+	int insert(T, int);
-
+
-	/*
+	/*
-	   Shorthand append
+	   Shorthand append
-	 */
+	 */
-	void operator += (T);
+	void operator += (T);
-
+
-	/*
+	/*
-	 Successfully sets a value
+	 Successfully sets a value
-	 from the list (shorthand set(int, T))
+	 from the list (shorthand set(int, T))
-	 */
+	 */
-	T& operator [](const int);
+	T& operator [](const int);
-
+
-	/*
+	/*
-	 Successfully gets a value
+	 Successfully gets a value
-	 from the list (shorthand get(int))
+	 from the list (shorthand get(int))
-	 */
+	 */
-	T operator [](const int) const;
+	T operator [](const int) const;
-
+
-	/*
+	/*
-	   Reference assignment
+	   Reference assignment
-	 */
+	 */
-	void operator =(LinkedList&);
+	void operator =(LinkedList&);
-
+
-	/*
+	/*
-	   Takes off the last element
+	   Takes off the last element
-	 */
+	 */
-	T trim();
+	T trim();
-
+
-//protected:
+//protected:
-	Node<T> *head;
+	Node<T> *head;
-	Node<T> *tail;
+	Node<T> *tail;
-
+
-//private:
+//private:
-	Node<T>* get(int);
+	Node<T>* get(int);
-
+
-	Node<T>* set(T, int);
+	Node<T>* set(T, int);
-
+
-	int append(T);
+	int append(T);
-
+
-	int append(T, bool);
+	int append(T, bool);
-
+
-	void print();
+	void print();
-
+
-	int insertAfter(T, Node<T>*);
+	int insertAfter(T, Node<T>*);
-
+
-	int insertBefore(T, Node<T>*);
+	int insertBefore(T, Node<T>*);
-
+
-	T destroy(Node<T>*);
+	T destroy(Node<T>*);
-
+
-	void expand(int);
+	void expand(int);
-
+
-	void prime();
+	void prime();
-
+
-	int s;
+	int s;
-
+
-	int minsize;
+	int minsize;
-};
+};
-
+
-/*
+/*
- *  LinkedList.cpp
+ *  LinkedList.cpp
- *  Project 1
+ *  Project 1
- *
+ *
- *  Created by Sean Allred on 2/8/12.
+ *  Created by Sean Allred on 2/8/12.
- *  Copyright 2012 St. Mary's College of Maryland. All rights reserved.
+ *  Copyright 2012 St. Mary's College of Maryland. All rights reserved.
- *
+ *
- */
+ */
-
+
-
+
-
+
-/*******************************/
+/*******************************/
-/* Constructors and Destructor */
+/* Constructors and Destructor */
-/*******************************/
+/*******************************/
-
+
-template <typename T>
+template <typename T>
-LinkedList<T>::LinkedList() {
+LinkedList<T>::LinkedList() {
-	this->prime();
+	this->prime();
 }
-
+
-template <typename T>
+template <typename T>
-LinkedList<T>::LinkedList(int i) {
+LinkedList<T>::LinkedList(int i) {
-	this->prime();
+	this->prime();
-
+
-	this->minsize = i;
+	this->minsize = i;
-
+
-	this->expand(i);
+	this->expand(i);
 }
-
+
-template <typename T>
+template <typename T>
-LinkedList<T>::LinkedList(const LinkedList<T>& l) {
+LinkedList<T>::LinkedList(const LinkedList<T>& l) {
-	this->prime();
+	this->prime();
-
+
-	Node<T> *n = l.head;
+	Node<T> *n = l.head;
-	while (n != NULL) {
+	while (n != NULL) {
-		this->append(n->value);
+		this->append(n->value);
-		n = n->next;
+		n = n->next;
-	}
+	}
 }
-
+
-template <typename T>
+template <typename T>
-LinkedList<T>::~LinkedList<T>() {
+LinkedList<T>::~LinkedList<T>() {
-	if(VERBOSE) {
+	if(VERBOSE) {
-		printf("Destroying List at %p\n", this);
+		printf("Destroying List at %p\n", this);
-	}
+	}
-	while (s != 0) {
+	while (s != 0) {
-		this->trim();
+		this->trim();
-	}
+	}
-	if (VERBOSE) {
+	if (VERBOSE) {
-		printf("List at %p destroyed\n", this);
+		printf("List at %p destroyed\n", this);
-	}
+	}
 }
-
+
-/**********************/
+/**********************/
-/* Operator Overloads */
+/* Operator Overloads */
-/**********************/
+/**********************/
-
+
-template <typename T> void
+template <typename T> void
-LinkedList<T>::operator = (LinkedList<T>& l) {
+LinkedList<T>::operator = (LinkedList<T>& l) {
-	this->head = l.head;
+	this->head = l.head;
-	this->tail = l.tail;
+	this->tail = l.tail;
 }
-
+
-template <typename T> void
+template <typename T> void
-LinkedList<T>::operator += (T val) {
+LinkedList<T>::operator += (T val) {
-	this->append(val);
+	this->append(val);
 }
-
+
-template <typename T> T& // set
+template <typename T> T& // set
-LinkedList<T>::operator [] (const int i) {
+LinkedList<T>::operator [] (const int i) {
-	return this->get(i)->value;
+	return this->get(i)->value;
 }
-
+
-template <typename T> T // get
+template <typename T> T // get
-LinkedList<T>::operator [] (const int i) const {
+LinkedList<T>::operator [] (const int i) const {
-	return this->get(i)->value;
+	return this->get(i)->value;
 }
-
+
-/***** Insertion and Extraction *****/
+/***** Insertion and Extraction *****/
-
+
-template <typename T> ostream&
+template <typename T> ostream&
-operator << (ostream &os, LinkedList<T> &list) {
+operator << (ostream &os, LinkedList<T> &list) {
-	Node<T> *p = list.head;
+	Node<T> *p = list.head;
-	os << "{";
+	os << "{";
-	while (p->next != NULL) {
+	while (p->next != NULL) {
-		os << p->value << ", ";
+		os << p->value << ", ";
-		p = p->next;
+		p = p->next;
-	}
+	}
-	os << p->value << "}";
+	os << p->value << "}";
-	return os;
+	return os;
 }
-
+
-template <typename T> istream&
+template <typename T> istream&
-operator >> (istream &is, LinkedList<T> &list) {
+operator >> (istream &is, LinkedList<T> &list) {
-	T val;
+	T val;
-
+
-	is >> val;
+	is >> val;
-
+
-	list.append(val);
+	list.append(val);
-
+
-	return is;
+	return is;
 }
-
+
-/********************/
+/********************/
-/* Member Functions */
+/* Member Functions */
-/********************/
+/********************/
-
+
-template <typename T>
+template <typename T>
-void	LinkedList<T>::prime() {
+void	LinkedList<T>::prime() {
-	if(VERBOSE) {
+	if(VERBOSE) {
-		printf("Created LinkedList at %p.\n", this);
+		printf("Created LinkedList at %p.\n", this);
-	}
+	}
-	this->s = 0;
+	this->s = 0;
-	this->minsize = 0;
+	this->minsize = 0;
-
+
-	this->head = NULL;
+	this->head = NULL;
-	this->tail = NULL;
+	this->tail = NULL;
 }
-
+
-/***** Accessors *****/
+/***** Accessors *****/
-
+
-template <typename T>
+template <typename T>
-int		LinkedList<T>::size() {
+int		LinkedList<T>::size() {
-	return this->s;
+	return this->s;
 }
-
+
-template <typename T>
+template <typename T>
-Node<T>* LinkedList<T>::get(int i) {
+Node<T>* LinkedList<T>::get(int i) {
-	if (i >= this->size()) {
+	if (i >= this->size()) {
-		this->expand(i - this->size() + 1);
+		this->expand(i - this->size() + 1);
-		///
+		///
-		this->tail->used = true;
+		this->tail->used = true;
-	}
+	}
-
+
-	Node<T> *r = this->head;
+	Node<T> *r = this->head;
-	while (i > 0 && r != this->tail) {
+	while (i > 0 && r != this->tail) {
-		r = r->next;
+		r = r->next;
-		i--;
+		i--;
-	}
+	}
-
+
-	return r;
+	return r;
 }
-
+
-/***** Mutators *****/
+/***** Mutators *****/
-
+
-/* Neutral */
+/* Neutral */
-
+
-template <typename T>
+template <typename T>
-Node<T>*	LinkedList<T>::set(T val, int i) {
+Node<T>*	LinkedList<T>::set(T val, int i) {
-	Node<T> *n = this->get(i);
+	Node<T> *n = this->get(i);
-
+
-	n->value = val;
+	n->value = val;
-	n->used = true;
+	n->used = true;
-
+
-	return n;
+	return n;
 }
-
+
-/* Constructive */
+/* Constructive */
-
+
-template <typename T>
+template <typename T>
-int		LinkedList<T>::append(T val) {
+int		LinkedList<T>::append(T val) {
-	return this->append(val, true);
+	return this->append(val, true);
 }
-
+
-template <typename T>
+template <typename T>
-int		LinkedList<T>::append(T val, bool used) {
+int		LinkedList<T>::append(T val, bool used) {
-
+
-	Node<T> *newnode = new Node<T>(val, used);
+	Node<T> *newnode = new Node<T>(val, used);
-
+
-	if(SUPERVERBOSE) {
+	if(SUPERVERBOSE) {
-		printf("Appending value '%d' at %p\n", val, newnode);
+		printf("Appending value '%d' at %p\n", val, newnode);
-	}
+	}
-
+
-	switch (s) {
+	switch (s) {
-		case 0:
+		case 0:
-			this->head = newnode;
+			this->head = newnode;
-			newnode->prev = NULL;
+			newnode->prev = NULL;
-			break;
+			break;
-
+
-		case 1:
+		case 1:
-			this->head->next = newnode;
+			this->head->next = newnode;
-			newnode->prev = this->head;
+			newnode->prev = this->head;
-			break;
+			break;
-
+
-		default:
+		default:
-			this->tail->next = newnode;
+			this->tail->next = newnode;
-			//newnode->prev = this->tail->prev;
+			//newnode->prev = this->tail->prev;
-			newnode->prev = this->get(s - 1);
+			newnode->prev = this->get(s - 1);
-	}
+	}
-
+
-	newnode->next = NULL;
+	newnode->next = NULL;
-	this->tail = newnode;
+	this->tail = newnode;
-
+
-	s++;
+	s++;
-	return 0;
+	return 0;
 }
-
+
-template <typename T>
+template <typename T>
-int		LinkedList<T>::insert(T val, int i) {
+int		LinkedList<T>::insert(T val, int i) {
-	if (s == 0 || s == 1) {
+	if (s == 0 || s == 1) {
-		s++;
+		s++;
-		return this->append(val);
+		return this->append(val);
-	}
+	}
-	return this->insertAfter(val, this->get(i));
+	return this->insertAfter(val, this->get(i));
 }
-
+
-template <typename T>
+template <typename T>
-int		LinkedList<T>::insertAfter(T val, Node<T> *oldnode) {
+int		LinkedList<T>::insertAfter(T val, Node<T> *oldnode) {
-	if (oldnode == this->tail) {
+	if (oldnode == this->tail) {
-		return this->append(val);
+		return this->append(val);
-	}
+	}
-	Node<T> *newnode = new Node<T>(val);
+	Node<T> *newnode = new Node<T>(val);
-
+
-	newnode->prev = oldnode;
+	newnode->prev = oldnode;
-	newnode->next = oldnode->next;
+	newnode->next = oldnode->next;
-
+
-	newnode->next->prev = newnode;
+	newnode->next->prev = newnode;
-	oldnode->next = newnode;
+	oldnode->next = newnode;
-
+
-	s++;
+	s++;
-
+
-	return 0;
+	return 0;
 }
-
+
-template <typename T>
+template <typename T>
-void	LinkedList<T>::expand(int i) {
+void	LinkedList<T>::expand(int i) {
-	while (i > 0) {
+	while (i > 0) {
-		T *n = new T;
+		T *n = new T;
-		this->append(*n, false);
+		this->append(*n, false);
-		i--;
+		i--;
-	}
+	}
 }
-
+
-/* Destructive */
+/* Destructive */
-
+
-template <typename T>
+template <typename T>
-T		LinkedList<T>::trim() {
+T		LinkedList<T>::trim() {
-	return this->delCell(this->size()-1);
+	return this->delCell(this->size()-1);
 }
-
+
-template <typename T>
+template <typename T>
-T		LinkedList<T>::delCell(int i) {
+T		LinkedList<T>::delCell(int i) {
-	Node<T> *del = this->get(i);
+	Node<T> *del = this->get(i);
-
+
-	if (del == this->head) {
+	if (del == this->head) {
-		this->head = del->next;
+		this->head = del->next;
-	} else {
+	} else {
-		del->prev->next = del->next;
+		del->prev->next = del->next;
-	}
+	}
-
+
-	if (del == this->tail) {
+	if (del == this->tail) {
-		this->tail = del->prev;
+		this->tail = del->prev;
-	} else {
+	} else {
-		del->next->prev = del->prev;
+		del->next->prev = del->prev;
-	}
+	}
-
+
-	int r = this->destroy(del);
+	int r = this->destroy(del);
-
+
-	if (s == 1) {
+	if (s == 1) {
-		this->tail = this->head;
+		this->tail = this->head;
-	}
+	}
-
+
-	if(this->s != 0 && !this->tail->used) {
+	if(this->s != 0 && !this->tail->used) {
-		this->trimEmpty();
+		this->trimEmpty();
-	}
+	}
-
+
-	return r;
+	return r;
 }
-
+
-template <typename T>
+template <typename T>
-T		LinkedList<T>::destroy(Node<T> *n) {
+T		LinkedList<T>::destroy(Node<T> *n) {
-	T r = n->value;
+	T r = n->value;
-	delete n;
+	delete n;
-	s--;
+	s--;
-
+
-	if(SUPERVERBOSE) {
+	if(SUPERVERBOSE) {
-		printf("Value '%d' at %p destroyed\n", r, n);
+		printf("Value '%d' at %p destroyed\n", r, n);
-	}
+	}
-
+
-	return r;
+	return r;
 }
-
+
-template <typename T>
+template <typename T>
-void	LinkedList<T>::trimEmpty() {
+void	LinkedList<T>::trimEmpty() {
-	Node<T> *n = this->tail;
+	Node<T> *n = this->tail;
-
+
-	while (this->s > this->minsize && this->s > 1 && !n->used ) {
+	while (this->s > this->minsize && this->s > 1 && !n->used ) {
-
+
-		n->prev->next = n->next;
+		n->prev->next = n->next;
-		this->tail = n->prev;
+		this->tail = n->prev;
-
+
-		this->destroy(n);
+		this->destroy(n);
-
+
-		n = this->tail;
+		n = this->tail;
-	}
+	}
-
+
-	if (this->s == 1 && !n->used) {
+	if (this->s == 1 && !n->used) {
-		this->head = NULL;
+		this->head = NULL;
-		this->tail = NULL;
+		this->tail = NULL;
-		destroy(n);
+		destroy(n);
-	}
+	}
 }
-
+
-template <typename T>
+template <typename T>
-void	LinkedList<T>::print() {
+void	LinkedList<T>::print() {
-	cout << *this;
+	cout << *this;
 }