import scala.
collection.
generic.
CanBuildFrom import collection.
{TraversableLike, SeqLike
} import collection.
immutable.
BitSet
class QuickSort
[Coll
](a
: Coll
) { //should be able to sort only something with defined order (someting like a Seq)
def quickSort
[T
](implicit ev0
: Coll
=> SeqLike
[T, Coll
],
cbf: CanBuildFrom[Coll, T, Coll],
n: Ordering[T]): Coll = {
quickSortAnything(ev0, cbf, n)
}
//we can even sort a Set, if we really want to
def quickSortAnything
[T
](implicit ev0
: Coll
=> TraversableLike
[T, Coll
],
cbf: CanBuildFrom[Coll, T, Coll],
n: Ordering[T]): Coll = {
a
// We pick the first value for the pivot.
val (lower, tmp
) = a.
partition(_ < pivot
) val (upper, same
) = tmp.
partition(_ > pivot
) b.sizeHint(a.size)
b ++
= new QuickSort
(lower
).
quickSortAnything b ++= same
b ++
= new QuickSort
(upper
).
quickSortAnything b.result
}
}
}
class FilterMap
[Repr
](a
: Repr
) { def filterMap
[A, B, That
](f
: A
=> Option
[B
])(implicit ev0
: Repr
=> TraversableLike
[A, Repr
],
cbf: CanBuildFrom[Repr, B, That]): That = {
a.flatMap(e => f(e).toSeq)
}
}
class FilterMapFixed
[A, Repr
<% TraversableLike
[A, Repr
]](a
: Repr
) { def filterMap2
[B, That
](f
: A
=> Option
[B
])(implicit cbf
: CanBuildFrom
[Repr, B, That
]): That
= { a.flatMap(e => f(e).toSeq)
}
}
implicit def toFM2
[A, Repr
<% TraversableLike
[A, Repr
]](a
: Repr
) = new FilterMapFixed
(a
) }
println("qwe".quickSort)
println(Array(2, 0).quickSort)
println(Seq(2, 0).quickSort)
//not very useful to sort a set, but just as a demonstration
println(BitSet(2, 0).quickSortAnything)
//need to hint type inferencer,
//probably will be able to overcome after https://i...content-available-to-author-only...g.org/browse/SI-4699 and
// related issues are fixed (by moving ev0 parameter from filterMap to toFM), see toFM2
println("qwe".filterMap((c: Char) => Some(c.toInt)))
println("qwe".filterMap((c: Char) => Some(c)))
println(Array(2, 0).filterMap((c: Int) => Some(c.toInt)))
println
(Seq
(2,
0).
filterMap((c
: Int
) => if (c
< 2) Some
(c +
"!") else None
)) def test
(i
:Int
) = Option
(i
) println(BitSet(2,0).filterMap(test))
println(toFM2("qwe").filterMap2(c => Some(c)))
println(toFM2(Array(2, 0)).filterMap2(c => Some(c.toInt)))
//No implicit view available from java.lang.String => scala.collection.TraversableLike[A,java.lang.String]. :(
//println("qwe".filterMap2(c => Some(c)))
}
aW1wb3J0IHNjYWxhLmNvbGxlY3Rpb24uZ2VuZXJpYy5DYW5CdWlsZEZyb20KaW1wb3J0IHNjYWxhLm1hdGguT3JkZXJpbmcKaW1wb3J0IGNvbGxlY3Rpb24ue1RyYXZlcnNhYmxlTGlrZSwgU2VxTGlrZX0KaW1wb3J0IGNvbGxlY3Rpb24uaW1tdXRhYmxlLkJpdFNldAoKY2xhc3MgUXVpY2tTb3J0W0NvbGxdKGE6IENvbGwpIHsKICAvL3Nob3VsZCBiZSBhYmxlIHRvIHNvcnQgb25seSBzb21ldGhpbmcgd2l0aCBkZWZpbmVkIG9yZGVyIChzb21ldGluZyBsaWtlIGEgU2VxKQogIGRlZiBxdWlja1NvcnRbVF0oaW1wbGljaXQgZXYwOiBDb2xsID0+IFNlcUxpa2VbVCwgQ29sbF0sCiAgICAgICAgICAgICAgICAgICBjYmY6IENhbkJ1aWxkRnJvbVtDb2xsLCBULCBDb2xsXSwKICAgICAgICAgICAgICAgICAgIG46IE9yZGVyaW5nW1RdKTogQ29sbCA9IHsKICAgIHF1aWNrU29ydEFueXRoaW5nKGV2MCwgY2JmLCBuKQogIH0KCiAgLy93ZSBjYW4gZXZlbiBzb3J0IGEgU2V0LCBpZiB3ZSByZWFsbHkgd2FudCB0bwogIGRlZiBxdWlja1NvcnRBbnl0aGluZ1tUXShpbXBsaWNpdCBldjA6IENvbGwgPT4gVHJhdmVyc2FibGVMaWtlW1QsIENvbGxdLAogICAgICAgICAgICAgICAgICAgICAgICAgICBjYmY6IENhbkJ1aWxkRnJvbVtDb2xsLCBULCBDb2xsXSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgbjogT3JkZXJpbmdbVF0pOiBDb2xsID0gewogICAgaW1wb3J0IG4uXwogICAgaWYgKGEuc2l6ZSA8IDIpIHsKICAgICAgYQogICAgfSBlbHNlIHsKICAgICAgLy8gV2UgcGljayB0aGUgZmlyc3QgdmFsdWUgZm9yIHRoZSBwaXZvdC4KICAgICAgdmFsIHBpdm90ID0gYS5oZWFkCiAgICAgIHZhbCAobG93ZXIsIHRtcCkgPSBhLnBhcnRpdGlvbihfIDwgcGl2b3QpCiAgICAgIHZhbCAodXBwZXIsIHNhbWUpID0gdG1wLnBhcnRpdGlvbihfID4gcGl2b3QpCiAgICAgIHZhbCBiID0gY2JmKCkKICAgICAgYi5zaXplSGludChhLnNpemUpCiAgICAgIGIgKys9IG5ldyBRdWlja1NvcnQobG93ZXIpLnF1aWNrU29ydEFueXRoaW5nCiAgICAgIGIgKys9IHNhbWUKICAgICAgYiArKz0gbmV3IFF1aWNrU29ydCh1cHBlcikucXVpY2tTb3J0QW55dGhpbmcKICAgICAgYi5yZXN1bHQKICAgIH0KICB9Cn0KCmNsYXNzIEZpbHRlck1hcFtSZXByXShhOiBSZXByKSB7CiAgZGVmIGZpbHRlck1hcFtBLCBCLCBUaGF0XShmOiBBID0+IE9wdGlvbltCXSkoaW1wbGljaXQgZXYwOiBSZXByID0+IFRyYXZlcnNhYmxlTGlrZVtBLCBSZXByXSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBjYmY6IENhbkJ1aWxkRnJvbVtSZXByLCBCLCBUaGF0XSk6IFRoYXQgPSB7CiAgICBhLmZsYXRNYXAoZSA9PiBmKGUpLnRvU2VxKQogIH0KfQoKY2xhc3MgRmlsdGVyTWFwRml4ZWRbQSwgUmVwciA8JSBUcmF2ZXJzYWJsZUxpa2VbQSwgUmVwcl1dKGE6IFJlcHIpIHsKICBkZWYgZmlsdGVyTWFwMltCLCBUaGF0XShmOiBBID0+IE9wdGlvbltCXSkoaW1wbGljaXQgY2JmOiBDYW5CdWlsZEZyb21bUmVwciwgQiwgVGhhdF0pOiBUaGF0ID0gewogICAgYS5mbGF0TWFwKGUgPT4gZihlKS50b1NlcSkKICB9Cn0KCm9iamVjdCBNeUVuaGFuY2VtZW50cyB7CiAgaW1wbGljaXQgZGVmIHRvUVNbQ29sbF0oYTogQ29sbCkgPSBuZXcgUXVpY2tTb3J0KGEpCiAgaW1wbGljaXQgZGVmIHRvRk1bQ29sbF0oYTogQ29sbCkgPSBuZXcgRmlsdGVyTWFwKGEpCiAgaW1wbGljaXQgZGVmIHRvRk0yW0EsIFJlcHIgPCUgVHJhdmVyc2FibGVMaWtlW0EsIFJlcHJdXShhOiBSZXByKSA9IG5ldyBGaWx0ZXJNYXBGaXhlZChhKQp9CgpvYmplY3QgTWFpbiBleHRlbmRzIEFwcGxpY2F0aW9uIHsKCiAgaW1wb3J0IE15RW5oYW5jZW1lbnRzLl8KCiAgcHJpbnRsbigicXdlIi5xdWlja1NvcnQpCiAgcHJpbnRsbihBcnJheSgyLCAwKS5xdWlja1NvcnQpCiAgcHJpbnRsbihTZXEoMiwgMCkucXVpY2tTb3J0KQogIC8vbm90IHZlcnkgdXNlZnVsIHRvIHNvcnQgYSBzZXQsIGJ1dCBqdXN0IGFzIGEgZGVtb25zdHJhdGlvbgogIHByaW50bG4oQml0U2V0KDIsIDApLnF1aWNrU29ydEFueXRoaW5nKQoKICAvL25lZWQgdG8gaGludCB0eXBlIGluZmVyZW5jZXIsCiAgLy9wcm9iYWJseSB3aWxsIGJlIGFibGUgdG8gb3ZlcmNvbWUgYWZ0ZXIgaHR0cHM6Ly9pLi4uY29udGVudC1hdmFpbGFibGUtdG8tYXV0aG9yLW9ubHkuLi5nLm9yZy9icm93c2UvU0ktNDY5OSAgYW5kCiAgLy8gcmVsYXRlZCBpc3N1ZXMgYXJlICBmaXhlZCAoYnkgbW92aW5nIGV2MCBwYXJhbWV0ZXIgZnJvbSBmaWx0ZXJNYXAgdG8gdG9GTSksIHNlZSB0b0ZNMgogIHByaW50bG4oInF3ZSIuZmlsdGVyTWFwKChjOiBDaGFyKSA9PiBTb21lKGMudG9JbnQpKSkKICBwcmludGxuKCJxd2UiLmZpbHRlck1hcCgoYzogQ2hhcikgPT4gU29tZShjKSkpCiAgcHJpbnRsbihBcnJheSgyLCAwKS5maWx0ZXJNYXAoKGM6IEludCkgPT4gU29tZShjLnRvSW50KSkpCiAgcHJpbnRsbihTZXEoMiwgMCkuZmlsdGVyTWFwKChjOiBJbnQpID0+IGlmIChjIDwgMikgU29tZShjICsgIiEiKSBlbHNlIE5vbmUpKQogIGRlZiB0ZXN0KGk6SW50KSA9IE9wdGlvbihpKQogIHByaW50bG4oQml0U2V0KDIsMCkuZmlsdGVyTWFwKHRlc3QpKQoKICBwcmludGxuKHRvRk0yKCJxd2UiKS5maWx0ZXJNYXAyKGMgPT4gU29tZShjKSkpCiAgcHJpbnRsbih0b0ZNMihBcnJheSgyLCAwKSkuZmlsdGVyTWFwMihjID0+IFNvbWUoYy50b0ludCkpKQogIC8vTm8gaW1wbGljaXQgdmlldyBhdmFpbGFibGUgZnJvbSBqYXZhLmxhbmcuU3RyaW5nID0+IHNjYWxhLmNvbGxlY3Rpb24uVHJhdmVyc2FibGVMaWtlW0EsamF2YS5sYW5nLlN0cmluZ10uIDooCiAgLy9wcmludGxuKCJxd2UiLmZpbHRlck1hcDIoYyA9PiBTb21lKGMpKSkKfQo=