Author: silene
Date: Thu May 7 00:02:21 2009
New Revision: 35463
URL: http://svn.gna.org/viewcvs/wesnoth?rev=35463&view=rev
Log:
Split the lower_bound algorithm away. Added an insert function.
Modified:
trunk/src/pathfind.cpp
trunk/src/pathfind.hpp
Modified: trunk/src/pathfind.cpp
URL:
http://svn.gna.org/viewcvs/wesnoth/trunk/src/pathfind.cpp?rev=35463&r1=35462&r2=35463&view=diff
==============================================================================
--- trunk/src/pathfind.cpp (original)
+++ trunk/src/pathfind.cpp Thu May 7 00:02:21 2009
@@ -267,20 +267,32 @@
}
}
-paths::dest_vect::const_iterator paths::dest_vect::find(const map_location
&loc) const
-{
- size_t sz = size(), pos = 0;
+static paths::dest_vect::iterator lower_bound(paths::dest_vect &v, const
map_location &loc)
+{
+ size_t sz = v.size(), pos = 0;
while (sz)
{
- if ((*this)[pos + sz / 2].curr < loc) {
+ if (v[pos + sz / 2].curr < loc) {
pos = pos + sz / 2 + 1;
sz = sz - sz / 2 - 1;
} else sz = sz / 2;
}
-
- const_iterator i_end = end(), i = begin() + pos;
+ return v.begin() + pos;
+}
+
+paths::dest_vect::const_iterator paths::dest_vect::find(const map_location
&loc) const
+{
+ const_iterator i = lower_bound(const_cast<dest_vect &>(*this), loc),
i_end = end();
if (i != i_end && i->curr != loc) i = i_end;
return i;
+}
+
+void paths::dest_vect::insert(const map_location &loc)
+{
+ iterator i = lower_bound(*this, loc), i_end = end();
+ if (i != i_end && i->curr == loc) return;
+ paths::step s = { loc, map_location(), 0 };
+ std::vector<step>::insert(i, s);
}
/**
Modified: trunk/src/pathfind.hpp
URL:
http://svn.gna.org/viewcvs/wesnoth/trunk/src/pathfind.hpp?rev=35463&r1=35462&r2=35463&view=diff
==============================================================================
--- trunk/src/pathfind.hpp (original)
+++ trunk/src/pathfind.hpp Thu May 7 00:02:21 2009
@@ -115,6 +115,7 @@
{
const_iterator find(const map_location &) const;
bool contains(const map_location &) const;
+ void insert(const map_location &);
std::vector<map_location> get_path(const const_iterator &)
const;
};
dest_vect destinations;
_______________________________________________
Wesnoth-commits mailing list
[email protected]
https://mail.gna.org/listinfo/wesnoth-commits
