Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

The standard library is missing a mutable.TreeMap implementation. #4147

Closed
scabug opened this issue Jan 10, 2011 · 12 comments
Closed

The standard library is missing a mutable.TreeMap implementation. #4147

scabug opened this issue Jan 10, 2011 · 12 comments
Assignees
Milestone

Comments

@scabug
Copy link

scabug commented Jan 10, 2011

= problem =
When converting code-bases as a proof of concept it is often necessary to have some working code after a short time. Having no mutable sorted implementations of Map is a big obstacle, because it forces code using it to be rewritten (which might make sense in a later step though) and makes it hard to argue that Scala is a good upgrade path from Java.

= analysis =
immutable.TreeMap exists but mutable implementation is missing in Scala's standard library.

= enhancement recommendation =
Scala should ship with support for this data structure.

@scabug
Copy link
Author

scabug commented Jan 10, 2011

Imported From: https://issues.scala-lang.org/browse/SI-4147?orig=1
Reporter: @soc

@scabug
Copy link
Author

scabug commented Jan 20, 2011

tim8dev said:
Well, I'm currently working on a mutable TreeSet/Map Implementation based on an AVL Tree.
While it is on average a bit more costly (but still O(log n)) to insert a value into an AVL Tree compared to a Red-Black Tree, it can check containments faster than Red-Black Trees because they are more balanced.

Well.. I've only implemented insert and contains yet, but we'll see what I can do over the weekend.
Some performance results:
n = 1 << 28
Creating Sets through insertion of n randomly generated numbers:
Immutable TreeSet: 14658 ms
My AVL TreeSet: 6129 ms
HashSet (immutable): 13397 ms
Checking containment of n randomly generated numers:
Immutable TreeSet: 6745 ms
My AVL TreeSet: 3948 ms
HashSet (immutable): 1797 ms

So, it's at least not slower :D

@scabug
Copy link
Author

scabug commented Jan 20, 2011

tim8dev said:
Sorry, for double post, but it's just unreadable, w/o line-breaks. [[BR]]
[[BR]]
Well, I'm currently working on a mutable TreeSet/Map? Implementation based on an AVL Tree. While it is on average a bit more costly (but still O(log n)) to insert a value into an AVL Tree compared to a Red-Black Tree, it can check containments faster than Red-Black Trees because they are more balanced.[[BR]]
[[BR]]
Well.. I've only implemented insert and contains yet, but we'll see what I can do over the weekend. Some performance results: n = 1 << 28 Creating Sets through insertion of n randomly generated numbers:[[BR]]
Immutable TreeSet: 14658 ms[[BR]]
My AVL TreeSet: 6129 ms[[BR]]
HashSet (immutable): 13397 ms[[BR]]
Checking containment of n randomly generated numers:[[BR]]
Immutable TreeSet: 6745 ms[[BR]]
My AVL TreeSet: 3948 ms[[BR]]
HashSet (immutable): 1797 ms[[BR]]
[[BR]]
So, it's at least not slower :D[[BR]]

@scabug
Copy link
Author

scabug commented Jan 24, 2011

@lindydonna said:
We agree that it would be good to include these features, but we don't have the resources to create a robust implementation. If someone creates a good implementation with full tests (e.g., tim8dev or someone else), there is a good chance that someone can pick it up and integrate it with the standard library.

@scabug
Copy link
Author

scabug commented Jun 11, 2011

Lucien Pereira (lpereira) said:
I implemented a mutable TreeSet backed by an immutable AVL Tree.
You can find my proposal here : https://github.com/lpereir4/t4147
Assertion based test and scalacheck test can be found in src/test/scala

@scabug
Copy link
Author

scabug commented Jun 19, 2011

Craig P. Motlin (motlin) said:
Is it reasonable to start by porting java.util.TreeMap or would that be a license problem?

@scabug
Copy link
Author

scabug commented Jun 19, 2011

Lucien Pereira (lpereira) said:
I think It would be easier to write it from scratch.

@scabug
Copy link
Author

scabug commented Jan 27, 2012

@soc said:
TreeSet was merged in scala/scala@51ddeb3

Now only mutable.TreeMap is missing.

@scabug
Copy link
Author

scabug commented Feb 21, 2012

@soc said:
Would it be possible to add a row to http://docs.scala-lang.org/overviews/collections/performance-characteristics.html?

@scabug
Copy link
Author

scabug commented Mar 14, 2012

Lucien Pereira (lpereira) said:
Documentation has been updated Simon.

@scabug
Copy link
Author

scabug commented May 10, 2015

@ruippeixotog said:
I may be needing this in one of my projects. If you're still into adding a mutable.TreeMap to the standard Scala collections, I can do a PR to 2.12.x once (and if) I'm able to implement it :) Personally, I think a mutable sorted map is more than common enough to warrant appearing in the standard lib of a programming language.

@scabug
Copy link
Author

scabug commented May 30, 2015

@Ichoran said:
Note that this would also (arguably) resolve #6938

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants