Пакет scala.collection.mutable

Этот класс реализует изменяемые отображения с ключами AnyRef, основанные на хэш-таблице с открытым адресованием.

Основные операции отображения по отдельным записям, включая contains и get, обычно значительно быстрее с AnyRefMap по сравнению с HashMap. Обратите внимание, что числа и символы не обрабатываются специально в AnyRefMap; используются только обычные equals и hashCode в сравнениях.

Методы, которые обходятся по отображению или перегенерируют его, включая foreach и map, в общем случае не быстрее, чем с HashMap. Однако методы foreachKey, foreachValue, mapValuesNow, и transformValues быстрее альтернативных способов достижения той же функциональности.

Отображения с открытым адресованием могут стать менее эффективными при поиске после многократного добавления/удаления элементов. Хотя AnyRefMap делает попытку оставаться эффективными независимо, вызов repack для отображения, в котором больше не будут удаляться элементы, но который будет активно использоваться, может сэкономить как время, так и хранилище.

Это отображение не предназначено для хранения более 2²⁹ записей (приблизительно 500 миллионов). Максимальная емкость — 2³⁰, но производительность будет резко ухудшаться по мере приближения к 2³⁰.

Реализация класса Buffer с использованием массива для внутреннего представления объединённой последовательности. Добавление, обновление и произвольный доступ занимают постоянное время (амортизированное время). Вставка в начало и удаление занимают время, линейно зависящее от размера буфера.

Класс-строитель для массивов.

Общие надклассы ArrayOps и WrappedArray, факторизующие метод deep для массивов и обернутых массивов, и служащие маркером для обёрток массивов.

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

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

Класс для полиморфных массивов элементов, который внутренне представлен массивом объектов. Это означает, что элементы примитивных типов упаковываются.

Простой класс стека, реализованный с помощью массива. Должен быть значительно быстрее стандартного мутабельного стека.

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

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

Буферы используются для создания последовательностей элементов постепенно, путем добавления, вставки или удаления новых элементов. Также можно получать доступ и изменять элементы в произвольном порядке с помощью индекса элемента в текущей последовательности.

Шаблонный трайт для буферов типа Buffer[A].
Буферы используются для создания последовательностей элементов постепенно, путем добавления, вставки или удаления новых элементов. Также можно получать доступ и изменять элементы в произвольном порядке с помощью индекса элемента в текущей последовательности.

Базовый трайт всех билдеров. Билдер позволяет построить коллекцию постепенно, добавляя элементы в билдер с помощью +=, а затем преобразуя в необходимый тип коллекции с помощью result.
Нельзя предполагать, что один Builder может построить более одного экземпляра желаемой коллекции. Отдельные подклассы могут позволять такое поведение. В противном случае result должен рассматриваться как терминальная операция: после ее вызова к билдеру больше не следует обращаться с другими методами. Разработайте трайт collection.mutable.ReusableBuilder вместо Builder для билдеров, которые можно повторно использовать для создания нескольких экземпляров.

Тракт для клонируемых коллекций.

Класс, используемый внутри для модели по умолчанию для карт.

Реализующий класс, поддерживающий HashSet.

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

Канонический билдер для коллекций, которые могут расти, т.е. поддерживают эффективный метод +=, который добавляет элемент в коллекцию.

GrowableBuilders могут производить только один экземпляр коллекции, которую они увеличивают.

Класс, используемый внутри.

Этот класс реализует изменяемые карты с помощью хеш-таблицы.

Этот класс реализует изменяемые множества с помощью хеш-таблицы.

Этот класс можно использовать для построения структур данных, основанных на хеш-таблицах. Класс HashTable[A] реализует хеш-таблицу, которая сопоставляет ключи типа A со значениями полностью абстрактного типа члена Entry. Классы, использующие HashTable, должны предоставить реализацию для Entry.

В основном существуют два параметра, которые влияют на производительность хеш-таблицы: начальный размер и коэффициент заполнения. Размер относится к количеству ведер в хеш-таблице, а коэффициент заполнения — это мера того, насколько полной может стать хеш-таблица, прежде чем ее размер будет автоматически удвоен. Оба параметра можно изменить, переопределив соответствующие значения в классе HashTable.

Объекты History[A, B] могут подписываться на события типа A, опубликованные объектом типа B . Объект-подписчик истории записывает все опубликованные события до максимального числа maxHistory событий.

Подкласс scala.collection.IndexedSeq, представляющий изменяемые последовательности.

Он объявляет метод update, который позволяет обновлять элемент по определенному индексу в последовательности.

Этот трайт просто реализует iterator в терминах apply и length. Однако см. IndexedSeqOptimized для реализации трайта, который переопределяет операции, чтобы сделать их более быстрыми при предположении о быстром произвольном доступе с apply.

Подкласс scala.collection.IndexedSeq, представляющий изменяемые последовательности.

Нестрогий вид изменяемой IndexedSeq.

Вид — это ленивая версия какой-либо коллекции. Трансформаторы коллекций, такие как map или filter или ++, не проходят по элементам при применении к виду. Вместо этого они создают новый вид, который просто записывает тот факт, что операция должна быть применена. Элементы коллекции и операции со взглядом обращаются к ним, когда нужен результат, отличный от взгляда, или когда вызывается метод force для вида. Некоторые из операций этого класса снова дадут изменяемую индексированную последовательность, другие дадут просто индексированную последовательность типа collection.IndexedSeq . Поскольку это листовой класс, нет связанного класса Like.

Базовый тракт для итерируемых коллекций, которые могут быть изменены.

Это базовый тракт для всех изменяемых коллекций Scala, которые определяют метод iterator, чтобы последовательно перебирать элементы коллекции. Реализации этого тракта должны предоставить конкретный метод с сигнатурой:

def iterator: Iterator[A]

Они также должны предоставить метод newBuilder, который создаёт билдер для коллекций того же типа.

Этот тракт реализует метод Iterable's foreach перебирая все элементы с помощью iterator. Подклассы должны повторно реализовать foreach, если возможно, более эффективно.

Этот тракт добавляет методы iterator, sameElements, takeRight, dropRight к методам, унаследованным от тракта `Traversable`.

Примечание: Этот тракт заменяет каждый метод, использующий break в TraversableLike, на версию с итератором.

Билдер, который создаёт результат лениво. Итераторы или итерируемые объекты, которые добавляются в этот билдер с помощью ++=, не оцениваются до вызова result.

Этот билдер может быть повторно использован.

Подтракт collection.LinearSeq, который представляет последовательности, которые можно изменить.

Линейные последовательности имеют достаточно эффективные методы head, tail и isEmpty. Если эти методы обеспечивают самый быстрый способ обхода коллекции, то коллекция Coll, которая расширяет этот тракт, также должна расширять LinearSeqOptimized[A, Coll[A]].

Класс для записи связанного хеш-карты, используемый внутри.

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

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

Реализация буфера, поддерживаемого списком. Она обеспечивает постоянное время добавления в начало и конец. Большинство других операций линейные.

Простой изменяемый массив, основанный на списке, поэтому он сохраняет порядок вставки.

Этот класс реализует изменяемые массивы с ключами типа Long, основанными на хеш-таблице с открытым адресованием.

Основные операции над отдельными элементами массива, включая contains и get, как правило, существенно быстрее с LongMap по сравнению с HashMap. Методы, действующие над всем массивом, включая foreach и map, как правило, не ожидаются быстрее, чем с общим массивом, за исключением тех, которые используют особенности внутренней структуры массива: foreachKey, foreachValue, mapValuesNow, и transformValues.

Массивы с открытым адресованием могут стать менее эффективными при поиске после многократного добавления/удаления элементов. Хотя LongMap делает все возможное, чтобы оставаться эффективным независимо от этого, вызов repack для массива, из которого больше не будут удаляться элементы, но который будет активно использоваться, может сэкономить как время, так и объем памяти.

Этот массив не предназначен для хранения более 2²⁹ элементов (приблизительно 500 миллионов). Максимальная емкость составляет 2³⁰, но производительность быстро ухудшается, когда 2³⁰ приближается.

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

Примечание к реализации: Этот тракт предоставляет большинство операций с изменяемым массивом независимо от его представления. Обычно он наследуется конкретными реализациями массивов.

Для реализации конкретного изменяемого массива необходимо предоставить реализации следующих методов:

def get(key: K): Option[V]
def iterator: Iterator[(K, V)]
def += (kv: (K, V)): This
def -= (key: K): This

Если вы хотите, чтобы методы, такие как take, drop, filter, также возвращали тот же вид массива, вы также должны переопределить:

def empty: This

Также целесообразно переопределить методы foreach и size для повышения эффективности.

Канонический билдер для неизменяемых карт, работающий с методом карты + для добавления новых элементов. Коллекции строятся из их empty элемента с помощью этого + метода.

Шаблонный интерфейс для изменяемых карт.

Примечание об реализации: Этот интерфейс предоставляет большинство операций изменяемой Map независимо от её представления. Он обычно наследуется конкретными реализациями карт.

Для реализации конкретной изменяемой карты, необходимо предоставить реализации следующих методов:

def get(key: K): Option[V]
def iterator: Iterator[(K, V)]
def += (kv: (K, V)): This
def -= (key: K): This

Если вы хотите, чтобы методы, такие как take, drop, filter также возвращали тот же тип карты, вы должны также переопределить:

def empty: This

Также рекомендуется переопределить методы foreach и size для повышения эффективности.

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

Этот класс обычно используется как миксин. Он превращает карты, которые отображают A в объекты Set[B], в многозначные карты, которые отображают A в объекты B.

Этот класс используется внутри для представления изменяемых списков. Он является основой для реализации класса Queue.

Изменяемый хеш-мап, основанный на схеме открытого хеширования. Точная схема не определена, но она должна приложить разумные усилия, чтобы гарантировать, что вставка с последовательными кодами хеша не подвергается ненужной штрафам. В частности, сопоставления последовательных целочисленных ключей должны работать без значительной потери производительности.

Этот класс реализует очереди с приоритетами, используя кучу. Для определения приоритета элементов типа A должно быть доступно неявное Ordering[A] при создании.

Если несколько элементов имеют одинаковый приоритет в порядке сортировки этой PriorityQueue, никакие гарантии не даются относительно порядка, в котором элементы возвращаются методами dequeue или dequeueAll. В частности, это означает, что этот класс не гарантирует поведение "первым вошел - первым вышел", которое может быть неправильно выведено из части "очередь" в имени этого класса.

Только методы dequeue и dequeueAll будут возвращать элементы в порядке приоритета (при удалении элементов из кучи). Стандартные методы коллекций, включая drop, iterator, и toString, будут удалять или проходить по куче в порядке, который кажется наиболее удобным.

Следовательно, вывод PriorityQueue не покажет порядок приоритетов элементов, хотя элемент с наивысшим приоритетом будет выведен первым. Чтобы вывести элементы в порядке, необходимо дублировать PriorityQueue (например, используя clone) и затем декьюить их:

Объекты Publisher[A,This] публикуют события типа A всем зарегистрированным подписчикам. При подписке подписчик может указать фильтр, который может использоваться для ограничения количества отправляемых подписчику событий. Подписчики могут приостановить свою подписку или возобновить приостановленную подписку. Класс Publisher обычно используется как миксин. Абстрактный тип Pub моделирует тип самого издателя.

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

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

ReusableBuilder — это маркерный трейт, указывающий, что Builder можно повторно использовать для построения более чем одной копии коллекции. В частности, вызов result за которым следует clear создаст коллекцию и сбросит состояние билдера, чтобы начать построение новой коллекции того же типа.

Подклассы должны реализовать это поведение и документировать любое другое поведение, отличающееся от стандартного использования ReusableBuilder (например, операции, которые определены после вызова result, или возможность получения различных снимков создаваемой коллекции).

Обратимая история — это History объект, поддерживающий операцию отмены. Переменная типа Evt ссылается на тип опубликованных событий, Pub обозначает тип издателя. Тип Pub обычно является подтипом Publisher.

Подтип collection.Seq, представляющий изменяемые последовательности.

Последовательности — это особые случаи итерируемых коллекций класса Iterable. В отличие от итерируемых объектов, последовательности всегда имеют определённый порядок элементов. Последовательности предоставляют метод apply для индексирования. Индексы варьируются от 0 до length последовательности. Последовательности поддерживают ряд методов для поиска вхождений элементов или подпоследовательностей, включая segmentLength, prefixLength, indexWhere, indexOf, lastIndexWhere, lastIndexOf, startsWith, endsWith, indexOfSlice.

Другой способ представить последовательность — это PartialFunction от Int значений к типу элементов последовательности. Метод isDefinedAt последовательности возвращает true для интервала от 0 до length.

К последовательностям можно получить доступ в обратном порядке их элементов, используя методы reverse и reverseIterator.

Последовательности имеют два основных подтипа, IndexedSeq и LinearSeq, которые предоставляют различные гарантии производительности. IndexedSeq обеспечивает быстрый произвольный доступ к элементам и быструю операцию length. LinearSeq обеспечивает быстрый доступ только к первому элементу через head, но также имеет быструю операцию tail.

Класс добавляет метод update к collection.Seq.

Шаблонный трайт для изменяемых последовательностей типа mutable.Seq[A].

Обобщённый трайт для изменяемых множеств.

Для реализации конкретного изменяемого множества необходимо предоставить реализации следующих методов:

def contains(elem: A): Boolean
def iterator: Iterator[A]
def += (elem: A): this.type
def -= (elem: A): this.type

Если вы хотите, чтобы методы, такие как take, drop, filter возвращали тот же вид множества, вы также должны переопределить:

def empty: This

Также рекомендуется переопределить методы foreach и size для повышения эффективности.

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

Шаблонный трейт для изменяемых множеств типа mutable.Set[A].

Этот трейт предоставляет большинство операций над mutable.Set независимо от его представления. Обычно он наследуется конкретными реализациями множеств.

Для реализации конкретного изменяемого множества необходимо предоставить реализации следующих методов:

def contains(elem: A): Boolean
def iterator: Iterator[A]
def += (elem: A): this.type
def -= (elem: A): this.type

Если вы хотите, чтобы методы, такие как take, drop, filter возвращали множество того же типа, необходимо также переопределить:

def empty: This

Также рекомендуется переопределить методы foreach и size для повышения эффективности.

Изменяемый словарь, ключи которого отсортированы.

Строитель для изменяемой последовательности символов. Этот класс предоставляет API, в основном совместимый с java.lang.StringBuilder, за исключением случаев конфликта с API Scala Collections (например, метод reverse).

Объекты Subscriber[A, B] могут подписываться на события типа A , публикуемые объектом типа B . B обычно является подтипом scala.collection.mutable.Publisher.

Трейт для обозримых коллекций, которые можно изменить.

Это базовый трейт всех видов изменяемых коллекций Scala. Он реализует общее поведение всех коллекций с помощью метода foreach с подписью:

def foreach[U](f: Elem => U): Unit

Классы коллекций, смешивающие этот трейт, предоставляют конкретный метод foreach , который перебирает все элементы, содержащиеся в коллекции, применяя к каждому заданную функцию. Они также должны предоставить метод newBuilder для создания строителя коллекций того же типа.

Класс коллекций может или не может иметь две характеристики: строгость и упорядоченность. Ни одна из них не представлена как тип.

Элементы строгой коллекции вычисляются до использования в качестве значений. В отличие от этого, элементы нестрогой коллекции могут быть вычислены после получения экземпляра коллекции. Типичный пример нестрогой коллекции — scala.collection.immutable.Stream. Более общий класс примеров — TraversableViews.

Если коллекция является экземпляром упорядоченного класса коллекций, перебор её элементов с помощью foreach всегда будет посещать элементы в том же порядке, даже при разных запусках программы. Если класс неупорядочен, foreach может посещать элементы в разных порядках при разных запусках (но сохранит порядок в одном запуске).

Типичный пример неупорядоченной коллекции — HashMap объектов. Порядок обхода хеш-таблиц зависит от хэш-кодов элементов, которые могут отличаться в разных запусках. В отличие от этого, LinkedHashMap является упорядоченным, поскольку метод foreach посещает элементы в порядке их вставки в HashMap.

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

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

Классы, которые смешивают класс Undoable , предоставляют операцию undo , которая может быть использована для отмены последней операции.

Буфер, который хранит элементы в свёрнутом связанном списке.

Свёрнутые связанные списки хранят элементы в связанных массивах фиксированного размера.

Свёрнутые буферы сохраняют свойства локальности и низкой нагрузки памяти массивов-буферов, но предлагают гораздо более эффективное добавление элементов, так как они никогда не перераспределяют и не копируют внутренний массив.

Однако они обеспечивают сложность O(n/m) случайного доступа, где n количество элементов, а m размер блоков внутреннего массива.

Идеально подходит для использования, когда:

элементы добавляются в буфер, а затем все элементы просматриваются последовательнодва свёрнутых буфера должны быть конкатенированы (см. concat)

Лучше, чем односвязные списки для случайного доступа, но всё же следует избегать для такой цели.

Хеш-карта с ссылками на записи, которые слабо достижимы. Записи удаляются из этой карты, когда на ключ больше нет (сильной) ссылки. Этот класс оборачивает java.util.WeakHashMap.

Класс, представляющий Array[T].

Класс-билдер для массивов.

Этот билдер может быть повторно использован.

Это простой класс-прокси для `scala.collection.mutable.Buffer`. Он наиболее полезен для динамического построения настраиваемых наборов абстракций с использованием композиции объектов и переадресации.

Этот класс используется внутри. Он реализует мутабельный Map класс в терминах трех функций: findEntry, addEntry, и entries.

Этот класс реализует двусвязные списки, где и голова (elem), и хвост (next) и ссылка на предыдущий узел (prev) являются мутабельными.

Этот расширяемый класс может быть использован в качестве основы для реализации двусвязных списков. Переменная типа A относится к типу элементов списка, переменная типа This используется для моделирования типов самих списков.

Инвариант этой структуры данных заключается в том, что prev всегда является ссылкой на предыдущий узел в списке. Если this — первый узел списка, то prev будет null. Поле next устанавливается в this, если список пуст.

Примеры (стрелка вправо представляет next, стрелка влево представляет prev, _ представляет отсутствие значения):

Empty:

null <-- [ _ ] --,
         [   ] <-`

Single element:

null <-- [ x ] --> [ _ ] --,
         [   ] <-- [   ] <-`

More elements:

null <-- [ x ] --> [ y ] --> [ z ] --> [ _ ] --,
         [   ] <-- [   ] <-- [   ] <-- [   ] <-`

Этот класс может быть использован как адаптер для создания изменяемых карт из неизменяемых реализаций карт. Только метод empty должен быть переопределён, если исходная неизменяемая карта не пуста. empty должен возвращать представление пустой карты.

Этот класс может быть использован как адаптер для создания изменяемых множеств из неизменяемых реализаций множеств. Только метод empty должен быть переопределён, если исходное неизменяемое множество не пусто. empty должен возвращать представление пустого множества.

Более традиционный/примитивный стиль списка, где "список" также является ссылкой "голова". Ссылки могут быть созданы и изменены вручную, хотя использование API, когда это возможно, рекомендуется.

Опасность прямого изменения next:

scala> val b = LinkedList(1)
b: scala.collection.mutable.LinkedList[Int] = LinkedList(1)

scala> b.next = null

scala> println(b)
java.lang.NullPointerException

Если список пуст, next должен быть установлен в this. Последний узел в каждом изменяемом связанном списке пуст.

Примеры (_ обозначает отсутствие значения):

Empty:

[ _ ] --,
[   ] <-`

Single element:

[ x ] --> [ _ ] --,
          [   ] <-`

More elements:

[ x ] --> [ y ] --> [ z ] --> [ _ ] --,
                              [   ] <-`

Этот расширяемый класс может быть использован в качестве основы для реализации связанного списка. Переменная типа A относится к типу элементов списка, переменная типа This используется для моделирования типов самих списков.

Если список пуст, next должен быть установлен в this. Последний узел в каждом изменяемом связанном списке пуст.

Примеры (_ обозначает отсутствие значения):

Empty:

[ _ ] --,
[   ] <-`

Single element:

[ x ] --> [ _ ] --,
          [   ] <-`

More elements:

[ x ] --> [ y ] --> [ z ] --> [ _ ] --,
                              [   ] <-`

Этот трайт реализует прокси для scala.collection.mutable.Map.

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

Этот класс обычно используется как миксин. Он добавляет механизм подписки к классу Buffer, в который этот абстрактный класс включён. Класс ObservableBuffer публикует события типа Message.

Этот класс обычно используется как миксин. Он добавляет механизм подписки к классу Map, в который этот абстрактный класс включён. Класс ObservableMap публикует события типа Message.

Этот класс обычно используется как миксин. Он добавляет механизм подписки к классу Set, в который этот абстрактный класс включён. Класс ObservableSet публикует события типа Message.

Этот класс служит прокси для очередей с приоритетами. Элементы очереди должны быть упорядочены в терминах класса Ordered[T].

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

Это простой класс-обёртка для scala.collection.mutable.Set. Он наиболее полезен для динамического сборки настраиваемых абстракций множеств с использованием композиции объектов и перенаправления.

Стек реализует структуру данных, которая позволяет хранить и извлекать объекты в порядке LIFO (последним вошел — первым вышел).

Стек реализует структуру данных, которая позволяет хранить и извлекать объекты в порядке LIFO (последним вошел — первым вышел).

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

Этот класс должен использоваться как миксин. Он синхронизирует Map функции класса, в который он добавлен.

Этот класс реализует синхронизированные очереди с приоритетами, используя двоичную кучу. Элементы очереди должны быть упорядочены по отношению к Ordered[T] классу.

Это синхронизированная версия Queue[T] класса. Он реализует структуру данных, которая позволяет вставлять и извлекать элементы в порядке FIFO (первым вошел — первым вышел).

Этот класс следует использовать в качестве миксина. Он синхронизирует функции Set класса, в который он смешан.

Это синхронизированная версия класса Stack[T]. Она реализует структуру данных, которая позволяет хранить и извлекать объекты в порядке «последний вошел — первый вышел» (LIFO).