Неизменяемость Scala Реализация карты, которая сохраняет порядок вставки

Ответ 1

ListMap реализует неизменяемую карту с использованием структуры данных на основе списка и, таким образом, сохраняет порядок вставки.

scala> import collection.immutable.ListMap
import collection.immutable.ListMap

scala> ListMap(1 -> 2) + (3 -> 4)
res31: scala.collection.immutable.ListMap[Int,Int] = Map(1 -> 2, 3 -> 4)

scala> res31 + (6 -> 9)
res32: scala.collection.immutable.ListMap[Int,Int] = Map(1 -> 2, 3 -> 4, 6 -> 9)

Следующий способ расширения - Seq#toListMap может быть весьма полезен при работе с ListMap s.

scala> import scalaz._, Scalaz._, Liskov._
import scalaz._
import Scalaz._
import Liskov._

scala> :paste
// Entering paste mode (ctrl-D to finish)

implicit def seqW[A](xs: Seq[A]) = new SeqW(xs)
class SeqW[A](xs: Seq[A]) {
  def toListMap[B, C](implicit ev: A <~< (B, C)): ListMap[B, C] = {
    ListMap(co[Seq, A, (B, C)](ev)(xs) : _*)  
  }
}


// Exiting paste mode, now interpreting.

seqW: [A](xs: Seq[A])SeqW[A]
defined class SeqW

scala> Seq((2, 4), (11, 89)).toListMap
res33: scala.collection.immutable.ListMap[Int,Int] = Map(2 -> 4, 11 -> 89)

Ответ 2

Пока ListMap сохранит порядок вставки, он не очень эффективен - например, время поиска является линейным. Я предлагаю вам создать новый класс коллекции, который обертывает как immutable.HashMap, так и immutable.TreeMap. Неизменяемую карту следует параметризовать как immutable.HashMap[Key, (Value, Long)], где Long в кортеже дает вам указатель на соответствующую запись в TreeMap[Long, Key]. Затем вы сохраняете счетчик входа сбоку. Эта древовидная карта будет сортировать записи в соответствии с порядком вставки.

Вы внедряете вставку и поиск простым способом - увеличиваете счетчик, вставляете в хэш-карту и вставляете в пару счётчика в treemap. Вы используете хэш-карту для поиска.

Вы реализуете итерацию с помощью карты деревьев.

Чтобы реализовать удаление, вам нужно удалить пару ключ-значение из хэш-карты и использовать индекс из кортежа, чтобы удалить соответствующую запись из карты дерева.