CRITIQUES WELCOME!
Posted: Mon Aug 20, 2007 2:41 pm
In a previous post, I asked for some help on my template linked-list program. Well between watching my daughter and going to the hospital (after a bad accident), I've managed to get quite a bit done. I know some of the functions are probably a bit overkill, but my goal was to learn how to write a template, and to refresh myself on linked-lists. One thing I'm really stuck on is the list copy constructor. Any help, comments, critiques, etc. are most welcome.
Thanx to all!
Thanx to all!
Code: Select all
template <typename T> class dlist{
struct type{
T data;
type *prev, *next;
type(const T& x, type* y = 0, type* z = 0) : data(x), prev(y), next(z) {}
type(const type& src) : data(src.data), prev(src.prev), next(src.next) {}
type& operator=(const type& src){
if(this != &src){
type* x, y;
try{
x = new type(*src.prev);
y = new type(*src.next);
}
catch(...){
delete x, y;
throw;
}
delete prev, next;
x = src.prev;
y = src.next;
}
return *this;
}
};
type *head, *tail;
public:
dlist() : head(new type(T())), tail(new type(T())) {}
dlist(const dlist& src);
~dlist(){ clear(); delete head; delete tail; }
bool empty();
unsigned int size();
bool sorted();
bool prox(const T&);
void makef(const T&);
void pushf(const T&);
void pushb(const T&);
void popf();
void popb();
void insert(const T&);
void revins(const T&);
void ins(const T&);
void remove(const T&);
void revrem(const T&);
void rem(const T&);
void remall(const T&);
void dis();
void revdis();
void sort();
void revsort();
void rev();
bool search(const T&);
void consearch(const T&);
void clear();
};
const bool HEAD = 1;
template <typename T> inline bool dlist<T>::empty(){
bool b = ((head->next == 0 && tail->prev == 0) || (head->next == tail && tail->prev == head)) ? 1 : 0;
return b;
}
template <typename T> inline bool dlist<T>::sorted(){
bool sortd;
type *curr, *p;
curr = (head->next)->next;
p = head->next;
while(p->data <= curr->data && curr != tail){
p = curr;
curr = curr->next;
}
sortd = (curr == tail) ? 1 : 0;
return sortd;
}
template <typename T> inline bool dlist<T>::prox(const T& x){
if(!empty()){
T diff1 = ((head->next)->data) - x;
T diff2 = ((tail->prev)->data) - x;
diff1 = (diff1 < 0) ? diff1 * -1 : diff1;
diff2 = (diff2 < 0) ? diff2 * -1 : diff2;
if(diff1 <= diff2){
return 1;
}
else{ return 0; }
}
}
template <typename T> inline void dlist<T>::clear(){
while(!empty()){
if(!empty()){ popf(); }
if(!empty()){ popb(); }
}
}
template <typename T> inline unsigned int dlist<T>::size(){
if(!empty()){
type* curr = head->next;
unsigned int x = 0;
while(curr != tail){
curr = curr->next;
x++;
}
return x;
}
else{ return 0; }
}
template <typename T> inline void dlist<T>::makef(const T& x){
type* temp = new type(x);
head->next = temp;
tail->prev = temp;
temp->prev = head;
temp->next = tail;
}
template <typename T> inline void dlist<T>::pushf(const T& x){
if(!empty()){
type *temp = new type(x);
temp->next = head->next;
temp->prev = head;
head->next = temp;
(temp->next)->prev = temp;
}
else{ makef(x); }
}
template <typename T> inline void dlist<T>::pushb(const T& x){
if(!empty()){
type* temp = new type(x);
temp->prev = tail->prev;
temp->next = tail;
tail->prev = temp;
(temp->prev)->next = temp;
}
else{ makef(x); }
}
template <typename T> inline void dlist<T>::popf(){
if(!empty()){
type* temp = head->next;
head->next = temp->next;
(temp->next)->prev = head;
delete temp;
}
}
template <typename T> inline void dlist<T>::popb(){
if(!empty()){
type* temp = tail->prev;
tail->prev = temp->prev;
(temp->prev)->next = tail;
delete temp;
}
}
template <typename T> void dlist<T>::insert(const T& x){
if(!empty()){
if(!sorted()){ sort(); }
type *curr, *temp;
curr = head->next;
temp = new type(x);
while(curr != tail && curr->data <=x){
curr = curr->next;
}
if(curr == head->next){ pushf(x); }
else if(curr == tail){ pushb(x); }
else{
temp->prev = curr->prev;
(curr->prev)->next = temp;
temp->next = curr;
curr->prev = temp;
}
}
else{ makef(x); }
}
template <typename T> void dlist<T>::revins(const T& x){
if(!empty()){
if(!sorted()){ sort(); }
type *curr, *temp;
curr = tail->prev;
temp = new type(x);
while(curr != head && curr->data >= x){
curr = curr->prev;
}
if(curr == tail->prev){ pushb(x); }
else if(curr == head){ pushf(x); }
else{
temp->next = curr->next;
(curr->next)->prev = temp;
temp->prev = curr;
curr->next = temp;
}
}
else{ makef(x); }
}
template <typename T> void dlist<T>::ins(const T& x){
unsigned int sz = size();
if(!(sz > 1 )){ insert(x); }
else{
if(prox(x) == HEAD){ insert(x); }
else{ revins(x); }
}
}
template <typename T> void dlist<T>::remove(const T& x){
if(!empty()){
int sz = size();
bool found = search(x);
if(found){
if(sz == 1){ popf(); }
else{
type* curr = head->next;
while(curr != tail && curr->data != x){
curr = curr->next;
}
if(curr == head->next){ popf(); }
else if(curr == tail->prev){ popb(); }
else{
(curr->prev)->next = curr->next;
(curr->next)->prev = curr->prev;
delete curr;
}
}
}
}
}
template <typename T> void dlist<T>::revrem(const T& x){
if(!empty()){
int sz = size();
bool found = search(x);
if(found){
if(sz == 1){ popf(); }
else{
type* curr = tail->prev;
while(curr != head && curr->data != x){
curr = curr->prev;
}
if(curr == tail->prev){ popb(); }
else if(curr == head->next){ popf(); }
else{
(curr->next)->prev = curr->prev;
(curr->prev)->next = curr->next;
delete curr;
}
}
}
}
}
template <typename T> void dlist<T>::rem(const T& x){
unsigned int sz = size();
if(!(sz > 1 )){ clear(); }
else{
if(prox(x) == HEAD){ remove(x); }
else{ revrem(x); }
}
}
template <typename T> void dlist<T>::remall(const T& x){
bool found = search(x);
if(found){
while(found){
rem(x);
found = search(x);
}
}
}
template <typename T> void dlist<T>::consearch(const T& x){
bool found = 0;
if(!empty()){
type* curr = head->next;
unsigned int position = 1;
while(curr != tail){
if(curr->data == x){
std::cout << "SEARCH: Found at position " << position << "." << std::endl;
found = 1;
}
curr = curr->next;
position++;
}
if(found != 1){
std::cout << "*FAILURE* SEARCH: Entry not found." << std::endl;
}
}
else{ std::cout << "*FAILURE* SEARCH: Empty list." << std::endl; }
}
template <typename T> bool dlist<T>::search(const T& x){
bool found = 0;
if(!empty()){
type* curr = head->next;
unsigned int position = 1;
while(curr != tail){
if(curr->data == x){
found = 1;
}
curr = curr->next;
position++;
}
}
return found;
}
template <typename T> void dlist<T>::dis(){
if(!empty()){
type* curr = head->next;
while(curr != tail){
std::cout << curr->data << std::endl;
curr = curr->next;
}
}
}
template <typename T> void dlist<T>::revdis(){
if(!empty()){
type* curr = tail->prev;
while(curr != head){
std::cout << curr->data << std::endl;
curr = curr->prev;
}
}
}
template <typename T> void dlist<T>::sort(){
if(!empty()){
type *curr, *p;
curr = (head->next)->next;
p = head->next;
while(curr != tail){
if(curr->data < p->data){
p->next = curr->next;
curr->prev = p->prev;
curr->next = p;
p->prev = curr;
(curr->prev)->next = curr;
(p->next)->prev = p;
curr = (head->next)->next;
p = head->next;
}
else{
p = curr;
curr = curr->next;
}
}
}
}
template <typename T> void dlist<T>::revsort(){
if(!empty()){
type *curr, *p;
curr = (head->next)->next;
p = head->next;
while(curr != tail){
if(curr->data > p->data){
p->next = curr->next;
curr->prev = p->prev;
curr->next = p;
p->prev = curr;
(curr->prev)->next = curr;
(p->next)->prev = p;
curr = (head->next)->next;
p = head->next;
}
else{
p = curr;
curr = curr->next;
}
}
}
}
template <typename T> void dlist<T>::rev(){
if(!empty()){
type* curr = head->next;
int sz = size();
while(curr != tail){
T temp = curr->data;
pushfront(temp);
curr = curr->next;
}
for(int i = 0; i < sz; i++){
popb();
}
}
}
