C++: дерево
От: m.a.g. Мальта http://dottedmag.net/
Дата: 14.02.03 12:31
Оценка: 63 (9) -2
Hi.

STL-like дерево. Копирайт, к сожалению, утерян.

///////////////////////////////////////////////////////////////////////////////
//  дерево.
//
#ifndef _tree_H_
#define _tree_H_

/*/

Главная фича: в итератор tree::iterator были добавлены функции
begin() и end() для получения итераторов child списка.

----------------
Краткое описание:

tree<> шаблон трехсвязного (вперед, назад, папа) дерева. Шаблон использует парадигму stl
контейнеров, для организации иерархических структур данных, типа TreeCtrl. Определен в
пространстве имен std.
Для вставки, итерирования по дереву используются bidirectional 
итераторы (реализованы операторы ++ и --):
iterator( const_iterator) - позволяет последовательно перебирать потомков одного узла. 
branch_iterator( const_branch_iterator) - позволяет делать полный
обход дерева или обход всех childoв для элемента
Есть соответствующие им reverse итераторы.

Кроме того у итератора есть методы:
parent() - возвращает итератор - выщестоящий элемент
level() - возвращает уровень элемента в иерархии (0 для tree.begin())
begin() - возвращает итератор первого элемента списка childов
end() - возвращает итератор конца списка childов
size() - возвращает число childов
У branch_iterator есть метод:
scipchild() - Следующий элемент без итерирования по childам

Шаблон tree<> содержит методы:
begin() - возвращает итератор начала списка верхнего уровня иерархии
end() - возвращает итератор конца списка верхнего уровня иерархии
insert() - добавление
erase()  - удаление элемента вместе со списком childoв
move()   - перемещение элемента вместе со списком childoв в другое место
дерева или в другое дерево
copy()  - копирование элемента вместе со списком childoв в другое место
дерева или в другое дерево

Кроме того файл содержит шаблонные функции операций с двусвязными списками с головным элементом:
inithead() - Инициализировать головной элемент списка
insertbefore() - Вставляет элемент insertnode до элемента marknode
insertafter() - Вставляет элемент insertnode после элемента marknode
swap() - Заменяет oldnode на newnode
erase() - Удаляет элемент из списка


Дерево можно представить в следующем виде:
 A1
  B11
   C111
   C112
  B12
  B13
 A2
  B21
   C211
  B22
 A3
  B31
    С311

A1-A3 - Элементы верхнего уровня
Доступ к элементам верхнего уровня аналогичен доступу к элементам
списка. 

// Перебор элементов верхнего(первого) уровня
tree::iterator it = thetree.begin();
for( ; it != thetree.end(); it++)
{
    ...
}

Элементы имеющие один парент-элемент тоже представляют из себя 
двусвязный список. Доступ к ним может быть получен 
следующим образом:

tree::iterator it = parent.begin();
for( ; it != parent.end(); it++)
{
    ...
}

Для обхода всех элементов дерева используется branch_iterator.
Итерирование будет произведено в порядке показаном на примере дерева.

tag_tree::branch_iterator it = thetree.begin();
for( ; it!=thetree.end(); it++)
{
    ...
}


/*/
#include <iterator>

namespace insidelist
{
    // список с головным элементом
    // в классе node (N), должны быть определены ф-ции:
    // N*& next() и N*& prev()

    // Инициализировать головной элемент списка
    template <class N>
        inline void inithead(N& headnode)
    {
        // Инициализация нового списка:
        headnode.next() = &headnode;
        headnode.prev() = &headnode;
    }

    // Вставляет элемент insertnode до элемента marknode
    template <class N>
        inline void insertbefore(N& insertnode, N& marknode)
    {
        insertnode.prev() = marknode.prev();
        insertnode.next() = &marknode;
        marknode.prev() = &insertnode;
        N* prevnode = insertnode.prev();
        prevnode->next() = &insertnode;
    }

    // Вставляет элемент insertnode после элемента marknode
    template <class N>
        inline void insertafter(N& insertnode, N& marknode)
    {
        insertnode.next() = marknode.next();
        insertnode.prev() = &marknode;
        marknode.next() = &insertnode;
        N* nextnode = insertnode.next();
        nextnode->prev() = &insertnode;
    }

    // Заменяет oldnode на newnode
    template <class N>
        inline void swap(N& oldnode, N& newnode)
    {
        if(oldnode.next()==&oldnode || oldnode.prev()==&oldnode)
        {
            inithead( newnode);
            return;
        }
        oldnode.next()->prev() = &newnode;
        newnode.next() = oldnode.next();
        oldnode.prev()->next() = &newnode;
        newnode.prev() = oldnode.prev();
    }

    // Удалить элемент из списка
    template <class N>
        inline bool erase(N& node)
    {
        if(node.next()==&node || node.prev()==&node) return false;
        N* nextnode = node.next();
        N* prevnode = node.prev();
        nextnode->prev() = prevnode;
        prevnode->next() = nextnode;
        return true;
    }
};

namespace std
{
using namespace insidelist;

template<class T>
class tree 
{
    struct node;
    typedef const T& const_reference;
    typedef const T* const_pointer;
    typedef T& reference;
    typedef T* pointer;
    
    class listnode
    {
        listnode* pnext;
        listnode* pprev;
    public:
        typedef listnode* plistnode;
        unsigned char index;
        plistnode& next(){return pnext;}
        plistnode& prev(){return pprev;}
        const plistnode& next()const {return pnext;}
        const plistnode& prev()const {return pprev;}
    };
    struct node
    {
        // Первый - элемент в sibling списке
        // Второй - головной элемент в child списке
        listnode links[2];
        // Значение
        T value;
        node():value()
        {
            links[0].index = 0;
            links[1].index = 1;
            inithead(links[1]);
        }
        node(const T& val):value(val)
        {
            links[0].index = 0;
            links[1].index = 1;
            insidelist::inithead(links[1]);
        }
        static node* getnode(listnode* lnode)
        {
            if( lnode->index>=2) return NULL; // ошибка
            lnode -= lnode->index;
            return (node*)lnode;
        }
    };
protected:
    // вершина дерева
    listnode head;

public:
    // CLASS const_iterator
    class const_iterator;
    class iterator;
    class const_branch_iterator;
    class branch_iterator;

    friend class tree::const_iterator;

    // reverse_iterator
    typedef reverse_bidirectional_iterator<iterator, T>
        reverse_iterator;
    // const_reverse_iterator
    typedef reverse_bidirectional_iterator<const_iterator, T> 
        const_reverse_iterator;
    // reverse_branch_iterator
    typedef reverse_bidirectional_iterator<branch_iterator, T>
        reverse_branch_iterator;
    // const_reverse_branch_iterator
    typedef reverse_bidirectional_iterator<const_branch_iterator, T>
        const_reverse_branch_iterator;

    explicit tree()
    {
        insidelist::inithead(head);
        head.index = 2;
    }
    tree(const tree& src)
    {
        insidelist::inithead(head);
        head.index = 2;
        *this = src;
    }
    tree& operator=(const tree& src)
    {
        clear();
        const_iterator from = src.begin();
        for( ; from != src.end(); from++) 
            copy(from, end());
        return *this;
    }
    ~tree(){clear();}

    // Пусто?
    bool empty(){return (head.begin() == &head);}
    // Вычистить все
    void clear(){for( ; begin()!=end(); ) erase(begin());}

    // Обычные итераторы
    const_iterator begin()const{return const_iterator( head.next());}
    const_iterator end()const{return const_iterator( &head);}
    iterator begin(){return iterator( head.next());}
    iterator end(){return iterator( &head);}

    // Обратные итераторы
    const_reverse_iterator rbegin()const{return const_reverse_iterator(end());}
    const_reverse_iterator rend()const{return const_reverse_iterator(begin());}
    reverse_iterator rbegin(){return reverse_iterator(end());}
    reverse_iterator rend(){return reverse_iterator(begin());}

    // Добавляет элемент того же уровня sibling
    iterator insert(iterator before_it, const T& value=T())
    {
        node* newnode = new node(value);
        insidelist::insertbefore(newnode->links[0], *before_it.plistnode);
        return iterator(&(newnode->links[0]));
    }
    // Добавляет элемент верхнего уровня
    // Все sibling элементы станут его childами
    iterator insertparent(iterator parent_for_it, const T& value=T())
    {
        return insertchild(parent_for_it.parent(), value);
    }
    // Добавляет элемент нижнего уровня
    // Все child элементы станут childами вставленного элемента
    iterator insertchild(iterator child_for_it, const T& value=T())
    {
        listnode* pparentnode = &head;
        node* parent = child_for_it.Node();
        if( parent) pparentnode = &parent->links[1];
        node* newnode = new node(value);
        insidelist::swap( *pparentnode, newnode->links[1]);
        insidelist::inithead( *pparentnode);
        insidelist::insertbefore(newnode->links[0], *pparentnode);
        return iterator(&(newnode->links[0]));
    }
    // Удалить элемент вместе с его childами
    iterator erase(iterator it)
    {
        if( it.IsEnd()) throw "Нельзя удалить такой элемент";

        // Обход childов в обратном порядке
        branch_iterator bit = it, endbit = it;
        iterator retit = it; retit++;
        bit = bit.scipchild();
        for( bit--; bit!=endbit; )
        {
            // Удаляемый элемент - гарантируется, что у него нет childов
            branch_iterator erit = bit;
            bit--;
            // Удалить
            node* pnode = erit.Node();
            if( erit.begin()!=erit.end()) throw "Ошибка при удалении";
            if( !insidelist::erase( pnode->links[0])) throw "Ошибка при удалении";
            delete pnode;
        }
        node* pnode = it.Node();
        if( !pnode) return retit;
        if( !insidelist::erase( pnode->links[0])) return retit;
        delete pnode;
        return retit;
    }
    // Переместить элемент вместе с childами
    iterator move(iterator from_it, iterator to_it)
    {
        if( from_it.IsEnd()) return from_it;
        iterator retit = from_it; retit++;
        // Надо проверить не является ли point_it childом target_it
        iterator temp(to_it);
        for( ; !temp.IsTreeEnd(); temp = temp.parent())
            if(temp.Node()==from_it.Node()) return retit;

        node* pnode = from_it.Node();
        // Выкинуть из текущего списка
        if( !insidelist::erase( pnode->links[0])) return retit;
        // Вставить в новое место
        insidelist::insertbefore(pnode->links[0], *(to_it.plistnode));
        return retit;
    }

    // Копировать элемент вместе с childами
    iterator copy(const_iterator from_it, iterator to_it)
    {
        const_iterator srcit = from_it;
        const_iterator endit = from_it; endit++;

        node* newnode = new node(*srcit);
        iterator dstit = iterator(&newnode->links[0]);
        dstit = dstit.begin();
        srcit = srcit.begin();
        for( ; srcit!=endit; )
        {
            if( !srcit.IsEnd())
            {
                dstit = insert(dstit, *srcit);
                if(srcit.end() != srcit.begin())
                {
                    srcit = srcit.begin();
                    dstit = dstit.begin();
                }
                else
                {
                    srcit++;
                    dstit++;
                }
                continue;
            }
            // К папе:
            srcit = srcit.parent();
            dstit = dstit.parent();
            srcit++;
            dstit++;
        }
        insidelist::insertbefore(newnode->links[0], *to_it.plistnode);
        return iterator(&(newnode->links[0]));
    }

    // Число элементов верхнего уровня
    int size() const
    {
        const_iterator it = begin();
        for( int size=0; it!=end(); it++, size++);
        return size;
    }

    // Надо проверить является ли it childoм itparent
    bool ischildof(const_iterator itparent, const_iterator it)
    {
        // Надо проверить не является ли point_it childом target_it
        iterator temp(it);
        for( ; !temp.IsTreeEnd(); temp = temp.parent())
            if(temp.Node()==itparent.Node()) return true;
        return false;
    }

    // Итератор для перебора элементов sibling одного parenta
    class const_iterator : public _Bidit<T, ptrdiff_t>
    {
    public:
        const_iterator():plistnode(NULL){}
        const_iterator(const listnode* _plistnode):plistnode((listnode*)_plistnode){}
        const_iterator(const const_iterator& it):plistnode(it.plistnode){}
        const_iterator& operator=(const const_iterator& it){this->const_iterator::const_iterator(it); return *this;}

        const_reference operator*() const
        {
            const node* pnode = node::getnode(plistnode);
            return pnode->value;
        }
        const_pointer operator->() const
        {
            const node* pnode = node::getnode(plistnode);
            return &pnode->value;
        }
        const_iterator& operator++()
        {
            plistnode = plistnode->next();
            return (*this); 
        }
        const_iterator operator++(int)
        {
            const_iterator _Tmp = *this;
            plistnode = plistnode->next();
            return (_Tmp); 
        }
        const_iterator& operator--()
        {
            plistnode = plistnode->prev();
            return (*this); 
        }
        const_iterator operator--(int)
        {
            const_iterator _Tmp = *this;
            --(*this);
            return (_Tmp); 
        }
        bool operator==(const const_iterator& it) const
        {
            return (plistnode == it.plistnode);
        }
        bool operator!=(const const_iterator& it) const
        {
            return (plistnode != it.plistnode);
        }
        bool operator<(const const_iterator& it) const
        {
            // Выровнять уровни
            const_iterator t1 = *this, t2 = it;
            for( ; t2.level()<t1.level(); ) t1 = t1.parent();
            for( ; t1.level()<t2.level(); ) t2 = t2.parent();
            // Пока не станут одинаковые parentы
            for( ; t1.parent()!=t2.parent(); ) 
                t2 = t2.parent(), t1.parent();
            if(t1 == t2) return false;
            const_iterator tt1 = t1, tt2 = t2;
            // Выяснить кто старше
            for( ; ; tt2++, tt1++)
            {
                if( tt1.IsEnd()) return false; // t2<t1
                if( tt2.IsEnd()) return true;  // t1<t2 
                if(tt2 == t1) return false; // t2<t1
                if(tt1 == t2) return true;  // t1<t2
            }
            return false;
        }
        bool operator<=(const const_iterator& it) const
        {
            if(*this==it) return true;
            return operator<(it);
        }
        bool operator>(const const_iterator& it) const
        {
            return !(operator<=(it));
        }
        bool operator>=(const const_iterator& it) const
        {
            return !(operator<(it));
        }
        const_iterator parent() const 
        {
            const_iterator it = *this;
            for( ; !it.IsEnd(); it++);
            if(it.IsTreeEnd()) return it;
            node* pnode = node::getnode(it.plistnode);
            return const_iterator( &pnode->links[0]);
        }
        const_iterator begin() const
        {
            if( IsEnd()) return *this;
            return (++end());
        }
        const_iterator end() const
        {
            if( IsEnd()) return *this;
            node* pnode = node::getnode(plistnode);
            return iterator( &pnode->links[1]);
        }
        int size() const
        {
            const_iterator it = begin();
            for( int size=0; it!=end(); it++, size++);
            return size;
        }
        long level() const
        {
            long level = 0;
            const_iterator par = parent();
            for(; !par.IsTreeEnd() ;level++)
                par = par.parent();
            return level;
        }

    // Служебные функции
    protected:
        node* Node(){return node::getnode(plistnode);}
        const node* Node()const{return node::getnode(plistnode);}
        bool IsEnd()const{return (plistnode->index!=0);}
        bool IsTreeEnd()const{return (plistnode->index==2);}
    protected:
        friend class tree<T>;
        listnode* plistnode;
    };

    // Итератор для перебора элементов sibling одного parenta
    class iterator : public const_iterator
    {
    public:
        iterator():const_iterator(){}
        iterator(listnode* _plistnode):const_iterator(_plistnode){}
        iterator(const iterator& it):const_iterator(it){}
        iterator(const branch_iterator& it):const_iterator(it){}
        iterator& operator=(const iterator& it){this->iterator::iterator(it); return *this;}
//      iterator& operator=(const branch_iterator& it){this->iterator::iterator(it); return *this;}

        reference operator*()
        {
            return Node()->value;
        }
        pointer operator->()
        {
            return &Node()->value;
        }
        iterator& operator++()
        {
            plistnode = plistnode->next();
            return (*this);
        }
        iterator operator++(int)
        {
            iterator _Tmp = *this;
            plistnode = plistnode->next();
            return (_Tmp);
        }
        iterator& operator--()
        {
            plistnode = plistnode->prev();
            return (*this);
        }
        iterator operator--(int)
        {
            iterator _Tmp = *this;
            --(*this);
            return (_Tmp);
        }

    // Дополнительные функции для иерархии
    public:
        iterator parent() const{const_iterator it = const_iterator::parent(); return *((iterator*)&it);}
        iterator begin() const{const_iterator it = const_iterator::begin(); return *((iterator*)&it);}
        iterator end() const{const_iterator it = const_iterator::end(); return *((iterator*)&it);}
    };

    // Итератор для полного обхода дерева
    class const_branch_iterator : public const_iterator
    {
    public:
        const_branch_iterator():const_iterator(){}
        const_branch_iterator(listnode* _plistnode):const_iterator(_plistnode){}
        const_branch_iterator(const const_iterator& it):const_iterator(it){}
        const_branch_iterator& operator=(const const_branch_iterator& it){this->const_iterator::const_iterator(it); return *this;}

        const_branch_iterator& operator++()
        {
            if( begin()!=end())
            {
                *this = begin();
                return *this;
            }
            for(;;)
            {
                if( IsEnd())
                {
                    // Конец списка child
                    // Перейти к верхнему эл-ту
                    if(IsTreeEnd()) return *this;
                    plistnode = &Node()->links[0];
                }
                plistnode = plistnode->next();
                if( !IsEnd()) return *this;
            }
            return (*this);
        }
        const_branch_iterator operator++(int)
        {
            iterator _Tmp = *this;
            ++(*this);
            return (_Tmp);
        }
        const_branch_iterator& operator--()
        {
            plistnode = plistnode->prev();
            if(!IsEnd())
            {
                // Спуститься до последнего childа
                for(;begin()!=end();)
                {
                    *this = end();
                    plistnode = plistnode->prev();
                }
            }
            else
            {
                // Вернуться к папе и вернуть его
                if(IsTreeEnd()) return *this;
                plistnode = &Node()->links[0];
                return *this;
            }
            return (*this); 
        }
        const_branch_iterator operator--(int)
        {
            branch_iterator _Tmp = *this;
            --(*this);
            return (_Tmp); 
        }
        // Следующий элемент без итерирования по childам
        const_branch_iterator scipchild() const
        {
            const_branch_iterator bit = end();
            return (++bit);
        }
    };

    class branch_iterator : public const_branch_iterator
    {
    public:
        branch_iterator():const_branch_iterator(){}
        branch_iterator(listnode* _plistnode):const_branch_iterator(_plistnode){}
        branch_iterator(const branch_iterator& it):const_branch_iterator(it){}
        branch_iterator(const iterator& it):const_branch_iterator(it){}
        branch_iterator& operator=(const branch_iterator& it){this->const_branch_iterator::const_branch_iterator(it); return *this;}
        branch_iterator& operator=(const iterator& it){this->const_branch_iterator::const_branch_iterator(it); return *this;}

        reference operator*()
        {
            return Node()->value;
        }
        pointer operator->()
        {
            return &Node()->value;
        }
        branch_iterator& operator++()
        {
            const_branch_iterator::operator++();
            return (*this);
        }
        branch_iterator operator++(int)
        {
            iterator _Tmp = *this; ++(*this); return (_Tmp);
        }
        branch_iterator& operator--()
        {
            const_branch_iterator::operator--();
            return (*this); 
        }
        branch_iterator operator--(int)
        {
            branch_iterator _Tmp = *this; --(*this); return (_Tmp); 
        }
        // Следующий элемент без итерирования по childам
        branch_iterator scipchild() const
        {
            return *((branch_iterator*)&const_branch_iterator::scipchild());
        }

    };

};

}

#endif
... << Rod Stewart [] Sailing >> ...
Re: C++: дерево
От: ssm  
Дата: 10.04.03 13:03
Оценка: +1
Здравствуйте, m.a.g., Вы писали:

MAG>STL-like дерево. Копирайт, к сожалению, утерян.


Судя по оценкам(я тоже вначале поставил, но потом удалил ) этот код должен быть работоспособен и нераз(опять же судя по оценкам) проверялся. Пытался и я попользовать приведенный код, но толком у меня ничего не вышло. Компилятор у меня gcc 2.95.3. В общем одни сплошные маты. Начал я разбираться, и много чего нашел сомнительного. Конечно этот код очень полезен с точки теории, но вот с точки реализации помоему слегка опасен. По крайней мере мне так показалось. Ну начнемс:


-Законно ли помещение tree в namespace std?
-Что хотел автор сказать делая конструктор tree::tree() explicit ?

-Пережитки прошлого?
    int size() const
    {
        const_iterator it = begin();
        for( int size=0; it!=end(); it++, size++);
        return size;
    }



-Тут имелось в виду std::bidirectional_iterator вместо _Bidit?
    class const_iterator : public _Bidit<T, ptrdiff_t>



Зачем передавать константу, чтобы потом снимать константность?
const_iterator::const_iterator(const listnode* _plistnode):plistnode((listnode*)_plistnode){}



Если учесть что plistnode — не константа, то как же:
const_iterator::const_iterator(const const_iterator& it):plistnode(it.plistnode){}


Что это вообще за странная запись, попытка вызова конструктора базового класса как функции?
const_iterator& const_iterator::operator=(const const_iterator& it){this->const_iterator::const_iterator(it); return *this;}



const_iterator ?
const_iterator const_iterator::end() const
{
  if( IsEnd()) return *this;
  node* pnode = node::getnode(plistnode);
  return iterator( &pnode->links[1]);
}



-Пережитки прошлого?
int const_iterator::size() const{
const_iterator it = begin();
for( int size=0; it!=end(); it++, size++);
return size;
}


???
iterator& iterator::operator=(const iterator& it){this->iterator::iterator(it); return *this;}



Как же так?
iterator iterator::parent() const{const_iterator it = const_iterator::parent(); return *((iterator*)&it);}
iterator iterator::begin() const{const_iterator it = const_iterator::begin(); return *((iterator*)&it);}
iterator iterator::end() const{const_iterator it = const_iterator::end(); return *((iterator*)&it);}



Дальше еще хуже
Какой же давности должен быть компилятор, чтобы он смог скомпилировать этот tree<> ? Или это я проезжаю?
http://www.rsdn.org/File/13021/angler.gif
Re[2]: C++: дерево(компилируемое)
От: ssm  
Дата: 17.04.03 11:59
Оценка: 15 (1)
Поковырялся на досуге, короче вот:


//tree.h

#ifndef __RSDN__TREE_H__
#define __RSDN__TREE_H__


/************************************************
  Изменение 17.04.2003 by rsdn::ssm :)
     -списковые операции вынесены в listop.h
     -tree определен в namespace rsdn
     -переделаны итераторы
     -вроде pure C++
     -тестировался на следующих компиляторах:
        -gcc 2.95(-ansi -pedantic -Wall -Wno-long-long)
        -MS Visual C++ 6
*************************************************/


/*
Главная фича: в итератор tree::iterator были добавлены функции
begin() и end() для получения итераторов child списка.

----------------
Краткое описание:

tree<> шаблон трехсвязного (вперед, назад, папа) дерева. Шаблон использует парадигму stl
контейнеров, для организации иерархических структур данных, типа TreeCtrl. Определен в
пространстве имен std.
Для вставки, итерирования по дереву используются bidirectional 
итераторы (реализованы операторы ++ и --):
iterator( const_iterator) - позволяет последовательно перебирать потомков одного узла. 
branch_iterator( const_branch_iterator) - позволяет делать полный
обход дерева или обход всех childoв для элемента
Есть соответствующие им reverse итераторы.

Кроме того у итератора есть методы:
parent() - возвращает итератор - выщестоящий элемент
level() - возвращает уровень элемента в иерархии (0 для tree.begin())
begin() - возвращает итератор первого элемента списка childов
end() - возвращает итератор конца списка childов
size() - возвращает число childов
У branch_iterator есть метод:
scipchild() - Следующий элемент без итерирования по childам

Шаблон tree<> содержит методы:
begin() - возвращает итератор начала списка верхнего уровня иерархии
end() - возвращает итератор конца списка верхнего уровня иерархии
insert() - добавление
erase()  - удаление элемента вместе со списком childoв
move()   - перемещение элемента вместе со списком childoв в другое место
дерева или в другое дерево
copy()  - копирование элемента вместе со списком childoв в другое место
дерева или в другое дерево

Кроме того файл содержит шаблонные функции операций с двусвязными списками с головным элементом:
inithead() - Инициализировать головной элемент списка
insertbefore() - Вставляет элемент insertnode до элемента marknode
insertafter() - Вставляет элемент insertnode после элемента marknode
swap() - Заменяет oldnode на newnode
erase() - Удаляет элемент из списка


Дерево можно представить в следующем виде:
 A1
  B11
   C111
   C112
  B12
  B13
 A2
  B21
   C211
  B22
 A3
  B31
    С311

A1-A3 - Элементы верхнего уровня
Доступ к элементам верхнего уровня аналогичен доступу к элементам
списка. 

// Перебор элементов верхнего(первого) уровня
tree::iterator it = thetree.begin();
for( ; it != thetree.end(); it++)
{
    ...
}

Элементы имеющие один парент-элемент тоже представляют из себя 
двусвязный список. Доступ к ним может быть получен 
следующим образом:

tree::iterator it = parent.begin();
for( ; it != parent.end(); it++)
{
    ...
}

Для обхода всех элементов дерева используется branch_iterator.
Итерирование будет произведено в порядке показаном на примере дерева.

tag_tree::branch_iterator it = thetree.begin();
for( ; it!=thetree.end(); it++)
{
    ...
}

*/



#include <iterator>
#include "listop.h"

//есть ли std::reverse_iterator?
#ifdef __GNU__
#    define _RSDN_HAS_REVERSE_ITERATOR
#endif

namespace rsdn{
    
template<typename T> class tree; 

class listnode
{
    listnode* pnext;
    listnode* pprev;
public:
    typedef listnode* plistnode;
    unsigned char index;
    plistnode& next(){return pnext;}
    plistnode& prev(){return pprev;}
    const plistnode& next()const {return pnext;}
    const plistnode& prev()const {return pprev;}
};

template<typename T>
struct NodeImpl
{
    // Первый - элемент в sibling списке
    // Второй - головной элемент в child списке
    listnode links[2];
    // Значение
    T value;
    NodeImpl():value()
    {
        links[0].index = 0;
        links[1].index = 1;
        insidelist::inithead(links[1]);
    }
    NodeImpl(const T& val):value(val)
    {
        links[0].index = 0;
        links[1].index = 1;
        insidelist::inithead(links[1]);
    }
    static NodeImpl* getnode(listnode* lnode)
    {
        if( lnode->index>=2) return NULL; // ошибка
        lnode -= lnode->index;
        return (NodeImpl*)lnode;
    }
};

template<typename T, typename TRef, typename TPtr>
struct _Iterator 
{
    typedef NodeImpl<T> node;
    
    typedef std::bidirectional_iterator_tag  iterator_category;
    typedef T                                value_type;
    typedef ptrdiff_t                        difference_type;
    typedef TPtr                             pointer;
    typedef TRef                             reference;

    typedef _Iterator<T, TRef, TPtr>            _Self;
    typedef _Iterator<T, T&, T*>                iterator;
    typedef _Iterator<T, const T&, const T*>    const_iterator;

public:
    _Iterator():plistnode(0){}
    _Iterator(listnode* plistnode):plistnode(plistnode){}
    _Iterator(const iterator& it):plistnode(it.plistnode){}
    
    _Iterator &operator=(const iterator& it){ plistnode = it.plistnode; return *this;}

    reference operator*(){return node::getnode(plistnode)->value;}
    pointer operator->(){return *(operator*());}
    
    _Iterator &operator++(){plistnode = plistnode->next(); return (*this);}
    _Iterator operator++(int){iterator _Tmp = *this; plistnode = plistnode->next(); return _Tmp;}
    _Iterator &operator--(){plistnode = plistnode->prev(); return (*this);}
    _Iterator operator--(int){iterator _Tmp = *this; --(*this); return (_Tmp); }
   
    bool operator==(const iterator& it) const  {return (plistnode == it.plistnode);}
    bool operator!=(const iterator& it) const  {return (plistnode != it.plistnode);}
    
    bool operator<(const iterator& it) const
    {
        // Выровнять уровни
        iterator t1 = *this, t2 = it;
        for( ; t2.level()<t1.level(); ) t1 = t1.parent();
        for( ; t1.level()<t2.level(); ) t2 = t2.parent();
        // Пока не станут одинаковые parentы
        for( ; t1.parent()!=t2.parent(); ) 
            t2 = t2.parent(), t1.parent();
        if(t1 == t2) return false;
        iterator tt1 = t1, tt2 = t2;
        // Выяснить кто старше
        for( ; ; tt2++, tt1++)
        {
            if( tt1.IsEnd()) return false; // t2<t1
            if( tt2.IsEnd()) return true;  // t1<t2 
            if(tt2 == t1) return false; // t2<t1
            if(tt1 == t2) return true;  // t1<t2
        }
        return false;
    }
    bool operator<=(const iterator& it) const {return (*this==it) ? true : operator<(it);}
    bool operator>(const iterator& it) const {return !(operator<=(it));}
    bool operator>=(const iterator& it) const {return !(operator<(it));}
    iterator parent() const 
    {
        iterator it = *this;
        for( ; !it.IsEnd(); it++);
        if(it.IsTreeEnd()) 
            return it;
        
        node* pnode = node::getnode(it.plistnode);
        return iterator( &pnode->links[0]);
    }
    iterator begin() const
    {
        if( IsEnd()) 
            return *this;
        
        return (++end());
    }
    iterator end() const
    {
        if( IsEnd()) 
            return *this;
        
        node* pnode = node::getnode(plistnode);
        return iterator( &pnode->links[1]);
    }
    int size() const
    {
        iterator it = begin();
        int size = 0;
        for( ; it!=end(); it++, size++);
        return size;
    }
    long level() const
    {
        long level = 0;
        iterator par = parent();
        for(; !par.IsTreeEnd() ;level++)
            par = par.parent();
        return level;
    }

// Служебные функции
protected:
    node* Node(){return node::getnode(plistnode);}
    const node* Node()const{return node::getnode(plistnode);}
    bool IsEnd()const{return (plistnode->index!=0);}
    bool IsTreeEnd()const{return (plistnode->index==2);}
public:
    listnode* plistnode;
    friend class rsdn::tree<T>;
};

 

// Итератор для полного обхода дерева
template<typename T, typename TRef, typename TPtr>
struct _BranchIterator : public _Iterator<T, TRef, TPtr>
{
    //std::iteratr 
    typedef std::bidirectional_iterator_tag         iterator_category;
    typedef T                                       value_type;
    typedef ptrdiff_t                               difference_type;
    typedef TPtr                                    pointer;
    typedef TRef                                    reference;

    typedef _BranchIterator<T, TRef, TPtr>          _Self;
    typedef _Iterator<T, TRef, TPtr>                   _Base;
    
    typedef _BranchIterator<T, T&, T*>              iterator;

public:
    _BranchIterator():_Base(){}
    _BranchIterator(listnode* _plistnode):_Base(_plistnode){}
    _BranchIterator(iterator& it):_Base(it){}
    _BranchIterator(const _Base &it) : _Base(it){}
    _BranchIterator &operator=(const _BranchIterator& it){
        _Base::operator=(it);
        return *this;
    }

    _BranchIterator& operator++()
    {
        if( this->begin()!= this->end())
        {
            *this = this->begin();
            return *this;
        }
        for(;;)
        {
            if( IsEnd())
            {
                // Конец списка child
                // Перейти к верхнему эл-ту
                if(IsTreeEnd()) return *this;
                plistnode = &Node()->links[0];
            }
            plistnode = plistnode->next();
            if( !IsEnd()) return *this;
        }
        return *this;
    }
    
    _BranchIterator operator++(int)
    {
        _BranchIterator _Tmp = *this;
        ++(*this);
        return _Tmp;
    }
    
    _BranchIterator &operator--()
    {
        plistnode = plistnode->prev();
        if(!IsEnd())
        {
            // Спуститься до последнего childа
            for(;this->begin()!=this->end();)
            {
                *this = this->end();
                plistnode = plistnode->prev();
            }
        }
        else
        {
            // Вернуться к папе и вернуть его
            if(IsTreeEnd()) return *this;
            plistnode = &Node()->links[0];
            return *this;
        }
        return *this; 
    }
    
    _BranchIterator operator--(int)
    {
        _BranchIterator _Tmp = *this;
        --(*this);
        return _Tmp; 
    }
    
    // Следующий элемент без итерирования по childам
    _BranchIterator scipchild() const
    {
        _BranchIterator bit = this->end();
        return ++bit;
    }

};


template<class T>
class tree 
{
    typedef const T& const_reference;
    typedef const T* const_pointer;
    typedef T& reference;
    typedef T* pointer;
    
protected:
    typedef NodeImpl<T> node;
    // вершина дерева
    listnode head;

public:
    typedef _Iterator<T, T&, T*>                            iterator;
    typedef typename iterator::const_iterator               const_iterator;
    typedef _BranchIterator<T, T&, T*>                      branch_iterator;
    typedef typename branch_iterator::const_iterator        const_branch_iterator;

#ifdef _RSDN_HAS_REVERSE_ITERATOR
    typedef std::reverse_iterator<iterator>                 reverse_iterator;
    typedef std::reverse_iterator<const_iterator>           const_reverse_iterator;
    typedef std::reverse_iterator<branch_iterator>          reverse_branch_iterator;
    typedef std::reverse_iterator<const_branch_iterator>    const_reverse_branch_iterator;
#else
    typedef std::reverse_bidirectional_iterator<iterator, T>   
        reverse_iterator;
    typedef std::reverse_bidirectional_iterator<const_iterator, T>
        const_reverse_iterator;
    typedef std::reverse_bidirectional_iterator<branch_iterator, T>       
        reverse_branch_iterator;
    typedef std::reverse_bidirectional_iterator<const_branch_iterator, T>   
        const_reverse_branch_iterator;
#endif

    explicit tree()
    {
        insidelist::inithead(head);
        head.index = 2;
    }
    tree(const tree& src)
    {
        rsdn::insidelist::inithead(head);
        head.index = 2;
        *this = src;
    }
    tree& operator=(const tree& src)
    {
        clear();
        const_iterator from = src.begin();
        for( ; from != src.end(); from++) 
            copy(from, end());
        return *this;
    }
    ~tree(){clear();}

    // Пусто?
    bool empty(){return (head.begin() == &head);}
    // Вычистить все
    void clear(){
        for( ; begin()!=end(); ) 
            erase(begin());
    }

    // Обычные итераторы
    const_iterator begin()const{return const_iterator( head.next());}
    const_iterator end()const{return const_iterator( &head);}
    iterator begin(){return iterator( head.next());}
    iterator end(){return iterator( &head);}

    // Обратные итераторы
    const_reverse_iterator rbegin()const{return const_reverse_iterator(end());}
    const_reverse_iterator rend()const{return const_reverse_iterator(begin());}
    reverse_iterator rbegin(){return reverse_iterator(end());}
    reverse_iterator rend(){return reverse_iterator(begin());}

    // Добавляет элемент того же уровня sibling
    iterator insert(iterator before_it, const T& value=T())
    {
        node* newnode = new node(value);
        insidelist::insertbefore(newnode->links[0], *before_it.plistnode);
        return iterator(&(newnode->links[0]));
    }
    // Добавляет элемент верхнего уровня
    // Все sibling элементы станут его childами
    iterator insertparent(iterator parent_for_it, const T& value=T())
    {
        return insertchild(parent_for_it.parent(), value);
    }
    // Добавляет элемент нижнего уровня
    // Все child элементы станут childами вставленного элемента
    iterator insertchild(iterator child_for_it, const T& value=T())
    {
        listnode* pparentnode = &head;
        node* parent = child_for_it.Node();
        if( parent) pparentnode = &parent->links[1];
        node* newnode = new node(value);
        insidelist::swap( *pparentnode, newnode->links[1]);
        insidelist::inithead( *pparentnode);
        insidelist::insertbefore(newnode->links[0], *pparentnode);
        return iterator(&(newnode->links[0]));
    }
    // Удалить элемент вместе с его childами
    iterator erase(iterator it)
    {
        if( it.IsEnd()) throw "Нельзя удалить такой элемент";
        // Обход childов в обратном порядке
        branch_iterator bit = it, endbit = it;
        iterator retit = it; retit++;
        bit = bit.scipchild();
        for( bit--; bit!=endbit; )
        {
            // Удаляемый элемент - гарантируется, что у него нет childов
            branch_iterator erit = bit;
            bit--;
            // Удалить
            node* pnode = erit.Node();
            if( erit.begin()!=erit.end()) throw "Ошибка при удалении";
            if( !insidelist::erase( pnode->links[0])) throw "Ошибка при удалении";
            delete pnode;
        }
        node* pnode = it.Node();
        if( !pnode) return retit;
        if( !insidelist::erase( pnode->links[0])) return retit;
        delete pnode;
        return retit;
    }
    // Переместить элемент вместе с childами
    iterator move(iterator from_it, iterator to_it)
    {
        if( from_it.IsEnd()) return from_it;
        iterator retit = from_it; retit++;
        // Надо проверить не является ли point_it childом target_it
        iterator temp(to_it);
        for( ; !temp.IsTreeEnd(); temp = temp.parent())
            if(temp.Node()==from_it.Node()) return retit;

        node* pnode = from_it.Node();
        // Выкинуть из текущего списка
        if( !insidelist::erase( pnode->links[0])) return retit;
        // Вставить в новое место
        insidelist::insertbefore(pnode->links[0], *(to_it.plistnode));
        return retit;
    }

    // Копировать элемент вместе с childами
    iterator copy(const_iterator from_it, iterator to_it)
    {
        const_iterator srcit = from_it;
        const_iterator endit = from_it; endit++;

        node* newnode = new node(*srcit);
        iterator dstit = iterator(&newnode->links[0]);
        dstit = dstit.begin();
        srcit = srcit.begin();
        for( ; srcit!=endit; )
        {
            if( !srcit.IsEnd())
            {
                dstit = insert(dstit, *srcit);
                if(srcit.end() != srcit.begin())
                {
                    srcit = srcit.begin();
                    dstit = dstit.begin();
                }
                else
                {
                    srcit++;
                    dstit++;
                }
                continue;
            }
            // К папе:
            srcit = srcit.parent();
            dstit = dstit.parent();
            srcit++;
            dstit++;
        }
        insidelist::insertbefore(newnode->links[0], *to_it.plistnode);
        return iterator(&(newnode->links[0]));
    }

    // Число элементов верхнего уровня
    int size() const
    {
        const_iterator it = begin();
        size = 0;
        for( ; it!=end(); it++, size++);
        return size;
    }

    // Надо проверить является ли it childoм itparent
    bool ischildof(const_iterator itparent, const_iterator it)
    {
        // Надо проверить не является ли point_it childом target_it
        iterator temp(it);
        for( ; !temp.IsTreeEnd(); temp = temp.parent())
            if(temp.Node()==itparent.Node()) return true;
        return false;
    }
};

    
}//end namespace rsdn


#endif //__RSDN__TREE_H__





//listop.h

#ifndef __RSDN__TREEOP_H__
#define __RSDN__TREEOP_H__

namespace rsdn{

 namespace insidelist{    
    // список с головным элементом
    // в классе node (N), должны быть определены ф-ции:
    // N*& next() и N*& prev()

    // Инициализировать головной элемент списка
    template <class N>
        inline void inithead(N& headnode)
    {
        // Инициализация нового списка:
        headnode.next() = &headnode;
        headnode.prev() = &headnode;
    }

    // Вставляет элемент insertnode до элемента marknode
    template <class N>
        inline void insertbefore(N& insertnode, N& marknode)
    {
        insertnode.prev() = marknode.prev();
        insertnode.next() = &marknode;
        marknode.prev() = &insertnode;
        N* prevnode = insertnode.prev();
        prevnode->next() = &insertnode;
    }

    // Вставляет элемент insertnode после элемента marknode
    template <class N>
        inline void insertafter(N& insertnode, N& marknode)
    {
        insertnode.next() = marknode.next();
        insertnode.prev() = &marknode;
        marknode.next() = &insertnode;
        N* nextnode = insertnode.next();
        nextnode->prev() = &insertnode;
    }

    // Заменяет oldnode на newnode
    template <class N>
        inline void swap(N& oldnode, N& newnode)
    {
        if(oldnode.next()==&oldnode || oldnode.prev()==&oldnode)
        {
            inithead( newnode);
            return;
        }
        oldnode.next()->prev() = &newnode;
        newnode.next() = oldnode.next();
        oldnode.prev()->next() = &newnode;
        newnode.prev() = oldnode.prev();
    }

    // Удалить элемент из списка
    template <class N>
        inline bool erase(N& node)
    {
        if(node.next()==&node || node.prev()==&node) return false;
        N* nextnode = node.next();
        N* prevnode = node.prev();
        nextnode->prev() = prevnode;
        prevnode->next() = nextnode;
        return true;
    }
 };//insidelist
};//rsdn


#endif//__RSDN__TREEOP_H__



Можно, в свободное от работы время, кидать помидорами
http://www.rsdn.org/File/13021/angler.gif
Re[3]: C++: дерево(компилируемое)
От: Toughpheeckouse Россия  
Дата: 17.04.03 12:14
Оценка:
Здравствуйте, ssm, Вы писали:

ssm>Поковырялся на досуге, короче вот:


ssm>Можно, в свободное от работы время, кидать помидорами


еще поменяй scipchild на skipchild
Думайте сами, решайте сами...
http://www.rsdn.org/tools/member.aspx?id=973
Re[4]: C++: дерево(компилируемое)
От: ssm  
Дата: 17.04.03 12:27
Оценка:
Здравствуйте, Toughpheeckouse, Вы писали:


T>еще поменяй scipchild на skipchild


Если будут еще пожелания, сделаю все пакетом
http://www.rsdn.org/File/13021/angler.gif
Re[3]: C++: дерево(компилируемое)
От: Аноним  
Дата: 17.04.03 14:57
Оценка: +1
Здравствуйте, ssm, Вы писали:

<...>

ssm>Можно, в свободное от работы время, кидать помидорами


Хех, ну тогда я покритикую :

Первое, что бросается в глаза — отсутствие allocator'а.
Далее, строчки типа throw "Нельзя удалить такой элемент".
Затем — методы типа IsEnd, формой выбивающиеся из общего строя.
А, не забыть (исправить) что всё это находится в namespace'е std.
В operator= нет проверки на this!=&src.
А где tree::swap ? И, как следствие, в каком состоянии станет находится tree, если в operator'е= произойдёт exception ?
explicit tree() ... хммм.
_Iterator::operator< — возможно, следует сделать функцией с понятным именем.
_Iterator — не предоставляет способа определить iterator_category. Для MSVC6, его необходимо породить от bidirectional_iterator_tag, иначе не скомпиляются вызовы функций, оперирующих итераторами. (std::advance, например)

Уууф.
Re[4]: C++: дерево(компилируемое)
От: ssm  
Дата: 17.04.03 15:17
Оценка:
Здравствуйте, Аноним, Вы писали:


А>Первое, что бросается в глаза — отсутствие allocator'а.


Скажем так, к чему бы ты хотел видеть allocator(T, listnode, NodeImpl)?

А>Далее, строчки типа throw "Нельзя удалить такой элемент".

Может убрать вообще проверку, оставить на совести юзера? Помоему в STL контейнерах именно так и сделано...

А>Затем — методы типа IsEnd, формой выбивающиеся из общего строя.


несовсем понял конкретней если можно

А>А, не забыть (исправить) что всё это находится в namespace'е std.


а зачем оно в std ? Да и нельзя туда ничего пихать, помоему

А>В operator= нет проверки на this!=&src.


ок, сделаю через конструктор копирования, а не наоборот, как сейчас

А>А где tree::swap ? И, как следствие, в каком состоянии станет находится tree, если в operator'е= произойдёт exception ?


согласен, исправлю

А>explicit tree() ... хммм.


об этом я тоже говорил в предыдущем посте, но забыл замочить

А>_Iterator::operator< — возможно, следует сделать функцией с понятным именем.

А>_Iterator — не предоставляет способа определить iterator_category. Для MSVC6, его необходимо породить от bidirectional_iterator_tag, иначе не скомпиляются вызовы функций, оперирующих итераторами. (std::advance, например)

А>Уууф.


в каком смылЕ ?


п.с. Я вот тут подумал, а не проще использовать допустим std::list для хранения элементов одного уровня, или лисапед forever?
http://www.rsdn.org/File/13021/angler.gif
Re[5]: C++: дерево(компилируемое)
От: Аноним  
Дата: 17.04.03 16:01
Оценка: 6 (1)
Здравствуйте, ssm, Вы писали:

<...>

ssm>Скажем так, к чему бы ты хотел видеть allocator(T, listnode, NodeImpl)?

Для всего — есть allocator::rebind, который позволяет получить аллокатор для внутренних структур из allocator'а для T. Пример — std::list. (Для MSVC6, как водится, потребуется грязный хак — _Charalloc).

ssm>Может убрать вообще проверку, оставить на совести юзера? Помоему в STL контейнерах именно так и сделано...

Я думаю, так и следует сделать.

А>Затем — методы типа IsEnd, формой выбивающиеся из общего строя.

ssm>несовсем понял конкретней если можно
Вообще, я предполагаю, что автор следовал C-style способу именования — все маленькие буквы и прочерки, где необходимо. Однако методы типа IsEnd нарушают этот стиль, что немного режет глаз.

А>А, не забыть (исправить) что всё это находится в namespace'е std.

ssm>а зачем оно в std ? Да и нельзя туда ничего пихать, помоему
Тут я проглядел, что класс в rsnd namespac'e. Тогда следует исправить шапку, которая говорит

"Определен в пространстве имен std."


А>_Iterator::operator< — возможно, следует сделать функцией с понятным именем.

А>_Iterator — не предоставляет способа определить iterator_category. Для MSVC6, его необходимо породить от bidirectional_iterator_tag, иначе не скомпиляются вызовы функций, оперирующих итераторами. (std::advance, например)
ssm>в каком смылЕ ?

Попробуй под MSVC6 скомпилять
rsdn::tree t;
...
rsdn::tree::iterator i=t.begin();
std::advance(i,1);

Не скомпиляется, так как advance не сможет определить категорию итератора (путём выбора перегруженной функции).

Насчёт operator< — надо сначала определить, что вообще он делает, хех. И назвать соответствующем образом.

ssm>п.с. Я вот тут подумал, а не проще использовать допустим std::list для хранения элементов одного уровня, или лисапед forever?

Overhead, я думаю, будет большой. Сколько "служебных" байт будет содержать node ?
Re[6]: C++: дерево(компилируемое)
От: ssm  
Дата: 17.04.03 16:42
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Для всего — есть allocator::rebind, который позволяет получить аллокатор для внутренних структур из allocator'а для T. Пример — std::list. (Для MSVC6, как водится, потребуется грязный хак — _Charalloc).


Ну тогда это на конец оставим...


ssm>Может убрать вообще проверку, оставить на совести юзера? Помоему в STL контейнерах именно так и сделано...

А>Я думаю, так и следует сделать.

тогда всуну assert

А>Затем — методы типа IsEnd, формой выбивающиеся из общего строя.

ssm>несовсем понял конкретней если можно
А>Вообще, я предполагаю, что автор следовал C-style способу именования — все маленькие буквы и прочерки, где необходимо. Однако методы типа IsEnd нарушают этот стиль, что немного режет глаз.

ok

А>А, не забыть (исправить) что всё это находится в namespace'е std.

ssm>а зачем оно в std ? Да и нельзя туда ничего пихать, помоему
А>Тут я проглядел, что класс в rsnd namespac'e. Тогда следует исправить шапку, которая говорит

"Определен в пространстве имен std."


Шляпу я нетрогал, а лишь дописал вверху то чего доделал сам, поэтому думаю так надо пока и оставить. Если удастся довести это безобразие до ума, то подправлю

А>_Iterator::operator< — возможно, следует сделать функцией с понятным именем.

А>_Iterator — не предоставляет способа определить iterator_category. Для MSVC6, его необходимо породить от bidirectional_iterator_tag, иначе не скомпиляются вызовы функций, оперирующих итераторами. (std::advance, например)

Да действительно, но скорее всего ты имел ввиду bidirectional_iterator

А>Попробуй под MSVC6 скомпилять

А>
А>rsdn::tree t;
А>...
А>rsdn::tree::iterator i=t.begin();
А>std::advance(i,1);
А>

А>Не скомпиляется, так как advance не сможет определить категорию итератора (путём выбора перегруженной функции).

Да уж... В стандарте о bidirectional_iterator упоминаний — нет, поэтому разрулю макросами...

Спасибо, доброе дело делаем(наверное )
http://www.rsdn.org/File/13021/angler.gif
Re[3]: C++: дерево(компилируемое) - v1.2
От: ssm  
Дата: 21.04.03 09:39
Оценка: 27 (4)
Спасибо Анониму за список доработок и неточностей.



//tree.h

#ifndef __RSDN__TREE_H__
#define __RSDN__TREE_H__

/************************************************
  Version : 1.2
  Изменение 21.04.2003 by rsdn::ssm
    -добавлен allocator. 
       Из-за невозможности MSVC6 использовать std::allocator::rebind, 
       необходимый для перехода от алокатора одного типа к другому, 
       был написан макрос RSDN_TREE_ALLOCATOR_BINDER посредством
       которого пользователь может выбрать свой алокатор:
          typedef rsdn::tree<
                    MyObject, 
                    RSDN_TREE_ALLOCATOR_BINDER(MyAllocator, MyObject)> 
                  MyTree;
       По умолчанию используеся std::allocator
    
    -добавлена возможность определения категории итератора для MSVC
    -rsdn::tree<>::swap
    -безопасный оператор присваивания(посредством конструктора копирования)
    -теперь дерево не бросает exception(assert).
    -поменял scipchild на skipchild 
*************************************************/

/************************************************
  Version : 1.1
  Изменение 17.04.2003 by rsdn::ssm :)
     -списковые операции вынесены в listop.h
     -tree определен в namespace rsdn
     -переделаны итераторы
     -тестировался на следующих компиляторах:
        -gcc 2.95(-ansi -pedantic -Wall -Wno-long-long)
        -MS Visual C++ 6
*************************************************/


/*
Главная фича: в итератор tree::iterator были добавлены функции
begin() и end() для получения итераторов child списка.

----------------
Краткое описание:

tree<> шаблон трехсвязного (вперед, назад, папа) дерева. Шаблон использует парадигму stl
контейнеров, для организации иерархических структур данных, типа TreeCtrl. Определен в
пространстве имен std.
Для вставки, итерирования по дереву используются bidirectional 
итераторы (реализованы операторы ++ и --):
iterator( const_iterator) - позволяет последовательно перебирать потомков одного узла. 
branch_iterator( const_branch_iterator) - позволяет делать полный
обход дерева или обход всех childoв для элемента
Есть соответствующие им reverse итераторы.

Кроме того у итератора есть методы:
parent() - возвращает итератор - выщестоящий элемент
level() - возвращает уровень элемента в иерархии (0 для tree.begin())
begin() - возвращает итератор первого элемента списка childов
end() - возвращает итератор конца списка childов
size() - возвращает число childов
У branch_iterator есть метод:
scipchild() - Следующий элемент без итерирования по childам

Шаблон tree<> содержит методы:
begin() - возвращает итератор начала списка верхнего уровня иерархии
end() - возвращает итератор конца списка верхнего уровня иерархии
insert() - добавление
erase()  - удаление элемента вместе со списком childoв
move()   - перемещение элемента вместе со списком childoв в другое место
дерева или в другое дерево
copy()  - копирование элемента вместе со списком childoв в другое место
дерева или в другое дерево

Кроме того файл содержит шаблонные функции операций с двусвязными списками с головным элементом:
inithead() - Инициализировать головной элемент списка
insertbefore() - Вставляет элемент insertnode до элемента marknode
insertafter() - Вставляет элемент insertnode после элемента marknode
swap() - Заменяет oldnode на newnode
erase() - Удаляет элемент из списка


Дерево можно представить в следующем виде:
 A1
  B11
   C111
   C112
  B12
  B13
 A2
  B21
   C211
  B22
 A3
  B31
    С311

A1-A3 - Элементы верхнего уровня
Доступ к элементам верхнего уровня аналогичен доступу к элементам
списка. 

// Перебор элементов верхнего(первого) уровня
tree::iterator it = thetree.begin();
for( ; it != thetree.end(); it++)
{
    ...
}

Элементы имеющие один парент-элемент тоже представляют из себя 
двусвязный список. Доступ к ним может быть получен 
следующим образом:

tree::iterator it = parent.begin();
for( ; it != parent.end(); it++)
{
    ...
}

Для обхода всех элементов дерева используется branch_iterator.
Итерирование будет произведено в порядке показаном на примере дерева.

tag_tree::branch_iterator it = thetree.begin();
for( ; it!=thetree.end(); it++)
{
    ...
}

*/



#include <iterator>
#include <cassert>
#include <memory>
#include "listop.h"

#ifdef __GNUC__
#    define _RSDN_HAS_REVERSE_ITERATOR
#   define _RSDN_USE_BIDIRECTIONAL_ITERATOR
#endif

    
      

#define RSDN_TREE_ALLOCATOR_BINDER(_Allocator, T)    _Allocator < NodeImpl<T> >



namespace rsdn{
    

class listnode
{
    listnode* pnext;
    listnode* pprev;
public:
    typedef listnode* plistnode;
    unsigned char index;
    plistnode& next(){return pnext;}
    plistnode& prev(){return pprev;}
    const plistnode& next()const {return pnext;}
    const plistnode& prev()const {return pprev;}
};

template<typename T>
struct NodeImpl
{
    // Первый - элемент в sibling списке
    // Второй - головной элемент в child списке
    listnode links[2];
    // Значение
    T value;
    NodeImpl():value()
    {
        links[0].index = 0;
        links[1].index = 1;
        insidelist::inithead(links[1]);
    }
    NodeImpl(const T& val):value(val)
    {
        links[0].index = 0;
        links[1].index = 1;
        insidelist::inithead(links[1]);
    }
    static NodeImpl* getnode(listnode* lnode)
    {
        if( lnode->index>=2) return NULL; // ошибка
        lnode -= lnode->index;
        return (NodeImpl*)lnode;
    }
};


#ifdef _RSDN_USE_BIDIRECTIONAL_ITERATOR
    template<typename>
    struct _BaseBidiIter{
        typedef std::bidirectional_iterator_tag  iterator_category;
    };
#else
    template<typename T>
    struct _BaseBidiIter : std::bidirectional_iterator<T, ptrdiff_t> {};
#endif

template<typename T,  typename A = RSDN_TREE_ALLOCATOR_BINDER(std::allocator, T)> class tree; 


template<typename T, typename TRef, typename TPtr>
struct _Iterator : _BaseBidiIter<T>
{
    typedef NodeImpl<T> node;
    
    typedef T                                value_type;
    typedef ptrdiff_t                        difference_type;
    typedef TPtr                             pointer;
    typedef TRef                             reference;

    typedef _Iterator<T, TRef, TPtr>            _Self;
    typedef _Iterator<T, T&, T*>                iterator;
    typedef _Iterator<T, const T&, const T*>    const_iterator;

public:
    _Iterator():plistnode(0){}
    _Iterator(listnode* plistnode):plistnode(plistnode){}
    _Iterator(const iterator& it):plistnode(it.plistnode){}
    
    _Iterator &operator=(const iterator& it){ plistnode = it.plistnode; return *this;}

    reference operator*(){return node::getnode(plistnode)->value;}
    pointer operator->(){return *(operator*());}
    
    _Iterator &operator++(){plistnode = plistnode->next(); return (*this);}
    _Iterator operator++(int){iterator _Tmp = *this; plistnode = plistnode->next(); return _Tmp;}
    _Iterator &operator--(){plistnode = plistnode->prev(); return (*this);}
    _Iterator operator--(int){iterator _Tmp = *this; --(*this); return (_Tmp); }
   
    bool operator==(const iterator& it) const  {return (plistnode == it.plistnode);}
    bool operator!=(const iterator& it) const  {return (plistnode != it.plistnode);}
    
    
    bool operator<(const iterator& it) const
    {
        // Выровнять уровни
        iterator t1 = *this, t2 = it;
        for( ; t2.level()<t1.level(); ) t1 = t1.parent();
        for( ; t1.level()<t2.level(); ) t2 = t2.parent();
        // Пока не станут одинаковые parentы
        for( ; t1.parent()!=t2.parent(); ) 
            t2 = t2.parent(), t1.parent();
        if(t1 == t2) return false;
        iterator tt1 = t1, tt2 = t2;
        // Выяснить кто старше
        for( ; ; tt2++, tt1++)
        {
            if( tt1.IsEnd()) return false; // t2<t1
            if( tt2.IsEnd()) return true;  // t1<t2 
            if(tt2 == t1) return false; // t2<t1
            if(tt1 == t2) return true;  // t1<t2
        }
        return false;
    }
    
    bool operator<=(const iterator& it) const {return (*this==it) ? true : operator<(it);}
    bool operator>(const iterator& it) const {return !(operator<=(it));}
    bool operator>=(const iterator& it) const {return !(operator<(it));}
    iterator parent() const 
    {
        iterator it = *this;
        for( ; !it.IsEnd(); it++);
        if(it.IsTreeEnd()) 
            return it;
        
        node* pnode = node::getnode(it.plistnode);
        return iterator( &pnode->links[0]);
    }
    iterator begin() const
    {
        if( IsEnd()) 
            return *this;
        
        return (++end());
    }
    iterator end() const
    {
        if( IsEnd()) 
            return *this;
        
        node* pnode = node::getnode(plistnode);
        return iterator( &pnode->links[1]);
    }
    int size() const
    {
        iterator it = begin();
        int size = 0;
        for( ; it!=end(); it++, size++);
        return size;
    }
    long level() const
    {
        long level = 0;
        iterator par = parent();
        for(; !par.IsTreeEnd() ;level++)
            par = par.parent();
        return level;
    }

// Служебные функции
protected:
    node* Node(){return node::getnode(plistnode);}
    const node* Node()const{return node::getnode(plistnode);}
    bool IsEnd()const{return (plistnode->index!=0);}
    bool IsTreeEnd()const{return (plistnode->index==2);}
public:
    listnode* plistnode;
    friend class rsdn::tree<T>;
};

 

// Итератор для полного обхода дерева
template<typename T, typename TRef, typename TPtr>
struct _BranchIterator : public _Iterator<T, TRef, TPtr>
{
    typedef T                                       value_type;
    typedef ptrdiff_t                               difference_type;
    typedef TPtr                                    pointer;
    typedef TRef                                    reference;

    typedef _BranchIterator<T, TRef, TPtr>          _Self;
    typedef _Iterator<T, TRef, TPtr>                _Base;
    
    typedef _BranchIterator<T, T&, T*>              iterator;

public:
    _BranchIterator():_Base(){}
    _BranchIterator(listnode* _plistnode):_Base(_plistnode){}
    _BranchIterator(iterator& it):_Base(it){}
    _BranchIterator(const _Base &it) : _Base(it){}
    _BranchIterator &operator=(const _BranchIterator& it){
        _Base::operator=(it);
        return *this;
    }

    _BranchIterator& operator++()
    {
        if( this->begin()!= this->end())
        {
            *this = this->begin();
            return *this;
        }
        for(;;)
        {
            if( IsEnd())
            {
                // Конец списка child
                // Перейти к верхнему эл-ту
                if(IsTreeEnd()) return *this;
                plistnode = &Node()->links[0];
            }
            plistnode = plistnode->next();
            if( !IsEnd()) return *this;
        }
        return *this;
    }
    
    _BranchIterator operator++(int)
    {
        _BranchIterator _Tmp = *this;
        ++(*this);
        return _Tmp;
    }
    
    _BranchIterator &operator--()
    {
        plistnode = plistnode->prev();
        if(!IsEnd())
        {
            // Спуститься до последнего childа
            for(;this->begin()!=this->end();)
            {
                *this = this->end();
                plistnode = plistnode->prev();
            }
        }
        else
        {
            // Вернуться к папе и вернуть его
            if(IsTreeEnd()) return *this;
            plistnode = &Node()->links[0];
            return *this;
        }
        return *this; 
    }
    
    _BranchIterator operator--(int)
    {
        _BranchIterator _Tmp = *this;
        --(*this);
        return _Tmp; 
    }
    
    // Следующий элемент без итерирования по childам
    _BranchIterator skipchild() const
    {
        _BranchIterator bit = this->end();
        return ++bit;
    }

};

template<typename T,  typename A >
class tree 
{
    typedef const T& const_reference;
    typedef const T* const_pointer;
    typedef T& reference;
    typedef T* pointer;
    
protected:
    typedef NodeImpl<T> node;
    typedef A allocator_type;
    
    
    listnode head;                  // вершина дерева
    allocator_type alloc;           // аллокатор
    
    node * _create_node(const T &val){
        node *p = alloc.allocate(1);
        try{
            new ((void *)p) node(val);
        }
        catch(...){
            alloc.deallocate(p, 1);
            throw;
        }
        return p;
    }
    
    void _free_node(node * pnode){
        alloc.destroy(pnode);
        alloc.deallocate(pnode, 1);
    }

    
        
public:
    typedef _Iterator<T, T&, T*>                        iterator;
    typedef typename iterator::const_iterator           const_iterator;
    typedef _BranchIterator<T, T&, T*>                  branch_iterator;
    typedef typename branch_iterator::const_iterator    const_branch_iterator;

    template <typename It> struct RevIter{
#ifdef _RSDN_HAS_REVERSE_ITERATOR
      typedef std::reverse_iterator<It>                  result;
#else
      typedef std::reverse_bidirectional_iterator<It, T> result;
#endif
    };
    
    typedef typename RevIter<iterator>::result                  
        reverse_iterator;
    typedef typename RevIter<const_iterator>::result
        const_reverse_iterator;
    typedef typename RevIter<branch_iterator>::result
        reverse_branch_iterator;
    typedef typename RevIter<const_branch_iterator>::result
        const_reverse_branch_iterator;
  

    tree()
    {
        insidelist::inithead(head);
        head.index = 2;
    }
    
    explicit tree(const tree& src)
    {
        rsdn::insidelist::inithead(head);
        head.index = 2;
        const_iterator from = src.begin();
        for( ; from != src.end(); from++) 
            copy(from, end());
    }

    void swap(tree &src)
    {
        std::swap(head, head);
    }
    
    tree& operator=(const tree& src)
    {
        tree tmp(src);
        swap(tmp, *this);
        return *this;
    }

    
    ~tree(){clear();}

    // Пусто?
    bool empty(){return (head.begin() == &head);}
    // Вычистить все
    void clear(){
        for( ; begin()!=end(); ) 
            erase(begin());
    }

    // Обычные итераторы
    const_iterator begin()const{return const_iterator( head.next());}
    const_iterator end()const{return const_iterator( &head);}
    iterator begin(){return iterator( head.next());}
    iterator end(){return iterator( &head);}

    // Обратные итераторы
    const_reverse_iterator rbegin()const{return const_reverse_iterator(end());}
    const_reverse_iterator rend()const{return const_reverse_iterator(begin());}
    reverse_iterator rbegin(){return reverse_iterator(end());}
    reverse_iterator rend(){return reverse_iterator(begin());}

    // Добавляет элемент того же уровня sibling
    iterator insert(iterator before_it, const T& value=T())
    {
        node *newnode = _create_node(value);
        insidelist::insertbefore(newnode->links[0], *before_it.plistnode);
        return iterator(&(newnode->links[0]));
    }
    // Добавляет элемент верхнего уровня
    // Все sibling элементы станут его childами
    iterator insertparent(iterator parent_for_it, const T& value=T())
    {
        return insertchild(parent_for_it.parent(), value);
    }
    // Добавляет элемент нижнего уровня
    // Все child элементы станут childами вставленного элемента
    iterator insertchild(iterator child_for_it, const T& value=T())
    {
        listnode* pparentnode = &head;
        node* parent = child_for_it.Node();
        if( parent) pparentnode = &parent->links[1];
        node* newnode = _create_node(value);
        insidelist::swap( *pparentnode, newnode->links[1]);
        insidelist::inithead( *pparentnode);
        insidelist::insertbefore(newnode->links[0], *pparentnode);
        return iterator(&(newnode->links[0]));
    }
    // Удалить элемент вместе с его childами
    iterator erase(iterator it)
    {
        assert(!it.IsEnd());
        // Обход childов в обратном порядке
        branch_iterator bit = it, endbit = it;
        iterator retit = it; retit++;
        bit = bit.skipchild();
        for( bit--; bit!=endbit; )
        {
            // Удаляемый элемент - гарантируется, что у него нет childов
            branch_iterator erit = bit;
            bit--;
            // Удалить
            node* pnode = erit.Node();
            assert(erit.begin() == erit.end());
            bool tmp = insidelist::erase( pnode->links[0]);
            assert(tmp);
            _free_node(pnode);
        }
        node* pnode = it.Node();
        if( !pnode) return retit;
        if( !insidelist::erase( pnode->links[0])) return retit;
        _free_node(pnode);
        return retit;
    }
    // Переместить элемент вместе с childами
    iterator move(iterator from_it, iterator to_it)
    {
        if( from_it.IsEnd()) return from_it;
        iterator retit = from_it; retit++;
        // Надо проверить не является ли point_it childом target_it
        iterator temp(to_it);
        for( ; !temp.IsTreeEnd(); temp = temp.parent())
            if(temp.Node()==from_it.Node()) return retit;

        node* pnode = from_it.Node();
        // Выкинуть из текущего списка
        if( !insidelist::erase( pnode->links[0])) return retit;
        // Вставить в новое место
        insidelist::insertbefore(pnode->links[0], *(to_it.plistnode));
        return retit;
    }

    // Копировать элемент вместе с childами
    iterator copy(const_iterator from_it, iterator to_it)
    {
        const_iterator srcit = from_it;
        const_iterator endit = from_it; endit++;

        node* newnode = _create_node(*srcit);
        iterator dstit = iterator(&newnode->links[0]);
        dstit = dstit.begin();
        srcit = srcit.begin();
        for( ; srcit!=endit; )
        {
            if( !srcit.IsEnd())
            {
                dstit = insert(dstit, *srcit);
                if(srcit.end() != srcit.begin())
                {
                    srcit = srcit.begin();
                    dstit = dstit.begin();
                }
                else
                {
                    srcit++;
                    dstit++;
                }
                continue;
            }
            // К папе:
            srcit = srcit.parent();
            dstit = dstit.parent();
            srcit++;
            dstit++;
        }
        insidelist::insertbefore(newnode->links[0], *to_it.plistnode);
        return iterator(&(newnode->links[0]));
    }

    // Число элементов верхнего уровня
    int size() const
    {
        const_iterator it = begin();
        size = 0;
        for( ; it!=end(); it++, size++);
        return size;
    }

    // Надо проверить является ли it childoм itparent
    bool ischildof(const_iterator itparent, const_iterator it)
    {
        // Надо проверить не является ли point_it childом target_it
        iterator temp(it);
        for( ; !temp.IsTreeEnd(); temp = temp.parent())
            if(temp.Node()==itparent.Node()) return true;
        return false;
    }
};

    
}//end namespace rsdn


#undef _RSDN_HAS_REVERSE_ITERATOR
#undef _RSDN_USE_BIDIRECTIONAL_ITERATOR



#endif //__RSDN__TREE_H__





//listop.h

#ifndef __RSDN__TREEOP_H__
#define __RSDN__TREEOP_H__

namespace rsdn{

 namespace insidelist{    
    // список с головным элементом
    // в классе node (N), должны быть определены ф-ции:
    // N*& next() и N*& prev()

    // Инициализировать головной элемент списка
    template <class N>
        inline void inithead(N& headnode)
    {
        // Инициализация нового списка:
        headnode.next() = &headnode;
        headnode.prev() = &headnode;
    }

    // Вставляет элемент insertnode до элемента marknode
    template <class N>
        inline void insertbefore(N& insertnode, N& marknode)
    {
        insertnode.prev() = marknode.prev();
        insertnode.next() = &marknode;
        marknode.prev() = &insertnode;
        N* prevnode = insertnode.prev();
        prevnode->next() = &insertnode;
    }

    // Вставляет элемент insertnode после элемента marknode
    template <class N>
        inline void insertafter(N& insertnode, N& marknode)
    {
        insertnode.next() = marknode.next();
        insertnode.prev() = &marknode;
        marknode.next() = &insertnode;
        N* nextnode = insertnode.next();
        nextnode->prev() = &insertnode;
    }

    // Заменяет oldnode на newnode
    template <class N>
        inline void swap(N& oldnode, N& newnode)
    {
        if(oldnode.next()==&oldnode || oldnode.prev()==&oldnode)
        {
            inithead( newnode);
            return;
        }
        oldnode.next()->prev() = &newnode;
        newnode.next() = oldnode.next();
        oldnode.prev()->next() = &newnode;
        newnode.prev() = oldnode.prev();
    }

    // Удалить элемент из списка
    template <class N>
        inline bool erase(N& node)
    {
        if(node.next()==&node || node.prev()==&node) return false;
        N* nextnode = node.next();
        N* prevnode = node.prev();
        nextnode->prev() = prevnode;
        prevnode->next() = nextnode;
        return true;
    }
 };//insidelist
};//rsdn


#endif//__RSDN__TREEOP_H__
http://www.rsdn.org/File/13021/angler.gif
Re[4]: C++: дерево(компилируемое) - v1.2
От: ORS  
Дата: 12.07.03 10:25
Оценка:
Здравствуйте,
я не знаю stl и только слегка знаком с шаблонами, так что извините заранее, если что не так. Просто позарез нужно хранить данные в структуре, типа дерева и мои поиски готового решения привели меня сюда. К сожалению мой уровень знаний не позволяет сразу воспользоваться этим исходником, может быть кто-нибудь уделит время написанию краткого хелпа на основе примера, объясняющего как пользоваться этим деревом (на языке понятном человеку, не знающему, что такое allocator и с чем его едят). За не имением такового попытался разобраться в исходнике сам, соответственно появились вопросы:
1.
template <class N>
    inline void swap(N& oldnode, N& newnode)
    {
        if(oldnode.next()==&oldnode || oldnode.prev()==&oldnode)
        {
            inithead( newnode);
            return;
        }
        oldnode.next()->prev() = &newnode;
        newnode.next() = oldnode.next();
        oldnode.prev()->next() = &newnode;
        newnode.prev() = oldnode.prev();
    }

Под if`ом точно должно быть ||, а не &&?
Судя по названию функции она меняет местами oldnode и newnode, по реализации же она убирает oldnode и вставляет на ее место newnode. Может стоит назвать функцию replace, а не swap?

2.
template <class N>
        inline bool erase(N& node)

Аналогично, может переименовать в remove, вместо erase, т.к. функция не удаляет сам объект node.

3.
static NodeImpl* getnode(listnode* lnode)
    {
        if( lnode->index>=2) return NULL; // &icirc;&oslash;&egrave;&aacute;&ecirc;&agrave;
        lnode -= lnode->index;
        return (NodeImpl*)lnode;
    }

Вообще не понял, что делает эта функция и как она работает.

4.
void swap(tree &src)
    {
        std::swap(head, head);
    }

Может нужно std::swap(head, src.head);?
Re[5]: C++: дерево(компилируемое) - v1.2
От: Аноним  
Дата: 05.01.04 17:48
Оценка:
Здравствуйте, ORS, Вы писали:

ORS>Здравствуйте,

ORS>я не знаю stl и только слегка знаком с шаблонами, так что извините заранее, если что не так. Просто позарез нужно хранить данные

Да, да, хотя-бы исходник с примером использования ! ПЛЗ...
Re: C++: дерево
От: VictorProg  
Дата: 31.08.04 13:03
Оценка:
Здравствуйте, m.a.g., Вы писали:

MAG>Hi.


MAG>STL-like дерево. Копирайт, к сожалению, утерян.


MAG>
MAG>///////////////////////////////////////////////////////////////////////////////
MAG>//  дерево.
MAG>//
MAG>#ifndef _tree_H_
MAG>#define _tree_H_

MAG>/*/

MAG>Главная фича: в итератор tree::iterator были добавлены функции
MAG>begin() и end() для получения итераторов child списка.

MAG>----------------
MAG>Краткое описание:

MAG>tree<> шаблон трехсвязного (вперед, назад, папа) дерева. Шаблон использует парадигму stl
MAG>контейнеров, для организации иерархических структур данных, типа TreeCtrl. Определен в
MAG>пространстве имен std.
MAG>Для вставки, итерирования по дереву используются bidirectional 
MAG>итераторы (реализованы операторы ++ и --):
MAG>iterator( const_iterator) - позволяет последовательно перебирать потомков одного узла. 
MAG>branch_iterator( const_branch_iterator) - позволяет делать полный
MAG>обход дерева или обход всех childoв для элемента
MAG>Есть соответствующие им reverse итераторы.

MAG>Кроме того у итератора есть методы:
MAG>parent() - возвращает итератор - выщестоящий элемент
MAG>level() - возвращает уровень элемента в иерархии (0 для tree.begin())
MAG>begin() - возвращает итератор первого элемента списка childов
MAG>end() - возвращает итератор конца списка childов
MAG>size() - возвращает число childов
MAG>У branch_iterator есть метод:
MAG>scipchild() - Следующий элемент без итерирования по childам

MAG>Шаблон tree<> содержит методы:
MAG>begin() - возвращает итератор начала списка верхнего уровня иерархии
MAG>end() - возвращает итератор конца списка верхнего уровня иерархии
MAG>insert() - добавление
MAG>erase()  - удаление элемента вместе со списком childoв
MAG>move()   - перемещение элемента вместе со списком childoв в другое место
MAG>дерева или в другое дерево
MAG>copy()  - копирование элемента вместе со списком childoв в другое место
MAG>дерева или в другое дерево

MAG>Кроме того файл содержит шаблонные функции операций с двусвязными списками с головным элементом:
MAG>inithead() - Инициализировать головной элемент списка
MAG>insertbefore() - Вставляет элемент insertnode до элемента marknode
MAG>insertafter() - Вставляет элемент insertnode после элемента marknode
MAG>swap() - Заменяет oldnode на newnode
MAG>erase() - Удаляет элемент из списка


MAG>Дерево можно представить в следующем виде:
MAG> A1
MAG>  B11
MAG>   C111
MAG>   C112
MAG>  B12
MAG>  B13
MAG> A2
MAG>  B21
MAG>   C211
MAG>  B22
MAG> A3
MAG>  B31
MAG>    С311

MAG>A1-A3 - Элементы верхнего уровня
MAG>Доступ к элементам верхнего уровня аналогичен доступу к элементам
MAG>списка. 

MAG>// Перебор элементов верхнего(первого) уровня
MAG>tree::iterator it = thetree.begin();
MAG>for( ; it != thetree.end(); it++)
MAG>{
MAG>    ...
MAG>}

MAG>Элементы имеющие один парент-элемент тоже представляют из себя 
MAG>двусвязный список. Доступ к ним может быть получен 
MAG>следующим образом:

MAG>tree::iterator it = parent.begin();
MAG>for( ; it != parent.end(); it++)
MAG>{
MAG>    ...
MAG>}

MAG>Для обхода всех элементов дерева используется branch_iterator.
MAG>Итерирование будет произведено в порядке показаном на примере дерева.

MAG>tag_tree::branch_iterator it = thetree.begin();
MAG>for( ; it!=thetree.end(); it++)
MAG>{
MAG>    ...
MAG>}


MAG>/*/
MAG>#include <iterator>

MAG>namespace insidelist
MAG>{
MAG>    // список с головным элементом
MAG>    // в классе node (N), должны быть определены ф-ции:
MAG>    // N*& next() и N*& prev()

MAG>    // Инициализировать головной элемент списка
MAG>    template <class N>
MAG>        inline void inithead(N& headnode)
MAG>    {
MAG>        // Инициализация нового списка:
MAG>        headnode.next() = &headnode;
MAG>        headnode.prev() = &headnode;
MAG>    }

MAG>    // Вставляет элемент insertnode до элемента marknode
MAG>    template <class N>
MAG>        inline void insertbefore(N& insertnode, N& marknode)
MAG>    {
MAG>        insertnode.prev() = marknode.prev();
MAG>        insertnode.next() = &marknode;
MAG>        marknode.prev() = &insertnode;
MAG>        N* prevnode = insertnode.prev();
MAG>        prevnode->next() = &insertnode;
MAG>    }

MAG>    // Вставляет элемент insertnode после элемента marknode
MAG>    template <class N>
MAG>        inline void insertafter(N& insertnode, N& marknode)
MAG>    {
MAG>        insertnode.next() = marknode.next();
MAG>        insertnode.prev() = &marknode;
MAG>        marknode.next() = &insertnode;
MAG>        N* nextnode = insertnode.next();
MAG>        nextnode->prev() = &insertnode;
MAG>    }

MAG>    // Заменяет oldnode на newnode
MAG>    template <class N>
MAG>        inline void swap(N& oldnode, N& newnode)
MAG>    {
MAG>        if(oldnode.next()==&oldnode || oldnode.prev()==&oldnode)
MAG>        {
MAG>            inithead( newnode);
MAG>            return;
MAG>        }
MAG>        oldnode.next()->prev() = &newnode;
MAG>        newnode.next() = oldnode.next();
MAG>        oldnode.prev()->next() = &newnode;
MAG>        newnode.prev() = oldnode.prev();
MAG>    }

MAG>    // Удалить элемент из списка
MAG>    template <class N>
MAG>        inline bool erase(N& node)
MAG>    {
MAG>        if(node.next()==&node || node.prev()==&node) return false;
MAG>        N* nextnode = node.next();
MAG>        N* prevnode = node.prev();
MAG>        nextnode->prev() = prevnode;
MAG>        prevnode->next() = nextnode;
MAG>        return true;
MAG>    }
MAG>};

MAG>namespace std
MAG>{
MAG>using namespace insidelist;

MAG>template<class T>
MAG>class tree 
MAG>{
MAG>    struct node;
MAG>    typedef const T& const_reference;
MAG>    typedef const T* const_pointer;
MAG>    typedef T& reference;
MAG>    typedef T* pointer;
    
MAG>    class listnode
MAG>    {
MAG>        listnode* pnext;
MAG>        listnode* pprev;
MAG>    public:
MAG>        typedef listnode* plistnode;
MAG>        unsigned char index;
MAG>        plistnode& next(){return pnext;}
MAG>        plistnode& prev(){return pprev;}
MAG>        const plistnode& next()const {return pnext;}
MAG>        const plistnode& prev()const {return pprev;}
MAG>    };
MAG>    struct node
MAG>    {
MAG>        // Первый - элемент в sibling списке
MAG>        // Второй - головной элемент в child списке
MAG>        listnode links[2];
MAG>        // Значение
MAG>        T value;
MAG>        node():value()
MAG>        {
MAG>            links[0].index = 0;
MAG>            links[1].index = 1;
MAG>            inithead(links[1]);
MAG>        }
MAG>        node(const T& val):value(val)
MAG>        {
MAG>            links[0].index = 0;
MAG>            links[1].index = 1;
MAG>            insidelist::inithead(links[1]);
MAG>        }
MAG>        static node* getnode(listnode* lnode)
MAG>        {
MAG>            if( lnode->index>=2) return NULL; // ошибка
MAG>            lnode -= lnode->index;
MAG>            return (node*)lnode;
MAG>        }
MAG>    };
MAG>protected:
MAG>    // вершина дерева
MAG>    listnode head;

MAG>public:
MAG>    // CLASS const_iterator
MAG>    class const_iterator;
MAG>    class iterator;
MAG>    class const_branch_iterator;
MAG>    class branch_iterator;

MAG>    friend class tree::const_iterator;

MAG>    // reverse_iterator
MAG>    typedef reverse_bidirectional_iterator<iterator, T>
MAG>        reverse_iterator;
MAG>    // const_reverse_iterator
MAG>    typedef reverse_bidirectional_iterator<const_iterator, T> 
MAG>        const_reverse_iterator;
MAG>    // reverse_branch_iterator
MAG>    typedef reverse_bidirectional_iterator<branch_iterator, T>
MAG>        reverse_branch_iterator;
MAG>    // const_reverse_branch_iterator
MAG>    typedef reverse_bidirectional_iterator<const_branch_iterator, T>
MAG>        const_reverse_branch_iterator;

MAG>    explicit tree()
MAG>    {
MAG>        insidelist::inithead(head);
MAG>        head.index = 2;
MAG>    }
MAG>    tree(const tree& src)
MAG>    {
MAG>        insidelist::inithead(head);
MAG>        head.index = 2;
MAG>        *this = src;
MAG>    }
MAG>    tree& operator=(const tree& src)
MAG>    {
MAG>        clear();
MAG>        const_iterator from = src.begin();
MAG>        for( ; from != src.end(); from++) 
MAG>            copy(from, end());
MAG>        return *this;
MAG>    }
MAG>    ~tree(){clear();}

MAG>    // Пусто?
MAG>    bool empty(){return (head.begin() == &head);}
MAG>    // Вычистить все
MAG>    void clear(){for( ; begin()!=end(); ) erase(begin());}

MAG>    // Обычные итераторы
MAG>    const_iterator begin()const{return const_iterator( head.next());}
MAG>    const_iterator end()const{return const_iterator( &head);}
MAG>    iterator begin(){return iterator( head.next());}
MAG>    iterator end(){return iterator( &head);}

MAG>    // Обратные итераторы
MAG>    const_reverse_iterator rbegin()const{return const_reverse_iterator(end());}
MAG>    const_reverse_iterator rend()const{return const_reverse_iterator(begin());}
MAG>    reverse_iterator rbegin(){return reverse_iterator(end());}
MAG>    reverse_iterator rend(){return reverse_iterator(begin());}

MAG>    // Добавляет элемент того же уровня sibling
MAG>    iterator insert(iterator before_it, const T& value=T())
MAG>    {
MAG>        node* newnode = new node(value);
MAG>        insidelist::insertbefore(newnode->links[0], *before_it.plistnode);
MAG>        return iterator(&(newnode->links[0]));
MAG>    }
MAG>    // Добавляет элемент верхнего уровня
MAG>    // Все sibling элементы станут его childами
MAG>    iterator insertparent(iterator parent_for_it, const T& value=T())
MAG>    {
MAG>        return insertchild(parent_for_it.parent(), value);
MAG>    }
MAG>    // Добавляет элемент нижнего уровня
MAG>    // Все child элементы станут childами вставленного элемента
MAG>    iterator insertchild(iterator child_for_it, const T& value=T())
MAG>    {
MAG>        listnode* pparentnode = &head;
MAG>        node* parent = child_for_it.Node();
MAG>        if( parent) pparentnode = &parent->links[1];
MAG>        node* newnode = new node(value);
MAG>        insidelist::swap( *pparentnode, newnode->links[1]);
MAG>        insidelist::inithead( *pparentnode);
MAG>        insidelist::insertbefore(newnode->links[0], *pparentnode);
MAG>        return iterator(&(newnode->links[0]));
MAG>    }
MAG>    // Удалить элемент вместе с его childами
MAG>    iterator erase(iterator it)
MAG>    {
MAG>        if( it.IsEnd()) throw "Нельзя удалить такой элемент";

MAG>        // Обход childов в обратном порядке
MAG>        branch_iterator bit = it, endbit = it;
MAG>        iterator retit = it; retit++;
MAG>        bit = bit.scipchild();
MAG>        for( bit--; bit!=endbit; )
MAG>        {
MAG>            // Удаляемый элемент - гарантируется, что у него нет childов
MAG>            branch_iterator erit = bit;
MAG>            bit--;
MAG>            // Удалить
MAG>            node* pnode = erit.Node();
MAG>            if( erit.begin()!=erit.end()) throw "Ошибка при удалении";
MAG>            if( !insidelist::erase( pnode->links[0])) throw "Ошибка при удалении";
MAG>            delete pnode;
MAG>        }
MAG>        node* pnode = it.Node();
MAG>        if( !pnode) return retit;
MAG>        if( !insidelist::erase( pnode->links[0])) return retit;
MAG>        delete pnode;
MAG>        return retit;
MAG>    }
MAG>    // Переместить элемент вместе с childами
MAG>    iterator move(iterator from_it, iterator to_it)
MAG>    {
MAG>        if( from_it.IsEnd()) return from_it;
MAG>        iterator retit = from_it; retit++;
MAG>        // Надо проверить не является ли point_it childом target_it
MAG>        iterator temp(to_it);
MAG>        for( ; !temp.IsTreeEnd(); temp = temp.parent())
MAG>            if(temp.Node()==from_it.Node()) return retit;

MAG>        node* pnode = from_it.Node();
MAG>        // Выкинуть из текущего списка
MAG>        if( !insidelist::erase( pnode->links[0])) return retit;
MAG>        // Вставить в новое место
MAG>        insidelist::insertbefore(pnode->links[0], *(to_it.plistnode));
MAG>        return retit;
MAG>    }

MAG>    // Копировать элемент вместе с childами
MAG>    iterator copy(const_iterator from_it, iterator to_it)
MAG>    {
MAG>        const_iterator srcit = from_it;
MAG>        const_iterator endit = from_it; endit++;

MAG>        node* newnode = new node(*srcit);
MAG>        iterator dstit = iterator(&newnode->links[0]);
MAG>        dstit = dstit.begin();
MAG>        srcit = srcit.begin();
MAG>        for( ; srcit!=endit; )
MAG>        {
MAG>            if( !srcit.IsEnd())
MAG>            {
MAG>                dstit = insert(dstit, *srcit);
MAG>                if(srcit.end() != srcit.begin())
MAG>                {
MAG>                    srcit = srcit.begin();
MAG>                    dstit = dstit.begin();
MAG>                }
MAG>                else
MAG>                {
MAG>                    srcit++;
MAG>                    dstit++;
MAG>                }
MAG>                continue;
MAG>            }
MAG>            // К папе:
MAG>            srcit = srcit.parent();
MAG>            dstit = dstit.parent();
MAG>            srcit++;
MAG>            dstit++;
MAG>        }
MAG>        insidelist::insertbefore(newnode->links[0], *to_it.plistnode);
MAG>        return iterator(&(newnode->links[0]));
MAG>    }

MAG>    // Число элементов верхнего уровня
MAG>    int size() const
MAG>    {
MAG>        const_iterator it = begin();
MAG>        for( int size=0; it!=end(); it++, size++);
MAG>        return size;
MAG>    }

MAG>    // Надо проверить является ли it childoм itparent
MAG>    bool ischildof(const_iterator itparent, const_iterator it)
MAG>    {
MAG>        // Надо проверить не является ли point_it childом target_it
MAG>        iterator temp(it);
MAG>        for( ; !temp.IsTreeEnd(); temp = temp.parent())
MAG>            if(temp.Node()==itparent.Node()) return true;
MAG>        return false;
MAG>    }

MAG>    // Итератор для перебора элементов sibling одного parenta
MAG>    class const_iterator : public _Bidit<T, ptrdiff_t>
MAG>    {
MAG>    public:
MAG>        const_iterator():plistnode(NULL){}
MAG>        const_iterator(const listnode* _plistnode):plistnode((listnode*)_plistnode){}
MAG>        const_iterator(const const_iterator& it):plistnode(it.plistnode){}
MAG>        const_iterator& operator=(const const_iterator& it){this->const_iterator::const_iterator(it); return *this;}

MAG>        const_reference operator*() const
MAG>        {
MAG>            const node* pnode = node::getnode(plistnode);
MAG>            return pnode->value;
MAG>        }
MAG>        const_pointer operator->() const
MAG>        {
MAG>            const node* pnode = node::getnode(plistnode);
MAG>            return &pnode->value;
MAG>        }
MAG>        const_iterator& operator++()
MAG>        {
MAG>            plistnode = plistnode->next();
MAG>            return (*this); 
MAG>        }
MAG>        const_iterator operator++(int)
MAG>        {
MAG>            const_iterator _Tmp = *this;
MAG>            plistnode = plistnode->next();
MAG>            return (_Tmp); 
MAG>        }
MAG>        const_iterator& operator--()
MAG>        {
MAG>            plistnode = plistnode->prev();
MAG>            return (*this); 
MAG>        }
MAG>        const_iterator operator--(int)
MAG>        {
MAG>            const_iterator _Tmp = *this;
MAG>            --(*this);
MAG>            return (_Tmp); 
MAG>        }
MAG>        bool operator==(const const_iterator& it) const
MAG>        {
MAG>            return (plistnode == it.plistnode);
MAG>        }
MAG>        bool operator!=(const const_iterator& it) const
MAG>        {
MAG>            return (plistnode != it.plistnode);
MAG>        }
MAG>        bool operator<(const const_iterator& it) const
MAG>        {
MAG>            // Выровнять уровни
MAG>            const_iterator t1 = *this, t2 = it;
MAG>            for( ; t2.level()<t1.level(); ) t1 = t1.parent();
MAG>            for( ; t1.level()<t2.level(); ) t2 = t2.parent();
MAG>            // Пока не станут одинаковые parentы
MAG>            for( ; t1.parent()!=t2.parent(); ) 
MAG>                t2 = t2.parent(), t1.parent();
MAG>            if(t1 == t2) return false;
MAG>            const_iterator tt1 = t1, tt2 = t2;
MAG>            // Выяснить кто старше
MAG>            for( ; ; tt2++, tt1++)
MAG>            {
MAG>                if( tt1.IsEnd()) return false; // t2<t1
MAG>                if( tt2.IsEnd()) return true;  // t1<t2 
MAG>                if(tt2 == t1) return false; // t2<t1
MAG>                if(tt1 == t2) return true;  // t1<t2
MAG>            }
MAG>            return false;
MAG>        }
MAG>        bool operator<=(const const_iterator& it) const
MAG>        {
MAG>            if(*this==it) return true;
MAG>            return operator<(it);
MAG>        }
MAG>        bool operator>(const const_iterator& it) const
MAG>        {
MAG>            return !(operator<=(it));
MAG>        }
MAG>        bool operator>=(const const_iterator& it) const
MAG>        {
MAG>            return !(operator<(it));
MAG>        }
MAG>        const_iterator parent() const 
MAG>        {
MAG>            const_iterator it = *this;
MAG>            for( ; !it.IsEnd(); it++);
MAG>            if(it.IsTreeEnd()) return it;
MAG>            node* pnode = node::getnode(it.plistnode);
MAG>            return const_iterator( &pnode->links[0]);
MAG>        }
MAG>        const_iterator begin() const
MAG>        {
MAG>            if( IsEnd()) return *this;
MAG>            return (++end());
MAG>        }
MAG>        const_iterator end() const
MAG>        {
MAG>            if( IsEnd()) return *this;
MAG>            node* pnode = node::getnode(plistnode);
MAG>            return iterator( &pnode->links[1]);
MAG>        }
MAG>        int size() const
MAG>        {
MAG>            const_iterator it = begin();
MAG>            for( int size=0; it!=end(); it++, size++);
MAG>            return size;
MAG>        }
MAG>        long level() const
MAG>        {
MAG>            long level = 0;
MAG>            const_iterator par = parent();
MAG>            for(; !par.IsTreeEnd() ;level++)
MAG>                par = par.parent();
MAG>            return level;
MAG>        }

MAG>    // Служебные функции
MAG>    protected:
MAG>        node* Node(){return node::getnode(plistnode);}
MAG>        const node* Node()const{return node::getnode(plistnode);}
MAG>        bool IsEnd()const{return (plistnode->index!=0);}
MAG>        bool IsTreeEnd()const{return (plistnode->index==2);}
MAG>    protected:
MAG>        friend class tree<T>;
MAG>        listnode* plistnode;
MAG>    };

MAG>    // Итератор для перебора элементов sibling одного parenta
MAG>    class iterator : public const_iterator
MAG>    {
MAG>    public:
MAG>        iterator():const_iterator(){}
MAG>        iterator(listnode* _plistnode):const_iterator(_plistnode){}
MAG>        iterator(const iterator& it):const_iterator(it){}
MAG>        iterator(const branch_iterator& it):const_iterator(it){}
MAG>        iterator& operator=(const iterator& it){this->iterator::iterator(it); return *this;}
MAG>//      iterator& operator=(const branch_iterator& it){this->iterator::iterator(it); return *this;}

MAG>        reference operator*()
MAG>        {
MAG>            return Node()->value;
MAG>        }
MAG>        pointer operator->()
MAG>        {
MAG>            return &Node()->value;
MAG>        }
MAG>        iterator& operator++()
MAG>        {
MAG>            plistnode = plistnode->next();
MAG>            return (*this);
MAG>        }
MAG>        iterator operator++(int)
MAG>        {
MAG>            iterator _Tmp = *this;
MAG>            plistnode = plistnode->next();
MAG>            return (_Tmp);
MAG>        }
MAG>        iterator& operator--()
MAG>        {
MAG>            plistnode = plistnode->prev();
MAG>            return (*this);
MAG>        }
MAG>        iterator operator--(int)
MAG>        {
MAG>            iterator _Tmp = *this;
MAG>            --(*this);
MAG>            return (_Tmp);
MAG>        }

MAG>    // Дополнительные функции для иерархии
MAG>    public:
MAG>        iterator parent() const{const_iterator it = const_iterator::parent(); return *((iterator*)&it);}
MAG>        iterator begin() const{const_iterator it = const_iterator::begin(); return *((iterator*)&it);}
MAG>        iterator end() const{const_iterator it = const_iterator::end(); return *((iterator*)&it);}
MAG>    };

MAG>    // Итератор для полного обхода дерева
MAG>    class const_branch_iterator : public const_iterator
MAG>    {
MAG>    public:
MAG>        const_branch_iterator():const_iterator(){}
MAG>        const_branch_iterator(listnode* _plistnode):const_iterator(_plistnode){}
MAG>        const_branch_iterator(const const_iterator& it):const_iterator(it){}
MAG>        const_branch_iterator& operator=(const const_branch_iterator& it){this->const_iterator::const_iterator(it); return *this;}

MAG>        const_branch_iterator& operator++()
MAG>        {
MAG>            if( begin()!=end())
MAG>            {
MAG>                *this = begin();
MAG>                return *this;
MAG>            }
MAG>            for(;;)
MAG>            {
MAG>                if( IsEnd())
MAG>                {
MAG>                    // Конец списка child
MAG>                    // Перейти к верхнему эл-ту
MAG>                    if(IsTreeEnd()) return *this;
MAG>                    plistnode = &Node()->links[0];
MAG>                }
MAG>                plistnode = plistnode->next();
MAG>                if( !IsEnd()) return *this;
MAG>            }
MAG>            return (*this);
MAG>        }
MAG>        const_branch_iterator operator++(int)
MAG>        {
MAG>            iterator _Tmp = *this;
MAG>            ++(*this);
MAG>            return (_Tmp);
MAG>        }
MAG>        const_branch_iterator& operator--()
MAG>        {
MAG>            plistnode = plistnode->prev();
MAG>            if(!IsEnd())
MAG>            {
MAG>                // Спуститься до последнего childа
MAG>                for(;begin()!=end();)
MAG>                {
MAG>                    *this = end();
MAG>                    plistnode = plistnode->prev();
MAG>                }
MAG>            }
MAG>            else
MAG>            {
MAG>                // Вернуться к папе и вернуть его
MAG>                if(IsTreeEnd()) return *this;
MAG>                plistnode = &Node()->links[0];
MAG>                return *this;
MAG>            }
MAG>            return (*this); 
MAG>        }
MAG>        const_branch_iterator operator--(int)
MAG>        {
MAG>            branch_iterator _Tmp = *this;
MAG>            --(*this);
MAG>            return (_Tmp); 
MAG>        }
MAG>        // Следующий элемент без итерирования по childам
MAG>        const_branch_iterator scipchild() const
MAG>        {
MAG>            const_branch_iterator bit = end();
MAG>            return (++bit);
MAG>        }
MAG>    };

MAG>    class branch_iterator : public const_branch_iterator
MAG>    {
MAG>    public:
MAG>        branch_iterator():const_branch_iterator(){}
MAG>        branch_iterator(listnode* _plistnode):const_branch_iterator(_plistnode){}
MAG>        branch_iterator(const branch_iterator& it):const_branch_iterator(it){}
MAG>        branch_iterator(const iterator& it):const_branch_iterator(it){}
MAG>        branch_iterator& operator=(const branch_iterator& it){this->const_branch_iterator::const_branch_iterator(it); return *this;}
MAG>        branch_iterator& operator=(const iterator& it){this->const_branch_iterator::const_branch_iterator(it); return *this;}

MAG>        reference operator*()
MAG>        {
MAG>            return Node()->value;
MAG>        }
MAG>        pointer operator->()
MAG>        {
MAG>            return &Node()->value;
MAG>        }
MAG>        branch_iterator& operator++()
MAG>        {
MAG>            const_branch_iterator::operator++();
MAG>            return (*this);
MAG>        }
MAG>        branch_iterator operator++(int)
MAG>        {
MAG>            iterator _Tmp = *this; ++(*this); return (_Tmp);
MAG>        }
MAG>        branch_iterator& operator--()
MAG>        {
MAG>            const_branch_iterator::operator--();
MAG>            return (*this); 
MAG>        }
MAG>        branch_iterator operator--(int)
MAG>        {
MAG>            branch_iterator _Tmp = *this; --(*this); return (_Tmp); 
MAG>        }
MAG>        // Следующий элемент без итерирования по childам
MAG>        branch_iterator scipchild() const
MAG>        {
MAG>            return *((branch_iterator*)&const_branch_iterator::scipchild());
MAG>        }

MAG>    };

MAG>};

MAG>}

MAG>#endif
MAG>


Тут поступала просьба привести пример использования всего этого. Я думаю, эта просьба имеет здравый смысл. Бо от всех этих деревьев чайник кипит.
Re: C++: дерево
От: ioni Россия  
Дата: 31.08.04 18:33
Оценка: 9 (2)
Здравствуйте, m.a.g., Вы писали:

а это видел
http://www.lsi.upc.es/~nlp/freeling/refman/tree_8h-source.html

здесь пример использования
http://www.damtp.cam.ac.uk/user/kp229/tree/
Re[2]: C++: дерево
От: Блудов Павел Россия  
Дата: 01.09.04 02:24
Оценка: +2 :)
Здравствуйте, VictorProg, Вы писали:

VP>Тут поступала просьба привести пример использования всего этого.


Пожалуйста, избегайте ненужного цитирования. Это может иметь очень неприятные для Вас последствия.
... << RSDN@Home 1.1.4 beta 2 >>
Re[3]: C++: дерево
От: VictorProg  
Дата: 01.09.04 07:32
Оценка:
Здравствуйте, Блудов Павел, Вы писали:

БП>Здравствуйте, VictorProg, Вы писали:


VP>>Тут поступала просьба привести пример использования всего этого.


БП>Пожалуйста, избегайте ненужного цитирования. Это может иметь очень неприятные для Вас последствия.


Я извиняюсь, если кого обидел....
Re: C++: дерево
От: spanasik  
Дата: 03.09.04 06:50
Оценка:
Здравствуйте, m.a.g., Вы писали:

MAG>STL-like дерево. Копирайт, к сожалению, утерян.

А зачем использовать это, если есть boost::graph, который в том числе
и как дерево можно использовать ?

Стас.
... << RSDN@Home 1.1.4 @@subversion >>
Re[2]: C++: дерево
От: Vlads  
Дата: 26.06.05 19:51
Оценка:
Здравствуйте, VictorProg, Вы писали:


VP>Тут поступала просьба привести пример использования всего этого. Я думаю, эта просьба имеет здравый смысл. Бо от всех этих деревьев чайник кипит.


Многоуважаемые знатоки, можете хоть кто-нибудь привести пример использования этого дерева?
Re[3]: C++: дерево
От: sadomovalex Россия http://sadomovalex.blogspot.com
Дата: 27.06.05 09:26
Оценка:
Здравствуйте, Vlads, Вы писали:

V>Здравствуйте, VictorProg, Вы писали:



VP>>Тут поступала просьба привести пример использования всего этого. Я думаю, эта просьба имеет здравый смысл. Бо от всех этих деревьев чайник кипит.


V>Многоуважаемые знатоки, можете хоть кто-нибудь привести пример использования этого дерева?


это дерево вообще лучше не использовать
я как то столкнулся, в результате пришлось самому писать
Автор: sadomovalex
Дата: 09.03.05
"Что не завершено, не сделано вовсе" Гаусс
https://lh3.googleusercontent.com/-jIXLxlvycbk/TtKm5Xxz7JI/AAAAAAAABEA/CITKwRG1hFg/w500-h200-k/mvp_horizontal.png
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.