Adding more data structures to the standard library

Doesn't Swift code do that too? I know NIO is non blocking, but there's way more IO to worry about than just networking. I've written blocking code before using readline, was there something non-blocking I could have used?

You really shouldn't

This is basically mandatory for any non-toy example.

Do these data structures need "an easy corresponding underlying implementation" to be considered? I see that as a non-issue. If it doesn't exist, we can write it

I would prefer it, is shows a decent summary of Swift's state of affairs, and act's as a "TODO", or at the minimum "to be considered".

Wow, yep, it's linear searching for elements. Here's the JDK 9 implementation.

I've run into that a while ago. It seemed like a strange hole, given how easily it is filled (just wrap a ConcurrentHashMap<K, Void>)

1 Like

It's definitely not the highest priority use case, in that we shouldn't be optimizing for it at the cost of other use-cases, but I find it to be incredibly important.

Code problems are a really natural way for people to introduce themselves to a language. It's a frustrating user experience if they learn that batteries aren't included, and worse, that batteries aren't available:

  • either because the code problem site doesn't support adding dependancies (I haven't seen one that does)
  • or because they don't know about SPM/Cocoapods/Carthage. We can't expect people to have to dive into this deep-end just for an efficient Deque, or some other basic data structure.

Also, a large portion of my day-to-day usage of Swift is writing small scratch files. Small scripts, quick little algorithm tests, stuff like that. Usually with the aim of prototyping an idea in Swift (where I'm fast and proficient) prior to implementing it in a less familiar language. These contexts make it hard to use anything besides the Swift and Foundation modules.

2 Likes

How about adding all of these to another package? Do they really need to be added to the standard library? I do agree that they should be avalible in a blessed way in one of Apple’s repos like the protobuff support is currently vended.

If it's as ubiquitous as Foundation, and just requires import DataStructures, I'm all for it.

But I don't think, under any circumstance, that it should require a package manager, an Xcode project, or other "scaffolding". It should be batteries-included, whether in a plain file.swift, a playground, REPL or online code problem platform.

4 Likes

This is an open problem. Same as the python module. Upstreaming the Python module - #9 by masters3d

I use Sets. Quickest way of de-duping a collection of values without any effort.

2 Likes

Sure, if you don’t need to preserve the order of elements.

1 Like

I've not yet encountered a situation where I wanted to preserve the order of a collection's elements but ignore subsequently repeated values of elements - in a simple task.

As part of a more complex algorithm I'd just iterate over the original collection, adding new elements to a 'parsed' Set and skipping those already present.

It's quite trivial to deduce an array while keeping elements, using a Set. But for some reason, very little people on StackOverflow ever show that.

Can you show that? Sets are just Maps with nil values right (said all golang users)?

1 Like
extension Sequence {
    /// Returns an array containing, in order, the first instances of
    /// elements of the sequence that compare equally for the keyPath.
    func unique<T: Hashable>(for keyPath: KeyPath<Element, T>) -> [Element] {
        var unique = Set<T>()
        return filter { unique.insert($0[keyPath: keyPath]).inserted }
    }
}
3 Likes

Probably GCD Dispatch IO? DispatchIO | Apple Developer Documentation

Dispatch I/O
An object that manages operations on a file descriptor using either stream-based or random-access semantics.

In a mini project i did one day for spending time i solved this problem by cleaning up the collection on next access. Not the best in terms of performances. :D

here

I have an idea for another way to do it. You create an internal class Key<K: Hashable> that wraps the key, and a reference to the Dictionary it's about to be stored in. Upon deallocation, you access the dict and nil out the associated value.

Your WeakHashableContainer can have different hash values for objects that are equal, which is illegal for Hashable and will leave your Dictionaries very confused :[

var a: NSObject? = NSObject()
var b: NSObject? = NSObject()

let aContainer = WeakHashableContainer(withObject: a!)
let bContainer = WeakHashableContainer(withObject: b!)

a = nil
b = nil

print(aContainer.hashValue == bContainer.hashValue) // false
print(aContainer == bContainer) // true

This would be a mutation of the underlying dictionary heap object, I assume? Then, I assume the blank entry stays until a mutation causes a resize event?

Personally I think we should also add Matrix<Element> type to Swift, because more and more newer techs like AR require matrix calculations so it'd be very convenient if we can have native matrix type support.

Of course you can create a matrix from Array type but it's not secure (e.g. even if you access a columnID that doesn't exist, as long as rowID * columsCount + columnID exists you get the result)

1 Like

just had to change the equality condition. Thank you for spotting this

    public static func ==(lhs: WeakHashableContainer<T>, rhs: WeakHashableContainer<T>) -> Bool {
        switch (lhs.weakReference, rhs.weakReference) {
        case let (.some(a), .some(b)): return a == b
        case (.some, .none), (.none, .some): return false
        case (.none, .none): return lhs.hashValue == rhs.hashValue
        }
    }

I think I might even compare just the hashValues... but somehow I feel it's wrong.

1 Like

Maybe we should open a discussion thread for each data structure? :) I feel like the thread is branched. :stuck_out_tongue:

3 Likes