{"sha":"e91c2205c8c73143b0eb4b472424ea2f4feff3ec","node_id":"MDY6Q29tbWl0MzU2ODEzNzY6ZTkxYzIyMDVjOGM3MzE0M2IwZWI0YjQ3MjQyNGVhMmY0ZmVmZjNlYw==","commit":{"author":{"name":"Felix Petriconi","email":"FelixPetriconi@users.noreply.github.com","date":"2020-09-16T19:37:36Z"},"committer":{"name":"GitHub","email":"noreply@github.com","date":"2020-09-16T19:37:36Z"},"message":"Merge pull request #316 from stlab/develop\n\nMerge develop into master for 1.5.3","tree":{"sha":"613a9cf0d828c7c4e7ee3f5d74bebad36fd1bdae","url":"https://api.github.com/repos/stlab/stlab/git/trees/613a9cf0d828c7c4e7ee3f5d74bebad36fd1bdae"},"url":"https://api.github.com/repos/stlab/stlab/git/commits/e91c2205c8c73143b0eb4b472424ea2f4feff3ec","comment_count":0,"verification":{"verified":true,"reason":"valid","signature":"-----BEGIN PGP SIGNATURE-----\n\nwsBcBAABCAAQBQJfYmmACRBK7hj4Ov3rIwAAdHIIAJ7DchyXjUpfZVkZgRVKl6vv\n4vFzJwL5/is1tIePIm/ulX3CXpv32pXiTOLKGXX+7L5Ml8mCrJU3CIkvETWbfpTd\nJEV9Te43mfcGQ9i4MpSkRUFKxz4JWtB5jWeNAjFQTwNA6bDkgQNWNiP2yiBQxog0\n0O7k57XOdQ9tzv303Jw0I+5b3WoGK2UFBo2YL0FmMrXPzuf1Xr4o7WJFpNV3KCJW\njx5+UkjdnaEOYMhfrrZ6jRTvok7vV93ecPXcQ3cbuX3e7lOpTf3cBjvjcnfCee3a\nkfiuisvS23S20UmicXBV0+3tEjPxKS2IoA2X9V5cWYoPWbiMCgfx4u7nOFEuKvw=\n=Sswm\n-----END PGP SIGNATURE-----\n","payload":"tree 613a9cf0d828c7c4e7ee3f5d74bebad36fd1bdae\nparent 2e411dd5c8b7eb096e9eb04c46b569c775b126c6\nparent 013d5981d5e6fab9c3ae93a7025a388fdc9de910\nauthor Felix Petriconi 1600285056 +0200\ncommitter GitHub 1600285056 +0200\n\nMerge pull request #316 from stlab/develop\n\nMerge develop into master for 1.5.3","verified_at":"2024-11-07T19:04:37Z"}},"url":"https://api.github.com/repos/stlab/stlab/commits/e91c2205c8c73143b0eb4b472424ea2f4feff3ec","html_url":"https://github.com/stlab/stlab/commit/e91c2205c8c73143b0eb4b472424ea2f4feff3ec","comments_url":"https://api.github.com/repos/stlab/stlab/commits/e91c2205c8c73143b0eb4b472424ea2f4feff3ec/comments","author":{"login":"FelixPetriconi","id":612377,"node_id":"MDQ6VXNlcjYxMjM3Nw==","avatar_url":"https://avatars.githubusercontent.com/u/612377?v=4","gravatar_id":"","url":"https://api.github.com/users/FelixPetriconi","html_url":"https://github.com/FelixPetriconi","followers_url":"https://api.github.com/users/FelixPetriconi/followers","following_url":"https://api.github.com/users/FelixPetriconi/following{/other_user}","gists_url":"https://api.github.com/users/FelixPetriconi/gists{/gist_id}","starred_url":"https://api.github.com/users/FelixPetriconi/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/FelixPetriconi/subscriptions","organizations_url":"https://api.github.com/users/FelixPetriconi/orgs","repos_url":"https://api.github.com/users/FelixPetriconi/repos","events_url":"https://api.github.com/users/FelixPetriconi/events{/privacy}","received_events_url":"https://api.github.com/users/FelixPetriconi/received_events","type":"User","user_view_type":"public","site_admin":false},"committer":{"login":"web-flow","id":19864447,"node_id":"MDQ6VXNlcjE5ODY0NDQ3","avatar_url":"https://avatars.githubusercontent.com/u/19864447?v=4","gravatar_id":"","url":"https://api.github.com/users/web-flow","html_url":"https://github.com/web-flow","followers_url":"https://api.github.com/users/web-flow/followers","following_url":"https://api.github.com/users/web-flow/following{/other_user}","gists_url":"https://api.github.com/users/web-flow/gists{/gist_id}","starred_url":"https://api.github.com/users/web-flow/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/web-flow/subscriptions","organizations_url":"https://api.github.com/users/web-flow/orgs","repos_url":"https://api.github.com/users/web-flow/repos","events_url":"https://api.github.com/users/web-flow/events{/privacy}","received_events_url":"https://api.github.com/users/web-flow/received_events","type":"User","user_view_type":"public","site_admin":false},"parents":[{"sha":"2e411dd5c8b7eb096e9eb04c46b569c775b126c6","url":"https://api.github.com/repos/stlab/stlab/commits/2e411dd5c8b7eb096e9eb04c46b569c775b126c6","html_url":"https://github.com/stlab/stlab/commit/2e411dd5c8b7eb096e9eb04c46b569c775b126c6"},{"sha":"013d5981d5e6fab9c3ae93a7025a388fdc9de910","url":"https://api.github.com/repos/stlab/stlab/commits/013d5981d5e6fab9c3ae93a7025a388fdc9de910","html_url":"https://github.com/stlab/stlab/commit/013d5981d5e6fab9c3ae93a7025a388fdc9de910"}],"stats":{"total":2540,"additions":2405,"deletions":135},"files":[{"sha":"12a8a92a13e88b9b1a35e57e13308f7a58997cca","filename":".clang-format","status":"modified","additions":0,"deletions":4,"changes":4,"blob_url":"https://github.com/stlab/stlab/blob/e91c2205c8c73143b0eb4b472424ea2f4feff3ec/.clang-format","raw_url":"https://github.com/stlab/stlab/raw/e91c2205c8c73143b0eb4b472424ea2f4feff3ec/.clang-format","contents_url":"https://api.github.com/repos/stlab/stlab/contents/.clang-format?ref=e91c2205c8c73143b0eb4b472424ea2f4feff3ec","patch":"@@ -94,10 +94,6 @@ PenaltyBreakString: 1000\n PenaltyExcessCharacter: 1000000\n PenaltyReturnTypeOnItsOwnLine: 1000\n PointerAlignment: Left\n-RawStringFormats: \n- - Delimiter: pb\n- Language: TextProto\n- BasedOnStyle: google\n ReflowComments: true\n SortIncludes: true\n SortUsingDeclarations: true"},{"sha":"10a1784920efc707fa0a5926d35a1e1593a657a8","filename":".hyde-config","status":"added","additions":9,"deletions":0,"changes":9,"blob_url":"https://github.com/stlab/stlab/blob/e91c2205c8c73143b0eb4b472424ea2f4feff3ec/.hyde-config","raw_url":"https://github.com/stlab/stlab/raw/e91c2205c8c73143b0eb4b472424ea2f4feff3ec/.hyde-config","contents_url":"https://api.github.com/repos/stlab/stlab/contents/.hyde-config?ref=e91c2205c8c73143b0eb4b472424ea2f4feff3ec","patch":"@@ -0,0 +1,9 @@\n+{\n+ \"hyde-src-root\": \"stlab\",\n+ \"hyde-yaml-dir\": \"../stlab.github.io/libraries\",\n+ \"clang_flags\": [\n+ \"-std=c++17\",\n+ \"-I.\",\n+ \"-Wno-everything\"\n+ ]\n+}"},{"sha":"4832a26026ed8579807bf2f2fad75f36b9237bdc","filename":"CHANGES.md","status":"modified","additions":9,"deletions":0,"changes":9,"blob_url":"https://github.com/stlab/stlab/blob/e91c2205c8c73143b0eb4b472424ea2f4feff3ec/CHANGES.md","raw_url":"https://github.com/stlab/stlab/raw/e91c2205c8c73143b0eb4b472424ea2f4feff3ec/CHANGES.md","contents_url":"https://api.github.com/repos/stlab/stlab/contents/CHANGES.md?ref=e91c2205c8c73143b0eb4b472424ea2f4feff3ec","patch":"@@ -1,3 +1,12 @@\n+## v1.5.3 - 2020 - September 16\n+- Fixed issues\n+ - [#312](https://github.com/stlab/libraries/issues/312): default_executor implementation for Windows has a memory leak\n+ - [#305](https://github.com/stlab/libraries/issues/305) stlab/concurrency/future.hpp won't compile with C++20\n+ - [#303](https://github.com/stlab/libraries/issues/) range based stlab::when_any data race\n+\n+- Enhancement\n+ - Adding Forest container and algorithms \n+ \n ## v1.5.2 - 2020 - February 05\n - Fixed issues\n - [#292](https://github.com/stlab/libraries/issues/292): What happened to our mutable lambdas?"},{"sha":"43b62110a056cd1e9e2f308fdc0c3095d4762a25","filename":"CMakeLists.txt","status":"modified","additions":1,"deletions":1,"changes":2,"blob_url":"https://github.com/stlab/stlab/blob/e91c2205c8c73143b0eb4b472424ea2f4feff3ec/CMakeLists.txt","raw_url":"https://github.com/stlab/stlab/raw/e91c2205c8c73143b0eb4b472424ea2f4feff3ec/CMakeLists.txt","contents_url":"https://api.github.com/repos/stlab/stlab/contents/CMakeLists.txt?ref=e91c2205c8c73143b0eb4b472424ea2f4feff3ec","patch":"@@ -14,7 +14,7 @@ else()\n set( subproject OFF )\n endif()\n \n-project( stlab VERSION 1.5.2 LANGUAGES CXX )\n+project( stlab VERSION 1.5.3 LANGUAGES CXX )\n \n include( CTest )\n include( CMakeDependentOption )"},{"sha":"8c466436ecb8e45b2d9d2e3d5a1ab76ee0ea5350","filename":"generate_docs.sh","status":"added","additions":19,"deletions":0,"changes":19,"blob_url":"https://github.com/stlab/stlab/blob/e91c2205c8c73143b0eb4b472424ea2f4feff3ec/generate_docs.sh","raw_url":"https://github.com/stlab/stlab/raw/e91c2205c8c73143b0eb4b472424ea2f4feff3ec/generate_docs.sh","contents_url":"https://api.github.com/repos/stlab/stlab/contents/generate_docs.sh?ref=e91c2205c8c73143b0eb4b472424ea2f4feff3ec","patch":"@@ -0,0 +1,19 @@\n+#!/bin/bash\n+\n+# The intent of this script is to generate the documentation shell that will eventually be migrated\n+# to stlab.github.io. This script assumes `stlab/` and `stlab.github.io/` are sibling repositories.\n+\n+pushd $(dirname $0) > /dev/null\n+\n+XCODE_TOOLCHAIN=$(xcode-select -p)\n+\n+# They moved it _again_! *shakes fist*\n+XCODE_11_5_CPP_DIR=${XCODE_TOOLCHAIN}/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1\n+\n+# echo ${XCODE_11_5_CPP_DIR}\n+\n+HYDE_ARGS=\"--hyde-update --access-filter-public --namespace-blacklist=detail,unsafe --use-system-clang\"\n+\n+hyde ${HYDE_ARGS} stlab/forest.hpp -- -I${XCODE_11_5_CPP_DIR}\n+\n+popd > /dev/null"},{"sha":"15cd29fc74c5b66fb525273ec1b3f43fb044f51f","filename":"stlab/algorithm/reverse.hpp","status":"added","additions":97,"deletions":0,"changes":97,"blob_url":"https://github.com/stlab/stlab/blob/e91c2205c8c73143b0eb4b472424ea2f4feff3ec/stlab%2Falgorithm%2Freverse.hpp","raw_url":"https://github.com/stlab/stlab/raw/e91c2205c8c73143b0eb4b472424ea2f4feff3ec/stlab%2Falgorithm%2Freverse.hpp","contents_url":"https://api.github.com/repos/stlab/stlab/contents/stlab%2Falgorithm%2Freverse.hpp?ref=e91c2205c8c73143b0eb4b472424ea2f4feff3ec","patch":"@@ -0,0 +1,97 @@\n+/*\n+ Copyright 2013 Adobe\n+ Distributed under the Boost Software License, Version 1.0.\n+ (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)\n+*/\n+/*************************************************************************************************/\n+\n+#ifndef STLAB_ALGORITHM_REVERSE_HPP\n+#define STLAB_ALGORITHM_REVERSE_HPP\n+\n+#include \n+#include \n+\n+#include \n+\n+/*************************************************************************************************/\n+\n+namespace stlab {\n+\n+/*************************************************************************************************/\n+\n+namespace unsafe {\n+\n+/*************************************************************************************************/\n+\n+template // I models NodeIterator\n+I reverse_append(I first, I last, I result) {\n+ while (first != last) {\n+ I prior(first);\n+ ++first;\n+ stlab::unsafe::set_next(prior, result);\n+ result = prior;\n+ }\n+ return result;\n+}\n+\n+template // I models NodeIterator\n+inline I reverse_append(R& range, I result) {\n+ return stlab::unsafe::reverse_append(std::begin(range), std::end(range), result);\n+}\n+\n+template // I models NodeIterator\n+inline I reverse_nodes(I first, I last) {\n+ return stlab::unsafe::reverse_append(first, last, last);\n+}\n+\n+template // R models NodeRange\n+inline typename R::iterator reverse_nodes(R& range) {\n+ return stlab::unsafe::reverse_nodes(std::begin(range), std::end(range));\n+}\n+\n+/*************************************************************************************************/\n+\n+} // namspace unsafe\n+\n+/*************************************************************************************************/\n+\n+template \n+inline void reverse(BidirectionalRange& range) {\n+ std::reverse(std::begin(range), std::end(range));\n+}\n+\n+template \n+inline void reverse_copy(BidirectionalRange& range, OutputIterator result) {\n+ std::reverse_copy(std::begin(range), std::end(range), result);\n+}\n+\n+template \n+inline void reverse_copy(const BidirectionalRange& range, OutputIterator result) {\n+ std::reverse_copy(std::begin(range), std::end(range), result);\n+}\n+\n+/*************************************************************************************************/\n+\n+template // I models BidirectionalIterator\n+std::pair reverse_until(I f, I m, I l) {\n+ while (f != m && m != l) {\n+ --l;\n+\n+ std::iter_swap(f, l);\n+\n+ ++f;\n+ }\n+\n+ return std::pair(f, l);\n+}\n+\n+/*************************************************************************************************/\n+\n+} // namespace stlab\n+\n+/*************************************************************************************************/\n+\n+#endif // STLAB_ALGORITHM_REVERSE_HPP\n+\n+/*************************************************************************************************/"},{"sha":"6238f8a2a2dc56fb0c513bc315290dca11ae5ca3","filename":"stlab/concurrency/config.hpp","status":"modified","additions":1,"deletions":1,"changes":2,"blob_url":"https://github.com/stlab/stlab/blob/e91c2205c8c73143b0eb4b472424ea2f4feff3ec/stlab%2Fconcurrency%2Fconfig.hpp","raw_url":"https://github.com/stlab/stlab/raw/e91c2205c8c73143b0eb4b472424ea2f4feff3ec/stlab%2Fconcurrency%2Fconfig.hpp","contents_url":"https://api.github.com/repos/stlab/stlab/contents/stlab%2Fconcurrency%2Fconfig.hpp?ref=e91c2205c8c73143b0eb4b472424ea2f4feff3ec","patch":"@@ -83,7 +83,7 @@\n #elif __cplusplus == 201703L\n #define STLAB_CPP_VERSION_PRIVATE() 17\n #else\n- #warning Unknown version of C+; assuming C++20.\n+ //#warning Unknown version of C+; assuming C++20.\n #define STLAB_CPP_VERSION_PRIVATE() 20\n #endif\n #endif"},{"sha":"020b3ab821a88801f628664e8e66bca12068cdeb","filename":"stlab/concurrency/default_executor.hpp","status":"modified","additions":13,"deletions":3,"changes":16,"blob_url":"https://github.com/stlab/stlab/blob/e91c2205c8c73143b0eb4b472424ea2f4feff3ec/stlab%2Fconcurrency%2Fdefault_executor.hpp","raw_url":"https://github.com/stlab/stlab/raw/e91c2205c8c73143b0eb4b472424ea2f4feff3ec/stlab%2Fconcurrency%2Fdefault_executor.hpp","contents_url":"https://api.github.com/repos/stlab/stlab/contents/stlab%2Fconcurrency%2Fdefault_executor.hpp?ref=e91c2205c8c73143b0eb4b472424ea2f4feff3ec","patch":"@@ -231,16 +231,26 @@ class task_system {\n template \n static void CALLBACK callback_impl(PTP_CALLBACK_INSTANCE /*instance*/,\n PVOID parameter,\n- PTP_WORK /*Work*/) {\n+ PTP_WORK work) {\n std::unique_ptr f(static_cast(parameter));\n (*f)();\n+ CloseThreadpoolWork(work);\n }\n };\n \n /**************************************************************************************************/\n \n #elif STLAB_TASK_SYSTEM(PORTABLE)\n \n+inline auto queue_size() {\n+#ifdef STLAB_UNIT_TEST\n+ // The test cannot run with less than two cores\n+ return std::max(2u, std::thread::hardware_concurrency());\n+#else\n+ return std::thread::hardware_concurrency();\n+#endif\n+}\n+\n class notification_queue {\n using lock_t = std::unique_lock;\n std::deque> _q;\n@@ -295,9 +305,9 @@ class notification_queue {\n class priority_task_system {\n using lock_t = std::unique_lock;\n \n- const unsigned _count{std::thread::hardware_concurrency()};\n+ const unsigned _count{queue_size()};\n // The 64 for spinning over the queues is a value of current experience.\n- const unsigned _spin{std::thread::hardware_concurrency()<64? 64 : std::thread::hardware_concurrency()};\n+ const unsigned _spin{queue_size()<64? 64 : queue_size()};\n \n struct thread_context\n {"},{"sha":"85688b5ab96b2bc75766a4d44c63bf7756f408ec","filename":"stlab/concurrency/future.hpp","status":"modified","additions":133,"deletions":84,"changes":217,"blob_url":"https://github.com/stlab/stlab/blob/e91c2205c8c73143b0eb4b472424ea2f4feff3ec/stlab%2Fconcurrency%2Ffuture.hpp","raw_url":"https://github.com/stlab/stlab/raw/e91c2205c8c73143b0eb4b472424ea2f4feff3ec/stlab%2Fconcurrency%2Ffuture.hpp","contents_url":"https://api.github.com/repos/stlab/stlab/contents/stlab%2Fconcurrency%2Ffuture.hpp?ref=e91c2205c8c73143b0eb4b472424ea2f4feff3ec","patch":"@@ -20,6 +20,7 @@\n #include \n #include \n #include \n+#include \n #include \n #include \n #include \n@@ -130,25 +131,25 @@ struct result_of_when_all_t;\n \n template \n struct result_of_when_all_t {\n- using result_type = typename std::result_of::type;\n+ using result_type = std::invoke_result_t;\n };\n \n template \n struct result_of_when_all_t {\n- using result_type = typename std::result_of&)>::type;\n+ using result_type = std::invoke_result_t&>;\n };\n \n template \n struct result_of_when_any_t;\n \n template \n struct result_of_when_any_t {\n- using result_type = typename std::result_of::type;\n+ using result_type = std::invoke_result_t;\n };\n \n template \n struct result_of_when_any_t {\n- using result_type = typename std::result_of::type;\n+ using result_type = std::invoke_result_t;\n };\n \n template \n@@ -291,7 +292,7 @@ struct shared_base> : std::enable_shared_from_this\n auto recover(E executor, F&& f) {\n- auto p = package)>()>(\n+ auto p = package>()>(\n executor, [_f = std::forward(f), _p = future(this->shared_from_this())]() mutable {\n return std::move(_f)(std::move(_p));\n });\n@@ -328,7 +329,7 @@ struct shared_base> : std::enable_shared_from_this(executor), std::forward(f));\n \n- auto p = package)>()>(\n+ auto p = package>()>(\n executor, [_f = std::forward(f), _p = future(this->shared_from_this())]() mutable {\n return _f(std::move(_p));\n });\n@@ -452,7 +453,7 @@ struct shared_base> : std::enable_shared_from_this<\n template \n auto recover_r(bool, E executor, F&& f) {\n // rvalue case unique is assumed.\n- auto p = package)>()>(\n+ auto p = package>()>(\n executor, [_f = std::forward(f), _p = future(this->shared_from_this())]() {\n return _f(std::move(_p));\n });\n@@ -555,7 +556,7 @@ struct shared_base : std::enable_shared_from_this> {\n }\n \n template \n- auto recover(E&& executor, F&& f) -> future)>>>;\n+ auto recover(E&& executor, F&& f) -> future>>>;\n \n template \n auto recover_r(bool, F&& f) {\n@@ -1126,26 +1127,37 @@ template \n struct when_all_shared {\n // decay\n Args _args;\n+ std::mutex _guard;\n future _holds[std::tuple_size::value]{};\n- std::atomic_size_t _remaining{std::tuple_size::value};\n- std::atomic_flag _error_happened = ATOMIC_FLAG_INIT;\n+ std::size_t _remaining{std::tuple_size::value};\n std::exception_ptr _exception;\n packaged_task<> _f;\n \n template \n void done(FF&& f) {\n- assign_ready_future::assign(std::get(_args), std::forward(f));\n- if (--_remaining == 0) _f();\n+ auto run{ false };\n+ {\n+ std::unique_lock lock{ _guard };\n+ if (!_exception) {\n+ assign_ready_future::assign(std::get(_args), std::forward(f));\n+ if (--_remaining == 0) run = true;\n+ }\n+ }\n+ if (run) _f();\n }\n \n void failure(std::exception_ptr error) {\n- auto before = _error_happened.test_and_set();\n- if (before == false) {\n- for (auto& h : _holds)\n- h.reset();\n- _exception = std::move(error);\n- _f();\n+ auto run{ false };\n+ {\n+ std::unique_lock lock{ _guard };\n+ if (!_exception) {\n+ for (auto& h : _holds)\n+ h.reset();\n+ _exception = std::move(error);\n+ run = true;\n+ }\n }\n+ if (run) _f();\n }\n };\n \n@@ -1154,28 +1166,37 @@ struct when_any_shared {\n using result_type = R;\n // decay\n stlab::optional _arg;\n+ std::mutex _guard;\n future _holds[S]{};\n- std::atomic_size_t _remaining{S};\n- std::atomic_flag _value_received = ATOMIC_FLAG_INIT;\n+ std::size_t _remaining{S};\n std::exception_ptr _exception;\n- size_t _index;\n+ std::size_t _index = std::numeric_limits::max();\n packaged_task<> _f;\n \n void failure(std::exception_ptr error) {\n- if (--_remaining == 0) {\n- _exception = std::move(error);\n- _f();\n+ auto run{ false };\n+ {\n+ std::unique_lock lock{ _guard };\n+ if (--_remaining == 0) {\n+ _exception = std::move(error);\n+ run = true;\n+ }\n }\n+ if (run) _f();\n }\n \n template \n void done(FF&& f) {\n- auto before = _value_received.test_and_set();\n- if (before == false) {\n- _arg = std::move(*std::forward(f).get_try());\n- _index = index;\n- _f();\n+ auto run{ false };\n+ {\n+ std::unique_lock lock{ _guard };\n+ if (_index == std::numeric_limits::max()) {\n+ _arg = std::move(*std::forward(f).get_try());\n+ _index = index;\n+ run = true;\n+ }\n }\n+ if (run) _f();\n }\n \n template \n@@ -1188,27 +1209,36 @@ template \n struct when_any_shared {\n using result_type = void;\n // decay\n+ std::mutex _guard;\n future _holds[S]{};\n- std::atomic_size_t _remaining{S};\n- std::atomic_flag _value_received = ATOMIC_FLAG_INIT;\n+ std::size_t _remaining{S};\n std::exception_ptr _exception;\n- size_t _index;\n+ std::size_t _index = std::numeric_limits::max();\n packaged_task<> _f;\n \n void failure(std::exception_ptr error) {\n- if (--_remaining == 0) {\n- _exception = std::move(error);\n- _f();\n+ auto run{ false };\n+ std::unique_lock lock{ _guard };\n+ {\n+ if (--_remaining == 0) {\n+ _exception = std::move(error);\n+ run = true;\n+ }\n }\n+ if (run) _f();\n }\n \n template \n void done(FF&&) {\n- auto before = _value_received.test_and_set();\n- if (before == false) {\n- _index = index;\n- _f();\n+ auto run{ false };\n+ {\n+ std::unique_lock lock{ _guard };\n+ if (_index == std::numeric_limits::max()) {\n+ _index = index;\n+ run = true;\n+ }\n }\n+ if (run) _f();\n }\n \n template \n@@ -1247,6 +1277,7 @@ auto apply_when_any_arg(F& f, P& p) {\n \n template \n void attach_when_arg_(E&& executor, std::shared_ptr

& p, T a) {\n+ std::unique_lock lock{ p->_guard };\n p->_holds[i] = std::move(a).recover(std::forward(executor), [_w = std::weak_ptr

(p)](auto x) {\n auto p = _w.lock();\n if (!p) return;\n@@ -1296,7 +1327,7 @@ template \n struct make_when_any {\n template \n static auto make(E executor, F f, future arg, future... args) {\n- using result_t = typename std::result_of::type;\n+ using result_t = std::invoke_result_t;\n \n auto shared = std::make_shared>();\n auto p = package(executor, [_f = std::move(f), _p = shared] {\n@@ -1316,7 +1347,7 @@ template <>\n struct make_when_any {\n template \n static auto make(E executor, F&& f, future... args) {\n- using result_t = typename std::result_of::type;\n+ using result_t = std::invoke_result_t;\n \n auto shared = std::make_shared>();\n auto p = package(executor, [_f = std::forward(f), _p = shared] {\n@@ -1344,21 +1375,21 @@ namespace detail {\n template \n struct value_storer {\n template \n- static void store(C& c, F&& f, size_t index) {\n- c._results = std::move(*std::forward(f).get_try());\n- c._index = index;\n+ static void store(C& context, F&& f, std::size_t index) {\n+ context._results = std::move(*std::forward(f).get_try());\n+ context._index = index;\n }\n };\n \n template \n struct value_storer> {\n template \n- static void store(C& c, F&& f, size_t index) {\n- c._results[index] = std::move(*std::forward(f).get_try());\n+ static void store(C& context, F&& f, std::size_t index) {\n+ context._results[index] = std::move(*std::forward(f).get_try());\n }\n };\n \n-template \n+template \n struct result_creator;\n \n template <>\n@@ -1399,43 +1430,43 @@ struct context_result {\n \n R _results;\n std::exception_ptr _exception;\n- size_t _index;\n+ std::size_t _index{0};\n F _f;\n \n- context_result(F f, size_t s) : _index(0), _f(std::move(f)) { init(_results, s); }\n+ context_result(F f, std::size_t s) : _f(std::move(f)) { init(_results, s); }\n \n template \n- void init(std::vector& v, size_t s) {\n+ void init(std::vector& v, std::size_t s) {\n v.resize(s);\n }\n \n template \n- void init(T&, size_t) {}\n+ void init(T&, std::size_t) {}\n \n template \n- void apply(FF&& f, size_t index) {\n+ void apply(FF&& f, std::size_t index) {\n value_storer::store(*this, std::forward(f), index);\n }\n \n- void apply(std::exception_ptr error, size_t) { _exception = std::move(error); }\n+ void apply(std::exception_ptr error, std::size_t) { _exception = std::move(error); }\n \n auto operator()() { return result_creator::go(*this); }\n };\n \n template \n struct context_result {\n std::exception_ptr _exception;\n- size_t _index;\n+ std::size_t _index{0};\n F _f;\n \n- context_result(F f, size_t) : _f(std::move(f)) {}\n+ context_result(F f, std::size_t) : _f(std::move(f)) {}\n \n template \n- void apply(FF&&, size_t index) {\n+ void apply(FF&&, std::size_t index) {\n _index = index;\n }\n \n- void apply(std::exception_ptr error, size_t) { _exception = std::move(error); }\n+ void apply(std::exception_ptr error, std::size_t) { _exception = std::move(error); }\n \n auto operator()() { return result_creator::go(*this); }\n };\n@@ -1444,20 +1475,26 @@ struct context_result {\n \n /*\n * This specialization is used for cases when only one ready future is enough to move forward.\n- * In case of when_any, the first successfull future triggers the continuation. All others are\n- * cancelled. In case of when_all, after the first error, this future cannot be fullfilled anymore\n+ * In case of when_any, the first successful future triggers the continuation. All others are\n+ * cancelled. In case of when_all, after the first error, this future cannot be fulfilled anymore\n * and so we cancel the all the others.\n */\n struct single_trigger {\n template \n- static void go(C& context, F&& f, size_t index) {\n- auto before = context._single_event_trigger.test_and_set();\n- if (!before) {\n- for (auto& h : context._holds)\n- h.reset();\n- context.apply(std::forward(f), index);\n- context._f();\n+ static bool go(C& context, F&& f, size_t index) {\n+ auto run{ false };\n+ {\n+ std::unique_lock lock{ context._guard };\n+ if (!context._single_event) {\n+ for (auto i = 0u; i < context._holds.size(); ++i) {\n+ if (i != index) context._holds[i].reset();\n+ }\n+ context._single_event = true;\n+ context.apply(std::forward(f), index);\n+ run = true;\n+ }\n }\n+ return run;\n }\n };\n \n@@ -1469,24 +1506,35 @@ struct single_trigger {\n */\n struct all_trigger {\n template \n- static void go(C& context, F&& f, size_t index) {\n- context.apply(std::forward(f), index);\n- if (--context._remaining == 0) context._f();\n+ static bool go(C& context, F&& f, size_t index) {\n+ auto run{ false };\n+ {\n+ std::unique_lock lock{ context._guard };\n+ context.apply(std::forward(f), index);\n+ if (--context._remaining == 0) run = true;\n+ }\n+ return run;\n }\n \n template \n- static void go(C& context, std::exception_ptr error, size_t index) {\n- if (--context._remaining == 0) {\n- context.apply(std::move(error), index);\n- context._f();\n+ static bool go(C& context, std::exception_ptr error, size_t index) {\n+ auto run{ false };\n+ {\n+ std::unique_lock lock{ context._guard };\n+ if (--context._remaining == 0) {\n+ context.apply(std::move(error), index);\n+ run = true;\n+ }\n }\n+ return run;\n }\n };\n \n template \n struct common_context : CR {\n- std::atomic_size_t _remaining;\n- std::atomic_flag _single_event_trigger = ATOMIC_FLAG_INIT;\n+ std::mutex _guard;\n+ std::size_t _remaining;\n+ bool _single_event{false};\n std::vector> _holds;\n packaged_task<> _f;\n \n@@ -1500,21 +1548,22 @@ struct common_context : CR {\n }\n \n void failure(std::exception_ptr& error, size_t index) {\n- FailureCollector::go(*this, error, index);\n+ if (FailureCollector::go(*this, error, index)) _f();\n }\n \n template \n void done(FF&& f, size_t index) {\n- ResultCollector::go(*this, std::forward(f), index);\n+ if (ResultCollector::go(*this, std::forward(f), index)) _f();\n }\n };\n \n /**************************************************************************************************/\n \n template \n void attach_tasks(size_t index, E executor, const std::shared_ptr& context, T&& a) {\n+ std::unique_lock guard(context->_guard);\n context->_holds[index] =\n- std::move(a).recover(std::move(executor), [_context = std::weak_ptr(context), _i = index](auto x) {\n+ std::move(a).recover(std::move(executor), [_context = make_weak_ptr(context), _i = index](auto x) {\n auto p = _context.lock();\n if (!p) return;\n if (auto ex = x.exception(); ex) {\n@@ -1627,8 +1676,8 @@ auto when_any(E executor, F&& f, std::pair range) {\n \n template \n auto async(E executor, F&& f, Args&&... args)\n- -> future(std::decay_t...)>> {\n- using result_type = std::result_of_t(std::decay_t...)>;\n+ -> future, std::decay_t...>> {\n+ using result_type = std::invoke_result_t, std::decay_t...>;\n \n auto p = package(\n executor, std::bind(\n@@ -1795,8 +1844,8 @@ void shared_base::set_value(F& f, Args&&... args) {\n \n template \n auto shared_base::recover(E&& executor, F&& f)\n- -> future)>>> {\n- auto p = package)>()>(\n+ -> future>>> {\n+ auto p = package>()>(\n executor, [_f = std::forward(f), _p = future(this->shared_from_this())]() mutable {\n return _f(_p);\n });\n@@ -1927,7 +1976,7 @@ auto operator co_await(stlab::future f) {\n void await_suspend(std::experimental::coroutine_handle<> ch) {\n std::move(_input)\n .then(stlab::default_executor,\n- [this, ch](auto&& result) {\n+ [this, ch](auto&& result) mutable {\n this->_result = std::forward(result);\n ch.resume();\n })\n@@ -1947,7 +1996,7 @@ inline auto operator co_await(stlab::future f) {\n \n inline void await_suspend(std::experimental::coroutine_handle<> ch) {\n std::move(_input)\n- .then(stlab::default_executor, [ch]() { ch.resume(); })\n+ .then(stlab::default_executor, [ch]() mutable { ch.resume(); })\n .detach();\n }\n };"},{"sha":"76107275f6746e429100643635ef6a7daad5907e","filename":"stlab/concurrency/system_timer.hpp","status":"modified","additions":6,"deletions":2,"changes":8,"blob_url":"https://github.com/stlab/stlab/blob/e91c2205c8c73143b0eb4b472424ea2f4feff3ec/stlab%2Fconcurrency%2Fsystem_timer.hpp","raw_url":"https://github.com/stlab/stlab/raw/e91c2205c8c73143b0eb4b472424ea2f4feff3ec/stlab%2Fconcurrency%2Fsystem_timer.hpp","contents_url":"https://api.github.com/repos/stlab/stlab/contents/stlab%2Fconcurrency%2Fsystem_timer.hpp?ref=e91c2205c8c73143b0eb4b472424ea2f4feff3ec","patch":"@@ -260,6 +260,11 @@ class system_timer {\n \n struct system_timer_type {\n using result_type = void;\n+ \n+ static system_timer& get_system_timer() {\n+ static system_timer only_system_timer;\n+ return only_system_timer;\n+ }\n \n [[deprecated(\"Use chrono::duration as parameter instead\")]]\n void operator()(std::chrono::steady_clock::time_point when, task f) const {\n@@ -268,8 +273,7 @@ struct system_timer_type {\n \n template >\n void operator()(std::chrono::duration duration, task f) const {\n- static system_timer only_system_timer;\n- only_system_timer(duration, std::move(f));\n+ get_system_timer()(duration, std::move(f));\n }\n };\n "},{"sha":"5fead8f543315bbf0c9666dbdf326aa34ac148fb","filename":"stlab/forest.hpp","status":"added","additions":1225,"deletions":0,"changes":1225,"blob_url":"https://github.com/stlab/stlab/blob/e91c2205c8c73143b0eb4b472424ea2f4feff3ec/stlab%2Fforest.hpp","raw_url":"https://github.com/stlab/stlab/raw/e91c2205c8c73143b0eb4b472424ea2f4feff3ec/stlab%2Fforest.hpp","contents_url":"https://api.github.com/repos/stlab/stlab/contents/stlab%2Fforest.hpp?ref=e91c2205c8c73143b0eb4b472424ea2f4feff3ec","patch":"@@ -0,0 +1,1225 @@\n+/*\n+ Copyright 2013 Adobe\n+ Distributed under the Boost Software License, Version 1.0.\n+ (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)\n+*/\n+/**************************************************************************************************/\n+\n+#ifndef STLAB_FOREST_HPP\n+#define STLAB_FOREST_HPP\n+\n+/**************************************************************************************************/\n+\n+#include \n+#include \n+#include \n+#include \n+\n+#include \n+#include \n+\n+/**************************************************************************************************/\n+\n+namespace stlab {\n+\n+/**************************************************************************************************/\n+\n+enum class forest_edge : bool { trailing, leading };\n+\n+constexpr auto forest_trailing_edge{forest_edge::trailing};\n+constexpr auto forest_leading_edge{forest_edge::leading};\n+\n+/**************************************************************************************************/\n+\n+constexpr auto pivot(forest_edge e) { return forest_edge(static_cast(e) ^ 1); }\n+\n+template // I models FullorderIterator\n+void pivot(I& i) {\n+ i.edge() = pivot(i.edge());\n+}\n+\n+template // I models FullorderIterator\n+auto pivot_of(I i) {\n+ pivot(i);\n+ return i;\n+}\n+\n+/**************************************************************************************************/\n+\n+template // I models a FullorderIterator\n+auto leading_of(I i) {\n+ i.edge() = forest_edge::leading;\n+ return i;\n+}\n+\n+template // I models a FullorderIterator\n+auto trailing_of(I i) {\n+ i.edge() = forest_edge::trailing;\n+ return i;\n+}\n+\n+/**************************************************************************************************/\n+\n+constexpr auto is_leading(forest_edge e) {\n+ return e == forest_edge::leading;\n+}\n+\n+template // I models a FullorderIterator\n+auto is_leading(const I& i) {\n+ return is_leading(i.edge());\n+}\n+\n+constexpr auto is_trailing(forest_edge e) {\n+ return e == forest_edge::trailing;\n+}\n+\n+template // I models a FullorderIterator\n+auto is_trailing(const I& i) {\n+ return is_trailing(i.edge());\n+}\n+\n+/**************************************************************************************************/\n+\n+template // I models FullorderIterator\n+I find_parent(I i) {\n+ do {\n+ i = std::next(trailing_of(i));\n+ } while (i.edge() != forest_edge::trailing);\n+ return i;\n+}\n+\n+/**************************************************************************************************/\n+\n+template // I models FullorderIterator\n+bool has_children(const I& i) {\n+ return !i.equal_node(std::next(leading_of(i)));\n+}\n+\n+/**************************************************************************************************/\n+\n+template // I models FullorderIterator\n+struct child_iterator {\n+ using value_type = typename std::iterator_traits::value_type;\n+ using difference_type = typename std::iterator_traits::difference_type;\n+ using reference = typename std::iterator_traits::reference;\n+ using pointer = typename std::iterator_traits::pointer;\n+ using iterator_category = typename std::iterator_traits::iterator_category;\n+\n+ child_iterator() = default;\n+ explicit child_iterator(I x) : _x(std::move(x)) {}\n+ template \n+ child_iterator(const child_iterator& u) : _x(u.base()) {}\n+\n+ I base() const { return _x; }\n+\n+ reference operator*() { return dereference(); }\n+ pointer operator->() { return &dereference(); }\n+ auto& operator++() {\n+ increment();\n+ return *this;\n+ }\n+ auto operator++(int) {\n+ auto result{*this};\n+ increment();\n+ return result;\n+ }\n+ auto& operator--() {\n+ decrement();\n+ return *this;\n+ }\n+ auto operator--(int) {\n+ auto result{*this};\n+ decrement();\n+ return result;\n+ }\n+\n+ friend bool operator==(const child_iterator& a, const child_iterator& b) {\n+ return a.base() == b.base();\n+ }\n+ friend bool operator!=(const child_iterator& a, const child_iterator& b) { return !(a == b); }\n+\n+private:\n+ I _x;\n+\n+ void increment() {\n+ pivot(_x);\n+ ++_x;\n+ }\n+ void decrement() {\n+ --_x;\n+ pivot(_x);\n+ }\n+\n+ reference dereference() { return *_x; }\n+};\n+\n+/**************************************************************************************************/\n+\n+template // I models FullorderIterator\n+I find_edge(I x, forest_edge edge) {\n+ while (x.edge() != edge)\n+ ++x;\n+ return x;\n+}\n+\n+template // I models FullorderIterator\n+I find_edge_reverse(I x, forest_edge edge) {\n+ while (x.edge() != edge)\n+ --x;\n+ return x;\n+}\n+\n+/**************************************************************************************************/\n+\n+template // I models FullorderIterator\n+struct edge_iterator {\n+ using value_type = typename std::iterator_traits::value_type;\n+ using difference_type = typename std::iterator_traits::difference_type;\n+ using reference = typename std::iterator_traits::reference;\n+ using pointer = typename std::iterator_traits::pointer;\n+ using iterator_category = typename std::iterator_traits::iterator_category;\n+\n+ edge_iterator() = default;\n+ explicit edge_iterator(I x) : _x(find_edge(x, Edge)) {}\n+ template \n+ edge_iterator(const edge_iterator& u) : _x(u.base()) {}\n+\n+ I base() const { return _x; }\n+\n+ reference operator*() { return dereference(); }\n+ pointer operator->() { return &dereference(); }\n+ auto& operator++() {\n+ increment();\n+ return *this;\n+ }\n+ auto operator++(int) {\n+ auto result{*this};\n+ increment();\n+ return result;\n+ }\n+ auto& operator--() {\n+ decrement();\n+ return *this;\n+ }\n+ auto operator--(int) {\n+ auto result{*this};\n+ decrement();\n+ return result;\n+ }\n+\n+ friend bool operator==(const edge_iterator& a, const edge_iterator& b) {\n+ return a.base() == b.base();\n+ }\n+ friend bool operator!=(const edge_iterator& a, const edge_iterator& b) { return !(a == b); }\n+\n+private:\n+ I _x;\n+\n+ void increment() { _x = find_edge(std::next(_x), Edge); }\n+\n+ void decrement() { _x = find_edge_reverse(std::prev(_x), Edge); }\n+\n+ reference dereference() { return *_x; }\n+};\n+\n+/**************************************************************************************************/\n+\n+template // P models UnaryPredicate of value_type(I)\n+struct filter_fullorder_iterator {\n+ using value_type = typename std::iterator_traits::value_type;\n+ using difference_type = typename std::iterator_traits::difference_type;\n+ using reference = typename std::iterator_traits::reference;\n+ using pointer = typename std::iterator_traits::pointer;\n+ using iterator_category = typename std::iterator_traits::iterator_category;\n+\n+ filter_fullorder_iterator() = default;\n+\n+ filter_fullorder_iterator(I f, I l, P p) :\n+ _x(skip_forward(f, l, p)), _inside(true), _first(f), _last(l), _predicate(p) {}\n+\n+ filter_fullorder_iterator(I f, I l) :\n+ _x(skip_forward(f, l, P())), _inside(true), _first(f), _last(l) {}\n+\n+ template \n+ filter_fullorder_iterator(const filter_fullorder_iterator& x) :\n+ _x(x.base()), _inside(x._inside), _first(x._first), _last(x._last),\n+ _predicate(x._predicate) {}\n+\n+ P predicate() const { return _predicate; }\n+\n+ forest_edge edge() const { return this->base().edge(); }\n+ forest_edge& edge() { return this->base_reference().edge(); }\n+\n+ bool equal_node(const filter_fullorder_iterator& y) const {\n+ return this->base().equal_node(y.base());\n+ }\n+\n+ I base() const { return _x; }\n+\n+ reference operator*() { return dereference(); }\n+ pointer operator->() { return &dereference(); }\n+ auto& operator++() {\n+ increment();\n+ return *this;\n+ }\n+ auto operator++(int) {\n+ auto result{*this};\n+ increment();\n+ return result;\n+ }\n+ auto& operator--() {\n+ decrement();\n+ return *this;\n+ }\n+ auto operator--(int) {\n+ auto result{*this};\n+ decrement();\n+ return result;\n+ }\n+\n+ friend bool operator==(const filter_fullorder_iterator& a, const filter_fullorder_iterator& b) {\n+ return a.base() == b.base();\n+ }\n+ friend bool operator!=(const filter_fullorder_iterator& a, const filter_fullorder_iterator& b) {\n+ return !(a == b);\n+ }\n+\n+private:\n+ I _x;\n+ bool _inside;\n+ I _first;\n+ I _last;\n+ P _predicate;\n+\n+ void increment() {\n+ I i = this->base();\n+\n+ if (i == _last) _inside = false;\n+ ++i;\n+ if (i == _first) _inside = true;\n+ if (_inside) i = skip_forward(i, _last, _predicate);\n+ this->base_reference() = i;\n+ }\n+\n+ static I skip_forward(I f, I l, P p)\n+ // Precondition: l is on a leading edge\n+ {\n+ while ((f.edge() == forest_edge::leading) && (f != l) && !p(*f)) {\n+ f.edge() = forest_edge::trailing;\n+ ++f;\n+ }\n+ return f;\n+ }\n+\n+ static I skip_backward(I f, I l, P p)\n+ // Precondition: f is on a trailing edge\n+ {\n+ while ((l.edge() == forest_edge::trailing) && (f != l) && !p(*l)) {\n+ l.edge() = forest_edge::leading;\n+ --l;\n+ }\n+ return l;\n+ }\n+\n+ void decrement() {\n+ I i = this->base();\n+\n+ if (i == _first) _inside = false;\n+ --i;\n+ if (i == _last) _inside = true;\n+ if (_inside) i = skip_backward(_first, i, _predicate);\n+ this->base_reference() = i;\n+ }\n+\n+ reference dereference() { return *_x; }\n+};\n+\n+/**************************************************************************************************/\n+\n+template // I models a FullorderIterator\n+struct reverse_fullorder_iterator {\n+ using iterator_type = I;\n+\n+ using value_type = typename std::iterator_traits::value_type;\n+ using difference_type = typename std::iterator_traits::difference_type;\n+ using reference = typename std::iterator_traits::reference;\n+ using pointer = typename std::iterator_traits::pointer;\n+ using iterator_category = typename std::iterator_traits::iterator_category;\n+\n+ reverse_fullorder_iterator() : _edge(forest_edge::trailing) {}\n+ explicit reverse_fullorder_iterator(I x) : _base(--x), _edge(pivot(_base.edge())) {}\n+ template \n+ reverse_fullorder_iterator(const reverse_fullorder_iterator& x) :\n+ _base(--x.base()), _edge(pivot(_base.edge())) {}\n+\n+ iterator_type base() const { return std::next(_base); }\n+\n+ forest_edge edge() const { return _edge; }\n+ forest_edge& edge() { return _edge; }\n+\n+ bool equal_node(const reverse_fullorder_iterator& y) const { return _base.equal_node(y._base); }\n+\n+ reference operator*() { return dereference(); }\n+ pointer operator->() { return &dereference(); }\n+ auto& operator++() {\n+ increment();\n+ return *this;\n+ }\n+ auto operator++(int) {\n+ auto result{*this};\n+ increment();\n+ return result;\n+ }\n+ auto& operator--() {\n+ decrement();\n+ return *this;\n+ }\n+ auto operator--(int) {\n+ auto result{*this};\n+ decrement();\n+ return result;\n+ }\n+\n+ friend bool operator==(const reverse_fullorder_iterator& a,\n+ const reverse_fullorder_iterator& b) {\n+ return a.equal(b);\n+ }\n+ friend bool operator!=(const reverse_fullorder_iterator& a,\n+ const reverse_fullorder_iterator& b) {\n+ return !(a == b);\n+ }\n+\n+private:\n+ I _base;\n+ forest_edge _edge;\n+\n+ void increment() {\n+ _base.edge() = pivot(_edge);\n+ --_base;\n+ _edge = pivot(_base.edge());\n+ }\n+ void decrement() {\n+ _base.edge() = pivot(_edge);\n+ ++_base;\n+ _edge = pivot(_base.edge());\n+ }\n+ reference dereference() const { return *_base; }\n+\n+ bool equal(const reverse_fullorder_iterator& y) const {\n+ return (_base == y._base) && (_edge == y._edge);\n+ }\n+};\n+\n+/**************************************************************************************************/\n+\n+template // I models FullorderIterator\n+struct depth_fullorder_iterator {\n+ using value_type = typename std::iterator_traits::value_type;\n+ using difference_type = typename std::iterator_traits::difference_type;\n+ using reference = typename std::iterator_traits::reference;\n+ using pointer = typename std::iterator_traits::pointer;\n+ using iterator_category = typename std::iterator_traits::iterator_category;\n+\n+ depth_fullorder_iterator(difference_type d = 0) : _depth(d) {}\n+ explicit depth_fullorder_iterator(I x, difference_type d = 0) : _x(x), _depth(d) {}\n+ template \n+ depth_fullorder_iterator(const depth_fullorder_iterator& x) :\n+ _x(x.base()), _depth(x._depth) {}\n+\n+ difference_type depth() const { return _depth; }\n+ forest_edge edge() const { return this->base().edge(); }\n+ forest_edge& edge() { return _x.edge(); }\n+ bool equal_node(depth_fullorder_iterator const& y) const {\n+ return this->base().equal_node(y.base());\n+ }\n+\n+ I base() const { return _x; }\n+\n+ reference operator*() { return dereference(); }\n+ pointer operator->() { return &dereference(); }\n+ auto& operator++() {\n+ increment();\n+ return *this;\n+ }\n+ auto operator++(int) {\n+ auto result{*this};\n+ increment();\n+ return result;\n+ }\n+ auto& operator--() {\n+ decrement();\n+ return *this;\n+ }\n+ auto operator--(int) {\n+ auto result{*this};\n+ decrement();\n+ return result;\n+ }\n+\n+ friend bool operator==(const depth_fullorder_iterator& a, const depth_fullorder_iterator& b) {\n+ return a.base() == b.base();\n+ }\n+ friend bool operator!=(const depth_fullorder_iterator& a, const depth_fullorder_iterator& b) {\n+ return !(a == b);\n+ }\n+\n+private:\n+ I _x;\n+ difference_type _depth;\n+\n+ void increment() {\n+ forest_edge old_edge(edge());\n+ ++_x;\n+ if (old_edge == edge())\n+ _depth += difference_type(static_cast(old_edge) << 1) - 1;\n+ }\n+\n+ void decrement() {\n+ forest_edge old_edge(edge());\n+ --_x;\n+ if (old_edge == edge())\n+ _depth -= difference_type(static_cast(old_edge) << 1) - 1;\n+ }\n+\n+ reference dereference() { return *_x; }\n+};\n+\n+/**************************************************************************************************/\n+\n+template \n+class child_adaptor;\n+template \n+class forest;\n+\n+/**************************************************************************************************/\n+\n+namespace detail {\n+\n+/**************************************************************************************************/\n+\n+template // derived class\n+struct node_base {\n+ enum next_prior_t { prior_s, next_s };\n+\n+ using node_ptr = D*;\n+ using reference = node_ptr&;\n+\n+ node_ptr& link(forest_edge edge, next_prior_t link) {\n+ return _nodes[static_cast(edge)][static_cast(link)];\n+ }\n+\n+ node_ptr link(forest_edge edge, next_prior_t link) const {\n+ return _nodes[static_cast(edge)][static_cast(link)];\n+ }\n+\n+ node_ptr _nodes[2][2];\n+\n+ node_base() :\n+ _nodes{{static_cast(this), static_cast(this)},\n+ {static_cast(this), static_cast(this)}} {}\n+};\n+\n+template // T models Regular\n+struct node : public node_base> {\n+ using value_type = T;\n+\n+ explicit node(const value_type& data) : _data(data) {}\n+\n+ value_type _data;\n+};\n+\n+/**************************************************************************************************/\n+\n+template \n+struct forest_const_iterator;\n+\n+template // T is value_type\n+struct forest_iterator {\n+ using value_type = T;\n+ using difference_type = std::ptrdiff_t;\n+ using reference = T&;\n+ using pointer = T*;\n+ using iterator_category = std::bidirectional_iterator_tag;\n+\n+ forest_iterator() = default;\n+\n+ forest_iterator(const forest_iterator& x) : _node(x._node), _edge(x._edge) {}\n+\n+ forest_edge edge() const { return _edge; }\n+ forest_edge& edge() { return _edge; }\n+\n+ bool equal_node(forest_iterator const& y) const { return _node == y._node; }\n+\n+ reference operator*() const { return dereference(); }\n+ pointer operator->() const { return &dereference(); }\n+ auto& operator++() {\n+ increment();\n+ return *this;\n+ }\n+ auto operator++(int) {\n+ auto result{*this};\n+ increment();\n+ return result;\n+ }\n+ auto& operator--() {\n+ decrement();\n+ return *this;\n+ }\n+ auto operator--(int) {\n+ auto result{*this};\n+ decrement();\n+ return result;\n+ }\n+\n+ friend bool operator==(const forest_iterator& a, const forest_iterator& b) {\n+ return a.equal(b);\n+ }\n+ friend bool operator!=(const forest_iterator& a, const forest_iterator& b) { return !(a == b); }\n+\n+private:\n+ friend class stlab::forest;\n+ template \n+ friend struct forest_iterator;\n+ template \n+ friend struct forest_const_iterator;\n+ friend struct unsafe::set_next_fn;\n+\n+ using node_t = node;\n+\n+ reference dereference() const { return _node->_data; }\n+\n+ void increment() {\n+ node_t* next(_node->link(_edge, node_t::next_s));\n+\n+ if (is_leading(_edge))\n+ _edge = forest_edge(next != _node);\n+ else\n+ _edge = forest_edge(next->link(forest_edge::leading, node_t::prior_s) == _node);\n+\n+ _node = next;\n+ }\n+\n+ void decrement() {\n+ node_t* next(_node->link(_edge, node_t::prior_s));\n+\n+ if (is_leading(_edge))\n+ _edge = forest_edge(next->link(forest_edge::trailing, node_t::next_s) != _node);\n+ else\n+ _edge = forest_edge(next == _node);\n+\n+ _node = next;\n+ }\n+\n+ bool equal(const forest_iterator& y) const { return (_node == y._node) && (_edge == y._edge); }\n+\n+ node_t* _node{nullptr};\n+ forest_edge _edge{forest_edge::leading};\n+\n+ forest_iterator(node_t* node, forest_edge edge) : _node(node), _edge(edge) {}\n+};\n+\n+/**************************************************************************************************/\n+\n+template // T is value_type\n+struct forest_const_iterator {\n+ using value_type = const T;\n+ using difference_type = std::ptrdiff_t;\n+ using reference = const T&;\n+ using pointer = const T*;\n+ using iterator_category = std::bidirectional_iterator_tag;\n+\n+ forest_const_iterator() = default;\n+\n+ forest_const_iterator(const forest_const_iterator& x) : _node(x._node), _edge(x._edge) {}\n+\n+ forest_const_iterator(const forest_iterator& x) : _node(x._node), _edge(x._edge) {}\n+\n+ forest_edge edge() const { return _edge; }\n+ forest_edge& edge() { return _edge; }\n+ bool equal_node(forest_const_iterator const& y) const { return _node == y._node; }\n+\n+ reference operator*() const { return dereference(); }\n+ pointer operator->() const { return &dereference(); }\n+ auto& operator++() {\n+ increment();\n+ return *this;\n+ }\n+ auto operator++(int) {\n+ auto result{*this};\n+ increment();\n+ return result;\n+ }\n+ auto& operator--() {\n+ decrement();\n+ return *this;\n+ }\n+ auto operator--(int) {\n+ auto result{*this};\n+ decrement();\n+ return result;\n+ }\n+\n+ friend bool operator==(const forest_const_iterator& a, const forest_const_iterator& b) {\n+ return a.equal(b);\n+ }\n+ friend bool operator!=(const forest_const_iterator& a, const forest_const_iterator& b) {\n+ return !(a == b);\n+ }\n+\n+private:\n+ template \n+ friend class stlab::forest;\n+ template \n+ friend struct forest_const_iterator;\n+ friend struct unsafe::set_next_fn;\n+\n+ using node_t = const node;\n+\n+ reference dereference() const { return _node->_data; }\n+\n+ void increment() {\n+ node_t* next(_node->link(_edge, node_t::next_s));\n+\n+ if (is_leading(_edge))\n+ _edge = forest_edge(next != _node);\n+ else\n+ _edge = forest_edge(next->link(forest_edge::leading, node_t::prior_s) == _node);\n+\n+ _node = next;\n+ }\n+\n+ void decrement() {\n+ node_t* next(_node->link(_edge, node_t::prior_s));\n+\n+ if (is_leading(_edge))\n+ _edge = forest_edge(next->link(forest_edge::trailing, node_t::next_s) != _node);\n+ else\n+ _edge = forest_edge(next == _node);\n+\n+ _node = next;\n+ }\n+\n+ bool equal(const forest_const_iterator& y) const {\n+ return (_node == y._node) && (_edge == y._edge);\n+ }\n+\n+ node_t* _node{nullptr};\n+ forest_edge _edge{forest_edge::leading};\n+\n+ forest_const_iterator(node_t* node, forest_edge edge) : _node(node), _edge(edge) {}\n+};\n+\n+/**************************************************************************************************/\n+\n+} // namespace detail\n+\n+/**************************************************************************************************/\n+\n+namespace unsafe {\n+\n+/**************************************************************************************************/\n+\n+template // T is node\n+struct set_next_fn> {\n+ void operator()(detail::forest_iterator x, detail::forest_iterator y) const {\n+ using node_t = typename detail::node;\n+\n+ x._node->link(x.edge(), node_t::next_s) = y._node;\n+ y._node->link(y.edge(), node_t::prior_s) = x._node;\n+ }\n+};\n+\n+/**************************************************************************************************/\n+\n+} // namespace unsafe\n+\n+/**************************************************************************************************/\n+\n+template \n+class forest {\n+private:\n+ using node_t = detail::node;\n+ friend class child_adaptor>;\n+\n+public:\n+ // types\n+ using reference = T&;\n+ using const_reference = const T&;\n+ using iterator = detail::forest_iterator;\n+ using const_iterator = detail::forest_const_iterator;\n+ using size_type = std::size_t;\n+ using difference_type = std::ptrdiff_t;\n+ using value_type = T;\n+ using pointer = T*;\n+ using const_pointer = const T*;\n+ using reverse_iterator = reverse_fullorder_iterator;\n+ using const_reverse_iterator = reverse_fullorder_iterator;\n+\n+ /* qualification needed since: A name N used in a class S shall refer to the same declaration\n+ in its context and when re-evaluated in the completed scope of\n+ S. */\n+ using child_iterator = stlab::child_iterator;\n+ using const_child_iterator = stlab::child_iterator;\n+ using reverse_child_iterator = std::reverse_iterator;\n+\n+ using preorder_iterator = edge_iterator;\n+ using const_preorder_iterator = edge_iterator;\n+ using postorder_iterator = edge_iterator;\n+ using const_postorder_iterator = edge_iterator;\n+\n+ forest() = default;\n+ ~forest() { clear(); }\n+\n+ forest(const forest& x) : forest() {\n+ insert(end(), const_child_iterator(x.begin()), const_child_iterator(x.end()));\n+ }\n+ forest(forest&& x) noexcept : forest() { splice(end(), x); }\n+ forest& operator=(const forest& x) {\n+ return *this = forest(x);\n+ }\n+ forest& operator=(forest&& x) noexcept {\n+ auto tmp{move(x)}; // this is `release()`\n+ clear(); // these two lines are `reset()`\n+ splice(end(), tmp);\n+ return *this;\n+ }\n+\n+ void swap(forest& x) { std::swap(*this, x); }\n+\n+ size_type size() const;\n+ size_type max_size() const { return size_type(-1); }\n+ bool size_valid() const { return _size != 0 || empty(); }\n+ bool empty() const { return begin() == end(); } // Don't test size which may be expensive\n+\n+ // iterators\n+ iterator root() { return iterator(tail(), forest_edge::leading); }\n+ const_iterator root() const { return const_iterator(tail(), forest_edge::leading); }\n+\n+ iterator begin() { return ++root(); }\n+ iterator end() { return iterator(tail(), forest_edge::trailing); }\n+ const_iterator begin() const { return ++root(); }\n+ const_iterator end() const { return const_iterator(tail(), forest_edge::trailing); }\n+\n+ reverse_iterator rbegin() { return reverse_iterator(end()); }\n+ reverse_iterator rend() { return reverse_iterator(begin()); }\n+ const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }\n+ const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }\n+\n+ reference front() {\n+ assert(!empty());\n+ return *begin();\n+ }\n+ const_reference front() const {\n+ assert(!empty());\n+ return *begin();\n+ }\n+ reference back() {\n+ assert(!empty());\n+ return *(--end());\n+ }\n+ const_reference back() const {\n+ assert(!empty());\n+ return *(--end());\n+ }\n+\n+ // modifiers\n+ void clear() {\n+ erase(begin(), end());\n+ assert(empty()); // Make sure our erase is correct\n+ }\n+\n+ iterator erase(const iterator& position);\n+ iterator erase(const iterator& first, const iterator& last);\n+\n+ iterator insert(const iterator& position, T x) {\n+ iterator result(new node_t(std::move(x)), forest_edge::leading);\n+\n+ if (size_valid()) ++_size;\n+\n+ unsafe::set_next(std::prev(position), result);\n+ unsafe::set_next(std::next(result), position);\n+\n+ return result;\n+ }\n+\n+ void push_front(const T& x) { insert(begin(), x); }\n+ void push_back(const T& x) { insert(end(), x); }\n+ void pop_front() {\n+ assert(!empty());\n+ erase(begin());\n+ }\n+ void pop_back() {\n+ assert(!empty());\n+ erase(--end());\n+ }\n+\n+ iterator insert(iterator position, const_child_iterator first, const_child_iterator last);\n+\n+ iterator splice(iterator position, forest& x);\n+ iterator splice(iterator position, forest& x, iterator i);\n+ iterator splice(iterator position, forest& x, child_iterator first, child_iterator last);\n+ iterator splice(iterator position,\n+ forest& x,\n+ child_iterator first,\n+ child_iterator last,\n+ size_type count);\n+\n+ iterator insert_parent(child_iterator front, child_iterator back, const T& x);\n+ void reverse(child_iterator first, child_iterator last);\n+\n+private:\n+ friend struct detail::forest_iterator;\n+ friend struct detail::forest_const_iterator;\n+ friend struct unsafe::set_next_fn;\n+\n+ mutable size_type _size{0};\n+ detail::node_base _tail;\n+\n+ node_t* tail() { return static_cast(&_tail); }\n+ const node_t* tail() const { return static_cast(&_tail); }\n+};\n+\n+/**************************************************************************************************/\n+\n+template \n+bool operator==(const forest& x, const forest& y) {\n+ if (x.size() != y.size()) return false;\n+\n+ for (auto first(x.begin()), last(x.end()), pos(y.begin()); first != last; ++first, ++pos) {\n+ if (first.edge() != pos.edge()) return false;\n+ if (is_leading(first) && (*first != *pos)) return false;\n+ }\n+\n+ return true;\n+}\n+\n+template \n+bool operator!=(const forest& x, const forest& y) {\n+ return !(x == y);\n+}\n+\n+/**************************************************************************************************/\n+\n+namespace unsafe {\n+\n+/**************************************************************************************************/\n+\n+template // I models a FullorderIterator\n+struct set_next_fn> {\n+ void operator()(child_iterator x, child_iterator y) {\n+ unsafe::set_next(pivot_of(x.base()), y.base());\n+ }\n+};\n+\n+/**************************************************************************************************/\n+\n+} // namespace unsafe\n+\n+/**************************************************************************************************/\n+\n+template \n+typename forest::size_type forest::size() const {\n+ if (!size_valid()) {\n+ const_preorder_iterator first(begin());\n+ const_preorder_iterator last(end());\n+\n+ _size = size_type(std::distance(first, last));\n+ }\n+\n+ return _size;\n+}\n+\n+/**************************************************************************************************/\n+\n+template \n+typename forest::iterator forest::erase(const iterator& first, const iterator& last) {\n+ difference_type stack_depth(0);\n+ iterator position(first);\n+\n+ while (position != last) {\n+ if (position.edge() == forest_edge::leading) {\n+ ++stack_depth;\n+ ++position;\n+ } else {\n+ if (stack_depth > 0)\n+ position = erase(position);\n+ else\n+ ++position;\n+ stack_depth = std::max(0, stack_depth - 1);\n+ }\n+ }\n+ return last;\n+}\n+\n+/**************************************************************************************************/\n+\n+template \n+typename forest::iterator forest::erase(const iterator& position) {\n+ /*\n+ NOTE (sparent) : After the first call to set_next() the invariants of the forest are\n+ violated and we can't determing leading/trailing if we navigate from the affected node.\n+ So we gather all the iterators up front then do the set_next calls.\n+ */\n+\n+ if (size_valid()) --_size;\n+\n+ iterator leading_prior(std::prev(leading_of(position)));\n+ iterator leading_next(std::next(leading_of(position)));\n+ iterator trailing_prior(std::prev(trailing_of(position)));\n+ iterator trailing_next(std::next(trailing_of(position)));\n+\n+ if (has_children(position)) {\n+ unsafe::set_next(leading_prior, leading_next);\n+ unsafe::set_next(trailing_prior, trailing_next);\n+ } else {\n+ unsafe::set_next(leading_prior, trailing_next);\n+ }\n+\n+ delete position._node;\n+\n+ return is_leading(position) ? std::next(leading_prior) : trailing_next;\n+}\n+\n+/**************************************************************************************************/\n+\n+template \n+typename forest::iterator forest::splice(iterator position, forest& x) {\n+ return splice(position, x, child_iterator(x.begin()), child_iterator(x.end()),\n+ x.size_valid() ? x.size() : 0);\n+}\n+\n+/**************************************************************************************************/\n+\n+template \n+typename forest::iterator forest::splice(iterator position, forest& x, iterator i) {\n+ i.edge() = forest_edge::leading;\n+ return splice(position, x, child_iterator(i), ++child_iterator(i), has_children(i) ? 0 : 1);\n+}\n+\n+/**************************************************************************************************/\n+\n+template \n+typename forest::iterator forest::insert(iterator pos,\n+ const_child_iterator f,\n+ const_child_iterator l) {\n+ for (const_iterator first(f.base()), last(l.base()); first != last; ++first, ++pos) {\n+ if (is_leading(first)) pos = insert(pos, *first);\n+ }\n+\n+ return pos;\n+}\n+\n+/**************************************************************************************************/\n+\n+template \n+typename forest::iterator forest::splice(\n+ iterator pos, forest& x, child_iterator first, child_iterator last, size_type count) {\n+ if (first == last || first.base() == pos) return pos;\n+\n+ if (&x != this) {\n+ if (count) {\n+ if (size_valid()) _size += count;\n+ if (x.size_valid()) x._size -= count;\n+ } else {\n+ _size = 0;\n+ x._size = 0;\n+ }\n+ }\n+\n+ iterator back(std::prev(last.base()));\n+\n+ unsafe::set_next(std::prev(first), last);\n+\n+ unsafe::set_next(std::prev(pos), first.base());\n+ unsafe::set_next(back, pos);\n+\n+ return first.base();\n+}\n+\n+/**************************************************************************************************/\n+\n+template \n+typename forest::iterator forest::splice(iterator pos,\n+ forest& x,\n+ child_iterator first,\n+ child_iterator last) {\n+ return splice(pos, x, first, last, 0);\n+}\n+\n+/**************************************************************************************************/\n+\n+template \n+typename forest::iterator forest::insert_parent(child_iterator first,\n+ child_iterator last,\n+ const T& x) {\n+ iterator result(insert(last.base(), x));\n+ if (first == last) return result;\n+ splice(trailing_of(result), *this, first, child_iterator(result));\n+ return result;\n+}\n+\n+/**************************************************************************************************/\n+\n+template \n+void forest::reverse(child_iterator first, child_iterator last) {\n+ iterator prior(first.base());\n+ --prior;\n+ first = unsafe::reverse_nodes(first, last);\n+ unsafe::set_next(prior, first.base());\n+}\n+\n+/**************************************************************************************************/\n+\n+template // I models FullorderIterator\n+child_iterator child_begin(const I& x) {\n+ return child_iterator(std::next(leading_of(x)));\n+}\n+\n+/**************************************************************************************************/\n+\n+template // I models FullorderIterator\n+child_iterator child_end(const I& x) {\n+ return child_iterator(trailing_of(x));\n+}\n+\n+/**************************************************************************************************/\n+\n+template \n+class child_adaptor {\n+public:\n+ using forest_type = Forest;\n+ using value_type = typename Forest::value_type;\n+ using iterator_type = typename Forest::iterator;\n+ using reference = typename Forest::reference;\n+ using const_reference = typename Forest::const_reference;\n+ using difference_type = typename Forest::difference_type;\n+ using iterator = typename Forest::child_iterator;\n+\n+ child_adaptor(forest_type& f, iterator_type& i) : _forest(f), _iterator(i) {}\n+\n+ value_type& back() { return *(--child_end(_iterator)); }\n+ value_type& front() { return *(child_begin(_iterator)); }\n+\n+ void push_back(const value_type& x) { _forest.insert(child_end(_iterator).base(), x); }\n+ void push_front(const value_type& x) { _forest.insert(child_begin(_iterator).base(), x); }\n+\n+ void pop_back() { _forest.erase(--child_end(_iterator).base()); }\n+ void pop_front() { _forest.erase(child_begin(_iterator).base()); }\n+\n+private:\n+ child_adaptor(); // not defined\n+\n+ forest_type& _forest;\n+ iterator_type& _iterator;\n+};\n+\n+/**************************************************************************************************/\n+\n+template \n+struct forest_range {\n+ I _f;\n+ I _l;\n+\n+ auto begin() const { return _f; }\n+ auto end() const { return _l; }\n+};\n+\n+/**************************************************************************************************/\n+\n+template // I models FullorderIterator\n+auto child_range(const I& x) {\n+ return forest_range>{child_begin(x), child_end(x)};\n+}\n+\n+/**************************************************************************************************/\n+\n+template // R models FullorderRange\n+auto filter_fullorder_range(R& x, P p) {\n+ using iterator = filter_fullorder_iterator;\n+\n+ return forest_range{iterator(std::begin(x), std::end(x), p),\n+ iterator(std::end(x), std::end(x), p)};\n+}\n+\n+template // R models FullorderRange\n+auto filter_fullorder_range(const R& x, P p) {\n+ using iterator = filter_fullorder_iterator;\n+\n+ return forest_range{iterator(std::begin(x), std::end(x), p),\n+ iterator(std::end(x), std::end(x), p)};\n+}\n+\n+/**************************************************************************************************/\n+\n+template // R models FullorderRange\n+auto reverse_fullorder_range(R& x) {\n+ using iterator = reverse_fullorder_iterator;\n+\n+ return forest_range{iterator(std::end(x)), iterator(std::begin(x))};\n+}\n+\n+template // R models FullorderRange\n+auto reverse_fullorder_range(const R& x) {\n+ using iterator = reverse_fullorder_iterator;\n+\n+ return forest_range{iterator(std::end(x)), iterator(std::begin(x))};\n+}\n+\n+/**************************************************************************************************/\n+\n+template // R models FullorderRange\n+auto depth_range(R& x) {\n+ using iterator = depth_fullorder_iterator;\n+\n+ return forest_range{iterator(std::begin(x)), iterator(std::end(x))};\n+}\n+\n+template // R models FullorderRange\n+auto depth_range(const R& x) {\n+ using iterator = depth_fullorder_iterator;\n+\n+ return forest_range{iterator(std::begin(x)), iterator(std::end(x))};\n+}\n+\n+/**************************************************************************************************/\n+\n+template // R models FullorderRange\n+auto postorder_range(R& x) {\n+ using iterator = edge_iterator;\n+\n+ return forest_range{iterator(std::begin(x)), iterator(std::end(x))};\n+}\n+\n+template // R models FullorderRange\n+auto postorder_range(const R& x) {\n+ using iterator = edge_iterator;\n+\n+ return forest_range{iterator(std::begin(x)), iterator(std::end(x))};\n+}\n+\n+/**************************************************************************************************/\n+\n+template // R models FullorderRange\n+auto preorder_range(R& x) {\n+ using iterator = edge_iterator;\n+\n+ return forest_range{iterator(std::begin(x)), iterator(std::end(x))};\n+}\n+\n+template // R models FullorderRange\n+auto preorder_range(const R& x) {\n+ using iterator = edge_iterator;\n+\n+ return forest_range{iterator(std::begin(x)), iterator(std::end(x))};\n+}\n+\n+/**************************************************************************************************/\n+\n+} // namespace stlab\n+\n+/**************************************************************************************************/\n+\n+#endif // STLAB_FOREST_HPP\n+\n+/**************************************************************************************************/"},{"sha":"3a73fd101a2ff800758b69a2f7b1df4956528d15","filename":"stlab/forest_algorithms.hpp","status":"added","additions":146,"deletions":0,"changes":146,"blob_url":"https://github.com/stlab/stlab/blob/e91c2205c8c73143b0eb4b472424ea2f4feff3ec/stlab%2Fforest_algorithms.hpp","raw_url":"https://github.com/stlab/stlab/raw/e91c2205c8c73143b0eb4b472424ea2f4feff3ec/stlab%2Fforest_algorithms.hpp","contents_url":"https://api.github.com/repos/stlab/stlab/contents/stlab%2Fforest_algorithms.hpp?ref=e91c2205c8c73143b0eb4b472424ea2f4feff3ec","patch":"@@ -0,0 +1,146 @@\n+/**************************************************************************************************/\n+\n+#ifndef STLAB_FOREST_ALGORITHMS_HPP\n+#define STLAB_FOREST_ALGORITHMS_HPP\n+\n+/**************************************************************************************************/\n+\n+// stlab\n+#include \n+#include \n+\n+/**************************************************************************************************/\n+\n+namespace stlab {\n+\n+/**************************************************************************************************/\n+\n+namespace forests {\n+\n+/**************************************************************************************************/\n+// \"Congruent\" would be a nice name here, but in geometry that also implies reflection.\n+template \n+bool equal_shape(const Forest1& x, const Forest2& y) {\n+ if (x.size_valid() && y.size_valid() && x.size() != y.size()) return false;\n+ auto pos{y.begin()};\n+ for (auto first(x.begin()), last(x.end()); first != last; ++first, ++pos) {\n+ if (first.edge() != pos.edge()) return false;\n+ }\n+ return true;\n+}\n+\n+/**************************************************************************************************/\n+\n+template \n+struct transcribe_iterator {\n+ using iterator_category = std::output_iterator_tag;\n+ using value_type = void;\n+ using difference_type = void;\n+ using pointer = void;\n+ using reference = void;\n+ using container_type = Container;\n+\n+ transcribe_iterator(Container& c, typename Container::iterator i) : _c{&c}, _i{std::move(i)} {}\n+\n+ constexpr auto& operator*() { return *this; }\n+ constexpr auto& operator++() {\n+ ++_i;\n+ return *this;\n+ }\n+ constexpr auto operator++(int) {\n+ auto result{*this};\n+ ++_i;\n+ return result;\n+ }\n+\n+ constexpr auto& operator=(const typename Container::value_type& value) {\n+ _i = _c->insert(_i, value);\n+ return *this;\n+ }\n+\n+ constexpr auto& operator=(typename Container::value_type&& value) {\n+ _i = _c->insert(_i, std::move(value));\n+ return *this;\n+ }\n+\n+ constexpr auto trailing() { _i = trailing_of(_i); }\n+\n+private:\n+ Container* _c;\n+ typename Container::iterator _i;\n+};\n+\n+template \n+auto transcriber(Container& c) {\n+ return transcribe_iterator(c, c.begin());\n+}\n+\n+/**************************************************************************************************/\n+\n+template \n+auto transcribe(I first, I last, O out, P proj, UP pred) {\n+ for (; first != last; ++first, ++out) {\n+ if (pred(first)) {\n+ out = proj(*first);\n+ } else {\n+ out.trailing();\n+ }\n+ }\n+ return out;\n+}\n+\n+template \n+auto transcribe(const R& range, O out, P proj, UP pred) {\n+ return transcribe(std::cbegin(range), std::cend(range), std::move(out), std::move(proj),\n+ std::move(pred));\n+}\n+\n+template \n+auto transcribe(I first, I last, O out, P proj) {\n+ return transcribe(std::move(first), std::move(last), std::move(out), std::move(proj),\n+ [](const auto& p) { return is_leading(p); });\n+}\n+\n+template \n+auto transcribe(const R& range, O out, P proj) {\n+ return transcribe(std::cbegin(range), std::cend(range), std::move(out), std::move(proj));\n+}\n+\n+/**************************************************************************************************/\n+\n+template // models OutputIterator\n+auto flatten(I first, I last, O out) {\n+ for (; first != last; ++first) {\n+ if (is_leading(first)) {\n+ *out++ = *first;\n+ } else {\n+ *out++ = std::nullopt;\n+ }\n+ }\n+ return out;\n+}\n+\n+/**************************************************************************************************/\n+\n+template \n+ class F> // F models Forest\n+auto unflatten(I first, I last, F& f) {\n+ return forests::transcribe(\n+ first, last, transcriber(f), [](const auto& x) { return *x; },\n+ [](const auto& p) { return *p; });\n+}\n+\n+/**************************************************************************************************/\n+\n+} // namespace forests\n+\n+/**************************************************************************************************/\n+\n+} // namespace stlab\n+\n+/**************************************************************************************************/\n+\n+#endif // STLAB_FOREST_ALGORITHMS_HPP\n+\n+/**************************************************************************************************/"},{"sha":"446a01f3d37b411ec5ccf41eae718f0eec77e001","filename":"stlab/iterator/set_next.hpp","status":"added","additions":62,"deletions":0,"changes":62,"blob_url":"https://github.com/stlab/stlab/blob/e91c2205c8c73143b0eb4b472424ea2f4feff3ec/stlab%2Fiterator%2Fset_next.hpp","raw_url":"https://github.com/stlab/stlab/raw/e91c2205c8c73143b0eb4b472424ea2f4feff3ec/stlab%2Fiterator%2Fset_next.hpp","contents_url":"https://api.github.com/repos/stlab/stlab/contents/stlab%2Fiterator%2Fset_next.hpp?ref=e91c2205c8c73143b0eb4b472424ea2f4feff3ec","patch":"@@ -0,0 +1,62 @@\n+/*\n+ Copyright 2013 Adobe\n+ Distributed under the Boost Software License, Version 1.0.\n+ (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)\n+*/\n+/*************************************************************************************************/\n+\n+#ifndef STLAB_ITERATOR_SET_NEXT_HPP\n+#define STLAB_ITERATOR_SET_NEXT_HPP\n+\n+/*************************************************************************************************/\n+\n+namespace stlab {\n+\n+/*************************************************************************************************/\n+\n+namespace unsafe {\n+\n+/*************************************************************************************************/\n+\n+template // I models NodeIterator\n+struct set_next_fn; // Must be specialized\n+\n+/*************************************************************************************************/\n+\n+template // I models NodeIterator\n+inline void set_next(I x, I y) {\n+ set_next_fn()(x, y);\n+}\n+\n+/*************************************************************************************************/\n+\n+template // T models ForwardNodeIterator\n+inline void splice_node_range(I location, I first, I last) {\n+ I successor(std::next(location));\n+ set_next(location, first);\n+ set_next(last, successor);\n+}\n+\n+template // I models ForwardNodeIterator\n+inline void skip_next_node(I location) {\n+ set_next(location, std::next(std::next(location)));\n+}\n+\n+template // I models BidirectionalNodeIterator\n+inline void skip_node(I location) {\n+ set_next(std::prev(location), std::next(location));\n+}\n+\n+/*************************************************************************************************/\n+\n+} // namespace unsafe\n+\n+/*************************************************************************************************/\n+\n+} // namespace stlab\n+\n+/*************************************************************************************************/\n+\n+#endif // STLAB_ITERATOR_SET_NEXT_HPP\n+\n+/*************************************************************************************************/"},{"sha":"d3464e1852986580bf2b22ccc9484662c129f61e","filename":"stlab/version.hpp","status":"modified","additions":2,"deletions":2,"changes":4,"blob_url":"https://github.com/stlab/stlab/blob/e91c2205c8c73143b0eb4b472424ea2f4feff3ec/stlab%2Fversion.hpp","raw_url":"https://github.com/stlab/stlab/raw/e91c2205c8c73143b0eb4b472424ea2f4feff3ec/stlab%2Fversion.hpp","contents_url":"https://api.github.com/repos/stlab/stlab/contents/stlab%2Fversion.hpp?ref=e91c2205c8c73143b0eb4b472424ea2f4feff3ec","patch":"@@ -19,13 +19,13 @@\n // STLAB_VERSION / 100 % 1000 is the minor version\n // STLAB_VERSION / 100000 is the major version\n \n-#define STLAB_VERSION 100502\n+#define STLAB_VERSION 100503\n \n //\n // STLAB_LIB_VERSION must be defined to be the same as STLAB_VERSION\n // but as a *string* in the form \"x_y[_z]\" where x is the major version\n // number, y is the minor version number, and z is the patch level if not 0.\n \n-#define STLAB_LIB_VERSION \"1_5_2\"\n+#define STLAB_LIB_VERSION \"1_5_3\"\n \n #endif"},{"sha":"dd0c481daf172b5afddd5af097b3ee746f7a7081","filename":"test/CMakeLists.txt","status":"modified","additions":26,"deletions":0,"changes":26,"blob_url":"https://github.com/stlab/stlab/blob/e91c2205c8c73143b0eb4b472424ea2f4feff3ec/test%2FCMakeLists.txt","raw_url":"https://github.com/stlab/stlab/raw/e91c2205c8c73143b0eb4b472424ea2f4feff3ec/test%2FCMakeLists.txt","contents_url":"https://api.github.com/repos/stlab/stlab/contents/test%2FCMakeLists.txt?ref=e91c2205c8c73143b0eb4b472424ea2f4feff3ec","patch":"@@ -12,6 +12,8 @@ if( NOT ( ${CMAKE_CXX_COMPILER_ID} STREQUAL \"MSVC\"\n tuple_algorithm_test.cpp\n main.cpp\n channel_test_helper.hpp )\n+\n+ target_compile_definitions(stlab.test.channel PRIVATE STLAB_UNIT_TEST)\n endif()\n \n target_link_libraries( stlab.test.channel PUBLIC stlab::testing )\n@@ -23,6 +25,8 @@ add_executable( stlab.test.executor\n executor_test.cpp\n main.cpp)\n \n+target_compile_definitions(stlab.test.executor PRIVATE STLAB_UNIT_TEST)\n+\n target_link_libraries( stlab.test.executor PUBLIC stlab::testing )\n add_test( NAME stlab.test.executor COMMAND stlab.test.executor )\n \n@@ -44,6 +48,9 @@ add_executable( stlab.test.future\n \n target_sources( stlab.test.future PUBLIC\n $<$>:future_coroutine_tests.cpp> )\n+\n+target_compile_definitions(stlab.test.future PRIVATE STLAB_UNIT_TEST)\n+\n target_link_libraries( stlab.test.future PUBLIC stlab::testing )\n add_test( NAME stlab.test.future COMMAND stlab.test.future )\n \n@@ -52,6 +59,8 @@ add_test( NAME stlab.test.future COMMAND stlab.test.future )\n add_executable( stlab.test.serial_queue\n serial_queue_test.cpp )\n \n+target_compile_definitions(stlab.test.serial_queue PRIVATE STLAB_UNIT_TEST)\n+\n target_link_libraries( stlab.test.serial_queue PUBLIC stlab::testing )\n add_test( NAME stlab.test.serial_queue COMMAND stlab.test.serial_queue )\n \n@@ -61,6 +70,8 @@ add_executable( stlab.test.cow\n cow_test.cpp\n main.cpp )\n \n+target_compile_definitions(stlab.test.cow PRIVATE STLAB_UNIT_TEST)\n+\n target_link_libraries( stlab.test.cow PUBLIC stlab::testing )\n add_test( NAME stlab.test.cow COMMAND stlab.test.cow )\n \n@@ -70,6 +81,8 @@ add_executable( stlab.test.task\n task_test.cpp\n main.cpp )\n \n+target_compile_definitions(stlab.test.task PRIVATE STLAB_UNIT_TEST)\n+\n target_link_libraries( stlab.test.task PUBLIC stlab::testing )\n add_test( NAME stlab.test.task COMMAND stlab.test.task )\n \n@@ -79,6 +92,8 @@ add_executable( stlab.test.tuple\n tuple_test.cpp\n main.cpp )\n \n+target_compile_definitions(stlab.test.channel PRIVATE STLAB_UNIT_TEST)\n+\n target_link_libraries( stlab.test.tuple PUBLIC stlab::testing )\n add_test( NAME stlab.test.tuple COMMAND stlab.test.tuple )\n \n@@ -88,9 +103,20 @@ add_executable( stlab.test.traits\n traits_test.cpp\n main.cpp )\n \n+target_compile_definitions(stlab.test.channel PRIVATE STLAB_UNIT_TEST)\n+\n target_link_libraries( stlab.test.traits PUBLIC stlab::testing )\n add_test( NAME stlab.test.traits COMMAND stlab.test.traits )\n \n+################################################################################\n+\n+add_executable( stlab.test.forest\n+ forest_test.cpp\n+ main.cpp )\n+\n+target_link_libraries( stlab.test.forest PUBLIC stlab::testing )\n+add_test( NAME stlab.test.forest COMMAND stlab.test.forest )\n+\n ################################################################################\n #\n # tests are compiled without compiler extensions to ensure the stlab headers"},{"sha":"4c7c2e9b30448cb2005177333b55634b733e61d6","filename":"test/executor_test.cpp","status":"modified","additions":128,"deletions":35,"changes":163,"blob_url":"https://github.com/stlab/stlab/blob/e91c2205c8c73143b0eb4b472424ea2f4feff3ec/test%2Fexecutor_test.cpp","raw_url":"https://github.com/stlab/stlab/raw/e91c2205c8c73143b0eb4b472424ea2f4feff3ec/test%2Fexecutor_test.cpp","contents_url":"https://api.github.com/repos/stlab/stlab/contents/test%2Fexecutor_test.cpp?ref=e91c2205c8c73143b0eb4b472424ea2f4feff3ec","patch":"@@ -5,21 +5,66 @@\n */\n /**************************************************************************************************/\n \n+#include \n #include \n \n #include \n #include \n \n+#include \n #include \n #include \n #include \n \n using namespace stlab;\n using namespace std;\n \n+namespace mp = boost::multiprecision;\n+\n+\n namespace\n {\n-inline void rest() { std::this_thread::sleep_for(std::chrono::milliseconds(1)); }\n+void rest() { std::this_thread::sleep_for(std::chrono::milliseconds(1)); }\n+\n+\n+template \n+T power(T x, N n, O op)\n+{\n+ if (n == 0) return identity_element(op);\n+\n+ while ((n & 1) == 0) {\n+ n >>= 1;\n+ x = op(x, x);\n+ }\n+\n+ T result = x;\n+ n >>= 1;\n+ while (n != 0) {\n+ x = op(x, x);\n+ if ((n & 1) != 0) result = op(result, x);\n+ n >>= 1;\n+ }\n+ return result;\n+}\n+\n+template \n+struct multiply_2x2 {\n+ std::array operator()(const std::array& x, const std::array& y)\n+ {\n+ return { x[0] * y[0] + x[1] * y[2], x[0] * y[1] + x[1] * y[3],\n+ x[2] * y[0] + x[3] * y[2], x[2] * y[1] + x[3] * y[3] };\n+ }\n+};\n+template \n+std::array identity_element(const multiply_2x2&) { return { N(1), N(0), N(0), N(1) }; }\n+\n+\n+template \n+R fibonacci(N n) {\n+ if (n == 0) return R(0);\n+ return power(std::array{ 1, 1, 1, 0 }, N(n - 1), multiply_2x2())[0];\n+}\n+\n }\n \n BOOST_AUTO_TEST_CASE(all_low_prio_tasks_are_executed) {\n@@ -140,53 +185,98 @@ BOOST_AUTO_TEST_CASE(task_system_restarts_after_it_went_pending) {\n BOOST_REQUIRE(!done);\n }\n \n-BOOST_AUTO_TEST_CASE(all_tasks_will_be_executed_according_to_their_prio) {\n- BOOST_TEST_MESSAGE(\"All tasks will be executed according to their prio\");\n+namespace\n+{\n+ auto fiboN{ 1000 };\n+ const auto iterations = 100'000;\n+ const auto startCount = 100;\n+ atomic_int workToDo = (iterations - startCount) * 3;\n+ const auto expectedWork = startCount * 3 + workToDo;\n+ atomic_int highCount{0};\n+ atomic_int defaultCount{0};\n+ atomic_int lowCount{0};\n+\n+ atomic_int taskRunning{0};\n+ atomic_int done{0};\n+\n \n- const auto iterations = 300000;\n- std::atomic_int done{0};\n- std::atomic_int highCount{0};\n- std::atomic_int defaultCount{0};\n- std::atomic_int correctDefault{0};\n- std::atomic_int correctLow{0};\n- std::atomic_int taskRunning{0};\n+ atomic_int correctLow{ 0 };\n+ atomic_int correctDefault{ 0 };\n+ atomic_int correctHigh{ 0 };\n+\n+ template\n+ struct check_task\n {\n- for (auto i = 0; i < iterations; ++i) {\n- low_executor([&] {\n- ++taskRunning;\n- correctLow += static_cast(highCount <= taskRunning && defaultCount <= taskRunning);\n- ++done;\n- --taskRunning;\n- });\n- ++defaultCount;\n- default_executor([&] {\n- ++taskRunning;\n- correctDefault += static_cast(highCount <= taskRunning);\n- --defaultCount;\n- ++done;\n- --taskRunning;\n- });\n- ++highCount;\n- high_executor([&] {\n- ++taskRunning;\n- --highCount;\n- ++done;\n- --taskRunning;\n- });\n+ atomic_int &_correctScheduleCount;\n+ atomic_int &_currentPrioCount;\n+\n+ check_task(atomic_int &correctCount, atomic_int& prioCount)\n+ : _correctScheduleCount(correctCount)\n+ , _currentPrioCount(prioCount)\n+ {\n+ ++_currentPrioCount;\n }\n- }\n \n- while (done != iterations * 3) {\n+ void operator()() {\n+ --_currentPrioCount;\n+\n+ ++taskRunning;\n+\n+ if constexpr (P == stlab::detail::executor_priority::low)\n+ _correctScheduleCount += static_cast(highCount <= taskRunning && defaultCount <= taskRunning);\n+\n+ if constexpr (P == stlab::detail::executor_priority::medium) {\n+ _correctScheduleCount += static_cast(highCount <= taskRunning);\n+ }\n+\n+ fibonacci(fiboN);\n+\n+ switch (workToDo % 3)\n+ {\n+ case 0:\n+ default_executor(check_task{correctDefault, defaultCount});\n+ break;\n+ \n+ case 1:\n+ high_executor(check_task{correctHigh, highCount});\n+ break;\n+\n+ case 2:\n+ low_executor(check_task{correctLow, lowCount});\n+ break;\n+ }\n+ --workToDo;\n+\n+ ++done;\n+ --taskRunning;\n+ }\n+ };\n+}\n+\n+BOOST_AUTO_TEST_CASE(all_tasks_will_be_executed_according_to_their_prio) {\n+ BOOST_TEST_MESSAGE(\"All tasks will be executed according to their prio\");\n+\n+ auto start = chrono::high_resolution_clock::now();\n+\n+ for (auto i = 0; i < startCount; ++i) {\n+ low_executor(check_task{correctLow, lowCount});\n+ high_executor(check_task{correctHigh, highCount});\n+ default_executor(check_task{correctDefault, defaultCount});\n+ }\n+ while (done < expectedWork) {\n rest();\n }\n \n+ auto stop = std::chrono::high_resolution_clock::now();\n+ std::cout << \"\\nPerformance measuring: \" << std::chrono::duration(stop - start).count() << \"s\\n\";\n+\n cout << \"Correct default ordering: \" << static_cast(correctDefault.load())/iterations <<\"%\\n\";\n cout << \"Correct low ordering: \" << static_cast(correctLow.load())/iterations << \"%\\n\";\n }\n \n BOOST_AUTO_TEST_CASE(MeasureTiming) {\n std::vector results;\n- const auto iterations = 100000;\n+ const auto iterations = 300'000;\n results.resize(iterations * 3);\n atomic_bool done = false;\n condition_variable ready;\n@@ -197,14 +287,17 @@ BOOST_AUTO_TEST_CASE(MeasureTiming) {\n for (auto i = 0; i < iterations; ++i) {\n low_executor([_i = i, &results,&counter] {\n results[_i] = 1;\n+ fibonacci(fiboN);\n ++counter;\n });\n default_executor([_i = i + iterations, &results,&counter] {\n results[_i] = 2;\n+ fibonacci(fiboN);\n ++counter;\n });\n high_executor([_i = i + iterations * 2, &results,&counter] {\n results[_i] = 3;\n+ fibonacci(fiboN);\n ++counter;\n });\n }"},{"sha":"ef99b70d512fda064be89bb4c1fabfee47248942","filename":"test/forest_test.cpp","status":"added","additions":476,"deletions":0,"changes":476,"blob_url":"https://github.com/stlab/stlab/blob/e91c2205c8c73143b0eb4b472424ea2f4feff3ec/test%2Fforest_test.cpp","raw_url":"https://github.com/stlab/stlab/raw/e91c2205c8c73143b0eb4b472424ea2f4feff3ec/test%2Fforest_test.cpp","contents_url":"https://api.github.com/repos/stlab/stlab/contents/test%2Fforest_test.cpp?ref=e91c2205c8c73143b0eb4b472424ea2f4feff3ec","patch":"@@ -0,0 +1,476 @@\n+/**************************************************************************************************/\n+\n+// stdc++\n+#include \n+\n+// boost\n+#include \n+\n+// stlab\n+#include \n+#include \n+\n+/**************************************************************************************************/\n+\n+using namespace stlab;\n+\n+/**************************************************************************************************/\n+\n+namespace {\n+\n+/**************************************************************************************************/\n+\n+template \n+void print(const forest& f) {\n+ auto first{f.begin()};\n+ auto last{f.end()};\n+ std::size_t depth{0};\n+\n+ while (first != last) {\n+ if (is_trailing(first)) {\n+ --depth;\n+ }\n+\n+ for (std::size_t i{0}; i < depth; ++i) std::cout << \" \";\n+\n+ if (is_leading(first)) {\n+ std::cout << \"<\";\n+ ++depth;\n+ } else {\n+ std::cout << \"\\n\";\n+ ++first;\n+ }\n+}\n+\n+/**************************************************************************************************/\n+\n+} // namespace\n+\n+/**************************************************************************************************/\n+\n+BOOST_AUTO_TEST_CASE(empty_forest) {\n+ forest f;\n+ BOOST_CHECK(f.empty());\n+ BOOST_CHECK(f.size() == 0);\n+ BOOST_CHECK(f.begin() == f.end());\n+}\n+\n+/**************************************************************************************************/\n+\n+BOOST_AUTO_TEST_CASE(single_node_forest) {\n+ forest f;\n+\n+ auto il = f.insert(f.end(), 42);\n+ BOOST_CHECK(il.edge() == forest_edge::leading);\n+ BOOST_CHECK(*il == 42);\n+ BOOST_CHECK(!f.empty());\n+\n+ BOOST_CHECK(f.begin() != f.end());\n+ BOOST_CHECK(f.size() == 1);\n+\n+ auto it = trailing_of(il);\n+ BOOST_CHECK(it.edge() == forest_edge::trailing);\n+ BOOST_CHECK(*it == *il);\n+}\n+\n+/**************************************************************************************************/\n+\n+namespace {\n+\n+/**************************************************************************************************/\n+\n+auto big_test_forest() {\n+ forest f;\n+\n+ auto a_iter = trailing_of(f.insert(f.end(), \"A\"));\n+\n+ auto b_iter = trailing_of(f.insert(a_iter, \"B\"));\n+\n+ auto c_iter = trailing_of(f.insert(b_iter, \"C\"));\n+ auto d_iter = trailing_of(f.insert(b_iter, \"D\"));\n+ auto e_iter = f.insert(b_iter, \"E\");\n+\n+ f.insert(c_iter, \"F\");\n+ f.insert(c_iter, \"G\");\n+ f.insert(c_iter, \"H\");\n+\n+ f.insert(d_iter, \"I\");\n+ f.insert(d_iter, \"J\");\n+ f.insert(d_iter, \"K\");\n+\n+ BOOST_CHECK(f.size() == 11);\n+\n+ BOOST_CHECK(has_children(a_iter));\n+ BOOST_CHECK(has_children(b_iter));\n+ BOOST_CHECK(has_children(c_iter));\n+ BOOST_CHECK(has_children(d_iter));\n+ BOOST_CHECK(!has_children(e_iter));\n+\n+ return f;\n+}\n+\n+/**************************************************************************************************/\n+\n+namespace detail {\n+\n+/**************************************************************************************************/\n+\n+template \n+auto to_string(const T& x) {\n+ return std::to_string(x);\n+}\n+\n+template <>\n+auto to_string(const std::string& x) {\n+ return x;\n+}\n+\n+template <>\n+auto to_string(const std::optional& x) {\n+ return x ? to_string(*x) : \"?\";\n+}\n+\n+/**************************************************************************************************/\n+\n+} // namespace detail\n+\n+/**************************************************************************************************/\n+\n+template \n+auto to_string(const R& r) {\n+ std::string result;\n+ for (const auto& x : r) {\n+ result += detail::to_string(x);\n+ }\n+ return result;\n+}\n+\n+template \n+auto to_string(I first, I last) {\n+ std::string result;\n+ while (first != last) {\n+ result += *first++;\n+ }\n+ return result;\n+}\n+\n+/**************************************************************************************************/\n+\n+template \n+void test_fullorder_traversal(Iterator first, Iterator last, const std::string& expected) {\n+ BOOST_CHECK(to_string(first, last) == expected);\n+}\n+\n+/**************************************************************************************************/\n+\n+template \n+auto test_edge_traversal(Forest& f, Iterator fi, Iterator li) {\n+ std::string expected;\n+\n+ {\n+ Iterator first{fi};\n+ Iterator last{li};\n+ while (first != last) {\n+ if (first.edge() == Edge)\n+ expected += *first;\n+ ++first;\n+ }\n+ BOOST_CHECK(expected.size() == f.size());\n+ }\n+\n+ {\n+ edge_iterator first(fi);\n+ edge_iterator last(li);\n+ std::string result{to_string(first, last)};\n+ BOOST_CHECK(result == expected);\n+ }\n+\n+ return expected;\n+}\n+\n+/**************************************************************************************************/\n+\n+using iterator_t = forest::iterator;\n+using const_iterator_t = forest::const_iterator;\n+using reverse_iterator_t = forest::reverse_iterator;\n+using const_reverse_iterator_t = forest::const_reverse_iterator;\n+\n+/**************************************************************************************************/\n+\n+} // namespace\n+\n+/**************************************************************************************************/\n+\n+BOOST_AUTO_TEST_CASE(forward_traversal) {\n+ auto f{big_test_forest()};\n+ auto first{std::begin(f)};\n+ auto last{std::end(f)};\n+\n+ /*fullorder*/ {\n+ static const auto expected{\"ABCFFGGHHCDIIJJKKDEEBA\"};\n+ test_fullorder_traversal(first, last, expected);\n+ test_fullorder_traversal(first, last, expected);\n+\n+#if 0 // fullorder_range doesn't exist?\n+ BOOST_CHECK(range_value(fullorder_range(f)) == expected);\n+#endif\n+ }\n+\n+ /*preorder*/ {\n+ auto a = test_edge_traversal(f, first, last);\n+ auto b = test_edge_traversal(f, first, last);\n+ BOOST_CHECK(a == b);\n+ BOOST_CHECK(to_string(preorder_range(f)) == a);\n+ }\n+\n+ /*postorder*/ {\n+ auto a = test_edge_traversal(f, first, last);\n+ auto b = test_edge_traversal(f, first, last);\n+ BOOST_CHECK(a == b);\n+ BOOST_CHECK(to_string(postorder_range(f)) == a);\n+ }\n+}\n+\n+/**************************************************************************************************/\n+\n+BOOST_AUTO_TEST_CASE(reverse_traversal) {\n+ auto f{big_test_forest()};\n+ auto rfirst{std::rbegin(f)};\n+ auto rlast{std::rend(f)};\n+\n+ /*fullorder*/ {\n+ static const auto expected{\"ABEEDKKJJIIDCHHGGFFCBA\"};\n+ test_fullorder_traversal(rfirst, rlast, expected);\n+ test_fullorder_traversal(rfirst, rlast, expected);\n+ BOOST_CHECK(to_string(reverse_fullorder_range(f)) == expected);\n+ }\n+\n+ /*preorder*/ {\n+ auto a = test_edge_traversal(f, rfirst, rlast);\n+ auto b = test_edge_traversal(f, rfirst, rlast);\n+ BOOST_CHECK(a == b);\n+ }\n+\n+ /*postorder*/ {\n+ auto a = test_edge_traversal(f, rfirst, rlast);\n+ auto b = test_edge_traversal(f, rfirst, rlast);\n+ BOOST_CHECK(a == b);\n+ }\n+}\n+\n+/**************************************************************************************************/\n+\n+template \n+auto find_node(Forest& f, const T& x) {\n+ return std::find_if(f.begin(), f.end(), [&](const auto& v){ return v == x; });\n+}\n+\n+/**************************************************************************************************/\n+\n+BOOST_AUTO_TEST_CASE(child_traversal) {\n+ auto f{big_test_forest()};\n+ auto parent{find_node(f, \"B\")};\n+ std::string expected;\n+\n+ BOOST_CHECK(*parent == \"B\");\n+\n+ {\n+ auto first{child_begin(parent)};\n+ auto last{child_end(parent)};\n+ expected = to_string(first, last);\n+ }\n+\n+ BOOST_CHECK(to_string(child_range(parent)) == expected);\n+\n+ if constexpr (false) { // I'm not sure reverse_child_iterator ever worked.\n+ forest::reverse_child_iterator first{child_begin(parent)};\n+ forest::reverse_child_iterator last{child_end(parent)};\n+ std::string result{to_string(first, last)};\n+ BOOST_CHECK(result == expected);\n+ }\n+}\n+\n+/**************************************************************************************************/\n+\n+BOOST_AUTO_TEST_CASE(test_find_parent) {\n+ auto f{big_test_forest()};\n+\n+ {\n+ auto child{find_node(f, \"B\")};\n+ BOOST_CHECK(*child == \"B\");\n+ auto parent{find_parent(child)};\n+ BOOST_CHECK(*parent == \"A\");\n+ }\n+\n+ {\n+ auto child{find_node(f, \"J\")};\n+ BOOST_CHECK(*child == \"J\");\n+ auto parent{find_parent(child)};\n+ BOOST_CHECK(*parent == \"D\");\n+ }\n+}\n+\n+/**************************************************************************************************/\n+\n+BOOST_AUTO_TEST_CASE(test_has_children) {\n+ auto f{big_test_forest()};\n+\n+ /*pass*/ {\n+ auto node{find_node(f, \"B\")};\n+ BOOST_CHECK(*node == \"B\");\n+ BOOST_CHECK(has_children(node));\n+ }\n+\n+ /*fail*/ {\n+ auto node{find_node(f, \"J\")};\n+ BOOST_CHECK(*node == \"J\");\n+ BOOST_CHECK(!has_children(node));\n+ }\n+}\n+\n+/**************************************************************************************************/\n+\n+BOOST_AUTO_TEST_CASE(erase) {\n+ auto f{big_test_forest()};\n+\n+ /*single node*/ {\n+ auto node{find_node(f, \"J\")};\n+ BOOST_CHECK(*node == \"J\");\n+ auto erased_result = f.erase(node);\n+ std::string result{to_string(preorder_range(f))};\n+ BOOST_CHECK(result == \"ABCFGHDIKE\");\n+ BOOST_CHECK(*erased_result == \"K\");\n+ }\n+\n+ /*multiple nodes*/ {\n+ auto node{find_node(f, \"D\")};\n+ BOOST_CHECK(*node == \"D\");\n+ auto erased_result = f.erase(leading_of(node), std::next(trailing_of(node)));\n+ std::string result{to_string(preorder_range(f))};\n+ BOOST_CHECK(result == \"ABCFGHE\");\n+ BOOST_CHECK(*erased_result == \"E\");\n+ }\n+}\n+\n+/**************************************************************************************************/\n+\n+BOOST_AUTO_TEST_CASE(construction) {\n+ auto f{big_test_forest()};\n+\n+ /* copy construction */ {\n+ auto f2 = f;\n+ BOOST_CHECK(f2 == f);\n+ }\n+\n+ /* move construction */ {\n+ auto f_size{f.size()};\n+ auto f2 = std::move(f);\n+ BOOST_CHECK(f2 != f);\n+ BOOST_CHECK(f2.size() == f_size);\n+ }\n+}\n+\n+/**************************************************************************************************/\n+\n+BOOST_AUTO_TEST_CASE(assignment) {\n+ auto f{big_test_forest()};\n+\n+ /* copy assignment */ {\n+ decltype(f) f2;\n+ BOOST_CHECK(f2.empty());\n+ f2 = f;\n+ BOOST_CHECK(f2 == f);\n+ }\n+\n+ /* move assignment */ {\n+ auto f_size{f.size()};\n+ decltype(f) f2;\n+ f2 = std::move(f);\n+ BOOST_CHECK(f2 != f);\n+ BOOST_CHECK(f2.size() == f_size);\n+ }\n+\n+ /* self-move assignment */ {\n+ auto f{big_test_forest()};\n+ auto* pf{&f}; // We use a pointer here to get around a clang error when moving to self.\n+ auto f_size{f.size()};\n+ f = std::move(*pf);\n+ BOOST_CHECK(f.size() == f_size);\n+ }\n+}\n+\n+/**************************************************************************************************/\n+\n+BOOST_AUTO_TEST_CASE(swap) {\n+ auto f1{big_test_forest()};\n+ auto f2{f1};\n+ f2.pop_back();\n+ f2.pop_front();\n+ auto f1_sz{f1.size()};\n+ auto f2_sz{f2.size()};\n+\n+ BOOST_CHECK(f1_sz != f2_sz);\n+ BOOST_CHECK(f1 != f2);\n+\n+ std::swap(f1, f2);\n+\n+ BOOST_CHECK(f2.size() == f1_sz);\n+ BOOST_CHECK(f1.size() == f2_sz);\n+\n+ f1.swap(f2);\n+\n+ BOOST_CHECK(f1.size() == f1_sz);\n+ BOOST_CHECK(f2.size() == f2_sz);\n+}\n+\n+/**************************************************************************************************/\n+\n+BOOST_AUTO_TEST_CASE(test_equal_shape) {\n+ auto f1{big_test_forest()};\n+ auto f2{f1};\n+ \n+ for (auto& x : preorder_range(f2)) {\n+ x = \"X\";\n+ }\n+\n+ BOOST_CHECK(f1 != f2);\n+ BOOST_CHECK(forests::equal_shape(f1, f2));\n+ BOOST_CHECK(to_string(f2) == \"XXXXXXXXXXXXXXXXXXXXXX\");\n+}\n+\n+/**************************************************************************************************/\n+\n+BOOST_AUTO_TEST_CASE(test_transcribe_forest) {\n+ auto f1{big_test_forest()};\n+ stlab::forest f2;\n+\n+ forests::transcribe(f1, forests::transcriber(f2), [](const std::string& x){\n+ assert(!x.empty());\n+ return static_cast(x.front());\n+ });\n+\n+ BOOST_CHECK(forests::equal_shape(f1, f2));\n+ BOOST_CHECK(to_string(f2) == \"65666770707171727267687373747475756869696665\");\n+}\n+\n+/**************************************************************************************************/\n+\n+BOOST_AUTO_TEST_CASE(test_flatten) {\n+ auto f1{big_test_forest()};\n+ std::vector> flat;\n+\n+ forests::flatten(f1.begin(), f1.end(), std::back_inserter(flat));\n+\n+ BOOST_CHECK(to_string(flat) == \"ABCF?G?H??DI?J?K??E???\");\n+\n+ decltype(f1) f2;\n+\n+ forests::unflatten(flat.begin(), flat.end(), f2);\n+\n+ BOOST_CHECK(f1 == f2);\n+}\n+\n+/**************************************************************************************************/"},{"sha":"f3970c478d520200d18acac21464a08766c700e0","filename":"test/future_when_all_range_tests.cpp","status":"modified","additions":32,"deletions":0,"changes":32,"blob_url":"https://github.com/stlab/stlab/blob/e91c2205c8c73143b0eb4b472424ea2f4feff3ec/test%2Ffuture_when_all_range_tests.cpp","raw_url":"https://github.com/stlab/stlab/raw/e91c2205c8c73143b0eb4b472424ea2f4feff3ec/test%2Ffuture_when_all_range_tests.cpp","contents_url":"https://api.github.com/repos/stlab/stlab/contents/test%2Ffuture_when_all_range_tests.cpp?ref=e91c2205c8c73143b0eb4b472424ea2f4feff3ec","patch":"@@ -11,6 +11,7 @@\n \n #include \n #include \n+#include \n #include \n #include \n \n@@ -73,6 +74,37 @@ BOOST_AUTO_TEST_CASE(future_when_all_void_range_with_one_element) {\n BOOST_REQUIRE_LE(1, custom_scheduler<1>::usage_counter());\n }\n \n+BOOST_AUTO_TEST_CASE(future_when_all_void_range_with_all_delayed) {\n+ using namespace std::chrono_literals;\n+\n+ stlab::serial_queue_t seriel_queue_1 {stlab::default_executor};\n+ stlab::serial_queue_t seriel_queue_2 {stlab::default_executor};\n+ stlab::serial_queue_t seriel_queue_3 {stlab::default_executor};\n+\n+ std::vector> test_futures;\n+ test_futures.emplace_back(\n+ stlab::async(seriel_queue_1.executor(), []{\n+ std::this_thread::sleep_for(0.1s);})\n+ );\n+\n+ test_futures.emplace_back(\n+ stlab::async(seriel_queue_2.executor(), []{\n+ std::this_thread::sleep_for(0.1s);})\n+ );\n+\n+ test_futures.emplace_back(\n+ stlab::async(seriel_queue_3.executor(), []{\n+ std::this_thread::sleep_for(0.1s);})\n+ );\n+ bool done{false};\n+ auto done_future = stlab::when_all(stlab::default_executor, [&done] { done = true;},\n+ std::make_pair(test_futures.begin(), test_futures.end()));\n+\n+ stlab::blocking_get(done_future);\n+\n+ BOOST_REQUIRE(done);\n+}\n+\n BOOST_AUTO_TEST_CASE(future_when_all_void_range_with_many_elements) {\n BOOST_TEST_MESSAGE(\"running future when_all void with range with many elements\");\n size_t p = 0;"},{"sha":"484770d689fed5fb03cccfd04d4c2c0c39d9a830","filename":"test/future_when_any_range_tests.cpp","status":"modified","additions":20,"deletions":0,"changes":20,"blob_url":"https://github.com/stlab/stlab/blob/e91c2205c8c73143b0eb4b472424ea2f4feff3ec/test%2Ffuture_when_any_range_tests.cpp","raw_url":"https://github.com/stlab/stlab/raw/e91c2205c8c73143b0eb4b472424ea2f4feff3ec/test%2Ffuture_when_any_range_tests.cpp","contents_url":"https://api.github.com/repos/stlab/stlab/contents/test%2Ffuture_when_any_range_tests.cpp?ref=e91c2205c8c73143b0eb4b472424ea2f4feff3ec","patch":"@@ -282,6 +282,26 @@ BOOST_AUTO_TEST_CASE(\n BOOST_REQUIRE_LE(1, custom_scheduler<1>::usage_counter());\n }\n \n+BOOST_AUTO_TEST_CASE(future_when_any_void_all_are_ready_at_the_beginning) {\n+ BOOST_TEST_MESSAGE(\"running future when_any void when all futures are ready from the start\");\n+\n+ std::vector> tasks{\n+ stlab::make_ready_future(stlab::default_executor),\n+ stlab::make_ready_future(stlab::default_executor),\n+ };\n+\n+ bool check{false};\n+\n+ sut = stlab::when_any(\n+ stlab::default_executor, [&check](auto) { check = true; },\n+ std::make_pair(std::begin(tasks), std::end(tasks)));\n+\n+ check_valid_future(sut);\n+ wait_until_future_completed(sut);\n+ BOOST_REQUIRE(check);\n+}\n+\n+\n BOOST_AUTO_TEST_CASE(future_when_any_int_void_range_with_many_elements_all_fails) {\n BOOST_TEST_MESSAGE(\"running future when_any int void with range all fails\");\n std::atomic_size_t failures{0};"},{"sha":"b65e158f0bac1998570ac1964e1f370b4cf3d8dd","filename":"test/sanitizer_suppressions","status":"modified","additions":0,"deletions":3,"changes":3,"blob_url":"https://github.com/stlab/stlab/blob/e91c2205c8c73143b0eb4b472424ea2f4feff3ec/test%2Fsanitizer_suppressions","raw_url":"https://github.com/stlab/stlab/raw/e91c2205c8c73143b0eb4b472424ea2f4feff3ec/test%2Fsanitizer_suppressions","contents_url":"https://api.github.com/repos/stlab/stlab/contents/test%2Fsanitizer_suppressions?ref=e91c2205c8c73143b0eb4b472424ea2f4feff3ec","patch":"@@ -1,5 +1,2 @@\n-race:stlab::v1::detail::attach_tasks\n-\n-race:stlab::v1::detail::when_all_shared\n \n race:stlab::v1::blocking_get"}]}