[erlang-questions] Trie NIFs

Michael Truog <>
Sat Feb 11 23:29:20 CET 2012


I added a function fold_match/4 which can do what you require:
1> Paths = trie:new(["/usr/bin","/usr/include/X12/Xtrans","/usr/include/X11/Xtrans"]).
{47,47,
 {{{117,117,
    {{{115,115,
       {{{114,114,{{{47,47,{{{98,105,{{...},...}},error}}},error}}},
         error}}},
      error}}},
   error}}}
2> trie:fold_match("/usr/include/*/Xtrans", fun(K, _, L) -> [K | L] end, [], Paths).
["/usr/include/X12/Xtrans","/usr/include/X11/Xtrans"]
3>

On 02/06/2012 03:54 PM, Michael Truog wrote:
> That code doesn't currently contain regex support, but you could iterate on the contents based on a common prefix held within the trie, while checking each string passed to the anonymous function to do this programmatically.  To do things this way, you would use:
> trie:fold_similar("/usr/include/", Function, Accumulator, Trie)
>
> Some simple pattern matching (perhaps using "*") could probably be grafted on in a similar way, where you would be matching string suffixes after the "*" character's last occurrence.
>
> On 02/06/2012 12:45 PM, Zabrane Mickael wrote:
>> Try this:
>> https://github.com/okeuday/trie
>>
>> See bench:
>> http://okeuday.livejournal.com/16941.html
>>
>> Regards,
>> Zabrane
>>
>>
>> On Feb 6, 2012, at 9:37 PM, Jon Watte wrote:
>>
>>> Why does it have to be NIF? On the surface, that looks like a data
>>> structure that might actually work reasonably well as an Erlang native
>>> library. (Modification generates log-N garbage)
>>>
>>> Sincerely,
>>>
>>> jw
>>>
>>>
>>> --
>>> Americans might object: there is no way we would sacrifice our living
>>> standards for the benefit of people in the rest of the world.
>>> Nevertheless, whether we get there willingly or not, we shall soon
>>> have lower consumption rates, because our present rates are
>>> unsustainable.
>>>
>>>
>>>
>>> On Mon, Feb 6, 2012 at 8:43 AM, ori brost < <mailto:>> wrote:
>>>> I'm looking for a trie NIF library that can support strings as trie
>>>> tokens, and basic pattern matching with a '.' like wildcard (i.e. If /
>>>> is the trie separator and the tree contains 3 entries: /usr/bin,
>>>> /usr/include/X12/XTrans, /usr/include/X11/Xtrans, then I can do
>>>>
>>>> trie:get_all(["usr", "include", '.', "XTrans"])
>>>>
>>>> and it will return
>>>>
>>>> [["usr","include","X11","Xtrans"],
>>>>  ["usr","include","X12","Xtrans"]]
>>>>
>>>> It would also be nice to have a
>>>>
>>>> trie:get_single(["usr","include", '.', "XTrans"])
>>>>
>>>> that returns only one of the matching entries
>>>>
>>>> Does anyone know of such a NIF library? Or something similar enough
>>>> that I can modify it for these needs?
>>>>
>>>> Regards, OriB.
>>>> _______________________________________________
>>>> erlang-questions mailing list
>>>>  <mailto:>
>>>> http://erlang.org/mailman/listinfo/erlang-questions
>>> _______________________________________________
>>> erlang-questions mailing list
>>>  <mailto:>
>>> http://erlang.org/mailman/listinfo/erlang-questions
>>
>>
>>   
>> _______________________________________________
>> erlang-questions mailing list
>>  <mailto:>
>> http://erlang.org/mailman/listinfo/erlang-questions
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20120211/81ba2c7c/attachment.html>


More information about the erlang-questions mailing list