Algorithms to merge Dictionaries and Arrays in GDScript (Godot Engine), with support for shallow and deep merging

README.md

Dictionary and Array merging in GDScript

GDScript algorithms for merging Dictionaries and Arrays in GDScript, with support for shallow and deep merging.

Usage

Merging dictionaries

var FuncTools = load('res://path/to/script/FuncTools.gd')

var dict1: Dictionary
var dict2: Dictionary

dict1 = {'a': 1, 'b': 2}
dict2 = {'c': 3}
FuncTools.merge_dict(dict1, dict2)
# {'a': 1, 'b': 2, 'c': 3}

dict1 = {'a': 1, 'b': {'b1': 1}}
dict2 = {'b': {'hello': 'world'}, 'c': 3}
FuncTools.merge_dict(dict1, dict2)  # Notice the 'deep_merge' argument is set to default (= false)
# {'a': 1, 'b': {'hello': 'world'}, 'c': 3}

dict1 = {'a': 1, 'b': {'b1': 1}}
dict2 = {'b': {'hello': 'world'}, 'c': 3}
FuncTools.merge_dict(dict1, dict2, true)  # Now the 'deep_merge' argument is set to true
# {'a': 1, 'b': {'b1': 1, 'hello': 'world'}, 'c': 3}
# When the third argument (deep_merge) is set to true, sub-dictionaries and sub-arrays are also merged

Merging Arrays

var FuncTools = load('res://path/to/script/FuncTools.gd')

var array1: Array
var array2: Array

array1 = ['a', 'b']
array2 = ['c']
FuncTools.merge_array(array1, array2)
# ['a', 'b', 'c']

array1 = ['a', 'b']
array2 = ['b', 'c']
FuncTools.merge_array(array1, array2)
# ['a', 'b', 'c']

array1 = ['a', {'b': 2}]
array2 = [{'b': 2}, 'c']
FuncTools.merge_array(array1, array2)  # Notice the 'deep_merge' argument is set to default (= false) - as a result, sub-dictionaries are duplicated in the merged array
# ['a', {'b': 2}, {'b': 2}, 'c']

array1 = ['a', {'b': 2}]
array2 = [{'b': 2}, 'c']
FuncTools.merge_array(array1, array2, true)  # Notice the 'deep_merge' argument is set to true - now, sub-dictionaries are not duplicated
# ['a', {'b': 2}, 'c']

Algorithmic Complexity

Dictionary merging

Time complexity: O(dict_1 + dict_2) ~= O(dict_n) Space complexity: O(dict_1 + dict_2) ~= O(dict_n)

Array merging

Time complexity: O(2*array_1² + array_2²) ~= O(array_n²) Space complexity: O(array_1 + array_2) ~= O(array_n)

Time complexity is a polynomial of second order (square of input size) due to JSON serialization of each sub-dictionary and sub-array (applicable when using deep_merge=true).

Observations

Unit testing (ref: test_FuncTools.gd) depends on GUT (Godot Unit Testing) library.

When using deep_merge=true with merge_array, all sub-dictionaries and sub-arrays must be JSON serializable.

The algorithms use deep copying before working on its arguments, resulting in no changes to the original Dictionaries or Arrays passed to them.

Not to confuse deep copying with deep merging. Deep merging relates to how the algorithms will merge Dictionaries or Arrays. Deep copying relates to how the algorithms manipulate their inputs (Dictionaries or Arrays). They could mutate the original inputs. Instead, they first create a deep copy of them and create an entirely new Dictionary/Array to avoid mutating the original ones.

FuncTools.gd

extends Node


func merge_array(array_1: Array, array_2: Array, deep_merge: bool = false) -> Array:
    var new_array = array_1.duplicate(true)
    var compare_array = new_array
    var item_exists

    if deep_merge:
        compare_array = []
        for item in new_array:
            if item is Dictionary or item is Array:
                compare_array.append(JSON.print(item))
            else:
                compare_array.append(item)

    for item in array_2:
        item_exists = item
        if item is Dictionary or item is Array:
            item = item.duplicate(true)
            if deep_merge:
                item_exists = JSON.print(item)

        if not item_exists in compare_array:
            new_array.append(item)
    return new_array


func merge_dict(dict_1: Dictionary, dict_2: Dictionary, deep_merge: bool = false) -> Dictionary:
    var new_dict = dict_1.duplicate(true)
    for key in dict_2:
        if key in new_dict:
            if deep_merge and dict_1[key] is Dictionary and dict_2[key] is Dictionary:
                new_dict[key] = merge_dict(dict_1[key], dict_2[key])
            elif deep_merge and dict_1[key] is Array and dict_2[key] is Array:
                new_dict[key] = merge_array(dict_1[key], dict_2[key])
            else:
                new_dict[key] = dict_2[key]
        else:
            new_dict[key] = dict_2[key]
    return new_dict

LICENSE.md

BSD 3-Clause License

Copyright 2022 Hackverse

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.

2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

3. Neither the name of the copyright holder nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

test_FuncTools.gd

extends 'res://addons/gut/test.gd'


class TestMergeArray:
    extends 'res://addons/gut/test.gd'

    var FuncTools = load('res://path/to/script/FuncTools.gd')

    func test_shallow_WITHOUT_overlap():
        var array1 = ['a', 'b']
        var array2 = ['c']
        var expected = ['a', 'b', 'c']

        var result = FuncTools.merge_array(array1, array2, false)

        assert_eq_deep(result, expected)

        # Shouldn't have modified the original Arrays
        assert_eq_deep(array1, ['a', 'b'])
        assert_eq_deep(array2, ['c'])

    func test_shallow_WITH_overlap():
        var array1 = ['a', 'b']
        var array2 = ['b', 'c']
        var expected = ['a', 'b', 'c']

        var result = FuncTools.merge_array(array1, array2, false)

        assert_eq_deep(result, expected)

        # Shouldn't have modified the original Arrays
        assert_eq_deep(array1, ['a', 'b'])
        assert_eq_deep(array2, ['b', 'c'])

    func test_shallow_with_sub_array_and_dictionary_WITHOUT_overlap():
        var array1 = ['a', {'b': 2}]
        var array2 = ['b', 'c']
        var expected = ['a', {'b': 2}, 'b', 'c']

        var result = FuncTools.merge_array(array1, array2, false)

        assert_eq_deep(result, expected)

        # Shouldn't have modified the original Arrays
        assert_eq_deep(array1, ['a', {'b': 2}])
        assert_eq_deep(array2, ['b', 'c'])

    func test_shallow_with_sub_array_and_dictionary_WITH_overlap():
        var array1 = ['a', {'b': 2}]
        var array2 = [{'b': 2}, 'c']
        var expected = ['a', {'b': 2}, {'b': 2}, 'c']

        var result = FuncTools.merge_array(array1, array2, false)

        assert_eq_deep(result, expected)

        # Shouldn't have modified the original Arrays
        assert_eq_deep(array1, ['a', {'b': 2}])
        assert_eq_deep(array2, [{'b': 2}, 'c'])

    func test_deep_with_sub_array_and_dictionary_WITHOUT_overlap():
        var array1 = ['a', {'b': 2}]
        var array2 = [{'b': 'override'}, 'c']
        var expected = ['a', {'b': 2}, {'b': 'override'}, 'c']

        var result = FuncTools.merge_array(array1, array2, true)

        assert_eq_deep(result, expected)

        # Shouldn't have modified the original Arrays
        assert_eq_deep(array1, ['a', {'b': 2}])
        assert_eq_deep(array2, [{'b': 'override'}, 'c'])

    func test_deep_with_sub_array_and_dictionary_WITH_overlap():
        var array1 = ['a', {'b': 2}]
        var array2 = [{'b': 2}, 'c']
        var expected = ['a', {'b': 2}, 'c']

        var result = FuncTools.merge_array(array1, array2, true)

        assert_eq_deep(result, expected)

        # Shouldn't have modified the original Arrays
        assert_eq_deep(array1, ['a', {'b': 2}])
        assert_eq_deep(array2, [{'b': 2}, 'c'])


class TestMergeDict:
    extends 'res://addons/gut/test.gd'

    var FuncTools = load('res://path/to/script/FuncTools.gd')

    func test_shallow_one_dimension_dicts_no_overlapping_keys():
        var dict1 = {'a': 1, 'b': 2}
        var dict2 = {'c': 3}
        var expected = {'a': 1, 'b': 2, 'c': 3}

        var result = FuncTools.merge_dict(dict1, dict2, false)

        assert_eq_deep(result, expected)

        # Shouldn't have modified the original dictionaries
        assert_eq_deep(dict1, {'a': 1, 'b': 2})
        assert_eq_deep(dict2, {'c': 3})

    func test_shallow_one_dimension_with_overlapping_keys():
        var dict1 = {'a': 1, 'b': 2}
        var dict2 = {'b': 0, 'c': 3}
        var expected = {'a': 1, 'b': 0, 'c': 3}

        var result = FuncTools.merge_dict(dict1, dict2, false)

        assert_eq_deep(result, expected)

        # Shouldn't have modified the original dictionaries
        assert_eq_deep(dict1, {'a': 1, 'b': 2})
        assert_eq_deep(dict2, {'b': 0, 'c': 3})

    func test_shallow_two_dimensions_no_overlapping_keys():
        var dict1 = {'a': [1, 2, 3], 'b': {'b1': 1}}
        var dict2 = {'b': {'b2': 2}, 'c': [4, 5, 6]}
        var expected = {'a': [1, 2, 3], 'b': {'b2': 2}, 'c': [4, 5, 6]}

        var result = FuncTools.merge_dict(dict1, dict2, false)

        assert_eq_deep(result, expected)

        # Shouldn't have modified the original dictionaries
        assert_eq_deep(dict1, {'a': [1, 2, 3], 'b': {'b1': 1}})
        assert_eq_deep(dict2, {'b': {'b2': 2}, 'c': [4, 5, 6]})

    func test_shallow_two_dimensions_with_overlapping_keys():
        var dict1 = {'a': 1, 'b': {'b1': 1}}
        var dict2 = {'b': {'b1': 0, 'b2': 2}, 'c': 3}
        var expected = {'a': 1, 'b': {'b1': 0, 'b2': 2}, 'c': 3}

        var result = FuncTools.merge_dict(dict1, dict2, false)

        assert_eq_deep(result, expected)

        # Shouldn't have modified the original dictionaries
        assert_eq_deep(dict1, {'a': 1, 'b': {'b1': 1}})
        assert_eq_deep(dict2, {'b': {'b1': 0, 'b2': 2}, 'c': 3})

    func test_shallow_with_overlapping_array():
        var dict1 = {'a': [1, 2, 3], 'b': 2}
        var dict2 = {'a': [3, 4, 5, 6], 'c': 3}
        var expected = {'a': [3, 4, 5, 6], 'b': 2, 'c': 3}

        var result = FuncTools.merge_dict(dict1, dict2, false)

        assert_eq_deep(result, expected)

        # Shouldn't have modified the original dictionaries
        assert_eq_deep(dict1, {'a': [1, 2, 3], 'b': 2})
        assert_eq_deep(dict2, {'a': [3, 4, 5, 6], 'c': 3})

    func test_deep_one_dimension_dicts_no_overlapping_keys():
        var dict1 = {'a': 1, 'b': 2}
        var dict2 = {'c': 3}
        var expected = {'a': 1, 'b': 2, 'c': 3}

        var result = FuncTools.merge_dict(dict1, dict2, true)

        assert_eq_deep(result, expected)

        # Shouldn't have modified the original dictionaries
        assert_eq_deep(dict1, {'a': 1, 'b': 2})
        assert_eq_deep(dict2, {'c': 3})

    func test_deep_one_dimension_with_overlapping_keys():
        var dict1 = {'a': 1, 'b': 2}
        var dict2 = {'b': 0, 'c': 3}
        var expected = {'a': 1, 'b': 0, 'c': 3}

        var result = FuncTools.merge_dict(dict1, dict2, true)

        assert_eq_deep(result, expected)

        # Shouldn't have modified the original dictionaries
        assert_eq_deep(dict1, {'a': 1, 'b': 2})
        assert_eq_deep(dict2, {'b': 0, 'c': 3})

    func test_deep_two_dimensions_no_overlapping_keys():
        var dict1 = {'a': [1, 2, 3], 'b': {'b1': 1}}
        var dict2 = {'b': {'b2': 2}, 'c': [4, 5, 6]}
        var expected = {'a': [1, 2, 3], 'b': {'b1': 1, 'b2': 2}, 'c': [4, 5, 6]}

        var result = FuncTools.merge_dict(dict1, dict2, true)

        assert_eq_deep(result, expected)

        # Shouldn't have modified the original dictionaries
        assert_eq_deep(dict1, {'a': [1, 2, 3], 'b': {'b1': 1}})
        assert_eq_deep(dict2, {'b': {'b2': 2}, 'c': [4, 5, 6]})

    func test_deep_two_dimensions_with_overlapping_keys():
        var dict1 = {'a': 1, 'b': {'b1': 1}}
        var dict2 = {'b': {'b1': 0, 'b2': 2}, 'c': 3}
        var expected = {'a': 1, 'b': {'b1': 0, 'b2': 2}, 'c': 3}

        var result = FuncTools.merge_dict(dict1, dict2, true)

        assert_eq_deep(result, expected)

        # Shouldn't have modified the original dictionaries
        assert_eq_deep(dict1, {'a': 1, 'b': {'b1': 1}})
        assert_eq_deep(dict2, {'b': {'b1': 0, 'b2': 2}, 'c': 3})

    func test_deep_with_overlapping_array():
        var dict1 = {'a': [1, 2, 3], 'b': 2}
        var dict2 = {'a': [3, 4, 5, 6], 'c': 3}
        var expected = {'a': [1, 2, 3, 4, 5, 6], 'b': 2, 'c': 3}

        var result = FuncTools.merge_dict(dict1, dict2, true)

        assert_eq_deep(result, expected)

        # Shouldn't have modified the original dictionaries
        assert_eq_deep(dict1, {'a': [1, 2, 3], 'b': 2})
        assert_eq_deep(dict2, {'a': [3, 4, 5, 6], 'c': 3})

[].append_array([]) was added in 3.4 (I think) and {}.merge({}) was added in 3.5

Had some issue to use the FuncTools as auto-loaded script in Godot 3.5, because FuncTools is a module in the python standard library. Calling FuncTools.merge_dict() just returned Null without any error message. The method was never called (checked with breakpoint and print messages).
As a remedy I renamed the class to CollectionUtils.
I know this sounds weird and took me quite a while to spot it. I still don't fully understand what is going on there.

Hey, when using this in GD script 4, is anyone else having issues with the following test case failing?

==============================================
= Run Summary
==============================================

res://test/unit/test_common_utils.gd.TestMergeArray
- test_shallow_with_sub_array_and_dictionary_WITH_overlap
    [Failed]:  ["a", { "b": 2 }, "c"] != ["a", { "b": 2 }, { "b": 2 }, "c"]  2 of 4 indexes do not match.
      [
          2:  "c" != Dictionary({ "b": 2 }).  Cannot compare String with Dictionary.
          3:  <missing index> != "c"
      ]
          at line 55

Totals
Scripts:          1
Passing tests     15
Failing tests     1
Risky tests       0
�Pending:          0
Asserts:          47 of 48 passed

15 passed 1 failed.  Tests finished in 0.067s