Changeset 184557e for src/Common

Timestamp:

Jul 6, 2018, 5:10:14 PM (6 years ago)

Author:

Aaron Moss <a3moss@…>

Branches:

new-env

Children:

5c14030

Parents:

b21c77a

Message:

First draft of persistent-hash-based TypeEnvironment?

Location:

src/Common

Files:

• PersistentDisjointSet.h (modified) (3 diffs)
• PersistentMap.h (modified) (2 diffs)
• option.h (added)

src/Common/PersistentDisjointSet.h

@@ -128 +128 @@
                 }
         }
+
+        /// Non-initializing constructor; should call init() before use
+        PersistentDisjointSet( Mode m ) : data(), mode(m) {}
 
         PersistentDisjointSet( Mode m, Base&& b ) : data(), mode(m) {
@@ -291 +294 @@
         size_type count(Elm i) const { return rerooted().count( i ); }
 
-        /// Finds root for element i, assertfs i is present
+        /// Finds root for element i, undefined behaviour if i is not present
         Elm find(Elm i) const {
                 const Base& self = rerooted();
@@ -375 +378 @@
         }
 
-        /// Reports all members of a class to `out`; none if i does not exist in map
-        template<typename OutputIterator>
-        void find_class(Elm i, OutputIterator&& out) const {
+private:
+        /// Removes the children of the tree rooted at `root` as `root_node`, returning a new 
+        /// uninitialized node and editing `next_edit` to point toward this new node.
+        static Self* remove_children(Elm root, Node& root_node, Base& base_map, Self* next_edit) {
+                // Invariant: root.next is *always* a pointer to a leaf of the most-recently added
+                // subtree.
+                //
+                // Proof: By induction on height:
+                // * height == 0: root.next == root, trivially true
+                // * added.height < root.height: true by ind. hyp.
+                // * added.height == root.height: no node may have a child the same height, ergo 
+                //   property holds for added, therefore root.
+                //
+                // Corollary: next of most-recently-added subtree root is previously added subtree
+
+                // remove all subtrees
+                while ( root != root_node.next ) {
+                        // find added child
+                        auto it = base_map.find( root_node.next );
+                        while ( it->second.parent != root ) it = base_map.find( it->second.parent );
+                        Elm added = it->first;
+                        Node& added_node = it->second;
+
+                        // unlink subtree and set up previous map as ADDTO new map
+                        std::swap( root_node.next, added_node.next );
+                        Self* new_edit = new Self{ BASE };
+                        next_edit->init<AddTo>( new_edit, root, added, false );  // assume unchanged root height
+                        next_edit->mode = ADDTO;
+
+                        // remove subtree children from map
+                        next_edit = remove_children( added, added_node, base_map, new_edit );
+
+                        // remove subtree root from map and set up previous map as ADD to new map
+                        base_map.erase( added );
+                        new_edit = new Self{ BASE };
+                        next_edit->init<Add>( new_edit, added );
+                        next_edit->mode = ADD;
+
+                        next_edit = new_edit;
+                }
+
+                return next_edit;
+        }
+
+public:
+        /// Removes all elements of a class given by its root; returns updated map.
+        Self* remove_class(Elm root) {
+                reroot();
+
+                // remove map from self
+                Base base_map = take_as<Base>();
+                reset_as_base();
+
+                // find root node and remove children
+                auto it = base_map.find( root );
+                assertf(it != base_map.end(), "root node must exist in map");
+                Self* next_edit = remove_children( root, it->second, base_map, this);
+
+                // root is alone in class, remove from map
+                base_map.erase( root );
+                Self* ret = new Self{ BASE, std::move(base_map) };
+                // reinitialize previous node as ADD to new map
+                next_edit->init<Add>( ret, root );
+                next_edit->mode = ADD;
+
+                return ret;
+        }
+
+        /// Applies `f` to all members of a class containing `i` (undefined behaviour if not present).
+        /// `f` should take members by const reference or copy
+        template<typename F>
+        void apply_to_class(Elm i, F&& f) const {
                 const Base& self = rerooted();
-
-                // skip empty classes
-                if ( ! self.count( i ) ) return;
 
                 Elm crnt = i;
                 do {
-                        *out++ = crnt;
+                        f( crnt );
                         auto it = self.find( crnt );
                         assertf( it != self.end(), "current node must exist in base" );

src/Common/PersistentMap.h

@@ -114 +114 @@
         }
 
+        /// Non-initializing constructor; should call init() before use
+        PersistentMap( Mode m ) : data(), mode(m) {}
+
         PersistentMap( Mode m, Base&& b ) : data(), mode(m) {
                 assertf(m == BASE, "invalid mode");
@@ -420 +423 @@
                 }
         }
+
+        /// Applies the function `f` to all elements of the map, returning a pointer to the updated map.
+        /// `f` should take two parameters, `const Key&` and `Val&`, returning option<Val> filled with 
+        /// the previous value if mutated, an empty option<Val> otherwise.
+        /// NOTE: when porting to C++17, this should work fine with std::optional
+        template<typename F>
+        Self* apply_to_all(F&& f) {
+                // reset to root and exit early if no change
+                if ( rerooted().empty() ) return this;
+
+                // remove map from self
+                Base base_map = take_as<Base>();
+                reset_as_base();
+
+                // apply all edits
+                Self* next_edit = this;
+                for ( auto& entry : base_map ) {
+                        auto res = f( entry.first, entry.second );
+                        if ( res ) {
+                                // entry has been mutated; reset next_edit node as mutation
+                                Self* new_node = new Self{ BASE };
+                                next_edit->init<Ins>( new_node, entry.first, *std::move(res) );
+                                next_edit->mode = UPD;
+                                next_edit = new_node;
+                        }
+                }
+
+                // set map into final node and return
+                next_edit->init<Base>( std::move(base_map) );
+                return next_edit;
+        }
+
+        /// Applies the function `f` to all elements of the map.
+        /// `f` should take two parameters, `const Key&` and `const Val&`.
+        template<typename F>
+        void apply_to_all(F&& f) const {
+                for ( const auto& entry : rerooted() ) { f( entry.first, entry.second ); }
+        }
 };