Add a type of ordered map that will allow you to insert a key/value at a certain index

[GoogleCodeExporter]

Right now, there is no functionality of that sort in any map.
It would be really nice to have an ordered map API that has that functionality.

Thanks :)

Original issue reported on code.google.com by ilan...@gmail.com on 2 Nov 2010 at 6:31

[GoogleCodeExporter]

This has crossed my mind several times. Recently there was someone asking on 
stackoverflow what kind of structure would be useful to implement a 
spreadsheet, with operations like merging columns, inserting columns, moving 
columns and so on (can't find it), and such a thing would be useful.

Another use-case: you maintain a set by randomly adding objects, deleting 
objects, applying operations on existing objects. You choose by code like "int 
n = random.nextInt(objects.size());". If deletions weren't there, a List<T> 
would be fine. 

The "obvious" solution to this is a red-black tree where each node is augmented 
by its descendants count, so this could support by-index operations in O(logn). 
In Java, it could look like a SortedMap (say, IndexableSortedMap) where the 
keySet() also extends List<K>, and a IndexableSortedSet could follow.

I saw the code of TreeMap, and was disappointed by the amount of work that this 
would involve. Sometimes I feel there are certain SPIs missing from java 
collections - that would make it easy for people to implement structures. 
Copying TreeMap's code? Rather unsatisfactory... (I understand people who took 
this root with copying ConcurrentHashMap would wish there was an easier way 
too!). 

I have a vauge feeling that Scala collections might be in a better position for 
such kind of extension, but those have a rather steep learning curve too. 
Anyway, enough of a brain-dump.

Original comment by jim.andreou on 2 Nov 2010 at 9:54

[GoogleCodeExporter]

And lets not forget SortedMap's comparator, a big, big complication. How would 
you expect that to behave, or a get(key) invocation, in face of such indexed 
updates?

Original comment by jim.andreou on 2 Nov 2010 at 10:43

[GoogleCodeExporter]

Original comment by kevinb@google.com on 18 Jul 2011 at 3:35

• Changed state: Triaged
• Added labels: Type-Enhancement

[GoogleCodeExporter]

What might be doable is providing Entry<K, V> entryAt(int index), which would 
have pretty well-defined semantics.

Original comment by wasserman.louis on 16 Oct 2011 at 10:47

[GoogleCodeExporter]

Original comment by fry@google.com on 10 Dec 2011 at 3:51

• Added labels: Package-Collect

[GoogleCodeExporter]

Original comment by fry@google.com on 16 Feb 2012 at 7:17

• Changed state: Acknowledged

[GoogleCodeExporter]

I don't think there's a conceivable sensible semantics for this, as it is -- at 
least, not as long as it's also a SortedMap.

If it isn't a sorted map, it becomes a Map with some notion of entry order, 
though.  ImmutableMap already has that to some extent.  I guess the only 
remaining case -- which I can't imagine has very much demand -- would be a 
LinkedHashMap variant that actually let you mess with the entry order somehow?  
How would that even work with the Map interface?

Original comment by wasserman.louis on 21 May 2012 at 8:34

[GoogleCodeExporter]

Original comment by kevinb@google.com on 30 May 2012 at 7:43

• Added labels: Type-Addition
• Removed labels: Type-Enhancement

[GoogleCodeExporter]

Original comment by kevinb@google.com on 22 Jun 2012 at 6:16

• Changed state: Research

[GoogleCodeExporter]

This issue has been migrated to GitHub.

It can be found at https://github.com/google/guava/issues/<id>

Original comment by cgdecker@google.com on 1 Nov 2014 at 4:15

• Added labels: MigratedToGitHub

[GoogleCodeExporter]

Original comment by cgdecker@google.com on 1 Nov 2014 at 4:18

• Changed state: Migrated

[GoogleCodeExporter]

Original comment by cgdecker@google.com on 3 Nov 2014 at 9:09

• Added labels: Restrict-AddIssueComment-Commit