How can I construct a SortedMap on top of Guava's computing map (or vice versa)? I want the sorted map keys as well as computing values on-the-fly.
The simplest is probably to use a ConcurrentSkipListMap and the memoizer idiom (see JCiP), rather than relying on the pre-built unsorted types from MapMaker. An example that you could use as a basis is a decorator implementation.