///////////////////////////////////////////////////////////////////////////////
// linklist.h
// Author: Seree Rakwong
// Date: 8-NOV-10
// Purpose: Link list container
#define linklist_h
namespace mstd {
template<class T>
class linklist {
public:
class linklist_node {
T data_;
linklist_node *prev_;
linklist_node *next_;
public:
linklist_node(const T& data)
: data_(data),
prev_(0),
next_(0)
{}
public:
T data() const { return data_; }
T& data() { return data_; }
linklist_node *prev() const { return prev_; }
linklist_node *&prev() { return prev_; }
linklist_node *next() const { return next_; }
linklist_node *&next() { return next_; }
}; // class linklist_node
private:
linklist_node *begin_;
linklist_node *end_;
unsigned long count_;
public:
linklist()
: begin_(0),
end_(0),
count_(0)
{}
virtual ~linklist() { remove_all(); }
public:
linklist_node *begin() const { return begin_; }
linklist_node *&begin() { return begin_; }
linklist_node *end() const { return end_; }
linklist_node *&end() { return end_; }
unsigned long count() const { return count_; }
public:
// remove all nodes
void remove_all() {
linklist_node *del_node = begin_;
while(del_node) {
begin_ = begin_->next();
delete del_node;
del_node = 0; // safe to use in the future
del_node = begin_;
}
begin_ = 0;
end_ = 0;
count_ = 0;
}
// remove the first
void remove_begin() {
if(!begin_) return; // don't do anything
linklist_node *node = begin_;
begin_ = begin_->next();
begin_->prev() = 0;
delete node;
node = 0;
count_--;
}
// remove the last
void remove_end() {
if(!end_) return; // don't do anything
linklist_node *node = end_;
end_ = end_->prev();
end_->next() = 0;
delete node;
node = 0;
count_--;
}
// remove at the node
void remove_at(linklist_node *at) {
if(!at) return; // don't do anything
linklist_node *next = at->next();
linklist_node *prev = at->prev();
next->prev() = prev;
prev->next() = next;
delete at;
at = 0; // safe to use in the future
}
// insert a new node at the first
linklist_node *insert_begin(const T& data) {
linklist_node *node = new linklist_node(data);
if(!node) return 0;
if(!begin_) {
begin_ = node;
end_ = node;
}
else {
node->next() = begin_;
begin_->prev() = node;
begin_ = node;
}
count_++;
return node;
}
// insert a new node at the last
linklist_node *insert_end(const T& data) {
linklist_node *node = new linklist_node(data);
if(!node) return 0;
if(!begin_) {
begin_ = node;
end_ = node;
}
else {
node->prev() = end_;
end_->next() = node;
end_ = node;
}
count_++;
return node;
}
// insert a new node before the node
linklist_node *insert_before(const T& data, linklist_node *at) {
if(!at) return 0;
linklist_node *node = new linklist_node(data);
if(!node) return 0;
// link to
//linklist_node *next = at->next();
linklist_node *prev = at->prev();
node->next() = at;
at->prev() = node;
node->prev() = prev;
if(prev) prev->next() = node;
count_++;
return node;
}
// insert a new node after the node
linklist_node *insert_after(const T& data, linklist_node *at) {
if(!at) return 0;
linklist_node *node = new linklist_node(data);
if(!node) return 0;
// link to
linklist_node *next = at->next();
node->prev() = at;
at->next() = node;
node->next() = next;
if(next) next->prev() = node;
count_++;
return node;
}
// insert a new node by reverse sorting
linklist_node *insert_rsort(const T& data) {
linklist_node *node = new linklist_node(data);
if(!node) return 0;
if(!begin_) {
begin_ = node;
end_ = node;
}
else {
linklist_node *current = end_;
while(current) {
if(data <= current->data()) {
if(current == end_) {
node->prev() = end_;
end_->next() = node;
end_ = node;
}
else {
node->prev() = current;
node->next() = current->next();
if(current->next()) current->next()->prev() = node;
current->next() = node;
}
break;
}
current = current->prev();
}
// its value is less than the first
if(!current) {
node->next() = begin_;
begin_->prev() = node;
begin_ = node;
}
}
count_++;
return node;
}
// insert a new node by sorting
linklist_node *insert_sort(const T& data) {
linklist_node *node = new linklist_node(data);
if(!node) return 0;
if(!begin_) {
begin_ = node;
end_ = node;
}
else {
linklist_node *current = begin_;
while(current) {
if(data <= current->data()) {
if(current == begin_) {
node->next() = begin_;
begin_->prev() = node;
begin_ = node;
}
else {
node->next() = current;
node->prev() = current->prev();
if(current->prev()) current->prev()->next() = node;
current->prev() = node;
}
break;
}
current = current->next();
}
// its value is greater than the last
if(!current) {
node->prev() = end_;
end_->next() = node;
end_ = node;
}
}
count_++;
return node;
}
// find the node
linklist_node *find(const T& data, linklist_node *at = 0) {
if(!at) at = begin_;
if(!at) return 0; // no node to be searched
while(at) {
if(at->data() == data) {
return at;
}
at = at->next();
}
return 0;
}
// reverse find the node
linklist_node *reverse_find(const T& data, linklist_node *at = 0) {
if(!at) at = end_;
if(!at) return 0; // no node to be searched
while(at) {
if(at->data() == data) {
return at;
}
at = at->prev();
}
return 0;
}
// swap between a node and a node
int swap(linklist_node *first, linklist_node *second) {
if(!first || !second) return 1; // cannot swap
T temp = first->data();
first->data() = second->data();
second->data() = temp;
return 0;
}
// find the middle of two nodes
linklist_node *mid(linklist_node *first, linklist_node *last) {
linklist_node *m = first;
unsigned long count = 1;
while(m && m != last) {
m = m->next();
count++;
}
// get the middle node
m = first;
for(unsigned long l = 0; l < count/2; l++) {
m = m->next();
}
return m;
}
unsigned long pos(linklist_node *at) {
if(!at || !begin_) return 0; // no node
linklist_node *current = begin_;
unsigned long count = 1;
while(current) {
if(current == at) {
return count;
}
count++;
current = current->next();
}
return 0; // not found
}
unsigned long reverse_pos(linklist_node *at) {
if(!at || !end_) return 0; // no node
linklist_node *current = end_;
unsigned long count = count_;
while(current) {
if(current == at) {
return count;
}
count--;
current = current->prev();
}
return 0; // not found
}
}; // class linklist
}; // namespace mstd
#endif //linklist_h
///////////////////////////////////////////////////////////////////////////////
// test.cpp
// Author: Seree Rakwong
// Date: 8-NOV-10
// Purpose: Link list container
#include <iostream>
using namespace mstd;
using namespace std;
int main() {
linklist<int> list;
linklist<int>::linklist_node *node = list.insert_begin(30);
list.insert_rsort(50);
list.insert_rsort(40);
list.insert_rsort(20);
list.insert_rsort(10);
list.insert_rsort(60);
cout << "list all nodes..." << endl;
linklist<int>::linklist_node *current = list.begin();
while(current) {
cout << current->data() << endl;
current = current->next();
}
cout << "reverse find(50): ";
current = list.reverse_find(50);
if(current) cout << "found" << endl;
else cout << "not found" << endl;
cout << "list nodes left..." << endl;
list.remove_begin();
list.remove_end();
list.remove_at(node);
current = list.begin();
while(current) {
cout << current->data() << endl;
current = current->next();
}
cout << "find(50): ";
current = list.find(50);
if(current) cout << "found" << endl;
else cout << "not found" << endl;
list.swap(list.begin(), list.end());
current = list.begin();
while(current) {
cout << current->data() << endl;
current = current->next();
}
return 0;
}
