функция для нах-я ноды с префиксом

import scala.collection.immutable.HashMap

class CritBitTree[T](nodes: HashMap[String, CritBitTree[T]], isExternalNode: Boolean, data: Option[T]) {
  def this(isExternalNode: Boolean, data: Option[T]) = this(HashMap[String, CritBitTree[T]](), isExternalNode, data)

  /*def contains(bitString: String): Boolean = {
  get(bitString) != None
}*/

  /*def get(bitString: String): Option[T] = {
    if (bitString.isEmpty) {
      if (isExternalNode) {
        return data
      } else {
        return None
      }
    }

    val commonPrefix = findCommonPrefix(bitString)
    if (commonPrefix.isEmpty) {
      return None
    }

    val keyVal = nodes.find(kv => kv._1.startsWith(commonPrefix)).get
    if (keyVal._1 != commonPrefix) {
      return None
    }
    keyVal._2.get(bitString.substring(commonPrefix.length))
  }*/

  def findIndex(index: Int, newString: String, existPrefix: String): Int = {
    if (index < newString.length && index < existPrefix.length && newString(index) == existPrefix(index)) {
      findIndex(index + 1, newString, existPrefix)
    }
    index
  }

  private def findCommonPrefix(bitString: String): String = {
    for (existPrefixes <- nodes.keys) {
      if (findIndex(0, bitString, existPrefixes) != 0) {
        return bitString.substring(0, findIndex(0, bitString, existPrefixes))
      }
    }

    bitString.substring(0, 0)
  }

  def findNodeWithPrefix(prefix: String): (String, CritBitTree[T]) = {
    val nodeWIthCommonPrefix = nodes.find(node => node._1.startsWith(prefix)).get
    (nodeWIthCommonPrefix._1, nodeWIthCommonPrefix._2)
  }

  def add(bitString: String, value: T): CritBitTree[T] = {
    if (bitString.length == 0)
      return new CritBitTree[T](nodes, true, Option[T](value))

    val commonPrefix = findCommonPrefix(bitString)

    if (commonPrefix.length == 0) {
      val newNode = bitString -> new CritBitTree[T](true, Option[T](value))
      return new CritBitTree[T](nodes + newNode, isExternalNode, data)
    }

    /*val nodeWIthCommonPrefix = nodes.find(node => node._1.startsWith(commonPrefix)).get
    val existPrefix = nodeWIthCommonPrefix._1
    val subtree = nodeWIthCommonPrefix._2*/
    val (subtree, existPrefix) = findNodeWithPrefix(commonPrefix)

    //добавление новой вершины
    if (existPrefix == commonPrefix) {
      val newLeaf = existPrefix -> trie.add(bitString.substring(existPrefix.length), value)
      val newNodes = nodes + newLeaf
      new CritBitTree[T](newNodes, isExternalNode, data)
    } else {
      val end = existPrefix.substring(commonPrefix.length)
      val middleVertex = new CritBitTree[T](HashMap(end -> trie), false, None)
      val newLeaf = commonPrefix -> middleVertex.add(bitString.substring(commonPrefix.length), value)

      val newNodes = (nodes - existPrefix) + newLeaf
      new CritBitTree[T](newNodes, isExternalNode, data)
    }
  }

 /* def remove(bitString: String): CritBitTree[T] = {
    if (bitString.isEmpty) {
      return new CritBitTree(nodes, false, None)
    }

    val commonPrefix = findCommonPrefix(bitString)
    if (commonPrefix.isEmpty) {
      return this
    }

    val keyVal = nodes.find(kv => kv._1.startsWith(commonPrefix)).get
    val edge = keyVal._1
    val trie = keyVal._2

    if (edge == commonPrefix) {
      val newLeaf = edge -> trie.remove(bitString.substring(edge.length))

      if (newLeaf._2.size() == 0) {
        val newNodes = nodes - edge
        val size = countWords(newNodes)
        new CritBitTree[T](newNodes, isExternalNode, size, data)
      } else {
        newLeaf._2.nodesNumber() match {
          case 1 =>
            val nextLeaf = newLeaf._2.getSingleLeaf()
            if (newLeaf._2.size() == nextLeaf._2.size()) {
              val leaf = (edge + nextLeaf._1) -> nextLeaf._2
              val newNodes = (nodes - edge) + leaf
              val size = countWords(newNodes)
              new CritBitTree[T](newNodes, isExternalNode, size, data)
            } else {
              val newNodes = nodes + newLeaf
              val size = countWords(newNodes)
              new CritBitTree[T](newNodes, isExternalNode, size, data)
            }
          case _ =>
            val newNodes = nodes + newLeaf
            val size = countWords(newNodes)
            new CritBitTree[T](newNodes, isExternalNode, size, data)
        }
      }
    } else {
      this
    }
  }*/



  def print(indent: Int = 0) {
    if (isExternalNode) println(" " * indent + "$(" + data.get + ")$")
    for (kv <- nodes) {
      println(" " * indent + kv._1)
      kv._2.print(indent + kv._1.length)
    }
  }

  /*private def nodesNumber() = nodes.size

  private def getSingleLeaf() = nodes.last*/


}

object CritBitTree {
  def apply[T](): CritBitTree[T] = {
    new CritBitTree[T](false, None)
  }
}