192 lines
6.8 KiB
GDScript
192 lines
6.8 KiB
GDScript
class_name ArrayExtensions
|
|
|
|
## Intersects two arrays of entities.[br]
|
|
## In common terms, use this to find items appearing in both arrays.
|
|
## [param array1] The first array to intersect.[br]
|
|
## [param array2] The second array to intersect.[br]
|
|
## [b]return Array[/b] The intersection of the two arrays.
|
|
static func intersect(array1: Array, array2: Array) -> Array:
|
|
# Optimize by using the smaller array for lookup
|
|
if array1.size() > array2.size():
|
|
return intersect(array2, array1)
|
|
|
|
# Use dictionary for O(1) lookup instead of O(n) Array.has()
|
|
var lookup := {}
|
|
for entity in array2:
|
|
lookup[entity] = true
|
|
|
|
var result: Array = []
|
|
for entity in array1:
|
|
if lookup.has(entity):
|
|
result.append(entity)
|
|
return result
|
|
|
|
## Unions two arrays of entities.[br]
|
|
## In common terms, use this to combine items without duplicates.[br]
|
|
## [param array1] The first array to union.[br]
|
|
## [param array2] The second array to union.[br]
|
|
## [b]return Array[/b] The union of the two arrays.
|
|
static func union(array1: Array, array2: Array) -> Array:
|
|
# Use dictionary to track uniqueness for O(1) lookups
|
|
var seen := {}
|
|
var result: Array = []
|
|
|
|
# Add all from array1
|
|
for entity in array1:
|
|
if not seen.has(entity):
|
|
seen[entity] = true
|
|
result.append(entity)
|
|
|
|
# Add unique items from array2
|
|
for entity in array2:
|
|
if not seen.has(entity):
|
|
seen[entity] = true
|
|
result.append(entity)
|
|
|
|
return result
|
|
|
|
## Differences two arrays of entities.[br]
|
|
## In common terms, use this to find items only in the first array.[br]
|
|
## [param array1] The first array to difference.[br]
|
|
## [param array2] The second array to difference.[br]
|
|
## [b]return Array[/b] The difference of the two arrays (entities in array1 not in array2).
|
|
static func difference(array1: Array, array2: Array) -> Array:
|
|
# Use dictionary for O(1) lookup instead of O(n) Array.has()
|
|
var lookup := {}
|
|
for entity in array2:
|
|
lookup[entity] = true
|
|
|
|
var result: Array = []
|
|
for entity in array1:
|
|
if not lookup.has(entity):
|
|
result.append(entity)
|
|
return result
|
|
|
|
## systems_by_group is a dictionary of system groups and their systems
|
|
## { "Group1": [SystemA, SystemB], "Group2": [SystemC, SystemD] }
|
|
static func topological_sort(systems_by_group: Dictionary) -> void:
|
|
# Iterate over each group key in 'systems_by_group'
|
|
for group in systems_by_group.keys():
|
|
var systems = systems_by_group[group]
|
|
# If the group has 1 or fewer systems, no sorting is needed
|
|
if systems.size() <= 1:
|
|
continue
|
|
|
|
# Create two data structures:
|
|
# 1) adjacency: stores, for a given system, which systems must come after it
|
|
# 2) indegree: tracks how many "prerequisite" systems each system has
|
|
var adjacency = {}
|
|
var indegree = {}
|
|
var wildcard_front = []
|
|
var wildcard_back = []
|
|
for s in systems:
|
|
adjacency[s] = []
|
|
indegree[s] = 0
|
|
|
|
# Build adjacency and indegree counts based on dependencies returned by s.deps()
|
|
for s in systems:
|
|
var deps_dict = s.deps()
|
|
|
|
# Check for Runs.Before array on s
|
|
# If present, each item in s.Runs.Before means "s must run before that item"
|
|
# So we add the item to adjacency[s], and increment the item's indegree
|
|
# If item is null or ECS.wildcard, we treat it as "run before everything" by pushing 's' onto wildcard_front
|
|
if deps_dict.has(System.Runs.Before):
|
|
for b in deps_dict[System.Runs.Before]:
|
|
if b == null:
|
|
# ECS.wildcard AKA 'null' means s should run before all systems
|
|
wildcard_front.append(s)
|
|
else:
|
|
# Find system instance that matches the dependency type
|
|
var target_system = _find_system_by_type(systems, b)
|
|
if target_system:
|
|
# Normal dependency within the group
|
|
adjacency[s].append(target_system)
|
|
indegree[target_system] += 1
|
|
|
|
# Check for Runs.After array on s
|
|
# If present, each item in s.Runs.After means "s must run after that item"
|
|
# So we add 's' to adjacency[item], and increment s's indegree
|
|
# If item is null or ECS.wildcard, we treat it as "run after everything" by pushing 's' onto wildcard_back
|
|
if deps_dict.has(System.Runs.After):
|
|
for a in deps_dict[System.Runs.After]:
|
|
if a == null:
|
|
# ECS.wildcard AKA 'null' means s should run after all systems
|
|
wildcard_back.append(s)
|
|
else:
|
|
# Find system instance that matches the dependency type
|
|
var dependency_system = _find_system_by_type(systems, a)
|
|
if dependency_system:
|
|
# Normal dependency within the group
|
|
adjacency[dependency_system].append(s)
|
|
indegree[s] += 1
|
|
|
|
# Kahn's Algorithm begins:
|
|
# 1) Insert all systems with zero indegree into a queue
|
|
# 2) Pop from the queue, add to sorted_result
|
|
# 3) Decrement indegree for each adjacent system
|
|
# 4) Any adjacent system that reaches zero indegree is appended to the queue
|
|
var queue = []
|
|
|
|
# Adjust for wildcard_front and wildcard_back:
|
|
# wildcard_front: s runs before everything -> point s -> other
|
|
for w in wildcard_front:
|
|
for other in systems:
|
|
if other != w and not adjacency[w].has(other):
|
|
adjacency[w].append(other)
|
|
indegree[other] += 1
|
|
|
|
# wildcard_back: s runs after everything -> point other -> s
|
|
for w in wildcard_back:
|
|
for other in systems:
|
|
if other != w and not adjacency[other].has(w):
|
|
adjacency[other].append(w)
|
|
indegree[w] += 1
|
|
|
|
# Collect all systems with zero indegree into the queue as our starting point
|
|
for s in systems:
|
|
if indegree[s] == 0:
|
|
queue.append(s)
|
|
|
|
var sorted_result = []
|
|
|
|
# While there are systems with no remaining prerequisites
|
|
while queue.size() > 0:
|
|
var current = queue.pop_front()
|
|
# Add that system to the sorted list
|
|
sorted_result.append(current)
|
|
# For each system that depends on 'current'
|
|
for nxt in adjacency[current]:
|
|
# Decrement its indegree because 'current' is now accounted for
|
|
indegree[nxt] -= 1
|
|
# If it has no more prerequisites, add it to the queue
|
|
if indegree[nxt] == 0:
|
|
queue.append(nxt)
|
|
|
|
# If we successfully placed all systems, overwrite the original array with sorted_result
|
|
if sorted_result.size() == systems.size():
|
|
systems_by_group[group] = sorted_result
|
|
else:
|
|
assert(
|
|
false,
|
|
(
|
|
"Topological sort failed for group '%s'. Possible cycle or mismatch in dependencies."
|
|
% group
|
|
)
|
|
)
|
|
# Otherwise, we found a cycle or mismatch. Fallback to the original unsorted array
|
|
systems_by_group[group] = systems
|
|
|
|
# The function modifies 'systems_by_group' in-place with a topologically sorted order
|
|
|
|
## Helper function to find a system instance by its type/class
|
|
static func _find_system_by_type(systems: Array, target_type) -> System:
|
|
for system in systems:
|
|
# Check if the system is an instance of the target type
|
|
if system.get_script() == target_type:
|
|
return system
|
|
# Also check class name matching for backward compatibility
|
|
if system.get_script() and system.get_script().get_global_name() == str(target_type).get_file().get_basename():
|
|
return system
|
|
return null
|