|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r79900 - in sandbox/metagraph: boost/metagraph/angly boost/metagraph/mpl_graph libs/metagraph/example
From: gordon_at_[hidden]
Date: 2012-08-07 06:18:38
Author: gordon.woodhull
Date: 2012-08-07 06:18:37 EDT (Tue, 07 Aug 2012)
New Revision: 79900
URL: http://svn.boost.org/trac/boost/changeset/79900
Log:
binomial heap impl; reformatting
Added:
sandbox/metagraph/boost/metagraph/mpl_graph/binomial_heap.hpp (contents, props changed)
sandbox/metagraph/libs/metagraph/example/binomial_heap.cpp (contents, props changed)
Text files modified:
sandbox/metagraph/boost/metagraph/angly/dfa.hpp | 11 ++++---
sandbox/metagraph/boost/metagraph/angly/dfa_lang.hpp | 56 ++++++++++++++++++++--------------------
2 files changed, 34 insertions(+), 33 deletions(-)
Modified: sandbox/metagraph/boost/metagraph/angly/dfa.hpp
==============================================================================
--- sandbox/metagraph/boost/metagraph/angly/dfa.hpp (original)
+++ sandbox/metagraph/boost/metagraph/angly/dfa.hpp 2012-08-07 06:18:37 EDT (Tue, 07 Aug 2012)
@@ -259,7 +259,7 @@
mpl::push_front<parent,
typename
create_frame<typename mpl::apply<typename get_transition_pre_action<typename PropFn::template apply<Match>::type>::type,
- typename get_frame_data<frame>::type,
+ typename get_frame_data<frame>::type,
typename get_state_start_data<typename PropFn::template apply<RecurseRule>::type>::type>::type,
RecurseRule,
typename mpl::begin<inner_seq>::type,
@@ -306,7 +306,8 @@
CurrIter,
EndIter>::type,
typename //end-frame
- create_frame<void,utterly_done_state, void, void, mpl::_2>::type> type;
+ create_frame<void,utterly_done_state, void, void, mpl::_2>::type
+ > type;
};
template<typename Stack>
@@ -345,9 +346,9 @@
typedef detail::dfa_end end;
};
- template<typename DFA, typename StartState, typename Input, typename PropFn = mpl::_1>
- struct run_dfa :
- mpl::fold<dfa_sequence<DFA, StartState, Input, typename mpl::lambda<PropFn>::type>,
+ template<typename DFA, typename StartState, typename Input, typename PropFn = mpl::_1>
+ struct run_dfa :
+ mpl::fold<dfa_sequence<DFA, StartState, Input, typename mpl::lambda<PropFn>::type>,
void,
mpl::_2 > // not really a fold, just iterate until done and return final data
{};
Modified: sandbox/metagraph/boost/metagraph/angly/dfa_lang.hpp
==============================================================================
--- sandbox/metagraph/boost/metagraph/angly/dfa_lang.hpp (original)
+++ sandbox/metagraph/boost/metagraph/angly/dfa_lang.hpp 2012-08-07 06:18:37 EDT (Tue, 07 Aug 2012)
@@ -72,43 +72,43 @@
// types for transitions
struct dfa_a_state :
dfa_transition<match_token<state<> >,
- state_name,
- // rebuild dfa data, pushing state onto both state seq and stmap
- mpl::pair<mpl::push_back<mpl::first<mpl::_1>,
- mpl::pair<s_name<mpl::_2>,
- s_transitions<mpl::_2> > >,
- mpl::push_back<mpl::copy<s_stmap<mpl::_2>,
- mpl::back_inserter<mpl::second<mpl::_1> > >,
- mpl::pair<s_name<mpl::_2>,
- detail::apply_seq_q<dfa_state>
- ::apply<s_args<mpl::_2> > > > > > {};
+ state_name,
+ // rebuild dfa data, pushing state onto both state seq and stmap
+ mpl::pair<mpl::push_back<mpl::first<mpl::_1>,
+ mpl::pair<s_name<mpl::_2>,
+ s_transitions<mpl::_2> > >,
+ mpl::push_back<mpl::copy<s_stmap<mpl::_2>,
+ mpl::back_inserter<mpl::second<mpl::_1> > >,
+ mpl::pair<s_name<mpl::_2>,
+ detail::apply_seq_q<dfa_state>
+ ::apply<s_args<mpl::_2> > > > > > {};
struct state_name_trans :
dfa_transition<mpl::always<mpl::true_>,
- void,
- mpl::vector4<mpl::_2, mpl::vector<>, mpl::vector<>, mpl::vector<> > > {};
+ void,
+ mpl::vector4<mpl::_2, mpl::vector<>, mpl::vector<>, mpl::vector<> > > {};
struct state_finish_trans :
dfa_transition<mpl::always<mpl::true_>,
- void,
- mpl::vector4<s_name<mpl::_1>, mpl::vector1<mpl::_2>, mpl::vector<>, mpl::vector<> > > {};
+ void,
+ mpl::vector4<s_name<mpl::_1>, mpl::vector1<mpl::_2>, mpl::vector<>, mpl::vector<> > > {};
struct state_data_trans :
dfa_transition<mpl::always<mpl::true_>,
- void,
- mpl::vector4<s_name<mpl::_1>,
- mpl::push_back<s_args<mpl::_1>, mpl::_2>,
- mpl::vector<>, mpl::vector<> > > {};
+ void,
+ mpl::vector4<s_name<mpl::_1>,
+ mpl::push_back<s_args<mpl::_1>, mpl::_2>,
+ mpl::vector<>, mpl::vector<> > > {};
struct state_transition :
dfa_transition<match_token<transition<> >,
- transition_name,
- // rebuild state data, pushing new transition onto transitions and stmap
- mpl::vector4<s_name<mpl::_1>, s_args<mpl::_1>,
- mpl::push_back<s_transitions<mpl::_1>,
- mpl::pair<t_name<mpl::_2>, t_target<mpl::_2> > >,
- mpl::push_back<s_stmap<mpl::_1>,
- mpl::pair<t_name<mpl::_2>,
- detail::apply_seq_q<dfa_transition>
- ::apply<t_args<mpl::_2> > > > >
- > {};
+ transition_name,
+ // rebuild state data, pushing new transition onto transitions and stmap
+ mpl::vector4<s_name<mpl::_1>, s_args<mpl::_1>,
+ mpl::push_back<s_transitions<mpl::_1>,
+ mpl::pair<t_name<mpl::_2>, t_target<mpl::_2> > >,
+ mpl::push_back<s_stmap<mpl::_1>,
+ mpl::pair<t_name<mpl::_2>,
+ detail::apply_seq_q<dfa_transition>
+ ::apply<t_args<mpl::_2> > > > >
+ > {};
struct state_name_transition : state_transition {};
struct state_finish_transition : state_transition {};
struct transition_name_trans :
Added: sandbox/metagraph/boost/metagraph/mpl_graph/binomial_heap.hpp
==============================================================================
--- (empty file)
+++ sandbox/metagraph/boost/metagraph/mpl_graph/binomial_heap.hpp 2012-08-07 06:18:37 EDT (Tue, 07 Aug 2012)
@@ -0,0 +1,146 @@
+// Copyright 2012 Gordon Woodhull
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_METAGRAPH_MPL_BINOMIAL_HEAP_HPP_INCLUDED
+#define BOOST_METAGRAPH_MPL_BINOMIAL_HEAP_HPP_INCLUDED
+
+// adapted from Chris Okasaki's Purely Functional Data Structures
+
+#include <boost/mpl/eval_if.hpp>
+#include <boost/mpl/if.hpp>
+#include <boost/mpl/less_equal.hpp>
+#include <boost/mpl/less.hpp>
+#include <boost/mpl/next_prior.hpp>
+#include <boost/mpl/push_front.hpp>
+#include <boost/mpl/fold.hpp>
+#include <boost/mpl/empty.hpp>
+#include <boost/mpl/next_prior.hpp>
+#include <boost/mpl/list.hpp>
+#include <boost/mpl/front.hpp>
+#include <boost/mpl/pop_front.hpp>
+#include <boost/mpl/int.hpp>
+#include <boost/mpl/identity.hpp>
+#include <boost/mpl/pair.hpp>
+#include <boost/mpl/identity.hpp>
+#include <boost/mpl/reverse.hpp>
+
+namespace boost {
+ namespace metagraph {
+ namespace mpl_graph {
+
+ template<typename Rank, typename Element, typename Children>
+ struct node {
+ typedef Rank rank;
+ typedef Element element;
+ typedef Children children;
+ };
+
+ template<typename Node>
+ struct rank {
+ typedef typename Node::rank type;
+ };
+ template<typename Node>
+ struct root {
+ typedef typename Node::element type;
+ };
+ template<typename Node>
+ struct children {
+ typedef typename Node::children type;
+ };
+
+ template<typename Node1, typename Node2>
+ struct link : // assumes elements are integral constant wrappers
+ mpl::if_<typename mpl::less_equal<typename root<Node1>::type,
+ typename root<Node2>::type>::type,
+ node<typename mpl::next<typename rank<Node1>::type>::type,
+ typename root<Node1>::type,
+ typename mpl::push_front<typename children<Node1>::type,
+ Node2>::type >,
+ node<typename mpl::next<typename rank<Node1>::type>::type,
+ typename root<Node2>::type,
+ typename mpl::push_front<typename children<Node2>::type,
+ Node1>::type > > {};
+
+ template<typename Tree, typename Heap> struct ins_tree;
+
+ template<typename Tree, typename Heap>
+ struct ins_tree_helper :
+ mpl::eval_if<typename mpl::less<typename rank<Tree>::type,
+ typename rank<typename mpl::front<Heap>::type>::type>,
+ mpl::push_front<Heap, Tree>,
+ ins_tree<typename link<Tree, typename mpl::front<Heap>::type>::type,
+ typename mpl::pop_front<Heap>::type> > {};
+
+ template<typename Tree, typename Heap>
+ struct ins_tree :
+ mpl::eval_if<typename mpl::empty<Heap>::type,
+ mpl::push_front<Heap, Tree>,
+ ins_tree_helper<Tree, Heap> > {};
+
+ template<typename Element, typename Heap>
+ struct insert : ins_tree<node<mpl::int_<0>, Element, mpl::list<> >, Heap> {};
+
+ template<typename Heap1, typename Heap2> struct merge;
+
+ template<typename Heap1, typename Heap2>
+ struct merge_helper {
+ typedef typename mpl::front<Heap1>::type head1;
+ typedef typename mpl::front<Heap2>::type head2;
+ typedef typename mpl::eval_if<mpl::less<typename rank<head1>::type, typename rank<head2>::type>,
+ mpl::push_front<typename merge<typename mpl::pop_front<Heap1>::type, Heap2>::type,
+ head1>,
+ mpl::eval_if<mpl::less<typename rank<head2>::type, typename rank<head1>::type>,
+ mpl::push_front<typename merge<Heap1, typename mpl::pop_front<Heap2>::type>::type,
+ head2>,
+ ins_tree<typename link<head1, head2>::type,
+ typename merge<typename mpl::pop_front<Heap1>::type,
+ typename mpl::pop_front<Heap2>::type>::type> > >::type type;
+ };
+
+ template<typename Heap1, typename Heap2>
+ struct merge :
+ mpl::eval_if<typename mpl::empty<Heap1>::type,
+ mpl::identity<Heap2>,
+ mpl::eval_if<typename mpl::empty<Heap2>::type,
+ mpl::identity<Heap1>,
+ merge_helper<Heap1, Heap2> > > {};
+
+ template<typename Heap> struct remove_min_tree;
+
+ template<typename Heap>
+ struct remove_min_tree_helper {
+ typedef typename mpl::front<Heap>::type head;
+ typedef typename mpl::pop_front<Heap>::type tail;
+ typedef typename remove_min_tree<tail>::type rest;
+ typedef typename mpl::first<rest>::type rest_tree;
+ typedef typename mpl::second<rest>::type rest_list;
+ typedef typename mpl::if_<typename mpl::less_equal<typename root<head>::type,
+ typename root<rest_tree>::type>,
+ mpl::pair<head, tail>,
+ mpl::pair<rest_tree, typename mpl::push_front<rest_list, head>::type> >::type type;
+ };
+ template<typename Heap>
+ struct remove_min_tree {
+ typedef typename mpl::front<Heap>::type head;
+ typedef typename mpl::pop_front<Heap>::type tail;
+ typedef typename mpl::eval_if<typename mpl::empty<tail>::type,
+ mpl::pair<head, mpl::list<> >,
+ remove_min_tree_helper<Heap> >::type type;
+ };
+
+ template<typename Heap>
+ struct find_min : root<typename mpl::first<typename remove_min_tree<Heap>::type>::type> {};
+
+ template<typename Heap>
+ struct delete_min {
+ typedef typename remove_min_tree<Heap>::type rmt;
+ typedef typename merge<typename mpl::reverse<typename children<typename mpl::first<rmt>::type>::type>::type,
+ typename mpl::second<rmt>::type>::type type;
+ };
+
+ } // namespace mpl_graph
+ } // namespace metagraph
+} // namespace boost
+
+#endif // BOOST_METAGRAPH_MPL_BINOMIAL_HEAP_HPP_INCLUDED
Added: sandbox/metagraph/libs/metagraph/example/binomial_heap.cpp
==============================================================================
--- (empty file)
+++ sandbox/metagraph/libs/metagraph/example/binomial_heap.cpp 2012-08-07 06:18:37 EDT (Tue, 07 Aug 2012)
@@ -0,0 +1,45 @@
+#include <boost/mpl/list.hpp>
+#include <boost/metagraph/mpl_graph/binomial_heap.hpp>
+#include <boost/mpl/equal.hpp>
+
+namespace mpl_graph = boost::metagraph::mpl_graph;
+namespace mpl = boost::mpl;
+
+typedef mpl_graph::insert<mpl::int_< 9>, mpl::list<> >::type heap0;
+typedef mpl_graph::insert<mpl::int_<17>, heap0 >::type heap1;
+typedef mpl_graph::insert<mpl::int_< 2>, heap1 >::type heap2;
+typedef mpl_graph::insert<mpl::int_<23>, heap2 >::type heap3;
+typedef mpl_graph::insert<mpl::int_< 0>, heap3 >::type heap4;
+typedef mpl_graph::insert<mpl::int_<-1>, heap4 >::type heap5;
+typedef mpl_graph::insert<mpl::int_<99>, heap5 >::type heap6;
+typedef mpl_graph::insert<mpl::int_<38>, heap6 >::type heap7;
+
+typedef mpl_graph::find_min<heap7>::type val0;
+typedef mpl_graph::delete_min<heap7>::type heapD1;
+BOOST_MPL_ASSERT(( boost::is_same<val0, mpl::int_<-1> > ));
+typedef mpl_graph::find_min<heapD1>::type val1;
+typedef mpl_graph::delete_min<heapD1>::type heapD2;
+BOOST_MPL_ASSERT(( boost::is_same<val1, mpl::int_<0> > ));
+typedef mpl_graph::find_min<heapD2>::type val2;
+typedef mpl_graph::delete_min<heapD2>::type heapD3;
+BOOST_MPL_ASSERT(( boost::is_same<val2, mpl::int_<2> > ));
+typedef mpl_graph::find_min<heapD3>::type val3;
+typedef mpl_graph::delete_min<heapD3>::type heapD4;
+BOOST_MPL_ASSERT(( boost::is_same<val3, mpl::int_<9> > ));
+typedef mpl_graph::find_min<heapD4>::type val4;
+typedef mpl_graph::delete_min<heapD4>::type heapD5;
+BOOST_MPL_ASSERT(( boost::is_same<val4, mpl::int_<17> > ));
+typedef mpl_graph::find_min<heapD5>::type val5;
+typedef mpl_graph::delete_min<heapD5>::type heapD6;
+BOOST_MPL_ASSERT(( boost::is_same<val5, mpl::int_<23> > ));
+typedef mpl_graph::find_min<heapD6>::type val6;
+typedef mpl_graph::delete_min<heapD6>::type heapD7;
+BOOST_MPL_ASSERT(( boost::is_same<val6, mpl::int_<38> > ));
+typedef mpl_graph::find_min<heapD7>::type val7;
+typedef mpl_graph::delete_min<heapD7>::type heapD8;
+BOOST_MPL_ASSERT(( boost::is_same<val7, mpl::int_<99> > ));
+
+int main() {
+ return 0;
+}
+
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk