<file_sep>CXX=/usr/bin/clang++
INCLUDE_DIRS=include ../include ./include
INCDIR=include
TESTDIR=test
CXXFLAGS=-I$(INCDIR) -std=c++11
TESTFILES=$(shell find $(TESTDIR) -name '*.cpp')
OBJFILES=$(patsubst test/%.cpp,bin/%.o,$(TESTFILES))
EXECS=$(patsubst test/%.cpp,bin/%,$(TESTFILES))
TEST_TARGETS=$(patsubst bin/%,%,$(EXECS))
PREV_BUILD=$(shell find ./.prev 2>/dev/null | xargs cat)

.PHONY: Makefile all include src lib README.md bin test tests check-syntax

.SUFFIXES: .cpp

all:
	@echo Available targets:
	@echo  - test: build all test targets
	@echo  - [target]: build and run specified target

test: $(EXECS)
	@echo $(EXECS) > ./.prev

tests: test

bin/%.o: test/%.cpp
	$(CXX) $(CXXFLAGS) -c $< -o $@

bin/%: bin/%.o
	$(CXX) $(CXXFLAGS) $< -o $@

$(TEST_TARGETS):
	$(eval OUTFILE=$(patsubst %,bin/%,$@) )
	$(CXX) $(CXXFLAGS) $(patsubst %,test/%.cpp,$@) -o $(OUTFILE)
	@echo $(OUTFILE) > ./.prev
	@echo Running $(OUTFILE)
	@$(OUTFILE)

clean:
	rm -f $(EXECS)
	rm -f $(OBJFILES)
	@clean $(INCDIR) $(TESTDIR)

redo: clean $(PREV_BUILD)

check-syntax:
	$(CXX) $(CXXFLAGS) -Wall -Wextra -fsyntax-only $(CHK_SOURCES)

dumpvars:
	@echo $(foreach var, ${DUMPVARS}, "\n$(var)=$($(var))")
<file_sep>#ifndef _MPH_DOUBLE_LIST_H_
#define _MPH_DOUBLE_LIST_H_

#include <iostream>

#include "node.hpp"

template <typename T>
class DoubleList {
public:
  Node<T> * fwalk(Node<T> * start, int dist) const;
  Node<T> * rwalk(Node<T> * start, int dist) const;
  Node<T> * head;
  Node<T> * tail;
public:
  DoubleList();
  DoubleList(T data);
  DoubleList(T * data, int len);
  DoubleList(DoubleList<T> * dl);
  ~DoubleList();
  Node<T> * begin() const { return this->head; }
  Node<T> * end() const { return this->tail; }
  T insert(int pos, T data) { return this->add(pos, data); }
  T add(int pos, T data);
  T remove(int pos);
  T prepend(T data);
  T append(T data);
  void clear();
  T at(int pos) const;
  T get(int pos) const;
  T set(int pos, T data);
  int size() const;
};

template <typename T>
DoubleList<T>::DoubleList(DoubleList<T> * dl) {
  for (int i = 0; i < dl->size(); i++) {
    this->append(dl->at(i));
  }
}

template <typename T>
Node<T> * DoubleList<T>::fwalk(Node<T> * start, int dist) const {
  Node<T> * tmp = start;
  for (int i = 0; i < dist; i++) {
    tmp = tmp->next;
    if (tmp->next == NULL) { return tmp; }
  }
  return tmp;
}

template <typename T>
Node<T> * DoubleList<T>::rwalk(Node<T> * start, int dist) const {
  Node<T> * tmp = start;
  for (int i = 0; i < dist; i++) {
    tmp = tmp->prev;
    if (tmp->prev == NULL) { return tmp; }
  }
  return tmp;
}

template <typename T>
DoubleList<T>::DoubleList() {
  this->head = NULL;
  this->tail = NULL;
}

template <typename T>
DoubleList<T>::DoubleList(T data) {
  this->head = new Node<T>(data, NULL, NULL);
  this->tail = this->head;
}

template <typename T>
DoubleList<T>::DoubleList(T * data, int len) {
  for (int i = 0; i < len; i++) {
    this->append(*(data + i));
  }
}

template <typename T>
DoubleList<T>::~DoubleList() {
  this->clear();
}

template <typename T>
T DoubleList<T>::add(int pos, T data) {
  if (pos > this->size()) { this->append(data); return data; }
  if (pos < 0) { this->prepend(data); return data; }
  Node<T> * tmp = fwalk(head, pos);
  Node<T> * new_node = new Node<T>(data, tmp->prev, tmp);
  tmp->prev = new_node;
  new_node->prev->next = new_node;
  return data;
}

template <typename T>
T DoubleList<T>::remove(int pos) {
  Node<T> * tmp = fwalk(head, pos);
  if (tmp != this->head) {
    tmp->prev->next = tmp->next;
  } else {
    this->head = tmp->next;
  }
  if (tmp != this->tail) {
    tmp->next->prev = tmp->prev;
  } else {
    this->tail = tmp->prev;
  }
  T data = tmp->data;
  delete tmp;
  return data;
}

template <typename T>
T DoubleList<T>::append(T data) {
  Node<T> * tmp = new Node<T>(data, this->tail, NULL);
  this->tail = tmp;
  if (this->head == NULL) {
    this->head = tmp;
  } else {
    tmp->prev->next = tmp;
  }
  return data;
}

template <typename T>
T DoubleList<T>::prepend(T data) {
  Node<T> * tmp = new Node<T>(data, NULL, this->head);
  this->head = tmp;
  if (this->tail == NULL) {
    this->tail = tmp;
  } else {
    tmp->next->prev = tmp;
  }
  return data;
}

template <typename T>
void DoubleList<T>::clear() {
  Node<T> * tmp;
  while (head != NULL) {
    tmp = head;
    head = tmp->next;
    delete tmp;
  }
  tail = head;
}

template <typename T>
T DoubleList<T>::at(int pos) const {
  if (pos < 0) { return (T)(NULL); }
  return fwalk(head, pos)->data;
}

template <typename T>
T DoubleList<T>::get(int pos) const {
  if (pos < 0) { return (T)(NULL); }
  return fwalk(head, pos)->data;
}

template <typename T>
T DoubleList<T>::set(int pos, T data) {
  Node<T> * tmp = fwalk(head, pos);
  tmp->data = data;
  return data;
}

template <typename T>
int DoubleList<T>::size() const {
  if (head == NULL) { return 0; }
  else if (head == tail) { return 1; }
  else if (head->next == tail) { return 2; }
  else {
    Node<T> * tmp = head;
    int count = 1;
    while (tmp->next != NULL) {
      tmp = tmp->next;
      count++;
    }
    return count;
  }
}

template<typename T>
std::ostream & operator<<(std::ostream & out, const DoubleList<T> & l) {
  Node<T> * tmp = l.begin();
  if (tmp == NULL) {
    out << "< empty >";
    return out;
  }
  while (tmp != l.end()) {
    out << tmp->data << " <-> ";
    tmp = tmp->next;
  }
  out << l.end()->data;
  return out;
}

template<typename T>
std::istream & operator>>(std::istream & in, DoubleList<T> & l) {
  T tmp;
  in >> tmp;
  l.append(tmp);
  return in;
}

#endif
<file_sep>#ifndef _MPH_HASH_H_
#define _MPH_HASH_H_

#include <cmath>

#include <vector.hpp>
#include <list.hpp>

namespace hash_functions {
  int knuth_div_hash(long k, int n) {
    return (k * (k + 3) ) % n;
  }

  int mod_hash(long k, int n) {
    return k % n;
  }
  
  int mult_hash(long k, int n) {
    float A = 0.5 * (sqrt(5) - 1);
    int s = floor(A * pow(2, 32));
    int x = k * s;
    return x >> (32 - 16);
  }

  int knuth_mult_hash(long k, int n) {
    return (k * 2654435761) >> (32 - (int)floor(log2(n)));
  }

  int basic_hash(long k, int n) {
    return knuth_mult_hash(k, n);
  }
};

template <typename T>
class HashTable {
private:
  int blocks;
  int (*hash_function)(long, int);
  Vector<List<T> > * contents;
public:
  HashTable();
  HashTable(int n);
  HashTable(int (*func)(int, int));
  HashTable(int (*func)(int, int), int n);
  ~HashTable();
  int size() const { return blocks; }
  int block_length(int block) const { return contents->at(block).size(); }
  int insert(T data);
  List<T> * const get_block(int block);
  T find(T data);
};

template <typename T> using Hash = HashTable<T>;

template <typename T>
HashTable<T>::HashTable() {
  hash_function = hash_functions::basic_hash;
  blocks = 100;
  contents = new Vector<List<T> >(blocks);
}

template <typename T>
HashTable<T>::HashTable(int s) {
  hash_function = hash_functions::basic_hash;
  blocks = s;
  contents = new Vector<List<T> >(blocks);
}

template <typename T>
HashTable<T>::HashTable(int (*func)(int, int)) {
  hash_function = func;
  blocks = 100;
  contents = new Vector<List<T> >(blocks);
}
  
template <typename T>
HashTable<T>::HashTable(int (*func)(int, int), int n) {
  hash_function = func;
  blocks = n;
  contents = new Vector<List<T> >(blocks);
}

template <typename T>
HashTable<T>::~HashTable() {
  delete contents;
}

template <typename T>
int HashTable<T>::insert(T data) {
  int k = hash_function((long)(data), size);
  contents->at(k).append(data);
  return k;
}

template <typename T>
List<T> * const HashTable<T>::get_block(int block) {
  return contents->at(block);
}

template <typename T>
T HashTable<T>::find(T data) {
  int k = hash_function((long)(data), size);
  
  return
}

#endif
<file_sep>#ifndef _MPH_QUEUE_H_
#define _MPH_QUEUE_H_

#include <list.hpp>

template <typename T>
class Queue {
private:
  List<T> contents;
  const int size;
public:
  Queue() : size(0) { };
  Queue(int s) : size(s) { };
  Queue(List<T> data) : size(data.size()) { };
  Queue(Queue<T> q) : size(q.size()); { };
  Queue(List<T> data, int s) : size(s > data.size() ? s : data.size()) { };
  Queue(Queue<T> data, int s) : size(s > data.length() ? s : data.size()) { };
  ~Queue() { };
  const int size() const { return size; }
  int length() const { return contents.size() };
  bool is_empty() const { return this->length() == 0; }
  bool is_full() const { size == 0 ? return false : return this->length() == this->size(); }
  T peek() const { return contents.get(contents.size()); }
  T pop();
  bool push(T data);
};

template <typename T>
T Queue<T>::pop() {
  if (is_empty()) {
    return (T)(0);
  }
  T data = contents.at(0);
  contents.remove(0);
  return data;
}

template <typename T>
bool Queue<T>::push(T data) {
  if (is_full()) {
    return false;
  }
  contents.append(data);
  return true;
}

#endif
<file_sep>#ifndef _MPH_LINKLIST_H_
#define _MPH_LINKLIST_H_
#include <iostream>

#include "node.hpp"

template <typename T>
class LinkList {
private:
  Node<T> * head;
  Node<T> * tail;
  Node<T> * walk(Node<T> * start, int pos) const;
public:
  LinkList();
  LinkList(T data);
  LinkList(T * data, int len);
  LinkList(LinkList<T> * dl);
  ~LinkList();
  Node<T> * begin() const { return head; }
  Node<T> * end() const { return tail; }
  T add(int pos, T data);
  T remove(int pos);
  T prepend(T data);
  T append(T data);
  T at(int pos) const;
  T get(int pos) const;
  T set(int pos, T data);
  void clear();
  int size() const;
};

template <typename T>
LinkList<T>::LinkList(LinkList<T> * dl) {
  for (int i = 0; i < dl->size(); i++) {
    this->append(dl->at(i));
  }
}

template <typename T>
Node<T> * LinkList<T>::walk(Node<T> * start, int pos) const {
  Node<T> * tmp = start;
  for (int i = 0; i < pos; i++) {
    tmp = tmp->next;
    if (tmp->next == NULL) { return tmp; }
  }
  return tmp;
}

template <typename T>
LinkList<T>::LinkList() {
  head = NULL;
  tail = NULL;
}

template <typename T>
LinkList<T>::LinkList(T data) {
  head = new Node<T>(data, NULL);
  tail = head;
}

template <typename T>
LinkList<T>::LinkList(T * data, int len) {
  for (int i = 0; i < len; i++) {
    this->append(*(data + i));
  }
}

template <typename T>
LinkList<T>::~LinkList() {
  this->clear();
}

template <typename T>
T LinkList<T>::add(int pos, T data) {
  Node<T> * tmp = walk(head, pos);
  Node<T> * new_node = new Node<T>(data, tmp);
  walk(head, pos - 1)->next = new_node;
  return data;
}

template <typename T>
T LinkList<T>::remove(int pos) {
  Node<T> * tmp = walk(head, pos);
  if (tmp == head) {
    head = head->next;
  } else if (tmp == tail) {
    tail = walk(head, pos - 1);
    tail->next = NULL;
  } else {
    walk(head, pos - 1)->next = walk(tmp, 1);
  }
  T data = tmp->data;
  delete tmp;
  return data;
}

template <typename T>
T LinkList<T>::prepend(T data) {
  Node<T> * tmp = new Node<T>(data, NULL);
  tmp->next = head;
  head = tmp;
  return data;
}

template <typename T>
T LinkList<T>::append(T data) {
  Node<T> * tmp = new Node<T>(data, NULL);
  tail->next = tmp;
  tail = tmp;
  return data;
}

template <typename T>
T LinkList<T>::at(int pos) const {
  if (pos < 0) { return NULL; }
  return walk(head, pos)->data;
}

template <typename T>
T LinkList<T>::get(int pos) const {
  if (pos < 0) { return NULL; }
  return walk(head, pos)->data;
}

template <typename T>
T LinkList<T>::set(int pos, T data) {
  Node<T> * tmp = walk(head, pos);
  tmp->data = data;
  return data;
}

template <typename T>
void LinkList<T>::clear() {
  Node<T> * tmp;
  while (head != NULL) {
    tmp = head;
    head = tmp->next;
    delete tmp;
  }
  tail = head;
}

template <typename T>
int LinkList<T>::size() const {
  if (head == NULL) { return 0; }
  else if (head == tail) { return 1; }
  else if (head->next == tail) { return 2; }
  else {
    Node<T> * tmp = head;
    int count = 1;
    while (tmp->next != NULL) {
      tmp = tmp->next;
      count++;
    }
    return count;
  }
}

template<typename T>
std::ostream & operator<<(std::ostream & out, const LinkList<T> & l) {
  Node<T> * tmp = l.begin();
  if (tmp == NULL) {
    out << "< empty >";
    return out;
  }
  while (tmp != l.end()) {
    out << tmp->data << " -> ";
    tmp = tmp->next;
  }
  out << l.end()->data;
  return out;
}

template<typename T>
std::istream & operator>>(std::istream & in, LinkList<T> & l) {
  T tmp;
  in >> tmp;
  l.append(tmp);
  return in;
}

#endif
<file_sep>#ifndef _MPH_STATIC_ARRAY_BAG_H_
#define _MPH_STATIC_ARRAY_BAG_H_

#include <iostream>

template <typename T>
class StaticArrayBag {
private:
  int maxItems;
  int itemCount;
  T * contents;
public:
  StaticArrayBag();
  StaticArrayBag(int size);
  StaticArrayBag(int size, T * data, int len);
  ~StaticArrayBag();
  int size() const { return itemCount; }
  bool isEmpty() const { return itemCount == 0; }
  bool isFull() const { return itemCount == maxItems; }
  bool insert(const T & newEntry);
  bool add(const T & newEntry) { return this->insert(newEntry); }
  bool remove(const T & toDelete);
  int contains(const T & data) const;
  template <typename U>
  friend std::ostream & operator<<(std::ostream & out, StaticArrayBag<U> & b);
  template <typename U>
  friend std::istream & operator>>(std::istream & in, StaticArrayBag<U> & b);
};

template <typename T>
StaticArrayBag<T>::StaticArrayBag() {
  maxItems = 10;
  itemCount = 0;
  contents = new T[maxItems];
}

template <typename T>
StaticArrayBag<T>::StaticArrayBag(int size) {
  itemCount = 0;
  if (size <= 0) {
    maxItems = 10;
  } else {
    maxItems = size;
  }
  contents = new T[maxItems];
}

template <typename T>
StaticArrayBag<T>::StaticArrayBag(int size, T * data, int len) {
  itemCount = 0;
  if (size <= 0) {
    maxItems = 10;
  } else {
    maxItems = size;
  }
  contents = new T[maxItems];
  for (int i = 0; i < len; i++) {
    this->insert(data[i]);
  }
}

template <typename T>
StaticArrayBag<T>::~StaticArrayBag() {
  delete [] contents;
}

template <typename T>
bool StaticArrayBag<T>::insert(const T & newEntry) {
  if (itemCount >= maxItems) {
    return false;
  }
  contents[itemCount] = newEntry;
  itemCount++;
  return true;
}

template<typename T>
std::istream & operator>>(std::istream & in, StaticArrayBag<T> & b) {
  T tmp;
  in >> tmp;
  b.add(tmp);
  return in;
}

template <typename T>
std::ostream & operator<<(std::ostream & out, StaticArrayBag<T> & b) {
  for (int i = 0; i < b.size() - 1; i++) {
    out << b.contents[i] << ", ";
  }
  out << b.contents[b.size() - 1];
  return out;
}

#endif
<file_sep>#ifndef _MPH_MAP_H_
#define _MPH_MAP_H_



#endif
<file_sep>#include <bag.hpp>
#include <iostream>
using namespace std;

void show_ptrs_fwd(const List<double> * ll) {
  Node<double> * tmp = ll->begin();
  cout << "Forward:  ";
  while (tmp != NULL) {
    cout << tmp << " ";
    tmp = tmp->next;
  }
  cout << endl;
}

void show_ptrs_bwd(const List<double> * ll) {
  Node<double> * tmp = ll->end();
  cout << "Backward: ";
  while (tmp != NULL) {
    cout << tmp << " ";
    tmp = tmp->prev;
  }
  cout << endl;
}

int main() {
  LinkListBag<double> b(5);
  const List<double> * c = b.get_contents();
  b.add(5.5);
  b.add(3);
  b.add(4);
  b.add(3);
  cout << b << endl;
  show_ptrs_fwd(c);
  show_ptrs_bwd(c);
  cout << *c << endl;
  b.remove(3);
  show_ptrs_fwd(c);
  show_ptrs_bwd(c);
  cout << *c << endl;
  b.remove(3);
  show_ptrs_fwd(c);
  show_ptrs_bwd(c);
  cout << *c << endl;
  b.remove(5.5);
  show_ptrs_fwd(c);
  show_ptrs_bwd(c);
  cout << *c << endl;
  b.remove(4);
  show_ptrs_fwd(c);
  show_ptrs_bwd(c);
  cout << *c << endl;
  b.remove(5.5);
  show_ptrs_fwd(c);
  show_ptrs_bwd(c);
  cout << *c << endl;

  StaticArrayBag<double> dB(4);
  for (int i = 0; i < 1000; i++) {
    dB.insert(i);
    if (dB.isFull()) {
      cout << "Expanding!" << endl;
    }
  }
  cout << dB << endl;
  return 0;
}
<file_sep>/*
  bag.hpp
 */
#ifndef _MPH_LL_BAG_H_
#define _MPH_LL_BAG_H_

#include <iostream>
using namespace std;

#include <list.hpp>

// Specification

template <typename T>
class LinkListBag {
private:
  const int BAG_SIZE;
  List<T> contents;
public:
  LinkListBag(int size) : BAG_SIZE(size) { }
  ~LinkListBag() { }
  const List<T> * get_contents() const { return &contents; }
  bool isEmpty() const;
  bool isFull() const;
  int contains(T data) const;
  const int size() const { return contents.size(); };
  const int capacity() const { return BAG_SIZE; };
  bool add(T data);
  bool remove(T data);
  template <typename U>
  friend std::ostream & operator<<(std::ostream & out, LinkListBag<U> & b);
  template <typename U>
  friend std::istream & operator>>(std::istream & in, LinkListBag<U> & b);
};

// Implementation

template <typename T>
bool LinkListBag<T>::isEmpty() const {
  return (size() == 0);
}

template <typename T>
bool LinkListBag<T>::isFull() const {
  return (size() == capacity());
}

template <typename T>
int LinkListBag<T>::contains(T data) const {
  int n = 0;
  for (int i = 0; i < this->size(); i++) {
    if (contents.at(i) == data) {
      n++;
    }
  }
  return n;
}

template <typename T>
bool LinkListBag<T>::add(T data) {
  if (size() < capacity()) {
    contents.append(data);
    return true;
  } else {
    return false;
  }
}

template <typename T>
bool LinkListBag<T>::remove(T data) {
  for (int i = 0; i < this->size(); i++) {
    if (contents.at(i) == data) {
      contents.remove(i);
      return true;
    }
  }
  return false;
}

template<typename T>
std::istream & operator>>(std::istream & in, LinkListBag<T> & b) {
  T tmp;
  in >> tmp;
  b.add(tmp);
  return in;
}

template <typename T>
std::ostream & operator<<(std::ostream & out, LinkListBag<T> & b) {
  if (b.isEmpty()) {
    out << "< empty >";
    return out;
  }
  for (int i = 0; i < b.size() - 1; i++) {
    out << b.contents.at(i) << ", ";
  }
  out << b.contents.at(b.size() - 1);
  return out;
}

#endif
<file_sep>#ifndef _MPH_NODE_H
#define _MPH_NODE_H

#ifndef NULL
#define NULL 0
#endif

template <typename T>
class Node {
public:
  T data;
  Node<T> * next;
  Node<T> * prev;
  Node(T d, Node<T> * n) {
    data = d;
    next = n;
    prev = NULL;
  }
  Node(T d, Node<T> * p, Node<T> * n) {
    data = d;
    next = n;
    prev = p;
  }
};

#endif
<file_sep>#ifndef _MPH_WRAPPER_QUEUE_H_
#define _MPH_WRAPPER_QUEUE_H_

#include <queue/queue.hpp>
#include <queue/deque.hpp>

template <typename T> using DoubleQueue = Deque<T>;

#endif
<file_sep>#ifndef _MPH_BAG_H_
#define _MPH_BAG_H_

#include <bags/static_array_bag.hpp>
#include <bags/dynamic_array_bag.hpp>
#include <bags/ll_bag.hpp>

template <typename T> using Bag = LinkListBag<T>;

#endif
<file_sep>#ifndef _MPH_WRAPPER_DEQUE_H_
#define _MPH_WRAPPER_DEQUE_H_

#include <queue.hpp>

#endif
<file_sep>#include <stack.hpp>
#include <iostream>
using namespace std;

int main() {
  cout << "Compiles!" << endl;
  Stack<int> s;
  s.push(4);
  s.push(5);
  s.pop();
  cout << s << endl;
  int data[7] = {1, 4, 5, 8, 6, 5, 10};
  s.push(data, 7);
  cout << s << endl;
  return 0;
}
<file_sep>Dacilndak/ds
============

A bunch of data structures made for CSCI2270.  Use the Makefile.<file_sep>#include <hash.hpp>

int main() {
  Hash<int> h;
  return 0;
}
<file_sep>#ifndef _MPH_LIST_H_
#define _MPH_LIST_H_

#include <list/node.hpp>
#include <list/linklist.hpp>
#include <list/doublelist.hpp>

template <typename T> using List = DoubleList<T>;

#endif
<file_sep>#ifndef _MPH_STACK_H_
#define _MPH_STACK_H_

#include <list.hpp>

#ifndef NULL
#define NULL 0
#endif

template <typename T>
class Stack {
private:
  List<T> contents;
public:
  Stack() : contents() { }
  Stack(T data) : contents(data) { }
  Stack(T * data, int len) : contents(data, len) { }
  T pop();
  T push(T data);
  T * push(T * data, int len);
  int size() const { return this->contents.size(); }
  template <typename U>
  friend std::ostream & operator<<(std::ostream & out, const Stack<U> & s);
  template <typename U>
  friend std::istream & operator>>(std::istream & out, Stack<U> & s);
};

template <typename T>
T Stack<T>::pop() {
  if (this->contents.size() == 0) {
    return (T)(NULL);
  }
  T temp = this->contents.at(this->contents.size());
  this->contents.remove(this->contents.size());
  return temp;
}

template <typename T>
T Stack<T>::push(T data) {
  this->contents.append(data);
  return data;
}

template <typename T>
T * Stack<T>::push(T * data, int len) {
  for (int i = 0; i < len; i++) {
    this->contents.append(data[i]);
  }
  return data;
}

template<typename T>
std::ostream & operator<<(std::ostream & out, const Stack<T> & s) {
  out << s.contents;
  return out;
}

template<typename T>
std::istream & operator>>(std::istream & in, Stack<T> & s) {
  T input;
  in >> input;
  s.push(input);
  return in;
}

#endif
<file_sep>#ifndef _MPH_VECTOR_H_
#define _MPH_VECTOR_H_

template <typename T>
class Vector {
private:
  int size;
  T * contents;
public:
  Vector();
  Vector(int size);
  Vector(int size, T * data, int len);
  ~Vector();
  bool insert(const T & newEntry, int index);
  bool append(const T & data);
  T & operator[](int index) { return this->at(index); }
  T & at(int index);
  int length() const { return size; }
};

template <typename T>
Vector<T>::Vector() {
  size = 0;
  contents = nullptr;
}

template <typename T>
Vector<T>::Vector(int s) {
  size = s;
  contents = new T[size];
}

template <typename T>
Vector<T>::Vector(int s, T * data, int len) {
  size = s > len ? s : len;
  contents = new T[size];
  for (int i = 0; i < len; i++) {
    contents[i] = data[i];
  }
}

template <typename T>
Vector<T>::~Vector() {
  if (contents != nullptr) {
    delete [] contents;
  }
}

template <typename T>
bool Vector<T>::insert(const T & newEntry, int index) {
  size += 1;
  T * tmp = realloc(contents, size);
  if (tmp == nullptr) {
    return false;
  }
  contents = tmp;
  for (int i = size - 1; i > index; i--) {
    contents[i] = contents[i - 1];
  }
  contents[index] = newEntry;
  return true;
}

template <typename T>
bool Vector<T>::append(const T & data) {
  size += 1;
  T * tmp = realloc(contents, size);
  if (tmp == nullptr) {
    return false;
  }
  contents = tmp;
  contents[size - 1] = data;
  return true;
}

template <typename T>
T & Vector<T>::at(int index) {
  return contents[index];
}

#endif
<file_sep>#ifndef _MPH_DEQUE_H_
#define _MPH_DEQUE_H_

template <typename T>
class DoubleQueue {
private:
  List<T> contents;
  const int size;
public:
  DoubleQueue() : size(0) { };
  DoubleQueue(int s) : size(s) { };
  DoubleQueue(List<T> data) : size(data.size()) { };
  DoubleQueue(DoubleQueue<T> q) : size(q.size()) { };
  DoubleQueue(List<T> data, int s) : size(s > data.size() ? s : data.size()) { };
  DoubleQueue(DoubleQueue<T> data, int s) : size(s > data.length() ? s : data.size()) { };
  ~DoubleQueue() { };
  const int capacity() const { return size; }
  const int size() const { return size; }
  int length() const { return contents.size(); };
  bool is_empty() const { return this->length() == 0; }
  bool is_full() const { size == 0 ? return false : return this->length() >= this->size(); }
  T peek_front() const { return contents.get(0); }
  T peek_back() const { return contents.get(contents.size()); }
  T pop_front();
  T pop_back();
  bool push_front(T data);
  bool push_back(T data);
};

template <typename T>
T DoubleQueue<T>::pop_front() {
  if (is_empty()) {
    return (T)(0);
  }
  T data = contents.at(0);
  contents.remove(0);
  return data;
}

template <typename T>
T DoubleQueue<T>::pop_back() {
  if (is_empty()) {
    return (T)(0);
  }
  T data = contents.at(contents.size());
  contents.remove(contents.size());
  return data;
}

template <typename T>
bool DoubleQueue<T>::push_front(T data) {
  if (is_full()) {
    return false;
  }
  contents.prepend(data);
  return true;
}

template <typename T>
bool DoubleQueue<T>::push_back(T data) {
  if (is_full()) {
    return false;
  }
  contents.append(data);
  return true;
}

#endif
<file_sep>#include <list.hpp>
#include <iostream>
using namespace std;

void show_ptrs(List<int> * ll) {
  Node<int> * tmp = ll->begin();
  while (tmp != NULL) {
    cout << "Address: " << tmp << endl;
    tmp = tmp->next;
  }
}

int main() {
  int nums[4] = { 1, 2, 3, 4 };
  List<int> x(nums, 4);
  cout << "Made list" << endl;
  show_ptrs(&x);
  x.append(20);
  cout << endl << "Appended" << endl;
  show_ptrs(&x);
  x.prepend(10);
  cout << endl << "Prepended" << endl;
  show_ptrs(&x);
  x.remove(1);
  cout << endl << "Removed" << endl;
  show_ptrs(&x);
  x.add(1, 20);
  x.add(2, 50);
  cout << endl << "Added" << endl;
  show_ptrs(&x);
  cout << "Size: " << x.size() << endl;
  cout << x;
  x.clear();
  cout << endl << "Cleared" << endl;
  show_ptrs(&x);
  cout << x << endl;
  cout << "Size: " << x.size() << endl;
  cout << endl << "Destructor" << endl;
  return 0;
}
<file_sep>#ifndef _MPH_ARRAY_BAG_H_
#define _MPH_ARRAY_BAG_H_

#include <iostream>

template <typename T>
class DynamicArrayBag {
private:
  int maxItems;
  int itemCount;
  T * contents;
public:
  DynamicArrayBag();
  DynamicArrayBag(int size);
  DynamicArrayBag(int size, T * data, int len);
  ~DynamicArrayBag();
  bool insert(const T & newEntry);
  bool add(const T & newEntry) { return this->insert(newEntry); }
  bool remove(const T & toDelete);
  int contains(const T & data) const;
  int size() const { return itemCount; }
  bool isEmpty() const { return itemCount == 0; }
  bool isFull() const { return itemCount == maxItems; }
  template <typename U>
  friend std::ostream & operator<<(std::ostream & out, DynamicArrayBag<U> & b);
  template <typename U>
  friend std::istream & operator>>(std::istream & in, DynamicArrayBag<U> & b);
};

template <typename T>
DynamicArrayBag<T>::DynamicArrayBag() {
  maxItems = 10;
  itemCount = 0;
  contents = new T[maxItems];
}

template <typename T>
DynamicArrayBag<T>::DynamicArrayBag(int size) {
  itemCount = 0;
  if (size <= 0) {
    maxItems = 10;
  } else {
    maxItems = size;
  }
  contents = new T[maxItems];
}

template <typename T>
DynamicArrayBag<T>::DynamicArrayBag(int size, T * data, int len) {
  itemCount = 0;
  if (size <= 0) {
    maxItems = 10;
  } else {
    maxItems = size;
  }
  contents = new T[maxItems];
  for (int i = 0; i < len; i++) {
    this->insert(data[i]);
  }
}

template <typename T>
DynamicArrayBag<T>::~DynamicArrayBag() {
  delete [] contents;
}

template <typename T>
bool DynamicArrayBag<T>::insert(const T & newEntry) {
  if (itemCount >= maxItems) {
    T * oldArray = contents;
    contents = new T[2 * maxItems];
    for (int i = 0; i < maxItems; i++) {
      contents[i] = oldArray[i];
    }
    delete [] oldArray;
    maxItems *= 2;
  }
  contents[itemCount] = newEntry;
  itemCount++;
  return true;
}

template <typename T>
bool DynamicArrayBag<T>::remove(const T & toDelete) {
  for (int i = 0; i < itemCount; i++) {
    if (contents[i] == toDelete) {
      for (int j = i + 1; j < itemCount; j++) {
	contents[j - 1] = contents[j];
      }
      itemCount--;
      return true;
    }
  }
  return false;
}

template <typename T>
int DynamicArrayBag<T>::contains(const T & data) const {
  int n = 0;
  for (int i = 0; i < itemCount; i++) {
    if (contents[i] == data) {
      n++;
    }
  }
  return n;
}

template<typename T>
std::istream & operator>>(std::istream & in, DynamicArrayBag<T> & b) {
  T tmp;
  in >> tmp;
  b.add(tmp);
  return in;
}

template <typename T>
std::ostream & operator<<(std::ostream & out, DynamicArrayBag<T> & b) {
  for (int i = 0; i < b.size() - 1; i++) {
    out << b.contents[i] << ", ";
  }
  out << b.contents[b.size() - 1];
  return out;
}

#endif
