rendered paste body#ifndef unrolled_h_
#define unrolled_h_
#ifndef iostream_h_
#define iostream_h_
#include <iostream>
#endif
const int NUM_ELEMENTS_PER_NODE=6;
template <class T>
class Node {
public:
Node() : next_(NULL), prev_(NULL), num_elements(0) {};
Node(const T& v);
// REPRESENTATION
T value_[NUM_ELEMENTS_PER_NODE];
Node<T>* next_;
Node<T>* prev_;
unsigned int num_elements;
};
template <class T>
Node<T>::Node(const T& v) {
next_=NULL;
prev_=NULL;
num_elements=1;
value_[0]=v;
}
//Definition of list_iterator, so UnrolledLL can use it
template <class T> class list_iterator;
template <class T>
class UnrolledLL {
public:
UnrolledLL() : head_(NULL), tail_(NULL), size_(0) {}
UnrolledLL(const UnrolledLL<T>& old) { this->copy_list(old); }
~UnrolledLL() { this->destroy_list(); }
UnrolledLL& operator= (const UnrolledLL<T>& old);
//Some basic functions
unsigned int size() const { return size_; }
bool empty() const { return head_ == NULL; }
void clear() { this->destroy_list(); }
//Front, back
const T& front() const { return head_->value_[0]; }
T& front() { return head_->value_[0]; }
const T& back() const { return tail_->value_[tail_->num_elements]; }
T& back() { return tail_->value_[tail_->num_elements]; }
//Entering new data
void push_front(const T& v);
void pop_front();
void push_back(const T& v);
void pop_back();
//Iterator functions
typedef list_iterator<T> iterator;
iterator begin() { return iterator(head_); }
iterator end() { return iterator(end_); }
list_iterator<T> erase(iterator itr);
list_iterator<T> insert(iterator itr, T const& v);
private:
void copy_list(const UnrolledLL<T>& old);
void destroy_list();
Node<T>* end_;
Node<T>* head_;
Node<T>* tail_;
unsigned int size_;
};
template <class T>
list_iterator<T> UnrolledLL<T>::insert(iterator itr, T const& v)
{
//Push front, if itr is at begin()
if(itr==this->begin())
{
this->push_front(v);
itr++;
return itr;
}
//Push back, if itr is at end()
if(itr==this->end())
{
this->push_back(v);
return itr;
}
//If itr is at the beginning of a full node, create a new node
if(itr.offset==0 && itr.ptr_->num_elements==NUM_ELEMENTS_PER_NODE)
{
Node<T>* temp=new Node<T>(v);
temp->next_=itr.ptr_;
temp->prev_=itr.ptr_->prev_;
temp->prev_->next_=temp;
itr.ptr_->prev_=temp;
return itr;
}
//If itr is somewhere else in a full node, create a new node
if(itr.ptr_->num_elements==NUM_ELEMENTS_PER_NODE)
{
Node<T>* temp=new Node<T>(itr.ptr_->value_[NUM_ELEMENTS_PER_NODE-1]);
int x;
for(x=NUM_ELEMENTS_PER_NODE-1 ; x>=itr.offset ; x--)
itr.ptr_->value_[x]=itr.ptr_->value_[x-1];
itr.ptr_->value_[itr.offset-1]=v;
return itr;
}
//If itr is in a node with room for the new element
{
int x;
for(x=itr.ptr_->num_elements-1;x>=itr.offset ; x--)
itr.ptr_->value_[x]=itr.ptr_->value_[x-1];
itr.ptr_->value_[itr.offset-1]=v;
itr.ptr_->num_elements=itr.ptr_->num_elements+1;
return itr;
}
}
template <class T>
list_iterator<T> UnrolledLL<T>::erase(iterator itr)
{
//Size=1
if(size_==1)
{
destroy_list();
itr=NULL;
return itr;
}
//Number of elements in node=1, head node
if((itr.ptr_)->num_elements==1 && (itr.ptr_)==(this->head_))
{
head_=head_->next_;
itr++;
delete head_->prev_;
head_->prev_=NULL;
return itr;
}
//Number of elements in node=1, tail node
if((itr.ptr_)->num_elements==1 && (itr.ptr_)==(this->tail_))
{
tail_=tail_->prev_;
delete tail_->next_;
tail_->next_=end_;
end_->prev_=tail_;
itr=NULL;
return itr;
}
//First element
if(itr.ptr_==(this->head_) && itr.offset==0)
{
this->pop_front();
return itr;
}
//Last element
if(itr.ptr_==(this->tail_) && itr.offset==(itr.ptr_)->num_elements-1)
{
this->pop_back();
return itr;
}
//Only one element in node
if(itr.ptr_->num_elements==1)
{
itr++;
itr.ptr_->prev_=itr.ptr_->prev_->prev_;
delete itr.ptr_->prev_->next_;
itr.ptr_->prev_->next_=itr.ptr_;
return itr;
}
//Last element in node
if(itr.offset==itr.ptr_->num_elements-1)
{
itr.ptr_->num_elements=itr.ptr_->num_elements-1;
itr++;
return itr;
}
//Normal case... More than one element in the node, not the last element in the node, and not the very first element in the list
int x;
for(x=itr.offset; x < itr.ptr_->num_elements;x++)
itr.ptr_->value_[x]=itr.ptr_->value_[x+1];
itr.ptr_->num_elements=itr.ptr_->num_elements-1;
return itr;
}
template <class T>
UnrolledLL<T>& UnrolledLL<T>::operator= (const UnrolledLL<T>& old) {
if (&old != this) {
this->destroy_list();
this->copy_list(old);
}
return *this;
}
template <class T>
void UnrolledLL<T>::copy_list(const UnrolledLL<T>& old)
{
size_=old.size_;
//empty list
if(size_==0)
{
head_=tail_=end_=0;
return;
}
//Create an appropritate number of nodes
Node<T>* temp=new Node<T>;
head_=tail_=temp;
for(int x=0;x<((size_-1)/6);x++)
{
temp=new Node<T>;
tail_->next_=temp;
temp->prev_=tail_;
tail_=temp;
}
end_=new Node<T>;
end_->prev_=tail_;
tail_->next_=end_;
//The minimum number of nodes has been created; head_, tail_, and end_ point to the correct spots, now fill in values
list_iterator<T> p=old.head_;
list_iterator<T> q=this->begin();
for(p;p != old.end_;p++)
{
*q=*p;
q++;
}
}
template <class T>
void UnrolledLL<T>::destroy_list()
{
if(head_==tail_)
delete head_;
if(head_!=tail_)
{
list_iterator<T> p=head_;
p++;
for(p;p!=end_;p++)
{
delete (p.ptr_)->prev_;
}
delete p.ptr_;
}
delete end_;
head_=NULL;
tail_=NULL;
end_=NULL;
}
template <class T>
std::ostream& operator<<(std::ostream& os, UnrolledLL<T> a)
{
list_iterator<T> itr=a.begin();
for(itr ; itr != a.end() ; itr++)
os << *itr << " ";
return os;
}
template <class T>
void UnrolledLL<T>::push_front(const T& v) {
//If there is no Node in existence
if(!tail_)
{
Node<T>* temp=new Node<T>(v);
head_=tail_=temp;
end_=new Node<T>;
end_ -> prev_ = tail_;
tail_ -> next_ = end_;
size_++;
return;
}
//If the current head Node is full
if(head_ -> num_elements==NUM_ELEMENTS_PER_NODE)
{
Node<T>*temp=new Node<T>(v);
head_ -> next_ = temp;
temp -> prev_ = head_;
head_=temp;
}
//If the current head Node has more room
if(head_ -> num_elements<NUM_ELEMENTS_PER_NODE)
{
for(int x=head_->num_elements-1;x==0;x++)
{
head_ -> value_[x+1] = head_ -> value_[x];
}
head_ -> value_[0]=v;
head_ -> num_elements = head_ -> num_elements + 1;
}
}
template <class T>
void UnrolledLL<T>::pop_front() {
//This is assuming there's a node in existence
//Normal case, if head has more than one value
if(head_ -> num_elements > 1)
{
for(int x=0;x< head_ -> num_elements; x++)
{
head_->value_[x]=head_->value_[x+1];
}
head_->num_elements=head_->num_elements-1;
}
//If head has only one value, but there are other nodes
if(head_-> num_elements==1 && size_>1)
{
head_=head_->next_;
delete head_->prev_;
head_->prev_=NULL;
}
//If there's only one value total, everything goes to null
if(size_==1)
{
delete head_;
delete end_;
head_=NULL;
tail_=NULL;
end_=NULL;
}
size_--;
}
template <class T>
void UnrolledLL<T>::pop_back() {
//This is assuming there's a node in existance
//Normal case, if tail has more than one value
if(tail_ -> num_elements > 1)
{
tail_-> num_elements = tail_-> num_elements -1;
}
//If tail has only one value, but there are other nodes
if(tail_-> num_elements==1 && size_>1)
{
tail_=tail_->prev_;
delete tail_->next_;
tail_->next_=end_;
end_->prev_=tail_;
}
//If there's only one value total, everything goes to null
if(size_==1)
{
delete head_;
delete end_;
head_=NULL;
tail_=NULL;
end_=NULL;
}
size_--;
}
template <class T>
void UnrolledLL<T>::push_back(const T& v) {
//If there is no Node in existence
if(!tail_)
{
Node<T>* temp=new Node<T>(v);
head_=tail_=temp;
end_=new Node<T>;
end_ -> prev_ = tail_;
tail_ -> next_ = end_;
}
//If the current tail Node is full
if(tail_ -> num_elements==NUM_ELEMENTS_PER_NODE)
{
Node<T>* temp=new Node<T>(v);
tail_ -> next_ = temp;
temp -> prev_ = tail_;
tail_=temp;
tail_ -> next_ = end_;
end_ -> prev_ = tail_;
}
//If the current tail Node has more room
if(tail_ -> num_elements<NUM_ELEMENTS_PER_NODE)
{
tail_ -> value_[tail_ -> num_elements]=v;
tail_ -> num_elements = tail_ -> num_elements++;
}
size_++;
}
template <class T>
class list_iterator
{
public:
list_iterator() : ptr_(NULL), offset(0) {};
list_iterator(Node<T>* p) : ptr_(p), offset(0) {};
list_iterator(Node<T>* p, int q): ptr_(p), offset(q) {};
list_iterator(list_iterator<T> const& old) : ptr_(old.ptr_) {}
~list_iterator() {};
list_iterator<T> & operator=(const list_iterator<T> & old) {
ptr_ = old.ptr_; return *this; }
// dereferencing operator gives access to the value at the pointer
T& operator*() { return ptr_->value_[offset]; }
// increment operator
list_iterator<T> & operator++() {
if(offset==ptr_->num_elements-1)
{
ptr_ = ptr_->next_;
offset=0;
}
if(offset<ptr_->num_elements-1)
{
offset++;
}
return *this;
}
list_iterator<T> operator++(int) {
list_iterator<T> temp(*this);
if(offset==ptr_->num_elements-1)
{
ptr_ = ptr_->next_;
offset=0;
}
if(offset<ptr_->num_elements-1)
{
offset++;
}
return temp;
}
// decrement operator
list_iterator<T> & operator--() {
if(offset==0)
{
ptr_ = ptr_->prev_;
offset=ptr_->num_elements-1;
}
if(offset>0)
{
offset--;
}
return *this;
}
list_iterator<T> operator--(int) {
list_iterator<T> temp(*this);
if(offset==0)
{
ptr_=ptr_->prev_;
offset=ptr_->num_elements-1;
}
if(offset>0)
{
offset--;
}
return *this;
}
friend class UnrolledLL<T>;
// comparison
friend bool operator==(const list_iterator<T>& l, const list_iterator<T>& r) {
return l.ptr_ == r.ptr_; }
friend bool operator!=(const list_iterator<T>& l, const list_iterator<T>& r) {
return l.ptr_ != r.ptr_; }
private:
Node<T>* ptr_;
unsigned int offset;
};
#endif