---

detree.h

Go to the documentation of this file.

//
//  detree.h
//
//  
//  begin       : Thu Feb 7 2002
//  copyright   : (C) 2002 by Solstice
//  email       : solstice@deninet.com
//

#ifndef DETREE_H
#define DETREE_H

#include <vector>
#include <stack>
#include <utility>

#ifndef null
#define null 0L
#endif

namespace deml
{
    template <class T> class tree
    {
        //  member classes
        private:
        
        class node
        {
            public:
            node(void);
            node(T);
            ~node(void);
            void clear(void);
            void append_child(T);
            void insert(T);
            void replace(T);
            T                   data;
            node*           next;
            node*           prev;
            node*           parent;
            node*           child_start;
            node*           child_end;
        };
        
        public:
        
        class iterator
        {
            public:
            iterator(void);
            iterator(const iterator& i);
            iterator& operator++(void);
            iterator& operator--(void);
            T operator*(void);
            T* operator->(void);
            bool operator==(const iterator&);
            bool operator!=(const iterator&);
            
            iterator step_in(void);
            iterator step_out(void);
            iterator begin(void);
            iterator end(void);
            bool valid(void);
            
            friend tree;
            private:
            iterator(node*);
            node*   current;
        };
        
        //  member functions
        public:
        
        iterator begin(void);       
        iterator end(void);     
        iterator append_child(iterator, T);
        iterator insert(iterator, T);
        iterator replace(iterator, T);
        iterator erase(iterator);
        
        //  data members
        friend iterator;
        private:
        
        node    treeRoot;
    };
    
    template<class T> tree<T>::iterator tree<T>::begin(void)
    {
        return iterator(&treeRoot);
    }
    
    template<class T> tree<T>::iterator tree<T>::end(void)
    {
        return iterator(&treeRoot);
    }
    
    template<class T> tree<T>::iterator tree<T>::append_child(iterator i, T data)
    {
        tree<T>::node* current = i.current;
        
        if(current != null)
        {
            current->append_child(data);
            return iterator(current->child_end);
        }
        
        return iterator(null);
    }
    
    template<class T> tree<T>::iterator tree<T>::insert(iterator i, T data)
    {
        tree<T>::node* n = i->current;
        
        if(n != null)
        {
            n->insert(data);
            return iterator(n->prev);
        }
        
        return iterator(null);
    }
    
    template<class T> tree<T>::iterator tree<T>::replace(iterator i, T data)
    {
        tree<T>::node* n = i.current;
        
        if(n != null)
            n->replace(data);
        
        return i;   
    }
    
    template<class T> tree<T>::iterator tree<T>::erase(iterator i)
    {
        node* n = i->current;
                
        if(n == null)
            return;
        
        if(n == &treeRoot)
            n->clear();
                
        if(n->prev != null)
            i->current = n->prev;
        else
            i->current = n->next;
            
        delete n;
        return i;
    }
    
    template<class T> tree<T>::iterator::iterator(void)
    {
        current = null;
    }
    
    template<class T> tree<T>::iterator::iterator(node* n)
    {
        current = n;
    }
    
    template<class T> tree<T>::iterator::iterator(const tree<T>::iterator& i)
    {
        current = i.current;
    }
    
    template<class T> tree<T>::iterator& tree<T>::iterator::operator++(void)
    {
        if(current->next != null)
            current = current->next;
        else
            current = null;
                    
        return (*this);
    }
    
    template<class T> tree<T>::iterator& tree<T>::iterator::operator--(void)
    {
        if(current->prev != null)
            current = current->prev;
        else
            current = null;
                    
        return (*this);
    }
    
    template<class T> T tree<T>::iterator::operator*(void)
    {
        return current->data;
    }

    template<class T> T* tree<T>::iterator::operator->(void)
    {
        return &current->data;
    }
    
    template<class T> bool tree<T>::iterator::operator==(const iterator& i)
    {
        if(i.current == current)
            return true;
            
        return false;
    }
    
    template<class T> bool tree<T>::iterator::operator!=(const iterator& i)
    {
        if(i.current != current)
            return true;
            
        return false;
    }
    
    template<class T> tree<T>::iterator tree<T>::iterator::step_in(void)
    {
        if(current == null)
            return (*this);
            
        if(current->child_start == null)
            return iterator(null);
        
        current = current->child_start;         
        return (*this);
    }
    
    template<class T> tree<T>::iterator tree<T>::iterator::step_out(void)
    {
        if(current == null)
            return (*this);
            
        if(current->parent == null)
            return iterator(null);
            
        current = current->parent;  
        return (*this);
    }
        
    template<class T> tree<T>::iterator tree<T>::iterator::begin(void)
    {
        if(current->parent == null)
            return current;
            
        node* parent = current->parent;
        
        return iterator(parent->child_start);
    }
    
    template<class T> tree<T>::iterator tree<T>::iterator::end(void)
    {
        if(current->parent == null)
            return current;
            
        node* parent = current->parent;
        
        return iterator(parent->child_end);
    }
    
    template<class T> bool tree<T>::iterator::valid(void)
    {
        if(current == null)
            return false;
            
        return true;
    }
    
    template<class T> tree<T>::node::node(void)
    {
        prev = null;
        next = null;
        parent = null;
        child_start = null;
        child_end = null;
    }
    
    template<class T> tree<T>::node::node(T value)
    {
        data = value;
        prev = null;
        next = null;
        parent = null;
        child_start = null;
        child_end = null;
    }
    
    template<class T> tree<T>::node::~node(void)
    {
        clear();
    }
    
    template<class T> void tree<T>::node::clear(void)
    {
        //  sever parent connection
        if(parent != null)
        {
            if(parent->child_start == this)
                parent->child_start = next;
                
            if(parent->child_end == this)
                parent->child_end = prev;
                
            parent = null;
        }
        
        //  remove this node from the list
        if(prev != null)
            prev->next = next;
            
        if(next != null)
            next->prev = prev;
        
        prev = next = null;
                
        //  progressivly delete the children
        tree<T>::node* current = child_start;
        while(current != null)
        {
            tree<T>::node* temp = current->next;
            delete current;
            current = temp;
        }   
    }
    
    template<class T> void tree<T>::node::append_child(T value)
    {
        node* n = new node(value);
        n->parent = this;
            
        if(child_start == null)
        {
            child_start = child_end = n;
            return;
        }
            
        n->prev = child_end;
        child_end->next = n;
        child_end = n;
    }
    
    template<class T> void tree<T>::node::insert(T value)
    {
        tree<T>::node* n = new node(value);
        n->prev = prev;
        n->next = this;
        
        if(prev != null)
            prev->next = n;
        else
            parent->child_start = n;
        
        prev = n;
    }
    
    template<class T> void tree<T>::node::replace(T value)
    {
        data = value;
    }
};

#endif

---