Queue of Strings - OOP344

From CDOT Wiki
Revision as of 17:55, 25 November 2010 by Mysnogorodsky (talk | contribs) (strque.cpp line 80 _head = _cur; is single = sign)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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;
}