Re: Tree of maps and leaves
On Mar 2, 9:56 pm, Andre Majorel <che...@halliburton.com> wrote:
I need to store key bindings. Those are unusual in that the
"key" can in fact be a *sequence* of keystrokes (think Vim's
ga, gq, etc...).
Seems to me that a good way to store the bindings would be a
tree of associative arrays where the key is a keystroke and
the value is either a) an "action" that describes the function
to which that key sequence is bound or b) a similar
associative array.
For example, given the following bindings :
a action1
b action2
cx action3
cy action4
... there would be two associative arrays, one containing :
'a' => action1
'b' => action2
'c' => pointer-or-reference-to-whymakeitsimple
... and another, whymakeitsimple, containing :
'x' => action3
'y' => action4
Were this C, I'd malloc and cast my way out of it. I'm trying
to do it the STL way, however. Now, that might be slight
retardation on my part but I don't quite see how to do that
with std::map. Is some graph container from Boost the answer ?
Even in C, I'd not use a cast:-).
Basically, the structure you describe is a called a tri. The STL
doesn't contain such a structure, directly, but they are easy to
implement using maps. The solution I would use for Node to be
an abstract base class, with two derived classes, one for leaf
nodes, and one for inner nodes. In this case, the maps would
contain pointers, and not Nodes, e.g.:
class Node : public Interface // blocks copy and assignment,
{ // provides virtual destructor
public:
virtual Action* getAction() const = 0 ;
virtual Node* getNext ( char ch ) const = 0 ;
} ;
class LeafNode : public Node
{
public:
explicit LeafNode( Action* action )
: myAction( action )
{
}
virtual Action* getAction() const
{
return myAction ;
}
virtual Node* getNext( char ) const
{
return NULL ;
}
private:
Action* myAction ;
} ;
class InnerNode : public Node
{
public:
virtual Action* getAction() const
{
return NULL ;
}
virtual Node* getNext( char ch ) const
{
return myMap[ ch ] ;
}
template< typename ForwardIterator >
void insert(
ForwardIterator begin,
ForwardIterator end,
Action* action )
{
assert( begin != end ) ;
std::map< char, Node* >::const_iterator
entry = myMap.find( *begin ) ;
ForwardIterator next = begin ;
++ next ;
if ( next == end ) {
assert( entry == myMap.end() ) ;
entry.second = new LeafNode( action ) ;
} else {
if ( entry == myMap.end() ) {
entry = myMap.insert(
std::pair< char, Leaf* >( *begin, new
InnerNode ) ) ;
}
dynamic_cast< InnerNode* >(
entry->second)->insert( next, end, action ) ;
}
}
private:
std::map< char, Node* >
myMap ;
} ;
Also: if you're indexing with a sequence of char's, like this,
you really don't need an std::map. In such cases, a simple
array of UCHAR_MAX + 1 will do the trick, e.g.:
class InnerNode : public Node
{
InnerNode()
{
std::fill( begin( myMap ), end( myMap ), NULL ) ;
}
virtual Node* getNext( char ch ) const
{
return myMap[ (unsigned char)( ch ) ] ;
}
// ...
private:
Node* myMap[ UCHAR_MAX + 1 ] ;
} ;
(Of course, boost::array or tr1::array would be far better than
the C style arrays, if you can use one of them. The point is
that you're indexing with a small, integral value, into a fixed
size array.)
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34