Implement a Set primitive to complement Dictionary and Array

[RabbitB]

Describe the project you are working on:
An old-school match-three game, although I've encountered the need for a Hashset on other projects, and I can foresee its need on future projects.

Describe the problem or limitation you are having in your project:
Sometimes what you care about most is the relationship between data, even more so than the data itself. In my case, I care about the set of data I have, and I want to easily perform traditional set operations on it, such as checking if a value exists in my collection of data, or if one set overlaps, is a subset/superset of another set, etc.

My explicit example and what prompted me to open an issue, is that in finding matches for items on my game board, I need to quickly check if an item already belongs to another match that was found, determine if that type of item has already been handled by any matches, and determine if different matches overlap so that I can properly merge them. As well as numerous other little things that require the same functionality.

I'm working around this by using Dictionary and only making use of the keys (just set the values to 0) when doing my checks, but what I'd ideally have access to is a Hashset. A data structure that doesn't store values, only keys, explicitly for performing fast set operations upon.

Describe the feature / enhancement and how it helps to overcome the problem or limitation:
This is related to proposal #821, but where it's concerned with adding set operations to existing primitives, I'd like to see an actual Hashset implemented, as it's best suited to situations where you explicitly need the lookup characteristics of a Dictionary, but do not have key:value pairs to store.

As you can see from the conversation in proposal #821, there is some ambiguity in set operations on Dictionaries, whereas there is none on a Hashset, since it stores only keys.

Describe how your proposal will work, with code, pseudocode, mockups, and/or diagrams:
I haven't dug enough into the Godot source to say how Dictionary and other primitives are implemented, but I would imagine it would be much like Dictionary in execution, but with the ability to store values removed and set operation functions as discussed in #821 added.

If this enhancement will not be used often, can it be worked around with a few lines of script?:
A Hashset could be developed in GDScript, but it would be slow and not a primitive like Array or Dictionary. There is no way to work around that in GDScript. For how often it would be used, I would imagine semi-regularly. Many people (including myself) tend to design their code around the [available] data-structure that best fits what you're trying to do.

Is there a reason why this should be core and not an add-on in the asset library?:
I don't believe it's possible to add primitive types through GDScript or GDNative, so this can only be added into the core engine itself.

[Beefster09]

Is there any reason you can't use a dictionary with boolean values?

[RabbitB]

Same reason you don't use an array when you need a linked-list. Different data sets have different data structure requirements, and although one can be interchanged with another if there's no alternative, you take a performance and memory-size penalty for it.

[mnn]

We have a small match 3 minigame, I am currently just brute forcing it (array of arrays of tiles = matches) and using not that performant functions from Golden Gadget library. I am probably getting away with it because we have a really small board (8x8) and target only PC, not mobile 😅.

[strank]

There is a Set datatype in the Godot codebase. It is not exposed to GDScript, and it is also a "TreeSet" (implemented with a Red-Black Tree) rather than a HashSet, and does not provide any of the usual set operations. It seems that it is mainly used to iterate over sets in order (not easy with HashSets), plus there's a lower_bound method used in only one class (also not easy for a HashSet).

I personally think a Set implementation with methods similar to what the python set type provides would be a very useful addition. But that would probably be a hashset.

[AntonioNoack]

Are there any updates on this? Sets are pretty basic and I am a little stunned, that it isn't a part of Godot...

[Calinou]

Are there any updates on this? Sets are pretty basic and I am a little stunned, that it isn't a part of Godot...

Nobody has started working on this feature yet. However, considering it's not an essential feature for most projects, it's understandable that people aren't rushing for it. Plenty of programming languages don't feature a built-in Set type 🙂

[nathanfranke]

Note: (Hash)Set is now implemented in the core engine c++, although there is no GDScript binding. godotengine/godot#61194

[okla]

although there is no GDScript binding

Is this intentional?

[nathanfranke]

Is this intentional?

Yes, having a C++ implementation doesn't always lead to GDScript bindings. There's a lot more structures in C++ than in GDScript (Vector, Map, Set, RID Owner)

[okla]

Yes

What is the reason/motivation of not adding Set to GDScript then?

[nathanfranke]

It will probably need to be rewritten (or a new type entirely) to support Variants only. C++ structures can contain any class, but GDScript can only understand Variants (e.g. floats, ints, Arrays, Nodes, etc.).

[okla]

Does this mean that it won't be added? Or there is no consensus on this? Or does it just wait to be implemented?

[nathanfranke]

Eventually this will show up in one of the weekly proposal discussions, where it will then be triaged (whether or not it will be added, which version, what priority, etc.). Since there is good community support, it will probably be accepted. Until then, just leaving 👍 (and encouraging others to do so) will rank this proposal higher and increase the chance it will be reviewed sooner.

[Zireael07]

I just found myself needing a Set structure: basically porting this to Godot: https://github.com/5310/aif-mesh

[samsface]

I gave implementing this a go to gauge how much effort adding a Set would be for this thread:
godotengine/godot@a5883dd

What I discovered was creating the class would be trivial. We would just need to duplicate the Dictionary variant renaming "Dictionary" to "Set" & then use the set template already a part of core. But then the mess begins... the Set would be a new type in the base Variant. Adding a new type to Variant isn't trivial and requires a lot of small modifications all over the code base. Bang for buck, all this work (not even mentioning documentation work) to gain essentially an alias of Dictionary with one or two functions changed might not be the best idea.

[jamesmcm]

Right now the dictionary in GDScript doesn't have set operations like difference, union, etc. though - even just adding those operations for dict keys would help a lot (i.e. not a separate HashSet type).

[Calinou]

Right now the dictionary in GDScript doesn't have set operations like difference, union, etc. though - even just adding those operations for dict keys would help a lot (i.e. not a separate HashSet type).

• See Add merge_with() and intersect_with() methods to the Array and Dictionary classes #1756.

There's Dictionay.merge() for union since Godot 3.5.

[SteampunkWizardStudios]

I ran into a situation where this would be optimal today. Please add this Godot!

I would also suggest Set.union(), Set.difference() and Set.intersection()
Would also apply to dictionaries of course and could have operator shorthands too.