#include <iostream>


// -----------------------------------------------------------------
//   ListNode Class
// ------------------------------------------------------------------
class ListNode {
private:
  void *data;
  ListNode *next;
  ListNode *prev;

public:
  ListNode(void *, ListNode *); 
  void *getData();
  ListNode *getNext();
  void setNext(ListNode *);
};

ListNode::ListNode(void *d, ListNode *n) {
  data = d;
  next = n;
}

void * 
ListNode::getData() {
  return data;
}

ListNode *
ListNode::getNext() {
  return next;
}

void
ListNode::setNext(ListNode *n) {
  next = n;
}



// -----------------------------------------------------------------
//  List Class
// -----------------------------------------------------------------
class List {
private:
  ListNode *head;
  int nitems;

public:
  bool ins(void *);
  bool del(void *);
  bool empty();
  List(); 
};


List::List() {
    nitems = 0;
    head = NULL;
}

bool
List::empty() {
  return nitems == 0;
}

bool
List::ins(void *data) {
  ListNode *node = new ListNode(data, head);
  head = node;
  nitems++;
  return true;
}


bool
List::del(void *data) {

  ListNode *curr = head;
  ListNode *before = 0;

  while(curr != NULL && data != curr->getData()) {
    before = curr;
    curr = curr->getNext();
  }
  if (curr == NULL) {
    cout << "Error: " << data << " not in list" << endl;
    return false; // item not in list
  }
  if (before == NULL) {  // if curr is the head
    head = curr->getNext();
  } else {
    before->setNext(curr->getNext());
  }
  delete curr;
  nitems--;
  return true;
}


void main(int argc, char * argv[]) {
  List * llist = new List();
  int last;

  cout << "Testing C++ linked list class." << endl;
  for(int i = 0; i < 20; i++) {
    cout << "Inserting " << i << endl;
    llist->ins((void *) i);
  }

  for(int i = 0; i < 20; i++) {
    if (llist->del((void *) i)) {
      cout << "Removed " << i << endl;
    }
  }
  /* delete a bogus item.  */
  llist->del((void *) 21);
}