// tree.hpp
#ifndef TREE_HEADER__
#define TREE_HEADER__
#include <iostream>
template<typename T> class tree;
template<typename T> std::basic_ostream<char>& operator<<( std::basic_ostream<char>&, const tree<T>& );
//template<typename T> std::basic_ostream<wchar_t>& operator<<( std::basic_ostream<wchar_t>&, const tree<T>& );
////// definition /////////////////////////////////////////////////////////
template<typename T>
class tree
{
friend std::basic_ostream<char>& operator<< <T>( std::basic_ostream<char>&, const tree<T>& );
//friend std::basic_ostream<wchar_t>& operator<< <T>( std::basic_ostream<wchar_t>&, const tree<T>& );
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<class F> F traverse( F f, int start_depth_diff, tree<T>* from, tree<T>* to );
template<class F> F traverse( F f, int start_depth_diff, tree<T>* from );
template<class F> F traverse( F f, int start_depth_diff );
template<class F> F traverse( F f, int start_depth_diff, const tree<T>* from, const tree<T>* to ) const;
template<class F> F traverse( F f, int start_depth_diff, const tree<T>* from ) const;
template<class F> F traverse( F f, int start_depth_diff ) const;
template<class F> F traverse_reverse( F f, int start_depth_diff, tree<T>* from, tree<T>* to );
template<class F> F traverse_reverse( F f, int start_depth_diff, tree<T>* from );
template<class F> F traverse_reverse( F f, int start_depth_diff );
template<class F> F traverse_reverse( F f, int start_depth_diff, const tree<T>* from, const tree<T>* to ) const;
template<class F> F traverse_reverse( F f, int start_depth_diff, const tree<T>* from ) const;
template<class F> 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<class T> int tree<T>::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 <iomanip>
#include <utility>
#include <cassert>
template<typename T> struct tree_trait;
template<typename T> tree<T>::tree() : val_(T())
{
init_();
}
template<typename T> tree<T>::tree( const T& t ) : val_(t)
{
init_();
}
template<typename T> tree<T>::tree( const tree<T>& rhs ) : val_(rhs.val_)
{
init_();
tree<T>* p = this;
TREE_MACRO_TRAVERSE_BEGIN( const tree<T>, 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<typename T> tree<T>& tree<T>::operator=( const tree<T>& rhs )
{
if( this != &rhs )
{
tree<T> 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<typename T> tree<T>::~tree()
{
destroysubs_();
}
template<typename T> inline T& tree<T>::val() { return val_; }
template<typename T> inline const T& tree<T>::val() const { return ((tree*)this)->val(); }
template<typename T> inline tree<T>& tree<T>::parent() { return *ptrparent_; }
template<typename T> inline tree<T>& tree<T>::left() { return *ptrleft_; }
template<typename T> inline tree<T>& tree<T>::right() { return *ptrright_; }
template<typename T> inline tree<T>& tree<T>::childfirst() { return *ptrchildfirst_; }
template<typename T> inline tree<T>& tree<T>::childlast() { return *ptrchildlast_; }
template<typename T> inline const tree<T>& tree<T>::parent() const { return ((tree*)this)->parent(); }
template<typename T> inline const tree<T>& tree<T>::left() const { return ((tree*)this)->left(); }
template<typename T> inline const tree<T>& tree<T>::right() const { return ((tree*)this)->right(); }
template<typename T> inline const tree<T>& tree<T>::childfirst() const { return ((tree*)this)->childfirst(); }
template<typename T> inline const tree<T>& tree<T>::childlast() const { return ((tree*)this)->childlast(); }
template<typename T> tree<T>& tree<T>::root()
{
tree* p;
for( p=this; p->ptrparent_; p=p->ptrparent_ );
return *p;
}
template<typename T> inline const tree<T>& tree<T>::root() const { return ((tree*)this)->root(); }
template<typename T> inline tree<T>* tree<T>::traverse_front()
{
return this;
}
template<typename T> tree<T>* tree<T>::traverse_back()
{
tree* p = this;
for( ; p->ptrchildlast_; p=p->ptrchildlast_ );
return p;
}
template<typename T> tree<T>* tree<T>::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<typename T> tree<T>* tree<T>::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<typename T> inline const tree<T>* tree<T>::traverse_front() const { return ((tree*)this)->traverse_front(); }
template<typename T> inline const tree<T>* tree<T>::traverse_back() const { return ((tree*)this)->traverse_back(); }
template<typename T> inline const tree<T>* tree<T>::traverse_next( int& depth_diff ) const { return ((tree*)this)->traverse_next(depth_diff); }
template<typename T> inline const tree<T>* tree<T>::traverse_prev( int& depth_diff ) const { return ((tree*)this)->traverse_prev(depth_diff); }
template<typename T> template<class F> F tree<T>::traverse( F f, int start_depth_diff, tree<T>* from, tree<T>* to )
{
TREE_MACRO_TRAVERSE_BEGIN( tree<T>, start_depth_diff, from, to, traverse_next )
f( ptree, depth_diff );
TREE_MACRO_TRAVERSE_END
return f;
}
template<typename T> template<class F> inline F tree<T>::traverse( F f, int start_depth_diff, tree<T>* from )
{
return traverse( f, start_depth_diff, from, traverse_back() );
}
template<typename T> template<class F> inline F tree<T>::traverse( F f, int start_depth_diff )
{
return traverse( f, start_depth_diff, traverse_front() );
}
template<typename T> template<class F> F tree<T>::traverse( F f, int start_depth_diff, const tree<T>* from, const tree<T>* to ) const
{
TREE_MACRO_TRAVERSE_BEGIN( const tree<T>, start_depth_diff, from, to, traverse_next )
f( ptree, depth_diff );
TREE_MACRO_TRAVERSE_END
return f;
}
template<typename T> template<class F> inline F tree<T>::traverse( F f, int start_depth_diff, const tree<T>* from ) const
{
return traverse( f, start_depth_diff, from, traverse_back() );
}
template<typename T> template<class F> inline F tree<T>::traverse( F f, int start_depth_diff ) const
{
return traverse( f, start_depth_diff, traverse_front() );
}
template<typename T> template<class F> F tree<T>::traverse_reverse( F f, int start_depth_diff, tree<T>* from, tree<T>* to )
{
TREE_MACRO_TRAVERSE_BEGIN( tree<T>, start_depth_diff, from, to, traverse_prev )
f( ptree, depth_diff );
TREE_MACRO_TRAVERSE_END
return f;
}
template<typename T> template<class F> inline F tree<T>::traverse_reverse( F f, int start_depth_diff, tree<T>* from )
{
return traverse_reverse( f, start_depth_diff, from, traverse_front() );
}
template<typename T> template<class F> inline F tree<T>::traverse_reverse( F f, int start_depth_diff )
{
return traverse_reverse( f, start_depth_diff, traverse_back() );
}
template<typename T> template<class F> F tree<T>::traverse_reverse( F f, int start_depth_diff, const tree<T>* from, const tree<T>* to ) const
{
TREE_MACRO_TRAVERSE_BEGIN( const tree<T>, start_depth_diff, from, to, traverse_prev )
f( ptree, depth_diff );
TREE_MACRO_TRAVERSE_END
return f;
}
template<typename T> template<class F> inline F tree<T>::traverse_reverse( F f, int start_depth_diff, const tree<T>* from ) const
{
return traverse_reverse( f, start_depth_diff, from, traverse_front() );
}
template<typename T> template<class F> inline F tree<T>::traverse_reverse( F f, int start_depth_diff ) const
{
return traverse_reverse( f, start_depth_diff, traverse_back() );
}
template<typename T> void tree<T>::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<typename T> void tree<T>::erasesubs()
{
destroysubs_();
ptrchildfirst_ = 0;
ptrchildlast_ = 0;
}
template<typename T> tree<T>& tree<T>::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<typename T> tree<T>& tree<T>::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<typename T> void tree<T>::swap( tree<T>& t )
{
if( this != &t )
{
#ifdef _DEBUG
for( tree<T>* p=this; p; p=p->ptrparent_ ) assert( p != &t );
for( tree<T>* 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<typename T> inline void swap( tree<T>& lhs, tree<T>& 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<typename T, bool IS_SOLID=true> struct cal_bin_size_
{
// [ size_t:depth, T:val(algin align of size_t) ], ..., size_t:0
size_t operator()( const tree<T>& t )
{
size_t n=0;
TREE_MACRO_TRAVERSE_BEGIN( const tree<T>, 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<typename T> struct cal_bin_size_<T,false>
{
// [ size_t:depth, size_t:val_size, T:val(algin align of size_t) ], ..., size_t:0
size_t operator()( const tree<T>& t )
{
size_t n=0;
TREE_MACRO_TRAVERSE_BEGIN( const tree<T>, 0, t.traverse_front(), t.traverse_back(), traverse_next )
n += sizeof(size_t) + sizeof(size_t) + fit_size(tree_trait<T>::bin_size(ptree->val()));
TREE_MACRO_TRAVERSE_END
return n + sizeof(size_t);
}
};
template<typename T, bool IS_SOLID=true> struct write_to_
{
size_t operator()( const tree<T>& 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<T>, 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<sizeof(size_t)-sizeof(T)%sizeof(size_t); ++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>& 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<T>, 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<typename T> struct write_to_<T,false>
{
size_t operator()( const tree<T>& 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<T>, 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<T>::bin_size(ptree->val()); *(size_t*)pdst = len; pdst+=sizeof(size_t);
tree_trait<T>::bin_write( ptree->val(), pdst ); pdst+=len;
if( len%sizeof(size_t) != 0 ) // fill interval with 0
for( size_t i=0; i<sizeof(size_t)-len%sizeof(size_t); ++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>& 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<T>, 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<T>::bin_size(ptree->val()); dst.write( (const char*)&len, sizeof(size_t) ); n+=sizeof(size_t); assert( dst );
tree_trait<T>::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<typename T, bool IS_SOLID=true> struct read_from_
{
size_t operator()( tree<T>& 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<T>* 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>& 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<T>* 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<typename T> struct read_from_<T,false>
{
size_t operator()( tree<T>& 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<T>::bin_read( t.val(), n, psrc ); psrc+=fit_size(m);
assert( m == n );
tree<T>* 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<T>::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>& 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<T>::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<T>* 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<T>::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<typename T> size_t tree<T>::cal_bin_size() const
{
return cal_bin_size_< T, tree_trait<T>::is_solid >()( *this );
}
template<typename T> size_t tree<T>::write_to( void* dst) const
{
return write_to_< T, tree_trait<T>::is_solid >()( *this, dst );
}
template<typename T> size_t tree<T>::write_to( std::ostream& dst) const
{
return write_to_< T, tree_trait<T>::is_solid >()( *this, dst );
}
template<typename T> size_t tree<T>::read_from( const void* src )
{
return read_from_< T, tree_trait<T>::is_solid >()( *this, src );
}
template<typename T> size_t tree<T>::read_from( std::istream& src )
{
return read_from_< T, tree_trait<T>::is_solid >()( *this, src );
}
template<typename T> inline void tree<T>::init_()
{
ptrparent_ = 0;
ptrleft_ = 0;
ptrright_ = 0;
ptrchildfirst_ = 0;
ptrchildlast_ = 0;
}
template<typename T> void tree<T>::destroysubs_()
{
if( ptrchildlast_ )
{
TREE_MACRO_TRAVERSE_BEGIN( tree<T>, 0, traverse_back(), traverse_next(), traverse_prev )
ptree->val_.~T();
operator delete( ptree );
TREE_MACRO_TRAVERSE_END
}
}
template<typename T> std::basic_ostream<char>& operator<<( std::basic_ostream<char>& os, const tree<T>& t )
{
int depth = 0;
TREE_MACRO_TRAVERSE_BEGIN( const tree<T>, 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<typename T> std::basic_ostream<wchar_t>& operator<<( std::basic_ostream<wchar_t>& os, const tree<T>& t )
//{
// int depth = 0;
// TREE_MACRO_TRAVERSE_BEGIN( const tree<T>, 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<typename T> struct wipeoff_const_volatile { typedef T Type; };
template<typename T> struct wipeoff_const_volatile<const T> { typedef T Type; };
template<typename T> struct wipeoff_const_volatile<volatile T> { typedef T Type; };
template<typename T> struct tree_trait_ { static const bool is_solid = false; };
template<> struct tree_trait_<bool> { static const bool is_solid = true; };
template<> struct tree_trait_<signed char> { static const bool is_solid = true; };
template<> struct tree_trait_<unsigned char> { static const bool is_solid = true; };
template<> struct tree_trait_<signed short> { static const bool is_solid = true; };
template<> struct tree_trait_<unsigned short> { static const bool is_solid = true; };
template<> struct tree_trait_<signed int> { static const bool is_solid = true; };
template<> struct tree_trait_<unsigned int> { static const bool is_solid = true; };
template<> struct tree_trait_<signed long> { static const bool is_solid = true; };
template<> struct tree_trait_<unsigned long> { static const bool is_solid = true; };
template<> struct tree_trait_<signed long long> { static const bool is_solid = true; };
template<> struct tree_trait_<unsigned long long> { static const bool is_solid = true; };
template<> struct tree_trait_<float> { static const bool is_solid = true; };
template<> struct tree_trait_<double> { static const bool is_solid = true; };
template<> struct tree_trait_<long double> { static const bool is_solid = true; };
template<typename T> struct tree_trait
{
static const bool is_solid = tree_trait_< typename wipeoff_const_volatile<T>::Type >::is_solid;
};
////// trait for std::string /////////////////////////////////////////////////////////
#include <string>
template<typename T> struct tree_trait< std::basic_string<T> >
{
static const bool is_solid = false;
static inline size_t bin_size( const std::basic_string<T>& s )
{
return s.size()*sizeof(T);
}
static inline size_t bin_write( const std::basic_string<T>& 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<T>& s, size_t n, const void* p )
{
s = std::basic_string<T>( (const T*)p, n/sizeof(T) );
return n;
}
static inline size_t bin_write( const std::basic_string<T>& 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<T>& 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>( (T*)p, n/sizeof(T) );
delete[] p;
return n;
}
};
template<typename T> struct tree_trait< const std::basic_string<T> > : tree_trait< std::basic_string<T> > {};
template<typename T> struct tree_trait< volatile std::basic_string<T> > : tree_trait< std::basic_string<T> > {};
////// trait for std::vector<unsigned char> /////////////////////////////////////////////////////////
#include <vector>
template<> struct tree_trait< std::vector<unsigned char> >
{
static const bool is_solid = false;
static inline size_t bin_size( const std::vector<unsigned char>& s )
{
return s.size();
}
static inline size_t bin_write( const std::vector<unsigned char>& s, void* p )
{
memcpy( (char*)p, &s[0], s.size() );
return s.size();
}
static inline size_t bin_read( std::vector<unsigned char>& s, size_t n, const void* p )
{
s = std::vector<unsigned char>( (const unsigned char*)p, (const unsigned char*)p+n );
return n;
}
static inline size_t bin_write( const std::vector<unsigned char>& 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<unsigned char>& 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<unsigned char>( (const unsigned char*)p, (const unsigned char*)p+n );
delete[] p;
return n;
}
};
template<> struct tree_trait<const std::vector<unsigned char> > : tree_trait< std::vector<unsigned char> > {};
template<> struct tree_trait<volatile std::vector<unsigned char> > : tree_trait< std::vector<unsigned char> > {};
std::ostream& operator<<( std::ostream& os, const std::vector<unsigned char>& 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<s.size(); ++i )
os << ',' << std::setw(2) << std::setfill('0') << s[0];
}
os << ']';
os.fill(pf);
return os;
}
#endif // TREE_HEADER__
// test.cpp
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#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_<foo> { 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_<foo2> { static const bool is_solid = true; };
template <typename T>
void test( tree<T>& t )
{
const tree<T>* p = 0;
const tree<T>* 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<BYTE> <--> memory ---" << endl;
{
tree< vector<unsigned char> > a1( vector<unsigned char>(1,'1') );
tree< vector<unsigned char> >& a2 = a1.addfirstchild( vector<unsigned char>(2,'2') );
tree< vector<unsigned char> >& a3 = a2.addfirstchild( vector<unsigned char>(3,'3') );
tree< vector<unsigned char> >& a4 = a3.addright( vector<unsigned char>(4,'4') );
tree< vector<unsigned char> >& a5 = a2.addright( vector<unsigned char>(5,'5') );
tree< vector<unsigned char> >& a6 = a5.addfirstchild( vector<unsigned char>(6,'6') );
tree< vector<unsigned char> >& a7 = a6.addright( vector<unsigned char>(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<unsigned char> > b1;
size_t n2 = b1.read_from( p );
assert( n2 == len );
cout << b1 << endl;
test( b1 );
tree< vector<unsigned char> > c1 = b1;
size_t n3 = c1.read_from( p );
assert( n3 == len );
cout << c1 << endl;
test( c1 );
delete[] p;
}
cout << "--- vector<BYTE> <--> stream ---" << endl;
{
tree< vector<unsigned char> > a1( vector<unsigned char>(1,'1') );
tree< vector<unsigned char> >& a2 = a1.addfirstchild( vector<unsigned char>(2,'2') );
tree< vector<unsigned char> >& a3 = a2.addfirstchild( vector<unsigned char>(3,'3') );
tree< vector<unsigned char> >& a4 = a3.addright( vector<unsigned char>(4,'4') );
tree< vector<unsigned char> >& a5 = a2.addright( vector<unsigned char>(5,'5') );
tree< vector<unsigned char> >& a6 = a5.addfirstchild( vector<unsigned char>(6,'6') );
tree< vector<unsigned char> >& a7 = a6.addright( vector<unsigned char>(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<unsigned char> > b1;
size_t n2 = b1.read_from( ios );
assert( n2 == len );
cout << b1 << endl;
test( b1 );
ios.seekg( 0 );
tree< vector<unsigned char> > 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<wstring> a1( L"1" );
// tree<wstring>& a2 = a1.addfirstchild( L"22" );
// tree<wstring>& a3 = a2.addfirstchild( L"333" );
// tree<wstring>& a4 = a3.addright( L"4444" );
// tree<wstring>& a5 = a2.addright( L"55555" );
// tree<wstring>& a6 = a5.addfirstchild( L"666666" );
// tree<wstring>& 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<wstring> b1;
// size_t n2 = b1.read_from( p );
// assert( n2 == len );
// wcout << b1 << endl;
// test( b1 );
//
// tree<wstring> c1 = b1;
// size_t n3 = c1.read_from( p );
// assert( n3 == len );
// wcout << c1 << endl;
// test( c1 );
//
// delete[] p;
// }
// cout << "--- wstring <--> stream ---" << endl;
// {
// tree<wstring> a1( L"1" );
// tree<wstring>& a2 = a1.addfirstchild( L"22" );
// tree<wstring>& a3 = a2.addfirstchild( L"333" );
// tree<wstring>& a4 = a3.addright( L"4444" );
// tree<wstring>& a5 = a2.addright( L"55555" );
// tree<wstring>& a6 = a5.addfirstchild( L"666666" );
// tree<wstring>& 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<wstring> b1;
// size_t n2 = b1.read_from( ios );
// assert( n2 == len );
// wcout << b1 << endl;
// test( b1 );
//
// ios.seekg( 0 );
// tree<wstring> 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<foo2> a1( 1 );
tree<foo2>& a2 = a1.addfirstchild(2);
tree<foo2>& a3 = a2.addfirstchild(3);
tree<foo2>& a4 = a3.addright(4);
tree<foo2>& a5 = a2.addright(5);
tree<foo2>& a6 = a5.addfirstchild(6);
tree<foo2>& 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<foo2> b1;
size_t n2 = b1.read_from( p );
assert( n2 == len );
cout << b1 << endl;
test( b1 );
tree<foo2> 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<foo2> a1( 1 );
tree<foo2>& a2 = a1.addfirstchild(2);
tree<foo2>& a3 = a2.addfirstchild(3);
tree<foo2>& a4 = a3.addright(4);
tree<foo2>& a5 = a2.addright(5);
tree<foo2>& a6 = a5.addfirstchild(6);
tree<foo2>& 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<foo2> b1;
size_t n2 = b1.read_from( ios );
assert( n2 == len );
cout << b1 << endl;
test( b1 );
ios.seekg( 0 );
tree<foo2> c1 = b1;
size_t n3 = c1.read_from( ios );
assert( n3 == len );
cout << c1 << endl;
test( c1 );
}
cout << "--- solid <--> memory ---" << endl;
{
tree<foo> a1( 1 );
tree<foo>& a2 = a1.addfirstchild(2);
tree<foo>& a3 = a2.addfirstchild(3);
tree<foo>& a4 = a3.addright(4);
tree<foo>& a5 = a2.addright(5);
tree<foo>& a6 = a5.addfirstchild(6);
tree<foo>& 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<foo> b1;
size_t n2 = b1.read_from( p );
assert( n2 == len );
cout << b1 << endl;
test( b1 );
tree<foo> c1 = b1;
size_t n3 = c1.read_from( p );
assert( n3 == len );
cout << c1 << endl;
test( c1 );
delete[] p;
}
cout << "--- solid <--> stream ---" << endl;
{
tree<foo> a1( 1 );
tree<foo>& a2 = a1.addfirstchild(2);
tree<foo>& a3 = a2.addfirstchild(3);
tree<foo>& a4 = a3.addright(4);
tree<foo>& a5 = a2.addright(5);
tree<foo>& a6 = a5.addfirstchild(6);
tree<foo>& 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<foo> b1;
size_t n2 = b1.read_from( ios );
assert( n2 == len );
cout << b1 << endl;
test( b1 );
ios.seekg( 0 );
tree<foo> c1 = b1;
size_t n3 = c1.read_from( ios );
assert( n3 == len );
cout << c1 << endl;
test( c1 );
}
cout << "--- non-solid <--> memory ---" << endl;
{
tree<string> a1( "1" );
tree<string>& a2 = a1.addfirstchild( "22" );
tree<string>& a3 = a2.addfirstchild( "333" );
tree<string>& a4 = a3.addright( "4444" );
tree<string>& a5 = a2.addright( "55555" );
tree<string>& a6 = a5.addfirstchild( "666666" );
tree<string>& 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<string> b1;
size_t n2 = b1.read_from( p );
assert( n2 == len );
cout << b1 << endl;
test( b1 );
tree<string> 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<string> a1( "1" );
tree<string>& a2 = a1.addfirstchild( "22" );
tree<string>& a3 = a2.addfirstchild( "333" );
tree<string>& a4 = a3.addright( "4444" );
tree<string>& a5 = a2.addright( "55555" );
tree<string>& a6 = a5.addfirstchild( "666666" );
tree<string>& 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<string> b1;
size_t n2 = b1.read_from( ios );
assert( n2 == len );
cout << b1 << endl;
test( b1 );
ios.seekg( 0 );
tree<string> c1 = b1;
size_t n3 = c1.read_from( ios );
assert( n3 == len );
cout << c1 << endl;
test( c1 );
}
cout << "--- 2node <--> 5node ---" << endl;
{
tree<foo> a1( 1 );
tree<foo>& a2 = a1.addfirstchild(2);
tree<foo>& a3 = a2.addfirstchild(3);
tree<foo>& a4 = a3.addright(4);
tree<foo>& a5 = a2.addright(5);
tree<foo>& a6 = a5.addfirstchild(6);
tree<foo>& a7 = a6.addright(7);
cout << a1 << endl;
swap( a2, a5 );
cout << a1 << endl;
test( a1 );
}
cout << "--- 2node <--> 6node ---" << endl;
{
tree<foo> a1( 1 );
tree<foo>& a2 = a1.addfirstchild(2);
tree<foo>& a3 = a2.addfirstchild(3);
tree<foo>& a4 = a3.addright(4);
tree<foo>& a5 = a2.addright(5);
tree<foo>& a6 = a5.addfirstchild(6);
tree<foo>& a7 = a6.addright(7);
cout << a1 << endl;
swap( a2, a6 );
cout << a1 << endl;
test( a1 );
}
cout << "--- move 7node to 2node.left ---" << endl;
{
tree<foo> a1( 1 );
tree<foo>& a2 = a1.addfirstchild(2);
tree<foo>& a3 = a2.addfirstchild(3);
tree<foo>& a4 = a3.addright(4);
tree<foo>& a5 = a2.addright(5);
tree<foo>& a6 = a5.addfirstchild(6);
tree<foo>& a7 = a6.addright(7);
tree<foo>& a8 = a7.addfirstchild(8);
tree<foo>& a9 = a8.addright(9);
cout << a1 << endl;
cout << " --->" << endl;
tree<foo>& b = a1.addfirstchild();
b.swap( a7 );
a7.erase();
cout << a1 << endl;
test( a1 );
}
cout << "--- 2node operator= 5node ---" << endl;
{
tree<foo> a1( 1 );
tree<foo>& a2 = a1.addfirstchild(2);
tree<foo>& a3 = a2.addfirstchild(3);
tree<foo>& a4 = a3.addright(4);
tree<foo>& a5 = a2.addright(5);
tree<foo>& a6 = a5.addfirstchild(6);
tree<foo>& a7 = a6.addright(7);
cout << a1 << endl;
a2 = a5;
test( a1 );
cout << a1 << endl;
}
cout << "--- search odd number---" << endl;
{
tree<foo> a1( 1 );
tree<foo>& a2 = a1.addfirstchild(2);
tree<foo>& a3 = a2.addfirstchild(3);
tree<foo>& a4 = a3.addright(4);
tree<foo>& a5 = a2.addright(5);
tree<foo>& a6 = a5.addfirstchild(6);
tree<foo>& a7 = a6.addright(7);
TREE_MACRO_TRAVERSE_BEGIN( const tree<foo>, 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<foo>, 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<foo>* 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<foo>::m == 0 ); // new/delete matching
return 0;
}
int main()
{
main1();
//main2();
main3();
system( "pause" );
return 0;
}
应该多加些注释.
TCL比你写的代码好!
- 访问:303770次
- 积分:2050分
- 排名:第2名
- 随笔:205篇
- 评论:2765条
随笔分类
随笔归档
个人相册
阅读排行榜
- windows下最好的C++ IDE (23795)
- 实时数据库的简介(初稿) (17096)
- 浮点数 和 EPSILON (文章越写越啰嗦) (8550)
- 用OpenCV显示一幅图像到指定的窗体 (6736)
- 个人资料 (6649)
- 访客留言 (6259)
- 代码片断 (5320)
- 读取NTFS的USN(获取文件的历史操作记录,即使这个文件已被删除) (4710)
- [夜语] “兆”是10的几次方 (4031)
- Qt 4.7.3 之 代理认证 (3982)
评论排行榜
- windows下最好的C++ IDE (473)
- 实时数据库的简介(初稿) (406)
- 个人资料 (176)
- 访客留言 (146)
- 代码片断 (100)
- 测试一下 Intel C++8.0 对模板的支持程度 (64)
- C/C++试题(汇总中) (48)
- 佛学佳句 (47)
- 普通话 与 粤语 (41)
- 浮点数 和 EPSILON (文章越写越啰嗦) (40)