TypeSortedCollection without indices

[cstjean]

I'd like to use TypeSortedCollection as a set (order does not matter at all), in high-performance code, and the cost of allocating/maintaining the vectors for the indices is bumming me out, since I have no use for it. I can't think of a perfect clean solution, but perhaps indices could be an empty tuple if preserve_order is false? That would require a lot of special-casing though... Do you feel like this is out of scope for this package?

In particular, I'd like to support filter!. but it looks mighty hairy to maintain the indices efficiently.

[tkoolen]

I think that's in scope. Let me think about this for a bit.

[tkoolen]

Just thinking aloud.

For a 'TypeSortedCollection without indices' map!, foreach, and broadcast! with mixed AbstractVector and TypeSortedCollection arguments cannot be supported. Everything else is fine. (By the way, in light of this post, I'm not sure if even the current broadcast! implementation is such a good idea). The current generated functions would still work though (with narrowed type signatures).

Options regarding types:

• empty tuple for indices, as you proposed. Could work, and probably the easiest to implement. I'm a little worried about empty TypeSortedCollections though, but maybe that's not such a big problem.
• could make type of indices a type parameter of TypeSortedCollection (use Nothing to signify no indices). Constructor signatures may be awkward though.
• could have AbstractTypeSortedCollection, TypeSortedCollection <: AbstractTypeSortedCollection, UnIndexedTypedSortedCollection <: AbstractTypeSortedCollection (name?)
• composition: TypeSortedCollection stores an UnIndexedTypedSortedCollection + indices (probably slower due to the extra indirection, so probably not acceptable)

[cstjean]

(probably slower due to the extra indirection, so probably not acceptable)

My understanding is that non-mutable structs are inlined, like in C. sizeof(Base.RefValue{SVector{30, Int64}}) is sizeof(Int64)*8, as expected.

If you create a new type, I propose TypeSortedSet. If there was such a type, would there be still be a use case for TypeSortedCollection with preserve_order=false?

[tkoolen]

Yeah, you're probably right then. I knew isbits types are inlined, but I wasn't 100% sure about immutable but non-pointerfree structs.

TypeSortedSet would make me think it can't contain duplicates, like Set. Were you thinking about having it be backed by an NTuple{N, <:Set} where N? (That would make it different from a TypeSortedCollection with preserve_order=false, so probably not.)

[cstjean]

That's a very good point, I hadn't thought of duplicates. I was just suggesting a shorter name. TypeSortedMultiset would be more correct, but it would also bring along incorrect connotations, like O(1) membership testing.

UnIndexedTypedSortedCollection is fine. As long as I don't have to pronounce it in front of an audience :) It's just bikeshedding anyway.

[cstjean]

Any further thought on this? At this point, I need such a datastructure for my work, so I can either implement it privately, or within this package (if we agree on a design)...

[tkoolen]

Sorry, I've been out of town. You know what, implementing this yourself is probably the most expedient thing to do; you need this soon and I can't justify having it high on my priority list right now. I'd just develop this privately if I were you.