scala - 如何获取树状自定义对象的大小
问题描述
我试图弄清楚如何获得以这种方式定义的自定义树状数据结构的大小(“级别”数):
case class PrefixTreeImpl[K, +V](value: Option[V], prefixTree: Map[K, PrefixTree[K, V]]) extends PrefixTree[K, V]
如您所见,它实现了PrefixTree
接口(实际上是特征),其中包含一个size()
方法:
def size: Int
我正在尝试使用 foldLeft() Scala 方法来实现它,但我真的不明白它如何与这种复杂的数据结构一起工作到目前为止,我想出了这个并卡住了:
override def size: Int = {
if (prefixTree.isEmpty) 0
else
prefixTree.foldLeft(0) {(z, Map[K, PrefixTree[K, V]]()) => z + 1}
}
显然它没有编译,但我还想不出别的东西。
DS 的工作方式是:
在:scala>val tree2 = tree1.put(List("one", "two"), 12)
出去:PrefixTreeImpl(None,Map(one -> PrefixTreeImpl(None,Map(two -> PrefixTreeImpl(Some(12),Map(tree -> PrefixTreeImpl(Some(123),Map())))))))
解决方案
它可以通过以下方式递归完成:
override def size: Int = {
if(prefixTree.nonEmpty) prefixTree.values.map(_.size + 1).max else 0
}
所以接下来的测试:
val tree = PrefixTreeImpl(None ,Map("one" -> PrefixTreeImpl(None, Map("two" -> PrefixTreeImpl(Some(12),Map("tree" -> PrefixTreeImpl(Some(123), Map.empty[String, PrefixTree[String, Int]])))))))
println(tree.size)
产生结果:3
希望这可以帮助!
推荐阅读
- r - 如何获得基于两列的频率计数总和?
- java - 在 Java Card 中将整数的二进制表示转换为 ASCII
- spring-batch - Spring批量集成MessageSource
到 Joblaunch 请求 - typescript - 如何在 Typescript + angular 中检查空类对象的属性类型?
- json - 在 React-Native 中使用 ListView 数组 JSON
- r - 并非所有系列都对 ts 对象具有相同的频率
- javascript - HTML大表格滚动非常缓慢
- laravel-5.6 - 未使用 Laravel MVC PHP Storm 定义路由
- python - 置换过于靠近的地理点(Python / Shapely)
- javascript - Javascript 两个对象相交