From db8d48f8ab912989726869ac7352ae9b0822515a Mon Sep 17 00:00:00 2001 From: Kyle K Date: Sun, 6 May 2012 17:37:28 -0500 Subject: initial commit --- Makefile | 30 +++++++++++ collection.cpp | 16 ++++++ collection.h | 26 +++++++++ linkedlist.cpp | 156 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ linkedlist.h | 46 ++++++++++++++++ main.cpp | 56 ++++++++++++++++++++ variablearray.cpp | 81 ++++++++++++++++++++++++++++ variablearray.h | 37 +++++++++++++ 8 files changed, 448 insertions(+) create mode 100644 Makefile create mode 100644 collection.cpp create mode 100644 collection.h create mode 100644 linkedlist.cpp create mode 100644 linkedlist.h create mode 100644 main.cpp create mode 100644 variablearray.cpp create mode 100644 variablearray.h 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(&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 +#include + +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 + +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 /* 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(&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::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::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::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 +#include +#include + +#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 arr; +}; + +#endif + -- cgit v1.2.3