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