Coverage Summary for Class: HashMapVector (lzwpack.data)

1 package lzwpack.data 2  3 import cats.{Eval, Now, Hash} 4 import cats.implicits._ 5  6 /** 7  * A [[HashMapVector]] is a hash map implementation on top of a bit-indexed trie. 8  * As such, it provides the same functionality and performance characteristics as 9  * [[SparseVector]], but instead of an integer key we can use any JVM object with 10  * `hashCode` implemented as the key. 11  */ 12 class HashMapVector[K: Hash, @specialized V] private[data](private val vector: SparseVector[HashMapVector[K, V]#Bucket]) { 13  // Use overflow lists ("buckets") to handle hashCode collisions 14  type Bucket = ListVector[(K, V)] 15  16  private def bucketForKey(key: K): Bucket = vector.get(key.hash).getOrElse(ListVector.empty) 17  18  // Sets (k -> v) in the given bucket 19  private def addOrReplaceInBucket(bucket: Bucket)(kv: (K, V)): Bucket = kv match { 20  case (key, _) => bucket.filter(_._1 =!= key) + kv 21  } 22  23  /** 24  * Returns a value for a given key. 25  * 26  * @throws scala.NoSuchElementException if there's no mapping from the given key to a value 27  */ 28  def apply(key: K): V = get(key).getOrElse(throw new NoSuchElementException) 29  30  /** 31  * Returns whether this HashMapVector contains a value for a given key. 32  */ 33  def contains(key: K): Boolean = get(key).nonEmpty 34  35  /** 36  * Returns an [[scala.Some]] with the value for the given key, or [[scala.None]] if there's no value. 37  */ 38  def get(key: K): Option[V] = for { 39  (_, value) <- bucketForKey(key).find(_._1 === key) 40  } yield value 41  42  /** 43  * Returns a new HashMapVector with the given key-value mapping changed. 44  */ 45  def updated(kv: (K, V)): HashMapVector[K, V] = 46  new HashMapVector(vector.updated(kv._1.hash, addOrReplaceInBucket(bucketForKey(kv._1))(kv))) 47  48  /** 49  * Alias for [[updated]] 50  */ 51  def +(kv: (K, V)): HashMapVector[K, V] = updated(kv) 52  53  /** 54  * Returns the number of key-value mappings in this HashMapVector. 55  */ 56  lazy val size: Int = vector.fold(0) { case ((_, xs), acc) => xs.size + acc } 57  58  /** 59  * Returns true if this HashMapVector contains no elements, false otherwise. 60  */ 61  def isEmpty: Boolean = vector.isEmpty 62  63  /** 64  * Folds the values of this HashMapVector with the given initial value and function. 65  * The order for traversing the values is unspecified. 66  */ 67  def fold[B](init: => B)(f: ((K, V), => B) => B): B = 68  vector.fold(init) { case ((_, kvs), rest) => kvs.foldRight(Eval.later(rest))((h, t) => Now(f(h, t.value))).value } 69  70  /** 71  * Returns the first element that `f` returns true for. If no element matches `f` then [[scala.None]] is returned. 72  * The order for traversing the values is unspecified. 73  */ 74  def find(f: (K, V) => Boolean): Option[(K, V)] = fold(Option.empty[(K, V)]) { 75  case ((k, v), acc) if f(k, v) => Some((k, v)) 76  case (_, acc) => acc 77  } 78  79  override def toString: String = s"HashMapVector($size elements)" 80 } 81  82 object HashMapVector { 83  /** 84  * Given a sequence of key-value tuples, constructs a new HashMapVector from them. 85  */ 86  def apply[K: Hash, V](kvs: (K, V)*): HashMapVector[K, V] = { 87  kvs.foldLeft(empty[K, V])((map, kv) => map + kv) 88  } 89  90  /** 91  * Returns an empty HashMapVector. 92  */ 93  def empty[K: Hash, V] = new HashMapVector[K, V](SparseVector.empty) 94 }