diff options
32 files changed, 396 insertions, 67 deletions
diff --git a/.clang-format b/.clang-format index 0712ea6..4d59fdb 100644 --- a/.clang-format +++ b/.clang-format @@ -80,7 +80,9 @@ IncludeCategories: Priority: 3 - Regex: ^<lexy-vdf/ Priority: 4 - - Regex: ^"openvic-simulation/ + - Regex: ^<tsl/ Priority: 5 - - Regex: .* + - Regex: ^"openvic-simulation/ Priority: 6 + - Regex: .* + Priority: 7 diff --git a/.gitmodules b/.gitmodules index 2309e93..a976f33 100644 --- a/.gitmodules +++ b/.gitmodules @@ -7,3 +7,6 @@ [submodule "deps/lexy-vdf"] path = deps/lexy-vdf url = https://github.com/OpenVicProject/lexy-vdf +[submodule "deps/ordered-map"] + path = deps/ordered-map + url = https://github.com/Tessil/ordered-map @@ -19,6 +19,8 @@ opts.Add(BoolVariable("build_ovsim_headless", "Build the openvic simulation head env.FinalizeOptions() +env.exposed_includes = [] + SConscript("deps/SCsub", "env") env.openvic_simulation = {} @@ -63,7 +65,7 @@ if env["build_ovsim_library"]: env.openvic_simulation["LIBPATH"] = env["LIBPATH"] env.openvic_simulation["LIBS"] = env["LIBS"] - env.openvic_simulation["INCPATH"] = [env.Dir(include_path)] + env.openvic_dataloader["INCPATH"] + env.openvic_simulation["INCPATH"] = [env.Dir(include_path)] + env.exposed_includes headless_program = None env["PROGSUFFIX"] = suffix + env["PROGSUFFIX"] @@ -8,6 +8,7 @@ def build_openvic_dataloader(env): env.Prepend(LIBS=ovdl_env.openvic_dataloader["LIBS"]) env.Append(CPPPATH=ovdl_env.openvic_dataloader["INCPATH"]) env.openvic_dataloader = ovdl_env.openvic_dataloader + env.exposed_includes += env.openvic_dataloader["INCPATH"] def build_lexy_vdf(env): lvdf_env = SConscript("lexy-vdf/SConstruct") @@ -16,5 +17,13 @@ def build_lexy_vdf(env): env.Append(CPPPATH=lvdf_env.lexy_vdf["INCPATH"]) env.lexy_vdf = lvdf_env.lexy_vdf +def build_ordered_map(env): + include_path = "ordered-map/include" + env.ordered_map = {} + env.ordered_map["INCPATH"] = [env.Dir(include_path)] + env.Append(CPPPATH=env.ordered_map["INCPATH"]) + env.exposed_includes += env.ordered_map["INCPATH"] + build_openvic_dataloader(env) -build_lexy_vdf(env)
\ No newline at end of file +build_lexy_vdf(env) +build_ordered_map(env)
\ No newline at end of file diff --git a/deps/ordered-map b/deps/ordered-map new file mode 160000 +Subproject bd8d5ef4149cd40783a486011778a2e7eedde44 diff --git a/src/openvic-simulation/country/Country.hpp b/src/openvic-simulation/country/Country.hpp index c35cf4f..76254a2 100644 --- a/src/openvic-simulation/country/Country.hpp +++ b/src/openvic-simulation/country/Country.hpp @@ -21,6 +21,7 @@ #include "openvic-simulation/types/Colour.hpp" #include "openvic-simulation/types/Date.hpp" #include "openvic-simulation/types/IdentifierRegistry.hpp" +#include "openvic-simulation/types/OrderedContainers.hpp" namespace OpenVic { struct GameManager; @@ -29,7 +30,7 @@ namespace OpenVic { struct CountryParty : HasIdentifier { friend struct CountryManager; - using policy_map_t = std::map<IssueGroup const*, Issue const*>; + using policy_map_t = ordered_map<IssueGroup const*, Issue const*>; private: const Date PROPERTY(start_date); @@ -50,8 +51,8 @@ namespace OpenVic { struct Country : HasIdentifierAndColour { friend struct CountryManager; - using unit_names_map_t = std::map<Unit const*, std::vector<std::string>>; - using government_colour_map_t = std::map<GovernmentType const*, colour_t>; + using unit_names_map_t = ordered_map<Unit const*, std::vector<std::string>>; + using government_colour_map_t = ordered_map<GovernmentType const*, colour_t>; private: GraphicalCultureType const& PROPERTY(graphical_culture); diff --git a/src/openvic-simulation/dataloader/NodeTools.cpp b/src/openvic-simulation/dataloader/NodeTools.cpp index e68a185..1dbc99c 100644 --- a/src/openvic-simulation/dataloader/NodeTools.cpp +++ b/src/openvic-simulation/dataloader/NodeTools.cpp @@ -1,6 +1,7 @@ #include "NodeTools.hpp" #include "openvic-simulation/types/Colour.hpp" +#include "openvic-simulation/utility/TslHelper.hpp" using namespace OpenVic; using namespace OpenVic::NodeTools; @@ -314,22 +315,20 @@ bool NodeTools::add_key_map_entry( } bool NodeTools::remove_key_map_entry(key_map_t& key_map, std::string_view key) { - const key_map_t::const_iterator it = key_map.find(key); - if (it != key_map.end()) { - key_map.erase(it); - return true; + if(key_map.erase(key) == 0) { + Logger::error("Failed to find dictionary key to remove: ", key); + return false; } - Logger::error("Failed to find dictionary key to remove: ", key); - return false; + return true; } key_value_callback_t NodeTools::dictionary_keys_callback(key_map_t& key_map, key_value_callback_t default_callback) { return [&key_map, default_callback](std::string_view key, ast::NodeCPtr value) -> bool { - const key_map_t::iterator it = key_map.find(key); + key_map_t::iterator it = key_map.find(key); if (it == key_map.end()) { return default_callback(key, value); } - dictionary_entry_t& entry = it->second; + dictionary_entry_t& entry = it.value(); if (++entry.count > 1 && !entry.can_repeat()) { Logger::error("Invalid repeat of dictionary key: ", key); return false; @@ -345,7 +344,7 @@ key_value_callback_t NodeTools::dictionary_keys_callback(key_map_t& key_map, key bool NodeTools::check_key_map_counts(key_map_t& key_map) { bool ret = true; - for (key_map_t::value_type& key_entry : key_map) { + for (auto key_entry : mutable_iterator(key_map)) { dictionary_entry_t& entry = key_entry.second; if (entry.must_appear() && entry.count < 1) { Logger::error("Mandatory dictionary key not present: ", key_entry.first); diff --git a/src/openvic-simulation/dataloader/NodeTools.hpp b/src/openvic-simulation/dataloader/NodeTools.hpp index c3eaf65..f3224aa 100644 --- a/src/openvic-simulation/dataloader/NodeTools.hpp +++ b/src/openvic-simulation/dataloader/NodeTools.hpp @@ -10,8 +10,11 @@ #include <openvic-dataloader/v2script/AbstractSyntaxTree.hpp> +#include <tsl/ordered_set.h> + #include "openvic-simulation/types/Colour.hpp" #include "openvic-simulation/types/Date.hpp" +#include "openvic-simulation/types/OrderedContainers.hpp" #include "openvic-simulation/types/Vector.hpp" namespace OpenVic { @@ -20,10 +23,10 @@ namespace OpenVic { /* Template for map from strings to Ts, in which string_views can be * searched for without needing to be copied into a string */ template<typename T> - using string_map_t = std::map<std::string, T, std::less<void>>; + using string_map_t = ordered_map<std::string, T>; /* String set type supporting heterogeneous key lookup */ - using string_set_t = std::set<std::string, std::less<void>>; + using string_set_t = ordered_set<std::string>; namespace NodeTools { @@ -137,7 +140,7 @@ namespace OpenVic { node_callback_t expect_dictionary(key_value_callback_t callback); struct dictionary_entry_t { - const enum class expected_count_t : uint8_t { + enum class expected_count_t : uint8_t { _MUST_APPEAR = 0b01, _CAN_REPEAT = 0b10, @@ -146,7 +149,7 @@ namespace OpenVic { ZERO_OR_MORE = _CAN_REPEAT, ONE_OR_MORE = _MUST_APPEAR | _CAN_REPEAT } expected_count; - const node_callback_t callback; + node_callback_t callback; size_t count; dictionary_entry_t(expected_count_t new_expected_count, node_callback_t new_callback) @@ -344,8 +347,8 @@ namespace OpenVic { }; } - template<typename T> - Callback<T const&> auto set_callback_pointer(std::set<T const*>& set) { + template<typename T, typename...SetArgs> + Callback<T const&> auto set_callback_pointer(tsl::ordered_set<T const*, SetArgs...>& set) { return [&set](T const& val) -> bool { set.insert(&val); return true; diff --git a/src/openvic-simulation/dataloader/Vic2PathSearch.cpp b/src/openvic-simulation/dataloader/Vic2PathSearch.cpp index 10bd08d..d3468e4 100644 --- a/src/openvic-simulation/dataloader/Vic2PathSearch.cpp +++ b/src/openvic-simulation/dataloader/Vic2PathSearch.cpp @@ -3,6 +3,7 @@ #include <lexy-vdf/KeyValues.hpp> #include <lexy-vdf/Parser.hpp> +#include "openvic-simulation/types/OrderedContainers.hpp" #include "openvic-simulation/utility/ConstexprIntToStr.hpp" #include "openvic-simulation/utility/Logger.hpp" @@ -331,7 +332,7 @@ fs::path Dataloader::search_for_game_path(fs::path hint_path) { }; using hint_path_t = fs::path; using game_path_t = fs::path; - static std::unordered_map<hint_path_t, game_path_t, fshash> _cached_paths; + static ordered_map<hint_path_t, game_path_t, fshash> _cached_paths; auto it = _cached_paths.find(hint_path); if (it != _cached_paths.end()) { diff --git a/src/openvic-simulation/economy/ProductionType.cpp b/src/openvic-simulation/economy/ProductionType.cpp index 05529f5..f0ad6ea 100644 --- a/src/openvic-simulation/economy/ProductionType.cpp +++ b/src/openvic-simulation/economy/ProductionType.cpp @@ -1,5 +1,7 @@ #include "ProductionType.hpp" +#include "openvic-simulation/types/OrderedContainers.hpp" + using namespace OpenVic; using namespace OpenVic::NodeTools; @@ -130,8 +132,8 @@ bool ProductionTypeManager::load_production_types_file( size_t expected_types = 0; // pass 1: find and store template identifiers - std::set<std::string_view> templates; - std::map<std::string_view, std::string_view> template_target_map; + ordered_set<std::string_view> templates; + ordered_map<std::string_view, std::string_view> template_target_map; bool ret = expect_dictionary( [this, &expected_types, &templates, &template_target_map](std::string_view key, ast::NodeCPtr value) -> bool { expected_types++; @@ -154,7 +156,7 @@ bool ProductionTypeManager::load_production_types_file( )(root); // pass 2: create and populate the template map - std::map<std::string_view, ast::NodeCPtr> template_node_map; + ordered_map<std::string_view, ast::NodeCPtr> template_node_map; ret &= expect_dictionary( [this, &expected_types, &templates, &template_node_map](std::string_view key, ast::NodeCPtr value) -> bool { if (templates.contains(key)) { diff --git a/src/openvic-simulation/history/CountryHistory.cpp b/src/openvic-simulation/history/CountryHistory.cpp index 00c88b8..48b30e6 100644 --- a/src/openvic-simulation/history/CountryHistory.cpp +++ b/src/openvic-simulation/history/CountryHistory.cpp @@ -242,7 +242,7 @@ bool CountryHistoryManager::load_country_history_file( return false; } } - CountryHistoryMap& country_history = it->second; + CountryHistoryMap& country_history = it.value(); return country_history._load_history_file( game_manager, dataloader, game_manager.get_military_manager().get_deployment_manager(), root diff --git a/src/openvic-simulation/history/CountryHistory.hpp b/src/openvic-simulation/history/CountryHistory.hpp index 106b1c3..6d4392b 100644 --- a/src/openvic-simulation/history/CountryHistory.hpp +++ b/src/openvic-simulation/history/CountryHistory.hpp @@ -3,22 +3,23 @@ #include <map> #include <optional> -#include "openvic-simulation/misc/Decision.hpp" #include "openvic-simulation/country/Country.hpp" #include "openvic-simulation/history/Bookmark.hpp" #include "openvic-simulation/history/HistoryMap.hpp" #include "openvic-simulation/map/Province.hpp" #include "openvic-simulation/military/Deployment.hpp" +#include "openvic-simulation/misc/Decision.hpp" #include "openvic-simulation/politics/Government.hpp" #include "openvic-simulation/politics/Ideology.hpp" #include "openvic-simulation/politics/Issue.hpp" #include "openvic-simulation/politics/NationalValue.hpp" #include "openvic-simulation/pop/Culture.hpp" #include "openvic-simulation/pop/Religion.hpp" -#include "openvic-simulation/types/Colour.hpp" -#include "openvic-simulation/types/Date.hpp" #include "openvic-simulation/research/Invention.hpp" #include "openvic-simulation/research/Technology.hpp" +#include "openvic-simulation/types/Colour.hpp" +#include "openvic-simulation/types/Date.hpp" +#include "openvic-simulation/types/OrderedContainers.hpp" namespace OpenVic { struct CountryHistoryMap; @@ -44,8 +45,8 @@ namespace OpenVic { std::vector<Reform const*> PROPERTY(reforms); std::optional<Deployment const*> PROPERTY(inital_oob); std::optional<TechnologySchool const*> PROPERTY(tech_school); - std::map<Technology const*, bool> PROPERTY(technologies); - std::map<Invention const*, bool> PROPERTY(inventions); + ordered_map<Technology const*, bool> PROPERTY(technologies); + ordered_map<Invention const*, bool> PROPERTY(inventions); fixed_point_map_t<Country const*> PROPERTY(foreign_investment); std::optional<fixed_point_t> PROPERTY(consciousness); std::optional<fixed_point_t> PROPERTY(nonstate_consciousness); @@ -55,8 +56,8 @@ namespace OpenVic { std::optional<fixed_point_t> PROPERTY(colonial_points); string_set_t PROPERTY(country_flags); string_set_t PROPERTY(global_flags); - std::map<GovernmentType const*, GovernmentType const*> PROPERTY(government_flag_overrides); - std::set<Decision const*> decisions; + ordered_map<GovernmentType const*, GovernmentType const*> PROPERTY(government_flag_overrides); + ordered_set<Decision const*> decisions; CountryHistoryEntry(Country const& new_country, Date new_date); }; @@ -81,7 +82,7 @@ namespace OpenVic { struct CountryHistoryManager { private: - std::map<Country const*, CountryHistoryMap> country_histories; + ordered_map<Country const*, CountryHistoryMap> country_histories; bool locked = false; public: diff --git a/src/openvic-simulation/history/HistoryMap.hpp b/src/openvic-simulation/history/HistoryMap.hpp index 576f00e..64975bc 100644 --- a/src/openvic-simulation/history/HistoryMap.hpp +++ b/src/openvic-simulation/history/HistoryMap.hpp @@ -5,6 +5,7 @@ #include "openvic-simulation/dataloader/NodeTools.hpp" #include "openvic-simulation/types/Date.hpp" +#include "openvic-simulation/types/OrderedContainers.hpp" namespace OpenVic { @@ -29,7 +30,7 @@ namespace OpenVic { using entry_type = _Entry; private: - std::map<Date, std::unique_ptr<entry_type>> PROPERTY(entries); + ordered_map<Date, std::unique_ptr<entry_type>> PROPERTY(entries); bool _try_load_history_entry(GameManager const& game_manager, Args... args, Date date, ast::NodeCPtr root) { entry_type *const entry = _get_or_make_entry(game_manager, date); diff --git a/src/openvic-simulation/history/ProvinceHistory.cpp b/src/openvic-simulation/history/ProvinceHistory.cpp index db998b7..f5e5187 100644 --- a/src/openvic-simulation/history/ProvinceHistory.cpp +++ b/src/openvic-simulation/history/ProvinceHistory.cpp @@ -147,7 +147,7 @@ ProvinceHistoryMap* ProvinceHistoryManager::_get_or_make_province_history(Provin return nullptr; } } - return &it->second; + return &it.value(); } bool ProvinceHistoryManager::load_province_history_file( diff --git a/src/openvic-simulation/history/ProvinceHistory.hpp b/src/openvic-simulation/history/ProvinceHistory.hpp index c3c8e67..0bda35d 100644 --- a/src/openvic-simulation/history/ProvinceHistory.hpp +++ b/src/openvic-simulation/history/ProvinceHistory.hpp @@ -11,6 +11,7 @@ #include "openvic-simulation/history/HistoryMap.hpp" #include "openvic-simulation/map/Province.hpp" #include "openvic-simulation/map/TerrainType.hpp" +#include "openvic-simulation/types/OrderedContainers.hpp" namespace OpenVic { struct ProvinceHistoryMap; @@ -30,8 +31,8 @@ namespace OpenVic { std::optional<Good const*> PROPERTY(rgo); std::optional<Province::life_rating_t> PROPERTY(life_rating); std::optional<TerrainType const*> PROPERTY(terrain_type); - std::map<BuildingType const*, BuildingType::level_t> PROPERTY(province_buildings); - std::map<BuildingType const*, BuildingType::level_t> PROPERTY(state_buildings); + ordered_map<BuildingType const*, BuildingType::level_t> PROPERTY(province_buildings); + ordered_map<BuildingType const*, BuildingType::level_t> PROPERTY(state_buildings); fixed_point_map_t<Ideology const*> PROPERTY(party_loyalties); std::vector<Pop> PROPERTY(pops); @@ -62,7 +63,7 @@ namespace OpenVic { struct ProvinceHistoryManager { private: - std::map<Province const*, ProvinceHistoryMap> PROPERTY(province_histories); + ordered_map<Province const*, ProvinceHistoryMap> PROPERTY(province_histories); bool locked = false; ProvinceHistoryMap* _get_or_make_province_history(Province const& province); diff --git a/src/openvic-simulation/map/Map.cpp b/src/openvic-simulation/map/Map.cpp index 39d4870..cce120e 100644 --- a/src/openvic-simulation/map/Map.cpp +++ b/src/openvic-simulation/map/Map.cpp @@ -2,7 +2,6 @@ #include <cassert> #include <cstddef> -#include <unordered_set> #include <vector> #include "openvic-simulation/economy/Good.hpp" @@ -10,6 +9,7 @@ #include "openvic-simulation/types/Colour.hpp" #include "openvic-simulation/utility/BMP.hpp" #include "openvic-simulation/utility/Logger.hpp" +#include "openvic-simulation/types/OrderedContainers.hpp" using namespace OpenVic; using namespace OpenVic::NodeTools; @@ -460,7 +460,7 @@ bool Map::load_map_images(fs::path const& province_path, fs::path const& terrain std::vector<fixed_point_map_t<TerrainType const*>> terrain_type_pixels_list(provinces.size()); bool ret = true; - std::unordered_set<colour_t> unrecognised_province_colours; + ordered_set<colour_t> unrecognised_province_colours; std::vector<fixed_point_t> pixels_per_province(provinces.size()); std::vector<fvec2_t> pixel_position_sum_per_province(provinces.size()); diff --git a/src/openvic-simulation/map/Map.hpp b/src/openvic-simulation/map/Map.hpp index 0025cf4..3e7ff35 100644 --- a/src/openvic-simulation/map/Map.hpp +++ b/src/openvic-simulation/map/Map.hpp @@ -9,6 +9,7 @@ #include "openvic-simulation/map/State.hpp" #include "openvic-simulation/map/TerrainType.hpp" #include "openvic-simulation/types/Colour.hpp" +#include "openvic-simulation/types/OrderedContainers.hpp" namespace OpenVic { namespace fs = std::filesystem; @@ -57,7 +58,7 @@ namespace OpenVic { }; #pragma pack(pop) private: - using colour_index_map_t = std::map<colour_t, Province::index_t>; + using colour_index_map_t = ordered_map<colour_t, Province::index_t>; IdentifierRegistry<Province> IDENTIFIER_REGISTRY_CUSTOM_INDEX_OFFSET(province, 1); IdentifierRegistry<Region> IDENTIFIER_REGISTRY(region); diff --git a/src/openvic-simulation/map/Province.hpp b/src/openvic-simulation/map/Province.hpp index 7a42666..bb10b29 100644 --- a/src/openvic-simulation/map/Province.hpp +++ b/src/openvic-simulation/map/Province.hpp @@ -2,10 +2,11 @@ #include <cassert> +#include "openvic-simulation/country/Country.hpp" #include "openvic-simulation/economy/BuildingInstance.hpp" #include "openvic-simulation/politics/Ideology.hpp" #include "openvic-simulation/pop/Pop.hpp" -#include "openvic-simulation/country/Country.hpp" +#include "openvic-simulation/types/OrderedContainers.hpp" namespace OpenVic { struct Map; @@ -81,7 +82,7 @@ namespace OpenVic { fvec2_t factory; fvec2_t building_construction; fvec2_t military_construction; - std::map<BuildingType const*, fvec2_t> building_position; + ordered_map<BuildingType const*, fvec2_t> building_position; fixed_point_map_t<BuildingType const*> building_rotation; }; diff --git a/src/openvic-simulation/map/TerrainType.hpp b/src/openvic-simulation/map/TerrainType.hpp index dc9bc56..b534ab5 100644 --- a/src/openvic-simulation/map/TerrainType.hpp +++ b/src/openvic-simulation/map/TerrainType.hpp @@ -1,6 +1,7 @@ #pragma once #include "openvic-simulation/misc/Modifier.hpp" +#include "openvic-simulation/types/OrderedContainers.hpp" namespace OpenVic { struct TerrainTypeManager; @@ -40,7 +41,7 @@ namespace OpenVic { struct TerrainTypeManager { private: - using terrain_type_mappings_map_t = std::map<TerrainTypeMapping::index_t, size_t>; + using terrain_type_mappings_map_t = ordered_map<TerrainTypeMapping::index_t, size_t>; IdentifierRegistry<TerrainType> IDENTIFIER_REGISTRY(terrain_type); IdentifierRegistry<TerrainTypeMapping> IDENTIFIER_REGISTRY(terrain_type_mapping); terrain_type_mappings_map_t terrain_type_mappings_map; diff --git a/src/openvic-simulation/misc/Event.hpp b/src/openvic-simulation/misc/Event.hpp index 71957c4..c41ef3f 100644 --- a/src/openvic-simulation/misc/Event.hpp +++ b/src/openvic-simulation/misc/Event.hpp @@ -1,6 +1,7 @@ #pragma once #include "openvic-simulation/types/IdentifierRegistry.hpp" +#include "openvic-simulation/types/OrderedContainers.hpp" namespace OpenVic { struct EventManager; @@ -66,7 +67,7 @@ namespace OpenVic { struct OnAction : HasIdentifier { friend struct EventManager; - using weight_map_t = std::map<Event const*, uint64_t>; + using weight_map_t = ordered_map<Event const*, uint64_t>; private: weight_map_t PROPERTY(weighted_events); diff --git a/src/openvic-simulation/misc/Modifier.cpp b/src/openvic-simulation/misc/Modifier.cpp index c86b121..94d38e0 100644 --- a/src/openvic-simulation/misc/Modifier.cpp +++ b/src/openvic-simulation/misc/Modifier.cpp @@ -1,6 +1,10 @@ #include "Modifier.hpp" + #include <string> +#include "openvic-simulation/types/OrderedContainers.hpp" +#include "openvic-simulation/utility/TslHelper.hpp" + using namespace OpenVic; using namespace OpenVic::NodeTools; @@ -16,7 +20,7 @@ ModifierValue& ModifierValue::operator=(ModifierValue const&) = default; ModifierValue& ModifierValue::operator=(ModifierValue&&) = default; void ModifierValue::trim() { - std::erase_if(values, [](effect_map_t::value_type const& value) -> bool { + erase_if(values, [](effect_map_t::value_type const& value) -> bool { return value.second == fixed_point_t::_0(); }); } @@ -57,7 +61,7 @@ ModifierValue ModifierValue::operator+(ModifierValue const& right) const { ModifierValue ModifierValue::operator-() const { ModifierValue ret = *this; - for (effect_map_t::value_type& value : ret.values) { + for (auto value : mutable_iterator(ret.values)) { value.second = -value.second; } return ret; diff --git a/src/openvic-simulation/politics/Rebel.hpp b/src/openvic-simulation/politics/Rebel.hpp index 29ae3ae..f7e8795 100644 --- a/src/openvic-simulation/politics/Rebel.hpp +++ b/src/openvic-simulation/politics/Rebel.hpp @@ -1,11 +1,12 @@ #pragma once +#include <cstdint> + #include "openvic-simulation/misc/Modifier.hpp" -#include "openvic-simulation/types/IdentifierRegistry.hpp" #include "openvic-simulation/politics/Government.hpp" #include "openvic-simulation/politics/Ideology.hpp" -#include <cstdint> -#include <unordered_map> +#include "openvic-simulation/types/IdentifierRegistry.hpp" +#include "openvic-simulation/types/OrderedContainers.hpp" namespace OpenVic { struct RebelManager; @@ -13,7 +14,7 @@ namespace OpenVic { struct RebelType : HasIdentifier { friend struct RebelManager; - using government_map_t = std::unordered_map<GovernmentType const*, GovernmentType const*>; + using government_map_t = ordered_map<GovernmentType const*, GovernmentType const*>; using icon_t = uint16_t; enum class area_t { diff --git a/src/openvic-simulation/politics/Rule.hpp b/src/openvic-simulation/politics/Rule.hpp index 260fb9e..4b47abf 100644 --- a/src/openvic-simulation/politics/Rule.hpp +++ b/src/openvic-simulation/politics/Rule.hpp @@ -1,6 +1,7 @@ #pragma once #include "openvic-simulation/types/IdentifierRegistry.hpp" +#include "openvic-simulation/types/OrderedContainers.hpp" namespace OpenVic { struct RuleManager; @@ -18,7 +19,7 @@ namespace OpenVic { struct RuleSet { friend struct RuleManager; - using rule_map_t = std::map<Rule const*, bool>; + using rule_map_t = ordered_map<Rule const*, bool>; private: rule_map_t rules; diff --git a/src/openvic-simulation/research/Invention.hpp b/src/openvic-simulation/research/Invention.hpp index a8ce96d..5d31155 100644 --- a/src/openvic-simulation/research/Invention.hpp +++ b/src/openvic-simulation/research/Invention.hpp @@ -2,6 +2,7 @@ #include "openvic-simulation/misc/Modifier.hpp" #include "openvic-simulation/types/IdentifierRegistry.hpp" +#include "openvic-simulation/types/OrderedContainers.hpp" namespace OpenVic { struct Unit; @@ -15,9 +16,9 @@ namespace OpenVic { struct Invention : Modifier { friend struct InventionManager; //TODO implement limit and chance - using unit_set_t = std::set<Unit const*>; - using building_set_t = std::set<BuildingType const*>; - using crime_set_t = std::set<Crime const*>; + using unit_set_t = ordered_set<Unit const*>; + using building_set_t = ordered_set<BuildingType const*>; + using crime_set_t = ordered_set<Crime const*>; private: const bool PROPERTY_CUSTOM_PREFIX(news, is); diff --git a/src/openvic-simulation/research/Technology.hpp b/src/openvic-simulation/research/Technology.hpp index 1035a8e..3b0b1da 100644 --- a/src/openvic-simulation/research/Technology.hpp +++ b/src/openvic-simulation/research/Technology.hpp @@ -1,10 +1,12 @@ #pragma once +#include <cstdint> + +#include "openvic-simulation/economy/BuildingType.hpp" +#include "openvic-simulation/military/Unit.hpp" #include "openvic-simulation/misc/Modifier.hpp" #include "openvic-simulation/types/Date.hpp" -#include "openvic-simulation/military/Unit.hpp" -#include "openvic-simulation/economy/BuildingType.hpp" -#include <cstdint> +#include "openvic-simulation/types/OrderedContainers.hpp" namespace OpenVic { struct TechnologyFolder : HasIdentifier { @@ -32,8 +34,8 @@ namespace OpenVic { struct Technology : Modifier { friend struct TechnologyManager; - using unit_set_t = std::set<Unit const*>; - using building_set_t = std::set<BuildingType const*>; + using unit_set_t = ordered_set<Unit const*>; + using building_set_t = ordered_set<BuildingType const*>; private: TechnologyArea const& PROPERTY(area); diff --git a/src/openvic-simulation/types/Colour.hpp b/src/openvic-simulation/types/Colour.hpp index dc9c4c6..38a1468 100644 --- a/src/openvic-simulation/types/Colour.hpp +++ b/src/openvic-simulation/types/Colour.hpp @@ -375,9 +375,7 @@ namespace OpenVic { }; template<typename T> - concept IsColour = requires(T t) { - { basic_colour_t { t } } -> std::same_as<T>; - }; + concept IsColour = OpenVic::utility::is_specialization_of_v<T, basic_colour_t>; template<typename ValueT, typename IntT> struct rgb_colour_traits : colour_traits<ValueT, IntT> { diff --git a/src/openvic-simulation/types/Date.hpp b/src/openvic-simulation/types/Date.hpp index 3dc6dab..2bf08e8 100644 --- a/src/openvic-simulation/types/Date.hpp +++ b/src/openvic-simulation/types/Date.hpp @@ -1,10 +1,12 @@ #pragma once +#include <climits> #include <cstdint> #include <ostream> #include <string> #include "openvic-simulation/utility/Getters.hpp" +#include "openvic-simulation/utility/Utility.hpp" namespace OpenVic { // A relative period between points in time, measured in days @@ -107,3 +109,14 @@ namespace OpenVic { }; std::ostream& operator<<(std::ostream& out, Date date); } + +namespace std { + template<> + struct hash<OpenVic::Date> { + [[nodiscard]] size_t operator()(OpenVic::Date date) const { + size_t result = 0; + OpenVic::utility::perfect_hash(result, date.get_day(), date.get_month(), date.get_year()); + return result; + } + }; +}
\ No newline at end of file diff --git a/src/openvic-simulation/types/OrderedContainers.hpp b/src/openvic-simulation/types/OrderedContainers.hpp new file mode 100644 index 0000000..e90000c --- /dev/null +++ b/src/openvic-simulation/types/OrderedContainers.hpp @@ -0,0 +1,101 @@ +#pragma once + +#include <concepts> +#include <deque> +#include <functional> +#include <memory> + +#include <tsl/ordered_map.h> +#include <tsl/ordered_set.h> + +#include "openvic-simulation/utility/Utility.hpp" + +namespace OpenVic { + struct ordered_container_string_hash { + using is_transparent = void; + [[nodiscard]] size_t operator()(const char* txt) const { + return std::hash<std::string_view> {}(txt); + } + [[nodiscard]] size_t operator()(std::string_view txt) const { + return std::hash<std::string_view> {}(txt); + } + [[nodiscard]] size_t operator()(const std::string& txt) const { + return std::hash<std::string> {}(txt); + } + }; + + template<typename T> + struct container_hash : std::hash<T> {}; + + template<> + struct container_hash<std::string> : ordered_container_string_hash {}; + template<> + struct container_hash<std::string_view> : ordered_container_string_hash {}; + template<> + struct container_hash<const char*> : ordered_container_string_hash {}; + + // Useful for contiguous memory + template< + class Key, class T, class Hash = container_hash<Key>, class KeyEqual = std::equal_to<>, + class Allocator = std::allocator<std::pair<Key, T>>, class IndexType = std::uint_least32_t> + using vector_ordered_map = + tsl::ordered_map<Key, T, Hash, KeyEqual, Allocator, std::vector<std::pair<Key, T>, Allocator>, IndexType>; + + // Useful for stable memory addresses (so long as you don't remove or insert values) + template< + class Key, class T, class Hash = container_hash<Key>, class KeyEqual = std::equal_to<>, + class Allocator = std::allocator<std::pair<Key, T>>, class IndexType = std::uint_least32_t> + using deque_ordered_map = + tsl::ordered_map<Key, T, Hash, KeyEqual, Allocator, std::deque<std::pair<Key, T>, Allocator>, IndexType>; + + template< + class Key, class T, class Hash = container_hash<Key>, class KeyEqual = std::equal_to<>, + class Allocator = std::allocator<std::pair<Key, T>>, class IndexType = std::uint_least32_t> + using ordered_map = vector_ordered_map<Key, T, Hash, KeyEqual, Allocator, IndexType>; + + // Useful for contiguous memory + template< + class Key, class Hash = container_hash<Key>, class KeyEqual = std::equal_to<>, class Allocator = std::allocator<Key>, + class ValueTypeContainer = std::deque<Key, Allocator>, class IndexType = std::uint_least32_t> + using vector_ordered_set = tsl::ordered_set<Key, Hash, KeyEqual, Allocator, std::vector<Key, Allocator>, IndexType>; + + // Useful for stable memory addresses (so long as you don't remove or insert values) + template< + class Key, class Hash = container_hash<Key>, class KeyEqual = std::equal_to<>, class Allocator = std::allocator<Key>, + class ValueTypeContainer = std::deque<Key, Allocator>, class IndexType = std::uint_least32_t> + using deque_ordered_set = tsl::ordered_set<Key, Hash, KeyEqual, Allocator, std::deque<Key, Allocator>, IndexType>; + + template< + class Key, class Hash = container_hash<Key>, class KeyEqual = std::equal_to<>, class Allocator = std::allocator<Key>, + class IndexType = std::uint_least32_t> + using ordered_set = vector_ordered_set<Key, Hash, KeyEqual, Allocator, IndexType>; + + template<typename T> + concept IsOrderedMap = utility::is_specialization_of_v<T, tsl::ordered_map>; + template<typename T> + concept IsOrderedSet = utility::is_specialization_of_v<T, tsl::ordered_set>; + template<typename T> + concept IsVectorOrderedMap = utility::is_specialization_of_v<T, vector_ordered_map>; + template<typename T> + concept IsVectorOrderedSet = utility::is_specialization_of_v<T, vector_ordered_set>; + template<typename T> + concept IsDequeOrderedMap = utility::is_specialization_of_v<T, deque_ordered_map>; + template<typename T> + concept IsDequeOrderedSet = utility::is_specialization_of_v<T, deque_ordered_set>; + + template<typename T, typename Key, typename Value> + concept IsOrderedMapOf = + IsOrderedMap<T> && std::same_as<Key, typename T::key_type> && std::same_as<Value, typename T::mapped_type>; + template<typename T, typename Key> + concept IsOrderedSetOf = IsOrderedSet<T> && std::same_as<Key, typename T::key_type>; + template<typename T, typename Key, typename Value> + concept IsVectorOrderedMapOf = + IsVectorOrderedMap<T> && std::same_as<Key, typename T::key_type> && std::same_as<Value, typename T::mapped_type>; + template<typename T, typename Key> + concept IsVectorOrderedSetOf = IsVectorOrderedSet<T> && std::same_as<Key, typename T::key_type>; + template<typename T, typename Key, typename Value> + concept IsDequeOrderedMapOf = + IsDequeOrderedMap<T> && std::same_as<Key, typename T::key_type> && std::same_as<Value, typename T::mapped_type>; + template<typename T, typename Key> + concept IsDequeOrderedSetOf = IsDequeOrderedSet<T> && std::same_as<Key, typename T::key_type>; +} diff --git a/src/openvic-simulation/types/fixed_point/FixedPointMap.hpp b/src/openvic-simulation/types/fixed_point/FixedPointMap.hpp index a7d298b..1904fec 100644 --- a/src/openvic-simulation/types/fixed_point/FixedPointMap.hpp +++ b/src/openvic-simulation/types/fixed_point/FixedPointMap.hpp @@ -1,11 +1,12 @@ #pragma once +#include "openvic-simulation/types/OrderedContainers.hpp" #include "openvic-simulation/types/fixed_point/FixedPoint.hpp" namespace OpenVic { template<typename T> - using fixed_point_map_t = std::map<T, fixed_point_t>; + using fixed_point_map_t = ordered_map<T, fixed_point_t>; template<typename T> using fixed_point_map_value_t = typename fixed_point_map_t<T>::value_type; diff --git a/src/openvic-simulation/utility/BMP.cpp b/src/openvic-simulation/utility/BMP.cpp index 4c220da..c615aea 100644 --- a/src/openvic-simulation/utility/BMP.cpp +++ b/src/openvic-simulation/utility/BMP.cpp @@ -3,6 +3,7 @@ #include <cstring> #include <set> +#include "openvic-simulation/types/OrderedContainers.hpp" #include "openvic-simulation/utility/Logger.hpp" using namespace OpenVic; @@ -91,7 +92,7 @@ bool BMP::read_header() { // Validate colours #define VALID_BITS_PER_PIXEL 1, 2, 4, 8, 16, 24, 32 #define STR(x) #x - static const std::set<uint16_t> BITS_PER_PIXEL { VALID_BITS_PER_PIXEL }; + static const ordered_set<uint16_t> BITS_PER_PIXEL { VALID_BITS_PER_PIXEL }; if (!BITS_PER_PIXEL.contains(header.bits_per_pixel)) { Logger::error("Invalid BMP bits per pixel: ", header.bits_per_pixel, " (must be one of " STR(VALID_BITS_PER_PIXEL) ")"); header_validated = false; diff --git a/src/openvic-simulation/utility/TslHelper.hpp b/src/openvic-simulation/utility/TslHelper.hpp new file mode 100644 index 0000000..9d1ae77 --- /dev/null +++ b/src/openvic-simulation/utility/TslHelper.hpp @@ -0,0 +1,129 @@ +#pragma once + +#include <type_traits> + +#include <tsl/ordered_map.h> +#include <tsl/ordered_set.h> + +#include "openvic-simulation/types/OrderedContainers.hpp" +#include "openvic-simulation/utility/Utility.hpp" + +namespace OpenVic { + template<IsOrderedMap Map, typename Key = typename Map::key_type, typename Mapped = typename Map::mapped_type> + struct _OrderedMapMutable { + using map_type = Map; + struct ordered_iterator { + using key_type = Key; + using mapped_type = Mapped; + using pair_type = std::pair<key_type const&, mapped_type&>; + using value_type = pair_type; + using iterator = typename map_type::iterator; + + using iterator_category = std::random_access_iterator_tag; + using difference_type = typename map_type::values_container_type::iterator::difference_type; + + pair_type operator*() { + return { m_iterator.key(), m_iterator.value() }; + } + + ordered_iterator& operator++() { + ++m_iterator; + return *this; + } + ordered_iterator& operator--() { + --m_iterator; + return *this; + } + + ordered_iterator operator++(int) { + ordered_iterator tmp(*this); + ++(*this); + return tmp; + } + ordered_iterator operator--(int) { + ordered_iterator tmp(*this); + --(*this); + return tmp; + } + + pair_type operator[](difference_type n) { + return *(*this + n); + } + + ordered_iterator& operator+=(difference_type n) { + m_iterator += n; + return *this; + } + ordered_iterator& operator-=(difference_type n) { + m_iterator -= n; + return *this; + } + + ordered_iterator operator+(difference_type n) { + ordered_iterator tmp(*this); + tmp += n; + return tmp; + } + ordered_iterator operator-(difference_type n) { + ordered_iterator tmp(*this); + tmp -= n; + return tmp; + } + + bool operator==(const ordered_iterator& rhs) const { + return m_iterator == rhs.m_iterator; + } + + bool operator!=(const ordered_iterator& rhs) const { + return m_iterator != rhs.m_iterator; + } + + bool operator<(const ordered_iterator& rhs) const { + return m_iterator < rhs.m_iterator; + } + + bool operator>(const ordered_iterator& rhs) const { + return m_iterator > rhs.m_iterator; + } + + bool operator<=(const ordered_iterator& rhs) const { + return m_iterator <= rhs.m_iterator; + } + + bool operator>=(const ordered_iterator& rhs) const { + return m_iterator >= rhs.m_iterator; + } + + friend ordered_iterator operator+(difference_type n, const ordered_iterator& it) { + return n + it.m_iterator; + } + + ordered_iterator operator+(const ordered_iterator& rhs) const { + return m_iterator + rhs.m_iterator; + } + + difference_type operator-(const ordered_iterator& rhs) const { + return m_iterator - rhs.m_iterator; + } + + iterator m_iterator; + }; + + _OrderedMapMutable(map_type& map) : _map(map) {} + + ordered_iterator begin() { + return ordered_iterator { _map.begin() }; + } + ordered_iterator end() { + return ordered_iterator { _map.end() }; + } + + private: + map_type& _map; + }; + + template<IsOrderedMap Map, typename Key = typename Map::key_type, typename Mapped = typename Map::mapped_type> + _OrderedMapMutable<Map, Key, Mapped> mutable_iterator(Map& map) { + return _OrderedMapMutable<Map, Key, Mapped> { map }; + } +} diff --git a/src/openvic-simulation/utility/Utility.hpp b/src/openvic-simulation/utility/Utility.hpp index e8d7205..0387e7f 100644 --- a/src/openvic-simulation/utility/Utility.hpp +++ b/src/openvic-simulation/utility/Utility.hpp @@ -1,5 +1,9 @@ #pragma once +#include <climits> +#include <functional> +#include <type_traits> + namespace OpenVic::utility { [[noreturn]] inline void unreachable() { // Uses compiler specific extensions if possible. @@ -11,4 +15,48 @@ namespace OpenVic::utility { __assume(false); #endif } + + template<class T> + constexpr inline void hash_combine(std::size_t& s, const T& v) { + std::hash<T> h; + s ^= h(v) + 0x9e3779b9 + (s << 6) + (s >> 2); + } + + template<size_t Shift, class T> + constexpr inline void hash_combine_index(std::size_t& s, const T& v) { + std::hash<T> h; + if constexpr(Shift == 0) { + s = h(v); + } else { + s ^= h(v) << Shift; + } + } + + template<class T, typename ...Args> + constexpr void perfect_hash(std::size_t& s, T&& v, Args&&... args) { + static_assert(sizeof(T) + (sizeof(Args) + ...) <= sizeof(std::size_t), "Perfect hashes must be able to fit into size_t"); + std::hash<T> h; + if constexpr(sizeof...(args) == 0) { + s = h(v); + } else { + const std::tuple arg_tuple { args... }; + s = h(v) << (sizeof(T) * CHAR_BIT); + ([&]{ + // If args is not last pointer of args + if (static_cast<const void*>(&(std::get<sizeof...(args) - 1>(arg_tuple))) != static_cast<const void*>(&args)) { + s <<= sizeof(Args) * CHAR_BIT; + } + s |= std::hash<Args>{}(args); + }(), ...); + } + } + + template<typename T, template<typename...> class Z> + struct is_specialization_of : std::false_type {}; + + template<typename... Args, template<typename...> class Z> + struct is_specialization_of<Z<Args...>, Z> : std::true_type {}; + + template<typename T, template<typename...> class Z> + inline constexpr bool is_specialization_of_v = is_specialization_of<T, Z>::value; } |