Coverage Summary for Class: ListVector (lzwpack.data)

1 package lzwpack.data 2  3 import ListVector._ 4 import cats._ 5 import cats.implicits._ 6  7  8 /** 9  * A [[ListVector]] is a list-like data structure in the sense that it provides 10  * efficient random access and append; prepend is not yet supported. 11  * Compared to a [[SparseVector]] this data structure is _bounded_ meaning that given a list with size |L| > 0 12  * there is guaranteed to be an element in each k ∈ [0..|L| - 1]. Updates to indices outside of the index range are prohibited. 13  */ 14 class ListVector[@specialized A] private[data](private[data] val trie: SparseVector[A], val size: Int, offset: Int = 0) { 15  /** 16  * Returns a new [[ListVector]] for which f(a) == true for all elements. 17  * Note that indices are not preserved; for instance, if index 3 was filtered out and 4 was not, 18  * then index 4 would become index 3. This is to preserve list-like semantics. 19  */ 20  def filter(f: A => Boolean): ListVector[A] = foldLeft(empty[A])((as, a) => if (f(a)) as + a else as) 21  22  /** 23  * Concatenates the argument to this [[ListVector]]. 24  */ 25  def concat(as1: ListVector[A]): ListVector[A] = as1.foldLeft(this)(_ + _) 26  27  /** 28  * Returns the first element `a` in this [[ListVector]] for which `f(a)` returns true, wrapped in an [[scala.Option]]. 29  * If no element matches `f`, then a [[scala.None]] is returned. 30  */ 31  def find(f: A => Boolean): Option[A] = foldRight(none[A]) { (a, rest) => if (f(a)) a.some else rest } 32  33  /** 34  * Unsafe version of [[get]]. 35  * @throws scala.IndexOutOfBoundsException if this [[ListVector]] does not contain the given index 36  */ 37  def apply(i: Int): A = get(i).getOrElse(throw new IndexOutOfBoundsException(s"$i > $size (offset $offset)")) 38  39  /** 40  * Returns the first element of this [[ListVector]]. 41  * @throws scala.IndexOutOfBoundsException if this [[ListVector]] is empty 42  */ 43  lazy val head: A = this(0) 44  45  /** 46  * Like [[head]], but returns an [[scala.Option]] determining the success of the operation instead of throwing 47  * an exception. 48  */ 49  lazy val headOption: Option[A] = get(0) 50  51  /** 52  * Returns a [[ListVector]] with all the elements from this vector except the first one (see [[head]]). 53  * The first index is dropped so that 54  * {{{ 55  * ListVector(1,2,3).tail.get(0) == Some(2) 56  * }}} 57  */ 58  lazy val tail: ListVector[A] = drop(1) 59  60  /** 61  * Returns a new [[ListVector]] without the first `n` items. 62  */ 63  def drop(n: Int): ListVector[A] = { 64  if (n > size) empty[A] else new ListVector(trie, size - n, offset + n) 65  } 66  67  /** 68  * Returns a new [[ListVector]] with only the first `n` items present. 69  */ 70  def take(n: Int): ListVector[A] = new ListVector[A](trie, Math.min(n, size), offset) 71  72  /** 73  * Appends the given value to the end of this [[ListVector]]. 74  * Complexity: O(log n) 75  */ 76  def append(a: A) = new ListVector(trie.updated(offset + size, a), size + 1) 77  78  /** 79  * If there exists an element with the given index, returns an [[scala.Option]] containing the element or 80  * an empty option otherwise. 81  * Complexity: O(log n) 82  */ 83  def get(i: Int): Option[A] = if (i < size) trie get (offset + i) else none[A] 84  85  /** 86  * Returns true if this [[ListVector]] contains an element at index `i`, `false` otherwise. 87  */ 88  def contains(i: Int): Boolean = get(i).isDefined 89  90  /** 91  * Alias for [[append]]. 92  */ 93  def +(a: A): ListVector[A] = append(a) 94  95  /** 96  * Alias for [[append]]. 97  */ 98  def :+(a: A): ListVector[A] = append(a) 99  100  /** 101  * Returns `true` if this [[ListVector]] is empty (i.e. contains no elements), `false` otherwise. 102  */ 103  def isEmpty: Boolean = size == 0 104  105  // Uses random access for speed (?) 106  @annotation.tailrec 107  private def foldl[B](start: Int, end: Int, init: B, f: (B, A) => B): B = { 108  if (start == end) init 109  else foldl(start + 1, end, f(init, this(start)), f) 110  } 111  112  private def foldr[B](start: Int, end: Int, init: => B, f: (A, => B) => B): B = { 113  if (start == end) init 114  else f(this(start), foldr(start + 1, end, init, f)) 115  } 116  117  /** 118  * Left folds the elements of this [[ListVector]]. 119  */ 120  def foldLeft[B](init: B)(f: (B, A) => B): B = foldl(0, size, init, f) 121  122  /** 123  * Right folds the elements of this ListVector. 124  */ 125  def foldRight[B](init: => B)(f: (A, => B) => B): B = foldr(0, size, init, f) 126  127  /** 128  * Returns an [[scala.Iterator]] for this [[ListVector]]. 129  * @note we do not implement the Iterable trait in order to make our own data structure methods 130  */ 131  def iterator: Iterator[A] = new Iterator[A] { 132  private var i = offset 133  134  override def hasNext: Boolean = ListVector.this.contains(i) 135  136  override def next(): A = { 137  val a = ListVector.this(i) 138  i += 1 139  a 140  } 141  } 142  143  /** 144  * Returns a new [[ListVector]] with each element applied to `f`. 145  */ 146  def map[B](f: A => B): ListVector[B] = 147  foldLeft(empty[B])((acc, a) => acc + f(a)) 148  149  override lazy val toString: String = s"ListVector(${this.map(_.toString).intercalate(", ")})" 150  151  /** 152  * Hash code calculated as in [[java.util.List]]. 153  */ 154  override lazy val hashCode: Int = foldLeft(1)((acc, e) => 31 * acc + e.hashCode()) 155  156  /** 157  * Converts this ListVector to a [[scala.Seq]]. 158  */ 159  lazy val toSeq: Seq[A] = iterator.toSeq 160 } 161  162 object ListVector { 163  def empty[A] = new ListVector(SparseVector.empty[A], 0) 164  165  def apply[A](as: A*): ListVector[A] = seq(as) 166  167  def seq[A](as: Seq[A]): ListVector[A] = as.foldLeft(empty[A])(_ + _) 168  169  def unfold[A, S](init: S)(f: S => Option[(A, S)]): ListVector[A] = { 170  @annotation.tailrec 171  def iter(acc: ListVector[A], s1: S): ListVector[A] = f(s1) match { 172  case None => acc 173  case Some((a, s2)) => iter(acc + a, s2) 174  } 175  iter(empty[A], init) 176  } 177  178  def range[A: Integral](from: A, to: A)(implicit integral: Integral[A]): ListVector[A] = { 179  import integral._ 180  // We need to append the upper bound explicitly in order to avoid numeric overflows when comparing values. 181  unfold(from)(_.some.filter(_ < to).map(n => (n, n + one))) + to 182  } 183 } 184  185 object :: { 186  def unapply[A](as: ListVector[A]): Option[(A, ListVector[A])] = as.headOption.map((_, as.tail)) 187 }