Container associating units to locations. More...

#include <map.hpp>

Classes
struct	const_iter_types

struct	iterator_base

struct	standard_iter_types

struct	unit_pod
	The pointer to the unit and a reference counter to record the number of extant iterators pointing to this unit. More...

Public Types
typedef iterator_base < standard_iter_types >	unit_iterator

typedef iterator_base < const_iter_types >	const_unit_iterator

typedef unit_iterator	iterator

typedef const_unit_iterator	const_iterator

Public Member Functions
	unit_map ()

	unit_map (const unit_map &that)

unit_map &	operator= (const unit_map &that)

	~unit_map ()

void	swap (unit_map &o)

unit_iterator	find (size_t id)

unit_iterator	find (const map_location &loc)

const_unit_iterator	find (const map_location &loc) const

const_unit_iterator	find (size_t id) const

unit_iterator	find_leader (int side)

const_unit_iterator	find_leader (int side) const

unit_iterator	find_first_leader (int side)

std::vector< unit_iterator >	find_leaders (int side)

std::vector< const_unit_iterator >	find_leaders (int side) const

size_t	count (const map_location &loc) const

unit_iterator	begin ()

const_unit_iterator	begin () const

unit_iterator	end ()

const_unit_iterator	end () const

size_t	size () const

size_t	num_iters () const

void	clear (bool force=false)

std::pair< unit_iterator, bool >	add (const map_location &l, const unit &u)
	Adds a copy of unit u at location l of the map. More...

std::pair< unit_iterator, bool >	insert (unit_ptr p)
	Adds the unit to the map. More...

std::pair< unit_iterator, bool >	move (const map_location &src, const map_location &dst)
	Moves a unit from location src to location dst. More...

std::pair< unit_iterator, bool >	replace (const map_location &l, const unit &u)
	Works like unit_map::add; but l is emptied first, if needed. More...

size_t	erase (const map_location &l)
	Erases the unit at location l, if any. More...

template<typename T >
size_t	erase (const T &iter)
	Erases a unit given by a pointer or an iterator. More...

unit_ptr	extract (const map_location &loc)
	Extracts a unit from the map. More...

bool	self_check () const
	Checks invariants. For debugging purposes only. Doesn't do anything in non-debug mode. More...

bool	has_unit (const unit *const u) const
	Is the unit in the map? More...

Private Types
typedef std::map< size_t, unit_pod >	t_umap
	Map of underlying_id to unit and a reference counter. More...

typedef boost::unordered_map < map_location, t_umap::iterator >	t_lmap
	Map of location to umap iterator. More...

Private Member Functions
t_umap::iterator	begin_core () const

bool	is_valid (const t_umap::const_iterator &i) const

bool	is_valid (const t_lmap::const_iterator &i) const

bool	is_found (const t_umap::const_iterator &i) const

bool	is_found (const t_lmap::const_iterator &i) const

template<typename X >
unit_map::unit_iterator	make_unit_iterator (X const &i)

template<typename X >
unit_map::const_unit_iterator	make_const_unit_iterator (X const &i) const

Private Attributes
t_umap	umap_
	underlying_id -> unit_pod. More...

t_lmap	lmap_
	location -> umap::iterator. More...

Detailed Description

Container associating units to locations.

An indirection location -> underlying_id -> unit ensures that iterators stay valid even if WML modifies or moves units on the fly. They even stay valid if a unit is erased from the map and another unit with the same underlying id is inserted in the map. In other words it is a doubly indexed ordered map with persistent iterators (that never invalidate)

Note: The unit_map is implemented as 2 maps, one unordered map that stores iterators from the ordered map of reference counted pointers to units. The unordered map provides O(1) find times. The ordered map ensures ordering of units by underlying_id. The reference counting is what guarantees the persistent iterators. Storing an iterator prevents only that dead unit's id-map entry from being recovered.; Prefered usages for tight loops follows. Use the std::pair<iterator, bool> format which checks the preconditions and returns false in the bool to indicate failure with no change to the unit_map. true indicates success and the new iterator is in first. Storing the result iterator prevents the old iterator from entering the fallback recovery code. This is faster than the old methodology of find to check if empty, insert and then find to check for success. It is the same method as std::map uses, the C++ way.

unit_iterator i; //results are stored here

Add std::pair<unit_iterator, bool> try_add(units->add(loc, unit)); if(try_add.second){i = try_add.first;}

Move std::pair<unit_iterator, bool> try_add(units->move(src, dst)); if(try_add.second){i = try_add.first;}

Insert std::pair<unit_iterator, bool> try_add(units->insert(unitp)); if(try_add.second){i = try_add.first;}

Replace (preferred over erase and then add) std::pair<unit_iterator, bool> try_add(units->move(loc, unit)); if(try_add.second){i = try_add.first;}

Note: The previous implementation was 2 binary tree based maps one the location map pointing to the other. Lookups were O(2*log(N)) and O(log(N)). Order was implicit in the id map choosen as the base. Persistence was provided by reference counting all iterators collectively and only recovering space when there were no iterators outstanding. Even 1 iterator being stored caused a leak, because all space for dead units is not recovered.; Units are owned by the container.; The indirection does not involve map lookups whenever an iterator is dereferenced, it just causes a pointer indirection. The downside is that incrementing iterator is not O(1).; The code does not involve any magic, so units moved while being iterated upon may be skipped or visited twice.; Iterators prevent ghost units from being collected. So they should never be stored into data structures, as it will cause slowdowns!; By popular demand iterators are effectively permanent. They are handles and not iterators. Any access might cause a full lookup. Keeping iterators around holds onto memory.

Definition at line 90 of file map.hpp.

Member Typedef Documentation

typedef const_unit_iterator unit_map::const_iterator

Definition at line 291 of file map.hpp.

typedef iterator_base<const_iter_types> unit_map::const_unit_iterator

Definition at line 287 of file map.hpp.

typedef unit_iterator unit_map::iterator

Definition at line 290 of file map.hpp.

typedef boost::unordered_map<map_location, t_umap::iterator> unit_map::t_lmap

private

Map of location to umap iterator.

Definition at line 110 of file map.hpp.

typedef std::map<size_t, unit_pod> unit_map::t_umap

private

Map of underlying_id to unit and a reference counter.

Dead units have a unit pointer equal to nullptr. The map entry is removed iff the reference counter equals zero and there are no more iterators pointing to this unit.

Definition at line 108 of file map.hpp.

typedef iterator_base<standard_iter_types> unit_map::unit_iterator

Definition at line 286 of file map.hpp.

Constructor & Destructor Documentation

unit_map::unit_map ( )

Definition at line 31 of file map.cpp.

unit_map::unit_map ( const unit_map & that )

Definition at line 37 of file map.cpp.

References add(), begin(), end(), and i.

unit_map::~unit_map ( )

Definition at line 59 of file map.cpp.

References clear().

Member Function Documentation

std::pair< unit_map::unit_iterator, bool > unit_map::add	(	const map_location &	l,
		const unit &	u
	)

Adds a copy of unit u at location l of the map.

Returns: std::pair<unit_iterator, bool> a bool indicating success and an iterator pointing to the new unit, or the unit already occupying location.

Note: It is 3 times as fast to attempt to insert a unit at l and check for success than it is to verify that the location is empty, insert the unit check the location for the unit.

Definition at line 70 of file map.cpp.

References insert(), and self_check().

Referenced by BOOST_AUTO_TEST_CASE(), ai::helper_place_unit(), editor::map_context::load_scenario(), editor::editor_action_unit::perform_without_undo(), replace(), SYNCED_COMMAND_HANDLER_FUNCTION(), temporary_unit_placer::temporary_unit_placer(), and unit_map().

unit_iterator unit_map::begin ( )

inline

Definition at line 308 of file map.hpp.

References begin_core(), and make_unit_iterator().

Referenced by ai::ai_default_rca::aspect_attacks_base::analyze_targets(), ai::readonly_context_impl::calculate_moves(), actions::check_recall_location(), actions::check_recruit_location(), ai::ai_default_rca::move_to_targets_phase::choose_move(), events::mouse_handler::cycle_units(), ai::stage_unit_formulas::do_play_stage(), display::draw_minimap_units(), preferences::encounter_start_units(), ai::ai_default_rca::goto_phase::evaluate(), game_logic::move_candidate_action::evaluate(), game_logic::attack_candidate_action::evaluate(), ai::ai_default_rca::get_healing_phase::evaluate(), ai::ai_default_rca::retreat_phase::evaluate(), find_first_leader(), find_leader(), find_leaders(), ai::default_ai_context_impl::find_targets(), null_unit_filter_impl::first_match_on_map(), basic_unit_filter_impl::first_match_on_map(), actions::get_recalls(), actions::get_recruits(), ai::formula_ai::get_value(), ai::ai_default_rca::get_villages_phase::get_villages(), game_board::heal_all_survivors(), game_lua_kernel::intf_heal_unit(), game_lua_kernel::intf_kill(), unit_map::iterator_base< iter_types >::operator--(), game_board::replace_map(), events::mouse_handler::select_hex(), dialogs::show_unit_list(), game_state::side_can_recruit_on(), editor::map_context::to_config(), unit_map(), and verify().

const_unit_iterator unit_map::begin ( ) const

inline

Definition at line 309 of file map.hpp.

References begin_core(), and make_const_unit_iterator().

unit_map::t_umap::iterator unit_map::begin_core ( ) const

private

Definition at line 63 of file map.cpp.

References i, self_check(), and umap_.

Referenced by begin().

void unit_map::clear ( bool force = false )

Definition at line 235 of file map.cpp.

References DBG_NG, i, is_valid(), lmap_, num_iters(), and umap_.

Referenced by ~unit_map().

size_t unit_map::count ( const map_location & loc ) const

inline

Definition at line 306 of file map.hpp.

References lmap_.

Referenced by ai::ai_default_rca::move_cost_calculator::cost(), ai::ai_default_rca::move_leader_to_keep_phase::evaluate(), ai::formula_ai::execute_variant(), ai::default_ai_context_impl::find_targets(), ai::ai_default_rca::move_to_targets_phase::form_group(), game_logic::attack_map_callable::get_value(), game_logic::move_map_callable::get_value(), game_display::highlight_hex(), ai::ai_default_rca::move_to_targets_phase::move_group(), and verify().

unit_iterator unit_map::end ( )

inline

Definition at line 311 of file map.hpp.

References make_unit_iterator(), and umap_.

const_unit_iterator unit_map::end ( ) const

inline

Definition at line 312 of file map.hpp.

References make_const_unit_iterator(), and umap_.

size_t unit_map::erase ( const map_location & l )

Erases the unit at location l, if any.

Returns: the number of erased units (0 or 1).

Definition at line 277 of file map.cpp.

References extract(), and self_check().

Referenced by erase(), game_lua_kernel::intf_erase_unit(), game_lua_kernel::intf_kill(), game_lua_kernel::intf_put_recall_unit(), game_lua_kernel::intf_put_unit(), events::menu_handler::kill_unit(), editor::editor_action_unit_delete::perform_without_undo(), lua_unit::put_map(), replace(), game_board::replace_map(), SYNCED_COMMAND_HANDLER_FUNCTION(), actions::undo::recruit_action::undo(), actions::undo::recall_action::undo(), and temporary_unit_placer::~temporary_unit_placer().

template<typename T >

size_t unit_map::erase ( const T & iter )

Erases a unit given by a pointer or an iterator.

Precondition: The unit is on the map.

Definition at line 436 of file map.hpp.

References erase().

unit_ptr unit_map::extract ( const map_location & loc )

Extracts a unit from the map.

The unit is no longer owned by the map. It can be reinserted later, if needed.

Definition at line 249 of file map.cpp.

References DBG_NG, i, lmap_, self_check(), and umap_.

Referenced by ai::attack_analysis::analyze(), wb::suppose_dead::apply_temp_modifier(), BOOST_AUTO_TEST_CASE(), erase(), game_lua_kernel::intf_extract_unit(), wb::recall::remove_temp_modifier(), and wb::recruit::remove_temp_modifier().

unit_map::unit_iterator unit_map::find ( size_t id )

Definition at line 285 of file map.cpp.

References i, self_check(), and umap_.

Referenced by unit::ability_active(), ai::ai_default_rca::move_to_targets_phase::access_points(), scoped_xy_unit::activate(), unit_creator::add_unit(), replay::add_unit_checksum(), advance_unit(), advance_unit_at(), dialogs::advance_unit_dialog(), ai::attack_analysis::analyze(), dialogs::animate_unit_advancement(), wb::move::apply_temp_modifier(), attack_unit_and_advance(), backstab_check(), battle_context::battle_context(), ai::readonly_context_impl::best_defensive_position(), BOOST_AUTO_TEST_CASE(), editor::editor_controller::can_execute_command(), events::menu_handler::change_side(), editor::editor_controller::change_unit_id(), ai::readonly_context_impl::check_attack_action(), actions::check_recall_location(), actions::check_recruit_location(), wb::move::check_validity(), wb::suppose_dead::check_validity(), ai::ai_default_rca::move_to_targets_phase::choose_move(), actions::shroud_clearer::clear_unit(), editor::mouse_action_unit::click_left(), game_logic::attack_map_callable::collect_possible_attacks(), events::menu_handler::continue_move(), ai::default_ai_context_impl::count_free_hexes_in_castle(), ai::ai_default_rca::aspect_attacks_base::do_attack_analysis(), ai::recall_result::do_check_after(), ai::recruit_result::do_check_after(), ai::stopunit_result::do_check_after(), ai::attack_result::do_check_before(), ai::attack_result::do_execute(), ai::move_result::do_execute(), ai::stopunit_result::do_execute(), do_replay_handle(), events::menu_handler::do_search(), editor::mouse_action_unit::drag_end_left(), display::draw_invalidated(), game_display::draw_movement_info(), events::menu_handler::end_unit_turn(), ai::ai_default_rca::goto_phase::evaluate(), ai::ai_default_rca::move_leader_to_keep_phase::evaluate(), ai::ai_default_rca::get_healing_phase::evaluate(), wb::attack::execute(), wb::move::execute(), ai::ai_default_rca::get_villages_phase::execute(), ai::ai_default_rca::leader_shares_keep_phase::execute(), ai::readwrite_context_impl::execute_attack_action(), editor::editor_controller::execute_command(), ai::formula_ai::execute_variant(), game_events::t_pump::filter_event(), game_board::find_unit(), pathfind::find_vacant_tile(), ai::ai_default_rca::get_villages_phase::find_villages(), game_board::find_visible_unit(), actions::shroud_clearer::fire_events(), footsteps_images(), ai::ai_default_rca::move_to_targets_phase::form_group(), lua_unit::get(), unit::get_abilities(), unit::get_ability_bool(), editor::editor_controller::get_action_state(), tod_manager::get_illuminated_time_of_day(), actions::get_recalls(), actions::get_recruits(), lua_unit::get_shared(), wb::manager::get_temp_move_unit(), wb::suppose_dead::get_unit(), game_events::entity_location::get_unit(), wb::move::get_unit(), ai::move_result::get_unit(), ai::stopunit_result::get_unit(), display_context::get_visible_unit(), game_board::has_visible_unit(), ai::helper_advance_unit(), basic_unit_filter_impl::internal_matches_filter(), game_lua_kernel::intf_find_cost_map(), game_lua_kernel::intf_find_path(), game_lua_kernel::intf_find_reach(), game_lua_kernel::intf_get_unit(), game_lua_kernel::intf_heal_unit(), game_lua_kernel::intf_kill(), game_lua_kernel::intf_teleport(), ai::default_recruitment::recruitment::is_enemy_in_radius(), events::menu_handler::kill_unit(), luaW_pushfaivariant(), pathfind::mark_route(), terrain_filter::match_internal(), unit_animation::matches(), wb::move::move(), editor::mouse_action_unit::move(), ai::ai_default_rca::move_to_targets_phase::move_group(), events::mouse_handler::move_unit_along_route(), actions::move_unit_and_record(), wb::manager::on_mouseover_change(), editor::editor_action_unit_delete::perform(), editor::editor_action_unit::perform_without_undo(), editor::editor_action_unit_replace::perform_without_undo(), editor::editor_action_unit_facing::perform_without_undo(), wb::manager::post_draw(), ai::readonly_context_impl::power_projection(), wb::manager::pre_draw(), lua_unit::put_map(), ai::ai_default_rca::move_to_targets_phase::rate_group(), actions::undo::move_action::redo(), wb::suppose_dead::remove_temp_modifier(), wb::move::remove_temp_modifier(), editor::editor_controller::rename_unit(), unit_display::reset_helpers(), game_lua_kernel::run_filter(), events::mouse_handler::select_hex(), wb::highlighter::set_mouseover_hex(), ai::formula_ai::shortest_path_calculator(), events::mouse_handler::show_attack_dialog(), events::mouse_handler::show_attack_options(), game_state::side_can_recruit_on(), ai::simulated_attack(), ai::simulated_stopunit(), attack_type::special_active(), wb::suppose_dead::suppose_dead(), SYNCED_COMMAND_HANDLER_FUNCTION(), under_leadership(), actions::undo::recruit_action::undo(), actions::undo::recall_action::undo(), actions::undo::move_action::undo(), unit_display::unit_attack(), display_context::unit_can_move(), editor::editor_controller::unit_description(), events::menu_handler::unit_hold_position(), unit_display::unit_recruited(), verify(), unit_display::wml_animation_internal(), and display_context::would_be_discovered().

unit_map::unit_iterator unit_map::find ( const map_location & loc )

Definition at line 292 of file map.cpp.

References lmap_, and self_check().

const_unit_iterator unit_map::find ( const map_location & loc ) const

inline

Definition at line 296 of file map.hpp.

References find().

Referenced by find().

const_unit_iterator unit_map::find ( size_t id ) const

inline

Definition at line 297 of file map.hpp.

References find().

Referenced by find().

unit_map::unit_iterator unit_map::find_first_leader ( int side )

Definition at line 306 of file map.cpp.

References begin(), end(), and i.

unit_map::unit_iterator unit_map::find_leader ( int side )

Definition at line 297 of file map.cpp.

References begin(), end(), and i.

Referenced by ai::ai_default_rca::move_leader_to_goals_phase::evaluate(), ai::ai_default_rca::get_villages_phase::evaluate(), ai::ai_default_rca::move_to_targets_phase::execute(), ai::ai_default_rca::get_villages_phase::execute(), unit_creator::find_location(), ai::default_ai_context_impl::find_targets(), events::menu_handler::get_title_suffix(), ai::formula_ai::get_value(), events::menu_handler::goto_leader(), ai::helper_check_village(), ai::readonly_context_impl::leader_can_reach_keep(), ai::readonly_context_impl::recalculate_move_maps(), events::menu_handler::scenario_settings_table(), game_display::scroll_to_leader(), game_board::side_change_controller(), game_board::side_drop_to(), events::menu_handler::status_table(), and game_board::team_is_defeated().

const_unit_iterator unit_map::find_leader ( int side ) const

inline

Definition at line 300 of file map.hpp.

References find_leader().

Referenced by find_leader().

std::vector< unit_map::unit_iterator > unit_map::find_leaders ( int side )

Definition at line 319 of file map.cpp.

References begin(), end(), and i.

Referenced by ai::ai_default_rca::move_leader_to_keep_phase::evaluate(), ai::default_recruitment::recruitment::evaluate(), ai::ai_default_rca::retreat_phase::evaluate(), ai::ai_default_rca::leader_shares_keep_phase::evaluate(), ai::default_recruitment::recruitment::execute(), ai::ai_default_rca::leader_shares_keep_phase::execute(), find_leaders(), and game_events::WML_HANDLER_FUNCTION().

std::vector< unit_map::const_unit_iterator > unit_map::find_leaders ( int side ) const

Definition at line 329 of file map.cpp.

References find_leaders().

bool unit_map::has_unit ( const unit *const u ) const

Is the unit in the map?

Precondition: u != nullptr

Parameters

u	Pointer to the unit to find.

Returns: True if found, false otherwise.

Definition at line 379 of file map.cpp.

References umap_.

std::pair< unit_map::unit_iterator, bool > unit_map::insert ( unit_ptr p )

Adds the unit to the map.

Inserts the unit pointed to by p into the unit_map.

Returns: std::pair<unit_iterator, bool> a bool indicating success and an iterator pointing to the new unit, or the unit already occupying location.

Note: It is 3 times as fast to attempt to insert a unit at l and check for success than it is to verify that the location is empty, insert the unit check the location for the unit.; If the unit::underlying_id is already in use, a new one will be generated.; The map takes ownership of the pointed object, only if it succeeds.

It needs to succeed on the insertion to the umap and to the lmap otherwise all operations are reverted.

Construct a unit_pod
Try insertion into the umap
Try insertion in the lmap and remove the umap entry on failure

The one oddity is that to facilitate non-invalidating iterators the list sometimes has nullptr pointers which should be used when they correspond to uids previously used.

Definition at line 126 of file map.cpp.

References DBG_NG, ERR_NG, error(), lmap_, make_unit_iterator(), unit::name(), unit_map::unit_pod::ref_count, self_check(), umap_, unit_map::unit_pod::unit, and map_location::valid().

Referenced by add(), ai::attack_analysis::analyze(), wb::recall::apply_temp_modifier(), wb::recruit::apply_temp_modifier(), BOOST_AUTO_TEST_CASE(), game_lua_kernel::intf_put_unit(), actions::place_recruit(), lua_unit::put_map(), wb::suppose_dead::remove_temp_modifier(), temporary_unit_mover::~temporary_unit_mover(), temporary_unit_placer::~temporary_unit_placer(), and temporary_unit_remover::~temporary_unit_remover().

bool unit_map::is_found ( const t_umap::const_iterator & i ) const

inlineprivate

Definition at line 408 of file map.hpp.

References umap_.

Referenced by is_valid(), make_const_unit_iterator(), and make_unit_iterator().

bool unit_map::is_found ( const t_lmap::const_iterator & i ) const

inlineprivate

Definition at line 409 of file map.hpp.

References lmap_.

bool unit_map::is_valid ( const t_umap::const_iterator & i ) const

inlineprivate

Definition at line 401 of file map.hpp.

References is_found().

Referenced by clear().

bool unit_map::is_valid ( const t_lmap::const_iterator & i ) const

inlineprivate

Definition at line 404 of file map.hpp.

References is_found().

template<typename X >

unit_map::const_unit_iterator unit_map::make_const_unit_iterator ( X const & i ) const

inlineprivate

Definition at line 417 of file map.hpp.

References is_found(), and umap_.

Referenced by begin(), and end().

template<typename X >

unit_map::unit_iterator unit_map::make_unit_iterator ( X const & i )

inlineprivate

Definition at line 412 of file map.hpp.

References is_found(), and umap_.

Referenced by begin(), end(), insert(), and move().

std::pair< unit_map::unit_iterator, bool > unit_map::move	(	const map_location &	src,
		const map_location &	dst
	)

Moves a unit from location src to location dst.

Returns: std::pair<unit_iterator, bool> a bool indicating success and an iterator pointing to the new unit, or the unit already occupying location.

Note: It is 3 times as fast to attempt to insert a unit at l and check for success than it is to verify that the location is empty, insert the unit check the location for the unit.

Definition at line 79 of file map.cpp.

References DBG_NG, i, lmap_, make_unit_iterator(), and self_check().

Referenced by ai::attack_analysis::analyze(), game_lua_kernel::intf_teleport(), editor::editor_action_unit_replace::perform_without_undo(), lua_unit::put_map(), actions::undo::move_action::redo(), ai::simulated_move(), temporary_unit_mover::temporary_unit_mover(), actions::undo::move_action::undo(), and temporary_unit_mover::~temporary_unit_mover().

size_t unit_map::num_iters ( ) const

Add up number of extant iterators

Definition at line 218 of file map.cpp.

References umap_.

Referenced by clear(), and swap().

unit_map & unit_map::operator= ( const unit_map & that )

Definition at line 46 of file map.cpp.

References swap().

std::pair< unit_map::unit_iterator, bool > unit_map::replace	(	const map_location &	l,
		const unit &	u
	)

Works like unit_map::add; but l is emptied first, if needed.

Returns: std::pair<unit_iterator, bool> a bool indicating success and an iterator pointing to the new unit, or the unit already occupying location.

Definition at line 207 of file map.cpp.

References add(), erase(), and self_check().

Referenced by unit_creator::add_unit(), advance_unit(), ai::helper_advance_unit(), lua_unit::put_map(), and SYNCED_COMMAND_HANDLER_FUNCTION().

bool unit_map::self_check ( ) const

inline

Checks invariants. For debugging purposes only. Doesn't do anything in non-debug mode.

Definition at line 380 of file map.hpp.

Referenced by add(), begin_core(), erase(), extract(), find(), insert(), move(), and replace().