mirror of
https://github.com/apple/swift-collections
synced 2026-11-22 04:20:40 +00:00
316 lines
12 KiB
Swift
316 lines
12 KiB
Swift
//===----------------------------------------------------------------------===//
|
|
//
|
|
// This source file is part of the Swift Collections open source project
|
|
//
|
|
// Copyright (c) 2022 - 2026 Apple Inc. and the Swift project authors
|
|
// Licensed under Apache License v2.0 with Runtime Library Exception
|
|
//
|
|
// See https://swift.org/LICENSE.txt for license information
|
|
//
|
|
// SPDX-License-Identifier: Apache-2.0 WITH Swift-exception
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
#if !COLLECTIONS_SINGLE_MODULE
|
|
import InternalCollectionsUtilities
|
|
#endif
|
|
|
|
extension TreeDictionary {
|
|
/// Creates an empty dictionary.
|
|
///
|
|
/// This initializer is equivalent to initializing with an empty dictionary
|
|
/// literal.
|
|
///
|
|
/// - Complexity: O(1)
|
|
@inlinable
|
|
public init() {
|
|
self.init(_new: ._emptyNode())
|
|
}
|
|
|
|
/// Makes a copy of an existing persistent dictionary.
|
|
///
|
|
/// - Complexity: O(1)
|
|
@inlinable
|
|
public init(_ other: TreeDictionary<Key, Value>) {
|
|
self = other
|
|
}
|
|
|
|
/// Creates a new persistent dictionary that contains the same key-value
|
|
/// pairs as the given `Dictionary` instance, although not necessarily
|
|
/// in the same order.
|
|
///
|
|
/// - Complexity: O(`other.count`)
|
|
@inlinable
|
|
public init(_ other: Dictionary<Key, Value>) {
|
|
self.init(_uniqueKeysWithValues: other)
|
|
}
|
|
|
|
/// Creates a new persistent dictionary by associating the given persistent
|
|
/// set of keys with the values generated using the specified closure.
|
|
///
|
|
/// - Complexity: O(`other.count`)
|
|
@inlinable
|
|
public init(
|
|
keys: TreeSet<Key>,
|
|
valueGenerator valueTransform: (Key) throws -> Value
|
|
) rethrows {
|
|
// FIXME: This is a non-standard addition
|
|
let root = try keys._root.mapValues { try valueTransform($0.key) }
|
|
self.init(_new: root)
|
|
}
|
|
|
|
/// Creates a new dictionary from the key-value pairs in the given sequence.
|
|
///
|
|
/// You use this initializer to create a dictionary when you have a sequence
|
|
/// of key-value tuples with unique keys. Passing a sequence with duplicate
|
|
/// keys to this initializer results in a runtime error. If your
|
|
/// sequence might have duplicate keys, use the
|
|
/// `Dictionary(_:uniquingKeysWith:)` initializer instead.
|
|
///
|
|
/// - Parameter keysAndValues: A sequence of key-value pairs to use for
|
|
/// the new dictionary. Every key in `keysAndValues` must be unique.
|
|
///
|
|
/// - Returns: A new dictionary initialized with the elements of
|
|
/// `keysAndValues`.
|
|
///
|
|
/// - Precondition: The sequence must not have duplicate keys.
|
|
///
|
|
/// - Complexity: Expected O(*n*) on average, where *n* is the count if
|
|
/// key-value pairs, if `Key` properly implements hashing.
|
|
@inlinable
|
|
public init(
|
|
uniqueKeysWithValues keysAndValues: some Sequence<(Key, Value)>
|
|
) {
|
|
self.init()
|
|
for item in keysAndValues {
|
|
let hash = _Hash(item.0)
|
|
let r = unsafe _root.insert(.top, item, hash)
|
|
precondition(unsafe r.inserted, "Duplicate key: '\(item.0)'")
|
|
}
|
|
_invariantCheck()
|
|
}
|
|
|
|
/// Creates a new dictionary from the key-value pairs in the given sequence.
|
|
///
|
|
/// You use this initializer to create a dictionary when you have a sequence
|
|
/// of key-value tuples with unique keys. Passing a sequence with duplicate
|
|
/// keys to this initializer results in a runtime error. If your
|
|
/// sequence might have duplicate keys, use the
|
|
/// `Dictionary(_:uniquingKeysWith:)` initializer instead.
|
|
///
|
|
/// - Parameter keysAndValues: A sequence of key-value pairs to use for
|
|
/// the new dictionary. Every key in `keysAndValues` must be unique.
|
|
///
|
|
/// - Returns: A new dictionary initialized with the elements of
|
|
/// `keysAndValues`.
|
|
///
|
|
/// - Precondition: The sequence must not have duplicate keys.
|
|
///
|
|
/// - Complexity: Expected O(*n*) on average, where *n* is the count if
|
|
/// key-value pairs, if `Key` properly implements hashing.
|
|
@_disfavoredOverload // https://github.com/apple/swift-collections/issues/125
|
|
@inlinable
|
|
public init(
|
|
uniqueKeysWithValues keysAndValues: some Sequence<Element>
|
|
) {
|
|
if let keysAndValues = _specialize(keysAndValues, for: Self.self) {
|
|
self = keysAndValues
|
|
return
|
|
}
|
|
if let keysAndValues = _specialize(
|
|
keysAndValues, for: Dictionary<Key, Value>.self
|
|
) {
|
|
self.init(keysAndValues)
|
|
return
|
|
}
|
|
self.init(_uniqueKeysWithValues: keysAndValues)
|
|
}
|
|
|
|
@inlinable
|
|
internal init(
|
|
_uniqueKeysWithValues keysAndValues: some Sequence<Element>
|
|
) {
|
|
self.init()
|
|
for item in keysAndValues {
|
|
let hash = _Hash(item.key)
|
|
let r = unsafe _root.insert(.top, item, hash)
|
|
precondition(unsafe r.inserted, "Duplicate key: '\(item.key)'")
|
|
}
|
|
_invariantCheck()
|
|
}
|
|
|
|
/// Creates a new dictionary from the key-value pairs in the given sequence,
|
|
/// using a combining closure to determine the value for any duplicate keys.
|
|
///
|
|
/// You use this initializer to create a dictionary when you have a sequence
|
|
/// of key-value tuples that might have duplicate keys. As the dictionary is
|
|
/// built, the initializer calls the `combine` closure with the current and
|
|
/// new values for any duplicate keys. Pass a closure as `combine` that
|
|
/// returns the value to use in the resulting dictionary: The closure can
|
|
/// choose between the two values, combine them to produce a new value, or
|
|
/// even throw an error.
|
|
///
|
|
/// let pairsWithDuplicateKeys = [("a", 1), ("b", 2), ("a", 3), ("b", 4)]
|
|
///
|
|
/// let firstValues = TreeDictionary(
|
|
/// pairsWithDuplicateKeys,
|
|
/// uniquingKeysWith: { (first, _) in first })
|
|
/// // ["a": 1, "b": 2]
|
|
///
|
|
/// let lastValues = TreeDictionary(
|
|
/// pairsWithDuplicateKeys,
|
|
/// uniquingKeysWith: { (_, last) in last })
|
|
/// // ["a": 3, "b": 4]
|
|
///
|
|
/// - Parameters:
|
|
/// - keysAndValues: A sequence of key-value pairs to use for the new
|
|
/// dictionary.
|
|
/// - combine: A closure that is called with the values for any duplicate
|
|
/// keys that are encountered. The closure returns the desired value for
|
|
/// the final dictionary.
|
|
///
|
|
/// - Complexity: Expected O(*n*) on average, where *n* is the count of
|
|
/// key-value pairs, if `Key` properly implements hashing.
|
|
public init(
|
|
_ keysAndValues: some Sequence<(Key, Value)>,
|
|
uniquingKeysWith combine: (Value, Value) throws -> Value
|
|
) rethrows {
|
|
self.init()
|
|
try self.merge(keysAndValues, uniquingKeysWith: combine)
|
|
}
|
|
|
|
/// Creates a new dictionary from the key-value pairs in the given sequence,
|
|
/// using a combining closure to determine the value for any duplicate keys.
|
|
///
|
|
/// You use this initializer to create a dictionary when you have a sequence
|
|
/// of key-value tuples that might have duplicate keys. As the dictionary is
|
|
/// built, the initializer calls the `combine` closure with the current and
|
|
/// new values for any duplicate keys. Pass a closure as `combine` that
|
|
/// returns the value to use in the resulting dictionary: The closure can
|
|
/// choose between the two values, combine them to produce a new value, or
|
|
/// even throw an error.
|
|
///
|
|
/// let pairsWithDuplicateKeys = [("a", 1), ("b", 2), ("a", 3), ("b", 4)]
|
|
///
|
|
/// let firstValues = TreeDictionary(
|
|
/// pairsWithDuplicateKeys,
|
|
/// uniquingKeysWith: { (first, _) in first })
|
|
/// // ["a": 1, "b": 2]
|
|
///
|
|
/// let lastValues = TreeDictionary(
|
|
/// pairsWithDuplicateKeys,
|
|
/// uniquingKeysWith: { (_, last) in last })
|
|
/// // ["a": 3, "b": 4]
|
|
///
|
|
/// - Parameters:
|
|
/// - keysAndValues: A sequence of key-value pairs to use for the new
|
|
/// dictionary.
|
|
/// - combine: A closure that is called with the values for any duplicate
|
|
/// keys that are encountered. The closure returns the desired value for
|
|
/// the final dictionary.
|
|
///
|
|
/// - Complexity: Expected O(*n*) on average, where *n* is the count of
|
|
/// key-value pairs, if `Key` properly implements hashing.
|
|
@_disfavoredOverload // https://github.com/apple/swift-collections/issues/125
|
|
public init(
|
|
_ keysAndValues: some Sequence<Element>,
|
|
uniquingKeysWith combine: (Value, Value) throws -> Value
|
|
) rethrows {
|
|
try self.init(
|
|
keysAndValues.lazy.map { ($0.key, $0.value) },
|
|
uniquingKeysWith: combine)
|
|
}
|
|
}
|
|
|
|
extension TreeDictionary {
|
|
/// Creates a new dictionary whose keys are the groupings returned by the
|
|
/// given closure and whose values are arrays of the elements that returned
|
|
/// each key.
|
|
///
|
|
/// The arrays in the "values" position of the new dictionary each contain at
|
|
/// least one element, with the elements in the same order as the source
|
|
/// sequence.
|
|
///
|
|
/// The following example declares an array of names, and then creates a
|
|
/// dictionary from that array by grouping the names by first letter:
|
|
///
|
|
/// let students = ["Kofi", "Abena", "Efua", "Kweku", "Akosua"]
|
|
/// let studentsByLetter = TreeDictionary(grouping: students, by: { $0.first! })
|
|
/// // ["K": ["Kofi", "Kweku"], "A": ["Abena", "Akosua"], "E": ["Efua"]]
|
|
///
|
|
/// The new `studentsByLetter` dictionary has three entries, with students'
|
|
/// names grouped by the keys `"E"`, `"K"`, and `"A"`.
|
|
///
|
|
/// - Parameters:
|
|
/// - values: A sequence of values to group into a dictionary.
|
|
/// - keyForValue: A closure that returns a key for each element in
|
|
/// `values`.
|
|
///
|
|
/// - Complexity: Expected O(*n*) on average, where *n* is the count of
|
|
/// values, if `Key` properly implements hashing.
|
|
@inlinable @inline(__always)
|
|
public init<S: Sequence>(
|
|
grouping values: S,
|
|
by keyForValue: (S.Element) throws -> Key
|
|
) rethrows
|
|
where Value: RangeReplaceableCollection, Value.Element == S.Element
|
|
{
|
|
try self.init(_grouping: values, by: keyForValue)
|
|
}
|
|
|
|
/// Creates a new dictionary whose keys are the groupings returned by the
|
|
/// given closure and whose values are arrays of the elements that returned
|
|
/// each key.
|
|
///
|
|
/// The arrays in the "values" position of the new dictionary each contain at
|
|
/// least one element, with the elements in the same order as the source
|
|
/// sequence.
|
|
///
|
|
/// The following example declares an array of names, and then creates a
|
|
/// dictionary from that array by grouping the names by first letter:
|
|
///
|
|
/// let students = ["Kofi", "Abena", "Efua", "Kweku", "Akosua"]
|
|
/// let studentsByLetter = TreeDictionary(grouping: students, by: { $0.first! })
|
|
/// // ["K": ["Kofi", "Kweku"], "A": ["Abena", "Akosua"], "E": ["Efua"]]
|
|
///
|
|
/// The new `studentsByLetter` dictionary has three entries, with students'
|
|
/// names grouped by the keys `"E"`, `"K"`, and `"A"`.
|
|
///
|
|
/// - Parameters:
|
|
/// - values: A sequence of values to group into a dictionary.
|
|
/// - keyForValue: A closure that returns a key for each element in
|
|
/// `values`.
|
|
///
|
|
/// - Complexity: Expected O(*n*) on average, where *n* is the count of
|
|
/// values, if `Key` properly implements hashing.
|
|
@inlinable @inline(__always)
|
|
public init<S: Sequence>(
|
|
grouping values: S,
|
|
by keyForValue: (S.Element) throws -> Key
|
|
) rethrows
|
|
where Value == [S.Element]
|
|
{
|
|
// Note: this extra overload is necessary to make type inference work
|
|
// for the `Value` type -- we want it to default to `[S.Element`].
|
|
// (https://github.com/apple/swift-collections/issues/139)
|
|
try self.init(_grouping: values, by: keyForValue)
|
|
}
|
|
|
|
@inlinable
|
|
internal init<S: Sequence>(
|
|
_grouping values: S,
|
|
by keyForValue: (S.Element) throws -> Key
|
|
) rethrows
|
|
where Value: RangeReplaceableCollection, Value.Element == S.Element
|
|
{
|
|
self.init()
|
|
for value in values {
|
|
let key = try keyForValue(value)
|
|
self.updateValue(forKey: key, default: Value()) { array in
|
|
array.append(value)
|
|
}
|
|
}
|
|
_invariantCheck()
|
|
}
|
|
}
|