|
Scala example source code file (Map.scala)
The Map.scala Scala example source codepackage scalaz /** * @see [[http://hackage.haskell.org/package/containers-0.5.7.1/docs/mini_Data-Map-Strict.html]] * @see [[https://github.com/haskell/containers/blob/v0.5.7.1/Data/Map/Base.hs]] */ import Ordering.{ EQ, LT, GT } import std.anyVal._ import std.option._ import annotation.tailrec /** An immutable map of key/value pairs implemented as a balanced binary tree * * Based on Haskell's Data.Map * * @since 7.0.3 */ sealed abstract class ==>>[A, B] { import ==>>._ /** number of key/value pairs - O(1) */ val size: Int /** returns `true` if this map contains no key/value pairs - O(1) */ def isEmpty: Boolean = this == empty /** tupled form of [[insert]] */ def + (a: (A, B))(implicit o: Order[A]): A ==>> B = insert(a._1, a._2) /** inserts a new key/value - O(log n). * * If the key is already present, its value is replaced by the provided value. */ def insert(kx: A, x: B)(implicit n: Order[A]): A ==>> B = this match { case Tip() => singleton(kx, x) case Bin(ky, y, l, r) => n.order(kx, ky) match { case LT => balanceL(ky, y, l.insert(kx, x), r) case GT => balanceR(ky, y, l, r.insert(kx, x)) case EQ => Bin(kx, x, l, r) } } /** inserts a new key/value pair, resolving the conflict if the key already exists - O(log n) * * @param f function to resolve conflict with existing key: * (insertedValue, existingValue) => resolvedValue * @param kx key * @param x value to insert if the key is not already present */ def insertWith(f: (B, B) => B, kx: A, x: B)(implicit o: Order[A]): A ==>> B = insertWithKey((_, a, b) => f(a,b), kx, x) /** inserts a new key/value pair, resolving the conflict if the key already exists - O(log n) * * @param f function to resolve conflict with existing key: * (key, insertedValue, existingValue) => resolvedValue * @param kx key * @param x value to insert if the key is not already present */ def insertWithKey(f: (A, B, B) => B, kx: A, x: B)(implicit o: Order[A]): A ==>> B = this match { case Tip() => singleton(kx, x) case Bin(ky, y, l, r) => o.order(kx, ky) match { case LT => balanceL(ky, y, l.insertWithKey(f, kx, x), r) case GT => balanceR(ky, y, l, r.insertWithKey(f, kx, x)) case EQ => Bin(kx, f(kx, x, y), l, r) } } /** alias for [[delete]] */ def -(k: A)(implicit o: Order[A]): A ==>> B = delete(k) /** removes a key/value pair - O(log n) */ def delete(k: A)(implicit n: Order[A]): A ==>> B = this match { case Tip() => empty case Bin(kx, x, l, r) => n.order(k, kx) match { case LT => balanceR(kx, x, l.delete(k), r) case EQ => glue(l, r) case GT => balanceL(kx, x, l, r.delete(k)) } } /** if the key exists, transforms its value - O(log n) */ def adjust(k: A, f: B => B)(implicit o: Order[A]): A ==>> B = adjustWithKey(k, (_, x) => f(x)) /** like [[adjust]] but with the key available in the transformation - O(log n) */ def adjustWithKey(k: A, f: (A, B) => B)(implicit o: Order[A]): A ==>> B = updateWithKey(k, (a, b) => some(f(a, b))) /** updates or removes a value - O(log n) * * if `f` returns `None`, then the key is removed from the map */ def update(k: A, f: B => Option[B])(implicit o: Order[A]): A ==>> B = updateWithKey(k, (_, x) => f(x)) /** like [[update]] but with the key available in the update function - O(log n) */ def updateWithKey(k: A, f: (A, B) => Option[B])(implicit o: Order[A]): A ==>> B = this match { case Tip() => empty case Bin(kx, x, l, r) => o.order(k, kx) match { case LT => balanceR(kx, x, l.updateWithKey(k, f), r) case GT => balanceL(kx, x, l, r.updateWithKey(k, f)) case EQ => f(kx, x) match { case Some(v) => Bin(kx, v, l, r) case None => glue(l, r) } } } /** looks up a key and updates its value - O(log n) * * Similar to [[updateWithKey]] but also returns the value. If the value was updated, returns the * new value. If the value was deleted, returns the old value. */ def updateLookupWithKey(k: A, f: (A, B) => Option[B])(implicit o: Order[A]): (Option[B], A ==>> B) = this match { case Tip() => (none, empty) case Bin(kx, x, l, r) => o.order(k, kx) match { case LT => val (found, ll) = l.updateLookupWithKey(k, f) (found, balanceR(kx, x, ll, r)) case GT => val (found, rr) = r.updateLookupWithKey(k, f) (found, balanceL(kx, x, l, rr)) case EQ => f(kx, x) match { case Some(xx) => (some(xx), Bin(kx, xx, l, r)) case None => (some(x), glue(l, r)) } } } def alter(k: A, f: Option[B] => Option[B])(implicit o: Order[A]): A ==>> B = this match { case Tip() => f(None) match { case None => empty case Some(x) => singleton(k, x) } case Bin(kx, x, l,r) => o.order(k, kx) match { case LT => balance(kx, x, l.alter(k, f), r) case GT => balance(kx, x, l, r.alter(k, f)) case EQ => f(some(x)) match { case None => glue(l, r) case Some(xx) => Bin(kx, xx, l, r) } } } @tailrec final def lookup(k: A)(implicit n: Order[A]): Option[B] = this match { case Tip() => none case Bin(kx, x, l, r) => n.order(k, kx) match { case LT => l.lookup(k) case GT => r.lookup(k) case EQ => some(x) } } @tailrec final def lookupAssoc(k: A)(implicit n: Order[A]): Option[(A, B)] = this match { case Tip() => none case Bin(kx, x, l, r) => n.order(k, kx) match { case LT => l.lookupAssoc(k) case GT => r.lookupAssoc(k) case EQ => some((kx, x)) } } @tailrec final def lookupLT(k: A)(implicit o: Order[A]): Option[(A, B)] = { @tailrec def goSome(kx: A, x: B, t: A ==>> B): Option[(A, B)] = t match { case Tip() => some((kx, x)) case Bin(ky, y, l, r) => if (o.lessThanOrEqual(k, ky)) goSome(kx, x, l) else goSome(ky, y, r) } this match { case Tip() => none case Bin(kx, x, l, r) => if (o.lessThanOrEqual(k, kx)) l.lookupLT(k) else goSome(kx, x, r) } } @tailrec final def lookupGT(k: A)(implicit o: Order[A]): Option[(A, B)] = { @tailrec def goSome(kx: A, x: B, t: A ==>> B): Option[(A, B)] = t match { case Tip() => some((kx, x)) case Bin(ky, y, l, r) => if (o.greaterThanOrEqual(k, ky)) goSome(kx, x, r) else goSome(ky, y, l) } this match { case Tip() => none case Bin(kx, x, l, r) => if (o.greaterThanOrEqual(k, kx)) r.lookupGT(k) else goSome(kx, x, l) } } @tailrec final def lookupLE(k: A)(implicit o: Order[A]): Option[(A, B)] = { @tailrec def goSome(kx: A, x: B, t: A ==>> B): Option[(A, B)] = t match { case Tip() => some((kx, x)) case Bin(ky, y, l, r) => o.order(k, ky) match { case LT => goSome(kx, x, l) case EQ => some((ky, y)) case GT => goSome(ky, y, r) } } this match { case Tip() => none case Bin(kx, x, l, r) => o.order(k, kx) match { case LT => l.lookupLE(k) case EQ => some((kx, x)) case GT => goSome(kx, x, r) } } } @tailrec final def lookupGE(k: A)(implicit o: Order[A]): Option[(A, B)] = { @tailrec def goSome(kx: A, x: B, t: A ==>> B): Option[(A, B)] = t match { case Tip() => some((kx, x)) case Bin(ky, y, l, r) => o.order(k, ky) match { case LT => goSome(ky, y, l) case EQ => some((ky, y)) case GT => goSome(kx, x, r) } } this match { case Tip() => none case Bin(kx, x, l, r) => o.order(k, kx) match { case LT => goSome(kx, x, l) case EQ => some((kx, x)) case GT => r.lookupGE(k) } } } def values: List[B] = foldrWithKey(List.empty[B])((_, x, xs) => x :: xs) def keys: List[A] = foldrWithKey(List.empty[A])((x, _, xs) => x :: xs) def keySet: ISet[A] = this match { case Tip() => ISet.Tip[A] case Bin(k,v,l,r) => ISet.Bin(k,l.keySet,r.keySet) } def toList: List[(A, B)] = toAscList def toAscList: List[(A, B)] = foldrWithKey(List.empty[(A, B)])((k, x, xs) => (k, x) :: xs) def toDescList: List[(A, B)] = foldlWithKey(List.empty[(A, B)])((xs, k, x) => (k, x) :: xs) def member(k: A)(implicit n: Order[A]): Boolean = lookup(k)(n).isDefined def notMember(k: A)(implicit n: Order[A]): Boolean = !member(k) def lookupIndex(k: A)(implicit o: Order[A]): Option[Int] = { @tailrec def go(n: Int, m: A ==>> B): Option[Int] = m match { case Tip() => none case Bin(kx, x, l, r) => o.order(k, kx) match { case LT => go(n, l) case GT => go(n + l.size + 1, r) case EQ => some((n + l.size)) } } go(0, this) } @tailrec final def elemAt(i: Int): Option[(A, B)] = this match { case Tip() => none case Bin(kx, x, l ,r) => implicitly[Order[Int]].order(i, l.size) match { case LT => l.elemAt(i) case GT => r.elemAt(i - l.size - 1) case EQ => some((kx, x)) } } // TODO: This should be a total function def updateAt(i: Int, f: (A, B) => Option[B]): A ==>> B = this match { case Tip() => sys.error("updateAt") case Bin(kx, x, l, r) => implicitly[Order[Int]].order(i, l.size) match { case LT => balanceR(kx, x, l.updateAt(i, f), r) case GT => balanceL(kx, x, l, r.updateAt(i - l.size - 1, f)) case EQ => f(kx, x) match { case Some(y) => Bin(kx, y, l, r) case None => glue(l, r) } } } def deleteAt(i: Int): A ==>> B = updateAt(i, (A, B) => None) @tailrec final def findMin: Option[(A, B)] = this match { case Bin(kx, x, Tip(), _) => some((kx, x)) case Bin(_, _, l, _) => l.findMin case Tip() => none } @tailrec final def findMax: Option[(A, B)] = this match { case Bin(kx, x, _, Tip()) => some((kx, x)) case Bin(_, _, _, r) => r.findMax case Tip() => none } def deleteMin: A ==>> B = this match { case Bin(_, _, Tip(), r) => r case Bin(kx, x, l, r) => balanceR(kx, x, l.deleteMin, r) case Tip() => empty } def deleteMax: A ==>> B = this match { case Bin(_, _, l, Tip()) => l case Bin(kx, x, l, r) => balanceL(kx, x, l, r.deleteMax) case Tip() => empty } def updateMin(f: B => Option[B]): A ==>> B = updateMinWithKey((_: A, b) => f(b)) def updateMinWithKey(f: (A, B) => Option[B]): A ==>> B = this match { case Bin(kx, x, Tip(), r) => f(kx, x) match { case None => r case Some(s) => Bin(kx, s, Tip(), r) } case Bin(kx, x, l, r) => balanceR(kx, x, l.updateMinWithKey(f), r) case Tip() => empty } def updateMax(f: B => Option[B]): A ==>> B = updateMaxWithKey((_: A, b) => f(b)) def updateMaxWithKey(f: (A, B) => Option[B]): A ==>> B = this match { case Bin(kx, x, l, Tip()) => f(kx, x) match { case None => l case Some(s) => Bin(kx, s, l, Tip()) } case Bin(kx, x, l, r) => balanceL(kx, x, l, r.updateMaxWithKey(f)) case Tip() => empty } /** * insert v into the map at k. If there is already a value for k, * append to the existing value using the Semigroup */ def updateAppend(k: A, v: B)(implicit o: Order[A], bsg: Semigroup[B]): A ==>> B = alter(k, old ⇒ Some(old.map(bsg.append(_, v)).getOrElse(v))) def minViewWithKey: Option[((A, B), A ==>> B)] = this match { case Tip() => none case x @ Bin(_, _, _, _) => some(deleteFindMin(x)) } def maxViewWithKey: Option[((A, B), A ==>> B)] = this match { case Tip() => none case x @ Bin(_, _, _, _) => some(deleteFindMax(x)) } def minView: Option[(B, A ==>> B)] = this match { case Tip() => none case x @ Bin(_, _, _, _) => val r = deleteFindMin(x) some((r._1._2, r._2)) } def maxView: Option[(B, A ==>> B)] = this match { case Tip() => none case x @ Bin(_, _, _, _) => val r = deleteFindMax(x) some((r._1._2, r._2)) } def deleteFindMax(t: Bin[A, B]): ((A, B), A ==>> B) = t match { case Bin(k, x, l, Tip()) => ((k,x), l) case Bin(k, x, l, r @ Bin(_, _, _, _)) => val (km, r2) = deleteFindMax(r) (km, balanceL(k, x, l, r2)) } def deleteFindMin(t: Bin[A, B]): ((A, B), A ==>> B) = t match { case Bin(k, x, Tip(), r) => ((k, x), r) case Bin(k, x, l @ Bin(_, _, _, _), r) => val (km, l2) = deleteFindMin(l) (km, balanceR(k, x, l2, r)) } /* Mappings */ def map[C](f: B => C): A ==>> C = mapWithKey((_, x: B) => f(x)) def mapWithKey[C](f: (A, B) => C): A ==>> C = this match { case Tip() => empty case Bin(kx, x, l, r) => Bin(kx, f(kx, x), l.mapWithKey(f), r.mapWithKey(f)) } def traverseWithKey[F[_], C](f: (A, B) => F[C])(implicit G: Applicative[F]): F[A ==>> C] = this match { case Tip() => G.point(Tip()) case Bin(kx, x, Tip(), Tip()) => G.apply(f(kx, x)) { x2 => Bin(kx, x2, Tip(), Tip()) } case Bin(kx, x, l, r) => G.apply3(l.traverseWithKey(f), f(kx, x), r.traverseWithKey(f)) { (l2, x2, r2) => Bin(kx, x2, l2, r2) } } def mapAccum[C](z: C)(f: (C, B) => (C, B)): (C, A ==>> B) = mapAccumWithKey(z)((a2, _, x2) => f(a2, x2)) def mapAccumWithKey[C](z: C)(f: (C, A, B) => (C, B)): (C, A ==>> B) = mapAccumL(z)(f) def mapAccumL[C](a: C)(f: (C, A, B) => (C, B)): (C, A ==>> B) = this match { case Tip() => (a, empty) case Bin(kx, x, l, r) => val (a1, l2) = l.mapAccumL(a)(f) val (a2, x2) = f(a1, kx, x) val (a3, r2) = r.mapAccumL(a2)(f) (a3, Bin(kx, x2, l2, r2)) } //def mapAccumRWithKey def mapKeys[C](f: A => C)(implicit o: Order[C]): C ==>> B = foldlWithKey(empty[C, B])((xs, k, x) => xs.insert(f(k), x)) def mapKeysWith[C](f: A => C, f2: (B, B) => B)(implicit o: Order[C]): C ==>> B = fromListWith[C, B](toList.map(x => (f(x._1), x._2)))(f2) /* Folds */ def fold[C](z: C)(f: (A, B, C) => C): C = foldrWithKey(z)(f) def foldlWithKey[C](z: C)(f: (C, A, B) => C): C = this match { case Tip() => z case Bin(kx, x, l, r) => r.foldlWithKey(f(l.foldlWithKey(z)(f), kx, x))(f) } def foldrWithKey[C](z: C)(f: (A, B, C) => C): C = this match { case Tip() => z case Bin(kx, x, l, r) => l.foldrWithKey(f(kx, x, r.foldrWithKey(z)(f)))(f) } def foldMapWithKey[C](f: (A, B) => C)(implicit F: Monoid[C]): C = this match { case Tip() => F.zero case Bin(k, x, Tip(), Tip()) => f(k, x) case Bin(k, x, l, r) => F.append(l.foldMapWithKey(f), F.append(f(k, x), r.foldMapWithKey(f))) } /* Unions */ def union(other: A ==>> B)(implicit k: Order[A]): A ==>> B = { def hedgeUnion(blo: Option[A], bhi: Option[A], m1: A ==>> B, m2: A ==>> B): A ==>> B = (m1, m2) match { case (t1, Tip()) => t1 case (Tip(), Bin(kx, x, l, r)) => link(kx, x, l filterGt blo, r filterLt bhi) case (t1, Bin(kx, x, Tip(), Tip())) => insertR(kx, x, t1) case (Bin(kx, x, l, r), t2) => val bmi = Some(kx) val nm1 = hedgeUnion(blo, bmi, l, ==>>.trim(blo, bmi, t2)) val nm2 = hedgeUnion(bmi, bhi, r, ==>>.trim(bmi, bhi, t2)) link(kx, x, nm1, nm2) } def insertR(kx: A, x: B, t: A ==>> B)(implicit o: Order[A]): A ==>> B = { def go(kx: A, x: B, m: A ==>> B): A ==>> B = m match { case Tip() => singleton(kx, x) case Bin(ky, y, l, r) => o.order(kx, ky) match { case LT => balanceL(ky, y, go(kx, x, l), r) case GT => balanceR(ky, y, l, go(kx, x, r)) case EQ => m } } go(kx, x, t) } (this, other) match { case (Tip(), t2) => t2 case (t1, Tip()) => t1 case (t1, t2) => hedgeUnion(None, None, t1, t2) } } def unionWith(other: A ==>> B)(f: (B, B) => B)(implicit o: Order[A]): A ==>> B = unionWithKey(other)((_, b, c) => f(b, c)) def unionWithKey(other: A ==>> B)(f: (A, B, B) => B)(implicit o: Order[A]): A ==>> B = mergeWithKey(this, other)((a, b, c) => some(f(a, b, c)))(x => x, x => x) // Difference functions def \\[C](other: A ==>> C)(implicit o: Order[A]): A ==>> B = difference(other) def difference[C](other: A ==>> C)(implicit o: Order[A]): A ==>> B = { def hedgeDiff(blo: Option[A], bhi: Option[A], a: A ==>> B, b: A ==>> C): A ==>> B = (a, b) match { case (Tip(), _) => empty case (Bin(kx, x, l, r), Tip()) => link(kx, x, l filterGt blo, r filterLt bhi) case (t, Bin(kx, _, l, r)) => val bmi = some(kx) val aa = hedgeDiff(blo, bmi, ==>>.trim(blo, bmi, t), l) val bb = hedgeDiff(bmi, bhi, ==>>.trim(bmi, bhi, t), r) aa merge bb } (this, other) match { case (Tip(), _) => empty case (t1, Tip()) => t1 case (t1, t2) => hedgeDiff(None, None, t1, t2) } } def differenceWith[C](other: A ==>> C)(f: (B, C) => Option[B])(implicit o: Order[A]): A ==>> B = differenceWithKey(other)((_, b, c) => f(b, c)) def differenceWithKey[C](other: A ==>> C)(f: (A, B, C) => Option[B])(implicit o: Order[A]): A ==>> B = mergeWithKey(this, other)(f)(x => x, _ => empty) // Intersections def intersection[C](other: A ==>> C)(implicit o: Order[A]): A ==>> B = { def hedgeInt(blo: Option[A], bhi: Option[A], a: A ==>> B, b: A ==>> C): A ==>> B = (a, b) match { case (_, Tip()) => empty case (Tip(), _) => empty case (Bin(kx, x, l, r), t2) => val bmi = some(kx) val l2 = hedgeInt(blo, bmi, l, ==>>.trim(blo, bmi, t2)) val r2 = hedgeInt(bmi, bhi, r, ==>>.trim(bmi, bhi, t2)) if (t2 member kx) link(kx, x, l2, r2) else l2 merge r2 } (this, other) match { case (Tip(), _) => empty case (_, Tip()) => empty case (t1, t2) => hedgeInt(None, None, t1, t2) } } def intersectionWith[C, D](other: A ==>> C)(f: (B, C) => D)(implicit o: Order[A]): A ==>> D = intersectionWithKey(other)((_, x, y) => f(x, y)) def intersectionWithKey[C, D](other: A ==>> C)(f: (A, B, C) => D)(implicit o: Order[A]): A ==>> D = mergeWithKey(this, other)((a, b, c) => some(f(a, b, c)))(_ => empty, _ => empty) // Submap def isSubmapOf(a: A ==>> B)(implicit o: Order[A], e: Equal[B]): Boolean = isSubmapOfBy(a, e.equal) def isSubmapOfBy(a: A ==>> B, f: (B, B) => Boolean)(implicit o: Order[A]): Boolean = size <= a.size && submap(a, f) private[scalaz] def submap(a: A ==>> B, f: (B, B) => Boolean)(implicit o: Order[A]): Boolean = (this, a) match { case (Tip(), _) => true case (_, Tip()) => false case (Bin(kx, x, l, r), t) => val (lt, found, gt) = t splitLookup kx found match { case None => false case Some(y) => f(x, y) && l.submap(lt, f) && r.submap(gt, f) } } // Filter def filter(p: B => Boolean)(implicit o: Order[A]): A ==>> B = filterWithKey((_, x) => p(x)) def filterWithKey(p: (A, B) => Boolean)(implicit o: Order[A]): A ==>> B = this match { case Tip() => empty case Bin(kx, x, l, r) => if (p(kx, x)) link(kx, x, l.filterWithKey(p), r.filterWithKey(p)) else l.filterWithKey(p) merge r.filterWithKey(p) } // Partition def partition(p: B => Boolean)(implicit o: Order[A]): (A ==>> B, A ==>> B) = partitionWithKey((_, x) => p(x)) def partitionWithKey(p: (A, B) => Boolean)(implicit o: Order[A]): (A ==>> B, A ==>> B) = this match { case Tip() => (empty, empty) case Bin(kx, x, l, r) => val (l1, l2) = l partitionWithKey p val (r1, r2) = r partitionWithKey p if (p(kx, x)) (link(kx, x, l1, r1), l2 merge r2) else (l1 merge r1, link(kx, x, l2, r2)) } def mapOption[C](f: B => Option[C])(implicit o: Order[A]): A ==>> C = mapOptionWithKey((_, x) => f(x)) def mapOptionWithKey[C](f: (A, B) => Option[C])(implicit o: Order[A]): A ==>> C = this match { case Tip() => empty case Bin(kx, x, l, r) => f(kx, x) match { case Some(y) => link(kx, y, l.mapOptionWithKey(f), r.mapOptionWithKey(f)) case None => l.mapOptionWithKey(f).merge(r.mapOptionWithKey(f)) } } def mapEither[C, D](f: B => C \/ D)(implicit o: Order[A]): (A ==>> C, A ==>> D) = mapEitherWithKey((_, x) => f(x)) def mapEitherWithKey[C, D](f: (A, B) => C \/ D)(implicit o: Order[A]): (A ==>> C, A ==>> D) = this match { case Tip() => (empty, empty) case Bin(kx, x, l, r) => val (l1, l2) = l.mapEitherWithKey(f) val (r1, r2) = r.mapEitherWithKey(f) f(kx, x) match { case -\/(y) => (link(kx, y, l1, r1), l2 merge r2) case \/-(z) => (l1 merge r1, link(kx, z, l2, r2)) } } // Split def split(k: A)(implicit o: Order[A]): (A ==>> B, A ==>> B) = this match { case Tip() => (empty, empty) case Bin(kx, x, l, r) => o.order(k, kx) match { case LT => val (lt, gt) = l.split(k) (lt, link(kx, x, gt, r)) case GT => val (lt, gt) = r.split(k) (link(kx, x, l, lt), gt) case EQ => (l, r) } } def splitLookup(k: A)(implicit o: Order[A]): (A ==>> B, Option[B], A ==>> B) = this match { case Tip() => (empty, none, empty) case Bin(kx, x, l, r) => o.order(k, kx) match { case LT => val (lt, z, gt) = l splitLookup k (lt, z, link(kx, x, gt, r)) case GT => val (lt, z, gt) = r splitLookup k (link(kx, x, l, lt), z, gt) case EQ => (l, some(x), r) } } def splitLookupWithKey(k: A)(implicit o: Order[A]): (A ==>> B, Option[(A, B)], A ==>> B) = this match { case Tip() => (empty, none, empty) case Bin(kx, x, l, r) => o.order(k, kx) match { case LT => val (lt, z, gt) = l splitLookupWithKey k (lt, z, link(kx, x, gt, r)) case GT => val (lt, z, gt) = r splitLookupWithKey k (link(kx, x, l, lt), z, gt) case EQ => (l, some((kx, x)), r) } } def splitRoot: List[A ==>> B] = this match { case Tip() => List.empty[A ==>> B] case Bin(k, x, l, r) => List(l, singleton(k, x), r) } // Utility functions // Because the following functions depend on some public interface, such as deleteFindMax, // they can't be moved to object ==>> unlike other utility functions, balance(...) for example. // TODO: merge should be private as it's a utility function but not a public interface. protected def merge(other: A ==>> B): A ==>> B = (this, other) match { case (Tip(), r) => r case (l, Tip()) => l case (l @ Bin(kx, x, lx, rx), r @ Bin(ky, y, ly, ry)) => if (delta * l.size < r.size) balanceL(ky, y, l.merge(ly), ry) else if (delta * r.size < l.size) balanceR(kx, x, lx, rx.merge(r)) else glue(l, r) } private def glue(l: A ==>> B, r: A ==>> B): A ==>> B = (l, r) match { case (Tip(), r) => r case (l, Tip()) => l case (l @ Bin(_, _, _, _), r @ Bin(_, _, _, _)) => if (l.size > r.size) { val ((km, m), l2) = deleteFindMax(l) balanceR(km, m, l2, r) } else { val ((km, m), r2) = deleteFindMin(r) balanceL(km, m, l, r2) } } @deprecated("trim is no longer a public function", "7.3") @tailrec final def trim(lo: A => Ordering, hi: A => Ordering): A ==>> B = this match { case Tip() => empty case t @ Bin(kx, _, l, r) => lo(kx) match { case LT => hi(kx) match { case GT => t case _ => l.trim(lo, hi) } case _ => r.trim(lo, hi) } } @deprecated("trimLookupLo is no longer a public function", "7.3") @tailrec final def trimLookupLo(lo: A, cmphi: A => Ordering)(implicit o: Order[A]): (Option[(A, B)], A ==>> B) = this match { case Tip() => (none, empty) case t @ Bin(kx, x, l, r) => o.order(lo, kx) match { case LT => cmphi(kx) match { case GT => (t lookupAssoc lo, t) case _ => l.trimLookupLo(lo, cmphi) } case GT => r.trimLookupLo(lo, cmphi) case EQ => (some((kx, x)), r.trim(a => o.order(lo, a), cmphi)) } } override final def equals(other: Any): Boolean = other match { case that: ==>>[A, B] => ==>>.mapEqual[A, B](Equal.equalA, Equal.equalA).equal(this, that) case _ => false } override final def hashCode: Int = toAscList.hashCode // filters on keys private def filterGt(a: Option[A])(implicit o: Order[A]): A ==>> B = { def filter(filteringKey: A, m: A ==>> B): A ==>> B = m match { case Tip() => empty case Bin(kx, x, l, r) => o.order(filteringKey, kx) match { case LT => link(kx, x, filter(filteringKey, l), r) case EQ => r case GT => filter(filteringKey, r) } } cata(a)(filter(_, this), this) } private def filterLt(a: Option[A])(implicit o: Order[A]): A ==>> B = { def filter(filteringKey: A, m: A ==>> B): A ==>> B = m match { case Tip() => empty case Bin(kx, x, l, r) => o.order(kx, filteringKey) match { case LT => link(kx, x, l, filter(filteringKey, r)) case EQ => l case GT => filter(filteringKey, l) } } cata(a)(filter(_, this), this) } @deprecated("join is no longer a protected function", "7.3") protected def join(kx: A, x: B, other: A ==>> B)(implicit o: Order[A]): A ==>> B = (this, other) match { case (Tip(), r) => insertMin(kx, x, r) case (l, Tip()) => insertMax(kx, x, l) case (l @ Bin(ky, y, ly, ry), r @ Bin(kz, z, lz, rz)) => if (delta * l.size < r.size) balanceL(kz, z, link(kx, x, l, lz), rz) else if (delta * r.size < l.size) balanceR(ky, y, ly, link(kx, x, ry, r)) else Bin(kx, x, l, r) } } sealed abstract class MapInstances0 { implicit def scalazMapInstance[S: Order]: Bind[S ==>> ?] with Align[S ==>> ?] with Zip[S ==>> ?] = new Bind[S ==>> ?] with Align[S ==>> ?] with Zip[S ==>> ?] { override def map[A, B](fa: S ==>> A)(f: A => B) = fa map f def bind[A, B](fa: S ==>> A)(f: A => (S ==>> B)) = fa.mapOptionWithKey((k, v) => f(v).lookup(k)) import \&/._, ==>>.Tip override def align[A, B](a: S ==>> A, b: S ==>> B) = (a, b) match { case (Tip(), Tip()) => Tip() case (a , Tip()) => a.map(This(_)) case (Tip(), b ) => b.map(That(_)) case (a , b ) => a.map(This(_): A \&/ B).unionWith(b.map(That(_): A \&/ B)){ case (This(aa), That(bb)) => Both(aa, bb) case _ => sys.error("==>> align") } } override def alignWith[A, B, C](f: A \&/ B => C) = { case (Tip(), Tip()) => Tip() case (a , Tip()) => a.map(aa => f(This(aa))) case (Tip(), b ) => b.map(bb => f(That(bb))) case (a , b ) => a.map(This(_): A \&/ B).unionWith(b.map(That(_): A \&/ B)){ case (This(aa), That(bb)) => Both(aa, bb) case _ => sys.error("==>> alignWith") }.map(f) } def zip[A, B](a: => (S ==>> A), b: => (S ==>> B)) = { val a0 = a if(a0.isEmpty) ==>>.empty else a0.intersectionWith(b)(Tuple2.apply) } override def zipWith[A, B, C](a: => (S ==>> A), b: => (S ==>> B))(f: (A, B) => C)(implicit F: Functor[S ==>> ?]) = { val a0 = a if(a0.isEmpty) ==>>.empty else a0.intersectionWith(b)(f) } } } sealed abstract class MapInstances extends MapInstances0 { import ==>>._ import std.list._ import std.tuple._ implicit def mapShow[A: Show, B: Show]: Show[==>>[A, B]] = Contravariant[Show].contramap(Show[List[(A, B)]])(_.toAscList) implicit def mapEqual[A: Equal, B: Equal]: Equal[A ==>> B] = new MapEqual[A, B] {def A = implicitly; def B = implicitly} implicit def mapOrder[A: Order, B: Order]: Order[A ==>> B] = new Order[A ==>> B] with MapEqual[A, B] { def A = implicitly def B = implicitly def order(o1: A ==>> B, o2: A ==>> B) = Order[List[(A,B)]].order(o1.toAscList, o2.toAscList) } implicit def mapUnion[A, B](implicit A: Order[A], B: Semigroup[B]): Monoid[A ==>> B] = Monoid.instance((l, r) => (l unionWith r)(B.append(_, _)), Tip()) implicit def mapIntersection[A, B](implicit A: Order[A], B: Semigroup[B] ): Semigroup[(A ==>> B) @@ Tags.Conjunction] = Tag.subst(Semigroup.instance((l, r) => (l intersectionWith r)(B.append(_, _)))) implicit def mapCovariant[S]: Traverse[S ==>> ?] = new Traverse[S ==>> ?] { override def findLeft[A](fa: S ==>> A)(f: A => Boolean): Option[A] = fa match { case Bin(_, x, l, r) => findLeft(l)(f) match { case a @ Some(_) => a case None => if (f(x)) Some(x) else findLeft(r)(f) } case Tip() => None } override def findRight[A](fa: S ==>> A)(f: A => Boolean): Option[A] = fa match { case Bin(_, x, l, r) => findRight(r)(f) match { case a @ Some(_) => a case None => if (f(x)) Some(x) else findRight(l)(f) } case Tip() => None } override def map[A, B](fa: S ==>> A)(f: A => B): S ==>> B = fa map f override def foldMap[A, B](fa: S ==>> A)(f: A => B)(implicit F: Monoid[B]): B = fa match { case Tip() => F.zero case Bin(k, x, l, r) => F.append(foldMap(l)(f), F.append(f(x), foldMap(r)(f))) } override def foldRight[A, B](fa: S ==>> A, z: => B)(f: (A, => B) => B): B = fa.foldrWithKey(z)((_, b, acc) => f(b, acc)) override def foldLeft[A, B](fa: S ==>> A, z: B)(f: (B, A) => B): B = fa.foldlWithKey(z)((acc, _, b) => f(acc, b)) override def index[A](fa: S ==>> A, i: Int): Option[A] = fa.elemAt(i).map(_._2) def traverseImpl[F[_], A, B](fa: S ==>> A)(f: A => F[B])(implicit G: Applicative[F]): F[S ==>> B] = fa match { case Tip() => G.point(Tip()) case Bin(kx, x, l, r) => G.apply3(traverseImpl(l)(f), f(x), traverseImpl(r)(f)){ (l2, x2, r2) => Bin(kx, x2, l2, r2) } } override def length[A](fa: S ==>> A): Int = fa.size override def any[A](fa: S ==>> A)(f: A => Boolean): Boolean = fa match { case Tip() => false case Bin(_, x, l, r) => any(l)(f) || f(x) || any(r)(f) } override def all[A](fa: S ==>> A)(f: A => Boolean): Boolean = fa match { case Tip() => true case Bin(_, x, l, r) => all(l)(f) && f(x) && all(r)(f) } } implicit val mapBifoldable: Bifoldable[==>>] = new Bifoldable[==>>] { def bifoldMap[A,B,M](fa: A ==>> B)(f: A => M)(g: B => M)(implicit F: Monoid[M]): M = fa match { case Tip() => F.zero case Bin(k, x, l, r) => F.append(bifoldMap(l)(f)(g), F.append(f(k), F.append(g(x), bifoldMap(r)(f)(g)))) } def bifoldRight[A,B,C](fa: A ==>> B, z: => C)(f: (A, => C) => C)(g: (B, => C) => C): C = fa.foldrWithKey(z)((a, b, c) => f(a, g(b, c))) override def bifoldLeft[A,B,C](fa: A ==>> B, z: C)(f: (C, A) => C)(g: (C, B) => C): C = fa.foldlWithKey(z)((c, a, b) => g(f(c, a), b)) } } private[scalaz] sealed trait MapEqual[A, B] extends Equal[A ==>> B] { import std.list._ import std.tuple._ implicit def A: Equal[A] implicit def B: Equal[B] final override def equal(a1: A ==>> B, a2: A ==>> B): Boolean = Equal[Int].equal(a1.size, a2.size) && Equal[List[(A, B)]].equal(a1.toAscList, a2.toAscList) } object ==>> extends MapInstances { private[scalaz] case object Tip extends (Nothing ==>> Nothing) { val size = 0 def unapply[A, B](a: A ==>> B): Boolean = a eq this def apply[A, B](): A ==>> B = this.asInstanceOf[A ==>> B] } private[scalaz] final case class Bin[A, B](k: A, v: B, l: A ==>> B, r: A ==>> B) extends ==>>[A, B] { val size = l.size + r.size + 1 } final def apply[A: Order, B](x: (A, B)*): A ==>> B = x.foldLeft(empty[A, B])((a, c) => a.insert(c._1, c._2)) final def empty[A, B]: A ==>> B = Tip[A, B]() final def singleton[A, B](k: A, x: B): A ==>> B = Bin(k, x, Tip(), Tip()) /* List operations */ final def fromList[A: Order, B](l: List[(A, B)]): A ==>> B = l.foldLeft(empty[A, B]) { (t, x) => t.insert(x._1, x._2) } final def fromListWith[A: Order, B](l: List[(A, B)])(f: (B, B) => B): A ==>> B = fromListWithKey(l)((_, x, y) => f(x, y)) final def fromListWithKey[A: Order, B](l: List[(A, B)])(f: (A, B, B) => B): A ==>> B = l.foldLeft(empty[A, B])((a, c) => a.insertWithKey(f, c._1, c._2)) /* TODO: Ordered lists , fromAscList , fromAscListWith , fromAscListWithKey , fromDistinctAscList */ /* Foldable operations */ final def fromFoldable[F[_]: Foldable, A: Order, B](fa: F[(A, B)]): A ==>> B = Foldable[F].foldLeft(fa, empty[A, B]) { (t, x) => t.insert(x._1, x._2) } final def fromFoldableWith[F[_]: Foldable, A: Order, B](fa: F[(A, B)])(f: (B, B) => B): A ==>> B = fromFoldableWithKey(fa)((_, x, y) => f(x, y)) final def fromFoldableWithKey[F[_]: Foldable, A: Order, B](fa: F[(A, B)])(f: (A, B, B) => B): A ==>> B = Foldable[F].foldLeft(fa, empty[A, B])((a, c) => a.insertWithKey(f, c._1, c._2)) final def fromSet[A: Order, B](s: ISet[A])(f: A => B): A ==>> B = s match { case ISet.Tip() => empty case ISet.Bin(x, l, r) => Bin(x, f(x), fromSet(l)(f), fromSet(r)(f)) } final def unions[A: Order, B](xs: List[A ==>> B]): A ==>> B = xs.foldLeft(empty[A, B])((a, c) => a.union(c)) final def unionsWith[A: Order, B](f: (B, B) => B)(xs: List[A ==>> B]): A ==>> B = xs.foldLeft(empty[A, B])((a, c) => a.unionWith(c)(f)) private[scalaz] final val ratio = 2 private[scalaz] final val delta = 3 // Even though we have balanceL and balanceR, we need balance function // as alter function still needs it. private[scalaz] def balance[A, B](k: A, x: B, l: A ==>> B, r: A ==>> B): A ==>> B = l match { case Tip() => r match { case Tip() => singleton(k, x) case Bin(_, _, Tip(), Tip()) => Bin(k, x, Tip(), r) case Bin(rk, rx, Tip(), rr@Bin(_, _, _, _)) => Bin(rk, rx, singleton(k, x), rr) case Bin(rk, rx, Bin(rlk, rlx, _, _), Tip()) => Bin(rlk, rlx, singleton(k, x), singleton(rk, rx)) case Bin(rk, rx, rl@Bin(rlk, rlx, rll, rlr), rr@Bin(_, _, _, _)) => if (rl.size < ratio*rr.size) Bin(rk, rx, Bin(k, x, Tip(), rl), rr) else Bin(rlk, rlx, Bin(k, x, Tip(), rll), Bin(rk, rx, rlr, rr)) } case Bin(lk, lx, ll, lr) => r match { case Tip() => (ll, lr) match { case (Tip(), Tip()) => Bin(k, x, l, Tip()) case (Tip(), Bin(lrk, lrx, _, _)) => Bin(lrk, lrx, singleton(lk, lx), singleton(k, x)) case (Bin(_, _, _, _), Tip()) => Bin(lk, lx, ll, singleton(k, x)) case (Bin(_, _, _, _), Bin(lrk, lrx, lrl, lrr)) => if (lr.size < ratio*ll.size) Bin(lk, lx, ll, Bin(k, x, lr, Tip())) else Bin(lrk, lrx, Bin(lk, lx, ll, lrl), Bin(k, x, lrr, Tip())) } case Bin(rk, rx, rl, rr) => if (r.size > delta*l.size) { (rl, rr) match { case (Bin(rlk, rlx, rll, rlr), Bin(_, _, _, _)) => if (rl.size < ratio*rr.size) Bin(rk, rx, Bin(k, x, l, rl), rr) else Bin(rlk, rlx, Bin(k, x, l, rll), Bin(rk, rx, rlr, rr)) case _ => sys.error("Failure in Map.balance") } } else if (l.size > delta*r.size) { (ll, lr) match { case (Bin(_, _, _, _), Bin(lrk, lrx, lrl, lrr)) => if (lr.size < ratio*ll.size) Bin(lk, lx, ll, Bin(k, x, lr, r)) else Bin(lrk, lrx, Bin(lk, lx, ll, lrl), Bin(k, x, lrr, r)) case _ => sys.error("Failure in Map.balance") } } else Bin(k, x, l, r) } } // balanceL is used to balance a tree when an element might have been inserted to // a left subtree, or when an element might have been deleted from a right subtree. private[scalaz] def balanceL[A, B](k: A, x: B, l: A ==>> B, r: A ==>> B): A ==>> B = r match { case Tip() => l match { case Tip() => singleton(k, x) case Bin(_, _, Tip(), Tip()) => Bin(k, x, l, Tip()) case Bin(lk, lx, Tip(), Bin(lrk, lrx, _, _)) => Bin(lrk, lrx, singleton(lk, lx), singleton(k, x)) case Bin(lk, lx, ll@Bin(_, _, _, _), Tip()) => Bin(lk, lx, ll, singleton(k, x)) case Bin(lk, lx, ll@Bin(_, _, _, _), lr@Bin(lrk, lrx, lrl, lrr)) => if (lr.size < ratio*ll.size) Bin(lk, lx, ll, Bin(k, x, lr, Tip())) else Bin(lrk, lrx, Bin(lk, lx, ll, lrl), Bin(k, x, lrr, Tip())) } case Bin(_, _, _, _) => l match { case Tip() => Bin(k, x, Tip(), r) case Bin(lk, lx, ll, lr) => if (l.size > delta*r.size) { (ll, lr) match { case (Bin(_, _, _, _), Bin(lrk, lrx, lrl, lrr)) => if (lr.size < ratio*ll.size) Bin(lk, lx, ll, Bin(k, x, lr, r)) else Bin(lrk, lrx, Bin(lk, lx, ll, lrl), Bin(k, x, lrr, r)) case _ => sys.error("Failure in Map.balanceL") } } else Bin(k, x, l, r) } } // balanceR is used to balance a tree when a key-value might have been inserted to // a right subtree, or when a key-value might have been deleted from a left subtree. private[scalaz] def balanceR[A, B](k: A, x: B, l: A ==>> B, r: A ==>> B): A ==>> B = l match { case Tip() => r match { case Tip() => singleton(k, x) case Bin(_, _, Tip(), Tip()) => Bin(k, x, Tip(), r) case Bin(rk, rx, Tip(), rr@Bin(_, _, _, _)) => Bin(rk, rx, singleton(k, x), rr) case Bin(rk, rx, Bin(rlk, rlx, _, _), Tip()) => Bin(rlk, rlx, singleton(k, x), singleton(rk, rx)) case Bin(rk, rx, rl@Bin(rlk, rlx, rll, rlr), rr@Bin(_, _, _, _)) => if (rl.size < ratio*rr.size) Bin(rk, rx, Bin(k, x, Tip(), rl), rr) else Bin(rlk, rlx, Bin(k, x, Tip(), rll), Bin(rk, rx, rlr, rr)) } case Bin(_, _, _, _) => r match { case Tip() => Bin(k, x, l, Tip()) case Bin(rk, rx, rl, rr) => if (r.size > delta*l.size) { (rl, rr) match { case (Bin(rlk, rlx, rll, rlr), Bin(_, _, _, _)) => if (rl.size < ratio*rr.size) Bin(rk, rx, Bin(k, x, l, rl), rr) else Bin(rlk, rlx, Bin(k, x, l, rll), Bin(rk, rx, rlr, rr)) case _ => sys.error("Failure in Map.balanceR") } } else Bin(k, x, l, r) } } private[scalaz] def link[A, B](kx: A, x: B, l: A ==>> B, r: A ==>> B): A ==>> B = (l, r) match { case (Tip(), r) => insertMin(kx, x, r) case (l, Tip()) => insertMax(kx, x, l) case (Bin(ky, y, ly, ry), Bin(kz, z, lz, rz)) => if (delta * l.size < r.size) balanceL(kz, z, link(kx, x, l, lz), rz) else if (delta * r.size < l.size) balanceR(ky, y, ly, link(kx, x, ry, r)) else Bin(kx, x, l, r) } // insertMax and insertMin are only used for link(...) private def insertMax[A, B](kx: A, x: B, t: A ==>> B): A ==>> B = t match { case Tip() => singleton(kx, x) case Bin(ky, y, l, r) => balanceR(ky, y, l, insertMax(kx, x, r)) } private def insertMin[A, B](kx: A, x: B, t: A ==>> B): A ==>> B = t match { case Tip() => singleton(kx, x) case Bin(ky, y, l, r) => balanceL(ky, y, insertMin(kx, x, l), r) } private[scalaz] def trim[A, B](lo: Option[A], hi: Option[A], t: A ==>> B)(implicit o: Order[A]): A ==>> B = (lo, hi) match { case (None, None) => t case (Some(lk), None) => @tailrec def greater(lo: A, m: A ==>> B): A ==>> B = m match { case Bin(kx, _, _, r) if o.lessThanOrEqual(kx, lo) => greater(lo, r) case _ => m } greater(lk, t) case (None, Some(hk)) => @tailrec def lesser(hi: A, m: A ==>> B): A ==>> B = m match { case Bin(kx, _, l, _) if o.greaterThanOrEqual(kx, hi) => lesser(hi, l) case _ => m } lesser(hk, t) case (Some(lk), Some(hk)) => @tailrec def middle(lo: A, hi: A, m: A ==>> B): A ==>> B = m match { case Bin(kx, _, _, r) if o.lessThanOrEqual(kx, lo) => middle(lo, hi, r) case Bin(kx, _, l, _) if o.greaterThanOrEqual(kx, hi) => middle(lo, hi, l) case _ => m } middle(lk, hk, t) } private[scalaz] def trimLookupLo[A, B](lk: A, hkOption: Option[A], t: A ==>> B)(implicit o: Order[A]): (Option[B], A ==>> B) = hkOption match { case None => @tailrec def greater(lo: A, m: A ==>> B): (Option[B], A ==>> B) = m match { case Tip() => (none, Tip()) case Bin(kx, x, l, r) => o.order(lo, kx) match { case LT => (l.lookup(lo), m) case EQ => (some(x), r) case GT => greater(lo, r) } } greater(lk, t) case Some(hk) => @tailrec def middle(lo: A, hi: A, m: A ==>> B): (Option[B], A ==>> B) = m match { case Tip() => (none, Tip()) case Bin(kx, x, l, r) => o.order(lo, kx) match { case LT if o.order(kx, hi) == LT => (l.lookup(lo), m) case LT => middle(lo, hi, l) case EQ => (some(x), lesser(hi, r)) case GT => middle(lo, hi, r) } } @tailrec def lesser(hi: A, m: A ==>> B): A ==>> B = m match { case Bin(k, _, l, _) if o.greaterThanOrEqual(k, hi) => lesser(hi, l) case _ => m } middle(lk, hk, t) } /* * The documentation below is partially copied from haskell/containers Map. * Please refer to the full documentation if necessary. * @see [[https://github.com/haskell/containers/blob/v0.5.7.1/Data/Map/Base.hs#L1402-L1440]] * -- | /O(n+m)/. A high-performance universal combining function. This function -- is used to define 'unionWith', 'unionWithKey', 'differenceWith', -- 'differenceWithKey', 'intersectionWith', 'intersectionWithKey' and can be -- used to define other custom combine functions. -- When calling mergeWithKey(a, b)(f)(g1, g2), a function combining two -- 'Map's is created, such that -- -- * if a key is present in both maps, it is passed with both corresponding -- values to the combine @f@ function. Depending on the result, the key is either -- present in the result with specified value, or is left out; -- -- * a nonempty subtree present only in the first map is passed to @g1@ and -- the output is added to the result; -- -- * a nonempty subtree present only in the second map is passed to @g2@ and -- the output is added to the result. * * @param a first map * @param b second map * @param f combine function used to define `XxxWithKey` * @param g1 function applied to a nonempty subtree present only in the first map a * @param g2 function applied to a nonempty subtree present only in the second map b */ def mergeWithKey[A: Order, B, C, D](a: A ==>> B, b: A ==>> C) (f: (A, B, C) => Option[D]) (g1: (A ==>> B) => (A ==>> D), g2: (A ==>> C) => (A ==>> D)) (implicit o: Order[A]): A ==>> D = { def hedgeMerge(blo: Option[A], bhi: Option[A], a: A ==>> B, b: A ==>> C): A ==>> D = { (a, b) match { case (t1, Tip()) => g1(t1) case (Tip(), Bin(kx, x, l, r)) => val t2 = link(kx, x, l.filterGt(blo)(o), r.filterLt(bhi)(o)) g2(t2) case (Bin(kx, x, l, r), t2) => val bmi = some(kx) val l2 = hedgeMerge(blo, bmi, l, trim(blo, bmi, t2)(o)) val (found, trim_t2) = trimLookupLo(kx, bhi, t2)(o) val r2 = hedgeMerge(bmi, bhi, r, trim_t2) found match { case None => g1(singleton(kx, x)) match { case Tip() => l2 merge r2 case Bin(_, x2, Tip(), Tip()) => link(kx, x2, l2, r2) case _ => sys.error("mergeWithKey: Given function g1 does not fulfil required conditions (see documentation)") } case Some(x2) => f(kx, x, x2) match { case None => l2 merge r2 case Some(xx) => link(kx, xx, l2, r2) } } } } (a, b) match { case (Tip(), t2) => g2(t2) case (t1, Tip()) => g1(t1) case (t1, t2) => hedgeMerge(None, None, t1, t2) } } } Other Scala examples (source code examples)Here is a short list of links related to this Scala Map.scala source code file: |
... this post is sponsored by my books ... | |
#1 New Release! |
FP Best Seller |
Copyright 1998-2021 Alvin Alexander, alvinalexander.com
All Rights Reserved.
A percentage of advertising revenue from
pages under the /java/jwarehouse
URI on this website is
paid back to open source projects.