OrderedDictionary

OrderedDictionary

The MIT License (MIT)

public struct OrderedDictionary<Key: Hashable, Value>: BidirectionalCollection

Copyright © 2015-2020 Lukas Kubanek

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Courtesy of https://github.com/lukaskubanek/OrderedDictionary A generic collection for storing key-value pairs in an ordered manner.

Same as in a dictionary all keys in the collection are unique and have an associated value. Same as in an array, all key-value pairs (elements) are kept sorted and accessible by a zero-based integer index.

Inheritance

BidirectionalCollection, ExpressibleByArrayLiteral, ExpressibleByDictionaryLiteral

Nested Type Aliases

Element

The type of the key-value pair stored in the ordered dictionary.

public typealias Element = (key: Key, value: Value)

Index

The type of the index.

public typealias Index = Int

Indices

The type of the indices collection.

public typealias Indices = CountableRange<Int>

SubSequence

The type of the contiguous subrange of the ordered dictionary's elements.

public typealias SubSequence = OrderedDictionarySlice<Key, Value>

Initializers

init()

Initializes an empty ordered dictionary.

public init()

init(minimumCapacity:)

Initializes an empty ordered dictionary with preallocated space for at least the specified number of elements.

public init(minimumCapacity: Int)

init(unsorted:areInIncreasingOrder:)

Initializes an ordered dictionary from a regular unsorted dictionary by sorting it using the given sort function.

public init(unsorted: Dictionary<Key, Value>, areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows

Parameters

• unsorted: The unsorted dictionary.
• areInIncreasingOrder: The sort function which compares the key-value pairs.

init(values:uniquelyKeyedBy:)

Initializes an ordered dictionary from a sequence of values keyed by a unique key extracted from the value using the given closure.

public init<S: Sequence>(values: S, uniquelyKeyedBy extractKey: (Value) throws -> Key) rethrows where S.Element == Value

Parameters

• values: The sequence of values.
• extractKey: The closure which extracts a key from the value. The returned keys must be unique for all values from the sequence.

init(values:uniquelyKeyedBy:)

Initializes an ordered dictionary from a sequence of values keyed by a unique key extracted from the value using the given key path.

public init<S: Sequence>(values: S, uniquelyKeyedBy keyPath: KeyPath<Value, Key>) where S.Element == Value

Parameters

• values: The sequence of values.
• keyPath: The key path to use for extracting a key from the value. The extracted keys must be unique for all values from the sequence.

init(uniqueKeysWithValues:)

Initializes an ordered dictionary from a sequence of key-value pairs.

public init<S: Sequence>(uniqueKeysWithValues keysAndValues: S) where S.Element == Element

Parameters

• keysAndValues: A sequence of key-value pairs to use for the new ordered dictionary. Every key in keysAndValues must be unique.

init(arrayLiteral:)

Initializes an ordered dictionary initialized from an array literal containing a list of key-value pairs. Every key in elements must be unique.

public init(arrayLiteral elements: Element)

init(dictionaryLiteral:)

Initializes an ordered dictionary initialized from a dictionary literal. Every key in elements must be unique.

public init(dictionaryLiteral elements: (Key, Value))

Properties

orderedKeys

A collection containing just the keys of the ordered dictionary in the correct order.

var orderedKeys: OrderedDictionaryKeys<Key, Value>

orderedValues

A collection containing just the values of the ordered dictionary in the correct order.

var orderedValues: OrderedDictionaryValues<Key, Value>

unorderedDictionary

Converts itself to a common unsorted dictionary.

var unorderedDictionary: Dictionary<Key, Value>

indices

The indices that are valid for subscripting the ordered dictionary.

var indices: Indices

startIndex

The position of the first key-value pair in a non-empty ordered dictionary.

var startIndex: Index

endIndex

The position which is one greater than the position of the last valid key-value pair in the ordered dictionary.

var endIndex: Index

capacity

The total number of elements that the ordered dictionary can contain without allocating new storage.

var capacity: Int

Methods

index(after:)

Returns the position immediately after the given index.

public func index(after i: Index) -> Index

index(before:)

Returns the position immediately before the given index.

public func index(before i: Index) -> Index

containsKey(_:)

Returns a Boolean value indicating whether the ordered dictionary contains the given key.

public func containsKey(_ key: Key) -> Bool

Parameters

• key: The key to be looked up.

Returns

true if the ordered dictionary contains the given key; otherwise, false.

value(forKey:)

Returns the value associated with the given key if the key is found in the ordered dictionary, or nil if the key is not found.

public func value(forKey key: Key) -> Value?

Parameters

• key: The key to find in the ordered dictionary.

Returns

The value associated with key if key is in the ordered dictionary; otherwise, nil.

updateValue(_:forKey:)

Updates the value stored in the ordered dictionary for the given key, or appends a new key-value pair if the key does not exist.

@discardableResult public mutating func updateValue(_ value: Value, forKey key: Key) -> Value?

Parameters

• value: The new value to add to the ordered dictionary.
• key: The key to associate with value. If key already exists in the ordered dictionary, value replaces the existing associated value. If key is not already a key of the ordered dictionary, the (key, value) pair is appended at the end of the ordered dictionary.

removeValue(forKey:)

Removes the given key and its associated value from the ordered dictionary.

@discardableResult public mutating func removeValue(forKey key: Key) -> Value?

If the key is found in the ordered dictionary, this method returns the key's associated value. On removal, the indices of the ordered dictionary are invalidated. If the key is not found in the ordered dictionary, this method returns nil.

Parameters

• key: The key to remove along with its associated value.

Returns

The value that was removed, or nil if the key was not present in the ordered dictionary.

removeAll(keepingCapacity:)

Removes all key-value pairs from the ordered dictionary and invalidates all indices.

public mutating func removeAll(keepingCapacity keepCapacity: Bool = false)

Parameters

• keepCapacity: Whether the ordered dictionary should keep its underlying storage. If you pass true, the operation preserves the storage capacity that the collection has, otherwise the underlying storage is released. The default is false.

index(forKey:)

Returns the index for the given key.

public func index(forKey key: Key) -> Index?

Parameters

• key: The key to find in the ordered dictionary.

Returns

The index for key and its associated value if key is in the ordered dictionary; otherwise, nil.

elementAt(_:)

Returns the key-value pair at the specified index, or nil if there is no key-value pair at that index.

public func elementAt(_ index: Index) -> Element?

Parameters

• index: The index of the key-value pair to be looked up. index does not have to be a valid index.

Returns

A tuple containing the key-value pair corresponding to index if the index is valid; otherwise, nil.

canInsert(_:)

Checks whether the given key-value pair can be inserted into to ordered dictionary by validating the presence of the key.

@available(*, deprecated, message: "Use canInsert(key:) with the element's key instead") public func canInsert(_ newElement: Element) -> Bool

Parameters

• newElement: The key-value pair to be inserted into the ordered dictionary.

Returns

true if the key-value pair can be safely inserted; otherwise, false.

canInsert(key:)

Checks whether a key-value pair with the given key can be inserted into the ordered dictionary by validating its presence.

public func canInsert(key: Key) -> Bool

Parameters

• key: The key to be inserted into the ordered dictionary.

Returns

true if the key can safely be inserted; ortherwise, false.

canInsert(at:)

Checks whether a new key-value pair can be inserted into the ordered dictionary at the given index.

public func canInsert(at index: Index) -> Bool

Parameters

• index: The index the new key-value pair should be inserted at.

Returns

true if a new key-value pair can be inserted at the specified index; otherwise, false.

insert(_:at:)

Inserts a new key-value pair at the specified position.

public mutating func insert(_ newElement: Element, at index: Index)

If the key of the inserted pair already exists in the ordered dictionary, a runtime error is triggered. Use canInsert(_:) for performing a check first, so that this method can be executed safely.

Parameters

• newElement: The new key-value pair to insert into the ordered dictionary. The key contained in the pair must not be already present in the ordered dictionary.
• index: The position at which to insert the new key-value pair. index must be a valid index of the ordered dictionary or equal to endIndex property.

canUpdate(_:at:)

Checks whether the key-value pair at the given index can be updated with the given key-value pair. This is not the case if the key of the updated element is already present in the ordered dictionary and located at another index than the updated one.

public func canUpdate(_ newElement: Element, at index: Index) -> Bool

Although this is a checking method, a valid index has to be provided.

Parameters

• newElement: The key-value pair to be set at the specified position.
• index: The position at which to set the key-value pair. index must be a valid index of the ordered dictionary.

update(_:at:)

Updates the key-value pair located at the specified position.

@discardableResult public mutating func update(_ newElement: Element, at index: Index) -> Element?

If the key of the updated pair already exists in the ordered dictionary and is located at a different position than the specified one, a runtime error is triggered. Use canUpdate(_:at:) for performing a check first, so that this method can be executed safely.

Parameters

• newElement: The key-value pair to be set at the specified position.
• index: The position at which to set the key-value pair. index must be a valid index of the ordered dictionary.

remove(at:)

Removes and returns the key-value pair at the specified position if there is any key-value pair, or nil if there is none.

@discardableResult public mutating func remove(at index: Index) -> Element?

Parameters

• index: The position of the key-value pair to remove.

Returns

The element at the specified index, or nil if the position is not taken.

popFirst()

Removes and returns the first key-value pair of the ordered dictionary if it is not empty.

public mutating func popFirst() -> Element?

popLast()

Removes and returns the last key-value pair of the ordered dictionary if it is not empty.

public mutating func popLast() -> Element?

removeFirst()

Removes and returns the first key-value pair of the ordered dictionary.

public mutating func removeFirst() -> Element

removeLast()

Removes and returns the last key-value pair of the ordered dictionary.

public mutating func removeLast() -> Element

moveElement(forKey:to:)

Moves an existing key-value pair specified by the given key to the new index by removing it from its original index first and inserting it at the new index. If the movement is actually performed, the previous index of the key-value pair is returned. Otherwise, nil is returned.

@discardableResult public mutating func moveElement(forKey key: Key, to newIndex: Index) -> Index?

Parameters

• key: The key specifying the key-value pair to move.
• newIndex: The new index the key-value pair should be moved to.

Returns

The previous index of the key-value pair if it was sucessfully moved.

sort(by:)

Sorts the ordered dictionary in place, using the given predicate as the comparison between elements.

public mutating func sort(by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows

The predicate must be a strict weak ordering over the elements.

Parameters

• areInIncreasingOrder: A predicate that returns true if its first argument should be ordered before its second argument; otherwise, false.

sorted(by:)

Returns a new ordered dictionary, sorted using the given predicate as the comparison between elements.

public func sorted(by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> OrderedDictionary<Key, Value>

The predicate must be a strict weak ordering over the elements.

• MutatingVariant: sort

Parameters

• areInIncreasingOrder: A predicate that returns true if its first argument should be ordered before its second argument; otherwise, false.

Returns

A new ordered dictionary sorted according to the predicate.

mapValues(_:)

Returns a new ordered dictionary containing the keys of this ordered dictionary with the values transformed by the given closure by preserving the original order.

public func mapValues<T>(_ transform: (Value) throws -> T) rethrows -> OrderedDictionary<Key, T>

compactMapValues(_:)

Returns a new ordered dictionary containing only the key-value pairs that have non-nil values as the result of transformation by the given closure by preserving the original order.

public func compactMapValues<T>(_ transform: (Value) throws -> T?) rethrows -> OrderedDictionary<Key, T>

reserveCapacity(_:)

Reserves enough space to store the specified number of elements, when appropriate for the underlying types.

public mutating func reserveCapacity(_ minimumCapacity: Int)

If you are adding a known number of elements to an ordered dictionary, use this method to avoid multiple reallocations. This method ensures that the underlying types of the ordered dictionary have space allocated for at least the requested number of elements.

Parameters

• minimumCapacity: The requested number of elements to store.