Получить родительский узел верхнего уровня для любого узла - PullRequest
Новая
       2

Получить родительский узел верхнего уровня для любого узла

0 голосов
/ 06 марта 2020

Учитывая формат в конце вопроса, как лучше всего получить имя верхнего уровня для данного элемента? Имена верхнего уровня - это имена с parentId = 1. 

def getTopLevel(name: String): String = {
    // Environment(150) -> Environment(150) - since its parentId is 1
    // Assassination -> Security - since Assassination(12) -> Terrorism(10) -> Security(2)
}

Вот мой текущий подход, но есть ли что-то лучше?

unmapped = Categories.size

L oop через этот список до тех пор, пока все еще не будут отображены элементы.
- построить карту (Int, String) для верхних уровней.
- построить карту (Int, Int) - которая сопоставляет идентификатор с идентификатором верхнего уровня.
- отслеживать несопоставленные элементы

при выходе из l oop я могу использовать обе карты, чтобы выполнить работу. 

[
    {
        "name": "Destination Overview",
        "id": 1,
        "parentId": null
    },
    {
        "name": "Environment",
        "id": 150,
        "parentId": 1
    },
    {
        "name": "Security",
        "id": 2,
        "parentId": 1
    },
    {
        "name": "Armed Conflict",
        "id": 10223,
        "parentId": 2
    },
    {
        "name": "Civil Unrest",
        "id": 21,
        "parentId": 2
    },
    {
        "name": "Terrorism",
        "id": 10,
        "parentId": 2
    },
    {
        "name": "Assassination",
        "id": 12,
        "parentId": 10
    }
]

1 Ответ

0 голосов
/ 06 марта 2020

На самом деле это два вопроса.

  1. Разбор Json в коллекцию Scala и
  2. Использование этой коллекции для отслеживания элементов обратно к верхнему родительскому элементу

Для первого вопроса вы можете использовать play- json. Вторая часть может быть обработана хвостовой рекурсивной функцией. Вот полная программа, которая решает обе проблемы: 

import play.api.libs.json.{Json, Reads}

case class Node(name: String, id: Int, parentId: Option[Int])
object JsonParentFinder {
  def main(args: Array[String]): Unit = {
    val s =
      """
        |[
        |    {
        |        "name": "Destination Overview",
        |        "id": 1,
        |        "parentId": null
        |    },
        |    {
        |        "name": "Environment",
        |        "id": 150,
        |        "parentId": 1
        |    },
        // rest of the json
        |]
        |""".stripMargin

    implicit val NodeReads : Reads[Node] =Json.reads[Node]
    val r = Json.parse(s).as[Seq[Node]]
      .map(x => x.id -> x).toMap

    println(getTopLevelNode(150, r))
    println(getTopLevelNode(12, r))
  }

  def getTopLevelNode(itemId : Int, nodes: Map[Int, Node], path : List[Node] = List.empty[Node]) : List[Node] = {
    if(nodes(itemId).id == 1)
      nodes(itemId) +: path  
    else
      getTopLevelNode(nodes(nodes(itemId).parentId.get).id, nodes, nodes(itemId) +: path)
  }
}

Вывод будет: 

List(Node(Destination Overview,1,None), Node(Environment,150,Some(1)))
List(Node(Destination Overview,1,None), Node(Security,2,Some(1)), Node(Terrorism,10,Some(2)), Node(Assassination,12,Some(10)))

Несколько замечаний:

  • Я не реализовал комплексный логи обработки ошибок c. Неявное предположение состоит в том, что единственным элементом с parentId==None является узел root. nodes(itemId).parentId.get может привести к неудаче.
  • Кроме того, при создании карты предполагается, что все элементы имеют уникальные идентификаторы.
  • Другое предположение состоит в том, что все узлы в конечном итоге имеют путь к узлу root. Если это не так, это не удастся. Но исправить эти случаи не составит труда, добавив больше условий остановки.
  • Я добавляю элементы в список аккумуляторов (здесь они называются path), потому что операция prepend для списков Scala занимает постоянное время. Вы можете просто reverse получить итоговый список или использовать другую структуру данных, например Vector, для эффективного построения пути.
...