circular doubly-linked list code

Node.h

// node for your double linked circular list

#ifndef NODE_CLASS

#define NODE_CLASS

#include

class Node{

private:

std::string word;

Node *next;

Node *prev;

public:

// default constructor

Node();

// constructor with single argument

Node(std::string);

// constructor with 2 arguments

// 2nd argument is a pointer to prev node

// primary constructor

Node(std::string, Node *);

// accessor for word

// returns contents of word

std::string& getWord();

// accessor for next

// returns pointer to node to which next is pointing

Node *getNext() const;

// accessor for next

// returns pointer to node to which prev is pointing

Node *getPrev() const;

// mutator for word

// changes string to value passed in

void setWord(std::string);

// mutator for next

// changes pointer to value passed in

void setNext(Node *);

// mutator for prev

// changes pointer to value passed in

void setPrev(Node *);

private:

// YOU MAY ADD ANY OTHER PRIVATE FUNCTIONS HERE

};

#endif // NODE_CLASS

Node.cpp

#include "Node.h" #include "Buffer.h" #include "Iterator.h" #include #include using namespace std; Node::Node() { word = ""; next = NULL; prev = NULL; } // constructor with single argument Node::Node(std::string a) { word = a; next = NULL; prev = NULL; }

// constructor with 2 arguments // 2nd argument is a pointer to prev node // primary constructor Node::Node(std::string a, Node *prev1) { word = a; prev = prev1; } // accessor for word // returns contents of word std::string& Node::getWord() { return word; } // accessor for next // returns pointer to node to which next is pointing Node* Node::getNext() const { if(prev==NULL) return NULL; else return next; } // accessor for next // returns pointer to node to which prev is pointing Node* Node::getPrev() const { if(prev==NULL) return NULL; else return prev; } // mutator for word // changes string to value passed in void Node::setWord(std::string b) { word = b; } // mutator for next // changes pointer to value passed in void Node::setNext(Node *next1) { next = next1; //checking } // mutator for prev // changes pointer to value passed in void Node::setPrev(Node *prev1) { prev = prev1; //checking }

Iterator.h

// circular doubly-linked list iterator class for Buffer

#ifndef ITERATOR

#define ITERATOR

#include

#include "Node.h"

// circular doubly-linked list iterator

class Iterator {

private:

Node *curr; // points to current node

public:

// initializes curr to currIn

Iterator(Node *currIn = NULL);

// dereference curr, returns plaintext string

const std::string operator*() const;

// pre-increment operator

Iterator& operator++();

// post-increment operator

Iterator operator++(int);

// for iterator math

// for example it = it + 2;

Iterator operator+(const int &);

// for iterator math

// for example it += 2;

Iterator operator+=(const int &);

// pre-decrement operator

Iterator& operator--();

// post-decrement operator

Iterator operator--(int);

// for iterator math

// for example it = it - 2;

Iterator operator-(const int &);

// for iterator math

// for example it -= 2;

Iterator operator-=(const int &);

// equality operator

// is true if 2 iterators are pointing to the same node

bool operator==(const Iterator &other);

// inequality operator

// is true if 2 iterators are pointing to different nodes

bool operator!=(const Iterator &other);

// returns the node to which the iterator points

Node *& getCurr();

private:

// YOU MAY ADD ANY OTHER PRIVATE FUNCTIONS HERE

};

#endif // ITERATOR

Iteration.cpp

#include "Node.h" #include "Buffer.h" #include "Iterator.h" #include #include using namespace std; // initializes curr to currIn Iterator::Iterator(Node *currIn) { curr = currIn; }

// dereference curr, returns plaintext string const std::string Iterator::operator*() const { return curr->getWord(); }

// pre-increment operator Iterator& Iterator::operator++() { curr = curr->getNext(); return *this; }

// post-increment operator Iterator Iterator::operator++(int) { Iterator return_value =*this; curr = curr->getNext(); ;return return_value; } // for iterator math // for example it = it + 2; Iterator Iterator::operator+(const int & c) { int i; for(i = 0; i < c; i++) { curr = curr->getNext(); } return *this; } // for iterator math // for example it += 2; Iterator Iterator::operator+=(const int & d) { int i; for(i = 0; i < d; i++) { curr = curr->getNext(); } return *this; } // pre-decrement operator Iterator& Iterator::operator--() { curr = curr->getPrev(); return *this; }

// post-decrement operator Iterator Iterator::operator--(int) { Iterator return_value =*this; curr = curr->getPrev(); ;return return_value; }

// for iterator math // for example it = it - 2; Iterator Iterator::operator-(const int & a) { int i; for(i = 0; i < a; i++) { curr = curr->getPrev(); } return *this; }

// for iterator math // for example it -= 2; Iterator Iterator::operator-=(const int & a) { int i; for(i = 0; i < a; i++) { curr = curr->getPrev(); } return *this; }

// equality operator // is true if 2 iterators are pointing to the same node bool Iterator::operator==(const Iterator &other) { if(this->curr == other.curr) return true; else return false; }

// inequality operator // is true if 2 iterators are pointing to different nodes bool Iterator::operator!=(const Iterator &other) { if(this->curr != other.curr) return true; else return false; }

// returns the node to which the iterator points Node *& Iterator::getCurr() { return curr; }

Buffer.h

// a circular, double linked list (ll) of Nodes

// dynamically resizes

// uses iterators to move through the data structure

#ifndef BUFFER_CLASS

#define BUFFER_CLASS

#include "Node.h"

#include "Iterator.h"

class Buffer {

private:

unsigned count; // the number of actual items in the ll

Node * head; // points to the head node

public:

// default constructor

// creates empty linked list of count = 0

Buffer();

// copy constructor for buffer

// creates a deep copy, of the ll,

// and stores it in other

// calls copy()

Buffer(const Buffer & other);

// destructor

// calls clear();

~Buffer();

// overloaded assignment operator

// calls copy()

Buffer & operator=(const Buffer & original);

// accessor

// returns the head

Node * getHead();

// accessor

// returns the tail node

Node * getTail();

// returns the string in the head node of the ll

// this operation is not valid for an empty ll (i.e. buffer)

// (If it is called on an empty buffer, return an emptry string "".)

std::string getHeadElement();

// returns the string in the tail node of the ll

// this operation is not valid for an empty ll (i.e. buffer)

// (If it is called on an empty buffer, return an emptry string "".)

std::string getTailElement();

// creates a node containing str

// adds the string at the head of the ll

// (i.e. before the current head node)

// after the operation, head node is the newly added one

void produceAtHead(const std::string str);

// creates a node containing str

// adds the string at the end of the ll

// (i.e. after the current tail node)

void produceAtTail(const std::string str);

// inserts Node containing "str" into the ll in front of "pos"

// return an iterator that points to the the newly inserted elements.

// any iterators after pos are considered invalid

Iterator produceAtMiddle(Iterator pos, const std::string str);

// buffer must not be empty before calling this

// deletes the first element (i.e. current head node)

void consumeAtHead();

// buffer must not be empty before calling this

// deletes the last element (i.e. current tail node)

void consumeAtTail();

// "it" is pointing to the element to be removed

void consume(Iterator it);

// erases all nodes in the range [s,t)

// s is erased and all nodes up to but not

// including t are erased

void consume(Iterator s, Iterator t);

// returns the number of elements in the ll

unsigned size() const;

// returns true if the ll is empty, otherwise it returns false

bool isEmpty();

// brackets operator allows indexing into the ll

// "fakes" random access to the ith element of the ll

// returns contents of ith element of the ll

// if ll looks like:

// we -> are -> family ->

// then element 2 would be "family"

// remember the first element is the 0th element

std::string & operator[](int i) const;

// returns the iterator pointing to the first node in the ll

Iterator getHeadItr();

// returns an iterator pointing the tail node in ll

Iterator getTailItr();

// returns an iterator of the next node pointed by it

Iterator getNextItr(Iterator it);

// returns an iterator of the previous node pointed by it

Iterator getPrevItr(Iterator it);

// prints out the ll like the following

// contents of node, followed by a space,

// followed by -> followed by a space

// after list is printed, it skips a line

// ie has 2 endls

// if list is empty, it prints "->" followed by

// 2 endls

void print();

private:

// makes a deep copy of the ll for copy constructor

// and assignment operator

// "other" is copied

void copy(const Buffer & other);

// clears the ll by deleting all nodes

// calls the recursive function deleteBuffer()

void clear();

// recursively deletes the ll p

// THIS FUNCTION MUST BE RECURSIVE

void deleteBuffer(Node * p);

// YOU MAY ADD ANY OTHER PRIVATE FUNCTIONS HERE

};

#endif // BUFFER_CLASS

// non-member function

// locates "str" in the range [first,last]

// if "str" is found in the range, return true

// if "str" is not found, return false

bool findNode(Iterator first, Iterator last, std::string str);

Buffer.cpp

#include "Node.h"

#include "Buffer.h"

#include "Iterator.h"

#include

#include

using namespace std;

// unsigned count; // the number of actual items in the ll

// Node * head; // points to the head node

// default constructor

// creates empty linked list of count = 0

Buffer::Buffer()

{

head = new Node;

count = 0;

}

// copy constructor for buffer

// creates a deep copy, of the ll,

// and stores it in other

// calls copy()

Buffer::Buffer(const Buffer & other)

{

//void Buffer::copy(const Buffer & other);

this->copy(other);

}

// destructor

// calls clear();

Buffer::~Buffer()

{

//void Buffer::clear();

clear();

}

// overloaded assignment operator

// calls copy()

Buffer & Buffer::operator=(const Buffer & original)

{

//void Buffer::copy(const Buffer & other);

this->copy(original);

}

// accessor

// returns the head

Node * Buffer::getHead()

{

return head;

}

// accessor

// returns the tail node

Node * Buffer::getTail()//why always like these thing....

{

Node *out;

while (out != NULL && out->getNext() != NULL)

out = out->getNext();

return out;

}

// returns the string in the head node of the ll

// this operation is not valid for an empty ll (i.e. buffer)

// (If it is called on an empty buffer, return an emptry string "".)

std::string Buffer::getHeadElement()

{

if(!isEmpty())

{

Node* front = head;

return front->getWord();

}

else

return "";

}

// returns the string in the tail node of the ll

// this operation is not valid for an empty ll (i.e. buffer)

// (If it is called on an empty buffer, return an emptry string "".)

std::string Buffer::getTailElement()

{

if(!isEmpty())

{

Node* back = getTail();

return back->getWord();

}

else

return "";

}

// creates a node containing str

// adds the string at the head of the ll

// (i.e. before the current head node)

// after the operation, head node is the newly added one

void Buffer::produceAtHead(const std::string str) /////check

{

Node* tail = getTail();

Node* temp = new Node;

temp->setWord(str);

temp->setNext(NULL);

if (head == NULL)

{

head = temp;

tail = temp;

temp = NULL;

}

else

{

tail->setNext(temp);

tail = temp;

}

}

// creates a node containing str

// adds the string at the end of the ll

// (i.e. after the current tail node)

void Buffer::produceAtTail(const std::string str) /////check

{

Node* tail = getTail();

Node* temp = new Node;

temp->setWord(str);

if(isEmpty())

{

Node* last = new Node;

last->setWord("END");

last->setNext(NULL);

temp->setNext(last);

head = temp;

tail = head;

}

else

{

temp->setNext(tail->getNext());

tail->setNext(temp);

tail = temp;

}

}

// inserts Node containing "str" into the ll in front of "pos"

// return an iterator that points to the the newly inserted elements.

// any iterators after pos are considered invalid

Iterator Buffer::produceAtMiddle(Iterator pos, const std::string str) /////check

{

Node* index = head;

Node* prev;

Node* temp = new Node;

temp->setWord(str);

if(pos.getCurr() == head)

{

temp->setNext(index);

head = temp;

}

else

{

while(index != pos.getCurr())

{

index = index->getNext();//index is pos.getCurr

}

prev = index->getPrev();

prev->setNext(temp);

temp->setNext(pos.getCurr());

}

count++;

}

// buffer must not be empty before calling this

// deletes the first element (i.e. current head node)

void Buffer::consumeAtHead()

{

Node* tail = getTail();

Node *temp = head;

if(head==NULL)

return;

else

{

tail = tail->getNext();

tail = head->getNext();

head = head->getNext();

head = head->getPrev();

head = tail;

}

delete [] temp;

}

// buffer must not be empty before calling this

// deletes the last element (i.e. current tail node)

void Buffer::consumeAtTail()

{

Node* tail = getTail();

if(isEmpty() == false)

{

Node* temp = head;

while(temp->getWord() != "END")

{

temp = temp->getNext();

}

if(head->getNext()->getWord() == "END")

{

Node* prev3 = temp->getPrev();

delete prev3;

count--;

}

else

{

Node* prev1 = temp->getPrev();

Node* prev2 = prev1->getPrev();

prev2->setNext(prev1->getNext());

delete prev1;

tail = prev2;

count--;

}

}

}

// "it" is pointing to the element to be removed

void Buffer::consume(Iterator it)

{

Node* tail = getTail();

Node* temp = head;

Node* back;

if(it.getCurr() == head)

{

head = it.getCurr()->getNext();

delete it.getCurr();

}

else

{

while(temp != it.getCurr())

{

temp = temp->getNext();

}

back = temp->getPrev();

back->setNext(it.getCurr()->getNext());

if(it.getCurr()==tail)

tail = temp;

delete it.getCurr();

}

count--;

it = this->getTailItr();

}

// erases all nodes in the range [s,t)

// s is erased and all nodes up to but not

// including t are erased

void Buffer::consume(Iterator s, Iterator t)

{

Node* s_temp = head;

Node* t_temp = head;

Node* s_prev;

Node* t_prev;

Node* index = s.getCurr();

Iterator it = s;

while(s_temp != s.getCurr())

{

s_temp = s_temp->getNext();

}

while(t_temp != t.getCurr())

{

t_temp = t_temp->getNext();

}

if(s_temp == head)

{

index = s.getCurr();

t_prev = t_temp->getPrev();

while(index != t_temp->getNext())

{

consume(it);

count--;

index = index->getNext();

it++;

}

}

else

{

s_prev = s_temp->getPrev();

t_prev = t_temp->getPrev();

index = s.getCurr();

s_prev->setNext(t.getCurr());

while(index != t_temp->getNext())

{

consume(it);

count--;

index = index->getNext();

it++;

}

}

}

// returns the number of elements in the ll

unsigned Buffer::size() const

{

if(head==NULL)

return 0;

int num = 0;

Node *current = head;

do

{

num++;

current = current->getNext();

}while(current != head);

return num;

}

// returns true if the ll is empty, otherwise it returns false

bool Buffer::isEmpty()

{

if(count == 0)

return true;

else

return false;

}

// brackets operator allows indexing into the ll

// "fakes" random access to the ith element of the ll

// returns contents of ith element of the ll

// if ll looks like:

// we -> are -> family ->

// then element 2 would be "family"

// remember the first element is the 0th element

std::string & Buffer::operator[](int i) const

{

string *buff = new string[i];

Node* temp = head;

int j;

for(j = 0; j < i; j++)

{

buff[j] = temp->getNext()->getWord();

if(j != i)

{

temp = temp->getNext();

}

}

return buff[i];

}

// returns the iterator pointing to the first node in the ll

Iterator Buffer::getHeadItr()

{

Iterator first = head;

return first;

}

// returns an iterator pointing the tail node in ll

Iterator Buffer::getTailItr()

{

Iterator last = head;

return last;

}

// returns an iterator of the next node pointed by it

Iterator Buffer::getNextItr(Iterator it)

{

it = head->getNext();

return it;

}

// returns an iterator of the previous node pointed by it

Iterator Buffer::getPrevItr(Iterator it)

{

Node *tail = getTail();

it = tail->getNext();

return it;

}

// prints out the ll like the following

// contents of node, followed by a space,

// followed by -> followed by a space

// after list is printed, it skips a line

// ie has 2 endls

// if list is empty, it prints "->" followed by

// 2 endls

void Buffer::print()

{

Node* temp = head;

if(isEmpty())

cout << "->" << endl << endl;

else

{

while(temp->getWord() != "END")

{

cout << temp->getWord() << " -> ";

temp = temp->getNext();

}

cout << endl << endl;

}

}

// makes a deep copy of the ll for copy constructor

// and assignment operator

// "other" is copied

void Buffer::copy(const Buffer & other)

{

Node* nhead = other.head;

Node* tail = getTail();

Node* shead = this->head;

while(nhead != tail)

{

produceAtTail(nhead->getWord());

nhead=nhead->getNext();

}

}

// clears the ll by deleting all nodes

// calls the recursive function deleteBuffer()

void Buffer::clear()

{

Node *tail = getTail();

deleteBuffer(tail);

}

// recursively deletes the ll p

// THIS FUNCTION MUST BE RECURSIVE

void Buffer::deleteBuffer(Node * p)

{

Node* temp = head;

Node* back;

while(temp != p)

{

temp = temp->getNext();

}

back = temp->getPrev();

if(back == head)

{

delete back;

}

else

{

deleteBuffer(back);

delete back;

}

}

// non-member function

// locates "str" in the range [first,last]

// if "str" is found in the range, return true

// if "str" is not found, return false

bool findNode(Iterator first, Iterator last, std::string str)

{

while(first.getCurr() != last.getCurr())

{

if(first.getCurr()->getWord() != str)

{

first.getCurr() = first.getCurr()->getNext();

}

else

{

return true;//if same, true

}

}

if(first.getCurr() == last.getCurr())//if not, false

{

return false;

}

}

i make this cpp file.

I do

#include #include "Buffer.h" #include "Iterator.h"

using namespace std;

int main() { Buffer v1; Iterator it;

v1.produceAtHead("Object"); v1.produceAtHead("Is"); v1.produceAtHead("This"); v1.produceAtTail("Oriented"); v1.produceAtTail("Programming");

cout << "count = " << v1.size() << endl; // print "5" cout << "first string= " << v1.getHeadElement() << endl; // print "This" cout << "last string= " << v1.getTailElement() << endl; // print "Programming" v1.print(); // This -> Is -> Object -> Oriented -> Programming

v1.consumeAtHead(); v1.consumeAtTail(); v1.print(); // Is -> Object -> Oriented

it = v1.getHeadItr(); it = v1.getNextItr(it); v1.consume(it); v1.print(); // Is -> Oriented

// insert in middle it = v1.getTailItr(); it = v1.produceAtMiddle(it, "Object"); v1.print(); // Is -> Object -> Oriented

// test find cout << findNode(v1.getHeadItr(), v1.getTailItr(), "Bond") << endl;

// empty buffer v1.consumeAtHead(); v1.consumeAtHead(); v1.consumeAtHead(); cout << "count = " << v1.size() << endl; // 0 v1.print(); // ->

// test isEmpty() if (v1.isEmpty()) cout << "empty buffer" << endl;

return 0; }

But it has segmantation fault. In here, it can't change header files.

Please change to make outputs like in main.cpp