18

キーの範囲を値にマップできるデータ構造で述べたのとほぼ同じ質問がありますが、Scala の場合です。

つまり、何らかの値v[i]にマップされる、重複しない 1D 範囲[a[i], b[i])の変更可能なシステムが必要です。この種の仕事を行うための標準的な基礎となるデータ構造は、赤黒木です。

私がしたい操作は、できればすべて O(log n) の複雑さを持つ必要があります。

  • その中の任意のポイントを指定して、特定の範囲 (開始、終了、保存された値) またはその欠如を照会して取得します
  • この構造に新しい範囲を挿入します
  • 構造から範囲を削除する

したがって、これまでのところ、次の亜種が見られると思いますが、それらにはすべて短所があります。

  • Java の TreeMap の上に独自のコンテナーを展開する- 迅速で汚れていますが、適切なメンテナンスが行われていないため、長期的にはおそらく問題があります
  • Guava のRangeMapを使用- 可能ですが、Scala コレクションの世界ではかなり厄介です
  • Scala の赤黒ツリーの実装を使用して独自のものを作成しようとしますが、Scala の TreeMapは不変のみであり、Java の TreeMap などの単純なルックアップ メソッドを欠いていることを考えると、それはかなり難しいと思います。floorEntry

ここで何か不足していますか？基本的な Scala コレクションを拡張する Scala 中心の API を使用して、Guava のようによく管理されたコレクション拡張ライブラリはありますか?

強く関連する質問:

4

1 に答える 1