initial commitHEADmaster

8 files changed, 448 insertions, 0 deletions

diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..25a36a1
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,30 @@
+PROG = collection
+OBJS = main.o collection.o linkedlist.o variablearray.o
+CC = g++
+DBGFLAGS = -g -O0
+ifdef DEBUG
+    CFLAGS = $(DBGFLAGS) -D DEBUG -std=c++98 -pedantic-errors -Wall
+else
+    CFLAGS = -O2 -std=c++98 -Wall
+endif
+LDFLAGS = -lm
+
+$(PROG): $(OBJS)
+	$(CC) $(LDFLAGS) $(OBJS) -o $@
+
+main.o: %.o: %.cpp collection.h linkedlist.h
+	$(CC) -c $(CFLAGS) $<
+
+collection.o: %.o: %.cpp %.h
+	$(CC) -c $(CFLAGS) $<
+
+linkedlist.o: %.o: %.cpp %.h collection.h
+	$(CC) -c $(CFLAGS) $<
+
+variablearray.o: %.o: %.cpp %.h collection.h
+	$(CC) -c $(CFLAGS) $<
+
+.PHONY: clean
+
+clean:
+	@rm -f ./$(OBJS) ./$(PROG)
diff --git a/collection.cpp b/collection.cpp
new file mode 100644
index 0000000..4da55a2
--- /dev/null
+++ b/collection.cpp
@@ -0,0 +1,16 @@
+#include "collection.h"
+
+int Collection::get_size(void) const
+{
+    return this->size_;
+}
+
+void Collection::iterate(void (*callback)(int *))
+{ /* can't really do anything at this point */
+}
+
+bool Collection::contains(int n) const
+{
+    return false;
+}
+
diff --git a/collection.h b/collection.h
new file mode 100644
index 0000000..e354065
--- /dev/null
+++ b/collection.h
@@ -0,0 +1,26 @@
+#ifndef _COLLECTION_H_
+#define _COLLECTION_H_
+
+class Collection
+{
+  public:
+    virtual ~Collection() {}
+
+    virtual void add(int) = 0;
+    virtual bool remove(int) = 0;
+    virtual Collection& operator=(const Collection&) = 0;
+    virtual int operator[](int) = 0;
+    virtual Collection *copy(void) = 0;
+
+    int get_size(void) const;
+    void iterate(void (*)(int *));
+    virtual bool contains(int) const;
+
+  private:
+  protected:
+    Collection() : size_(0) {}
+    int size_;
+};
+
+#endif
+
diff --git a/linkedlist.cpp b/linkedlist.cpp
new file mode 100644
index 0000000..9298521
--- /dev/null
+++ b/linkedlist.cpp
@@ -0,0 +1,156 @@
+#include "linkedlist.h"
+
+LinkedList::LinkedList() : Collection(), head(NULL), tail(NULL)
+{
+}
+
+LinkedList::LinkedList(const LinkedList& list) : Collection(list), head(NULL), tail(NULL)
+{
+    Node *iter = list.tail;
+    while (iter) {
+        this->add(iter->v);
+        iter = iter->prev;
+    }
+}
+
+LinkedList& LinkedList::operator=(const Collection& rhs)
+{
+    if (this == &rhs)
+        return *this;
+
+    this->cleanup();
+    this->size_ = 0;
+
+    Node *iter = dynamic_cast<const LinkedList *>(&rhs)->head; /* it's ok g++ */
+    while (iter) {
+        this->add(iter->v);
+        iter = iter->next;
+    }
+
+    return *this;
+}
+
+LinkedList::~LinkedList()
+{
+    this->cleanup();
+}
+
+void LinkedList::cleanup(void)
+{
+    Node *iter, *prev;
+    iter = prev = this->head;
+    while (iter) {
+        prev = iter;
+        iter = iter->next;
+        delete prev;
+    }
+}
+
+void LinkedList::add(int n)
+{
+    Node *node = new Node();
+    node->v = n;
+    node->next = this->head;     /* link next */
+    if (!this->head)             /* first node */
+        this->tail = node;       /* this where tail gets assigned */
+    else
+        this->head->prev = node; /* link prev */
+
+    this->head = node;
+    this->size_++;
+}
+
+bool LinkedList::remove(int n)
+{
+    if (!this->head)
+        return false;
+
+    if (this->head->v == n) { /* deleting first element or head */
+        Node *first = this->head;
+        this->head = this->head->next;
+        if (this->get_size() == 1)
+            this->tail = NULL; /* tail gets nuked here */
+        delete first;
+        return true;
+    }
+    else if (this->tail->v == n) { /* deleting last element or tail */
+        Node *last = this->tail;
+        this->tail = this->tail->prev;
+        this->tail->next = NULL;
+        delete last;
+        return true;
+    }
+
+    Node *iter = this->head;
+    while (iter) {
+        if (iter->v == n) {
+            iter->prev->next = iter->next;
+            delete iter;
+            this->size_--;
+            return true;
+        }
+        iter = iter->next;
+    }
+
+    return false;
+}
+
+/* assumes first element is at index of zero */
+int LinkedList::operator[](int i)
+{
+    /* invalid accesses */
+    if (!this->size_ || i < 0 || i+1 > this->size_)
+        return -1;
+
+    Node *iter = this->head;
+    int cnt = this->size_ - i - 1;
+    while (cnt--) {
+        iter = iter->next;
+    }
+
+    return iter->v;
+}
+
+LinkedList *LinkedList::copy(void)
+{
+    LinkedList *ret = new LinkedList(*this);
+    return ret;
+}
+
+void LinkedList::iterate(void (*modifier)(int *))
+{
+    Node *iter = this->head;
+    while (iter) {
+        modifier(&iter->v); /* missing smalltalk? No! */
+        iter = iter->next;
+    }
+}
+
+bool LinkedList::contains(int i) const
+{
+    Node *iter;
+    for (iter = this->head; iter != NULL && iter->v != i; iter = iter->next)
+        ;
+
+    return iter ? true : false;
+}
+
+void LinkedList::print_helper(std::stringstream& sstm, Node *n) const
+{
+    if (!n)
+        return;
+
+    print_helper(sstm, n->next);
+    sstm << n->v << " ";
+}
+
+/* does a recursive print since ll is inverted with respect to array */
+/* could just use tail and iterate through prev pointers */
+std::string LinkedList::print() const
+{
+    std::stringstream sstm;
+    print_helper(sstm, this->head);
+
+    return sstm.str();
+}
+
diff --git a/linkedlist.h b/linkedlist.h
new file mode 100644
index 0000000..336e131
--- /dev/null
+++ b/linkedlist.h
@@ -0,0 +1,46 @@
+#ifndef _LINKEDLIST_H_
+#define _LINKEDLIST_H_
+
+#include "collection.h"
+#include <string>
+#include <sstream>
+
+class LinkedList : public Collection
+{
+  private:
+    class Node {
+      public:
+        Node() : v(-1), next(NULL), prev(NULL) {}
+        int v;
+        Node *next;
+        Node *prev;
+    };
+
+  public:
+    LinkedList();
+    LinkedList(const LinkedList&);
+    /* we can override the return type and still preserve dynamic binding! */
+    LinkedList& operator=(const Collection&);
+    ~LinkedList();
+
+    virtual void add(int);
+    virtual bool remove(int);
+    virtual int operator[](const int);
+    virtual LinkedList *copy(void);
+
+    /* override these methods that had empty definitions in the interface */
+    void iterate(void (*)(int *));
+    bool contains(int) const;
+
+    std::string print(void) const;
+
+  protected:
+  private:
+    void print_helper(std::stringstream&, Node *) const;
+    void cleanup(void);
+    Node *head;
+    Node *tail;
+};
+
+#endif
+
diff --git a/main.cpp b/main.cpp
new file mode 100644
index 0000000..8d7d026
--- /dev/null
+++ b/main.cpp
@@ -0,0 +1,56 @@
+/*
+ *
+ * kkamin8
+ */
+
+#include "linkedlist.h"
+#include "variablearray.h"
+#include <iostream>
+
+int main(int argc, char *argv[])
+{
+    Collection *ll = new LinkedList();
+    std::cout << "adding elements into linked list" << std::endl;
+    ll->add(7);
+    ll->add(12);
+    ll->add(21);
+    ll->add(33);
+    std::cout << "elements in ll: " << ((LinkedList *) ll)->print() << std::endl;
+
+    std::cout << "element at zero is: " << (*ll)[0] << std::endl;
+    std::cout << "element at two is : " << (*ll)[2] << std::endl;
+    std::cout << "the size of ll is: " << ll->get_size() << std::endl;
+    std::cout << "does ll contain 33? " << (ll->contains(33) ? "Yes\n" : "No\n");
+    std::cout << "does ll contain 999? " << (ll->contains(999) ? "Yes\n" : "No\n");
+
+    Collection *ll_copy = ll->copy();
+    delete ll;
+    std::cout << "copy of ll contains: " << ((LinkedList *) ll_copy)->print() << std::endl;
+
+    std::cout << std::endl << "adding elements into variable array" << std::endl;
+    Collection *arr = new VariableArray();
+    arr->add(13);
+    arr->add(131);
+    arr->add(-23);
+    arr->add(99);
+    arr->add(45);
+    std::cout << "array contains: " << ((VariableArray *)arr)->print() << std::endl;
+    std::cout << "removing 22 and 131" << std::endl;
+    arr->remove(22);
+    arr->remove(131);
+    std::cout << "array contains: " << ((VariableArray *)arr)->print() << std::endl;
+    std::cout << "the size of array is: " << arr->get_size() << std::endl;
+    std::cout << "element at two is: " << (*arr)[2] << std::endl;
+    std::cout << "element at four is: " << (*arr)[4] << std::endl;
+    std::cout << "NOTE: -1 means out of bounds access" << std::endl;
+
+    Collection *arr_copy = arr->copy();
+    delete arr;
+    std::cout << "copy of va contains: " << ((VariableArray *) arr_copy)->print() << std::endl;
+
+    delete ll_copy;
+    delete arr_copy;
+
+    return 0;
+}
+
diff --git a/variablearray.cpp b/variablearray.cpp
new file mode 100644
index 0000000..c1d0503
--- /dev/null
+++ b/variablearray.cpp
@@ -0,0 +1,81 @@
+#include "variablearray.h"
+#include <algorithm> /* for find() */
+
+VariableArray::VariableArray() : arr(/* ARR_STARTING_SIZE */)
+{
+}
+
+VariableArray::VariableArray(const VariableArray& array) : Collection(array), arr(array.arr) /* ha! */
+{
+}
+
+VariableArray& VariableArray::operator=(const Collection& rhs)
+{
+    this->arr = dynamic_cast<const VariableArray *>(&rhs)->arr; /* use vector's copy ctor */
+    this->size_ = rhs.get_size();
+    return *this;
+}
+
+VariableArray::~VariableArray()
+{
+}
+
+void VariableArray::add(int n)
+{
+    this->arr.push_back(n);
+    this->size_++;
+}
+
+bool VariableArray::remove(int n)
+{
+    std::vector<int>::iterator pos = std::find(this->arr.begin(), this->arr.end(), n);
+    if (pos != this->arr.end())
+    {
+        this->arr.erase(pos); /* kind of slow, since elements will get shifted */
+        this->size_--;
+        return true;
+    }
+    else
+        return false;
+}
+
+int VariableArray::operator[](const int i)
+{
+    /* invalid accesses */
+    if (!this->size_ || i < 0 || i+1 > this->size_)
+        return -1;
+
+    return this->arr[i];
+}
+
+VariableArray *VariableArray::copy(void)
+{
+    VariableArray *ret = new VariableArray(*this);
+    return ret;
+}
+
+void VariableArray::iterate(void (*callback)(int *))
+{
+    std::vector<int>::size_type i;
+    for (i = 0; i != this->arr.size(); ++i)
+        callback(&this->arr[i]);
+}
+
+bool VariableArray::contains(int n) const
+{
+    return (std::find(this->arr.begin(), this->arr.end(), n) != this->arr.end());
+}
+
+std::string VariableArray::print(void) const
+{
+    std::stringstream sstm;
+    std::vector<int>::const_iterator iter = this->arr.begin();
+    while (iter != this->arr.end())
+    {
+        sstm << *iter << " ";
+        iter++;
+    }
+
+    return sstm.str();
+}
+
diff --git a/variablearray.h b/variablearray.h
new file mode 100644
index 0000000..8b793a3
--- /dev/null
+++ b/variablearray.h
@@ -0,0 +1,37 @@
+#ifndef _VARIABLEARRAY_H_
+#define _VARIABLEARRAY_H_
+
+#include "collection.h"
+#include <string>
+#include <sstream>
+#include <vector>
+
+#define ARR_STARTING_SIZE   8
+
+class VariableArray : public Collection
+{
+  public:
+    VariableArray();
+    VariableArray(const VariableArray&);
+    VariableArray& operator=(const Collection&);
+    ~VariableArray();
+
+    virtual void add(int);
+    virtual bool remove(int);
+    virtual int operator[](const int);
+    virtual VariableArray *copy(void);
+
+    /* override these methods that had empty definitions in the interface */
+    void iterate(void (*)(int *));
+    bool contains(int) const;
+
+    std::string print(void) const;
+
+  protected:
+
+  private:
+    std::vector<int> arr;
+};
+
+#endif
+