Boost logo

Boost-Commit :

Subject: [Boost-commit] svn:boost r83190 - sandbox/icl/libs/xplore/value_sem/TreeSync1/TreeSync1
From: afojgo_at_[hidden]
Date: 2013-02-27 12:58:04


Author: jofaber
Date: 2013-02-27 12:58:03 EST (Wed, 27 Feb 2013)
New Revision: 83190
URL: http://svn.boost.org/trac/boost/changeset/83190

Log:
Improving merge algorithm.
Added:
   sandbox/icl/libs/xplore/value_sem/TreeSync1/TreeSync1/TreeMaker.h (contents, props changed)
Text files modified:
   sandbox/icl/libs/xplore/value_sem/TreeSync1/TreeSync1/Object.h | 10 ++-
   sandbox/icl/libs/xplore/value_sem/TreeSync1/TreeSync1/Tree.h | 100 ++++++++++++++++++++++++++-------------
   sandbox/icl/libs/xplore/value_sem/TreeSync1/TreeSync1/TreeSync1.cpp | 65 ++++++++++----------------
   sandbox/icl/libs/xplore/value_sem/TreeSync1/TreeSync1/std_algorithm.h | 31 ++++++++++--
   4 files changed, 125 insertions(+), 81 deletions(-)

Modified: sandbox/icl/libs/xplore/value_sem/TreeSync1/TreeSync1/Object.h
==============================================================================
--- sandbox/icl/libs/xplore/value_sem/TreeSync1/TreeSync1/Object.h (original)
+++ sandbox/icl/libs/xplore/value_sem/TreeSync1/TreeSync1/Object.h 2013-02-27 12:58:03 EST (Wed, 27 Feb 2013)
@@ -78,9 +78,13 @@
   std::unique_ptr<concept> m_value;
 };
 
-// friend enabled gate to polymorphic objects
-bool operator < (object const& lhs, object const& rhs){ return is_less(lhs, rhs); }
-
+/*
+// friend enabled gate to polymorphic objects!!
+bool operator < (object const& lhs, object const& rhs)
+{
+ return is_less(lhs, rhs);
+}
+*/
 
 // 30:13 unsave operator= using delete / new. (defects)
 // 30:25 operator= via unique_ptr and reset.

Modified: sandbox/icl/libs/xplore/value_sem/TreeSync1/TreeSync1/Tree.h
==============================================================================
--- sandbox/icl/libs/xplore/value_sem/TreeSync1/TreeSync1/Tree.h (original)
+++ sandbox/icl/libs/xplore/value_sem/TreeSync1/TreeSync1/Tree.h 2013-02-27 12:58:03 EST (Wed, 27 Feb 2013)
@@ -3,21 +3,21 @@
 #include <ostream>
 #include <iterator>
 #include <vector>
+#include <boost/function.hpp>
 #include <boost/utility/enable_if.hpp>
 #include "std_algorithm.h"
-#include "Object.h"
+//#include "Object.h"
 
 typedef int tUuid;
 typedef int tTime;
 
-template<class ContentT, class UuidT = int, class TimeT = int>
-class Node;
+template<class ContentT, class UuidT, class TimeT> class Node;
 
 template<class Uuid, class Time = int>
 class Playable
 {
 public:
- Playable(Uuid uuid)
+ Playable(Uuid uuid = 0)
     : m_uuid(uuid)
   { }
 
@@ -35,26 +35,13 @@
   return lhs.time() < rhs.time();
 }
 
-template<class Comparable>
-struct Minimum
-{
- Comparable operator()(Comparable const& lhs, Comparable const& rhs)
- { return rhs < lhs ? rhs : lhs; }
-};
-
-template<class Comparable>
-struct Maximum
-{
- Comparable operator()(Comparable const& lhs, Comparable const& rhs)
- { return lhs < rhs ? rhs : lhs; }
-};
 
 template<class Mergable>
 struct Merger
 {
   Mergable operator()(Mergable const& lhs, Mergable const& rhs)
   {
- return merge(lhs, rhs);
+ return std::move(merge(lhs, rhs));
   }
 };
 
@@ -76,22 +63,25 @@
 
   typedef typename tVector::size_type size_type;
   typedef typename tVector::value_type value_type;
- typedef Type ValueType;
+ //CL typedef Type ValueType;
   typedef typename tVector::const_reference const_reference;
 
   typedef typename tVector::iterator iterator;
   typedef typename tVector::const_iterator const_iterator;
 
   Vec(): m_uuid(), m_time(), m_name("empty"), m_vector() {}
- Vec(Uuid const& uuid, Time const& time, std::string const& name)
- : m_uuid(uuid), m_time(time), m_name(name), m_vector() {}
+
+ Vec(Uuid const& uuid, Time const& time, std::string const& name, size_type capac = 4)
+ : m_uuid(uuid), m_time(time), m_name(name), m_vector(capac)
+ {
+ }
 
   Vec(Vec const& val) : m_vector(val.m_vector)
     , m_uuid(val.m_uuid)
     , m_time(val.m_time)
     , m_name(val.m_name)
   {
- //std::cout << "c() ";
+ std::cout << "c() ";
   }
 
   Vec(Vec&& val): m_vector(std::move(val.m_vector))
@@ -121,7 +111,12 @@
   void reserve(size_type size){ m_vector.reserve(size); }
   size_type size()const { return m_vector.size(); }
 
- //void push_back(const value_type& val)
+ void emplace_back(const Type& val)
+ {
+ m_time = std::move(std::max(m_time, val.time()));
+ m_vector.emplace_back(val);
+ }
+
   void push_back(const Type& val)
   {
     //JODO
@@ -135,6 +130,7 @@
 
   void setUuid(Uuid const& uuid){ m_uuid = uuid; }
   void setTime(Time const& time){ m_time = time; }
+ void setName(std::string const& name){ m_name = name; }
   void name(std::string const& name)const { m_name = name; }
 
   Uuid m_uuid;
@@ -146,7 +142,7 @@
 template<class Type, class Uuid, class Time>
 bool operator < (Vec<Type,Uuid,Time> const& lhs, Vec<Type,Uuid,Time> const& rhs)
 {
- return lhs.time() < rhs.time();
+ return lhs.uuid() < rhs.uuid();
 }
 
 //-----------------------------------------------------------------
@@ -224,7 +220,7 @@
 }
 
 template<class Syncable>
-struct LessForUuid : std::binary_function<Syncable const&, Syncable const&, bool>
+struct LessForUuid : std::binary_function<Syncable, Syncable, bool>
 {
     bool operator()(Syncable const& lhs, Syncable const& rhs)
     {
@@ -232,6 +228,18 @@
     }
 };
 
+template<class Syncable>
+struct LessForTime : std::binary_function<Syncable, Syncable, bool>
+{
+ typedef Syncable first_argument_type;
+ typedef Syncable second_argument_type;
+
+ bool operator()(Syncable const& lhs, Syncable const& rhs)
+ {
+ return less_for_time(lhs, rhs);
+ }
+};
+
 
 //-----------------------------------------------------------------
 
@@ -251,7 +259,6 @@
   typedef typename NodeVec::const_iterator node_const_iterator;
   typedef typename NodeVec::iterator node_iterator;
 
-
   Node( Uuid const& uuid = 0, std::string const& name = std::string()
       , const ContentVec& content = ContentVec(), const NodeVec& children = NodeVec())
     : m_uuid(uuid), m_name(name)
@@ -278,9 +285,18 @@
   Time time()const { return m_time; }
   std::string name()const { return m_name; }
 
+ Uuid contentUuid()const { return m_content.uuid(); }
+ Time contentTime()const { return m_content.time(); }
+ std::string contentName()const { return m_content.name(); }
+
+ Uuid childrenUuid()const { return m_children.uuid(); }
+ Time childrenTime()const { return m_children.time(); }
+ std::string childrenName()const { return m_children.name(); }
+
   void setUuid(Uuid const& uuid) { m_uuid=uuid; }
   void setTime(Time const& time) { m_time=time; }
   void setName(std::string& name){ m_name=name; }
+
   void setContent(ContentVec content){ m_content = std::move(content); };
   void setChildren(NodeVec nodes){ m_children = std::move(nodes); };
 
@@ -296,6 +312,14 @@
 };
 
 
+template<class Type, class Uuid, class Time>
+bool operator < (Node<Type,Uuid,Time> const& lhs, Node<Type,Uuid,Time> const& rhs)
+{
+ return lhs.uuid() < rhs.uuid();
+}
+
+
+
 template<class Type>
 void draw(const Node<Type>& obj, std::ostream& out, size_t pos)
 {
@@ -322,6 +346,7 @@
   Node<Type> merged;
   merged.setUuid(lhs.uuid());
   merged.setTime(std::max(lhs.time(), rhs.time()));
+ merged.setName(lhs.name());
 
   merged.setContent(mergeElements(lhs, rhs));
   merged.setChildren(mergeNodes(lhs, rhs));
@@ -334,15 +359,20 @@
 typename Node<Type>::ContentVec mergeElements(Node<Type>const& lhs, Node<Type>const& rhs)
 {
   typedef Node<Type>::ContentVec Elements;
- typedef Elements::ValueType ElementType;
+ typedef Elements::value_type Element;
 
   Elements merged;
   merged.reserve(lhs.element_count() + rhs.element_count());
+ merged.setUuid(lhs.contentUuid());
+ merged.setName(lhs.contentName());
+ merged.setTime(std::max(lhs.contentTime(), rhs.contentTime()));
 
   std::general_union( lhs.elements_begin(), lhs.elements_end()
                     , rhs.elements_begin(), rhs.elements_end()
- , Maximum<ElementType>()
- , std::back_inserter(merged) );
+ , std::back_inserter(merged)
+ , LessForUuid<Element>()
+ , std::Maximum<LessForTime<Element> >()
+ );
 
   return std::move(merged);
 }
@@ -352,15 +382,20 @@
 typename Node<Type>::NodeVec mergeNodes(Node<Type>const& lhs, Node<Type>const& rhs)
 {
   typedef Node<Type>::NodeVec Nodes;
- typedef typename Nodes::ValueType NodeType;
+ typedef typename Nodes::value_type NodeType;
 
   Nodes merged;
   merged.reserve(lhs.node_count() + rhs.node_count());
+ merged.setUuid(lhs.childrenUuid());
+ merged.setName(lhs.childrenName());
+ merged.setTime(std::max(lhs.childrenTime(), rhs.childrenTime()));
   
   std::general_union( lhs.nodes_begin(), lhs.nodes_end()
                     , rhs.nodes_begin(), rhs.nodes_end()
+ , std::back_inserter(merged)
+ , LessForUuid<NodeType>()
                     , Merger<NodeType>()
- , std::back_inserter(merged) );
+ );
                     
   return std::move(merged);
 }
@@ -390,8 +425,7 @@
 template<class Type>
 void sortNodes(Node<Type>& val)
 {
- std::sort( val.nodes_begin(), val.nodes_end(), LessForUuid<Node<Type> >());
   std::for_each(val.nodes_begin(), val.nodes_end(), Sorter<Node<Type> >());
+ std::sort( val.nodes_begin(), val.nodes_end(), LessForUuid<Node<Type> >());
 }
 
-

Added: sandbox/icl/libs/xplore/value_sem/TreeSync1/TreeSync1/TreeMaker.h
==============================================================================
--- (empty file)
+++ sandbox/icl/libs/xplore/value_sem/TreeSync1/TreeSync1/TreeMaker.h 2013-02-27 12:58:03 EST (Wed, 27 Feb 2013)
@@ -0,0 +1,55 @@
+#pragma once
+
+#include "Tree.h"
+
+typedef Vec<Playable<int> > Playlist;
+typedef Vec<Playlist> Playlists;
+typedef Vec<Node<Playlist> > NodeList;
+
+
+Playlists content_1(int uuid, std::string const& name)
+{
+
+ Playlist pl1(3, 2, " pl_1 ");
+ pl1.emplace_back(Playable<int>(11));
+
+ Playlist pl2(2, 5, " pl_2 ");
+ pl2.emplace_back(Playable<int>(22));
+ pl2.emplace_back(Playable<int>(21));
+
+ Playlists pls1(uuid, 0, name);
+ pls1.emplace_back(std::move(pl1));
+ pls1.emplace_back(std::move(pl2));
+ //pls1.emplace_back(Playlist(3, 2, " pl_1 ").emplace_back(Playable<int>(11)));
+
+ return std::move(pls1);
+}
+
+Playlists content_2(int uuid, std::string const& name)
+{
+
+ Playlist pl1(3, 6, " pl_3 ");
+ pl1.emplace_back(Playable<int>(11));
+ pl1.emplace_back(Playable<int>(12));
+ pl1.emplace_back(Playable<int>(11));
+
+ Playlist pl2(7, 5, " pl_4 ");
+ pl2.emplace_back(Playable<int>(22));
+ pl2.emplace_back(Playable<int>(21));
+
+ Playlists pls1(uuid, 0, name);
+ pls1.emplace_back(pl1);
+ pls1.emplace_back(pl2);
+
+ return std::move(pls1);
+}
+
+NodeList children_0(int uuid, int time, std::string const& name, Playlists pls)
+{
+ Node<Playlist> node(6, "node_1", pls);
+ NodeList nodes1(uuid, time, " nodes_1 ");
+ nodes1.emplace_back(node);
+ return std::move(nodes1);
+}
+
+

Modified: sandbox/icl/libs/xplore/value_sem/TreeSync1/TreeSync1/TreeSync1.cpp
==============================================================================
--- sandbox/icl/libs/xplore/value_sem/TreeSync1/TreeSync1/TreeSync1.cpp (original)
+++ sandbox/icl/libs/xplore/value_sem/TreeSync1/TreeSync1/TreeSync1.cpp 2013-02-27 12:58:03 EST (Wed, 27 Feb 2013)
@@ -6,15 +6,12 @@
 
 #include "Object.h"
 #include "Tree.h"
+#include "TreeMaker.h"
 
 typedef std::vector<object> collection;
 typedef collection::iterator coll_iter;
 typedef collection::const_iterator coll_citer;
 
-typedef Vec<Playable<int> > Playlist;
-typedef Vec<Playlist> Playlists;
-typedef Vec<Node<Playlist> > NodeList;
-
 
 template<class Type>
 std::string type_name(Type const& value)
@@ -56,6 +53,8 @@
     << "</Vec>\n";
 }
 
+
+
 int _tmain(int argc, _TCHAR* argv[])
 {
   std::cout << "Hello concept\n";
@@ -64,51 +63,37 @@
 
   coll.push_back(42);
 
- //--- Playlist --------------------
- Playlist pl1(3, 2, " pl_1 ");
- pl1.push_back(Playable<int>(11));
- //pl1.push_back(Playable<int>(10));
-
- Playlist pl2(2, 5, " pl_2 ");
- pl2.push_back(Playable<int>(21));
- pl2.push_back(Playable<int>(20));
-
- Playlist pl3(1, 3, " pl_3 ");
- pl3.push_back(Playable<int>(31));
-
-
- //--- Playlists -------------------
- Playlists pls1(4, 0, " pls_1 ");
- pls1.push_back(pl1);
- //pls1.push_back(pl2);
- //pls1.push_back(pl3);
-
- Playlists pls2(5, 0, " pls_2 ");
- pls2.push_back(pl2);
- pls2.push_back(pl3);
 
+ Playlists content1 = content_1(4, " pls_1 ");
+
+
+ /*
   //--- Nodes -----------------------
- Node<Playlist> node1(6, " node_1 ", pls1);
- NodeList nodes1(7, 2, " nodes_1 ");
- nodes1.push_back(node1);
+ Playlists content1 = content_1(4, " pls_1 ");
+ NodeList children1 = children_0(5, 6, "children_1", content1);
 
- Node<Playlist> node2(8, " node_2 ", pls2, nodes1);
+ Playlists content2 = content_2(9, " pls_2 ");
+ NodeList children2 = children_0(10, 6, "children_2", content1);
 
- //=================================
- draw(node1, std::cout, 0);
+ Node<Playlist> node1 = Node<Playlist>(8, " node_1 ", content1, children1);
+
+ Node<Playlist> node2 = Node<Playlist>(11, " node_2 ", content2, children2);
 
- std::cout << "========================================\n";
- //Node<Playlist> merged = merge(node1, node2);
- //draw(merged, std::cout, 0);
 
- sort(node1);
   draw(node1, std::cout, 0);
 
- Node<Playlist> node3 = node1;
- Node<Playlist> merged = merge(node3, node2);
+ sort(node1);
+ sort(node2);
+ std::cout << "node1 ========================================\n";
+ draw(node1, std::cout, 0);
+ std::cout << "node2 ========================================\n";
+ draw(node2, std::cout, 0);
 
- std::cout << "========================================\n";
- draw(node3, std::cout, 0);
+
+ Node<Playlist> merged = merge(node1, node2);
+ std::cout << "merged ========================================\n";
+ draw(merged, std::cout, 0);
+ */
 
   return 0;
 }

Modified: sandbox/icl/libs/xplore/value_sem/TreeSync1/TreeSync1/std_algorithm.h
==============================================================================
--- sandbox/icl/libs/xplore/value_sem/TreeSync1/TreeSync1/std_algorithm.h (original)
+++ sandbox/icl/libs/xplore/value_sem/TreeSync1/TreeSync1/std_algorithm.h 2013-02-27 12:58:03 EST (Wed, 27 Feb 2013)
@@ -5,19 +5,18 @@
 namespace std
 {
 
-template <class InputIterator1, class InputIterator2, class OutputIterator, class Merger>
+template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare, class Merger>
   OutputIterator general_union(InputIterator1 first1, InputIterator1 last1,
                                InputIterator2 first2, InputIterator2 last2,
- Merger merger,
- OutputIterator result)
+ OutputIterator result, Compare less, Merger merger)
 {
   while (true)
   {
     if (first1==last1) return std::copy(first2,last2,result);
     if (first2==last2) return std::copy(first1,last1,result);
 
- if (*first1 < *first2) { *result = *first1; ++first1; }
- else if (*first2 < *first1) { *result = *first2; ++first2; }
+ if (less(*first1, *first2)) { *result = *first1; ++first1; }
+ else if (less(*first2, *first1)) { *result = *first2; ++first2; }
     else {
       // *first1 == *first2
       *result = merger(*first1, *first2);
@@ -27,4 +26,26 @@
   }
 }
 
+
+template<class Less>
+struct Minimum : std::binary_function<typename Less::first_argument_type, typename Less::first_argument_type, typename Less::first_argument_type>
+{
+ typedef typename Less::first_argument_type Comparable;
+ typedef typename Less::first_argument_type first_argument_type;
+
+ Comparable operator()(Comparable const& lhs, Comparable const& rhs)
+ { return Less()(rhs,lhs) ? rhs : lhs; }
+};
+
+template<class Less>
+struct Maximum : std::binary_function<typename Less::first_argument_type, typename Less::first_argument_type, typename Less::first_argument_type>
+{
+ typedef typename Less::first_argument_type Comparable;
+ typedef typename Less::first_argument_type first_argument_type;
+
+ Comparable operator()(Comparable const& lhs, Comparable const& rhs)
+ { return Less()(lhs,rhs) ? rhs : lhs; }
+};
+
+
 } //std
\ No newline at end of file


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