Templated Doubly Linked List Problem

[JCSmith]

Okay, so I've been working on an assignment for a few days, it is a doubly list and I seem to be getting an infinite loop in my program. I believe the cause to be in my insert_after function (lines 149-151). Debugging used gdb is telling me that nextfield is pointing to the iterator spot but that should be previousfield I believe as it is in the the construction of my node class but I can't seem to figure out how to fix this loop.

Would really appreciate the help!

  </* dnode class*/
#ifndef DNODE_H
#define DNODE_H
#include <iostream>

template <class T>
class dnode {
        public:
                dnode(T d = T(), dnode *n = NULL, dnode *p = NULL)
                {datafield = d; nextfield = n; previousfield = p;}

                void set_next(dnode *n) {nextfield = n;}
                void set_prev(dnode *p) {previousfield = p;}
                void set_data(T d) {datafield = d;}

                dnode *next() {return nextfield;}
                dnode *prev() {return previousfield;}
                T data() {return datafield;}

                const dnode *next() const{return nextfield;}
                const dnode *prev() const{return previousfield;}
                const T data() const{return datafield;}

        private:
                dnode *nextfield;
                dnode *previousfield;
                T datafield;
};

#endif 

<#ifndef DLIST_H
#define DLIST_H
#include <iostream>
#include "dnode.h"
#include "node_iterator.h"

template <class T>
class dlist {
        public:
            typedef node_iterator<T> iterator; //
            typedef node_iterator<T> const_iterator;//

            dlist(dnode<T> *h = NULL, dnode<T> *t = NULL) {head = h; tail = t;}
            ~dlist(); //

            dlist(const dlist& other);//
            dlist& operator =(const dlist& other);//

            void front_insert(const T& item);//
            void front_remove();//
            void rear_insert(const T& item);//
            void rear_remove();//
            void show();//

            iterator begin() {return iterator(head);}
            const_iterator begin() const{return const_iterator(head);}

            iterator end() {return iterator();}
            const_iterator end() const{return const_iterator();}

            iterator r_begin() {return iterator(tail);}
            const_iterator r_begin() const{return const_iterator(tail);}

            iterator r_end() {return iterator(head->prev());}
            const_iterator r_end() const {return const_iterator(head->prev());}

            void insert_before(iterator spot, T item);//
            void insert_after(iterator spot, T item);//
            void remove(iterator spot);//

            int size();

        private:
            dnode<T> *head;
            dnode<T> *tail;
};

#include "dlist.template"

#endif>

<template <class T>
dlist<T>::~dlist(){
        dnode<T> *cur;

        while(head != NULL){
                cur = head->next();
                delete head;
                head = cur;
        }
        tail = NULL;
}


template <class T>
dlist<T>::dlist(const dlist<T>& other){
        if(!other.head)
                head = tail = NULL;
        else{
                head = new dnode<T>(other.head->data());

                dnode<T> *dest = head;
                dnode<T> *source = other.head;

                while(source != NULL){
                        dest->set_next(new dnode<T>);
                        dest = dest->next();
                        dest->set_data(source->data());
                        source = source->next(); //
                }
                dest->set_next(NULL);
                tail = dest;
        }
        
        
}

template <class T>
dlist<T>& dlist<T>::operator =(const dlist<T>& other){
        if(this == &other)
                return *this;

        dnode<T> *rmptr;

        while(head != NULL){
                rmptr = head;
                head = head->next();
                delete rmptr;
        }

        tail = NULL;
        const dnode<T> *source = other.head;

        while(source != NULL){
                rear_insert(source->data());
                source = source->next();
        }
}

template <class T>
void dlist<T>::show()
{
	dnode<T> *new_head = head;
	dnode<T> *temp;
	
	while(new_head != NULL)
	{
		std::cout << new_head->next();
		new_head = new_head->next();
	}
}

template <class T>
void dlist<T>::front_insert(const T& item){
        if(head == NULL)
                head = tail = new dnode<T>(item);
        else if(head == tail){
                head = new dnode<T>(item);
                head->set_next(tail);
                tail->set_prev(head);
        }else{
                dnode<T> *old_head = head;
                head = new dnode<T>(item);
                head->set_next(old_head);
                old_head->set_prev(head);
        }
}

template <class T>
void dlist<T>::front_remove(){
        iterator rmspot = head;
        remove(rmspot);
}

template <class T>
void dlist<T>::rear_insert(const T& item){
        if(head == NULL)
                head = tail = new dnode<T>(item);
        else if(head == tail){
                tail = new dnode<T>(item);
                tail->set_prev(head);
                head->set_next(tail);
        }else{
                dnode<T> *old_tail = tail;
                tail = new dnode<T>(item);
                tail->set_prev(old_tail);
                old_tail->set_next(tail);
        }
}

template <class T>
void dlist<T>::rear_remove(){
        iterator rmspot = tail;
        remove(rmspot);
}

template <class T>
void dlist<T>::insert_before(iterator spot, T item){
        if(head == NULL)
                head = tail = new dnode<T>(item);
        else if(spot == end())
				front_insert(item);
        else if(head == tail){
                head = new dnode<T>(item);
                tail->set_prev(head);
                head->set_next(tail);
        }else if(head == spot.current)
                front_insert(item);
        else if(spot.current != NULL){
                dnode<T> *s = spot.current;
                dnode<T> *new_node = new dnode<T>(item, s, s->prev());
                s->prev()->set_next(new_node);
                s->set_prev(new_node);
        }
    
}

template <class T>
void dlist<T>::insert_after(iterator spot, T item){
        if(head == NULL)
                head = tail = new dnode<T>(item);
        else if(spot == end())
				rear_insert(item);
        else if(head == tail){
                tail = new dnode<T>(item);
                head->set_next(tail);
                tail->set_prev(head);
        }else if(spot.current == tail)
                rear_insert(item);
        else if(spot.current != NULL){
                dnode<T> *s = spot.current; // current = 0x2a628
                dnode<T> *new_node = new dnode<T>(item, s->next(), s);
                s->next()->set_prev(new_node); //new_node = {nextfield = 0x2a628, previousfield = 0x2a678}
                s->set_next(new_node);
        }
}

template <class T>
void dlist<T>::remove(iterator spot){
        dnode<T> *rmptr = spot.current;

        if(rmptr){
                if(head == NULL)
                        std::cout << "Can't remove anything, list is empty.\n";
                else if(rmptr == head && rmptr == tail){
                        delete rmptr;
                        head = tail = NULL;
                }else if(rmptr == head){
                        dnode<T> *new_head = head;
                        head = head->next();
                        delete new_head;
                        head->set_prev(NULL);
                }else if(rmptr == tail){
                        dnode<T> *new_tail = tail;
                        tail = tail->prev();
                        tail->set_next(NULL);
                        delete new_tail;
                        new_tail = NULL;
                }else{
                        rmptr->prev()->set_next(rmptr->next());
                        rmptr->next()->set_prev(rmptr->prev());
                        delete rmptr;
                        rmptr = NULL;
                }
        }
}

template <class T>
int dlist<T>::size(){
        int len = 0;
        dnode<T> *new_head = head;

        while(new_head != NULL)
		{
                len++;
                new_head = new_head->next();
        }

        return len;
}>

[JCSmith]

Sorry! The problem lines are on (152-154) mistake in formatting.

[JCSmith]

Also! Here is my main for this program.

#include <fstream>
#include "dlist.h"
#include "swatch.h"
#include "node_iterator.h"

using namespace std; 

int main() 
{	
	dlist<Swatch> swatches;
	dlist<Swatch>::iterator it; 
	ifstream fin; 
	fin.open("swatches.txt"); 
	if (fin.fail())
	{
		cout << "Could not open input file." << endl; 
		return 1; 
	}
	Swatch tmp; 
	while (fin >> tmp)
	{
		int red = tmp.get_red(); 
		int green = tmp.get_green(); 
		int blue = tmp.get_blue(); 
		
		if ( (red>=green) && (red>=blue) ) // red is dominant
		{
			swatches.front_insert(tmp); 
		}
		else if ( (green >= red) && (green >= blue) ) 
				// green is dominant
		{
			swatches.rear_insert(tmp); 
		}
		else // blue is dominant
		{
		   it = swatches.begin();
		   for(int i = 0;i < swatches.size()/2;i++)
			++it; // loop moves iterator to the middle
		   if(swatches.size()%2 == 1){
			if(swatches.size()>2){
			it++;
			}
			swatches.insert_before(it,tmp);
		   }
		   else{
			swatches.insert_after(it,tmp);
		   }
		}
	}
	fin.close(); 

	dlist<Swatch> copy(swatches); // make a copy
	
	// remove the front, back, and centermost swatch from the copy
	copy.front_remove(); 
	copy.rear_remove(); 
	it = copy.begin();
	for(int i =0; i < copy.size()/2; ++i)
		++it;
	if(copy.size()%2 ==1) ++it; // if list has a true middle
					// step up into it
	copy.remove(it);
	
	
	// output the original list frontwards
	for (dlist<Swatch>::iterator i=swatches.begin(); i != swatches.end(); ++i)
	{
		cout << *i << endl; 
	}
	
	cout << endl << endl; // some space
	
	// output the copy frontwards
	for (dlist<Swatch>::iterator i=copy.begin(); i != copy.end(); ++i)
	{
		cout << *i << endl; 
	}

	cout << endl << endl; // some space

	// output the original backwards
	for (dlist<Swatch>::iterator i=swatches.r_begin(); i != swatches.r_end(); --i)
	{
		cout << *i << endl; 
	}
	
	cout << endl << endl; // some space

	// destroy the original list by alternating between removal of first and 
	// last items.  Print each item as it is removed
	int counter=0; 
	while (swatches.size() > 1)//0
	{
		if (swatches.begin() != NULL)
			cout<<*swatches.begin()<<endl;
		swatches.front_remove();
	
		 if(swatches.r_begin() != NULL)//if(swatches.size() > 0){
		    cout<<*swatches.r_begin()<<endl;
		swatches.rear_remove();
	}

	cout << endl << endl; // some space

	// output the copy backwards
	for (dlist<Swatch>::iterator i=copy.r_begin(); i != copy.r_end(); --i)
	{
		cout << *i << endl; 
	}

	return 0; 
}

[codewalker]

the problem is in while (fin >> tmp)
The ifstream operator >> has no way of knowing how to read class from text.
You need to overload the >> oprator or input individual members of the class using >>

If the member itself is a class then you will need to input the members of that class using >> (or obviously overload >> for that class too)

[dhayden]

Your copy constructor doesn't work. It needs to set the prev pointers.

I think end() isn't right because insert_after(end()) won't work.

Can you post the definition of iterator?

template <class T>
void dlist<T>::insert_before(iterator spot, T item){
        if(head == NULL)
                head = tail = new dnode<T>(item);
        else if(spot == end())
				front_insert(item);

Shouldn't insert_before(end(), item) put the item at the end of the list? You're putting at the beginning.