tree容器（0.0.0.4 版）

// tree.hpp

#ifndef TREE_HEADER__
#define TREE_HEADER__

#include

template class tree;
template std::basic_ostream& operator<<( std::basic_ostream&, const tree& );
//template std::basic_ostream& operator<<( std::basic_ostream&, const tree& );

////// definition /////////////////////////////////////////////////////////

template
class tree
{
    friend std::basic_ostream& operator<< ( std::basic_ostream&, const tree& );
    //friend std::basic_ostream& operator<< ( std::basic_ostream&, const tree& );
public:
    typedef T value_type;

    tree();
    explicit tree( const T& t );
    tree( const tree& rhs );
    tree& operator=( const tree& rhs );
    ~tree();

    T& val();
    const T& val() const;

    tree& parent();
    tree& left();
    tree& right();
    tree& childfirst();
    tree& childlast();
    const tree& parent() const;
    const tree& left() const;
    const tree& right() const;
    const tree& childfirst() const;
    const tree& childlast() const;

    tree& root();
    const tree& root() const;

    tree* traverse_front();
    tree* traverse_back();
    tree* traverse_next( int& depth_diff = *(int*)0 );
    tree* traverse_prev( int& depth_diff = *(int*)0 );
    const tree* traverse_front() const;
    const tree* traverse_back() const;
    const tree* traverse_next( int& depth_diff = *(int*)0 ) const;
    const tree* traverse_prev( int& depth_diff = *(int*)0 ) const;

    template F traverse( F f, int start_depth_diff, tree* from, tree* to );
    template F traverse( F f, int start_depth_diff, tree* from );
    template F traverse( F f, int start_depth_diff );
    template F traverse( F f, int start_depth_diff, const tree* from, const tree* to ) const;
    template F traverse( F f, int start_depth_diff, const tree* from ) const;
    template F traverse( F f, int start_depth_diff ) const;
    template F traverse_reverse( F f, int start_depth_diff, tree* from, tree* to );
    template F traverse_reverse( F f, int start_depth_diff, tree* from );
    template F traverse_reverse( F f, int start_depth_diff );
    template F traverse_reverse( F f, int start_depth_diff, const tree* from, const tree* to ) const;
    template F traverse_reverse( F f, int start_depth_diff, const tree* from ) const;
    template F traverse_reverse( F f, int start_depth_diff ) const;

    void erase();
    void erasesubs();
    tree& addfirstchild( const T& t=T() );
    tree& addright( const T& t=T() );

    void swap( tree& t );

    size_t cal_bin_size() const;
    size_t write_to( void* ) const;
    size_t read_from( const void* );
    size_t write_to( std::ostream& ) const;
    size_t read_from( std::istream& );

protected:
    void init_();
    void destroysubs_();

protected:
    T val_;
    tree* ptrparent_;
    tree* ptrleft_;
    tree* ptrright_;
    tree* ptrchildfirst_;
    tree* ptrchildlast_;

#ifndef TREE_DEBUG__
};
#else
public:
    static int m;
    static void* operator new( size_t n )
    {
        ++m;
        return ::operator new(n);
    }
    static void operator delete( void* p )
    {
        --m;
        ::operator delete(p);
    }
};
template int tree::m = 0;
#endif

#define TREE_MACRO_TRAVERSE_BEGIN( type, start_depth_diff, from, to, next ) \
{                                                                           \
    type* to_ = to;                                                         \
    int depth_diff = start_depth_diff;                                      \
    for( type* ptree=from; ptree; )                                         \
    {                                                                       \
        int tmp_dd;                                                         \
        type* tmp_p;                                                        \
        if( ptree != to_ ) tmp_p = ptree->next(tmp_dd);

#define TREE_MACRO_TRAVERSE_END                                             \
        if( ptree == to_ ) break;                                           \
        depth_diff = tmp_dd;                                                \
        ptree = tmp_p;                                                      \
    }                                                                       \
}

////// implement /////////////////////////////////////////////////////////

#include
#include
#include
template struct tree_trait;

template tree::tree() : val_(T())
{
    init_();
}
template tree::tree( const T& t ) : val_(t)
{
    init_();
}
template tree::tree( const tree& rhs ) : val_(rhs.val_)
{
    init_();

    tree* p = this;
    TREE_MACRO_TRAVERSE_BEGIN( const tree, 1, rhs.traverse_next(), rhs.traverse_back(), traverse_next )
        if( depth_diff > 0 )
        {
            p = &p->addfirstchild( ptree->val_ );
        }
        else
        {
            for( ; depth_diff!=0; ++depth_diff )
                p = p->ptrparent_;

            p = &p->addright( ptree->val_ );
        }
    TREE_MACRO_TRAVERSE_END
}
template tree& tree::operator=( const tree& rhs )
{
    if( this != &rhs )
    {
        tree bk = rhs;

        destroysubs_();

        std::swap( val_, bk.val_ );
        ptrchildfirst_=bk.ptrchildfirst_; ptrchildfirst_->ptrparent_=this; bk.ptrchildfirst_=0;
        ptrchildlast_ =bk.ptrchildlast_;  ptrchildlast_->ptrparent_ =this; bk.ptrchildlast_ =0;
    }
    return *this;
}
template tree::~tree()
{
    destroysubs_();
}

template inline T& tree::val() { return val_; }
template inline const T& tree::val() const { return ((tree*)this)->val(); }

template inline tree& tree::parent() { return *ptrparent_; }
template inline tree& tree::left() { return *ptrleft_; }
template inline tree& tree::right() { return *ptrright_; }
template inline tree& tree::childfirst() { return *ptrchildfirst_; }
template inline tree& tree::childlast() { return *ptrchildlast_; }
template inline const tree& tree::parent() const { return ((tree*)this)->parent(); }
template inline const tree& tree::left() const { return ((tree*)this)->left(); }
template inline const tree& tree::right() const { return ((tree*)this)->right(); }
template inline const tree& tree::childfirst() const { return ((tree*)this)->childfirst(); }
template inline const tree& tree::childlast() const { return ((tree*)this)->childlast(); }

template tree& tree::root()
{
    tree* p;
    for( p=this; p->ptrparent_; p=p->ptrparent_ );
    return *p;
}
template inline const tree& tree::root() const { return ((tree*)this)->root(); }

template inline tree* tree::traverse_front()
{
    return this;
}
template tree* tree::traverse_back()
{
    tree* p = this;
    for( ; p->ptrchildlast_; p=p->ptrchildlast_ );
    return p;
}
template tree* tree::traverse_next( int& depth_diff )
{
    int dd = 0;

    tree* p = this;
    if( p->ptrchildfirst_ )
    {
        p = p->ptrchildfirst_;
        ++dd;
    }
    else if( p->ptrright_ )
    {
        p = p->ptrright_;
    }
    else
    {
        while( 1 )
        {
            p = p->ptrparent_;
            --dd;
            if( !p )
                break;
            if( p->ptrright_ )
            {
                p = p->ptrright_;
                break;
            }
        }
    }

    if( &depth_diff )
        depth_diff = dd;
    return p;
}
template tree* tree::traverse_prev(  int& depth_diff  )
{
    int dd = 0;

    tree* p = this;
    if( p->ptrleft_ )
    {
        p = p->ptrleft_;
        for( ; p->ptrchildlast_; p=p->ptrchildlast_ )
        {
            ++dd;
        }
    }
    else if( p->ptrparent_ )
    {
        p = p->ptrparent_;
        --dd;
    }
    else
        p = 0;

    if( &depth_diff )
        depth_diff = dd;
    return p;
}

template inline const tree* tree::traverse_front() const { return ((tree*)this)->traverse_front(); }
template inline const tree* tree::traverse_back() const { return ((tree*)this)->traverse_back(); }
template inline const tree* tree::traverse_next( int& depth_diff ) const { return ((tree*)this)->traverse_next(depth_diff); }
template inline const tree* tree::traverse_prev( int& depth_diff ) const { return ((tree*)this)->traverse_prev(depth_diff); }

template template F tree::traverse( F f, int start_depth_diff, tree* from, tree* to )
{
    TREE_MACRO_TRAVERSE_BEGIN( tree, start_depth_diff, from, to, traverse_next )
        f( ptree, depth_diff );
    TREE_MACRO_TRAVERSE_END
    return f;
}
template template inline F tree::traverse( F f, int start_depth_diff, tree* from )
{
    return traverse( f, start_depth_diff, from, traverse_back() );
}
template template inline F tree::traverse( F f, int start_depth_diff )
{
    return traverse( f, start_depth_diff, traverse_front() );
}
template template F tree::traverse( F f, int start_depth_diff, const tree* from, const tree* to ) const
{
    TREE_MACRO_TRAVERSE_BEGIN( const tree, start_depth_diff, from, to, traverse_next )
        f( ptree, depth_diff );
    TREE_MACRO_TRAVERSE_END
    return f;
}
template template inline F tree::traverse( F f, int start_depth_diff, const tree* from ) const
{
    return traverse( f, start_depth_diff, from, traverse_back() );
}
template template inline F tree::traverse( F f, int start_depth_diff ) const
{
    return traverse( f, start_depth_diff, traverse_front() );
}
template template F tree::traverse_reverse( F f, int start_depth_diff, tree* from, tree* to )
{
    TREE_MACRO_TRAVERSE_BEGIN( tree, start_depth_diff, from, to, traverse_prev )
        f( ptree, depth_diff );
    TREE_MACRO_TRAVERSE_END
    return f;
}
template template inline F tree::traverse_reverse( F f, int start_depth_diff, tree* from )
{
    return traverse_reverse( f, start_depth_diff, from, traverse_front() );
}
template template inline F tree::traverse_reverse( F f, int start_depth_diff )
{
    return traverse_reverse( f, start_depth_diff, traverse_back() );
}
template template F tree::traverse_reverse( F f, int start_depth_diff, const tree* from, const tree* to ) const
{
    TREE_MACRO_TRAVERSE_BEGIN( const tree, start_depth_diff, from, to, traverse_prev )
        f( ptree, depth_diff );
    TREE_MACRO_TRAVERSE_END
    return f;
}
template template inline F tree::traverse_reverse( F f, int start_depth_diff, const tree* from ) const
{
    return traverse_reverse( f, start_depth_diff, from, traverse_front() );
}
template template inline F tree::traverse_reverse( F f, int start_depth_diff ) const
{
    return traverse_reverse( f, start_depth_diff, traverse_back() );
}

template void tree::erase()
{
    destroysubs_();

    if( ptrparent_ )
    {
        if( ptrleft_ )
            ptrleft_->ptrright_ = ptrright_;
        else
            ptrparent_->ptrchildfirst_ = ptrright_;

        if( ptrright_ )
            ptrright_->ptrleft_ = ptrleft_;
        else
            ptrparent_->ptrchildlast_ = ptrleft_;

        val_.~T();
        operator delete( this );
    }
    else
    {
        ptrchildfirst_ = 0;
        ptrchildlast_ = 0;
        val_ = T();
    }
}
template void tree::erasesubs()
{
    destroysubs_();
    ptrchildfirst_ = 0;
    ptrchildlast_ = 0;
}
template tree& tree::addfirstchild( const T& t )
{
    tree* pnew = new tree(t);
    if( ptrchildfirst_ )
    {
        ptrchildfirst_->ptrleft_ = pnew;
        pnew->ptrright_ = ptrchildfirst_;
        ptrchildfirst_ = pnew;
        pnew->ptrparent_ = this;
    }
    else
    {
        ptrchildfirst_ = pnew;
        ptrchildlast_ = pnew;
        pnew->ptrparent_ = this;
    }
    return *pnew;
}
template tree& tree::addright( const T& t )
{
    assert( ptrparent_ );

    tree* pnew = new tree(t);
    pnew->ptrparent_ = ptrparent_;
    pnew->ptrleft_ = this;
    pnew->ptrright_ = ptrright_;
    if( ptrright_ )
        ptrright_->ptrleft_ = pnew;
    else
        ptrparent_->ptrchildlast_ = pnew;
    ptrright_ = pnew;

    return *pnew;
}

template void tree::swap( tree& t )
{
    if( this != &t )
    {
#ifdef _DEBUG
        for( tree* p=this; p; p=p->ptrparent_ ) assert( p != &t   );
        for( tree* p=&t;   p; p=p->ptrparent_ ) assert( p != this );
#endif
        std::swap( val_, t.val_ );

        if( ptrchildfirst_ )
        {
            ptrchildfirst_->ptrparent_ = &t;
            ptrchildlast_->ptrparent_ = &t;
        }
        if( t.ptrchildfirst_ )
        {
            t.ptrchildfirst_->ptrparent_ = this;
            t.ptrchildlast_->ptrparent_ = this;
        }

        tree* p;
        p=ptrchildfirst_; ptrchildfirst_=t.ptrchildfirst_; t.ptrchildfirst_=p;
        p=ptrchildlast_;  ptrchildlast_ =t.ptrchildlast_;  t.ptrchildlast_ =p;
    }
}
namespace std
{
    template inline void swap( tree& lhs, tree& rhs )
    {
        return lhs.swap( rhs );
    }
}

namespace
{
    inline size_t fit_size( size_t n )
    {
        return (n+sizeof(size_t)-1)/sizeof(size_t)*sizeof(size_t);
    }
    template struct cal_bin_size_
    {
        // [ size_t:depth, T:val(algin align of size_t) ], ..., size_t:0
        size_t operator()( const tree& t )
        {
            size_t n=0;
            TREE_MACRO_TRAVERSE_BEGIN( const tree, 0, t.traverse_front(), t.traverse_back(), traverse_next )
                ++n;
            TREE_MACRO_TRAVERSE_END

            return n*( sizeof(size_t) + fit_size(sizeof(T)) ) + sizeof(size_t);
        }
    };
    template struct cal_bin_size_
    {
        // [ size_t:depth, size_t:val_size, T:val(algin align of size_t) ], ..., size_t:0
        size_t operator()( const tree& t )
        {
            size_t n=0;
            TREE_MACRO_TRAVERSE_BEGIN( const tree, 0, t.traverse_front(), t.traverse_back(), traverse_next )
                n += sizeof(size_t) + sizeof(size_t) + fit_size(tree_trait::bin_size(ptree->val()));
            TREE_MACRO_TRAVERSE_END

            return n + sizeof(size_t);
        }
    };

    template struct write_to_
    {
        size_t operator()( const tree& t, void* dst )
        {
            // [ size_t:depth, T:val(algin align of size_t) ], ..., size_t:0
            char* pdst = (char*)dst;
            size_t fill = 0;

            size_t depth = 0;
            TREE_MACRO_TRAVERSE_BEGIN( const tree, 0, t.traverse_front(), t.traverse_back(), traverse_next )
                depth += depth_diff;
                *(size_t*)pdst = depth; pdst+=sizeof(size_t);
                *(T*)pdst = ptree->val(); pdst+=sizeof(T);
                if( sizeof(T)%sizeof(size_t) != 0 ) // fill interval with 0
                    for( size_t i=0; i                        *pdst++ = 0;
            TREE_MACRO_TRAVERSE_END
            *(size_t*)pdst = 0; pdst+=sizeof(size_t);

            return pdst-(char*)dst;
        }

        size_t operator()( const tree& t, std::ostream& dst )
        {
            // [ size_t:depth, T:val(algin align of size_t) ], ..., size_t:0
            size_t n = 0;
            size_t depth = 0;
            const size_t bk = 0;
            TREE_MACRO_TRAVERSE_BEGIN( const tree, 0, t.traverse_front(), t.traverse_back(), traverse_next )
                depth += depth_diff;
                dst.write( (const char*)&depth, sizeof(depth) ); n+=sizeof(size_t); assert( dst );
                dst.write( (const char*)&ptree->val(), sizeof(T) ); n+=sizeof(T); assert( dst );
                if( sizeof(T)%sizeof(size_t) != 0 ) // fill interval with 0
                {
                    dst.write( (const char*)&bk, sizeof(size_t)-sizeof(T)%sizeof(size_t) ); n+=sizeof(size_t)-sizeof(T)%sizeof(size_t); assert( dst );
                }
            TREE_MACRO_TRAVERSE_END

            dst.write( (const char*)&bk, sizeof(size_t) ); n+=sizeof(size_t); assert( dst );

            return n;
        }
    };

    template struct write_to_
    {
        size_t operator()( const tree& t, void* dst )
        {
            // [ size_t:depth, size_t:val_size, T:val(algin align of size_t) ], ..., size_t:0
            char* pdst = (char*)dst;

            size_t depth = 0;
            TREE_MACRO_TRAVERSE_BEGIN( const tree, 0, t.traverse_front(), t.traverse_back(), traverse_next )
                depth += depth_diff;
                *(size_t*)pdst = depth; pdst+=sizeof(size_t);
                size_t len = tree_trait::bin_size(ptree->val()); *(size_t*)pdst = len; pdst+=sizeof(size_t);
                tree_trait::bin_write( ptree->val(), pdst ); pdst+=len;
                if( len%sizeof(size_t) != 0 ) // fill interval with 0
                    for( size_t i=0; i                        *pdst++ = 0;
            TREE_MACRO_TRAVERSE_END
            *(size_t*)pdst = 0; pdst+=sizeof(size_t);

            return pdst-(char*)dst;
        }

        size_t operator()( const tree& t, std::ostream& dst )
        {
            // [ size_t:depth, size_t:val_size, T:val(algin align of size_t) ], ..., size_t:0
            size_t n = 0;
            size_t depth = 0;
            const size_t bk = 0;
            TREE_MACRO_TRAVERSE_BEGIN( const tree, 0, t.traverse_front(), t.traverse_back(), traverse_next )
                depth += depth_diff;
                dst.write( (const char*)&depth, sizeof(depth) ); n+=sizeof(size_t); assert( dst );
                size_t len = tree_trait::bin_size(ptree->val()); dst.write( (const char*)&len, sizeof(size_t) ); n+=sizeof(size_t); assert( dst );
                tree_trait::bin_write( ptree->val(), dst ); n+=len; assert( dst );
                if( len%sizeof(size_t) != 0 ) // fill interval with 0
                {
                    dst.write( (const char*)&bk, (std::streamsize)(sizeof(size_t)-len%sizeof(size_t)) ); n+=sizeof(size_t)-len%sizeof(size_t); assert( dst );
                }
            TREE_MACRO_TRAVERSE_END
            dst.write( (const char*)&bk, sizeof(size_t) ); n+=sizeof(size_t); assert( dst );

            return n;
        }
    };

    template struct read_from_
    {
        size_t operator()( tree& t, const void* src )
        {
            // [ size_t:depth, T:val(algin align of size_t) ], ..., size_t:0
            const char* psrc = (const char*)src;
            size_t fz = fit_size(sizeof(T));

            t.erasesubs();
            size_t depth_begin = *(size_t*)psrc; psrc+=sizeof(size_t);
            t.val() = *(T*)psrc; psrc+=fz;
            tree* p = &t;

            size_t depth_pre = depth_begin;
            size_t depth = *(size_t*)psrc; psrc+=sizeof(size_t);
            while( depth != depth_begin )
            {
                if( depth == depth_pre )
                {
                    p=&p->addright( *(T*)psrc ); psrc+=fz;
                }
                else if( depth > depth_pre )
                {
                    assert( depth = depth_pre+1 );
                    p=&p->addfirstchild( *(T*)psrc ); psrc+=fz;
                }
                else
                {
                    for( size_t i=depth; i!=depth_pre; ++i )
                        p = &p->parent();
                    p=&p->addright( *(T*)psrc ); psrc+=fz;
                }
                depth_pre = depth;
                depth = *(size_t*)psrc; psrc+=sizeof(size_t);
            }

            return psrc-(char*)src;
        }

        size_t operator()( tree& t, std::istream& src )
        {
            // [ size_t:depth, T:val(algin align of size_t) ], ..., size_t:0
            size_t n = 0;
            size_t w = 0;
            size_t y = sizeof(size_t) - sizeof(T) % sizeof(size_t);

            t.erasesubs();
            size_t depth_begin = 0;
            src.read( (char*)&depth_begin, sizeof(size_t) ); n+=sizeof(size_t);
            assert( src && src.gcount()==sizeof(size_t) );
            src.read( (char*)&t.val(), sizeof(T) ); n+=sizeof(T);
            assert( src && src.gcount()==sizeof(T) );
            if( sizeof(T)%sizeof(size_t) )
            {
                src.read( (char*)&w, (std::streamsize)y ); n += y;
                assert( src && src.gcount()==y );
            }
            tree* p = &t;

            size_t depth_pre = depth_begin;
            size_t depth = 0; src.read( (char*)&depth, sizeof(size_t) ); n+=sizeof(size_t);
            assert( src && src.gcount()==sizeof(size_t) );
            while( depth != depth_begin )
            {
                if( depth == depth_pre )
                {
                    p=&p->addright();
                }
                else if( depth > depth_pre )
                {
                    assert( depth = depth_pre+1 );
                    p=&p->addfirstchild();
                }
                else
                {
                    for( size_t i=depth; i!=depth_pre; ++i )
                        p = &p->parent();
                    p=&p->addright();
                }
                src.read( (char*)&p->val(), sizeof(T) ); n+=sizeof(T);
                assert( src && src.gcount()==sizeof(T) );
                if( sizeof(T)%sizeof(size_t) )
                {
                    src.read( (char*)&w, (std::streamsize)y ); n += y;
                    assert( src && src.gcount()==y );
                }

                depth_pre = depth;
                src.read( (char*)&depth, sizeof(size_t) ); n+=sizeof(size_t);
                assert( src && src.gcount()==sizeof(size_t) );
            }

            return n;
        }
    };

    template struct read_from_
    {
        size_t operator()( tree& t, const void* src )
        {
            // [ size_t:depth, size_t:val_size, T:val(algin align of size_t) ], ..., size_t:0
            const char* psrc = (const char*)src;

            t.erasesubs();
            size_t depth_begin = *(size_t*)psrc; psrc+=sizeof(size_t);
            size_t n = *(size_t*)psrc; psrc+=sizeof(size_t);
            size_t m = tree_trait::bin_read( t.val(), n, psrc ); psrc+=fit_size(m);
            assert( m == n );
            tree* p = &t;

            size_t depth_pre = depth_begin;
            size_t depth = *(size_t*)psrc; psrc+=sizeof(size_t);
            while( depth != depth_begin )
            {
                if( depth == depth_pre )
                {
                    p=&p->addright();
                }
                else if( depth > depth_pre )
                {
                    assert( depth = depth_pre+1 );
                    p=&p->addfirstchild();
                }
                else
                {
                    for( size_t i=depth; i!=depth_pre; ++i )
                        p = &p->parent();
                    p=&p->addright();
                }
                n = *(size_t*)psrc; psrc+=sizeof(size_t);
                m = tree_trait::bin_read( p->val(), n, psrc ); psrc+=fit_size(m);
                assert( m == n );

                depth_pre = depth;
                depth = *(size_t*)psrc; psrc+=sizeof(size_t);
            }

            return psrc-(char*)src;
        }

        size_t operator()( tree& t, std::istream& src )
        {
            // [ size_t:depth, size_t:val_size, T:val(algin align of size_t) ], ..., size_t:0
            size_t n = 0;
            size_t w = 0;

            t.erasesubs();
            size_t depth_begin = 0;
            src.read( (char*)&depth_begin, sizeof(size_t) ); n+=sizeof(size_t);
            assert( src && src.gcount()==sizeof(size_t) );
            size_t m = 0;
            src.read( (char*)&m, sizeof(size_t) ); n+=sizeof(size_t);
            assert( src && src.gcount()==sizeof(size_t) );
            tree_trait::bin_read( t.val(), m, src ); n+=m;
            if( m%sizeof(size_t) )
            {
                size_t y = sizeof(size_t) - m % sizeof(size_t);
                src.read( (char*)&w, (std::streamsize)y ); n += y;
                assert( src && src.gcount()==y );
            }
            tree* p = &t;

            size_t depth_pre = depth_begin;
            size_t depth = 0;
            src.read( (char*)&depth, sizeof(size_t) ); n+=sizeof(size_t);
            assert( src && src.gcount()==sizeof(size_t) );
            while( depth != depth_begin )
            {
                if( depth == depth_pre )
                {
                    p=&p->addright();
                }
                else if( depth > depth_pre )
                {
                    assert( depth = depth_pre+1 );
                    p=&p->addfirstchild();
                }
                else
                {
                    for( size_t i=depth; i!=depth_pre; ++i )
                        p = &p->parent();
                    p=&p->addright();
                }
                src.read( (char*)&m, sizeof(size_t) ); n+=sizeof(size_t);
                assert( src && src.gcount()==sizeof(size_t) );
                tree_trait::bin_read( p->val(), m, src ); n+=m;
                if( m%sizeof(size_t) )
                {
                    size_t y = sizeof(size_t) - m % sizeof(size_t);
                    src.read( (char*)&w, (std::streamsize)y ); n += y;
                    assert( src && src.gcount()==y );
                }

                depth_pre = depth;
                src.read( (char*)&depth, sizeof(size_t) ); n+=sizeof(size_t);
                assert( src && src.gcount()==sizeof(size_t) );
            }

            return n;
        }
    };
}
template size_t tree::cal_bin_size() const
{
    return cal_bin_size_< T, tree_trait::is_solid >()( *this );
}
template size_t tree::write_to( void* dst) const
{
    return write_to_< T, tree_trait::is_solid >()( *this, dst );
}
template size_t tree::write_to( std::ostream& dst) const
{
    return write_to_< T, tree_trait::is_solid >()( *this, dst );
}
template size_t tree::read_from( const void* src )
{
    return read_from_< T, tree_trait::is_solid >()( *this, src );
}
template size_t tree::read_from( std::istream& src )
{
    return read_from_< T, tree_trait::is_solid >()( *this, src );
}

template inline void tree::init_()
{
    ptrparent_ = 0;
    ptrleft_ = 0;
    ptrright_ = 0;
    ptrchildfirst_ = 0;
    ptrchildlast_ = 0;
}
template void tree::destroysubs_()
{
    if( ptrchildlast_ )
    {
        TREE_MACRO_TRAVERSE_BEGIN( tree, 0, traverse_back(), traverse_next(), traverse_prev )
            ptree->val_.~T();
            operator delete( ptree );
        TREE_MACRO_TRAVERSE_END
    }
}

template std::basic_ostream& operator<<( std::basic_ostream& os, const tree& t )
{
    int depth = 0;
    TREE_MACRO_TRAVERSE_BEGIN( const tree, 0, t.traverse_front(), t.traverse_back(), traverse_next )
        depth += depth_diff;
        os << std::setw(depth) << "" << ptree->val_ << '\n';
    TREE_MACRO_TRAVERSE_END

    return os;
}
//template std::basic_ostream& operator<<( std::basic_ostream& os, const tree& t )
//{
//    int depth = 0;
//    TREE_MACRO_TRAVERSE_BEGIN( const tree, 0, t.traverse_front(), t.traverse_back(), traverse_next )
//        depth += depth_diff;
//        os << std::setw(depth) << L"" << ptree->val_ << L'\n';
//    TREE_MACRO_TRAVERSE_END
//
//    return os;
//}

////// trait for native types /////////////////////////////////////////////////////////

template struct wipeoff_const_volatile             { typedef T Type; };
template struct wipeoff_const_volatile    { typedef T Type; };
template struct wipeoff_const_volatile { typedef T Type; };

template struct tree_trait_           { static const bool is_solid = false; };
template<> struct tree_trait_               { static const bool is_solid = true; };
template<> struct tree_trait_        { static const bool is_solid = true; };
template<> struct tree_trait_      { static const bool is_solid = true; };
template<> struct tree_trait_       { static const bool is_solid = true; };
template<> struct tree_trait_     { static const bool is_solid = true; };
template<> struct tree_trait_         { static const bool is_solid = true; };
template<> struct tree_trait_       { static const bool is_solid = true; };
template<> struct tree_trait_        { static const bool is_solid = true; };
template<> struct tree_trait_      { static const bool is_solid = true; };
template<> struct tree_trait_   { static const bool is_solid = true; };
template<> struct tree_trait_ { static const bool is_solid = true; };
template<> struct tree_trait_              { static const bool is_solid = true; };
template<> struct tree_trait_             { static const bool is_solid = true; };
template<> struct tree_trait_        { static const bool is_solid = true; };

template struct tree_trait
{
    static const bool is_solid = tree_trait_< typename wipeoff_const_volatile::Type >::is_solid;
};

////// trait for std::string /////////////////////////////////////////////////////////
#include

template struct tree_trait< std::basic_string >
{
    static const bool is_solid = false;

    static inline size_t bin_size( const std::basic_string& s )
    {
        return s.size()*sizeof(T);
    }
    static inline size_t bin_write( const std::basic_string& s, void* p )
    {
        memcpy( (T*)p, s.c_str(), s.size()*sizeof(T) );
        return s.size()*sizeof(T);
    }
    static inline size_t bin_read( std::basic_string& s, size_t n, const void* p )
    {
        s = std::basic_string( (const T*)p, n/sizeof(T) );
        return n;
    }
    static inline size_t bin_write( const std::basic_string& s, std::ostream& os )
    {
        os.write( (const char *)s.c_str(), (std::streamsize)s.size()*sizeof(T) );
        assert( os );
        return s.size()*sizeof(T);
    }
    static inline size_t bin_read( std::basic_string& s, size_t n, std::istream& is )
    {
        char* p = new char[n];
        is.read( p, (std::streamsize)n );
        assert( is && is.gcount() == n );
        s = std::basic_string( (T*)p, n/sizeof(T) );
        delete[] p;
        return n;
    }
};

template struct tree_trait< const std::basic_string > : tree_trait< std::basic_string > {};
template struct tree_trait< volatile std::basic_string > : tree_trait< std::basic_string > {};

////// trait for std::vector /////////////////////////////////////////////////////////
#include

template<> struct tree_trait< std::vector >
{
    static const bool is_solid = false;

    static inline size_t bin_size( const std::vector& s )
    {
        return s.size();
    }
    static inline size_t bin_write( const std::vector& s, void* p )
    {
        memcpy( (char*)p, &s[0], s.size() );
        return s.size();
    }
    static inline size_t bin_read( std::vector& s, size_t n, const void* p )
    {
        s = std::vector( (const unsigned char*)p, (const unsigned char*)p+n );
        return n;
    }
    static inline size_t bin_write( const std::vector& s, std::ostream& os )
    {
        os.write( (char*)&s[0], (std::streamsize)s.size() );
        assert( os );
        return s.size();
    }
    static inline size_t bin_read( std::vector& s, size_t n, std::istream& is )
    {
        unsigned char* p = new unsigned char[n];
        is.read( (char*)p, (std::streamsize)n );
        assert( is && is.gcount() == n );
        s = std::vector( (const unsigned char*)p, (const unsigned char*)p+n );
        delete[] p;
        return n;
    }
};

template<> struct tree_trait > : tree_trait< std::vector > {};
template<> struct tree_trait > : tree_trait< std::vector > {};

std::ostream& operator<<( std::ostream& os, const std::vector& s )
{
    char pf = os.fill('0');

    os << '[';
    if( !s.empty() )
    {
        os << std::setw(2) << std::setfill('0') << s[0];
        for( size_t i=1; i            os << ',' << std::setw(2) << std::setfill('0') << s[0];
    }
    os << ']';

    os.fill(pf);
    return os;
}

#endif // TREE_HEADER__

// test.cpp

#include
#include
#include
#include
#define TREE_DEBUG__
#include "tree.hpp"
using namespace std;

struct foo //for test
{
    static int n;
    int v;

    foo( int i=0 ) : v(i)
    {
        ++n;
    }
    foo( const foo& I ) : v(I.v)
    {
        ++n;
    }
    ~foo()
    {
        --n;
    }

    operator int&()
    {
        return v;
    }
    operator int() const
    {
        return v;
    }
};
int foo::n = 0;
template<> struct tree_trait_            { static const bool is_solid = true; };

struct foo2
{
    char v[5];
    foo2( int i=0 )
    {
        *(int*)v = i;
        v[4] = 0;
    }
    operator int() const
    {
        return *(int*)v;
    }
};
template<> struct tree_trait_           { static const bool is_solid = true; };

template
void test( tree& t )
{
    const tree* p = 0;
    const tree* pend = t.traverse_back();
    for( p=t.traverse_front(); p!=pend; p=p->traverse_next() )
    {
        if( &p->left() )
        {
            assert( &p->left().right() == p );

            assert( &p->left().parent() == &p->parent() );
        }
        else
        {
            if( &p->parent() )
                assert( &p->parent().childfirst() == p );
        }

        if( &p->right() )
        {
            assert( &p->right().left() == p );
        }
        else
        {
            if( &p->parent() )
                assert(&p->parent().childlast() == p );
        }
    }

    assert( &p->childfirst() == 0 );
    assert( &p->childlast() == 0 );
    assert( &p->right() == 0 );
}

int main3()
{
    cout << "--- vector <--> memory ---" << endl;
    {
        tree< vector > a1( vector(1,'1') );
        tree< vector >& a2 = a1.addfirstchild( vector(2,'2') );
        tree< vector >& a3 = a2.addfirstchild( vector(3,'3') );
        tree< vector >& a4 = a3.addright( vector(4,'4') );
        tree< vector >& a5 = a2.addright( vector(5,'5') );
        tree< vector >& a6 = a5.addfirstchild( vector(6,'6') );
        tree< vector >& a7 = a6.addright( vector(7,'7') );

        size_t len = a1.cal_bin_size();
        char* p = new char[len];
        size_t n1 = a1.write_to( p );
        assert( n1 == len );

        tree< vector > b1;
        size_t n2 = b1.read_from( p );
        assert( n2 == len );
        cout << b1 << endl;
        test( b1 );

        tree< vector > c1 = b1;
        size_t n3 = c1.read_from( p );
        assert( n3 == len );
        cout << c1 << endl;
        test( c1 );

        delete[] p;
    }
    cout << "--- vector <--> stream ---" << endl;
    {
        tree< vector > a1( vector(1,'1') );
        tree< vector >& a2 = a1.addfirstchild( vector(2,'2') );
        tree< vector >& a3 = a2.addfirstchild( vector(3,'3') );
        tree< vector >& a4 = a3.addright( vector(4,'4') );
        tree< vector >& a5 = a2.addright( vector(5,'5') );
        tree< vector >& a6 = a5.addfirstchild( vector(6,'6') );
        tree< vector >& a7 = a6.addright( vector(7,'7') );

        fstream ios( "test.bin", ios_base::binary|ios_base::in|ios_base::out|ios_base::trunc );

        size_t len = a1.cal_bin_size();
        size_t n1 = a1.write_to( ios );
        assert( n1 == len );

        ios.seekg( 0 );
        tree< vector > b1;
        size_t n2 = b1.read_from( ios );
        assert( n2 == len );
        cout << b1 << endl;
        test( b1 );

        ios.seekg( 0 );
        tree< vector > c1 = b1;
        size_t n3 = c1.read_from( ios );
        assert( n3 == len );
        cout << c1 << endl;
        test( c1 );
    }

    return 0;
}

//int main2()
//{
//    cout << "--- wstring <--> memory ---" << endl;
//    {
//        tree a1( L"1" );
//        tree& a2 = a1.addfirstchild( L"22" );
//        tree& a3 = a2.addfirstchild( L"333" );
//        tree& a4 = a3.addright( L"4444" );
//        tree& a5 = a2.addright( L"55555" );
//        tree& a6 = a5.addfirstchild( L"666666" );
//        tree& a7 = a6.addright( L"7777777" );
//
//        size_t len = a1.cal_bin_size();
//        char* p = new char[len];
//        size_t n1 = a1.write_to( p );
//        assert( n1 == len );
//
//        tree b1;
//        size_t n2 = b1.read_from( p );
//        assert( n2 == len );
//        wcout << b1 << endl;
//        test( b1 );
//
//        tree c1 = b1;
//        size_t n3 = c1.read_from( p );
//        assert( n3 == len );
//        wcout << c1 << endl;
//        test( c1 );
//
//        delete[] p;
//    }
//    cout << "--- wstring <--> stream ---" << endl;
//    {
//        tree a1( L"1" );
//        tree& a2 = a1.addfirstchild( L"22" );
//        tree& a3 = a2.addfirstchild( L"333" );
//        tree& a4 = a3.addright( L"4444" );
//        tree& a5 = a2.addright( L"55555" );
//        tree& a6 = a5.addfirstchild( L"666666" );
//        tree& a7 = a6.addright( L"7777777" );
//
//        fstream ios( "test.bin", ios_base::binary|ios_base::in|ios_base::out|ios_base::trunc );
//
//        size_t len = a1.cal_bin_size();
//        size_t n1 = a1.write_to( ios );
//        assert( n1 == len );
//
//        ios.seekg( 0 );
//        tree b1;
//        size_t n2 = b1.read_from( ios );
//        assert( n2 == len );
//        wcout << b1 << endl;
//        test( b1 );
//
//        ios.seekg( 0 );
//        tree c1 = b1;
//        size_t n3 = c1.read_from( ios );
//        assert( n3 == len );
//        wcout << c1 << endl;
//        test( c1 );
//    }
//
//    return 0;
//}

int main1()
{
    cout << "--- solid(5bytes) <--> memory ---" << endl;
    {
        tree a1( 1 );
        tree& a2 = a1.addfirstchild(2);
        tree& a3 = a2.addfirstchild(3);
        tree& a4 = a3.addright(4);
        tree& a5 = a2.addright(5);
        tree& a6 = a5.addfirstchild(6);
        tree& a7 = a6.addright(7);

        size_t len = a1.cal_bin_size();
        char* p = new char[len];
        size_t n1 = a1.write_to( p );
        assert( n1 == len );

        tree b1;
        size_t n2 = b1.read_from( p );
        assert( n2 == len );
        cout << b1 << endl;
        test( b1 );

        tree c1 = b1;
        size_t n3 = c1.read_from( p );
        assert( n3 == len );
        cout << c1 << endl;
        test( c1 );

        delete[] p;
    }
    cout << "--- solid(5bytes) <--> stream ---" << endl;
    {
        tree a1( 1 );
        tree& a2 = a1.addfirstchild(2);
        tree& a3 = a2.addfirstchild(3);
        tree& a4 = a3.addright(4);
        tree& a5 = a2.addright(5);
        tree& a6 = a5.addfirstchild(6);
        tree& a7 = a6.addright(7);

        fstream ios( "test.bin", ios_base::binary|ios_base::in|ios_base::out|ios_base::trunc );
        assert( ios );
        //ios.write( "0", 1 );
        assert( ios );
        size_t len = a1.cal_bin_size();
        size_t n1 = a1.write_to( ios );
        assert( n1 == len );

        ios.seekg( 0 );
        tree b1;
        size_t n2 = b1.read_from( ios );
        assert( n2 == len );
        cout << b1 << endl;
        test( b1 );

        ios.seekg( 0 );
        tree c1 = b1;
        size_t n3 = c1.read_from( ios );
        assert( n3 == len );
        cout << c1 << endl;
        test( c1 );
    }

    cout << "--- solid <--> memory ---" << endl;
    {
        tree a1( 1 );
        tree& a2 = a1.addfirstchild(2);
        tree& a3 = a2.addfirstchild(3);
        tree& a4 = a3.addright(4);
        tree& a5 = a2.addright(5);
        tree& a6 = a5.addfirstchild(6);
        tree& a7 = a6.addright(7);

        size_t len = a1.cal_bin_size();
        char* p = new char[len];
        size_t n1 = a1.write_to( p );
        assert( n1 == len );

        tree b1;
        size_t n2 = b1.read_from( p );
        assert( n2 == len );
        cout << b1 << endl;
        test( b1 );

        tree c1 = b1;
        size_t n3 = c1.read_from( p );
        assert( n3 == len );
        cout << c1 << endl;
        test( c1 );

        delete[] p;
    }
    cout << "--- solid <--> stream ---" << endl;
    {
        tree a1( 1 );
        tree& a2 = a1.addfirstchild(2);
        tree& a3 = a2.addfirstchild(3);
        tree& a4 = a3.addright(4);
        tree& a5 = a2.addright(5);
        tree& a6 = a5.addfirstchild(6);
        tree& a7 = a6.addright(7);

        fstream ios( "test.bin", ios_base::binary|ios_base::in|ios_base::out|ios_base::trunc );

        size_t len = a1.cal_bin_size();
        size_t n1 = a1.write_to( ios );
        assert( n1 == len );

        ios.seekg( 0 );
        tree b1;
        size_t n2 = b1.read_from( ios );
        assert( n2 == len );
        cout << b1 << endl;
        test( b1 );

        ios.seekg( 0 );
        tree c1 = b1;
        size_t n3 = c1.read_from( ios );
        assert( n3 == len );
        cout << c1 << endl;
        test( c1 );
    }
    cout << "--- non-solid <--> memory ---" << endl;
    {
        tree a1( "1" );
        tree& a2 = a1.addfirstchild( "22" );
        tree& a3 = a2.addfirstchild( "333" );
        tree& a4 = a3.addright( "4444" );
        tree& a5 = a2.addright( "55555" );
        tree& a6 = a5.addfirstchild( "666666" );
        tree& a7 = a6.addright( "7777777" );

        size_t len = a1.cal_bin_size();
        char* p = new char[len];
        size_t n1 = a1.write_to( p );
        assert( n1 == len );

        tree b1;
        size_t n2 = b1.read_from( p );
        assert( n2 == len );
        cout << b1 << endl;
        test( b1 );

        tree c1 = b1;
        size_t n3 = c1.read_from( p );
        assert( n3 == len );
        cout << c1 << endl;
        test( c1 );

        delete[] p;
    }
    cout << "--- non-solid <--> stream ---" << endl;
    {
        tree a1( "1" );
        tree& a2 = a1.addfirstchild( "22" );
        tree& a3 = a2.addfirstchild( "333" );
        tree& a4 = a3.addright( "4444" );
        tree& a5 = a2.addright( "55555" );
        tree& a6 = a5.addfirstchild( "666666" );
        tree& a7 = a6.addright( "7777777" );

        fstream ios( "test.bin", ios_base::binary|ios_base::in|ios_base::out|ios_base::trunc );

        size_t len = a1.cal_bin_size();
        size_t n1 = a1.write_to( ios );
        assert( n1 == len );

        ios.seekg( 0 );
        tree b1;
        size_t n2 = b1.read_from( ios );
        assert( n2 == len );
        cout << b1 << endl;
        test( b1 );

        ios.seekg( 0 );
        tree c1 = b1;
        size_t n3 = c1.read_from( ios );
        assert( n3 == len );
        cout << c1 << endl;
        test( c1 );
    }
    cout << "--- 2node <--> 5node ---" << endl;
    {
        tree a1( 1 );
        tree& a2 = a1.addfirstchild(2);
        tree& a3 = a2.addfirstchild(3);
        tree& a4 = a3.addright(4);
        tree& a5 = a2.addright(5);
        tree& a6 = a5.addfirstchild(6);
        tree& a7 = a6.addright(7);

        cout << a1 << endl;
        swap( a2, a5 );
        cout << a1 << endl;
        test( a1 );
    }
    cout << "--- 2node <--> 6node ---" << endl;
    {
        tree a1( 1 );
        tree& a2 = a1.addfirstchild(2);
        tree& a3 = a2.addfirstchild(3);
        tree& a4 = a3.addright(4);
        tree& a5 = a2.addright(5);
        tree& a6 = a5.addfirstchild(6);
        tree& a7 = a6.addright(7);

        cout << a1 << endl;
        swap( a2, a6 );
        cout << a1 << endl;
        test( a1 );
    }
    cout << "--- move 7node to 2node.left ---" << endl;
    {
        tree a1( 1 );
        tree& a2 = a1.addfirstchild(2);
        tree& a3 = a2.addfirstchild(3);
        tree& a4 = a3.addright(4);
        tree& a5 = a2.addright(5);
        tree& a6 = a5.addfirstchild(6);
        tree& a7 = a6.addright(7);
        tree& a8 = a7.addfirstchild(8);
        tree& a9 = a8.addright(9);

        cout << a1 << endl;
        cout << "   --->" << endl;
        tree& b = a1.addfirstchild();
        b.swap( a7 );
        a7.erase();
        cout << a1 << endl;

        test( a1 );
    }
    cout << "--- 2node operator= 5node ---" << endl;
    {
        tree a1( 1 );
        tree& a2 = a1.addfirstchild(2);
        tree& a3 = a2.addfirstchild(3);
        tree& a4 = a3.addright(4);
        tree& a5 = a2.addright(5);
        tree& a6 = a5.addfirstchild(6);
        tree& a7 = a6.addright(7);

        cout << a1 << endl;
        a2 = a5;
        test( a1 );
        cout << a1 << endl;
    }
    cout << "--- search odd number---" << endl;
    {
        tree a1( 1 );
        tree& a2 = a1.addfirstchild(2);
        tree& a3 = a2.addfirstchild(3);
        tree& a4 = a3.addright(4);
        tree& a5 = a2.addright(5);
        tree& a6 = a5.addfirstchild(6);
        tree& a7 = a6.addright(7);

        TREE_MACRO_TRAVERSE_BEGIN( const tree, 0, a1.traverse_front(), a1.traverse_back(), traverse_next )
            if( ptree->val()&1 ) cout << ptree->val() << " ";
        TREE_MACRO_TRAVERSE_END
        cout << endl;

        TREE_MACRO_TRAVERSE_BEGIN( const tree, 0, a1.traverse_back(), a1.traverse_front(), traverse_prev )
            if( ptree->val()&1 ) cout << ptree->val() << " ";
        TREE_MACRO_TRAVERSE_END
        cout << endl;

        // cann't work over in g++3.4.2
        //struct print
        //{
        //    void operator()( const tree* ptree, int depth_diff )
        //    {
        //        if( ptree->val()&1 ) cout << ptree->val() << " ";
        //    }
        //} print;
        //a1.traverse( print, 0 );
        //cout << endl;
        //a1.traverse_reverse( print, 0 );
        //cout << endl;
    }

    assert( foo::n == 0 ); // foo construct/destruct matching
    assert( tree::m == 0 ); // new/delete matching

    return 0;
}

int main()
{
    main1();
    //main2();
    main3();

    system( "pause" );
    return 0;
}