ReverseTrie question

[postacik]

            var x = new Emitter.Utility.ReverseTrie<string>(-1);
            x.RegisterHandler("test/", "Hello");
            x.RegisterHandler("test/", "Hello2");
            var y = x.Match("test/");

The match result y is ["Hello"] in this code sample.

Is this the expected behaviour or should it be ["Hello2"] or ["Hello","Hello2"]?

[Florimond]

Yes, it is the expected behavior. The new handler for this exact path replaces the old one.

[postacik]

The new handler for this exact path replaces the old one => No, in your implementation the old one stays.

[postacik]

And in my application 2 different objects share the same emitter instance and they both subscribe to the same channel. This behavior has a side effect which does not let one of them receive the channel messages in its own handler.

[postacik]

By the way, I'm trying to extend the JavaScript library to support inline event handlers and I wrote a JavaScript version of ReverseTrie class:

var ReverseTrie = (function () {

    function ReverseTrie(level) {
        this.children = {};
        this.level = level || 0;
        this.value = null;
    }

    ReverseTrie.prototype.registerHandler = function (channel, value) {
        // Add the value or replace it.
        this.addOrUpdate(this.createKey(channel), 0, () => value, (old) => value);       
    };

    ReverseTrie.prototype.unRegisterHandler = function (channel) {
        var removed = this.tryRemove(this.createKey(channel), 0);       
    };

    ReverseTrie.prototype.recurMatch = function (query, posInQuery, children) {
        var matches = [];
        if (posInQuery == query.length)
            return matches;
        var childNode = children["+"];
        if (childNode) {
            if (childNode.value)
                matches.push(childNode.value);
            matches = matches.concat(this.recurMatch(query, posInQuery + 1, childNode.children));
        }
        childNode = children[query[posInQuery]];
        if (childNode) {
            if (childNode.value)
                matches.push(childNode.value);
            matches = matches.concat(this.recurMatch(query, posInQuery + 1, childNode.children));
        }
        return matches;
    };

    ReverseTrie.prototype.match = function (channel) {
        var query = this.createKey(channel);
        var result =  this.recurMatch(query, 0, this.children);
        return result;
    };

    ReverseTrie.prototype.createKey = function (channel) {
        return channel.replace(new RegExp("^[/]+"), "").replace(new RegExp("[/]+$"), "").split("/");
    };

    ReverseTrie.prototype.addOrUpdate = function (key, position, addFunc, updateFunc) {
        if (position == key.length)
        {
            // There's already a value
            if (this.value)
                return updateFunc(this.value);

            // No value, add it
            this.value = addFunc();
            return this.value;
        }

        var child = null;
        if (this.children[key[position]]) {
            child = this.children[key[position]];
        } else {
            child = new ReverseTrie(position);
            this.children[key[position]] = child;
        }           
        return child.addOrUpdate(key, position + 1, addFunc, updateFunc);
    };

    ReverseTrie.prototype.tryRemove = function (key, position) {
        if (position == key.length)
        {
            if (!this.value)
                return false;
            this.value = null;
            return true;
        }

        // Remove from the child
        var child = this.children[key[position]];
        if (child)
            return child.tryRemove(key, position + 1);

        this.value = null;
        return false;
    };

    return ReverseTrie;
})();

[Florimond]

Right, didn't read properly, sorry. Then it's a bug, it should be replaced. I suppose you already know where the problem is situated? I'll check the python implementation too.

Not enough unit tests I guess...

You can certainly integrate your reverse trie with the rest of the JS version if you want, thanks a lot. It's been a while I've been meaning to do so.

[postacik]

According to your default behavior description, AddOrUpdate function should be modified like this. Am I right?

        private object AddOrUpdate(string[] key, int position, AddFunc addFunc, UpdateFunc updateFunc)
        {
            if (position == key.Length)
            {
                // TODO check lock's position
                lock (this)
                {
                    // There's already a value
                    if (this.Value != default(T))
                        this.Value = updateFunc(this.Value);
                    else
                        this.Value = addFunc();
                    return this.Value;
                }
            }

            // Create a child
            var child = Utils.GetOrAddToHashtable(Children, key[position], new ReverseTrie<T>((short)position)) as ReverseTrie<T>;
            return child.AddOrUpdate(key, position + 1, addFunc, updateFunc);
        }

[Florimond]

Yes, that's what I understand.

By the way, the python version, which I wrote from scratch, doesn't use this system of addFunc and updateFunc. I left it in the C# version because it was already there, but do you see any use for it?

[postacik]

As long as you use it like this, it has no use because it simply sets the value, when added or updated.

this.AddOrUpdate(CreateKey(channel), 0, () => value, (old) => value); It would be of use when you have special add and update algorithms.

Probably you could simplify it like this (I did not test this!)

this.SetValue(CreateKey(channel), 0, value);

     private object SetValue(string[] key, int position, T value)
        {
            if (position == key.Length)
            {
                // TODO check lock's position
                lock (this)
                {
                    this.Value = value;
                    return this.Value;
                }
            }

            // Create a child
            var child = Utils.GetOrAddToHashtable(Children, key[position], new ReverseTrie<T>((short)position)) as ReverseTrie<T>;
            return child.SetValue(key, position + 1, value);
        }

[postacik]

An additional note:

I was thinking a global message handler would suffice for most needs but after some work, I realized that an inline message handler defined in the subscribe request would make things much easier especially when you have channels like 'channel/+/subchannel'. And your trie implementation is just the fit for this requirement.

[postacik]

I updated the dart library. Now the subscribe function has an inline message handler parameter.