# 
# patch "ChangeLog"
#  from [80ee6926d234f46a341bcc4c874056b57d5ebdbd]
#    to [57d565f3778c1c511828115215cbd8fd7e2555d7]
# 
# patch "change_set.cc"
#  from [c9554a69662fecf70ead4b8fec54eab5c355118a]
#    to [f45da9e6d6bc784324d6f606a12d21c34a6f306d]
# 
# patch "smap.hh"
#  from [8fb308c5059d3d572a078c96a6937ed989b425ec]
#    to [d4acf13bff4208cfe2d87cb93fcb182a290d77f8]
# 
--- ChangeLog
+++ ChangeLog
@@ -1,3 +1,10 @@
+2005-04-15  Matt Johnston  <address@hidden>
+
+	* change_set.cc (confirm_proper_tree): use bitsets rather than maps
+	for tracking set membership.
+	* smap.hh: return reverse iterators properly, iterate over the vector
+	rather than self in ensure_sort()
+
 2005-04-14  Derek Scherger  <address@hidden>
 
 	* database_check.cc (check_db): fail with N(...) when problems are
--- change_set.cc
+++ change_set.cc
@@ -18,6 +18,7 @@
 #include <boost/filesystem/path.hpp>
 #include <boost/shared_ptr.hpp>
 #include <boost/lexical_cast.hpp>
+#include <boost/dynamic_bitset.hpp>
 
 #include "basic_io.hh"
 #include "change_set.hh"
@@ -513,19 +514,30 @@
 static void
 confirm_proper_tree(path_state const & ps)
 {
-  std::map<tid,bool> confirmed;
-  I(ps.find(root_tid) == ps.end());
+  if (ps.empty())
+    return;
+
+  I(ps.find(root_tid) == ps.end()); // Note that this find() also ensures
+                                    // sortedness of ps.
+
+  tid min_tid = ps.begin()->first;
+  tid max_tid = ps.rbegin()->first;
+  size_t tid_range = max_tid - min_tid + 1;
+  
+  boost::dynamic_bitset<> confirmed(tid_range);
+  boost::dynamic_bitset<> ancs(tid_range);
+
   for (path_state::const_iterator i = ps.begin(); i != ps.end(); ++i)
     {
       tid curr = i->first;
       path_item item = i->second;
-      std::map<tid,bool> ancs; 
+      ancs.reset();
 
-      while (confirmed.find(curr) == confirmed.end())
+      while (confirmed.test(curr - min_tid) == false)
         {             
           sanity_check_path_item(item);
-          I(ancs.find(curr) == ancs.end());
-          ancs.insert(std::make_pair(curr,true));
+          I(ancs.test(curr - min_tid) == false);
+          ancs.set(curr - min_tid);
           if (path_item_parent(item) == root_tid)
             break;
           else
@@ -542,10 +554,8 @@
               I(path_item_type(item) == ptype_directory);
             }
         }
-      std::copy(ancs.begin(), ancs.end(), 
-                inserter(confirmed, confirmed.begin()));      
+      confirmed |= ancs;
     }
-  I(confirmed.find(root_tid) == confirmed.end());
 }
 
 static void
--- smap.hh
+++ smap.hh
@@ -86,11 +86,11 @@
         std::sort(vec.begin(), vec.end(), val_cmp);
         // make sure we don't have any duplicate entries
         const_iterator leader, lagged;
-        lagged = begin();
-        leader = begin();
-        I(leader != end());
+        lagged = vec.begin();
+        leader = vec.begin();
+        I(leader != vec.end());
         ++leader;
-        for (; leader != end(); ++lagged, ++leader)
+        for (; leader != vec.end(); ++lagged, ++leader)
           I(lagged->first != leader->first);
         damaged = false;
       }
@@ -165,13 +165,13 @@
   
   iterator begin() { return vec.begin(); }
   iterator end() { return vec.end(); }
-  iterator rbegin() { return vec.rbegin(); }
-  iterator rend() { return vec.rend(); }
+  reverse_iterator rbegin() { return vec.rbegin(); }
+  reverse_iterator rend() { return vec.rend(); }
 
   const_iterator begin() const { return vec.begin(); }
   const_iterator end() const { return vec.end(); }
-  const_iterator rbegin() const { return vec.rbegin(); }
-  const_iterator rend() const { return vec.rend(); }
+  const_reverse_iterator rbegin() const { return vec.rbegin(); }
+  const_reverse_iterator rend() const { return vec.rend(); }
 
   bool empty() const { return vec.empty(); }
   size_type size() const { return vec.size(); }