249 lines
6.9 KiB
GDScript
249 lines
6.9 KiB
GDScript
class_name Set extends RefCounted
|
|
## Adapted from: https://gist.github.com/NoodleSushi/3eb9cc08eb1d1c369bef308262804f1e
|
|
## A custom implementation of a set data structure in GDScript.
|
|
##
|
|
## Usage Example:
|
|
## [codeblock]
|
|
## var mySet = Set.new([1, 2, 3])
|
|
## var otherSet = Set.new([2, 3, 4])
|
|
##
|
|
## var differenceSet = mySet.difference(otherSet)
|
|
## print(differenceSet.elements()) # Output: [1]
|
|
##
|
|
## mySet.intersection_update(otherSet)
|
|
## print(mySet.elements()) # Output: [2, 3]
|
|
## [/codeblock]
|
|
|
|
|
|
var _set := {}
|
|
|
|
## The constructor initializes the set with elements from the specified object,
|
|
## supporting various data types. Unsupported types trigger an assertion error.
|
|
func _init(obj: Variant = null) -> void:
|
|
match typeof(obj):
|
|
TYPE_ARRAY, TYPE_PACKED_BYTE_ARRAY, TYPE_PACKED_COLOR_ARRAY, \
|
|
TYPE_PACKED_FLOAT32_ARRAY, TYPE_PACKED_FLOAT64_ARRAY, \
|
|
TYPE_PACKED_INT32_ARRAY, TYPE_PACKED_INT64_ARRAY, \
|
|
TYPE_PACKED_VECTOR2_ARRAY, TYPE_PACKED_VECTOR3_ARRAY, \
|
|
TYPE_PACKED_STRING_ARRAY:
|
|
for element in obj:
|
|
add(element)
|
|
TYPE_NIL: pass
|
|
_:
|
|
assert(false, "Type %s unsupported for Set objects" % [typeof(obj)])
|
|
|
|
## Adds an [param element] to the set.
|
|
func add(element: Variant) -> void:
|
|
_set[element] = 0
|
|
|
|
## Clears all elements from the set.
|
|
func clear() -> void:
|
|
_set.clear()
|
|
|
|
## Creates and returns a new [Set] containing the same elements as the current set.
|
|
func duplicate() -> Set:
|
|
var new_set := Set.new()
|
|
new_set._set = _set.duplicate()
|
|
return new_set
|
|
|
|
# O(min(|self|, |set|))
|
|
## Returns a new [Set] containing elements that are present in the current set
|
|
## but not in the provided [param set].
|
|
func difference(param: Set) -> Set:
|
|
if param.hash() == self.hash():
|
|
return Set.new()
|
|
var out := self.duplicate()
|
|
if param.size() > self.size():
|
|
for element in self.elements():
|
|
if param.has(element):
|
|
out.erase(element)
|
|
else:
|
|
for element in param.elements():
|
|
out.erase(element)
|
|
return out
|
|
|
|
# O(min(|self|, |set|))
|
|
## Modifies the current [Set] to contain elements present in the current set\
|
|
## but not in the provided [param set].
|
|
func difference_update(param: Set) -> void:
|
|
if param.hash() == self.hash():
|
|
self.clear()
|
|
return
|
|
if param.size() > self.size():
|
|
for element in self.elements():
|
|
if param.has(element):
|
|
self.erase(element)
|
|
else:
|
|
for element in param.elements():
|
|
self.erase(element)
|
|
|
|
# O(min(|self|, |set|))
|
|
## Returns a new [Set] containing elements common to both the current set and
|
|
## the provided [param set].
|
|
func intersection(param: Set) -> Set:
|
|
if param.hash() == self.hash():
|
|
return duplicate()
|
|
var out := Set.new()
|
|
if param.size() > self.size():
|
|
for element in self.elements():
|
|
if param.has(element):
|
|
out.add(element)
|
|
else:
|
|
for element in param.elements():
|
|
if self.has(element):
|
|
out.add(element)
|
|
return out
|
|
|
|
# O(min(|self|, |set|))
|
|
## Modifies the current set to contain only elements common to both the
|
|
## current set and the provided [param set].
|
|
func intersection_update(param: Set) -> void:
|
|
if param.hash() == self.hash():
|
|
return
|
|
var out := Set.new()
|
|
if param.size() > self.size():
|
|
for element in self.elements():
|
|
if param.has(element):
|
|
out.add(element)
|
|
else:
|
|
for element in param.elements():
|
|
if self.has(element):
|
|
out.add(element)
|
|
self.clear()
|
|
self._set = out._set
|
|
|
|
# O([1, min(|self|, |set|)])
|
|
## Returns [code]true[/code] if the sets have no elements in common;
|
|
## otherwise, returns [code]false[/code].
|
|
func isdisjoint(param: Set) -> bool:
|
|
if param.size() > self.size():
|
|
for element in self.elements():
|
|
if param.has(element):
|
|
return false
|
|
else:
|
|
for element in param.elements():
|
|
if self.has(element):
|
|
return false
|
|
return true
|
|
|
|
# O([1, |self|])
|
|
## Returns [code]true[/code] if every element of the current set is present
|
|
## in the provided [param set]; otherwise, returns [code]false[/code].
|
|
func issubset(param: Set) -> bool:
|
|
if param.size() < self.size():
|
|
return false
|
|
else:
|
|
for element in self.elements():
|
|
if !param.has(element):
|
|
return false
|
|
return true
|
|
|
|
# O([1, |set|])
|
|
## Returns [code]true[/code] if every element of the provided [param set]
|
|
## is present in the current set; otherwise, returns [code]false[/code].
|
|
func issuperset(param: Set) -> bool:
|
|
if self.size() < param.size():
|
|
return false
|
|
else:
|
|
for element in param.elements():
|
|
if !self.has(element):
|
|
return false
|
|
return true
|
|
|
|
# O(|self|) ?
|
|
## Removes and returns an arbitrary element from the set.
|
|
func pop() -> Variant:
|
|
assert(self.size() > 0)
|
|
var element = self.elements()[randi() % self.size()]
|
|
self.erase(element)
|
|
return element
|
|
|
|
## Removes the specified [param element] from the set.
|
|
func erase(element: Variant) -> void:
|
|
_set.erase(element)
|
|
|
|
# O(min(|self|, |set|))
|
|
## Returns a new [Set] containing elements that are present in either
|
|
## the current set or the provided [param set], but not in both.
|
|
func symmetric_difference(param: Set) -> Set:
|
|
if param.hash() == self.hash():
|
|
return Set.new()
|
|
if param.size() > self.size():
|
|
var out := param.duplicate()
|
|
for element in self.elements():
|
|
if param.has(element):
|
|
out.remove(element)
|
|
return out
|
|
else:
|
|
var out := self.duplicate()
|
|
for element in param.elements():
|
|
if self.has(element):
|
|
out.remove(element)
|
|
return out
|
|
|
|
# O(min(|self|, |set|))
|
|
## Modifies the current set to contain elements that are present in either
|
|
## the current set or the provided [param set], but not in both.
|
|
func symmetric_difference_update(param: Set) -> void:
|
|
if param.size() > self.size():
|
|
var temp := param.duplicate()
|
|
for element in self.elements():
|
|
if temp.has(element):
|
|
temp.erase(element)
|
|
else:
|
|
temp.add(element)
|
|
self._set = temp._set
|
|
else:
|
|
for element in param.elements():
|
|
if self.has(element):
|
|
self.erase(element)
|
|
else:
|
|
self.add(element)
|
|
|
|
# O(min(|self|, |set|))
|
|
## Returns a new [Set] containing all elements from both the current
|
|
## set and the provided [param set].
|
|
func union(param: Set) -> Set:
|
|
if param.size() > self.size():
|
|
var out := param.duplicate()
|
|
for element in self.elements():
|
|
out.add(element)
|
|
return out
|
|
else:
|
|
var out := self.duplicate()
|
|
for element in param.elements():
|
|
out.add(element)
|
|
return out
|
|
|
|
# O(min(|self|, |set|))
|
|
## Modifies the current set to contain all elements from both the current set
|
|
## and the provided [param set].
|
|
func update(param: Set) -> void:
|
|
if param.size() > self.size():
|
|
var temp := param.duplicate()
|
|
for element in self.elements():
|
|
temp.add(element)
|
|
self._dict = temp._dict
|
|
else:
|
|
var temp := self.duplicate()
|
|
for element in param.elements():
|
|
temp.add(element)
|
|
self._dict = temp.dict
|
|
|
|
## Returns an [Array] containing all elements of the set.
|
|
func elements() -> Array:
|
|
return _set.keys()
|
|
|
|
## Returns [code]true[/code] if the set contains the specified [param element];
|
|
## otherwise, returns [code]false[/code].
|
|
func has(element: Variant) -> bool:
|
|
return _set.has(element)
|
|
|
|
## Returns the number of elements in the set.
|
|
func size() -> int:
|
|
return _set.size()
|
|
|
|
## Returns a hash value for the set.
|
|
func hash() -> int:
|
|
return _set.hash()
|