Re: Tree of maps and leaves
Kai-Uwe Bux wrote:
Andre Majorel wrote:
On 2009-03-04, Kai-Uwe Bux <jkherciueh@gmx.net> wrote:
Andre Majorel 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
[snip]
I don't understand the precise requirement, yet. What counts
as a collision? In particular, should the data structure
allow or forbid entries where one is a prefic of the other,
i.e., can you have
abc action7
ab action8
Yes. Having bindings for both "ab" and "abc" would not achieve
anything useful. The "abc" binding would never be seen.
I suppose one could argue that binding "ab" to somefunc while
keeping the old "abc" binding around would allow a user to
temporarily bind "ab" and easily restore all the hidden "ab?*"
bindings by unbinding "ab".
Whether that convenience would be worth the potential confusion
caused by unreachable bindings appearing in the list, I don't
know.
Assuming that those do count as collisions, should inserting a
new string/action pair fail (with some return code) when a
collision occurs or will client code ensure that this never
happens?
If the hidden bindings cannot exist along the new one, the most
useful behaviour would be to silently replace them, IMHO. I know
that's what I would want as a user.
I don't think that silence is a good thing. I would at least return a bool
to indicate the presence of a collision. But hey, it's your specs.
Also, should the data structure support erasure of
string/action pairs?
That would be nice.
Ok, the following proof of concept tries to use the STL and get away
without non-standard components. The only exception is the use of
tr1::function, which is a convenient way to store commands.
Here is another version that flags collisions. (It also contains a bugfix
that became aparent because of this.)
#include <iostream>
#include <map>
#include <utility>
#include <string>
#include <vector>
#include <algorithm>
#include <tr1/functional>
#include <cstring>
#include <limits>
#include <iostream>
#include <iomanip>
#include <cassert>
class command_parser {
public:
typedef char key;
typedef std::string multikey;
typedef std::tr1::function< void( multikey const & ) > command;
private:
typedef std::pair< unsigned, command > entry;
typedef std::map< multikey, entry > table;
/*
Idea: the unsigned part of an entry provides the count
of all stored string/command pairs for which this node
is indexed by a strict prefix of the string. Leaves, therefore,
have a count of 0 and that is how one can recognize them.
The command part is the command to be executed.
*/
table the_table;
command the_default_cmd;
table::iterator first ( multikey const & prefix ) {
return ( the_table.lower_bound( prefix ) );
}
table::iterator last ( multikey const & prefix ) {
multikey next = prefix;
while ( next.size() > 0 ) {
if ( next[ next.size()-1 ] < std::numeric_limits< key >::max() ) {
++ next[ next.size()-1 ];
break;
}
next.erase( next.end()-1 );
}
if ( next.empty() ) {
return ( the_table.end() );
}
return ( the_table.lower_bound( next ) );
}
bool prune_table ( multikey prefix ) {
bool result = false;
table::iterator from = first( prefix );
table::iterator to = last( prefix );
for ( table::iterator iter = from; iter != to; ++iter ) {
if ( iter->second.first == 0 ) {
erase( iter->first );
result = true;
}
}
while ( prefix.size() > 0 ) {
prefix.erase( prefix.end() - 1 );
table::iterator where = the_table.find( prefix );
if ( where != the_table.end() && where->second.first == 0 ) {
erase( where->first );
result = true;
}
}
return ( result );
}
public:
template < typename Func >
command_parser ( Func f )
: the_table ()
, the_default_cmd ( f )
{}
template < typename KeyInputIter >
void parse ( KeyInputIter from, KeyInputIter to ) {
multikey index;
while ( from != to ) {
index += *from++;
table::const_iterator where = the_table.find( index );
if ( where == the_table.end() ) {
the_default_cmd( index );
index.clear();
continue;
}
if ( where->second.first > 0 ) {
continue;
}
where->second.second( index );
index.clear();
}
}
bool insert ( multikey const & index, command const & cmd ) {
/*
A collision happens if index is a prefix of a stored value
(i.e., at index, an empty box is stored; or if any prefix of
index is a command.
In case of a collision, the new value silently overwrites the
old one.
*/
bool result = prune_table( index );
for ( multikey::size_type n = 0; ++n < index.size(); ) {
multikey prefix ( index.begin(), index.begin() + n );
++ the_table[ prefix ].first;
}
the_table[ index ].second = cmd;
return ( result );
}
bool erase ( multikey const & index ) {
assert( the_table.find( index ) != the_table.end() );
assert( the_table.find( index )->second.first == 0 );
for ( multikey::size_type n = 0; ++n < index.size(); ) {
multikey prefix ( index.begin(), index.begin() + n );
table::iterator where = the_table.find( prefix );
--where->second.first;
if ( where->second.second == 0 ) {
the_table.erase( where );
}
}
}
}; // command_parser
void banner ( std::string const & ) {
std::cout << "banner\n";
}
void print ( std::string const & msg ) {
std::cout << msg << "\n";
}
int main ( void ) {
std::string input ( "ababacdefgab" );
command_parser cp ( &banner );
std::cout << std::boolalpha << cp.insert( "ab", &print ) << "\n";
std::cout << std::boolalpha << cp.insert( "ba", &print ) << "\n";
std::cout << std::boolalpha << cp.insert( "ac", &print ) << "\n";
std::cout << std::boolalpha << cp.insert( "aba", &print ) << "\n";
cp.parse( input.begin(), input.end() );
}
Best
Kai-Uwe Bux