rust-lang/rust — pull request #18287 by michaelsproul (2014-10-24 19:10:07+00:00)
Title: Implement the collection views API for TrieMap.

I've implemented the new collection views API for TrieMap. I more or less followed the approach set out by @Gankro in BTreeMap, by using a `SearchStack`. There's quite a bit of unsafe code, but I've wrapped it safely where I think is appropriate. I've added tests to ensure everything works, and performance seems quite good.

```
test trie::bench_map::bench_find ... bench: 67879 ns/iter (+/- 4192)
test trie::bench_map::bench_find_entry ... bench: 186814 ns/iter (+/- 18748)
test trie::bench_map::bench_insert_large ... bench: 716612 ns/iter (+/- 160121)
test trie::bench_map::bench_insert_large_entry ... bench: 851219 ns/iter (+/- 20331)
test trie::bench_map::bench_remove ... bench: 838856 ns/iter (+/- 27998)
test trie::bench_map::bench_remove_entry ... bench: 981711 ns/iter (+/- 53046)
```

Using an entry is slow compared to a plain find, but is only ~15% slower for inserts and removes, which is where this API is most useful. I'm tempted to remove the standalone `remove` function in favour of an entry-based approach (to cut down on complexity).

I've added some more comments to the general part of the code-base, which will hopefully help the next person looking over this. I moved the three key structures to the top of the file so that the nesting structure is clearly visible, and renamed `Child` to `TrieNode` and `TrieNode` to `InternalNode` to improve clarity. If these changes are creeping, I'm happy to revert them.

Let me know if my use of `fail!` is ok, I was a little unsure of how specific to be. Some of the data-structures have various invariants that shouldn't be broken, so using `fail!` seemed appropriate.

## Still to do

* Modernise iterators (make them double-ended).
* Make the keys generic, or rename this data-structure (see: https://github.com/rust-lang/rust/issues/14902).
* Possibly move this code out of libcollections. [Searching Github for TrieMap turns up very few real results.][triemap-search]

Related issues: https://github.com/rust-lang/rust/issues/18009 and https://github.com/rust-lang/rust/issues/17320

[triemap-search]: https://github.com/search?utf8=%E2%9C%93&q=TrieMap+language%3ARust&type=Code&ref=searchresults