Breaking change.

The insert function no longer requires an index. Order is determined by elements.

Strong influence from SortedArray. Please confirm with Ole if it is ok to use this code, given most of the code is literal copy paste from that project.

    func sorts() {
        let subject = OrderedSet(unsorted: [3, 4, 2, 1], areInIncreasingOrder: <)
        let expected = OrderedSet(sorted: [1, 2, 3, 4])
        XCTAssertEqual(subject, expected)
    }

    func insertFront() {
        let subject = OrderedSet(sorted: [1, 2, 3])
        let outcome = subject.insert(0)
        XCTAssertEqual(outcome.index, 0)
        let expected = OrderedSet(sorted: [0, 1, 2, 3])
        XCTAssertEqual(subject, expected)
        XCTAssertTrue(outcome.didInsert)
    }
    
    func insertMiddle() {
        let subject = OrderedSet(sorted: [1, 2, 3])
        let outcome = subject.insert(2)
        XCTAssertEqual(outcome.index, 1)
        let expected = OrderedSet(sorted: [1, 2, 3])
        XCTAssertEqual(subject, expected)
        XCTAssertFalse(outcome.didInsert)
    }
    
    func insertEnd() {
        let subject = OrderedSet(sorted: [1, 2, 3])
        let outcome = subject.insert(4)
        XCTAssertEqual(outcome.index, 3)
        let expected = OrderedSet(sorted: [1, 2, 3, 4])
        XCTAssertEqual(subject, expected)
        XCTAssertTrue(outcome.didInsert)
    }

You know this probably, but she won't compile, I get 75-ish errors, some of which were beyond me to even come close to addressing.

Do you have a branch somewhere that is compatible?

I looked here -> swift3 but it's immutable

Thanx in advance

Hi~ 👋 i want to add removeAllObject(where:) function in ordered set

removeAllObject(where:) function has simple logic and powerful
we can use it when want to remove all objects that satisfy the given predicate in the ordered set.
like Swift.Array.removeAllObject

i can't waiting your good feedback~😆 thanks

Hello! I'm wondering if making OrderedSet into a proper copy-on-write type is something y'all would consider, and it's totally ok if the answer is "no"!

We ran into a double-free crash removing the same element from two OrderedSets where the second OrderedSet was made by referring to the first (var newSet = oldSet). See test testRemoveObjects__whenRemovingSameObjectFromTwoSets_doesNotCrash() in this PR. The underlying issue is that each OrderedSet has an array of pointers that point to the same memory addresses, so the second OrderedSet to deallocate that memory will crash.

At this point, we noticed the copy() method :) That lets us avoid crashing. But it occurred to me that if one OrderedSet can cause another to crash, one OrderedSet can probably mess with another in other fun ways. This is test testSubscriptAssignObjectAtIndex_doesNotAffectOtherSet(), where newSet[0] = "foo" modifies oldSet.

As a quick fix, I moved sequencedContents into a reference type and got OrderedSet to copy it whenever it's not uniquely referenced. This fixes the issues I found above, and it obviates the copy() method.

If making OrderedSet copy-on-write like this seems sensible, I'm more than happy to reformat this PR as needed. The main downside I can think of is possibly slower performance, but I admit I have not even attempted to do benchmarks. And it might be cleaner to move most of the logic, as well as the contents dictionary, into the storage class? I'm happy to do that too.

If y'all aren't interested in this change to OrderedSet, that's totally fair. I don't have any great suggestions for avoiding the double-free crash though, beyond wrapping each pointer in a reference type and ensuring deallocation only happens once. It might be worth considering whether to change OrderedSet to a reference type (i.e. class OrderedSet) and/or to add some documentation that sets don't work the same way as built-in collection types like Array and Dictionary; I suspect we're not the first and won't be the last to have the wrong expectation.

Thanks!

Maybe I misunderstand the subscript usage or there are issues with the MutableCollection implementation. The problems arise when using the subscript to set values already contained in the set. Example:

let set = OrderedSet(sequence: [0, 1, 2])
print(set)  // [0, 1, 2]

set[1] = 0
set[2] = 0

print(set.count)  // 1
print(set)  // [0]
set.forEach { print($0) }  // 0, 0, 0

Here, the iterator returns repeated values, more than promised by count. I think this example could be resolved just by removing the custom Iterator here and just using the default one.

However, after digging into it, I found more issues, example:

let set = OrderedSet(sequence: [0, 1, 2])
print(set)  // [0, 1, 2]

set[1] = 0

print(set.count)  // 2
print(set)  // [0, 0]
set.forEach { print($0) }  // 0, 0, 2

The iterator again returns more than count values but also note that print(set)now contains duplicate values and omits 2!

The indices for contents and sequencedContents get out of sync. I haven't had time to find the exact issue but there are several problems:

1. The type of iterator returned
2. The implementations of startIndex, endIndex, and index(after:)
3. The subscript setter doesn't/can't protect against already contained values

Here is my sample code:

var set = OrderedSet<Int>() {
    didSet {
        print("didSet was called")
    }
}

set.append(1)
set.append(2)
set.append(3)

the print messages is never called and printed event though the set was changed.

Maybe I am doing this incorrectly. Any advice would help.

Swift 4 has been out for some time now and most libraries have made the transition. Is there a reason why you are keeping the legacy 3.x as the primary branch? If anything Swift 4 should be on master with 3.x on a separate legacy branch.

The current implementation of the + - operators are mutating the input lhs. This contains a fix to avoid mutation.

Test case:

       let lhs = OrderedSet<Int>()
       let rhs = OrderedSet<Int>(sequence: [1,2])
       
       let sum = lhs + rhs
       print("lhsCount: \(lhs.count), summCount: \(sum.count)") // "lhsCount: 2, summCount: 2" instead of "lhsCount: 0, summCount: 2"

Added cleaning of allocated memory in case of removing elements from set. Based on Apple documentation and memory graph there is a need to deinitialize object first before being able to deallocate it or we end up with lot of leftovers in memory.

Hi,

I added targets to build iOS and macOS frameworks so that OrderedSet can be used via Carthage. Also important to ignore Carthage/ subdirectory. Only app target is now code signed; frameworks don't need this when embedded. Some other fairly standard additions to .gitignore as well.

These new targets shouldn't affect your podspec, but you might want to check.

If you accept the pull, please could you also tag a new version (2.0.5), otherwise Carthage will only pull the previous version and won't get the frameworks.

Cheers!

According to the documentation, a value stored into a subscript of a MutableCollection instance must subsequently be accessible at that same position. However, setting an OrderedSet subscript may result in a size change operation on the OrderedSet. For example, if we had 1,2,3 in the collection, and did set[2] = 1, the collection becomes 2,1. set[2] is now no longer accessible. There isn't a predictable/clean way to handle this case so I've opted to remove this conformance.

I've added what in the only method we used from MutableCollection as part of our API.

Based on comments in issue #9

Any chance of this supporting Codable? I tried digging in and updating T's generic constraints to be Hashable and Codable (which works fine) but am not familiar enough with UnsafeMutablePointer to know how to have it fit the Codable conformance. I imagine it could just converted in and out as Data but not sure. Thanks!