| Commit message (Collapse) | Author | Age | Files | Lines |
|---|
| |
|
|
|
|
|
|
| |
The previous implementation of `mutable.TreeSet` uses a mutable reference to an immutable red-black tree as its underlying data structure. That leads to unnecessary objects being created, which can be a problem in systems with limited resources. It also has reduced performance when compared with common mutable implementations.
In this commit `mutable.TreeSet` is changed so that it uses the recently created `mutable.RedBlackTree` as its underlying data structure. Specialized red-black tree methods were created for working with keys for efficiency reasons. The new implementation is source-compatible with the previous one, although its serialized representation obviously changes.
Closes [SI-6938](https://issues.scala-lang.org/browse/SI-6938).
|
| |
|
|
|
|
| |
The previous implementation has a major bug - although `clear()` sets the root node to `null`, the `size` attribute of the `Tree` was not updated. This effectively meant that even after a `map.clear()`, a call to `map.size` would still yield the old size of the map.
The scalacheck test suite was updated to contemplate this issue.
|
|
|
This commit contains an implementation of a mutable red-black tree with focus on performance. It also contains a new `mutable.TreeMap` Scala collection that is backed by the aforementioned tree. The common generic factories and traits related to mutable sorted maps didn't exist yet, so this commit also adds them.
Regarding performance, `TreeMap` overrides (from `MapLike` and `SortedMapLike`) all of the most common methods for maps and also those whose default implementations are asymptotically worse than direct red-black tree algorithms (e.g. `last`, `clear`).
The `rangeImpl` method of `TreeMap` returns an instance of `TreeMapView`, an inner class of `TreeMap`. This view is backed by the same `RedBlackTree.Tree` instance, and therefore changes to the original map are reflected in the view and vice-versa. The semantics of mutating a view by adding and removing keys outside the view's range are the same of the current `mutable.TreeSet`. A bit less focus was given on the performance of views - in particular, getting the `size` of a `TreeMapView` is O(n) on the number of elements inside the view bounds. That can be improved in the future.
In a future commit, `mutable.TreeSet` can be changed to be backed by this red-black tree implementation.
|
