diff options
Diffstat (limited to 'core/variant/array.cpp')
| -rw-r--r-- | core/variant/array.cpp | 292 |
1 files changed, 221 insertions, 71 deletions
diff --git a/core/variant/array.cpp b/core/variant/array.cpp index 5043868b1d..69a0fff1a1 100644 --- a/core/variant/array.cpp +++ b/core/variant/array.cpp @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2020 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2020 Godot Engine contributors (cf. AUTHORS.md). */ +/* Copyright (c) 2007-2021 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2021 Godot Engine contributors (cf. AUTHORS.md). */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ @@ -34,7 +34,9 @@ #include "core/object/class_db.h" #include "core/object/script_language.h" #include "core/templates/hashfuncs.h" +#include "core/templates/search_array.h" #include "core/templates/vector.h" +#include "core/variant/callable.h" #include "core/variant/variant.h" class ArrayPrivate { @@ -86,8 +88,8 @@ int Array::size() const { return _p->array.size(); } -bool Array::empty() const { - return _p->array.empty(); +bool Array::is_empty() const { + return _p->array.is_empty(); } void Array::clear() { @@ -95,11 +97,38 @@ void Array::clear() { } bool Array::operator==(const Array &p_array) const { - return _p == p_array._p; + return recursive_equal(p_array, 0); } bool Array::operator!=(const Array &p_array) const { - return !operator==(p_array); + return !recursive_equal(p_array, 0); +} + +bool Array::recursive_equal(const Array &p_array, int recursion_count) const { + // Cheap checks + if (_p == p_array._p) { + return true; + } + const Vector<Variant> &a1 = _p->array; + const Vector<Variant> &a2 = p_array._p->array; + const int size = a1.size(); + if (size != a2.size()) { + return false; + } + + // Heavy O(n) check + if (recursion_count > MAX_RECURSION) { + ERR_PRINT("Max recursion reached"); + return true; + } + recursion_count++; + for (int i = 0; i < size; i++) { + if (!a1[i].hash_compare(a2[i], recursion_count)) { + return false; + } + } + + return true; } bool Array::operator<(const Array &p_array) const { @@ -130,17 +159,27 @@ bool Array::operator>=(const Array &p_array) const { } uint32_t Array::hash() const { - uint32_t h = hash_djb2_one_32(0); + return recursive_hash(0); +} +uint32_t Array::recursive_hash(int recursion_count) const { + if (recursion_count > MAX_RECURSION) { + ERR_PRINT("Max recursion reached"); + return 0; + } + + uint32_t h = hash_djb2_one_32(Variant::ARRAY); + + recursion_count++; for (int i = 0; i < _p->array.size(); i++) { - h = hash_djb2_one_32(_p->array[i].hash(), h); + h = hash_djb2_one_32(_p->array[i].recursive_hash(recursion_count), h); } return h; } -void Array::_assign(const Array &p_array) { +bool Array::_assign(const Array &p_array) { if (_p->typed.type != Variant::OBJECT && _p->typed.type == p_array._p->typed.type) { - //same type or untyped, just reference, shuold be fine + //same type or untyped, just reference, should be fine _ref(p_array); } else if (_p->typed.type == Variant::NIL) { //from typed to untyped, must copy, but this is cheap anyway _p->array = p_array._p->array; @@ -149,7 +188,7 @@ void Array::_assign(const Array &p_array) { //for objects, it needs full validation, either can be converted or fail for (int i = 0; i < p_array._p->array.size(); i++) { if (!_p->typed.validate(p_array._p->array[i], "assign")) { - return; + return false; } } _p->array = p_array._p->array; //then just copy, which is cheap anyway @@ -167,10 +206,10 @@ void Array::_assign(const Array &p_array) { Callable::CallError ce; Variant::construct(_p->typed.type, new_array.write[i], (const Variant **)&ptr, 1, ce); if (ce.error != Callable::CallError::CALL_OK) { - ERR_FAIL_MSG("Unable to convert array index " + itos(i) + " from '" + Variant::get_type_name(src_val.get_type()) + "' to '" + Variant::get_type_name(_p->typed.type) + "'."); + ERR_FAIL_V_MSG(false, "Unable to convert array index " + itos(i) + " from '" + Variant::get_type_name(src_val.get_type()) + "' to '" + Variant::get_type_name(_p->typed.type) + "'."); } } else { - ERR_FAIL_MSG("Unable to convert array index " + itos(i) + " from '" + Variant::get_type_name(src_val.get_type()) + "' to '" + Variant::get_type_name(_p->typed.type) + "'."); + ERR_FAIL_V_MSG(false, "Unable to convert array index " + itos(i) + " from '" + Variant::get_type_name(src_val.get_type()) + "' to '" + Variant::get_type_name(_p->typed.type) + "'."); } } @@ -179,12 +218,13 @@ void Array::_assign(const Array &p_array) { } else if (_p->typed.can_reference(p_array._p->typed)) { //same type or compatible _ref(p_array); } else { - ERR_FAIL_MSG("Assignment of arrays of incompatible types."); + ERR_FAIL_V_MSG(false, "Assignment of arrays of incompatible types."); } + return true; } void Array::operator=(const Array &p_array) { - _assign(p_array); + _ref(p_array); } void Array::push_back(const Variant &p_value) { @@ -201,9 +241,14 @@ Error Array::resize(int p_new_size) { return _p->array.resize(p_new_size); } -void Array::insert(int p_pos, const Variant &p_value) { - ERR_FAIL_COND(!_p->typed.validate(p_value, "insert")); - _p->array.insert(p_pos, p_value); +Error Array::insert(int p_pos, const Variant &p_value) { + ERR_FAIL_COND_V(!_p->typed.validate(p_value, "insert"), ERR_INVALID_PARAMETER); + return _p->array.insert(p_pos, p_value); +} + +void Array::fill(const Variant &p_value) { + ERR_FAIL_COND(!_p->typed.validate(p_value, "fill")); + _p->array.fill(p_value); } void Array::erase(const Variant &p_value) { @@ -292,12 +337,29 @@ const Variant &Array::get(int p_idx) const { } Array Array::duplicate(bool p_deep) const { + return recursive_duplicate(p_deep, 0); +} + +Array Array::recursive_duplicate(bool p_deep, int recursion_count) const { Array new_arr; + + if (recursion_count > MAX_RECURSION) { + ERR_PRINT("Max recursion reached"); + return new_arr; + } + int element_count = size(); new_arr.resize(element_count); new_arr._p->typed = _p->typed; - for (int i = 0; i < element_count; i++) { - new_arr[i] = p_deep ? get(i).duplicate(p_deep) : get(i); + if (p_deep) { + recursion_count++; + for (int i = 0; i < element_count; i++) { + new_arr[i] = get(i).recursive_duplicate(true, recursion_count); + } + } else { + for (int i = 0; i < element_count; i++) { + new_arr[i] = get(i); + } } return new_arr; @@ -318,7 +380,7 @@ Array Array::slice(int p_begin, int p_end, int p_step, bool p_deep) const { // l ERR_FAIL_COND_V_MSG(p_step == 0, new_arr, "Array slice step size cannot be zero."); - if (empty()) { // Don't try to slice empty arrays. + if (is_empty()) { // Don't try to slice empty arrays. return new_arr; } if (p_step > 0) { @@ -354,6 +416,79 @@ Array Array::slice(int p_begin, int p_end, int p_step, bool p_deep) const { // l return new_arr; } +Array Array::filter(const Callable &p_callable) const { + Array new_arr; + new_arr.resize(size()); + int accepted_count = 0; + + const Variant *argptrs[1]; + for (int i = 0; i < size(); i++) { + argptrs[0] = &get(i); + + Variant result; + Callable::CallError ce; + p_callable.call(argptrs, 1, result, ce); + if (ce.error != Callable::CallError::CALL_OK) { + ERR_FAIL_V_MSG(Array(), "Error calling method from 'filter': " + Variant::get_callable_error_text(p_callable, argptrs, 1, ce)); + } + + if (result.operator bool()) { + new_arr[accepted_count] = get(i); + accepted_count++; + } + } + + new_arr.resize(accepted_count); + + return new_arr; +} + +Array Array::map(const Callable &p_callable) const { + Array new_arr; + new_arr.resize(size()); + + const Variant *argptrs[1]; + for (int i = 0; i < size(); i++) { + argptrs[0] = &get(i); + + Variant result; + Callable::CallError ce; + p_callable.call(argptrs, 1, result, ce); + if (ce.error != Callable::CallError::CALL_OK) { + ERR_FAIL_V_MSG(Array(), "Error calling method from 'map': " + Variant::get_callable_error_text(p_callable, argptrs, 1, ce)); + } + + new_arr[i] = result; + } + + return new_arr; +} + +Variant Array::reduce(const Callable &p_callable, const Variant &p_accum) const { + int start = 0; + Variant ret = p_accum; + if (ret == Variant() && size() > 0) { + ret = front(); + start = 1; + } + + const Variant *argptrs[2]; + for (int i = start; i < size(); i++) { + argptrs[0] = &ret; + argptrs[1] = &get(i); + + Variant result; + Callable::CallError ce; + p_callable.call(argptrs, 2, result, ce); + if (ce.error != Callable::CallError::CALL_OK) { + ERR_FAIL_V_MSG(Variant(), "Error calling method from 'reduce': " + Variant::get_callable_error_text(p_callable, argptrs, 2, ce)); + } + ret = result; + } + + return ret; +} + struct _ArrayVariantSort { _FORCE_INLINE_ bool operator()(const Variant &p_l, const Variant &p_r) const { bool valid = false; @@ -371,25 +506,22 @@ void Array::sort() { } struct _ArrayVariantSortCustom { - Object *obj = nullptr; - StringName func; + Callable func; _FORCE_INLINE_ bool operator()(const Variant &p_l, const Variant &p_r) const { const Variant *args[2] = { &p_l, &p_r }; Callable::CallError err; - bool res = obj->call(func, args, 2, err); - if (err.error != Callable::CallError::CALL_OK) { - res = false; - } + Variant res; + func.call(args, 2, res, err); + ERR_FAIL_COND_V_MSG(err.error != Callable::CallError::CALL_OK, false, + "Error calling sorting method: " + Variant::get_callable_error_text(func, args, 1, err)); return res; } }; -void Array::sort_custom(Object *p_obj, const StringName &p_function) { - ERR_FAIL_NULL(p_obj); +void Array::sort_custom(Callable p_callable) { SortArray<Variant, _ArrayVariantSortCustom, true> avs; - avs.compare.obj = p_obj; - avs.compare.func = p_function; + avs.compare.func = p_callable; avs.sort(_p->array.ptrw(), _p->array.size()); } @@ -407,50 +539,23 @@ void Array::shuffle() { } } -template <typename Less> -_FORCE_INLINE_ int bisect(const Vector<Variant> &p_array, const Variant &p_value, bool p_before, const Less &p_less) { - int lo = 0; - int hi = p_array.size(); - if (p_before) { - while (lo < hi) { - const int mid = (lo + hi) / 2; - if (p_less(p_array.get(mid), p_value)) { - lo = mid + 1; - } else { - hi = mid; - } - } - } else { - while (lo < hi) { - const int mid = (lo + hi) / 2; - if (p_less(p_value, p_array.get(mid))) { - hi = mid; - } else { - lo = mid + 1; - } - } - } - return lo; -} - int Array::bsearch(const Variant &p_value, bool p_before) { ERR_FAIL_COND_V(!_p->typed.validate(p_value, "binary search"), -1); - return bisect(_p->array, p_value, p_before, _ArrayVariantSort()); + SearchArray<Variant, _ArrayVariantSort> avs; + return avs.bisect(_p->array.ptrw(), _p->array.size(), p_value, p_before); } -int Array::bsearch_custom(const Variant &p_value, Object *p_obj, const StringName &p_function, bool p_before) { +int Array::bsearch_custom(const Variant &p_value, Callable p_callable, bool p_before) { ERR_FAIL_COND_V(!_p->typed.validate(p_value, "custom binary search"), -1); - ERR_FAIL_NULL_V(p_obj, 0); - _ArrayVariantSortCustom less; - less.obj = p_obj; - less.func = p_function; + SearchArray<Variant, _ArrayVariantSortCustom> avs; + avs.compare.func = p_callable; - return bisect(_p->array, p_value, p_before, less); + return avs.bisect(_p->array.ptrw(), _p->array.size(), p_value, p_before); } -void Array::invert() { - _p->array.invert(); +void Array::reverse() { + _p->array.reverse(); } void Array::push_front(const Variant &p_value) { @@ -459,9 +564,9 @@ void Array::push_front(const Variant &p_value) { } Variant Array::pop_back() { - if (!_p->array.empty()) { - int n = _p->array.size() - 1; - Variant ret = _p->array.get(n); + if (!_p->array.is_empty()) { + const int n = _p->array.size() - 1; + const Variant ret = _p->array.get(n); _p->array.resize(n); return ret; } @@ -469,14 +574,39 @@ Variant Array::pop_back() { } Variant Array::pop_front() { - if (!_p->array.empty()) { - Variant ret = _p->array.get(0); + if (!_p->array.is_empty()) { + const Variant ret = _p->array.get(0); _p->array.remove(0); return ret; } return Variant(); } +Variant Array::pop_at(int p_pos) { + if (_p->array.is_empty()) { + // Return `null` without printing an error to mimic `pop_back()` and `pop_front()` behavior. + return Variant(); + } + + if (p_pos < 0) { + // Relative offset from the end + p_pos = _p->array.size() + p_pos; + } + + ERR_FAIL_INDEX_V_MSG( + p_pos, + _p->array.size(), + Variant(), + vformat( + "The calculated index %s is out of bounds (the array has %s elements). Leaving the array untouched and returning `null`.", + p_pos, + _p->array.size())); + + const Variant ret = _p->array.get(p_pos); + _p->array.remove(p_pos); + return ret; +} + Variant Array::min() const { Variant minval; for (int i = 0; i < size(); i++) { @@ -532,6 +662,10 @@ Array::Array(const Array &p_from, uint32_t p_type, const StringName &p_class_nam _assign(p_from); } +bool Array::typed_assign(const Array &p_other) { + return _assign(p_other); +} + void Array::set_typed(uint32_t p_type, const StringName &p_class_name, const Variant &p_script) { ERR_FAIL_COND_MSG(_p->array.size() > 0, "Type can only be set when array is empty."); ERR_FAIL_COND_MSG(_p->refcount.get() > 1, "Type can only be set when array has no more than one user."); @@ -546,6 +680,22 @@ void Array::set_typed(uint32_t p_type, const StringName &p_class_name, const Var _p->typed.where = "TypedArray"; } +bool Array::is_typed() const { + return _p->typed.type != Variant::NIL; +} + +uint32_t Array::get_typed_builtin() const { + return _p->typed.type; +} + +StringName Array::get_typed_class_name() const { + return _p->typed.class_name; +} + +Variant Array::get_typed_script() const { + return _p->typed.script; +} + Array::Array(const Array &p_from) { _p = nullptr; _ref(p_from); |