Index: src/Common/PersistentDisjointSet.h =================================================================== --- src/Common/PersistentDisjointSet.h (revision b21c77a0e211d9361763565a2eb5ef4330f2957b) +++ src/Common/PersistentDisjointSet.h (revision 184557ed94d1cdbdc6fd685e497e5375f8968a96) @@ -128,4 +128,7 @@ } } + + /// Non-initializing constructor; should call init() before use + PersistentDisjointSet( Mode m ) : data(), mode(m) {} PersistentDisjointSet( Mode m, Base&& b ) : data(), mode(m) { @@ -291,5 +294,5 @@ 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,15 +378,81 @@ } - /// Reports all members of a class to `out`; none if i does not exist in map - template - 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( 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( 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(); + 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( 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 + 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" ); Index: src/Common/PersistentMap.h =================================================================== --- src/Common/PersistentMap.h (revision b21c77a0e211d9361763565a2eb5ef4330f2957b) +++ src/Common/PersistentMap.h (revision 184557ed94d1cdbdc6fd685e497e5375f8968a96) @@ -114,4 +114,7 @@ } + /// 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,4 +423,42 @@ } } + + /// 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 filled with + /// the previous value if mutated, an empty option otherwise. + /// NOTE: when porting to C++17, this should work fine with std::optional + template + 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(); + 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( 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( 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 + void apply_to_all(F&& f) const { + for ( const auto& entry : rerooted() ) { f( entry.first, entry.second ); } + } }; Index: src/Common/option.h =================================================================== --- src/Common/option.h (revision 184557ed94d1cdbdc6fd685e497e5375f8968a96) +++ src/Common/option.h (revision 184557ed94d1cdbdc6fd685e497e5375f8968a96) @@ -0,0 +1,233 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// option.h -- +// +// Author : Aaron B. Moss +// Created On : Wed Jul 03 15:41:00 2018 +// Last Modified By : Aaron B. Moss +// Last Modified On : Wed Jul 03 15:41:00 2018 +// Update Count : 1 +// + +#pragma once + +#include +#include +#include + +#include "debug.h" + +using std::move; + +/// A class that may or may not hold a value of type T +/// Similar interface to the C++17 std::optional +template +class option { + typename std::aligned_storage::type storage; + bool filled; + + /// gets the underlying value (filled must be true) + T& get() { return reinterpret_cast(storage); } + const T& get() const { return reinterpret_cast(storage); } + + /// copy-initializes from a value + void init( const T& x ) { + new(&storage) T(x); + filled = true; + } + + /// move-initializes from a value + void init( T&& x ) { + new(&storage) T( move(x) ); + filled = true; + } + + /// destroys the underlying value (must be filled), sets filled to false + void destroy() { + get().~T(); + filled = false; + } + +public: + + option() : filled(false) {} + option( const T& x ) { init( x ); } + option( T&& x ) { init( move(x) ); } + option( const option& o ) : filled(o.filled) { if ( filled ) init( o.get() ); } + option( option&& o ) : filled(o.filled) { if ( filled ) init( move(o.get()) ); } + option& operator= ( const T& x ) { + if ( filled ) { get() = x; } else { init( x ); } + return *this; + } + option& operator= ( T&& x ) { + if ( filled ) { get() = move(x); } else { init( move(x) ); } + return *this; + } + option& operator= ( const option& o ) { + if ( filled ) { + if ( o.filled ) { + get() = o.get(); + } else { + destroy(); + } + } else if ( o.filled ) { + init( o.get() ); + } + return *this; + } + option& operator= ( option&& o ) { + if ( filled ) { + if ( o.filled ) { + get() = move(o.get()); + } else { + destroy(); + } + } else if ( o.filled ) { + init( move(o.get()) ); + } + return *this; + } + ~option() { if ( filled ) get().~T(); } + + void swap( option& o ) { + if ( filled ) { + if ( o.filled ) { + std::swap( get(), o.get() ); + } else { + o.init( move(get()) ); + destroy(); + } + } else if ( o.filled ) { + init( move(o.get()) ); + o.destroy(); + } + } + + /// Get contained value (unchecked) + T* operator->() { return &get(); } + const T* operator->() const { return &get(); } + T& operator*() & { return get(); } + const T& operator*() const& { return get(); } + T&& operator*() && { return move(get()); } + const T&& operator*() const&& { return move(get()); } + + /// Check if option is filled + constexpr explicit operator bool() const { return filled; } + constexpr bool has_value() const { return filled; } + + /// Get contained value (checked) + T& value() & { assume(filled, "checked get failed"); return get(); } + const T& value() const& { assume(filled, "checked get failed"); return get(); } + T&& value() && { assume(filled, "checked get failed"); return move(get()); } + const T&& value() const&& { assume(filled, "checked get failed"); return move(get()); } + + /// Get contained or default value + template + T value_or( U&& y ) const& { return filled ? get() : static_cast(std::forward(y)); } + template + T value_or( U&& y ) && { return filled ? move(get()) : static_cast(std::forward(y)); } + + /// Unset value if set + void reset() { if ( filled ) destroy(); } + + /// Construct value in-place (destroys existing value if needed) + template + void emplace( Args&&... args ) { + if ( filled ) { destroy(); } + new(&storage) T{ std::forward(args)... }; + filled = true; + } +}; + +template +bool operator== ( const option& a, const option& b ) { + return a ? (b && *a == *b) : !b; +} + +template +bool operator!= ( const option& a, const option& b ) { return !(a == b); } + +template +bool operator< ( const option& a, const option& b ) { + return b && (!a || *a < *b); +} + +template +bool operator<= ( const option& a, const option& b ) { + return !a || (b && *a <= *b); +} + +template +bool operator> ( const option& a, const option& b ) { return b < a; } + +template +bool operator>= ( const option& a, const option& b ) { return b <= a; } + +template +bool operator== ( const option& a, const T& x ) { + return a && *a == x; +} + +template +bool operator!= ( const option& a, const T& x ) { return !(a == x); } + +template +bool operator< ( const option& a, const T& x ) { + return !a || *a < x; +} + +template +bool operator<= ( const option& a, const T& x ) { + return !a || *a <= x; +} + +template +bool operator> ( const option& a, const T& x ) { + return a && *a > x; +} + +template +bool operator>= ( const option& a, const T& x ) { + return a && *a >= x; +} + +template +bool operator== ( const T& x, const option& b ) { return b == x; } + +template +bool operator!= ( const T& x, const option& b ) { return !(b == x); } + +template +bool operator< ( const T& x, const option& b ) { return b > x; } + +template +bool operator<= ( const T& x, const option& b ) { return b >= x; } + +template +bool operator> ( const T& x, const option& b ) { return b < x; } + +template +bool operator>= ( const T& x, const option& b ) { return b <= x; } + +template +option make_option( Args&&... args ) { + option o; + o.emplace( std::forward(args)... ); + return o; +} + +namespace std { + template + void swap( option& a, option& b ) { a.swap(b); } + + template + struct hash< option > { + size_t operator() ( const option& a ) { + return a ? hash{}( *a ) : size_t(1); + } + }; +}