Commit message (Collapse) | Author | Age | Files | Lines | ||
---|---|---|---|---|---|---|
* | Test for maximum height of red-black tree. | Erik Rozendaal | 2012-01-08 | 1 | -0/+5 | |
| | ||||||
* | Fix silly copy-paste error. | Erik Rozendaal | 2012-01-07 | 1 | -9/+9 | |
| | ||||||
* | Tests for takeWhile/dropWhile/span. | Erik Rozendaal | 2012-01-07 | 4 | -8/+32 | |
| | | | | Also simplified implementation of span to just use splitAt. | |||||
* | Renamed object RedBlack to RedBlackTree. | Erik Rozendaal | 2012-01-07 | 6 | -469/+690 | |
| | | | | | | This more clearly separates the new implementation from the now deprecated abstract class RedBlack and avoids naming conflicts for the member classes. | |||||
* | Restore old RedBlack class to maintain backwards compatibility. | Erik Rozendaal | 2012-01-06 | 4 | -171/+452 | |
| | | | | | | | | | The class is marked as deprecated and no longer used by the TreeMap/TreeSet implementation but is restored in case it was used by anyone else (since it was not marked as private to the Scala collection library). Renamed RedBlack.{Tree,RedTree,BlackTree} to Node, RedNode, and BlackNode to work around name clash with RedBlack class. | |||||
* | Deprecate TreeMap.isSmaller and TreeSet.isSmaller. | Erik Rozendaal | 2012-01-06 | 2 | -0/+2 | |
| | | | | | | These methods were used by the old RedBlack tree implementation, but are no longer required and were not defined in any interface. Use ordering or compare instead. | |||||
* | Add implementation notes. Consistently use eq/ne to compare with null. | Erik Rozendaal | 2012-01-05 | 1 | -7/+24 | |
| | ||||||
* | Move nth method to RedBlack. Inline factories for tree nodes. | Erik Rozendaal | 2012-01-05 | 3 | -18/+20 | |
| | ||||||
* | Optimize foreach and iterators. | Erik Rozendaal | 2012-01-04 | 5 | -44/+103 | |
| | ||||||
* | Use null to represent empty trees. Removed Empty/NonEmpty classes. | Erik Rozendaal | 2012-01-03 | 4 | -404/+367 | |
| | ||||||
* | Implemented range without using pattern matching. | Erik Rozendaal | 2012-01-02 | 1 | -9/+14 | |
| | ||||||
* | Implemented deletes without pattern matching. | Erik Rozendaal | 2012-01-02 | 1 | -61/+72 | |
| | ||||||
* | Moved key/value/left/right fields up to NonEmpty class. Don't rely | Erik Rozendaal | 2012-01-02 | 3 | -33/+57 | |
| | | | | on pattern matching for updating the tree. | |||||
* | Minimize number of calls to ordering. | Erik Rozendaal | 2011-12-28 | 1 | -13/+14 | |
| | ||||||
* | Added some tests for TreeMap/TreeSet. | Erik Rozendaal | 2011-12-28 | 2 | -0/+182 | |
| | ||||||
* | Improved performance of RedBlack.NonEmpty.nth (helps take/drop/split/etc). | Erik Rozendaal | 2011-12-28 | 1 | -2/+3 | |
| | ||||||
* | Performance improvements for iteration (foreach and iterator). | Erik Rozendaal | 2011-12-28 | 3 | -18/+51 | |
| | ||||||
* | TreeMap/TreeSet no longer keep track of the size (the RedBlack tree | Erik Rozendaal | 2011-12-28 | 2 | -40/+31 | |
| | | | | already does so). | |||||
* | Made RedBlack private to the scala.collection.immutable package. | Erik Rozendaal | 2011-12-28 | 2 | -10/+12 | |
| | | | | | Use ArrayStack instead of Stack in TreeIterator for slightly increased performance. | |||||
* | Make sure the redblack test compiles and runs. | Erik Rozendaal | 2011-12-28 | 2 | -42/+37 | |
| | ||||||
* | Use single shared Empty instance across all RedBlack trees. | Erik Rozendaal | 2011-12-28 | 3 | -23/+32 | |
| | ||||||
* | Changed abstract class RedBlack to singleton object. | Erik Rozendaal | 2011-12-28 | 3 | -10/+13 | |
| | ||||||
* | Moved type parameter A from RedBlack to Tree. | Erik Rozendaal | 2011-12-28 | 3 | -71/+71 | |
| | ||||||
* | Moved from Empty case object to case class in preparation of moving | Erik Rozendaal | 2011-12-28 | 3 | -15/+15 | |
| | | | | type parameter A. | |||||
* | Moved from implicit ordering value to implicit parameter. | Erik Rozendaal | 2011-12-28 | 1 | -17/+15 | |
| | ||||||
* | Switched from isSmaller to ordering. | Erik Rozendaal | 2011-12-28 | 1 | -9/+9 | |
| | ||||||
* | Implemented takeWhile/dropWhile/span to use tree splitting. This | Erik Rozendaal | 2011-12-28 | 2 | -0/+26 | |
| | | | | | changes the operation from O(n log n) to O(n) and allows for more structural sharing. | |||||
* | Implemented drop/take/slice/splitAt/dropRight/takeRight for | Erik Rozendaal | 2011-12-28 | 3 | -0/+53 | |
| | | | | | | TreeMap/TreeSet by splitting the underlying RedBlack tree. This makes the operation O(log n) instead of O(n) and allows more structural sharing. | |||||
* | RedBlack.scala: Change count from 'def' to 'val' in NonEmpty tree | Erik Rozendaal | 2011-12-28 | 1 | -1/+1 | |
| | | | | | to ensure TreeSet/TreeMap 'range' operations are O(log n) instead of O(n). | |||||
* | Optimized implementation of init/tail for TreeSet/TreeMap. | Erik Rozendaal | 2011-12-28 | 2 | -0/+6 | |
| | ||||||
* | Optimized implementations of head/headOption/last/lastOption for | Erik Rozendaal | 2011-12-28 | 3 | -0/+19 | |
| | | | | TreeMap/TreeSet. | |||||
* | Use custom implementation for iterating over RedBlack trees. Raw | Erik Rozendaal | 2011-12-28 | 1 | -5/+31 | |
| | | | | performance is much better than '++' based iterator. | |||||
* | Use RedBlack.iterator to create iterators for TreeSet/TreeMap. | Erik Rozendaal | 2011-12-28 | 2 | -2/+2 | |
| | | | | | | | This turns iterator creation from an O(n) operation into an O(log n) operation. Unfortunately, it halves actual iteration speed (consuming the iterator fully), probably due to the many by-name closures that are needed. | |||||
* | Merge branch 'type-currying-mini' of /scala/trunk into develop | Paul Phillips | 2011-12-27 | 3 | -3/+76 | |
|\ | ||||||
| * | Consecutive type application. | Paul Phillips | 2011-12-27 | 3 | -3/+76 | |
| | | | | | | | | | | | | | | | | | | | | | | | | | | The parser through I think a quirk of history would not allow back to back type applications, like expr[T1, T2][T3, T4] Now it does, meaning the only thing it can: val n0 = Partial[immutable.HashMap][String][Int] ++ Seq(("a", 1)) val n1 = Partial.apply[immutable.HashMap].apply[String].apply[Int] ++ Seq(("a", 1)) assert(n0 == n1) | |||||
| | | ||||||
| \ | ||||||
| \ | ||||||
| \ | ||||||
| \ | ||||||
| \ | ||||||
| \ | ||||||
| \ | ||||||
*-------. \ | Merge remote-tracking branches 'ijuma/issue/5341', ↵ | Paul Phillips | 2011-12-27 | 26 | -1/+458 | |
|\ \ \ \ \ \ | | | | | | | | | | | | | | | | | | | | | | 'kepler/topic/reifyclosuretests', 'kepler/topic/antscalacheck', 'szabolcsberecz/SI-5104', 'kepler/ticket/5334' and 'kepler/topic/miscfixes' into develop | |||||
| | | | | * | | Documented emptyValDef field | Eugene Burmako | 2011-12-23 | 1 | -0/+5 | |
| | | | | | | | ||||||
| | | | * | | | Tests for recently submitted SI-5334 | Eugene Burmako | 2011-12-23 | 2 | -0/+30 | |
| | | | |/ / | ||||||
| | | * / / | fixes #5104 and related NaN ordering inconsistencies | Szabolcs Berecz | 2011-12-25 | 2 | -0/+170 | |
| | | |/ / | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The bug was caused by the inconsistency between j.l.Math.min() and j.l.Double.compareTo() wrt NaN (j.l.Math.min() considers NaN to be less than any other value while j.l.Double.compareTo() says it's greater...) The fix changes Ordering.{FloatOrdering,DoubleOrdering) to base it's results on primitive comparisons and math.{min,max} instead of j.l.{Float,Double}.compareTo() | |||||
| | * | | | scalacheck now also has pre-scalacheck and its personal timer | Eugene Burmako | 2011-12-26 | 1 | -1/+10 | |
| | | | | | ||||||
| * | | | | A handful of tests for closures under reification | Eugene Burmako | 2011-12-26 | 20 | -0/+243 | |
| | |_|/ | |/| | | ||||||
* / | | | Fix SI-5341: PhaseAssembly.removeDanglingNodes removes elements from mutable.Map | Ismael Juma | 2011-12-27 | 1 | -1/+1 | |
|/ / / | | | | | | | | | | during iteration. | |||||
* | | | Fixed regression in lub calculation. | Paul Phillips | 2011-12-26 | 2 | -9/+29 | |
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Changing NullaryMethodType to be a SimpleTypeProxy because nearly all its operations forward to its result type was it seems not such a good idea, because it also meant that calling .underlying returned the result type rather than the method type. The way this materialized was in subtype checks of refinement types. A lub is calculated for two nullary method types in the course of calculating a refinement, and then the input types are checked against the calculated lub. However in the lub refinement, the nullary method type has become a bare typeref, and so the subtype check failed. Closes SI-5317. This does give me confidence that all the malformed lubs one sees logged under -Ydebug (and there are still many, especially with type constructors) are alerting us to real bugs elsewhere in Types. | |||||
* | | | Merge pull request #77 from scalamacros/topic/antlocale | Paul Phillips | 2011-12-25 | 1 | -1/+1 | |
|\ \ \ | |/ / |/| | | Addresses a bug in SimpleDateFormatter | |||||
| * | | Addresses a bug in SimpleDateFormatter | Eugene Burmako | 2011-12-25 | 1 | -1/+1 | |
| |/ | ||||||
* | | Optimizing at the Name/String boundary. | Paul Phillips | 2011-12-25 | 11 | -87/+114 | |
| | | | | | | | | | | | | Working on reducing the now significant amount of both garbage and retained but duplicated Strings taking place as Names become Strings and vice versa. Long way to go. | |||||
* | | Optimization in ZipArchive. | Paul Phillips | 2011-12-25 | 1 | -4/+8 | |
| | | | | | | | | Avoid creating empty array when len == 0. | |||||
* | | Merge remote-tracking branch 'origin/develop' into develop | Paul Phillips | 2011-12-24 | 0 | -0/+0 | |
|\ \ | ||||||
| * \ | Merge pull request #1 from odersky/topic/reify | odersky | 2011-12-22 | 6 | -89/+78 | |
| |\ \ | | | | | | | | | | | | | Improvements to reification and resetAttrs | |||||
| | * | | Hardening of resetAllAttrs to work in the case where TypeTrees refer to ↵ | Martin Odersky | 2011-12-22 | 2 | -41/+44 | |
| | | | | | | | | | | | | | | | | locally erased symbols. |