Menu
▾
▴
[Dmcs-notify] SF.net SVN: dmcs:[3303] dmcs/branches/dmcs1.5
|
From: <mm...@us...> - 2012-12-04 10:49:37
|
Revision: 3303
http://dmcs.svn.sourceforge.net/dmcs/?rev=3303&view=rev
Author: mmsc
Date: 2012-12-04 10:49:24 +0000 (Tue, 04 Dec 2012)
Log Message:
-----------
Add Cache for position.
Modified Paths:
--------------
dmcs/branches/dmcs1.5/include/mcs/Makefile.am
dmcs/branches/dmcs1.5/src/Makefile.am
dmcs/branches/dmcs1.5/src/mcs/Makefile.am
dmcs/branches/dmcs1.5/testsuite/Makefile.am
Added Paths:
-----------
dmcs/branches/dmcs1.5/include/mcs/CachePosition.h
dmcs/branches/dmcs1.5/src/mcs/CachePosition.cpp
dmcs/branches/dmcs1.5/testsuite/testCache.cpp
Added: dmcs/branches/dmcs1.5/include/mcs/CachePosition.h
===================================================================
--- dmcs/branches/dmcs1.5/include/mcs/CachePosition.h (rev 0)
+++ dmcs/branches/dmcs1.5/include/mcs/CachePosition.h 2012-12-04 10:49:24 UTC (rev 3303)
@@ -0,0 +1,54 @@
+/* DMCS -- Distributed Nonmonotonic Multi-Context Systems.
+ * Copyright (C) 2009, 2010 Minh Dao-Tran, Thomas Krennwallner
+ *
+ * This file is part of DMCS.
+ *
+ * DMCS is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * DMCS is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with DMCS. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+/**
+ * @file CachePosition.h
+ * @author Minh Dao-Tran <da...@kr...>
+ * @date Tue Dec 4 10:35:26 2012
+ *
+ * @brief
+ */
+
+#ifndef ___CACHE_H___
+#define ___CACHE_H___
+
+#include <vector>
+
+namespace dmcs {
+
+class CachePosition {
+public:
+ void
+ update_cache(std::size_t index,
+ std::size_t k);
+
+ std::size_t
+ find_position(const std::size_t k);
+
+private:
+ std::vector<std::size_t> mark;
+};
+
+} // namespace dmcs
+
+#endif // ___CACHE_H___
+
+// Local Variables:
+// mode: C++
+// End:
Modified: dmcs/branches/dmcs1.5/include/mcs/Makefile.am
===================================================================
--- dmcs/branches/dmcs1.5/include/mcs/Makefile.am 2012-12-03 10:59:03 UTC (rev 3302)
+++ dmcs/branches/dmcs1.5/include/mcs/Makefile.am 2012-12-04 10:49:24 UTC (rev 3303)
@@ -10,6 +10,7 @@
BridgeRule.h \
BridgeRuleEvaluator.h \
BridgeRuleTable.h \
+ CachePosition.h \
ForwardMessage.h \
Heads.h \
ID.h \
Modified: dmcs/branches/dmcs1.5/src/Makefile.am
===================================================================
--- dmcs/branches/dmcs1.5/src/Makefile.am 2012-12-03 10:59:03 UTC (rev 3302)
+++ dmcs/branches/dmcs1.5/src/Makefile.am 2012-12-04 10:49:24 UTC (rev 3303)
@@ -39,7 +39,7 @@
# the new_dmcsd binary
new_dmcsd_SOURCES = \
- new_dmcsd.cpp
+ new_dmcsd.cpp
new_dmcsd_LDADD = \
$(top_builddir)/src/dmcs/libdmcs.a \
@@ -48,6 +48,7 @@
$(top_builddir)/src/network/libthreads.a \
$(top_builddir)/src/process/libprocess.a \
$(top_builddir)/src/mcs/libmcs.a \
+ $(top_builddir)/src/mcs/libcache.a \
@LIBCURL@
# the dmcsc binary
Added: dmcs/branches/dmcs1.5/src/mcs/CachePosition.cpp
===================================================================
--- dmcs/branches/dmcs1.5/src/mcs/CachePosition.cpp (rev 0)
+++ dmcs/branches/dmcs1.5/src/mcs/CachePosition.cpp 2012-12-04 10:49:24 UTC (rev 3303)
@@ -0,0 +1,94 @@
+/* DMCS -- Distributed Nonmonotonic Multi-Context Systems.
+ * Copyright (C) 2009, 2010 Minh Dao-Tran, Thomas Krennwallner
+ *
+ * This file is part of DMCS.
+ *
+ * DMCS is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * DMCS is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with DMCS. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+/**
+ * @file CachePosition.cpp
+ * @author Minh Dao-Tran <da...@kr...>
+ * @date Tue Dec 4 10:39:01 2012
+ *
+ * @brief
+ */
+
+#include <assert.h>
+#include <iostream>
+#include "mcs/CachePosition.h"
+
+namespace dmcs {
+
+void
+CachePosition::update_cache(std::size_t index,
+ std::size_t k)
+{
+ assert (index == mark.size()+1);
+
+ if (index == 1)
+ {
+ mark.push_back(k);
+ }
+ else
+ {
+ k += mark.back();
+ mark.push_back(k);
+ }
+}
+
+std::size_t
+CachePosition::find_position(const std::size_t k)
+{
+ if (mark.empty())
+ {
+ return 0;
+ }
+
+ // as mark is incremental, we can do a binary search here
+ std::size_t beg = 0;
+ std::size_t end = mark.size();
+ std::size_t mid;
+
+ while (beg+1 < end)
+ {
+ mid = (beg + end)/2;
+ if (mark[mid] < k)
+ {
+ beg = mid;
+ }
+ else if (mark[mid] > k)
+ {
+ end = mid;
+ }
+ else if (mark[mid] == k)
+ {
+ return mid;
+ }
+ }
+
+ // actually beg but outside we count from 1
+ if (mark[beg] == k)
+ {
+ return beg;
+ }
+
+ return beg+1;
+}
+
+} // namespace dmcs
+
+// Local Variables:
+// mode: C++
+// End:
Modified: dmcs/branches/dmcs1.5/src/mcs/Makefile.am
===================================================================
--- dmcs/branches/dmcs1.5/src/mcs/Makefile.am 2012-12-03 10:59:03 UTC (rev 3302)
+++ dmcs/branches/dmcs1.5/src/mcs/Makefile.am 2012-12-04 10:49:24 UTC (rev 3303)
@@ -26,7 +26,7 @@
$(BOOST_GRAPH_LIBS)
-noinst_LIBRARIES = libmcs.a
+noinst_LIBRARIES = libmcs.a libcache.a
# the mcs library
libmcs_a_SOURCES = \
@@ -49,3 +49,7 @@
QueryPlan.cpp \
ReturnedBeliefState.cpp \
StreamingJoiner.cpp
+
+# the cache lirary
+libcache_a_SOURCES = \
+ CachePosition.cpp
\ No newline at end of file
Modified: dmcs/branches/dmcs1.5/testsuite/Makefile.am
===================================================================
--- dmcs/branches/dmcs1.5/testsuite/Makefile.am 2012-12-03 10:59:03 UTC (rev 3302)
+++ dmcs/branches/dmcs1.5/testsuite/Makefile.am 2012-12-04 10:49:24 UTC (rev 3303)
@@ -25,6 +25,7 @@
TESTS = \
+ testCache \
testClasp \
testBeliefComparison \
testBridgeRuleParswer \
@@ -68,6 +69,7 @@
BOOST_TEST_LOG_LEVEL=all
check_PROGRAMS = \
+ testCache \
testClasp \
testBeliefComparison \
testBridgeRuleParser \
@@ -111,6 +113,10 @@
testSystemWithQueryPlan \
testSystem
+testCache_SOURCES = testCache.cpp
+testCache_LDADD = \
+ $(top_builddir)/src/mcs/libcache.a
+
testClasp_SOURCES = testClasp.cpp
testClasp_LDADD = \
$(top_builddir)/src/dmcs/libdmcs.a \
Added: dmcs/branches/dmcs1.5/testsuite/testCache.cpp
===================================================================
--- dmcs/branches/dmcs1.5/testsuite/testCache.cpp (rev 0)
+++ dmcs/branches/dmcs1.5/testsuite/testCache.cpp 2012-12-04 10:49:24 UTC (rev 3303)
@@ -0,0 +1,79 @@
+/* DMCS -- Distributed Nonmonotonic Multi-Context Systems.
+ * Copyright (C) 2009, 2010 Minh Dao-Tran, Thomas Krennwallner
+ *
+ * This file is part of DMCS.
+ *
+ * DMCS is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * DMCS is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with DMCS. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+/**
+ * @file testCache.cpp
+ * @author Minh Dao-Tran <da...@kr...>
+ * @date Tue Dec 4 11:02:21 2012
+ *
+ * @brief
+ *
+ *
+ */
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif // HAVE_CONFIG_H
+
+#include <iostream>
+#include "mcs/CachePosition.h"
+
+#define BOOST_TEST_DYN_LINK
+#define BOOST_TEST_MODULE "testCache"
+#include <boost/test/unit_test.hpp>
+#include <boost/thread.hpp>
+
+using namespace dmcs;
+
+BOOST_AUTO_TEST_CASE ( testCachPosition )
+{
+ CachePosition cp;
+ cp.update_cache(1,3);
+ cp.update_cache(2,3);
+ cp.update_cache(3,3);
+ cp.update_cache(4,3);
+ cp.update_cache(5,3);
+ cp.update_cache(6,3);
+ cp.update_cache(7,3);
+ cp.update_cache(8,3);
+ cp.update_cache(9,3);
+ cp.update_cache(10,3);
+ cp.update_cache(11,3);
+ cp.update_cache(12,3);
+ cp.update_cache(13,3);
+ cp.update_cache(14,3);
+ cp.update_cache(15,3);
+
+ std::cerr << "Update finished" << std::endl;
+
+ static const std::size_t ask[] = {3, 5, 10, 12, 20, 23, 25, 27};
+ std::vector<std::size_t> ask_vec(ask, ask + sizeof(ask)/sizeof(ask[0]));
+
+ for (std::vector<std::size_t>::const_iterator it = ask_vec.begin(); it != ask_vec.end(); ++it)
+ {
+ std::cerr << "Find position for value = " << *it << std::endl;
+ std::size_t pos = cp.find_position(*it);
+ std::cerr << "value = " << *it << ", pos = " << pos << std::endl;
+ }
+}
+
+
+// Local Variables:
+// mode: C++
+// End:
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
