I'm very interested in having tree container concepts in Boost. It's my plan
to submit such a thing to Boost in the summer. Currently I only have a
rank_tree implementation (log2 n, or better on all ops) so having someone
else work on other types of tree implementations would be awsome ;-)
I'd be happy to share ideas. I have included the implementation that I was referring to in the previous e-mail. I know that it needs a lot of work if it were to be submitted to boost, but I just wanted to gague reactions before I did any major work to it.
The tree_node_map class provides an implementation to a basic tree node of variable branching size. The implementation here uses the std::map to implement the children, but this could equally be a std::list, std::vector or any suitable container; it could even be a low-level implementation (for performance) or a fixed-size array (for n-ary nodes).
The tree class is just a wrapper around a tree node that provides access to a root element. This would need some major work and additional support (e.g. post/pre/in-order traversal iterators) if it were to be useful.
The trie class is an application of the tree class that provides operations for adding and looking for items in an associative container-like way. There is a bug with the word count (it does not track with std::map<>::size() on the same data).
The trie class operates on a key that is a sequence of elements. If the key is std::string, then the trie class will construct the tree operating on characters as lookup for the child nodes, e.g.
*-h-e-l-l-o-$ /-$ +-w-o-r-l-d--+-s-$
This is useful for associative lookup in two ways:
* it should provide faster lookup than a std::map because it is iterating through the key as it moves down the list, therefore it does not need to recompare the strings every time it moves around the tree (unlike the red-black binary tree used in most std::map implementations)
* it stores the strings in a compressed form (although this benefit is removed by the need for the space to store the tree structure)
The lookup function for the trie class will add an item if the key is not currently in the trie structure, whereas find will not. Both operate on a first to last iterator principle.
I hope this helps with your submission in the Summer. If you want we could combine forces to develop the library.
-rhd-
_________________________________________________________________
It's fast, it's easy and it's free. Get MSN Messenger today! http://messenger.msn.co.uk
#ifndef __STL__TRIE #define __STL__TRIE # include <cstdio> # include <map> # include <windows.h>
# define null NULL
////////////////////////////////////////////////////////////////////////////////////////////////
namespace stl
{
template< typename T, typename Index = int, class Allocator = std::allocator< T > >
class tree_node_map
{
public:
typedef T value_type;
typedef Allocator allocator_type;
typedef Index index_type;
public:
typedef typename Allocator::template rebind< T >::other
value_allocator;
public:
typedef typename value_allocator::reference reference;
typedef typename value_allocator::const_reference const_reference;
typedef typename value_allocator::pointer pointer;
typedef typename value_allocator::const_pointer const_pointer;
public:
typedef typename value_allocator::size_type size_type;
typedef typename value_allocator::difference_type difference_type;
public:
typedef std::map< index_type, tree_node_map * > child_container;
public:
class iterator
{
friend class tree_node_map;
private:
typename child_container::iterator node;
public:
inline iterator & operator++()
{
++node;
return( *this );
}
inline iterator & operator--()
{
--node;
return( *this );
}
public:
inline typename tree_node_map & operator*()
{
return( *( node -> second ));
}
inline typename tree_node_map * operator->()
{
return( node -> second );
}
public:
inline bool operator==( const iterator & i )
{
return( node == i.node );
}
inline bool operator!=( const iterator & i )
{
return( node != i.node );
}
protected:
inline iterator( typename child_container::iterator i ): node( i )
{
}
public:
inline iterator( const iterator & i ): node( i.node )
{
}
inline iterator(): node()
{
}
};
public:
typedef typename child_container::const_iterator const_iterator;
public:
value_type data;
private:
child_container children;
public:
inline iterator first_child()
{
return( children.begin());
}
inline iterator last_child()
{
return( children.end());
}
public:
inline const_iterator first_child() const
{
return( children.begin());
}
inline const_iterator last_child() const
{
return( children.end());
}
public:
inline size_type number_of_children() const
{
return( children.size());
}
inline bool isleaf() const
{
return( children.empty());
}
public:
inline iterator insert( index_type it )
{
iterator i = children.find( it );
if( i == children.end())
{
typename Allocator::template rebind< tree_node_map >::other
na;
tree_node_map * p = na.allocate( sizeof( tree_node_map ));
na.construct( p, tree_node_map< T, Index, Allocator >( value_type()));
return( children.insert( std::make_pair( it, p )).first );
}
return( i );
}
public:
inline iterator insert( index_type it, value_type vt )
{
iterator & i = insert( it );
i -> data = vt;
return( i );
}
public:
inline void erase_children()
{
typename Allocator::template rebind< tree_node_map >::other
na;
for( iterator i = children.begin(); i != children.end(); ++i )
{
na.destroy( &( *i ));
na.deallocate( &( *i ), sizeof( tree_node_map ));
}
children.clear();
}
public:
inline iterator operator[]( index_type it )
{
return( insert( it, value_type()));
}
inline iterator find( index_type it )
{
return( children.find( it ));
}
public:
inline tree_node_map( const value_type & vt ): data( vt )
{
}
inline ~tree_node_map()
{
erase_children();
}
};
}
////////////////////////////////////////////////////////////////////////////////////////////////
namespace stl
{
template< class TreeNode >
class tree
{
public:
typedef TreeNode tree_node_type;
typedef typename tree_node_type::value_type value_type;
typedef typename tree_node_type::index_type index_type;
typedef typename tree_node_type::allocator_type allocator_type;
typedef typename tree_node_type::size_type size_type;
public:
typedef typename tree_node_type::iterator iterator;
typedef typename tree_node_type::const_iterator const_iterator;
private:
tree_node_type * root_node;
public:
inline tree_node_type * root()
{
return( root_node );
}
public:
inline tree()
{
typename allocator_type::template rebind< tree_node_type >::other
na;
root_node = na.allocate( sizeof( tree_node_type ));
na.construct( root_node, tree_node_type( value_type()));
}
inline ~tree()
{
if( root_node != null )
{
typename allocator_type::template rebind< tree_node_type >::other
na;
na.destroy( root_node );
na.deallocate( root_node, sizeof( tree_node_type ));
}
}
};
}
////////////////////////////////////////////////////////////////////////////////////////////////
namespace stl
{
template< class Key, typename T >
class trie
{
public:
typedef Key key_type;
typedef typename key_type::value_type index_type;
typedef T value_type;
typedef tree_node_map< value_type, index_type > node_type;
typedef tree< node_type > tree_type;
public:
typedef typename tree_type::size_type size_type;
typedef typename tree_type::iterator iterator;
private:
tree_type tree;
unsigned long numwords;
public:
template< typename Iterator >
inline T & lookup( Iterator first, Iterator last )
{
if( !find( first, last )) ++numwords;
iterator i = tree.root() -> first_child();
for( ; first != last; ++first )
{
i = i -> insert( *first ); // move down
}return( i -> insert( null ) -> data );
}
template< typename Container >
inline T & operator[]( const Container & c )
{
return( lookup( c.begin(), c.end()));
}
inline T & operator[]( const index_type * ia )
{
return( operator[]( Key( ia )));
}
public:
template< typename Iterator >
inline bool find( Iterator first, Iterator last )
{
iterator i = tree.root() -> first_child();
for( ; first != last; ++first )
{
iterator j = i -> find( *first );
if( j == i -> last_child())
{
return( false );
}
i = j; // move down
}
return(( first == last ) && ( i -> find( null ) != i -> last_child()));
}
template< typename Container >
inline bool find( const Container & c )
{
return( find( c.begin(), c.end()));
}
inline bool find( const index_type * ia )
{
return( find( Key( ia )));
}
public:
inline size_type size() const
{
return( numwords );
}
inline bool empty() const
{
return( size() == 0 );
}
public:
inline trie(): tree(), numwords( 0 )
{
tree.root() -> insert( index_type( 0 ), value_type());
}
};
}
#endif
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
