diff options
author | Kyle K <kylek389@gmail.com> | 2012-05-06 17:37:28 -0500 |
---|---|---|
committer | Kyle Kaminski <kyle@kkaminsk.com> | 2012-05-06 17:37:28 -0500 |
commit | db8d48f8ab912989726869ac7352ae9b0822515a (patch) | |
tree | 7ed3d5eab98784dcd50a639863e5192be41a4880 | |
download | collection++-master.tar.gz collection++-master.tar.bz2 collection++-master.zip |
-rw-r--r-- | Makefile | 30 | ||||
-rw-r--r-- | collection.cpp | 16 | ||||
-rw-r--r-- | collection.h | 26 | ||||
-rw-r--r-- | linkedlist.cpp | 156 | ||||
-rw-r--r-- | linkedlist.h | 46 | ||||
-rw-r--r-- | main.cpp | 56 | ||||
-rw-r--r-- | variablearray.cpp | 81 | ||||
-rw-r--r-- | variablearray.h | 37 |
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 + |