History.scala

object History {
  val emptyRootHash: Blake2b256Hash = RadixHistory.emptyRootHash

  def create[F[_]: Concurrent: Sync: Parallel](
      root: Blake2b256Hash,
      store: KeyValueStore[F]
  ): F[RadixHistory[F]] = RadixHistory(root, RadixHistory.createStore(store))

  type KeyPath = Seq[Byte]
  type KeyWord = Byte
  
  // Key segment implementation using byte sequence
  implicit val baks = (bv: Seq[Byte]) =>
    new KeySegment[Seq[Byte], Byte] {
      def value: Seq[Byte]                = bv
      def size: Long                      = value.length.toLong
      def nonEmpty: Boolean               = value.nonEmpty
      def isEmpty: Boolean                = value.isEmpty
      def head: Byte                      = value.head
      def tail: Seq[Byte]                 = value.tail
      def headOption: Option[Byte]        = value.headOption
      def ++(other: Seq[Byte]): Seq[Byte] = value ++ other
      def :+(byte: Byte): Seq[Byte]       = value :+ byte
      def toHex: String                   = value.map(_.toString).mkString(" ")
    }
  implicit val baEmpty = new EmptyKey[Seq[Byte]] {
    override def empty: Seq[Byte] = Seq.empty[Byte]
  }

  // Key segment implementation using ByteVector
//  implicit val bvks = (bv: ByteVector) =>
//    new KeySegment[ByteVector, Byte] {
//      def value: ByteVector                 = bv
//      def size: Long                        = value.size
//      def nonEmpty: Boolean                 = value.nonEmpty
//      def isEmpty: Boolean                  = value.isEmpty
//      def head: Byte                        = value.head
//      def tail: ByteVector                  = value.tail
//      def headOption: Option[Byte]          = value.headOption
//      def ++(other: ByteVector): ByteVector = value ++ other
//      def :+(byte: Byte): ByteVector        = value :+ byte
//      def toHex: String                     = value.toHex
//    }
//  implicit val bvEmpty = new EmptyKey[ByteVector] {
//    override def empty: ByteVector = ByteVector.empty
//  }

}

KeySegment.scala

/**
  * Segment of a History key
  * @tparam V type of a key value
  * @tparam I type of a word in key alphabet
  */
trait KeySegment[V, I] {
  def size: Long
  def isEmpty: Boolean
  def nonEmpty: Boolean
  def head: I
  def headOption: Option[I]
  def toHex: String
  def :+(item: I): V
  def tail: V
  def ++(other: V): V
}

object KeySegment {

  trait EmptyKey[V] {
    def empty: V
  }

  /**
    * Find the common part of b1 and b2.
    * @return (Common part, rest of b1, rest of b2).
    */
  def commonPrefix[V, I](a: V, b: V)(
      implicit vAsKS: V => KeySegment[V, I],
      empty: EmptyKey[V]
  ): (V, V, V) = {
    @tailrec
    def go(common: V, l: V, r: V): (V, V, V) =
      if (r.isEmpty || l.isEmpty) (common, l, r)
      else {
        val lHead = l.head
        val rHead = r.head
        if (lHead == rHead) go(common :+ lHead, l.tail, r.tail)
        else (common, l, r)
      }

    go(empty[V], a, b)
  }
}