Coverage Summary for Class: Branch (lzwpack.data)

Class	Method, %	Line, %
Branch	100% (8/ 8)	100% (13/ 13)
Branch$	0% (0/ 1)	0% (0/ 1)
total	88.9% (8/ 9)	92.9% (13/ 14)
1 package lzwpack.data
2 
3 import lzwpack._
4 
5 import scala.annotation.unchecked.uncheckedVariance
6 import SparseVector._
7 import cats.Eval
8 
9 /**
10   * A [[SparseVector]] is a bit-mapped trie with 32 branches at each node.
11   * It supports O(log32(n)) insertion, updating and random access.
12   */
13 sealed trait SparseVector[@specialized +A] {
14   def apply(i: Int): A = get(i).getOrElse(throw new NoSuchElementException)
15 
16   def contains(i: Int): Boolean = get(i).nonEmpty
17 
18   def get(i: Int): Option[A]
19 
20   def updated[AA >: A](i: Int, a: AA): SparseVector[AA]
21 
22   def +[AA >: A](kv: (Int, AA)): SparseVector[AA] = kv match {
23     case (k, v) => updated(k, v)
24   }
25 
26   def fold[B](init: => B)(f: ((Int, A), => B) => B): B
27 
28   // Note: O(n) complexity because we don't really keep track of the bounds
29   lazy val size: Int = fold(0)((_, n) => n + 1)
30 
31   def find(f: (Int, A) => Boolean): Option[(Int, A)] = fold(Option.empty[(Int, A)]) {
32     case ((k, v), _) if f(k, v) => Some((k, v))
33     case (_, acc) => acc
34   }
35 
36   def isEmpty: Boolean
37 }
38 
39 // Type parameter variance on Array is suppressed due to it being invariant; we can maintain the invariant ourselves
40 // by never mutating the array
41 private[data] case class Branch[+A](private val subforest: Array[SparseVector[A @uncheckedVariance]]) extends SparseVector[A] {
42   def get(i: Int): Option[A] = {
43     subforest(i & Bitmask).get(i >>> ChunkSize)
44   }
45 
46   def updated[AA >: A](i: Int, a: AA): SparseVector[AA] = {
47     // Make a new copy of the array to preserve persistence
48     val copy = new Array[SparseVector[AA]](Radix)
49     subforest.copyToArray(copy)
50     copy.update(i & Bitmask, copy(i & Bitmask).updated(i >>> ChunkSize, a))
51 
52     Branch[AA](copy)
53   }
54 
55 
56   /**
57     * Folds this trie in a depth-first manner.
58     */
59   override def fold[B](init: => B)(f: ((Int, A), => B) => B): B = {
60     var acc = init
61     for ((subtree, prefix) <- subforest.zipWithIndex if !subtree.isEmpty) {
62       acc = subtree.fold(acc) { case ((suffix, v), acc) =>
63         val key = (suffix << ChunkSize) ^ prefix
64         f((key, v), acc)
65       }
66     }
67     acc
68   }
69 
70   override val isEmpty: Boolean = false
71 }
72 
73 private[data] case class Leaf[+A](key: Int, value: A) extends SparseVector[A] {
74   def get(i: Int) = if (key == i) Some(value) else None
75   def updated[AA >: A](i: Int, a: AA): SparseVector[AA] = {
76     if (key == i) {
77       // Update the existing element
78       Leaf(key, a)
79     } else {
80       // Convert this Leaf to a Branch with the new and current values as leaves
81       EmptyBranch.updated(key, value).updated(i, a)
82     }
83   }
84 
85 
86   override def fold[B](init: => B)(f: ((Int, A), => B) => B): B = f((key, value), init)
87 
88   override val isEmpty: Boolean = false
89 }
90 
91 private[data] case object Empty extends SparseVector[Nothing] {
92   def get(i: Int): Option[Nothing] = None
93   def updated[A](i: Int, a: A): SparseVector[A] = Leaf(i, a)
94 
95   override val isEmpty: Boolean = true
96 
97   override def fold[B](init: => B)(f: ((Int, Nothing), => B) => B): B = init
98 }
99 
100 object SparseVector {
101   val Radix = 32
102   private[data] val ChunkSize = Radix.bitsize - 1
103   private[data] val Bitmask = Radix - 1 // Radix must be a power of 2, so (Radix - 1) masks values 0..Radix
104 
105   def apply[A](as: A*): SparseVector[A] = as.zipWithIndex.foldLeft(EmptyBranch: SparseVector[A]) {
106     case (acc, (a, i)) => acc.updated(i, a)
107   }
108 
109   def empty[A]: SparseVector[A] = Empty
110 
111   // we only need a single empty branch instance
112   private[data] val EmptyBranch: SparseVector[Nothing] = Branch(Array.fill(Radix)(empty))
113 }