# 
# add_file "roster3.cc"
# 
# add_file "roster3.hh"
# 
# patch "cset.hh"
#  from [b4dfecf288821a2e5b7ccae2b97328af59b17da9]
#    to [9e59f30c4d529d3c406e32cc2ebbf52499fb3d93]
# 
# patch "roster3.cc"
#  from []
#    to [49d706cac36843bc95469bc82a71741d31d78353]
# 
# patch "roster3.hh"
#  from []
#    to [53c429f5d8c02cd6f0a6ba8a273b0b7bcc738ba6]
# 
========================================================================
--- cset.hh	b4dfecf288821a2e5b7ccae2b97328af59b17da9
+++ cset.hh	9e59f30c4d529d3c406e32cc2ebbf52499fb3d93
@@ -42,7 +42,7 @@
   // Modifying elements in-place
   virtual void apply_delta(split_path const & pth, 
                            file_id const & old_id, 
-                           file_id const & new_new) = 0;
+                           file_id const & new_id) = 0;
   virtual void clear_attr(split_path const & pth,
                           attr_name const & name) = 0;
   virtual void set_attr(split_path const & pth,
========================================================================
--- roster3.cc	
+++ roster3.cc	49d706cac36843bc95469bc82a71741d31d78353
@@ -0,0 +1,227 @@
+// copyright (C) 2005 nathaniel smith <address@hidden>
+// all rights reserved.
+// licensed to the public under the terms of the GNU GPL (>= 2)
+// see the file COPYING for details
+
+#include "roster3.hh"
+
+// FIXME: move this to a header somewhere
+template <typename T, typename K>
+safe_erase(T & container, K const & key)
+{
+  I(container.erase(key));
+}
+template <typename T, typename V>
+safe_insert(T & container, V const & val)
+{
+  I(container.insert(val).second);
+}
+
+// FIXME: we assume split and join paths always start with a null component
+
+node_id
+roster_t::lookup(split_path const & sp) const
+{
+  node_id nid = the_null_node;
+  for (split_path::const_iterator i = sp.begin(); i != sp.end(); ++i)
+    nid = lookup(nid, *i);
+  return nid;
+}
+
+node_id
+roster_t::lookup(node_id parent, path_component child) const
+{
+  if (null_node(parent))
+    {
+      I(null_name(child));
+      I(!null_node(root_dir));
+      return root_dir;
+    }
+  dir_map & dir = children(parent);
+  dir_map::const_iterator i = dir.find(child);
+  I(i != dir.end());
+  return i->second;
+}
+
+node_id
+roster_t::get_name(node_id nid, split_path & sp) const
+{
+  sp.clear();
+  while (!null_node(nid))
+    {
+      node_t & n = element(nid);
+      sp.push_back(n.name);
+      nid = n.parent;
+    }
+  std::reverse(sp.begin(), sp.end());
+}
+
+dir_map & children
+roster_t::children(node_id nid)
+{
+  std::map<node_id, dir_map>::iterator i = children_map.find(nid);
+  I(i != children_map.end());
+  return *i;
+}
+
+node_t & node(node_id nid)
+{
+  std::map<node_id, node_t>::iterator i = nodes.find(nid);
+  I(i != nodes.end());
+  return *i;
+}
+
+void replace_node_id(node_id from, node_id to)
+{
+  {
+    std::map<node_id, node_t>::iterator i = nodes.find(from);
+    I(i != nodes.end());
+    safe_insert(nodes, std::make_pair(to, i->second));
+    nodes.erase(i);
+  }
+  node_t n = node(to);
+  if (root_dir == from)
+    root_dir = to;
+  else
+    {
+      dir_map & dir = children(n.parent);
+      dir_map::iterator i = dir.find(n.name);
+      I(i != dir.end());
+      I(i->second == from);
+      i->second = to;
+    }
+  if (n.type == etype_dir)
+    {
+      std::map<node_id, dir_map>::iterator i = children_map.find(from);
+      I(i != children_map.end());
+      for (dir_map::iterator j = i->second.begin(); j != i->second.end(); ++j)
+        {
+          node_t & child_n = node(j->second);
+          I(child_n.parent == from);
+          child_n.parent = to;
+        }
+      safe_insert(children_map, std::make_pair(to, i->second));
+      children_map.erase(i);
+    }
+}
+
+static inline void
+dirname_basename(split_path const & sp,
+                 split_path & dirname, path_component & basename)
+{
+  I(!sp.empty());
+  split_path::const_iterator penultimate = sp.end();
+  --penultimate;
+  dirname = split_path(sp.begin(), penultimate);
+  basename = *penultimate;
+}
+
+// FIXME: we assume split and join paths always start with a null component
+// split_path [] means the_null_component (which is the parent of the root dir)
+// [""] means the root dir
+// ["", "foo"] means root dir's sub-element "foo"
+// etc.
+
+void
+roster_t::detach_node(split_path const & src)
+{
+  node_id nid = lookup(src);
+  node_t & n = node(nid);
+  // for now, the root dir can be created, but cannot be removed
+  I(nid != root_dir);
+  node_id parent = n.parent;
+  safe_erase(children(parent), nid);
+  n.parent = the_null_node;
+  n.name = the_null_component;
+  if (n.type == ntype_dir)
+    {
+      std::map<esoul, dir_map>::iterator i = children_map.find(es);
+      I(i != children_map.end());
+      I(i->second.empty());
+      children_map.erase(i);
+    }
+}
+
+void
+roster_t::drop_detached_node(node_id nid)
+{
+  safe_erase(nodes, nid);
+}
+
+node_id
+roster_t::create_dir_node(node_id_source & nis)
+{
+  node_id nid = nis.next();
+  safe_insert(nodes, std::make_pair(node_t(ntype_dir), n));
+  return nid;
+}
+
+node_id
+roster_t::create_file_node(file_id const & content, node_id_source & nis)
+{
+  node_id nid = nis.next();
+  safe_insert(nodes, std::make_pair(node_t(ntype_file, content), n));
+  return nid;
+}
+
+// FIXME: we assume split and join paths always start with a null component
+// split_path [] means the_null_component (which is the parent of the root dir)
+// [""] means the root dir
+// ["", "foo"] means root dir's sub-element "foo"
+// etc.
+
+void
+roster_t::attach_node(node_id nid, split_path const & dst)
+{
+  split_path dirname;
+  path_component basename;
+  dirname_basename(dst, dirname, basename);
+  node_id parent = lookup(dirname);
+  node_t & n = node(nid);
+  if (null_node(parent))
+    {
+      // this is the root dir
+      root_dir = nid;
+      I(n.type == ntype_dir);
+    }
+  else
+    safe_insert(children(parent), std::make_pair(basename, nid));
+  if (n.type == ntype_dir)
+    safe_insert(children_map, std::make_pair(nid, dir_map()));
+}
+
+void
+roster_t::apply_delta(split_path const & pth,
+                      file_id const & old_id,
+                      fild_id const & new_id);
+{
+  node_id nid = lookup(pth);
+  node_t & n = node(nid);
+  I(n.type = ntype_file);
+  I(n.content == old_id);
+  I(n.content != new_id);
+  n.content = new_id;
+}
+
+void
+roster_t::clear_attr(split_path const & pth,
+                     attr_name const & name)
+{
+  node_id nid = lookup(pth);
+  node_t & n = node(nid);
+  safe_erase(n.attrs, name);
+}
+
+void
+roster_t::set_attr(split_path const & pth,
+                   attr_name const & name,
+                   attr_val const & val)
+{
+  node_id nid = lookup(pth);
+  node_t & n = node(nid);
+  std::map<attr_key, attr_value>::iterator i = n.attrs.find(name);
+  I(i != n.attrs.end());
+  I(i->second != val);
+  i->second = val;
+}
+
========================================================================
--- roster3.hh	
+++ roster3.hh	53c429f5d8c02cd6f0a6ba8a273b0b7bcc738ba6
@@ -0,0 +1,166 @@
+#ifndef __ROSTER_HH__
+#define __ROSTER_HH__
+
+// copyright (C) 2005 nathaniel smith <address@hidden>
+// all rights reserved.
+// licensed to the public under the terms of the GNU GPL (>= 2)
+// see the file COPYING for details
+
+#include <vector>
+#include <map>
+
+#include "vocab.hh"
+#include "numeric_vocab.hh"
+#include "paths.hh"
+#include "cset.hh"
+
+const node_id the_null_node = 0;
+const node_id first_node = 1;
+inline bool null_node(node_id n)
+{
+  return n == the_null_node;
+}
+const node_id first_temp_node = widen<node_id, int>(1) << (sizeof(node_id) * 8 - 1);
+inline bool temp_node(node_id n)
+{
+  return n & first_temp_node;
+}
+
+struct node_id_source
+{
+  virtual node_id next() = 0;
+}
+
+struct temp_node_id_source : public node_id_source
+{
+  temp_node_id_source() : curr(first_temp_node) {}
+  virtual node_id next()
+  {
+    node_id n = curr++;
+    I(temp_node(n));
+    return n;
+  }
+  node_id curr;
+};
+
+///////////////////////////////////////////////////////////////////
+
+
+typedef enum { ntype_dir, ntype_file } ntype;
+
+struct node_t
+{
+  node_t(ntype type)
+    : parent(the_null_node), name(the_null_component), type(type)
+    {
+      I(type) == ntype_dir;
+    }
+  node_t(ntype type, file_id const & content)
+    : parent(the_null_node), name(the_null_component), type(type),
+      content(content)
+    {
+      I(type) == ntype_file;
+    }
+  ntype type;
+  revision_id birth_revision;
+  // this is null iff this is a root dir
+  node_id parent;
+  // this is null iff this is a root dir
+  path_component name;
+  file_id content;
+  std::map<attr_key, attr_value> attrs;
+};
+
+typedef std::map<path_component, node_id> dir_map;
+
+class roster_t
+{
+public:
+  roster_t() : root_dir(the_null_node) {}
+  node_id lookup(split_path const & sp) const;
+  node_id lookup(node_id parent, path_component child) const;
+  void get_name(node_id n, split_path & sp) const;
+  dir_map & children(node_id n);
+  node_t & node(node_id n);
+  void replace_node_id(node_id from, node_id to);
+
+  // editable_tree methods
+  node_id detach_node(split_path const & src);
+  void drop_detached_node(node_id n);
+  node_id create_dir_node(node_id_source & nid);
+  node_id create_file_node(file_id const & content,
+                           node_id_source & nid);
+  void attach_node(node_id n, split_path const & dst);
+  void apply_delta(split_path const & pth, 
+                   file_id const & old_id, 
+                   file_id const & new_new);
+  void clear_attr(split_path const & pth,
+                  attr_name const & name);
+  void set_attr(split_path const & pth,
+                attr_name const & name,
+                attr_val const & val);
+private:
+  std::map<node_id, node_t> nodes;
+  std::map<node_id, dir_map> children_map;
+  node_id root_dir;
+};
+
+class editable_roster : public editable_tree
+{
+public:
+  editable_roster(roster_t & r, node_id_source & nis)
+    : r(r), nis(nis)
+    {}
+
+  // editable_tree methods
+  virtual node_id detach_node(split_path const & src)
+  {
+    return r.detch_node(src);
+  }
+  virtual void drop_detached_node(node_id nid)
+  {
+    r.drop_detached_node(nid);
+  }
+  virtual node_id create_dir_node()
+  {
+    node_id nid = r.create_dir_node(nis);
+    new_nodes.insiert(nid);
+    return nid;
+  }
+  virtual node_id create_file_node(file_id const & content)
+  {
+    node_id nid = r.create_file_node(content, nis);
+    new_nodes.insiert(nid);
+    return nid;
+  }
+  virtual void attach_node(node_id nid, split_path const & dst)
+  {
+    r.attach_node(nid, dst);
+    touched_nodes.insert(nid);
+  }
+  virtual void apply_delta(split_path const & pth, 
+                           file_id const & old_id, 
+                           file_id const & new_id)
+  {
+    r.apply_delta(pth, old_id, new_id);
+    touched_nodes.insert(r.lookup(pth));
+  }
+  virtual void clear_attr(split_path const & pth,
+                          attr_name const & name)
+  {
+    r.clear_attr(pth, name);
+    touched_nodes.insert(r.lookup(pth));
+  }
+  virtual void set_attr(split_path const & pth,
+                        attr_name const & name,
+                        attr_val const & val)
+  {
+    r.set_attr(pth, name, val);
+    touched_nodes.insert(r.lookup(pth));
+  }
+private:
+  roster_t & r;
+  node_id_source & nis;
+  std::set<node_id> new_nodes;
+  std::set<node_id> touched_nodes;
+};