Queue of Strings - OOP344
Revision as of 17:55, 25 November 2010 by Mysnogorodsky (talk | contribs) (→strque.cpp line 80 _head = _cur; is single = sign)
A Queue of Strings
Note that this code is neither efficient nor bug free.
Use it just as a base for a double linked list of strings to be optimized later...
strque.h
#ifndef __FS_STRQUE_H__
#define __FS_STRQUE_H__
#define NullNode ((DNode*)0)
class StrQue;
class DNode{
char* _data;
DNode* _next;
DNode* _prev;
DNode(const char* data, DNode* prev = NullNode, DNode* Next= NullNode);
~DNode();
friend class StrQue;
};
class StrQue{
DNode* _head;
DNode* _tail;
DNode* _cur;
int _size;
DNode* _savedCur;
public:
StrQue();
~StrQue();
// add to the end
void Append(const char* data);
// deletes the cur and if possible
// cur will point to next otherwise cur
// will point to prev
bool Delete();
// inserts a node between cur and cur->prev
// cur becomes the newly inserted node
void Insert(const char* data);
void InsertAfter(const char* data);
bool IsEmpty();
// if cur exists, it return cur->data
// if failes returns null
char* Visit();
// counts the nodes form the beg to
// index and returns the data of the node
// having the fist as zero
char* operator[](unsigned int index);
// returns number of nodes
int Size();
// Store the _cur pointer so it can be restored after operation
void StoreCur();
// Restores the _cur pointer back to the last '''SotreCur()''' call.
void RestoreCur();
bool GoNext();
bool GoPrev();
bool GoHead();
bool GoTail();
};
#endif
strque.cpp
#include <cstring>
using namespace std;
#include "strque.h"
DNode::DNode(const char* data, DNode* prev, DNode* next){
_data = new char[strlen(data)+1];
strcpy(_data, data);
_next = next;
_prev = prev;
}
DNode::~DNode(){
delete[] _data;
}
StrQue::StrQue(){
_savedCur = _head = _tail = _cur = NullNode;
_size = 0;
}
StrQue::~StrQue(){
while(Delete());
}
char* StrQue::Visit(){
return _cur->_data;
}
void StrQue::Append(const char* data){
DNode* nn = new DNode(data, _tail);
if(_cur){
_tail->_next = nn;
_cur=_tail = nn;
}
else{
_head = _tail = _cur = nn;
}
_size ++ ;
}
bool StrQue::Delete(){
bool ok = true;
if(!_cur){
ok = false;
}
else if(_head == _tail){
delete _cur;
_head = _tail = _cur = _savedCur = NullNode;
}
else if(_cur == _head){
DNode* toDel = _cur;
_cur->_next->_prev = NullNode;
_cur = _head = _cur->_next;
delete toDel;
}
else if(_cur == _tail){
DNode* toDel = _cur;
_cur->_prev->_next = NullNode;
_cur = _tail = _cur->_prev;
delete toDel;
}
else{
DNode* toDel = _cur;
_cur = _cur->_next;
_cur->_prev = toDel->_prev;
toDel->_prev->_next = _cur;
delete toDel;
}
_size -= (int)ok;
return ok;
}
void StrQue::Insert(const char* data){
DNode* newnode;
if(IsEmpty()){
_head = _cur= _tail = new DNode(data);
}
else if(_head == _tail){
newnode = new DNode(data,NullNode, _cur);
_cur->_prev = newnode;
_head = _cur = newnode;
}
else if(_cur == _head){
newnode = new DNode(data,_cur->_prev, _cur);
_cur = newnode;
_cur->_next->_prev = _cur;
_head = _cur;
}
else{
newnode = new DNode(data,_cur->_prev, _cur);
_cur = newnode;
_cur->_next->_prev = _cur;
_cur->_prev->_next = _cur;
}
_size++;
}
void StrQue::InsertAfter(const char* data){
if(_cur == _tail){
Append(data);
}
else{
GoNext();
Insert(data);
}
}
bool StrQue::IsEmpty(){
return !_cur;
}
char* StrQue::operator[](unsigned int index){
StoreCur();
char* cdata = (char*)0;
index = index % _size;
if(GoHead()){
int i;
for(i=0;i<index && GoNext();i++);
if(i == index) cdata = _cur->_data;
}
RestoreCur();
return cdata;
}
int StrQue::Size(){
return _size;
}
void StrQue::StoreCur(){
_savedCur = _cur;
}
void StrQue::RestoreCur(){
_cur = _savedCur;
}
bool StrQue::GoNext(){
bool ok = false;
if(_cur && _cur->_next){
_cur = _cur->_next;
ok = true;
}
return ok;
}
bool StrQue::GoPrev(){
bool ok = false;
if(_cur && _cur->_prev){
_cur = _cur->_prev;
ok = true;
}
return ok;
}
bool StrQue::GoHead(){
bool ok = false;
if(_cur){
_cur = _head;
ok = true;
}
return ok;
}
bool StrQue::GoTail(){
bool ok = false;
if(_cur){
_cur = _tail;
ok = true;
}
return ok;
}