#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