Package scala.collection.immutable.scala.collection.immutable

package scala.collection.immutable

Classlikes

Source

final case class ::[+A](head: A, var next: List[A]) extends List[A]

Source

abstract class AbstractMap[K, +V] extends AbstractMap[K, V] with Map[K, V]

Явное создание экземпляра Map для уменьшения размера файлов классов в подклассах.

Source

abstract class AbstractSeq[+A] extends AbstractSeq[A] with Seq[A]

Явное создание экземпляра Seq для уменьшения размера файлов классов в подклассах.

Source

abstract class AbstractSet[A] extends AbstractSet[A] with Set[A]

Явное создание экземпляра Set для уменьшения размера файлов классов в подклассах.

Source

sealed abstract class ArraySeq[+A] extends AbstractSeq[A] with IndexedSeq[A] with IndexedSeqOps[A, ArraySeq, ArraySeq[A]] with StrictOptimizedSeqOps[A, ArraySeq, ArraySeq[A]] with EvidenceIterableFactoryDefaults[A, ArraySeq, ClassTag] with Serializable

Неизменяемый массив.

Поддерживает эффективную индексированную обработку и имеет небольшой размер занимаемой памяти.

Source@SerialVersionUID(3L)

object ArraySeq extends StrictOptimizedClassTagSeqFactory[ArraySeq]

Этот объект предоставляет набор операций для создания значений ArraySeq.

Source

sealed abstract class BitSet extends AbstractSet[Int] with SortedSet[Int] with SortedSetOps[Int, SortedSet, BitSet] with StrictOptimizedSortedSetOps[Int, SortedSet, BitSet] with BitSet with BitSetOps[BitSet] with Serializable

Класс для неизменяемых битовых множеств.

Битовые множества представляют собой множества неотрицательных целых чисел, которые представлены массивами переменного размера бит, упакованными в 64-битные слова. Нижняя граница размера занимаемой памяти определяется наибольшим числом, хранящимся в нём.

Source@nowarn("cat=deprecation&msg=Implementation classes of BitSet should not be accessed directly") @SerialVersionUID(3L)

object BitSet extends SpecificIterableFactory[Int, BitSet]

Этот объект предоставляет набор операций для создания значений immutable.BitSet.

Source

final class HashMap[K, +V] extends AbstractMap[K, V] with StrictOptimizedMapOps[K, V, HashMap, HashMap[K, V]] with MapFactoryDefaults[K, V, HashMap, Iterable] with DefaultSerializable

Этот класс реализует неизменяемые отображения, используя сжатое хеш-массивно-отображаемое префиксное дерево. Более подробную информацию см. в статье https://michael.steindorfer.name/publications/oopsla15.pdf.

Source@SerialVersionUID(3L)

object HashMap extends MapFactory[HashMap]

Этот объект предоставляет набор операций для создания значений immutable.HashMap.

Source

final class HashSet[A] extends AbstractSet[A] with StrictOptimizedSetOps[A, HashSet, HashSet[A]] with IterableFactoryDefaults[A, HashSet] with DefaultSerializable

Этот класс реализует неизменяемые множества, используя сжатое хеш-массивно-отображаемое префиксное дерево. Более подробную информацию см. в статье https://michael.steindorfer.name/publications/oopsla15.pdf.

Source@SerialVersionUID(3L)

object HashSet extends IterableFactory[HashSet]

Этот объект предоставляет набор операций для создания значений immutable.HashSet.

Source

trait IndexedSeq[+A] extends Seq[A] with IndexedSeq[A] with IndexedSeqOps[A, IndexedSeq, IndexedSeq[A]] with IterableFactoryDefaults[A, IndexedSeq]

Базовый трайт для неизменяемых индексированных последовательностей, которые имеют эффективные apply и length.

Source@SerialVersionUID(3L)

object IndexedSeq extends Delegate[IndexedSeq]

Source

object IndexedSeqDefaults

Source

trait IndexedSeqOps[+A, +CC[_], +C] extends SeqOps[A, CC, C] with IndexedSeqOps[A, CC, C]

Базовый трайт для неизменяемых индексированных операций Seq

Source

object IntMap

Объект-компаньон для целочисленных отображений.

Исходный код

sealed abstract class IntMap[+T] extends AbstractMap[Int, T] with StrictOptimizedMapOps[Int, T, Map, IntMap[T]] with Serializable

Специализированная неизменяемая структура карты для целочисленных ключей, основанная на Быстрых объединяемых целочисленных картах Окасаки и Гиля. По существу, это дерево, основанное на двоичных разрядах целых чисел.

Примечание: С версии 2.8 этот класс в значительной степени устарел по сравнению с HashMap.

Исходный код

trait Iterable[+A] extends Iterable[A] with IterableOps[A, Iterable, Iterable[A]] with IterableFactoryDefaults[A, Iterable]

Трейт для коллекций, которые гарантированно неизменяемы.

Исходный код@SerialVersionUID(3L)

object Iterable extends Delegate[Iterable]

Исходный код@SerialVersionUID(3L)

final class LazyList[+A] extends AbstractSeq[A] with LinearSeq[A] with LinearSeqOps[A, LazyList, LazyList[A]] with IterableFactoryDefaults[A, LazyList] with Serializable

Этот класс реализует неизменяемый связанный список. Мы называем его «ленивым», потому что он вычисляет свои элементы только тогда, когда они нужны.

Элементы кешируются; то есть значение каждого элемента вычисляется не более одного раза.

Элементы вычисляются в порядке и никогда не пропускаются. Другими словами, доступ к хвосту приводит к вычислению головы в первую очередь.

Насколько ленив LazyList? Когда у вас есть значение типа LazyList, вы еще не знаете, пустой ли список или нет. Если вы узнаете, что он не пустой, то вы также знаете, что голова была вычислена. Но хвост сам по себе является LazyList, пустой ли он или нет, может остаться не определенным.

LazyList может быть бесконечным. Например, LazyList.from(0) содержит все натуральные числа 0, 1, 2 и так далее. Для бесконечных последовательностей некоторые методы (такие как count, sum, max или min) не завершатся.

Вот пример:

import scala.math.BigInt
object Main extends App {
  val fibs: LazyList[BigInt] =
    BigInt(0) #:: BigInt(1) #:: fibs.zip(fibs.tail).map{ n => n._1 + n._2 }
  fibs.take(5).foreach(println)
}

// prints
//
// 0
// 1
// 1
// 2
// 3

Чтобы проиллюстрировать, давайте добавим некоторую информацию в определение fibs, чтобы увидеть, что происходит.

import scala.math.BigInt
object Main extends App {
  val fibs: LazyList[BigInt] =
    BigInt(0) #:: BigInt(1) #::
      fibs.zip(fibs.tail).map{ n =>
        println(s"Adding ${n._1} and ${n._2}")
        n._1 + n._2
      }
  fibs.take(5).foreach(println)
  fibs.take(6).foreach(println)
}

// prints
//
// 0
// 1
// Adding 0 and 1
// 1
// Adding 1 and 1
// 2
// Adding 1 and 2
// 3

// And then prints
//
// 0
// 1
// 1
// 2
// 3
// Adding 2 and 3
// 5

Обратите внимание, что определение fibs использует val, а не def. Кеширование LazyList требует, чтобы у нас было место для хранения информации, и val позволяет это сделать.

Дополнительные замечания о семантике LazyList:

- Хотя LazyList изменяется при доступе, это не противоречит его неизменяемости. После того, как значения помещаются в кеш, они не меняются. Значения, которые еще не помещены в кеш, все еще «существуют», просто они еще не вычислены.

- Следует проявлять осторожность при кешировании; оно может потреблять много памяти, если вы не будете осторожны. Это происходит потому, что кеширование LazyList создает структуру, очень похожую на scala.collection.immutable.List. До тех пор, пока что-то держит голову, голова держит хвост, и так далее рекурсивно. Если же ничего не держит голову (например, если мы использовали def для определения LazyList) то, как только она больше не используется напрямую, она исчезает.

- Обратите внимание, что некоторые операции, включая drop, dropWhile, flatMap или collect, могут обработать большое количество промежуточных элементов перед возвратом.

Вот еще один пример. Давайте начнем с натуральных чисел и итерируемся по ним.

// We'll start with a silly iteration
def loop(s: String, i: Int, iter: Iterator[Int]): Unit = {
  // Stop after 200,000
  if (i < 200001) {
    if (i % 50000 == 0) println(s + i)
    loop(s, iter.next(), iter)
  }
}

// Our first LazyList definition will be a val definition
val lazylist1: LazyList[Int] = {
  def loop(v: Int): LazyList[Int] = v #:: loop(v + 1)
  loop(0)
}

// Because lazylist1 is a val, everything that the iterator produces is held
// by virtue of the fact that the head of the LazyList is held in lazylist1
val it1 = lazylist1.iterator
loop("Iterator1: ", it1.next(), it1)

// We can redefine this LazyList such that all we have is the Iterator left
// and allow the LazyList to be garbage collected as required.  Using a def
// to provide the LazyList ensures that no val is holding onto the head as
// is the case with lazylist1
def lazylist2: LazyList[Int] = {
  def loop(v: Int): LazyList[Int] = v #:: loop(v + 1)
  loop(0)
}
val it2 = lazylist2.iterator
loop("Iterator2: ", it2.next(), it2)

// And, of course, we don't actually need a LazyList at all for such a simple
// problem.  There's no reason to use a LazyList if you don't actually need
// one.
val it3 = new Iterator[Int] {
  var i = -1
  def hasNext = true
  def next(): Int = { i += 1; i }
}
loop("Iterator3: ", it3.next(), it3)

- В примере fibs ранее, тот факт, что tail работает, представляет интерес. fibs имеет начальное (0, 1, LazyList(...)), поэтому tail детерминировано. Если бы мы определили fibs таким образом, что только 0 были бы конкретно известны, то действие определения tail потребовало бы оценки tail, поэтому вычисление не смогло бы продвинуться, как в этом коде:

// The first time we try to access the tail we're going to need more
// information which will require us to recurse, which will require us to
// recurse, which...
lazy val sov: LazyList[Vector[Int]] = Vector(0) #:: sov.zip(sov.tail).map { n => n._1 ++ n._2 }

Определение fibs выше создает больше объектов, чем необходимо, в зависимости от того, как вы хотите это реализовать. Следующая реализация обеспечивает более «эффективную» реализацию, так как она имеет более прямой путь к самим числам:

lazy val fib: LazyList[Int] = {
  def loop(h: Int, n: Int): LazyList[Int] = h #:: loop(n, h + n)
  loop(1, 1)
}

Голова, хвост и пуст ли список или нет, могут быть изначально неизвестны. Как только любой из них будет оценен, все они будут известны, хотя если хвост построен с помощью #:: или #:::, его содержимое все еще не оценивается. Вместо этого, оценка содержимого хвостов откладывается до тех пор, пока не будут оценены пустой статус хвоста, голова или хвост.

Отсрочка оценки, пуст ли LazyList или нет, до момента необходимости позволяет LazyList не жадно оценивать какие-либо элементы при вызове filter.

Только когда он оценивается далее (что может быть никогда!), любые элементы принудительно оцениваются.

например:

def tailWithSideEffect: LazyList[Nothing] = {
  println("getting empty LazyList")
  LazyList.empty
}

val emptyTail = tailWithSideEffect // prints "getting empty LazyList"

val suspended = 1 #:: tailWithSideEffect // doesn't print anything
val tail = suspended.tail // although the tail is evaluated, *still* nothing is yet printed
val filtered = tail.filter(_ => false) // still nothing is printed
filtered.isEmpty // prints "getting empty LazyList"

Исходный код@SerialVersionUID(3L)

object LazyList extends SeqFactory[LazyList]

Этот объект предоставляет набор операций для создания LazyList значений.

Исходный код

trait LinearSeq[+A] extends Seq[A] with LinearSeq[A] with LinearSeqOps[A, LinearSeq, LinearSeq[A]] with IterableFactoryDefaults[A, LinearSeq]

Базовый трейт для неизменяемых линейных последовательностей, которые имеют эффективные head и tail

Исходный код@SerialVersionUID(3L)

object LinearSeq extends Delegate[LinearSeq]

Исходный код

trait LinearSeqOps[+A, +CC <: (LinearSeq), +C <: LinearSeq[A] & LinearSeqOps[A, CC, C]] extends SeqOps[A, CC, C] with LinearSeqOps[A, CC, C]

Исходный код@SerialVersionUID(3L)

sealed abstract class List[+A] extends AbstractSeq[A] with LinearSeq[A] with LinearSeqOps[A, List, List[A]] with StrictOptimizedLinearSeqOps[A, List, List[A]] with StrictOptimizedSeqOps[A, List, List[A]] with IterableFactoryDefaults[A, List] with DefaultSerializable

Класс неизменяемых связанных списков, представляющих упорядоченные коллекции элементов типа A.

Этот класс поставляется с двумя реализующими case-классами scala.Nil и scala.::, которые реализуют абстрактные члены isEmpty, head и tail.

Этот класс оптимален для схем доступа LIFO (последним вошел — первым вышел), похожих на стеки. Если вам нужна другая схема доступа, например, произвольный доступ или FIFO, рассмотрите использование коллекции, более подходящей для этой цели, чем List.

Производительность

Время: List имеет O(1) вставка в начало и доступ к голове/хвосту. Большинство других операций имеют сложность O(n) от числа элементов в списке. Это включает в себя поиск элементов по индексу, length, append и reverse.

Память: List реализует совместное использование хвоста списка. Это означает, что многие операции имеют нулевую или постоянную стоимость памяти.

val mainList = List(3, 2, 1)
val with4 =    4 :: mainList  // re-uses mainList, costs one :: instance
val with42 =   42 :: mainList // also re-uses mainList, cost one :: instance
val shorter =  mainList.tail  // costs nothing as it uses the same 2::1::Nil instances as mainList

// Make a list via the companion object factory
val days = List("Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday")
// Make a list element-by-element
val when = "AM" :: "PM" :: Nil
// Pattern match
days match {
  case firstDay :: otherDays =>
    println("The first day of the week is: " + firstDay)
  case Nil =>
    println("There don't seem to be any week days.")
}

Исходный код@SerialVersionUID(3L)

объект List extends StrictOptimizedSeqFactory[List]

Этот объект предоставляет набор операций для создания значений List.

Исходный код

запечатанный класс ListMap[K, +V] extends AbstractMap[K, V] with SeqMap[K, V] with StrictOptimizedMapOps[K, V, ListMap, ListMap[K, V]] with MapFactoryDefaults[K, V, ListMap, Iterable] with DefaultSerializable

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

Элементы хранятся во внутреннем порядке обратной вставки, то есть самый новый ключ находится в начале списка. Таким образом, такие методы, как head и tail имеют сложность O(n), в то время как last и init имеют сложность O(1). Другие операции, такие как вставка или удаление элементов, также имеют сложность O(n), что делает эту коллекцию подходящей только для небольшого количества элементов.

Экземпляры ListMap представляют пустые отображения; они могут быть созданы либо путем непосредственного вызова конструктора, либо путем применения функции ListMap.empty.

Исходный код@SerialVersionUID(3L)

объект ListMap extends MapFactory[ListMap]

Этот объект предоставляет набор операций для создания значений ListMap.

Обратите внимание, что каждая вставка элемента занимает время O(n), что означает, что создание отображения ListMap с n элементами займет время O(n2). Это делает этот билдер подходящим только для небольшого количества элементов.

Исходный код

запечатанный класс ListSet[A] extends AbstractSet[A] with StrictOptimizedSetOps[A, ListSet, ListSet[A]] with IterableFactoryDefaults[A, ListSet] with DefaultSerializable

Этот класс реализует неизменяемые множества, используя структуру данных на основе списка. Итераторы и методы обхода ListSet посещают элементы в том порядке, в котором они были вставлены.

Элементы хранятся во внутреннем порядке обратной вставки, то есть самый новый элемент находится в начале списка. Таким образом, такие методы, как head и tail имеют сложность O(n), в то время как last и init имеют сложность O(1). Другие операции, такие как вставка или удаление элементов, также имеют сложность O(n), что делает эту коллекцию подходящей только для небольшого количества элементов.

Экземпляры ListSet представляют пустые множества; они могут быть созданы либо путем непосредственного вызова конструктора, либо путем применения функции ListSet.empty.

Исходный код@SerialVersionUID(3L)

объект ListSet extends IterableFactory[ListSet]

Этот объект предоставляет набор операций для создания значений ListSet.

Обратите внимание, что каждая вставка элемента занимает время O(n), что означает, что создание множества ListSet с n элементами займет время O(n2). Это делает этот билдер подходящим только для небольшого количества элементов.

Исходный код

объект LongMap

Объект-компаньон для отображений long.

Исходный код

запечатанный абстрактный класс LongMap[+T] extends AbstractMap[Long, T] with StrictOptimizedMapOps[Long, T, Map, LongMap[T]] with Serializable

Специализированная неизменяемая структура отображения для ключей long, основанная на быстрых объединяемых отображениях Long Okasaki и Gill. По сути, это trie, основанное на двоичных цифрах целых чисел.

Примечание: этот класс с версии 2.8 в значительной степени устарел по сравнению с HashMap.

Исходный код

trait Map[K, +V] extends Iterable[(K, V)] with Map[K, V] with MapOps[K, V, Map, Map[K, V]] with MapFactoryDefaults[K, V, Map, Iterable]

Базовый тип неизменяемых отображений

Исходный код@SerialVersionUID(3L)

объект Map extends MapFactory[Map]

Этот объект предоставляет набор операций для создания значений immutable.Map.

Исходный код

trait MapOps[K, +V, +CC <: (MapOps), +C <: MapOps[K, V, CC, C]] extends IterableOps[(K, V), Iterable, C] with MapOps[K, V, CC, C]

Базовый признак реализаций неизменяемых отображений

Исходный код

случайный объект Nil extends List[Nothing]

Источник@SerialVersionUID(3L)

sealed class NumericRange[T](val start: T, val end: T, val step: T, val isInclusive: Boolean)(implicit num: Integral[T]) extends AbstractSeq[T] with IndexedSeq[T] with IndexedSeqOps[T, IndexedSeq, IndexedSeq[T]] with StrictOptimizedSeqOps[T, IndexedSeq, IndexedSeq[T]] with IterableFactoryDefaults[T, IndexedSeq] with Serializable

NumericRange — это более обобщённая версия класса Range, которая работает с произвольными типами. Она должна быть снабжена реализацией Integral типа диапазона.

Фабрики для распространённых типов включают Range.BigInt, Range.Long, и Range.BigDecimal. Range.Int существует для полноты, но основанная на Int версия scala.Range должна быть более производительной.

val r1 = Range(0, 100, 1)
val veryBig = Int.MaxValue.toLong + 1
val r2 = Range.Long(veryBig, veryBig + 100, 1)
assert(r1 sameElements r2.map(_ - veryBig))

Источник

object NumericRange

Объект-компаньон для числовых диапазонов.

Источник

sealed class Queue[+A] extends AbstractSeq[A] with LinearSeq[A] with LinearSeqOps[A, Queue, Queue[A]] with StrictOptimizedLinearSeqOps[A, Queue, Queue[A]] with StrictOptimizedSeqOps[A, Queue, Queue[A]] with IterableFactoryDefaults[A, Queue] with DefaultSerializable

Queue объекты реализуют структуры данных, позволяющие добавлять и извлекать элементы в порядке очереди (FIFO).

Queue реализована как пара List списков, один из которых содержит входящие элементы, а другой — выходящие. Элементы добавляются в входящий список и удаляются из исходящего. Когда исходящий список пуст, очередь переворачивается, заменяя исходящий список на in.reverse, а входящий — на Nil.

Добавление элементов в очередь всегда имеет стоимость O(1). Удаление элементов имеет стоимость O(1), за исключением случаев, когда требуется переворот, в этом случае взимается стоимость O(n), где n — количество элементов в очереди. В таких случаях гарантируется n операций удаления со стоимостью O(1). Удаление элемента в среднем имеет сложность O(1).

Источник@SerialVersionUID(3L)

object Queue extends StrictOptimizedSeqFactory[Queue]

Этот объект предоставляет набор операций для создания значений immutable.Queue.

Источник@SerialVersionUID(3L)

sealed abstract class Range(val start: Int, val end: Int, val step: Int) extends AbstractSeq[Int] with IndexedSeq[Int] with IndexedSeqOps[Int, IndexedSeq, IndexedSeq[Int]] with StrictOptimizedSeqOps[Int, IndexedSeq, IndexedSeq[Int]] with IterableFactoryDefaults[Int, IndexedSeq] with Serializable

Класс Range представляет целые значения в диапазоне [start;end) с ненулевым шагом step. Это частный случай индексированного последовательности. Например:

val r1 = 0 until 10
val r2 = r1.start until r1.end by r1.step + 1
println(r2.length) // = 5

Диапазоны, содержащие более Int.MaxValue элементов, могут быть созданы, но эти переполненные диапазоны имеют ограниченные возможности. Любой метод, который мог бы потребовать создания коллекции длиной более Int.MaxValue элементов или запросить индексирование сверх Int.MaxValue элементов, вызовет исключение. Переполненные диапазоны можно безопасно уменьшить в размере, изменив шаг (например, by 3) или взяв/отбросив элементы. contains, equals, и доступ к концам диапазона (head, last, tail, init) также разрешены для переполненных диапазонов.

Источник

object Range

Объект-компаньон для диапазонов.

Источник

trait Seq[+A] extends Iterable[A] with Seq[A] with SeqOps[A, Seq, Seq[A]] with IterableFactoryDefaults[A, Seq]

Источник@SerialVersionUID(3L)

object Seq extends Delegate[Seq]

Этот объект предоставляет набор операций для создания значений immutable.Seq.

Источник

trait SeqMap[K, +V] extends Map[K, V] with SeqMap[K, V] with MapOps[K, V, SeqMap, SeqMap[K, V]] with MapFactoryDefaults[K, V, SeqMap, Iterable]

Общий трайт для упорядоченных неизменяемых отображений. Конкретные классы должны предоставить функциональность для абстрактных методов в SeqMap.

Обратите внимание, что при проверке на равенство SeqMap не учитывает порядок.

Источник

object SeqMap extends MapFactory[SeqMap]

Источник

trait SeqOps[+A, +CC[_], +C] extends SeqOps[A, CC, C]

Источник

trait Множество[A] extends Итерируемый[A] with Множество[A] with ОперацииНадМножествами[A, Множество, Множество[A]] with ЗначенияПоУмолчаниюДляФабрикИтерируемых[A, Множество]

Базовый трайт для неизменяемых коллекций множеств

Источник@SerialVersionUID(3L)

object Множество extends ФабрикаИтерируемых[Множество]

Этот объект предоставляет набор операций для создания immutable.Set значений.

Источник

trait ОперацииНадМножествами[A, +CC[X], +C <: ОперацииНадМножествами[A, CC, C]] extends ОперацииНадМножествами[A, CC, C]

Базовый трайт для неизменяемых операций над множествами

Источник

trait ОтсортированныйСловарь[K, +V] extends Словарь[K, V] with ОтсортированныйСловарь[K, V] with ОперацииНадОтсортированнымиСловарями[K, V, ОтсортированныйСловарь, ОтсортированныйСловарь[K, V]] with ЗначенияПоУмолчаниюДляФабрикОтсортированныхСловарией[K, V, ОтсортированныйСловарь, Итерируемый, Словарь]

Неизменяемый словарь, пары ключ-значение которого отсортированы в соответствии с scala.math.Ordering по ключам.

Разрешает выполнение запросов по диапазонам по своим ключам, и реализации должны гарантировать, что обход происходит в отсортированном порядке в соответствии с scala.math.Ordering словаря.

import scala.collection.immutable.SortedMap
// Make a SortedMap via the companion object factory
val weekdays = SortedMap(
  2 -> "Monday",
  3 -> "Tuesday",
  4 -> "Wednesday",
  5 -> "Thursday",
  6 -> "Friday"
)
// TreeMap(2 -> Monday, 3 -> Tuesday, 4 -> Wednesday, 5 -> Thursday, 6 -> Friday)
val days = weekdays ++ List(1 -> "Sunday", 7 -> "Saturday")
// TreeMap(1 -> Sunday, 2 -> Monday, 3 -> Tuesday, 4 -> Wednesday, 5 -> Thursday, 6 -> Friday, 7 -> Saturday)
val day3 = days.get(3) // Some("Tuesday")
val rangeOfDays = days.range(2, 5) // TreeMap(2 -> Monday, 3 -> Tuesday, 4 -> Wednesday)
val daysUntil2 = days.rangeUntil(2) // TreeMap(1 -> Sunday)
val daysTo2 = days.rangeTo(2) // TreeMap(1 -> Sunday, 2 -> Monday)
val daysAfter5 = days.rangeFrom(5) //  TreeMap(5 -> Thursday, 6 -> Friday, 7 -> Saturday)

Источник@SerialVersionUID(3L)

object ОтсортированныйСловарь extends Делегат[ОтсортированныйСловарь]

Источник

trait ОперацииНадОтсортированнымиСловарями[K, +V, +CC <: ([X, Y] =>> Словарь[X, Y] & ОперацииНадОтсортированнымиСловарями[X, Y, CC, _]), +C <: ОперацииНадОтсортированнымиСловарями[K, V, CC, C]] extends ОперацииНадСловарями[K, V, Словарь, C] with ОперацииНадОтсортированнымиСловарями[K, V, CC, C]

Источник

trait ОтсортированноеМножество[A] extends Множество[A] with ОтсортированноеМножество[A] with ОперацииНадОтсортированнымиМножествами[A, ОтсортированноеМножество, ОтсортированноеМножество[A]] with ЗначенияПоУмолчаниюДляФабрикОтсортированныхМножеств[A, ОтсортированноеМножество, Множество]

Базовый трайт для отсортированных множеств

Источник@SerialVersionUID(3L)

object ОтсортированноеМножество extends Делегат[ОтсортированноеМножество]

Этот объект предоставляет набор операций для создания immutable.SortedSet значений.

Источник

trait ОперацииНадОтсортированнымиМножествами[A, +CC <: (ОтсортированноеМножество), +C <: ОперацииНадОтсортированнымиМножествами[A, CC, C]] extends ОперацииНадМножествами[A, Множество, C] with ОперацииНадОтсортированнымиМножествами[A, CC, C]

Источник

trait ОптимизированныеОперацииНадСловарями[K, +V, +CC <: (ОперацииНадСловарями), +C <: ОперацииНадСловарями[K, V, CC, C]] extends ОперацииНадСловарями[K, V, CC, C] with ОптимизированныеОперацииНадСловарями[K, V, CC, C] with ОптимизированныеОперацииНадИтерируемыми[(K, V), Итерируемый, C]

Источник

trait ОптимизированныеОперацииНадПоследовательностями[+A, +CC[_], +C] extends ОперацииНадПоследовательностями[A, CC, C] with ОптимизированныеОперацииНадПоследовательностями[A, CC, C] with ОптимизированныеОперацииНадИтерируемыми[A, CC, C]

Трайт, переопределяющий операции для использования строгих билдеров.

Источник

trait ОптимизированныеОперацииНадМножествами[A, +CC[X], +C <: ОперацииНадМножествами[A, CC, C]] extends ОперацииНадМножествами[A, CC, C] with ОптимизированныеОперацииНадМножествами[A, CC, C] with ОптимизированныеОперацииНадИтерируемыми[A, CC, C]

Источник

trait ОптимизированныеОперацииНадОтсортированнымиСловарями[K, +V, +CC <: ([X, Y] =>> Словарь[X, Y] & ОперацииНадОтсортированнымиСловарями[X, Y, CC, _]), +C <: ОперацииНадОтсортированнымиСловарями[K, V, CC, C]] extends ОперацииНадОтсортированнымиСловарями[K, V, CC, C] with ОптимизированныеОперацииНадОтсортированнымиСловарями[K, V, CC, C] with ОптимизированныеОперацииНадСловарями[K, V, Словарь, C]

Источник

trait ОптимизированныеОперацииНадОтсортированнымиМножествами[A, +CC <: (ОтсортированноеМножество), +C <: ОперацииНадОтсортированнымиМножествами[A, CC, C]] extends ОперацииНадОтсортированнымиМножествами[A, CC, C] with ОптимизированныеОперацииНадОтсортированнымиМножествами[A, CC, C] with ОптимизированныеОперацииНадМножествами[A, Множество, C]

Источник

final class ДеревоСловарь[K, +V] extends АбстрактныйСловарь[K, V] with ОтсортированныйСловарь[K, V] with ОптимизированныеОперацииНадОтсортированнымиСловарями[K, V, ДеревоСловарь, ДеревоСловарь[K, V]] with ЗначенияПоУмолчаниюДляФабрикОтсортированныхСловарией[K, V, ДеревоСловарь, Итерируемый, Словарь] with ПоУмолчаниюСериализуемый

Неизменяемый отсортированный словарь, значения которого хранятся в красно-черном дереве.

Этот класс оптимален, когда будут выполняться запросы по диапазонам или когда требуется обход в порядке упорядочения. Если вам нужны только поиски по ключу и неважно, в каком порядке ключи-значения обходятся, рассмотрите использование * scala.collection.immutable.HashMap, который, как правило, имеет лучшую производительность. Если вам нужна последовательность вставки, рассмотрите использование * scala.collection.immutable.SeqMap, которому не нужно предоставлять упорядочивание.

import scala.collection.immutable.TreeMap
// Make a TreeMap via the companion object factory
val weekdays = TreeMap(
  2 -> "Monday",
  3 -> "Tuesday",
  4 -> "Wednesday",
  5 -> "Thursday",
  6 -> "Friday"
)
// TreeMap(2 -> Monday, 3 -> Tuesday, 4 -> Wednesday, 5 -> Thursday, 6 -> Friday)
val days = weekdays ++ List(1 -> "Sunday", 7 -> "Saturday")
// TreeMap(1 -> Sunday, 2 -> Monday, 3 -> Tuesday, 4 -> Wednesday, 5 -> Thursday, 6 -> Friday, 7 -> Saturday)
val day3 = days.get(3) // Some("Tuesday")
val rangeOfDays = days.range(2, 5) // TreeMap(2 -> Monday, 3 -> Tuesday, 4 -> Wednesday)
val daysUntil2 = days.rangeUntil(2) // TreeMap(1 -> Sunday)
val daysTo2 = days.rangeTo(2) // TreeMap(1 -> Sunday, 2 -> Monday)
val daysAfter5 = days.rangeFrom(5) //  TreeMap(5 -> Thursday, 6 -> Friday, 7 -> Saturday)

Source@SerialVersionUID(3L)

object TreeMap extends SortedMapFactory[TreeMap]

Этот объект предоставляет набор операций для создания неизменяемых значений TreeMap.

Source

final class TreeSeqMap[K, +V] extends AbstractMap[K, V] with SeqMap[K, V] with MapOps[K, V, TreeSeqMap, TreeSeqMap[K, V]] with StrictOptimizedIterableOps[(K, V), Iterable, TreeSeqMap[K, V]] with StrictOptimizedMapOps[K, V, TreeSeqMap, TreeSeqMap[K, V]] with MapFactoryDefaults[K, V, TreeSeqMap, Iterable]

Этот класс реализует неизменяемый массив, сохраняющий порядок, используя хеш-таблицу для сопоставления ключ-значение для обеспечения эффективного поиска и дерево для упорядочения ключей для обеспечения эффективного прохода по порядку вставки/изменения и деструктуризации.

По умолчанию используется порядок вставки (TreeSeqMap.OrderBy.Insertion), но вместо этого можно использовать порядок изменения (TreeSeqMap.OrderBy.Modification), если это указано при создании.

Метод orderingBy(orderBy: TreeSeqMap.OrderBy): TreeSeqMap[K, V] может быть использован для переключения на указанный порядок для возвращаемого массива.

Ключ можно вручную обновить (т. е. поместить в конец) с помощью метода refresh(key: K): TreeSeqMap[K, V] (независимо от используемого порядка).

Внутренне счётчик порядковых номеров увеличивается при каждой вставке/изменении, а затем текущий порядковый номер используется в качестве ключа в дереве. После 232 вставок/изменений весь массив копируется (тем самым сбрасывая счётчик порядковых номеров).

Source

object TreeSeqMap extends MapFactory[TreeSeqMap]

Source

final class TreeSet[A] extends AbstractSet[A] with SortedSet[A] with SortedSetOps[A, TreeSet, TreeSet[A]] with StrictOptimizedSortedSetOps[A, TreeSet, TreeSet[A]] with SortedSetFactoryDefaults[A, TreeSet, Set] with DefaultSerializable

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

Source@SerialVersionUID(3L)

object TreeSet extends SortedIterableFactory[TreeSet]

Этот объект предоставляет набор операций для создания immutable.TreeSet значений.

Source@SerialVersionUID(3L)

object Vector extends StrictOptimizedSeqFactory[Vector]

Этот объект предоставляет набор операций для создания Vector значений.

Source

sealed abstract class Vector[+A] extends AbstractSeq[A] with IndexedSeq[A] with IndexedSeqOps[A, Vector, Vector[A]] with StrictOptimizedSeqOps[A, Vector, Vector[A]] with IterableFactoryDefaults[A, Vector] with DefaultSerializable

Вектор — это универсальная неизменяемая структура данных. Она обеспечивает произвольный доступ и обновления за время O(log n), а также очень быстрые добавление/вставку в начало/конец/хвост/начало (амортизированное O(1), в худшем случае O(log n)). Поскольку векторы обеспечивают хороший баланс между быстрым произвольным выбором и быстрым произвольным функциональным обновлением, они в настоящее время являются реализацией по умолчанию неизменяемых индексированных последовательностей.

Векторы реализуются с помощью сбалансированных по радиксу пальцевых деревьев ширины 32. Для каждого уровня (от 0 до 6, где 0 — пустой вектор, а 6 — дерево с максимальной шириной 64 на верхнем уровне) существует отдельный подкласс.

Сбалансированность дерева: - Размер первого измерения массива может быть меньше WIDTH - В массиве data (центральный) первое измерение может иметь длину до WIDTH-2, в prefix1 и suffix1 до WIDTH, а в других prefix и suffix массивах до WIDTH-1 - prefix1 и suffix1 никогда не пустые - Балансировка не пересекает основной массив данных (т. е. добавление в начало никогда не касается суффикса, а добавление в конец никогда не касается префикса). Уровень увеличивается/уменьшается, когда затронутая сторона плюс основной массив уже заполнены/пусты - Все массивы выровнены слева и усечены

Помимо разделов данных (prefix1, prefix2, ..., dataN, ..., suffix2, suffix1) мы храним текущую сумму элементов после каждого префикса для более эффективного индексирования без необходимости привязываться ко всем префиксным массивам.

Source

final class VectorBuilder[A] extends ReusableBuilder[A, Vector[A]]

Source

final class VectorMap[K, +V] extends AbstractMap[K, V] with SeqMap[K, V] with StrictOptimizedMapOps[K, V, VectorMap, VectorMap[K, V]] with MapFactoryDefaults[K, V, VectorMap, Iterable]

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

В отличие от ListMap, VectorMap имеет амортизированный эффективно постоянный поиск в ущерб использованию дополнительной памяти и, как правило, более низкой производительности для других операций

Source

object VectorMap extends MapFactory[VectorMap]

Source@SerialVersionUID(3L)

final class WrappedString(self: String) extends AbstractSeq[Char] with IndexedSeq[Char] with IndexedSeqOps[Char, IndexedSeq, WrappedString] with Serializable

Этот класс служит оболочкой, дополняющей String всеми операциями, доступными для индексированных последовательностей.

Разница между этим классом и StringOps заключается в том, что вызов методов преобразования, таких как filter и map, вернёт объект типа WrappedString, а не String.

Исходный код@SerialVersionUID(3L)

объект WrappedString расширяет SpecificIterableFactory[Char, WrappedString]

Объект-компаньон для обернутых строк.

Типы

Исходный код

тип StringOps = StringOps

Исходный код

тип StringView = StringView

Конкретные поля

Исходный код

переменная StringOps: StringOps.type

Исходный код

переменная StringView: StringView.type