|
|
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