Уникальная последовательность Scala

Question

В Scala (2.10) мне нужна неизменная коллекция SeqLike (поддерживающая индексация), которая предлагает пользователю интерфейс SetLike и не позволит дублировать элементы. В идеале это будет реализовывать как SetLike, так и SeqLike, но это невозможно, поэтому я должен выбрать один. Моя первая мысль была следующим образом:

sealed class IndexableSet[A] (private val values : Seq[A]) 
    extends Set[A] 
    with SetLike[A,IndexableSet[A]] 
{ 
    override def empty : IndexableSet[A] = new IndexableSet[A](Seq[A]()) 

    def + (elem : A) : IndexableSet[A] = values.contains(elem) match 
    { 
     case true => this 
     case false => new IndexableSet[A](values :+ elem) 
    } 

    def - (elem : A) : IndexableSet[A] = values.contains(elem) 
    { 
     case true => new IndexableSet[A](values.filter(_ != elem)) 
     case false => this 
    } 

    def iterator = values.iterator 

    def contains(elem : A) = values.contains(elem) 

    def apply(index : Int) = values(index) 

    def length : Int = values.size 

    def contents : Seq[A] = values 
} 

Это подвергает подходящий интерфейс, но не sortability (нет SortBy или сортируются)

Я задаюсь вопросом, поэтому, следует ли изменить свою реализацию на что-то, которое реализует Seq и SeqLike вместо этого, и фальсифицирует интерфейс Set:

sealed class UniqueSeq[A] private (private val values : IndexedSeq[A]) 
    extends SeqLike[A,UniqueSeq[A]] 
    with Seq[A] 
    with GenericTraversableTemplate[A,UniqueSeq] 
{ 
    def apply(idx : Int) : A = values(idx) 

    def iterator = values.iterator 

    def length = values.length 

    override def companion: GenericCompanion[UniqueSeq] = new GenericCompanion[UniqueSeq]() 
    { 
     def newBuilder[A]: Builder[A, UniqueSeq[A]] = new Builder[A, UniqueSeq[A]] 
     { 
      val elems = new ArrayBuffer[A]() 
      def +=(a:A) = { elems += a; this } 
      def clear() { elems.clear } 
      def result(): UniqueSeq[A] = new UniqueSeq[A](elems) 
     } 
    } 

    def + (elem : A) : UniqueSeq[A] = values.contains(elem) match 
    { 
     case true => this 
     case false => new UniqueSeq[A](values :+ elem) 
    } 

    def - (elem : A) : UniqueSeq[A] = values.contains(elem) match 
    { 
     case true => new UniqueSeq[A](values.filter(_ != elem)) 
     case false => this 
    } 
} 

я не уверен, что лучше - или есть ли другой способ. Я знаю, что есть такие вещи, как TreeSet, но свойство SortedSet не дает критической индексируемости.

Так вопросы:

1. Есть явный победитель между этими двумя реализациями?
2. Есть ли другой способ, который лучше, в стандартных коллекциях?

Answer 1

Я бы создал SeqLike при поддержке Seq. Переопределите любые функции, которые добавляют элементы для добавления элемента в базовый Seq, а затем вызов distinct для устранения дубликатов.

Answer 2

Я предпочитаю второе решение, возможно, модифицированный для поддержания одновременно Set и Seq внутренне:

sealed class UniqueSeq[A] private (values : IndexedSeq[A], valueSet : Set[A]) 
    extends SeqLike[A,UniqueSeq[A]] 
    with Seq[A] 
    with GenericTraversableTemplate[A,UniqueSeq] 
{ 
    def apply(idx : Int) : A = values(idx) 

    def iterator = values.iterator 

    def length = values.length 

    override def companion: GenericCompanion[UniqueSeq] = new GenericCompanion[UniqueSeq]() 
    { 
     def newBuilder[A]: Builder[A, UniqueSeq[A]] = new Builder[A, UniqueSeq[A]] 
     { 
      val elems = new ArrayBuffer[A]() 
      def +=(a:A) = { elems += a; this } 
      def clear() { elems.clear } 
      def result(): UniqueSeq[A] = new UniqueSeq[A](elems) 
     } 
    } 

    def + (elem : A) : UniqueSeq[A] = valueSet.contains(elem) match 
    { 
     case true => this 
     case false => new UniqueSeq[A](values :+ elem, valueSet + elem) 
    } 

    def - (elem : A) : UniqueSeq[A] = valueSet.contains(elem) match 
    { 
     case true => new UniqueSeq[A](values.filter(_ != elem), valueSet - elem) 
     case false => this 
    } 
} 

Answer 3

Следующий код работает в моем приложении. Он смешивает свой код с кодом из этого вопроса: Create a custom scala collection where map defaults to returning the custom collection?

class Unique[A] private (list: Vector[A], set: Set[A]) extends Traversable[A] 
    with TraversableLike[A, Unique[A]] 
    with GenericTraversableTemplate[A, Unique] 
{ 
    def apply(index: Int): A = list(index) 
    override def companion: GenericCompanion[Unique] = Unique 
    def foreach[U](f: A => U) { list foreach f } 
    override def seq = list 

    def +(elem: A): Unique[A] = { 
     if (set.contains(elem)) this 
     else new Unique(list :+ elem, set + elem) 
    } 

    def -(elem: A): Unique[A] = { 
     if (set.contains(elem)) new Unique(list.filter(_ != elem), set - elem) 
     else this 
    } 

    def --(elems: Traversable[A]): Unique[A] = { 
     val set = elems.toSet 
     val values2 = list.filterNot(set.contains) 
     new Unique(values2, values2.toSet) 
    } 

    def ++(elems: Traversable[A]): Unique[A] = { 
     val list2 = elems.filterNot(set.contains) 
     val values2 = list ++ list2 
     new Unique(values2, values2.toSet) 
    } 

    def contains(elem: A): Boolean = set.contains(elem) 

    def zipWithIndex: Traversable[(A, Int)] = list.zipWithIndex 
} 

object Unique extends TraversableFactory[Unique] { 
    def newBuilder[A] = new UniqueBuilder[A] 

    implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, Unique[A]] = { 
     new CanBuildFrom[Coll, A, Unique[A]] { 
      def apply(): Builder[A, Unique[A]] = new UniqueBuilder() 
      def apply(from: Coll): Builder[A, Unique[A]] = apply() 
     } 
    } 

    class UniqueBuilder[A] extends Builder[A, Unique[A]] { 
     private val list = Vector.newBuilder[A] 
     private val set = new HashSet[A]() 

     def += (elem: A): this.type = { 
      if (!set.contains(elem)) { 
       list += elem 
       set += elem 
      } 
      this 
     } 

     def clear() { 
      list.clear() 
      set.clear() 
     } 

     def result(): Unique[A] = new Unique(list.result, set.toSet) 
    } 
}