LinkedList<T>

/*
 *  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;
}