text:
// MIT License
//
// Copyright (c) 2018 degski
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in all
// copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
// SOFTWARE.

#pragma once

#include <iostream>
#include <mutex> // For std::lock_guard < >...

#include <boost/serialization/strong_typedef.hpp>
#include <boost/container/deque.hpp>

#define MSC_CLANG 1
#include <tbb/concurrent_vector.h>
#undef MSC_CLANG

#include <srwlock.hpp>
#include <integer_utils.hpp>

#define VERSION_11

#pragma warning ( push )
#pragma warning ( disable: 4244 )

// Root: The top node in a tree.
// Parent The converse notion of child.
// Siblings Nodes with the same parent.
// Descendant a node reachable by repeated proceeding from parent to child.
// Ancestor a node reachable by repeated proceeding from child to parent.
// Leaf a node with no children.
// Internal node a node with at least one child.
// External node a node with no children.
// Degree number of sub trees of a node.
// Edge connection between one node to another.
// Path a sequence of m_nodes and edges connecting a node with a descendant.
// Level The level of a node is defined by 1 + the number of connections between
//	the node and the root.
// Height of tree The height of a tree is the number of edges on the longest
//	downward path between the root and a leaf.
// Height of node The height of a node is the number of edges on the longest
//	downward path between that node and a leaf.
// Depth The depth of a node is the number of edges from the node to the tree's
//	root node.
// Forest A forest is a set of n = 0 disjoint trees.

namespace rt { // Rooted Tree namespace...

	typedef int32_t index_t;

	template < typename T, size_t Size = jimi::nextPowerOfTwo ( sizeof ( T ) ) - sizeof ( T ) >
	struct PaddedType : public T {

		template < typename ... Args > PaddedType ( Args && ... args_ ) : T ( std::forward < Args > ( args_ ) ... ) { }
		template < typename ... Args > PaddedType ( const bool b_, Args && ... args_ ) : T ( b_, std::forward < Args > ( args_ ) ... ) { }

	private:

		char padding_ [ Size ];
	};

	template < typename T >
	struct PaddedType < T, 0 > : public T { // No padding...

		template < typename ... Args > PaddedType ( Args && ... args_ ) : T ( std::forward < Args > ( args_ ) ... ) { }
		template < typename ... Args > PaddedType ( const bool b_, Args && ... args_ ) : T ( b_, std::forward < Args > ( args_ ) ... ) { }
	};

	typedef SRWLock < false > Lock;
	typedef std::lock_guard < Lock > ScopedLock;
	typedef struct nulldata { } nulldata_t;

	template < typename T >
	struct LockAndDataType : public Lock, public T {

		template < typename ... Args > explicit LockAndDataType ( const bool must_lock_, Args && ... args_ ) noexcept : T ( std::forward < Args > ( args_ ) ... ) { if ( must_lock_ ) { lock ( ); } }
	};

	template<>
	struct LockAndDataType < nulldata_t > : public Lock {

		explicit LockAndDataType ( const bool must_lock_ ) noexcept { if ( must_lock_ ) { lock ( ); } }
	};

	template < typename Graph >
	struct Link;

	template < typename ArcDataType, typename NodeDataType >
	class Tree {

	public:

		typedef Link < Tree > Link;

		BOOST_STRONG_TYPEDEF ( index_t, Arc )
		BOOST_STRONG_TYPEDEF ( index_t, Node )

	private:

		template < typename  T >
		class UnpaddedArcType {

			friend class Tree < ArcDataType, NodeDataType >;

			Node source, target;
			Arc next_in, next_out;

		protected:

			T data;

		public:

			template < typename ... Args >
			UnpaddedArcType ( const bool b_, Args && ... args_ ) noexcept : next_in ( Tree::invalid_arc ), next_out ( Tree::invalid_arc ), data ( b_, std::forward < Args > ( args_ ) ... ) { }

			template < typename ... Args >
			UnpaddedArcType ( const bool b_, const Node s_, const Node t_, Args && ... args_ ) noexcept : source ( s_ ), target ( t_ ), next_in ( Tree::invalid_arc ), next_out ( Tree::invalid_arc ), data ( b_, std::forward < Args > ( args_ ) ... ) { }

			void setSourceTarget ( const Node s_, const Node t_ ) noexcept { source = s_; target = t_; } // Must be locked.
		};

		template < typename T >
		class UnpaddedNodeType {

			friend class Tree < ArcDataType, NodeDataType >;

			Arc head_in, tail_in, head_out, tail_out;

		protected:

			T data;

		public:

			template < typename ... Args >
			UnpaddedNodeType ( const bool b_, Args && ... args_ ) noexcept : head_in ( Tree::invalid_arc ), tail_in ( head_in ), head_out ( Tree::invalid_arc ), tail_out ( head_out ), data ( b_, args_ ... ) { }

			template < typename ... Args >
			UnpaddedNodeType ( const bool b_, const Arc a_, Args && ... args_ ) noexcept : head_in ( a_ ), tail_in ( head_in ), head_out ( Tree::invalid_arc ), tail_out ( head_out ), data ( b_, args_ ... ) { }
		};

		// The main data containers...

		typedef PaddedType < UnpaddedArcType < LockAndDataType < ArcDataType > > >  ArcType;
		typedef PaddedType < UnpaddedNodeType < LockAndDataType < NodeDataType > > > NodeType;

		tbb::concurrent_vector <  ArcType >  m_arcs;
		tbb::concurrent_vector < NodeType > m_nodes;

	public:

		enum class ItType : index_t { in = 1, out = 2 };
		enum class LockType : index_t { read = 3, write = 4 };

		Arc   root_arc;
		Node root_node;

		static const Arc   invalid_arc;
		static const Node invalid_node;

		// Construct...

		Tree ( const size_t a_size_ = 128, const size_t n_size_ = 128 ) : root_arc ( 0 ), root_node ( 0 ) {

			m_arcs.reserve ( a_size_ ); m_nodes.reserve ( n_size_ );

			m_nodes.emplace_back ( false, static_cast < Arc > ( m_arcs.emplace_back ( false, invalid_node, root_node ) - m_arcs.begin ( ) ) );
		}

		void setRoot ( const Node n_ ) {

			root_node = n_;

			m_arcs [ root_arc ].setSourceTarget ( invalid_node, root_node );
		}

		void resetRoot ( ) {

			root_node = 0;

			m_arcs [ root_arc ].setSourceTarget ( invalid_node, root_node );
		}

	private:

		// Maps...

		template < typename T >
		class NodeMap {

			std::vector < T > m_map;

		public:

			NodeMap ( Tree & g_, const T & v_ = T ( ) ) : m_map ( g_.nodeNum ( ), v_ ) { }

			auto begin ( ) -> decltype ( m_map.begin ( ) ) const { return m_map.begin ( ); }
			auto end ( ) -> decltype ( m_map.end ( ) ) const { return m_map.end ( ); }

			T const & operator [ ] ( const Node i_ ) const noexcept { return m_map [ i_ ]; }
			T & operator [ ] ( const Node i_ ) noexcept { return m_map [ i_ ]; }
		};

		template < typename T >
		class ArcMap {

			std::vector < T > m_map;

		public:

			ArcMap ( Tree & g_, const T & v_ = T ( ) ) : m_map ( g_.arcNum ( ), v_ ) { }

			auto begin ( ) -> decltype ( m_map.begin ( ) ) const { return m_map.begin ( ); }
			auto end ( ) -> decltype ( m_map.end ( ) ) const { return m_map.end ( ); }

			T const & operator [ ] ( const Arc i_ ) const noexcept { return m_map [ i_ ]; }
			T & operator [ ] ( const Arc i_ ) noexcept { return m_map [ i_ ]; }
		};

	public:

		// Adding...

		Link addArc ( const Node s_, const Node t_ ) { // Add arc between existing m_nodes...

			const Link l ( static_cast < Arc > ( m_arcs.emplace_back ( false, s_, t_ ) - m_arcs.begin ( ) ), t_ );

			{
				ScopedLock node_lock ( m_nodes [ t_ ].data );
				ScopedLock arc_lock ( m_arcs [ m_nodes [ t_ ].tail_in ].data );

				m_nodes [ t_ ].tail_in = m_arcs [ m_nodes [ t_ ].tail_in ].next_in = l.arc;
			}

			{
				ScopedLock node_lock ( m_nodes [ s_ ].data );

				if ( m_nodes [ s_ ].head_out == invalid_arc ) {

					m_nodes [ s_ ].head_out = m_nodes [ s_ ].tail_out = l.arc;
				}

				else {

					ScopedLock arc_lock ( m_arcs [ m_nodes [ s_ ].tail_out ].data );

					m_nodes [ s_ ].tail_out = m_arcs [ m_nodes [ s_ ].tail_out ].next_out = l.arc;
				}
			}

			return l;
		}

		Link addArcUnsafe ( const Node s_, const Node t_ ) { // Add arc between existing m_nodes...

			// Non-locking addArc...

			const Link l ( static_cast < Arc > ( m_arcs.emplace_back ( false, s_, t_ ) - m_arcs.begin ( ) ), t_ );

			m_nodes [ t_ ].tail_in = m_arcs [ m_nodes [ t_ ].tail_in ].next_in = l.arc;

			if ( m_nodes [ s_ ].head_out == invalid_arc ) {

				m_nodes [ s_ ].head_out = m_nodes [ s_ ].tail_out = l.arc;
			}

			else {

				m_nodes [ s_ ].tail_out = m_arcs [ m_nodes [ s_ ].tail_out ].next_out = l.arc;
			}

			return l;
		}

	private:

		template < typename T >
		std::string inv ( const T t_ ) const {

			if ( t_ == invalid_arc ) {

				return std::string ( "invalid_arc" );
			}

			else if ( t_ == invalid_node ) {

				return std::string ( "invalid_node" );
			}

			else {

				char buf [ 64 ] = { };

				_itoa_s ( static_cast < index_t > ( t_ ), buf, 64, 10 );

				return std::string ( buf );
			}
		}

	public:

		void printArc ( const Arc a_ ) {

			std::cout << "Arc      " << inv ( a_ ) << std::endl;

			std::cout << "Source   " << inv ( m_arcs [ a_ ].source ) << std::endl;
			std::cout << "Next out " << inv ( m_arcs [ a_ ].next_out ) << std::endl;

			std::cout << "Target   " << inv ( m_arcs [ a_ ].target ) << std::endl;
			std::cout << "Next in  " << inv ( m_arcs [ a_ ].next_in ) << std::endl;

			std::cout << std::endl;

		}

		void printNode ( const Node n_ ) {

			std::cout << "Node     " << inv ( n_ ) << std::endl;

			std::cout << "Head in  " << inv ( m_nodes [ n_ ].head_in ) << std::endl;
			std::cout << "Tail in  " << inv ( m_nodes [ n_ ].tail_in ) << std::endl;

			std::cout << "Head out " << inv ( m_nodes [ n_ ].head_out ) << std::endl;
			std::cout << "Tail out " << inv ( m_nodes [ n_ ].tail_out ) << std::endl;

			std::cout << std::endl;
		}

		Link addNode ( const Node s_ ) { // Add node and incident arc...

			const Arc  a ( static_cast < Arc > ( m_arcs.emplace_back ( true ) - m_arcs.begin ( ) ) ); // Locked arc...
			const Node t ( static_cast < Node > ( m_nodes.emplace_back ( false, a ) - m_nodes.begin ( ) ) );

			m_arcs [ a ].setSourceTarget ( s_, t );
			m_arcs [ a ].data.unlock ( );

			ScopedLock node_lock ( m_nodes [ s_ ].data );

			if ( m_nodes [ s_ ].head_out == invalid_arc ) {

				m_nodes [ s_ ].tail_out = m_nodes [ s_ ].head_out = a;
			}

			else {

				Arc & ref = m_nodes [ s_ ].tail_out;

				ScopedLock arc_lock ( m_arcs [ ref ].data );

				ref = m_arcs [ ref ].next_out = a;
			}

			return Link ( a, t );
		}

		Link addNodeUnsafe ( const Node s_ ) { // Add node and incident arc...

			// Non-locking addNode...

			const  Arc a ( static_cast < Arc > ( m_arcs.emplace_back ( false ) - m_arcs.begin ( ) ) );
			const Node t ( static_cast < Node > ( m_nodes.emplace_back ( false, a ) - m_nodes.begin ( ) ) );

			m_arcs [ a ].setSourceTarget ( s_, t );

			if ( m_nodes [ s_ ].head_out == invalid_arc ) {

				m_nodes [ s_ ].tail_out = m_nodes [ s_ ].head_out = a;
			}

			else {

				m_nodes [ s_ ].tail_out = m_arcs [ m_nodes [ s_ ].tail_out ].next_out = a;
			}

			return Link ( a, t );
		}

		// Iterating...

	private:

		template < ItType I, LockType L >
		class ArcItBase {

		protected:

			Tree & g;
			Arc arc;

			ArcItBase ( Tree & g_, const Node n_ ) noexcept : g ( g_ ), arc ( I == ItType::in ? g.m_nodes [ n_ ].head_in : g.m_nodes [ n_ ].head_out ) { }
			virtual ~ArcItBase ( ) { } // Base class must have virtual destructor...

			Arc getNext ( const Arc a_ ) const noexcept { return I == ItType::in ? g.m_arcs [ a_ ].next_in : g.m_arcs [ a_ ].next_out; }
			Arc getNext ( ) const noexcept { return I == ItType::in ? g.m_arcs [ arc ].next_in : g.m_arcs [ arc ].next_out; }

			void lock ( const Arc a_ ) const noexcept { L == LockType::write ? g.m_arcs [ a_ ].data.lock ( ) : g.m_arcs [ a_ ].data.lockRead ( ); }
			void lock ( ) const noexcept { L == LockType::write ? g.m_arcs [ arc ].data.lock ( ) : g.m_arcs [ arc ].data.lockRead ( ); }

			bool tryLock ( const Arc a_ ) const noexcept { return L == LockType::write ? g.m_arcs [ a_ ].data.tryLock ( ) : g.m_arcs [ a_ ].data.tryLockRead ( ); }
			bool tryLock ( ) const noexcept { return L == LockType::write ? g.m_arcs [ arc ].data.tryLock ( ) : g.m_arcs [ arc ].data.tryLockRead ( ); }

			void unlock ( const Arc a_ ) const noexcept { L == LockType::write ? g.m_arcs [ a_ ].data.unlock ( ) : g.m_arcs [ a_ ].data.unlockRead ( ); }
			void unlock ( ) const noexcept { L == LockType::write ? g.m_arcs [ arc ].data.unlock ( ) : g.m_arcs [ arc ].data.unlockRead ( ); }

			bool valid ( const Arc a_ ) const noexcept { return a_ != g.invalid_arc; }
			bool valid ( ) const noexcept { return arc != g.invalid_arc; }

			bool invalid ( const Arc a_ ) const noexcept { return a_ == g.invalid_arc; }
			bool invalid ( ) const noexcept { return arc == g.invalid_arc; }

		public:

			Arc get ( ) const noexcept { return arc; }

			const bool operator != ( const Arc rhs_ ) const noexcept { return arc != rhs_; }
			const bool operator == ( const Arc rhs_ ) const noexcept { return arc == rhs_; }

			ArcDataType const & operator * ( ) const noexcept { return g.m_arcs [ arc ].data; }
			ArcDataType & operator * ( ) noexcept { return g.m_arcs [ arc ].data; }

			ArcDataType const * operator -> ( ) const noexcept { return &g.m_arcs [ arc ].data; }
			ArcDataType * operator -> ( ) noexcept { return &g.m_arcs [ arc ].data; }

			static const Arc end ( ) noexcept { return Tree::invalid_arc; }
		};

	public:

		template < ItType I, LockType L >
		class QueingArcIt_ : public ArcItBase < I, L > {

			boost::container::deque < Arc > m_queue;
			bool m_not_all_touched = true;

		public:

			QueingArcIt_ ( Tree & g_, const Node n_ ) noexcept : ArcItBase < I, L > ( g_, n_ ) {

				m_queue.push_back ( g_.invalid_arc );

				if ( ArcItBase < I, L >::valid ( ) ) {

					ArcItBase < I, L >::lock ( );
				}
			}

			Arc queuePop ( ) noexcept { const Arc a = m_queue.front ( ); m_queue.pop_front ( ); return a; }

			QueingArcIt_ & operator ++ ( ) noexcept {

				Arc next = ArcItBase < I, L >::getNext ( );

				ArcItBase < I, L >::unlock ( );

				while ( ArcItBase < I, L >::valid ( next ) ) {

					if ( ArcItBase < I, L >::tryLock ( next ) ) {

						break;
					}

					else {

						m_queue.push_back ( next );

						if ( m_not_all_touched ) {

							next = ArcItBase < I, L >::getNext ( next );

							if ( ArcItBase < I, L >::invalid ( next ) ) {

								m_not_all_touched = false;

								next = queuePop ( );
							}
						}

						else {

							next = queuePop ( );
						}
					}
				}

				ArcItBase < I, L >::arc = next;

				return * this;
			}

			// auto operator ++ ( index_t ) -> decltype ( * this ) = delete;
		};

		template < ItType I, LockType L >
		class ArcIt_ : public ArcItBase < I, L > {

		public:

			ArcIt_ ( Tree & g_, const Node n_ ) : ArcItBase < I, L > ( g_, n_ ) {

				if ( ArcItBase < I, L >::valid ( ) ) {

					ArcItBase < I, L >::lock ( );
				}
			}

			ArcIt_ & operator ++ ( ) noexcept {

				const Arc next = ArcItBase < I, L >::getNext ( );

				ArcItBase < I, L >::unlock ( );

				if ( ArcItBase < I, L >::valid ( next ) ) {

					ArcItBase < I, L >::lock ( next );
				}

				ArcItBase < I, L >::arc = next;

				return * this;
			}

			// auto operator ++ ( index_t ) -> decltype ( * this ) = delete;
		};

		class InIt {

			const Tree & g;
			Arc arc;

		public:

			InIt ( const Tree & g_, const Node n_ ) noexcept : g ( g_ ), arc ( g.m_nodes [ n_ ].head_in ) { }

			InIt & operator ++ ( ) noexcept {

				arc = g.m_arcs [ arc ].next_in;

				return * this;
			}

			// auto operator ++ ( index_t ) -> decltype ( * this ) = delete;
			const bool operator != ( const Arc rhs_ ) const noexcept { return arc != rhs_; }

			Arc get ( ) const noexcept { return arc; }
			static const Arc end ( ) noexcept { return Tree::invalid_arc; }
		};

		class OutIt {

			const Tree & g;
			Arc arc;

		public:

			OutIt ( const Tree &g_, const Node n_ ) noexcept : g ( g_ ), arc ( g.m_nodes [ n_ ].head_out ) { }

			OutIt & operator ++ ( ) noexcept {

				arc = g.m_arcs [ arc ].next_out;

				return * this;
			}

			// auto operator ++ ( index_t ) -> decltype ( * this ) = delete;
			const bool operator != ( const Arc rhs_ ) const noexcept { return arc != rhs_; }

			Arc get ( ) const noexcept { return arc; }
			static const Arc end ( ) noexcept { return Tree::invalid_arc; }
		};

		typedef QueingArcIt_ < ItType::in, LockType::write > QWrInIt;
		typedef QueingArcIt_ < ItType::out, LockType::write > QWrOutIt;
		typedef QueingArcIt_ < ItType::in, LockType::read > QRdInIt;
		typedef QueingArcIt_ < ItType::out, LockType::read > QRdOutIt;

		typedef ArcIt_ < ItType::in, LockType::write > WrInIt;
		typedef ArcIt_ < ItType::out, LockType::write > WrOutIt;
		typedef ArcIt_ < ItType::in, LockType::read > RdInIt;
		typedef ArcIt_ < ItType::out, LockType::read > RdOutIt;

		class ArcIt {

			Tree & g;
			Arc a;

		public:

			ArcIt ( Tree & g_ ) noexcept : g ( g_ ), a ( g.root_arc ) { }

			ArcIt & operator ++ ( ) noexcept { ++a; return * this; }
			// auto operator ++ ( index_t ) -> decltype ( * this ) = delete;

			const bool operator == ( const Arc rhs_ ) const noexcept { return a == rhs_; }
			const bool operator != ( const Arc rhs_ ) const noexcept { return a != rhs_; }

			Arc const operator * ( ) const noexcept { return a; }
			Arc operator * ( ) noexcept { return a; }

			Arc begin ( ) noexcept { return g.root_arc; }
			Arc end ( ) noexcept { return static_cast < Arc > ( g.m_arcs.end ( ) - g.m_arcs.begin ( ) ); }
		};

		class NodeIt {

			Tree & g;
			Node n;

		public:

			NodeIt ( Tree & g_ ) noexcept : g ( g_ ), n ( g.root_node ) { }

			NodeIt & operator ++ ( ) noexcept { ++n; return * this; }
			// auto operator ++ ( index_t ) -> decltype ( * this ) = delete;

			const bool operator == ( const Node rhs_ ) const noexcept { return n == rhs_; }
			const bool operator != ( const Node rhs_ ) const noexcept { return n != rhs_; }

			Node const operator * ( ) const noexcept { return n; }
			Node operator * ( ) noexcept { return n; }

			Node begin ( ) noexcept { return g.root_node; }
			Node end ( ) noexcept { return static_cast < Node > ( g.m_nodes.end ( ) - g.m_nodes.begin ( ) ); }
		};

		// Data access...

		ArcDataType const & operator [ ] ( const Arc i_ ) const noexcept { return m_arcs [ i_ ].data; }
		ArcDataType & operator [ ] ( const Arc i_ ) noexcept { return m_arcs [ i_ ].data; }

		template < typename It > ArcDataType const & operator [ ] ( const It & it_ ) const noexcept { return m_arcs [ it_.get ( ) ].data; }
		template < typename It > ArcDataType & operator [ ] ( const It & it_ ) noexcept { return m_arcs [ it_.get ( ) ].data; }

		NodeDataType const & operator [ ] ( const Node i_ ) const noexcept { return m_nodes [ i_ ].data; }
		NodeDataType & operator [ ] ( const Node i_ ) noexcept { return m_nodes [ i_ ].data; }

		template < typename It > ArcType const & operator ->* ( const It & it_ ) const noexcept { return m_arcs [ it_.get ( ) ]; }
		template < typename It > ArcType & operator ->* ( const It & it_ ) noexcept { return m_arcs [ it_.get ( ) ]; }

		// Connectivity...

		Node source ( const Arc a_ ) const noexcept { return m_arcs [ a_ ].source; }
		Node target ( const Arc a_ ) const noexcept { return m_arcs [ a_ ].target; }

		template < typename It > Node source ( const It & it_ ) const noexcept { return m_arcs [ it_.get ( ) ].source; }
		template < typename It > Node target ( const It & it_ ) const noexcept { return m_arcs [ it_.get ( ) ].target; }

		Link link ( const Arc a_ ) const noexcept { return Link ( a_, m_arcs [ a_ ].target ); }
		template < typename It > Link link ( const It & it_ ) const noexcept { return Link ( it_.get ( ), m_arcs [ it_.get ( ) ].target ); }

		bool isLeaf ( const Node n_ ) const noexcept { return m_nodes [ n_ ].head_out == invalid_arc; }
		bool isInternal ( const Node n_ ) const noexcept { return not ( isLeaf ( n_ ) ); }

		bool valid ( const Arc a_ ) const noexcept { return a_ != invalid_arc; }
		bool invalid ( const Arc a_ ) const noexcept { return a_ == invalid_arc; }

		bool valid ( const Node n_ ) const noexcept { return n_ != invalid_node; }
		bool invalid ( const Node n_ ) const noexcept { return n_ == invalid_node; }

		template < typename It > bool valid ( const It & it_ ) const noexcept { return it_.get ( ) != invalid_arc; }
		template < typename It > bool invalid ( const It & it_ ) const noexcept { return it_.get ( ) == invalid_arc; }

		// Locking...

		void lock ( const Arc a_ ) noexcept { m_arcs [ a_ ].data.lock ( ); }
		bool tryLock ( const Arc a_ ) noexcept { return m_arcs [ a_ ].data.tryLock ( ); }
		void unlock ( const Arc a_ ) noexcept { m_arcs [ a_ ].data.unlock ( ); }

		void lockRead ( const Arc a_ ) noexcept { m_arcs [ a_ ].data.lockRead ( ); }
		bool tryLockRead ( const Arc a_ ) noexcept { return m_arcs [ a_ ].data.tryLockRead ( ); }
		void unLockRead ( const Arc a_ ) noexcept { m_arcs [ a_ ].data.unlockRead ( ); }

		template < typename It > void lock ( const It & it_ ) noexcept { m_arcs [ it_.get ( ) ].data.lock ( ); }
		template < typename It > bool tryLock ( const It & it_ ) noexcept { return m_arcs [ it_.get ( ) ].data.tryLock ( ); }
		template < typename It > void unlock ( const It & it_ ) noexcept { m_arcs [ it_.get ( ) ].data.unlock ( ); }

		template < typename It > void lockRead ( const It & it_ ) noexcept { m_arcs [ it_.get ( ) ].data.lockRead ( ); }
		template < typename It > bool tryLockRead ( const It & it_ ) noexcept { return m_arcs [ it_.get ( ) ].data.tryLockRead ( ); }
		template < typename It > void unLockRead ( const It & it_ ) noexcept { m_arcs [ it_.get ( ) ].data.unlockRead ( ); }

		void lock ( const Node n_ ) noexcept { m_nodes [ n_ ].data.lock ( ); }
		bool tryLock ( const Node n_ ) noexcept { return m_nodes [ n_ ].data.tryLock ( ); }
		void unlock ( const Node n_ ) noexcept { m_nodes [ n_ ].data.unlock ( ); }

		void lockRead ( const Node n_ ) noexcept { m_nodes [ n_ ].data.lockRead ( ); }
		bool tryLockRead ( const Node n_ ) noexcept { return m_nodes [ n_ ].data.tryLockRead ( ); }
		void unlockRead ( const Node n_ ) noexcept { m_nodes [ n_ ].data.unlockRead ( ); }

		// Stats...

		size_t nodeNum ( ) const { return m_nodes.size ( ); }
		size_t arcNum ( ) const { return m_arcs.size ( ); }

		// Arcs and Nodes...

		Arc arc ( const Node s_, const Node t_ ) const {

			for ( Arc a = m_nodes [ s_ ].head_out; a != invalid_arc; a = m_arcs [ a ].next_out ) { // Out-iteration...

				if ( m_arcs [ a ].target == t_ ) {

					return a;
				}
			}

			return invalid_arc;
		}

		Node randomNode ( ) const noexcept {

			static jimi::XoRoShiRo128Plus rng;

			return ( Node ) boost::random::uniform_int_distribution < index_t > ( 1, m_nodes.size ( ) - 1 ) ( rng );
		}

		// Slice...

		void sliceDF ( Tree & new_srd_, const Node & old_node_ ) const {

			if ( invalid ( old_node_ ) ) { // New root did not exist...

				return;
			}

			// auto_timer t ( milliseconds );

			// Not thread-safe...

			typedef std::vector < Node > Visited; // New m_nodes by old_index...
			typedef boost::container::deque < Node > Stack;

			Visited visited ( nodeNum ( ), Tree::invalid_node );

			visited [ old_node_ ] = root_node;

			Stack stack;

			stack.emplace_back ( old_node_ );

			new_srd_ [ root_node ] = ( * this ) [ old_node_ ];

			while ( not ( stack.empty ( ) ) ) {

				const Node parent = stack.back ( );

				stack.pop_back ( );

				for ( Arc a = m_nodes [ parent ].head_out; a != invalid_arc; a = m_arcs [ a ].next_out ) {

					const Node child ( target ( a ) );

					if ( visited [ child ] == Tree::invalid_node ) { // Not visited yet...

						const Link link = new_srd_.addNodeUnsafe ( visited [ parent ] );

						visited [ child ] = link.target;
						stack.emplace_back ( child );

						new_srd_ [ link.arc ] = ( * this ) [ a ];
						new_srd_ [ link.target ] = ( * this ) [ child ];
					}

					else {

						new_srd_ [ new_srd_.addArcUnsafe ( visited [ parent ], visited [ child ] ).arc ] = ( * this ) [ a ];
					}
				}
			}
		}

		void sliceBF ( Tree & new_srd_, const Node & old_node_ ) const {

			if ( invalid ( old_node_ ) ) { // New root did not exist...

				return;
			}

			// Not thread-safe...

			typedef std::vector < Node > Visited; // New m_nodes by old_index...
			typedef boost::container::deque < Node > Queue;

			Visited visited ( nodeNum ( ), Tree::invalid_node );

			visited [ old_node_ ] = root_node;

			Queue queue;

			queue.emplace_back ( old_node_ );

			new_srd_ [ root_node ] = ( * this ) [ old_node_ ];

			while ( not ( queue.empty ( ) ) ) {

				const Node parent = queue.front ( );

				queue.pop_front ( );

				for ( Arc a = m_nodes [ parent ].head_out; a != invalid_arc; a = m_arcs [ a ].next_out ) {

					const Node child ( target ( a ) );

					if ( visited [ child ] == Tree::invalid_node ) { // Not visited yet...

						const Link link = new_srd_.addNodeUnsafe ( visited [ parent ] );

						visited [ child ] = link.target;
						queue.emplace_back ( child );

						new_srd_ [ link.arc ] = ( * this ) [ a ];
						new_srd_ [ link.target ] = ( * this ) [ child ];
					}

					else {

						new_srd_ [ new_srd_.addArcUnsafe ( visited [ parent ], visited [ child ] ).arc ] = ( * this ) [ a ];
					}
				}
			}
		}
	};

	template < typename ArcDataType, typename NodeDataType >
	typename Tree < ArcDataType, NodeDataType >::Arc  const  Tree < ArcDataType, NodeDataType >::invalid_arc = static_cast <  Tree<ArcDataType, NodeDataType>::Arc > ( INT_MIN + 0 );
	template < typename ArcDataType, typename NodeDataType >
	typename Tree < ArcDataType, NodeDataType >::Node const Tree < ArcDataType, NodeDataType >::invalid_node = static_cast < Tree<ArcDataType, NodeDataType>::Node > ( INT_MIN + 1 );

	template < typename Graph >
	struct Link {

		typedef typename Graph::Arc   Arc;
		typedef typename Graph::Node Node;

		Arc arc; Node target;

		Link ( ) noexcept { }
		Link ( const Link & l_ ) noexcept : arc ( l_.arc ), target ( l_.target ) { }
		Link ( const Arc a_, const Node t_ ) noexcept : arc ( a_ ), target ( t_ ) { }
		Link ( const Arc a_ ) noexcept : arc ( a_ ) { }
		Link ( const Node t_ ) noexcept : target ( t_ ) { }

		bool operator == ( const Link & rhs_ ) { return arc == rhs_.arc && target == rhs_.target; }
		bool operator != ( const Link & rhs_ ) { return arc != rhs_.arc || target != rhs_.target; }
	};

	template < typename Graph >
	class Path {

		typedef typename Graph::Arc   Arc;
		typedef typename Graph::Node Node;

		typedef Link < Graph > Link;

		boost::container::deque < Link > m_path;

	public:

		Path ( ) : m_path ( ) { }
		Path ( const Link & l_ ) : m_path ( 1, l_ ) { }
		Path ( const Arc a_, const Node t_ ) : m_path ( 1, Link ( a_, t_ ) ) { }

		void push ( const Link & l_ ) noexcept { m_path.emplace_back ( l_ ); }
		void push ( const Arc a_, const Node t_ ) noexcept { m_path.emplace_back ( a_, t_ ); }
		Link pop ( ) noexcept { const Link r = m_path.back ( ); m_path.pop_back ( ); return r; }

		auto back ( ) -> decltype ( m_path.back ( ) ) const { return m_path.back ( ); }
		auto begin ( ) -> decltype ( m_path.begin ( ) ) const { return m_path.begin ( ); }
		auto end ( ) -> decltype ( m_path.end ( ) ) const { return m_path.end ( ); }

		void resize ( const size_t s_ ) noexcept { m_path.resize ( s_ ); }
		void reserve ( const size_t s_ ) noexcept { m_path.reserve ( s_ ); }
	};
}

#pragma warning ( pop )

ext: hpp

max_stars_repo_name: degski/MCTSConnectFour

max_issues_repo_name: degski/MCTSConnectFour

max_forks_repo_name: degski/MCTSConnectFour


text:
//=======================================================================
// Copyright 2002 Indiana University.
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================

#ifndef BOOST_GRAPH_ARCHETYPES_HPP
#define BOOST_GRAPH_ARCHETYPES_HPP

#include <boost/property_map.hpp>
#include <boost/concept_archetype.hpp>

namespace boost { // should use a different namespace for this

  namespace detail {
    struct null_graph_archetype : public null_archetype<> {
      struct traversal_category { };
    };
  }

  //===========================================================================
  template <typename Vertex, typename Directed, typename ParallelCategory,
    typename Base = detail::null_graph_archetype >
  struct incidence_graph_archetype : public Base
  {
    typedef typename Base::traversal_category base_trav_cat;
    struct traversal_category
      : public incidence_graph_tag, public base_trav_cat { };
#if 0
    typedef immutable_graph_tag mutability_category;
#endif
    typedef Vertex vertex_descriptor;
    typedef unsigned int degree_size_type;
    typedef unsigned int vertices_size_type;
    typedef unsigned int edges_size_type;
    struct edge_descriptor {
      edge_descriptor() { }
      edge_descriptor(const detail::dummy_constructor&) { }
      bool operator==(const edge_descriptor&) const { return false; }
      bool operator!=(const edge_descriptor&) const { return false; }
    };
    typedef input_iterator_archetype<edge_descriptor> out_edge_iterator;

    typedef Directed directed_category;
    typedef ParallelCategory edge_parallel_category;

    typedef void adjacency_iterator;
    typedef void in_edge_iterator;
    typedef void vertex_iterator;
    typedef void edge_iterator;
  };
  template <typename V, typename D, typename P, typename B>
  V source(const typename incidence_graph_archetype<V,D,P,B>::edge_descriptor&,
           const incidence_graph_archetype<V,D,P,B>& )
  {
    return V(static_object<detail::dummy_constructor>::get());
  }
  template <typename V, typename D, typename P, typename B>
  V target(const typename incidence_graph_archetype<V,D,P,B>::edge_descriptor&,
           const incidence_graph_archetype<V,D,P,B>& )
  {
    return V(static_object<detail::dummy_constructor>::get());
  }

  template <typename V, typename D, typename P, typename B>
  std::pair<typename incidence_graph_archetype<V,D,P,B>::out_edge_iterator,
            typename incidence_graph_archetype<V,D,P,B>::out_edge_iterator>
  out_edges(const V&, const incidence_graph_archetype<V,D,P,B>& )
  {
    typedef typename incidence_graph_archetype<V,D,P,B>::out_edge_iterator Iter;
    return std::make_pair(Iter(), Iter());
  }

  template <typename V, typename D, typename P, typename B>
  typename incidence_graph_archetype<V,D,P,B>::degree_size_type
  out_degree(const V&, const incidence_graph_archetype<V,D,P,B>& )
  {
    return 0;
  }

  //===========================================================================
  template <typename Vertex, typename Directed, typename ParallelCategory,
    typename Base = detail::null_graph_archetype >
  struct adjacency_graph_archetype : public Base
  {
    typedef typename Base::traversal_category base_trav_cat;
    struct traversal_category
      : public adjacency_graph_tag, public base_trav_cat { };
    typedef Vertex vertex_descriptor;
    typedef unsigned int degree_size_type;
    typedef unsigned int vertices_size_type;
    typedef unsigned int edges_size_type;
    typedef void edge_descriptor;
    typedef input_iterator_archetype<Vertex> adjacency_iterator;

    typedef Directed directed_category;
    typedef ParallelCategory edge_parallel_category;

    typedef void in_edge_iterator;
    typedef void out_edge_iterator;
    typedef void vertex_iterator;
    typedef void edge_iterator;
  };

  template <typename V, typename D, typename P, typename B>
  std::pair<typename adjacency_graph_archetype<V,D,P,B>::adjacency_iterator,
            typename adjacency_graph_archetype<V,D,P,B>::adjacency_iterator>
  adjacent_vertices(const V&, const adjacency_graph_archetype<V,D,P,B>& )
  {
    typedef typename adjacency_graph_archetype<V,D,P,B>::adjacency_iterator Iter;
    return std::make_pair(Iter(), Iter());
  }

  template <typename V, typename D, typename P, typename B>
  typename adjacency_graph_archetype<V,D,P,B>::degree_size_type
  out_degree(const V&, const adjacency_graph_archetype<V,D,P,B>& )
  {
    return 0;
  }

  //===========================================================================
  template <typename Vertex, typename Directed, typename ParallelCategory,
    typename Base = detail::null_graph_archetype >
  struct vertex_list_graph_archetype : public Base
  {
    typedef incidence_graph_archetype<Vertex, Directed, ParallelCategory>
      Incidence;
    typedef adjacency_graph_archetype<Vertex, Directed, ParallelCategory>
      Adjacency;

    typedef typename Base::traversal_category base_trav_cat;
    struct traversal_category
      : public vertex_list_graph_tag, public base_trav_cat { };
#if 0
    typedef immutable_graph_tag mutability_category;
#endif
    typedef Vertex vertex_descriptor;
    typedef unsigned int degree_size_type;
    typedef typename Incidence::edge_descriptor edge_descriptor;
    typedef typename Incidence::out_edge_iterator out_edge_iterator;
    typedef typename Adjacency::adjacency_iterator adjacency_iterator;

    typedef input_iterator_archetype<Vertex> vertex_iterator;
    typedef unsigned int vertices_size_type;
    typedef unsigned int edges_size_type;

    typedef Directed directed_category;
    typedef ParallelCategory edge_parallel_category;

    typedef void in_edge_iterator;
    typedef void edge_iterator;
  };

  template <typename V, typename D, typename P, typename B>
  std::pair<typename vertex_list_graph_archetype<V,D,P,B>::vertex_iterator,
            typename vertex_list_graph_archetype<V,D,P,B>::vertex_iterator>
  vertices(const vertex_list_graph_archetype<V,D,P,B>& )
  {
    typedef typename vertex_list_graph_archetype<V,D,P,B>::vertex_iterator Iter;
    return std::make_pair(Iter(), Iter());
  }

  template <typename V, typename D, typename P, typename B>
  typename vertex_list_graph_archetype<V,D,P,B>::vertices_size_type
  num_vertices(const vertex_list_graph_archetype<V,D,P,B>& )
  {
    return 0;
  }

  // ambiguously inherited from incidence graph and adjacency graph
  template <typename V, typename D, typename P, typename B>
  typename vertex_list_graph_archetype<V,D,P,B>::degree_size_type
  out_degree(const V&, const vertex_list_graph_archetype<V,D,P,B>& )
  {
    return 0;
  }

  //===========================================================================

  struct property_graph_archetype_tag { };

  template <typename GraphArchetype, typename Property, typename ValueArch>
  struct property_graph_archetype : public GraphArchetype
  {
    typedef property_graph_archetype_tag graph_tag;
    typedef ValueArch vertex_property_type;
    typedef ValueArch edge_property_type;
  };

  struct choose_edge_property_map_archetype {
    template <typename Graph, typename Property, typename Tag>
    struct bind_ {
      typedef mutable_lvalue_property_map_archetype
        <typename Graph::edge_descriptor, Property> type;
      typedef lvalue_property_map_archetype
        <typename Graph::edge_descriptor, Property> const_type;
    };
  };
  template <>
  struct edge_property_selector<property_graph_archetype_tag> {
    typedef choose_edge_property_map_archetype type;
  };

  struct choose_vertex_property_map_archetype {
    template <typename Graph, typename Property, typename Tag>
    struct bind_ {
      typedef mutable_lvalue_property_map_archetype
        <typename Graph::vertex_descriptor, Property> type;
      typedef lvalue_property_map_archetype
        <typename Graph::vertex_descriptor, Property> const_type;
    };
  };

  template <>
  struct vertex_property_selector<property_graph_archetype_tag> {
    typedef choose_vertex_property_map_archetype type;
  };

  template <typename G, typename P, typename V>
  typename property_map<property_graph_archetype<G, P, V>, P>::type
  get(P, property_graph_archetype<G, P, V>&) {
    typename property_map<property_graph_archetype<G, P, V>, P>::type pmap;
    return pmap;
  }

  template <typename G, typename P, typename V>
  typename property_map<property_graph_archetype<G, P, V>, P>::const_type
  get(P, const property_graph_archetype<G, P, V>&) {
    typename property_map<property_graph_archetype<G, P, V>, P>::const_type pmap;
    return pmap;
  }

  template <typename G, typename P, typename K, typename V>
  typename property_traits<typename property_map<property_graph_archetype<G, P, V>, P>::const_type>::value_type
  get(P p, const property_graph_archetype<G, P, V>& g, K k) {
    return get( get(p, g), k);
  }

  template <typename G, typename P, typename V, typename Key>
  void
  put(P p, property_graph_archetype<G, P, V>& g,
      const Key& key, const V& value)
  {
    typedef typename boost::property_map<property_graph_archetype<G, P, V>, P>::type Map;
    Map pmap = get(p, g);
    put(pmap, key, value);
  }

  struct color_value_archetype {
    color_value_archetype() { }
    color_value_archetype(detail::dummy_constructor) { }
    bool operator==(const color_value_archetype& ) const { return true; }
    bool operator!=(const color_value_archetype& ) const { return true; }
  };
  template <>
  struct color_traits<color_value_archetype> {
    static color_value_archetype white()
    {
      return color_value_archetype
        (static_object<detail::dummy_constructor>::get());
    }
    static color_value_archetype gray()
    {
      return color_value_archetype
        (static_object<detail::dummy_constructor>::get());
    }
    static color_value_archetype black()
    {
      return color_value_archetype
        (static_object<detail::dummy_constructor>::get());
    }
  };

  template <typename T>
  class buffer_archetype {
  public:
    void push(const T&) {}
    void pop() {}
    T& top() { return static_object<T>::get(); }
    const T& top() const { return static_object<T>::get(); }
    bool empty() const { return true; }
  };

} // namespace boost

#endif // BOOST_GRAPH_ARCHETYPES_HPP

max_stars_repo_name: schinmayee/nimbus


text:
#ifndef _ITERATOR_INCREMENT_HPP_
#define _ITERATOR_INCREMENT_HPP_

#include <boost/iterator/iterator_facade.hpp>
#include <boost/iterator/counting_iterator.hpp>
#include <cassert>

namespace iterator {

    namespace details {

	template<typename T>
	struct increment_cast { typedef T type; };

	template<typename T>
	struct increment_cast<T*> { typedef size_t type; };

    }

    template <typename T>
    class increment_iterator
	: public boost::iterator_facade<increment_iterator<T>,
					const T,
					std::forward_iterator_tag>
    {
    private:
	friend class boost::iterator_core_access;
	typedef typename details::increment_cast<T>::type cast;
	T value, incr;
	void increment() { value += cast(incr); }
	bool equal(const increment_iterator& other) const {
	    //this is probably somewhat problematic, assuming that the "end iterator"
	    //is always the right-hand value?
	    return ((incr >= 0 && value >= other.value) ||
		    (incr < 0 && value <= other.value));
	}
	const T& dereference() const { return value; }
    public:
	increment_iterator(T value, T incr = T(1)): value(value), incr(incr) {}
    };

}

#endif /* _ITERATOR_INCREMENT_HPP_ */


text:
//
// Copyright (C) 2011 Denis V Chapligin
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//

#define BOOST_TEST_MODULE "STLCacheCopy"
#include <boost/test/unit_test.hpp>

#ifndef _MSC_VER
#include <unistd.h>
#define WAIT_A_SECOND sleep(2);
#else
#include <windows.h>
#define WAIT_A_SECOND Sleep(2000);
#endif /* _MSC_VER */

#include <stlcache/stlcache.hpp>

using namespace stlcache;

BOOST_AUTO_TEST_SUITE(STLCacheSuite)

BOOST_AUTO_TEST_CASE(copyNone) {
    cache<int,string,policy_none> c1(3);

    c1.insert(1,"data1");
    c1.insert(2,"data2");

    c1.insert(3,"data3");
    BOOST_CHECK(c1.size()==3);
    BOOST_CHECK(c1.max_size()==3);

    cache<int,string,policy_none> c2(c1);

    c2.insert(4,"data4");
    BOOST_CHECK(c2.size()==3);
    BOOST_CHECK(c2.max_size()==3);

    //We cannot predict which items will be removed, so wedo not check it
}

BOOST_AUTO_TEST_CASE(copyLRU) {
    cache<int,string,policy_lru> c1(3);

    c1.insert(1,"data1");
    c1.insert(2,"data2");

    c1.insert(3,"data3");
    BOOST_CHECK(c1.size()==3);
    BOOST_CHECK(c1.max_size()==3);

    cache<int,string,policy_lru> c2(c1);

    c2.insert(4,"data4");
    BOOST_CHECK(c2.size()==3);
    BOOST_CHECK(c2.max_size()==3);

    BOOST_REQUIRE_THROW(c2.fetch(1),exception_invalid_key); //Must be removed by LRU policy
}

BOOST_AUTO_TEST_CASE(copyMRU) {
    cache<int,string,policy_mru> c1(3);

    c1.insert(1,"data1");
    c1.insert(2,"data2");

    c1.insert(3,"data3");
    BOOST_CHECK(c1.size()==3);
    BOOST_CHECK(c1.max_size()==3);

    cache<int,string,policy_mru> c2(c1);

    c2.insert(4,"data4");
    BOOST_CHECK(c2.size()==3);
    BOOST_CHECK(c2.max_size()==3);

    BOOST_REQUIRE_THROW(c2.fetch(3),exception_invalid_key); //Must be removed by MRU policy
}

BOOST_AUTO_TEST_CASE(copyLFU) {
    cache<int,string,policy_lfu> c1(3);

    c1.insert(1,"data1");
    c1.insert(2,"data2");
    c1.insert(3,"data3");

    cache<int,string,policy_lfu> c2(c1);

    c2.touch(1);
    c2.touch(2);

    c2.insert(4,"data4");

    BOOST_REQUIRE_THROW(c2.fetch(3),exception_invalid_key); //Must be removed by LFU policy (cause 1&2 are touched)
}

BOOST_AUTO_TEST_CASE(copyLFUStar) {
    cache<int,string,policy_lfustar> c1(3);

    c1.insert(1,"data1");
    c1.insert(2,"data2");
    c1.insert(3,"data3");

    c1.touch(1);
    c1.touch(2);

    cache<int,string,policy_lfustar> c2(c1);

    c2.insert(4,"data4");

    BOOST_REQUIRE_THROW(c2.fetch(3),exception_invalid_key); //Must be removed by LFU policy (cause 1&2 are touched)
}

BOOST_AUTO_TEST_CASE(copyLFUAging) {
    cache<int,string,policy_lfuaging<3600> > c1(3);

    c1.insert(1,"data1");
    c1.insert(2,"data2");
    c1.insert(3,"data3");

    cache<int,string,policy_lfuaging<3600> > c2(c1);

    c2.touch(1);
    c2.touch(2);

    c2.insert(4,"data4");

    BOOST_REQUIRE_THROW(c2.fetch(3),exception_invalid_key); //Must be removed by LFU policy (cause 1&2 are touched)
}

BOOST_AUTO_TEST_CASE(copyLFUAgingStar) {
    cache<int,string,policy_lfuagingstar<1> > c1(3);

    c1.insert(1,"data1");
    c1.insert(2,"data2");
    c1.insert(3,"data3");

    c1.touch(1); //For key one refcount is 3 now
    c1.touch(1);
    c1.touch(2); //For key two refcount is 3 now
    c1.touch(2);
    c1.touch(3); //For key three refcount is 2 now

    cache<int,string,policy_lfuagingstar<1> > c2(c1);

    WAIT_A_SECOND;

    c2.insert(4,"data4");

    BOOST_REQUIRE_THROW(c2.fetch(3),exception_invalid_key); //Must be removed by LFU policy (cause every item have been touched and refcount for key 3 is 1)
}

BOOST_AUTO_TEST_CASE(copyAdaptive) {
    cache<int,string,policy_adaptive> c1(3);

    c1.insert(1,"data1");
    c1.insert(2,"data2");
    c1.insert(3,"data3");

    c1.touch(3); //At this stage key4 moved from T1 to T2 and T1 still bigger list and lru entry is key1;

    cache<int,string,policy_adaptive> c2(c1);

    c2.insert(4,"data4");

    BOOST_REQUIRE_THROW(c2.fetch(1),exception_invalid_key);
}

BOOST_AUTO_TEST_SUITE_END();

ext: cpp

max_stars_repo_name: tomwhoiscontrary/stlcache

max_issues_repo_name: tomwhoiscontrary/stlcache

max_forks_repo_name: tomwhoiscontrary/stlcache


text:
// Copyright (c) 2017-2020 The Bitcoin developers
// Distributed under the MIT software license, see the accompanying
// file COPYING or http://www.opensource.org/licenses/mit-license.php.

#include <consensus/consensus.h>
#include <rpc/server.h>

#include <test/setup_common.h>

#include <boost/algorithm/string.hpp>
#include <boost/test/unit_test.hpp>

#include <limits>
#include <string>

extern UniValue CallRPC(std::string strMethod);

BOOST_FIXTURE_TEST_SUITE(excessiveblock_tests, TestingSetup)

BOOST_AUTO_TEST_CASE(excessiveblock_rpc) {
    BOOST_CHECK_NO_THROW(CallRPC("getexcessiveblock"));

    BOOST_CHECK_THROW(CallRPC("setexcessiveblock"), std::runtime_error);
    BOOST_CHECK_THROW(CallRPC("setexcessiveblock not_uint"),
                      std::runtime_error);
    BOOST_CHECK_THROW(CallRPC("setexcessiveblock 1000000 not_uint"),
                      std::runtime_error);
    BOOST_CHECK_THROW(CallRPC("setexcessiveblock 1000000 1"),
                      std::runtime_error);
    BOOST_CHECK_THROW(CallRPC("setexcessiveblock -1"), std::runtime_error);

    BOOST_CHECK_THROW(CallRPC("setexcessiveblock 0"), std::runtime_error);
    BOOST_CHECK_THROW(CallRPC("setexcessiveblock 1"), std::runtime_error);
    BOOST_CHECK_THROW(CallRPC("setexcessiveblock 1000"), std::runtime_error);
    BOOST_CHECK_THROW(CallRPC(std::string("setexcessiveblock ") +
                              std::to_string(ONE_MEGABYTE - 1)),
                      std::runtime_error);
    BOOST_CHECK_THROW(CallRPC(std::string("setexcessiveblock ") +
                              std::to_string(ONE_MEGABYTE)),
                      std::runtime_error);

    BOOST_CHECK_NO_THROW(CallRPC(std::string("setexcessiveblock ") +
                                 std::to_string(ONE_MEGABYTE + 1)));
    BOOST_CHECK_NO_THROW(CallRPC(std::string("setexcessiveblock ") +
                                 std::to_string(ONE_MEGABYTE + 10)));

    // Default can be higher than 1MB in future - test it too
    BOOST_CHECK_NO_THROW(CallRPC(std::string("setexcessiveblock ") +
                                 std::to_string(DEFAULT_MAX_BLOCK_SIZE)));
    BOOST_CHECK_NO_THROW(CallRPC(std::string("setexcessiveblock ") +
                                 std::to_string(DEFAULT_MAX_BLOCK_SIZE * 8)));

    BOOST_CHECK_NO_THROW(
        CallRPC(std::string("setexcessiveblock ") +
                std::to_string(std::numeric_limits<int64_t>::max())));

    BOOST_CHECK_THROW(
        CallRPC(
            std::string("setexcessiveblock ") +
            std::to_string(uint64_t(std::numeric_limits<int64_t>::max()) + 1)),
        std::runtime_error);

    BOOST_CHECK_THROW(
        CallRPC(std::string("setexcessiveblock ") +
                std::to_string(std::numeric_limits<uint64_t>::max())),
        std::runtime_error);
}

BOOST_AUTO_TEST_SUITE_END()

max_stars_repo_name: edggge/bitcoin-abc

max_issues_repo_name: edggge/bitcoin-abc

max_forks_repo_name: edggge/bitcoin-abc


text:
// vim:ts=2:sw=2:expandtab:autoindent:filetype=cpp:

// Copyright (c) 2007 Aristid Breitkreuz, Ruediger Sonderfeld, Christian Uhrhan
//
// Distributed under the Boost Software License, Version 1.0 and under the MIT
// License.
//
// See accompanying LICENSES.txt or
// <http://fragments.sourceforge.net/LICENSES.txt> or, for the Boost Software
// License, <http://www.boost.org/LICENSE_1_0.txt>.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
// SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
// FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
// ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
// DEALINGS IN THE SOFTWARE.

#include <fragments/concepts/resulting_concept.hpp>

#include <boost/preprocessor/stringize.hpp>
#include <boost/mpl/and.hpp>
#include <boost/mpl/size.hpp>
#include <boost/mpl/vector.hpp>
#include <iostream>

template<typename SeqA,
         typename SeqB,
         bool emptyA = boost::mpl::empty<SeqA>::value,
         bool emptyB = boost::mpl::empty<SeqB>::value>
struct equivalent_sequence
  : boost::mpl::and_<
      typename boost::is_same<
        typename boost::mpl::front<SeqA>::type,
        typename boost::mpl::front<SeqB>::type
      >::type,
      typename equivalent_sequence<
        typename boost::mpl::pop_front<SeqA>::type,
        typename boost::mpl::pop_front<SeqB>::type
     >::type>
{ };

template<typename SeqA,
         typename SeqB>
struct equivalent_sequence<SeqA, SeqB, true, true>
  : boost::mpl::true_
{ };

template<typename SeqA,
         typename SeqB,
         bool x>
struct equivalent_sequence<SeqA, SeqB, x, true>
  : boost::mpl::false_
{ };

template<typename SeqA,
         typename SeqB,
         bool x>
struct equivalent_sequence<SeqA, SeqB, true, x>
  : boost::mpl::false_
{ };

#define CHECK(X, expect)                                           \
  {                                                                \
    bool b = equivalent_sequence<X, expect>::value;                \
    ret = ret && b;                                                \
    if(!b)                                                         \
      std::cerr << __FILE__ ":" BOOST_PP_STRINGIZE(__LINE__) ":"   \
        " FAILED: " BOOST_PP_STRINGIZE(X) " not equaivalent to "   \
        BOOST_PP_STRINGIZE(expect) << '\n';                        \
  }

namespace {
  struct conceptA { };
  struct conceptiA { typedef boost::mpl::vector1<conceptA> implies; };
  struct conceptiAiA { typedef boost::mpl::vector1<conceptiA> implies; };
  struct conceptB { };
  struct conceptC { };

  struct fragmentA {
    template<typename Before>
    struct fragment : public Before { };

    typedef boost::mpl::vector1<conceptA> concept;
  };

  struct fragmentAiA {
    template<typename Before>
    struct fragment : public Before { };

    typedef boost::mpl::vector2<conceptA, conceptiA> concept;
  };

  struct fragmentiA {
    template<typename Before>
    struct fragment : public Before { };

    typedef boost::mpl::vector1<conceptiA> concept;
  };

  struct fragmentiAiA {
    template<typename Before>
    struct fragment : public Before { };

    typedef boost::mpl::vector1<conceptiAiA> concept;
  };

  struct fragmentB {
    template<typename Before>
    struct fragment : public Before { };

    typedef boost::mpl::vector1<conceptB> concept;
  };

  struct fragmentC {
    template<typename Before>
    struct fragment : public Before { };

    typedef boost::mpl::vector1<conceptC> concept;
  };

  struct fragment0 {
    template<typename Before>
    struct fragment : public Before { };

    typedef boost::mpl::vector0< > concept;
  };
}

int main() {
  bool ret = true;
  {
    typedef boost::mpl::vector0< > seq;
    typedef boost::mpl::vector0< > result;

    CHECK(fragments::concepts::resulting_concept<seq>::type, result)
  }
  {
    typedef boost::mpl::vector1<fragment0> seq;
    typedef boost::mpl::vector0< > result;

    CHECK(fragments::concepts::resulting_concept<seq>::type, result)
  }
  {
    typedef boost::mpl::vector1<fragmentA> seq;
    typedef boost::mpl::vector1<conceptA> result;

    CHECK(fragments::concepts::resulting_concept<seq>::type, result)
  }
  {
    typedef boost::mpl::vector3<fragmentA, fragmentB, fragmentC> seq;
    typedef boost::mpl::vector3<conceptA, conceptB, conceptC> result;

    CHECK(fragments::concepts::resulting_concept<seq>::type, result)
  }
  {
    typedef boost::mpl::vector1<fragmentiA> seq;
    typedef boost::mpl::vector2<conceptA, conceptiA> result;

    CHECK(fragments::concepts::resulting_concept<seq>::type, result)
  }
  {
    typedef boost::mpl::vector3<fragmentB, fragmentiA, fragmentC> seq;
    typedef boost::mpl::vector4<conceptB, conceptA, conceptiA, conceptC> result;

    CHECK(fragments::concepts::resulting_concept<seq>::type, result)
  }
  {
    typedef boost::mpl::vector1<fragmentiAiA> seq;
    typedef boost::mpl::vector3<conceptA, conceptiA, conceptiAiA> result;

    CHECK(fragments::concepts::resulting_concept<seq>::type, result)
  }
  {
    typedef boost::mpl::vector1<fragmentAiA> seq;
    typedef boost::mpl::vector3<conceptA, conceptA, conceptiA> result;

    CHECK(fragments::concepts::resulting_concept<seq>::type, result)
  }

  {
    typedef boost::mpl::vector2<fragmentA, fragmentiA> seq;
    typedef boost::mpl::vector3<conceptA, conceptA, conceptiA> result;

    CHECK(fragments::concepts::resulting_concept<seq>::type, result)
  }
  return ret ? 0 : 1;
}

max_stars_repo_name: aristidb/fragments

max_issues_repo_name: aristidb/fragments

max_forks_repo_name: aristidb/fragments


text:
/**/
#ifndef CAROS_ButtonSensorSIProxy_HPP_
#define CAROS_ButtonSensorSIProxy_HPP_

#include <caros_sensor_msgs/ButtonSensorState.h>

#include <rw/common/Ptr.hpp>
#include <rw/math.hpp>
#include <rw/trajectory/Path.hpp>
#include <boost/thread.hpp>
#include <std_srvs/Empty.h>
#include <ros/ros.h>

#include <queue>

namespace caros {

/**
 * @brief this class implements a cpp proxy to control and read data from
 * a ButtonSensorServiceInterface.
 *
 */
class ButtonSensorSIProxy {

public:
	typedef rw::common::Ptr<ButtonSensorSIProxy> Ptr;

	//! constructor
	ButtonSensorSIProxy(rw::common::Ptr<ros::NodeHandle> nhandle);

	//! constructor
    ButtonSensorSIProxy(const std::string& devname);

	//! destructor
	virtual ~ButtonSensorSIProxy();

	struct ButtonData {
		float button;
		std::string id;
		bool isAnalog;
		ros::Time stamp;
	};

	std::vector<ButtonData> getButtons();

	ros::Time getTimeStamp();

protected:
	void handleButtonSensorState(const caros_sensor_msgs::ButtonSensorState& state);

protected:
	rw::common::Ptr<ros::NodeHandle> _nodeHnd;

	// states
	ros::Subscriber _buttonSensorState;

private:
	boost::mutex _mutex;

	// state variables
	std::vector<ButtonData> _buttons;
	ros::Time _stamp;
};

}
#endif //end include guard


text:
// Shasta.
#include "Assembler.hpp"
#include "LocalMarkerGraph2.hpp"
using namespace ChanZuckerberg;
using namespace shasta;

// Boost libraries.
#include <boost/graph/iteration_macros.hpp>
#include <boost/uuid/uuid.hpp>
#include <boost/uuid/uuid_generators.hpp>
#include <boost/uuid/uuid_io.hpp>

// Standard library.
#include "chrono.hpp"

void Assembler::exploreMarkerGraph(
    const vector<string>& request,
    ostream& html)
{
    // Get the request parameters.
    LocalMarkerGraphRequestParameters requestParameters;
    getLocalMarkerGraphRequestParameters(request, requestParameters);

    // Write the form.
    requestParameters.writeForm(html, reads.size());

    // If any required values are missing, stop here.
    if(requestParameters.hasMissingRequiredParameters()) {
        return;
    }

    // Validity checks.
    if(requestParameters.readId > reads.size()) {
        html << "
Invalid read id " << requestParameters.readId;
        html << ". Must be between 0 and " << reads.size()-1 << ".";
        return;
    }
    if(requestParameters.strand>1) {
        html << "
Invalid strand " << requestParameters.strand;
        html << ". Must be 0 or 1.";
        return;
    }
    const OrientedReadId orientedReadId(requestParameters.readId, requestParameters.strand);
    const auto orientedReadMarkerCount = markers.size(orientedReadId.getValue());
    if(requestParameters.ordinal >= orientedReadMarkerCount) {
        html <<
            "
Invalid marker ordinal. "
            "Oriented read " << orientedReadId <<
            " has "  << orientedReadMarkerCount <<
            " markers, and therefore the ordinal must be"
            " between 0 and " << orientedReadMarkerCount-1 << ".";
        return;
    }

    // Create the local marker graph.
    LocalMarkerGraph2 graph(
        uint32_t(assemblerInfo->k),
        reads,
        assemblerInfo->useRunLengthReads,
        readRepeatCounts,
        markers,
        globalMarkerGraphVertex,
        *consensusCaller);
    const auto createStartTime = steady_clock::now();
    if(!extractLocalMarkerGraph(
        orientedReadId,
        requestParameters.ordinal,
        requestParameters.maxDistance,
        requestParameters.timeout,
        graph)) {
        html << "
Timeout for graph creation exceeded. Increase the timeout or reduce the maximum distance from the start vertex.";
        return;
    }
    if(num_vertices(graph) == 0) {
        html << "
The specified marker does not correspond to a vertex of the marker graph.";
        return;
    }
    graph.approximateTopologicalSort();
    vector< pair<shasta::Base, int> > sequence;
    if( requestParameters.showOptimalSpanningTree ||
        requestParameters.portionToDisplay=="spanningTree" ||
        requestParameters.portionToDisplay=="optimalPath" ||
        requestParameters.portionToDisplay=="clippedOptimalPath" ||
        requestParameters.showAssembledSequence) {
        graph.computeOptimalSpanningTree();
        graph.computeOptimalSpanningTreeBestPath();
        if(requestParameters.showAssembledSequence) {
            graph.assembleDominantSequence(requestParameters.maxDistance, sequence);
        }
    }
    const auto createFinishTime = steady_clock::now();
    if(seconds(createFinishTime - createStartTime) > requestParameters.timeout) {
        html << "
Timeout for graph creation exceeded. Increase the timeout or reduce the maximum distance from the start vertex.";
        return;
    }

    html <<
        "\n";

    // Assembled sequence from the graph, if requested.
    // This must be done while the graph is still intact.
    if(requestParameters.showAssembledSequence) {

        const string fastaSequenceName =
            "AssembledSequence-" + orientedReadId.getString() +
            "-" + to_string(requestParameters.ordinal) + "-" + to_string(requestParameters.maxDistance);
        const string fastaFileName = fastaSequenceName + ".fa";
        string fastaString = ">" + fastaSequenceName + " length " + to_string(sequence.size()) + "\\n";
        for(const auto& p: sequence) {
            char c = p.first.character();
            const auto coverage = p.second;
            if(coverage < 10) {
                c = char(std::tolower(c));
            }
            fastaString += c;
        }
        fastaString += "\\n";

        html << "
Sequence assembled from this local marker graph
";

        if(!assemblerInfo->useRunLengthReads) {
            html <<
                "
"
                "Assembled sequence";;
            if(assemblerInfo->useRunLengthReads) {
                html << " in run-length representation";
            }
            html << " (" << sequence.size() << " bases).
";
            html << "
Coverage/consensus ("
                "blank if ≥ 10) is shown in blue. Sequence base is lower case if coverage < 10. "
                "Download in FASTA format"
                "";

            // Labels.
            if(assemblerInfo->useRunLengthReads) {
                html << "
";
            } else {
                html << "
";
            }
            for(size_t position=0; position<sequence.size(); position+=10) {
                const string label = to_string(position);
                html << label;
                for(size_t i=0; i<10-label.size(); i++) {
                    html << " ";
                }
            }
            html << "
";

            // Scale.
            if(assemblerInfo->useRunLengthReads) {
                html << "
";
            } else {
                html << "
";
            }
            for(size_t position=0; position<sequence.size(); position++) {
                if((position%10)==0) {
                    html << "|";
                } else if((position%5)==0) {
                    html << "+";
                } else {
                    html << ".";
                }
            }
            html << "
";

            // Sequence.
            if(assemblerInfo->useRunLengthReads) {
                html << "
";
            } else {
                html << "
";
            }
            for(const auto& p: sequence) {
                const auto coverage = p.second;
                if(coverage < 10) {
                    html << char(std::tolower(p.first.character()));
                } else {
                    html << p.first;
                }
            }
            html << "
";

            // Coverage.
            if(assemblerInfo->useRunLengthReads) {
                html << "
";
            } else {
                html << "
";
            }
            for(const auto& p: sequence) {
                const auto coverage = p.second;
                if(coverage<10) {
                    html << coverage;
                } else {
                    html << " ";
                }
            }
            html << "
";
        }

        if(assemblerInfo->useRunLengthReads) {
            graph.assembleDominantSequenceUsingSeqan(html);
        }

#if 0
        // Also show alignments of oriented reads to assembled sequence.
        html << "

Marker alignments of assembled sequence to oriented reads
";
        if(assemblerInfo->useRunLengthReads) {
            html << "
All read and assembled sequence in this table is "
                "in run-length representation.";
            showLocalMarkerGraphAlignments(html, graph, requestParameters);
        }
#endif
    }

    // Remove the portion of the graph that we don't want to display.
    if(requestParameters.portionToDisplay=="spanningTree") {
        graph.removeNonSpanningTreeEdges();
    } else if(requestParameters.portionToDisplay=="optimalPath") {
        graph.removeAllExceptOptimalPath();
    } else if(requestParameters.portionToDisplay=="clippedOptimalPath") {
        graph.removeAllExceptClippedOptimalPath();
    } else if(requestParameters.portionToDisplay=="none") {
        graph.clear();
    }

    // Write it out in graphviz format.
    const string uuid = to_string(boost::uuids::random_generator()());
    const string dotFileName = "/dev/shm/" + uuid + ".dot";
    graph.write(
        dotFileName,
        requestParameters.minCoverage,
        requestParameters.maxDistance,
        requestParameters.detailed,
        requestParameters.showVertexId);

    // Compute layout in svg format.
    const string command =
        "timeout " + to_string(requestParameters.timeout - seconds(createFinishTime - createStartTime)) +
        " dot -O -T svg " + dotFileName +
        " -Gsize=" + to_string(requestParameters.sizePixels/72.);
    const int commandStatus = ::system(command.c_str());
    if(WIFEXITED(commandStatus)) {
        const int exitStatus = WEXITSTATUS(commandStatus);
        if(exitStatus == 124) {
            html << "
Timeout for graph layout exceeded. Increase the timeout or reduce the maximum distance from the start vertex.";
            filesystem::remove(dotFileName);
            return;
        }
        else if(exitStatus!=0 && exitStatus!=1) {    // sfdp returns 1 all the time just because of the message about missing triangulation.
            filesystem::remove(dotFileName);
            throw runtime_error("Error " + to_string(exitStatus) + " running graph layout command: " + command);
        }
    } else if(WIFSIGNALED(commandStatus)) {
        const int signalNumber = WTERMSIG(commandStatus);
        throw runtime_error("Signal " + to_string(signalNumber) + " while running graph layout command: " + command);
    } else {
        throw runtime_error("Abnormal status " + to_string(commandStatus) + " while running graph layout command: " + command);

    }
    // Remove the .dot file.
    filesystem::remove(dotFileName);

    // Write the graph.
    if(requestParameters.portionToDisplay == "none") {
        html << "
As requested, the graph was not displayed.";
    } else {
        // Write the page title.
        const string legendName =
            requestParameters.detailed ?
            "MarkerGraphLegend-Detailed.html" :
            "MarkerGraphLegend-Compact.html";
        html <<
            "
Marker graph near marker " << requestParameters.ordinal <<
            " of oriented read " << orientedReadId <<
            " <a href='docs/" << legendName << "'>(see legend)
";

        const string svgFileName = dotFileName + ".svg";
        ifstream svgFile(svgFileName);
        html << svgFile.rdbuf();
        svgFile.close();

        // Remove the .svg file.
        filesystem::remove(svgFileName);

        // Make the vertices clickable to recompute the graph with the
        // same parameters, but starting at the clicked vertex.
        // For a detailed graph, only the "Distance" label of each vertex
        // is made clickable.
        html << "\n";

        // Position the start vertex at the center of the window.
        const GlobalMarkerGraphVertexId startVertexId =
            getGlobalMarkerGraphVertex(orientedReadId, requestParameters.ordinal);
        html <<
            "\n";
    }
}

// Extract  from the request the parameters for the display
// of the local marker graph.
void Assembler::getLocalMarkerGraphRequestParameters(
    const vector<string>& request,
    LocalMarkerGraphRequestParameters& parameters) const
{
    parameters.readId = 0;
    parameters.readIdIsPresent = getParameterValue(
        request, "readId", parameters.readId);

    parameters.strand = 0;
    parameters.strandIsPresent = getParameterValue(
        request, "strand", parameters.strand);

    parameters.ordinal = 0;
    parameters.ordinalIsPresent = getParameterValue(
        request, "ordinal", parameters.ordinal);

    parameters.maxDistance = 0;
    parameters.maxDistanceIsPresent = getParameterValue(
        request, "maxDistance", parameters.maxDistance);

    string detailedString;
    parameters.detailed = getParameterValue(
        request, "detailed", detailedString);

    string showVertexIdString;
    parameters.showVertexId = getParameterValue(
        request, "showVertexId", showVertexIdString);

    string showOptimalSpanningTreeString;
    parameters.showOptimalSpanningTree = getParameterValue(
        request, "showOptimalSpanningTree", showOptimalSpanningTreeString);

    string showAssembledSequenceString;
    parameters.showAssembledSequence = getParameterValue(
        request, "showAssembledSequence", showAssembledSequenceString);

    parameters.minCoverage = 0;
    parameters.minCoverageIsPresent = getParameterValue(
        request, "minCoverage", parameters.minCoverage);

    parameters.sizePixels = 800;
    parameters.sizePixelsIsPresent = getParameterValue(
        request, "sizePixels", parameters.sizePixels);

    parameters.timeout = 30;
    parameters.timeoutIsPresent = getParameterValue(
        request, "timeout", parameters.timeout);

    parameters.portionToDisplay = "all";
    getParameterValue(
        request, "portionToDisplay", parameters.portionToDisplay);

}

void Assembler::LocalMarkerGraphRequestParameters::writeForm(
    ostream& html,
    size_t readCount) const
{
    html <<
        "
Display a local subgraph of the global marker graph
"
        "<form>"

        "
"

        "<tr title='Read id between 0 and " << readCount-1 << "'>"
        "Read id"
        "<input type=text required name=readId size=8 style='text-align:center'"
        << (readIdIsPresent ? ("value='"+to_string(readId)+"'") : "") <<
        ">"

        "
"
        "Strand"
        "";
    writeStrandSelection(html, "strand",
        strandIsPresent && strand==0,
        strandIsPresent && strand==1);

    html <<
        "
"
        "Marker ordinal"
        "<input type=text required name=ordinal size=8 style='text-align:center'"
        << (ordinalIsPresent ? ("value='"+to_string(ordinal)+"'") : "") <<
        ">"

        "
"
        "Maximum distance"
        "<input type=text required name=maxDistance size=8 style='text-align:center'"
        << (maxDistanceIsPresent ? ("value='" + to_string(maxDistance)+"'") : " value='6'") <<
        ">"

        "
"
        "Detailed"
        "<input type=checkbox name=detailed"
        << (detailed ? " checked=checked" : "") <<
        ">"

        "
"
        "Show vertex ids"
        "<input type=checkbox name=showVertexId"
        << (showVertexId ? " checked=checked" : "") <<
        ">"

        "
"
        "Show optimal spanning tree"
        "<input type=checkbox name=showOptimalSpanningTree"
        << (showOptimalSpanningTree ? " checked=checked" : "") <<
        ">"

        "
"
        "Show assembled sequence"
        "<input type=checkbox name=showAssembledSequence"
        << (showAssembledSequence ? " checked=checked" : "") <<
        ">"

        "
"
        "Coverage threshold"
        "<input type=text required name=minCoverage size=8 style='text-align:center'"
        << (minCoverageIsPresent ? (" value='" + to_string(minCoverage)+"'") : " value='3'") <<
        ">"

        "
"
        "Graphics size in pixels"
        "<input type=text required name=sizePixels size=8 style='text-align:center'"
        << (sizePixelsIsPresent ? (" value='" + to_string(sizePixels)+"'") : " value='1600'") <<
        ">"

        "
"
        "Timeout (seconds) for graph creation and layout"
        "<input type=text required name=timeout size=8 style='text-align:center'"
        << (timeoutIsPresent ? (" value='" + to_string(timeout)+"'") : " value='30'") <<
        ">"
        "
"

        // Radio buttons to choose what portion of the graph to display.
        "Portion of the graph to display:"

        "
<input type=radio name=portionToDisplay value=all" <<
        (portionToDisplay=="all" ? " checked=on" : "") <<
        ">Entire graph"

        "
<input type=radio name=portionToDisplay value=spanningTree" <<
        (portionToDisplay=="spanningTree" ? " checked=on" : "") <<
        ">Optimal spanning tree only"

        "
<input type=radio name=portionToDisplay value=optimalPath" <<
        (portionToDisplay=="optimalPath" ? " checked=on" : "") <<
        ">Optimal spanning tree best path only"

        "
<input type=radio name=portionToDisplay value=clippedOptimalPath" <<
        (portionToDisplay=="clippedOptimalPath" ? " checked=on" : "") <<
        "><span "
        " title='Longest subpath of the best path in the optimal spanning tree "
        "that does not contain any vertices at maximum distance. "
        "This subpath is used to assemble sequence.'" <<
        ">Path used to assemble sequence"

        "
<input type=radio name=portionToDisplay value=none" <<
        (portionToDisplay=="none" ? " checked=on" : "") <<
        ">Nothing"

        "
<input type=submit value='Display'>"

        " <span style='background-color:#e0e0e0' title='"
        "Fill this form to display a local subgraph of the global marker graph starting at the "
        "vertex containing the specified marker and extending out to a given distance "
        "(number of edges) from the start vertex."
        "The marker is specified by its oriented read id (read id, strand) and marker ordinal. "
        "The marker ordinal is the sequential index of the marker in the specified oriented read "
        "(the first marker is marker 0, the second marker is marker 1, and so on).'>"
        "Mouse here to explain form"
        "</form>";
}

bool Assembler::LocalMarkerGraphRequestParameters::hasMissingRequiredParameters() const
{
    return
        !readIdIsPresent ||
        !strandIsPresent ||
        !ordinalIsPresent ||
        !maxDistanceIsPresent ||
        !minCoverageIsPresent ||
        !timeoutIsPresent;
}

void Assembler::showLocalMarkerGraphAlignments(
    ostream& html,
    const LocalMarkerGraph2& graph,
    const LocalMarkerGraphRequestParameters& requestParameters
    )
{
    using vertex_descriptor = LocalMarkerGraph2::vertex_descriptor;
    using edge_descriptor = LocalMarkerGraph2::edge_descriptor;
    const size_t k = assemblerInfo->k;

    // Create a table with one column for each vertex
    // (in topologically sorted order), plus an additional column
    // between each pair of successive vertices.
    html << "
";

    // Row with vertex ids.
    if(requestParameters.showVertexId) {
        html << "
Vertex";
        for(size_t i=0; i<graph.topologicallySortedVertices.size(); i++) {
            const vertex_descriptor v = graph.topologicallySortedVertices[i];
            const LocalMarkerGraph2Vertex& vertex = graph[v];
            const auto vertexId = graph[v].vertexId;

            // Color.
            string color;
            if(vertex.distance == int(requestParameters.maxDistance)) {
                color = "cyan";
            } else if(vertex.distance == 0) {
                color = "lightGreen";
            } else if(vertex.markerInfos.size() >= requestParameters.minCoverage) {
                color = "green";
            } else {
                color = "red";
            }

            html << "<td style='background-color:" << color << ";text-align:center;font-size:8px'";
            if(requestParameters.portionToDisplay != "none") {
                html <<
                    " title='Click to position graph display at this vertex.'"
                    " onClick='positionAtVertex(" << vertexId << ")'";
            }
            html << ">";
            html << vertexId;

            // Add a column before the next vertex.
            if(i != graph.topologicallySortedVertices.size()-1) {
                html << "";
            }
        }
    }

    // Row with vertex ranks.
    html << "
Rank";
    for(size_t i=0; i<graph.topologicallySortedVertices.size(); i++) {
        const vertex_descriptor v = graph.topologicallySortedVertices[i];
        const LocalMarkerGraph2Vertex& vertex = graph[v];

        // Color.
        string color;
        if(vertex.distance == int(requestParameters.maxDistance)) {
            color = "cyan";
        } else if(vertex.distance == 0) {
            color = "lightGreen";
        } else if(vertex.markerInfos.size() >= requestParameters.minCoverage) {
            color = "green";
        } else {
            color = "red";
        }

        html << "<td style='background-color:" << color << ";text-align:center;cursor:pointer'";
        if(requestParameters.portionToDisplay != "none") {
            html <<
                " title='Vertex rank. Click to position graph display at this vertex.'"
                " onClick='positionAtVertex(" << vertex.vertexId << ")'";
        }
        html << ">";
        html << vertex.rank;

        // Add a column before the next vertex.
        if(i != graph.topologicallySortedVertices.size()-1) {
            html << "";
        }
    }

    // Row with vertex distances.
    html << "
Distance";
    for(size_t i=0; i<graph.topologicallySortedVertices.size(); i++) {
        const vertex_descriptor v = graph.topologicallySortedVertices[i];
        const LocalMarkerGraph2Vertex& vertex = graph[v];

        // Color.
        string color;
        if(vertex.distance == int(requestParameters.maxDistance)) {
            color = "cyan";
        } else if(vertex.distance == 0) {
            color = "lightGreen";
        } else if(vertex.markerInfos.size() >= requestParameters.minCoverage) {
            color = "green";
        } else {
            color = "red";
        }

        html << "<td style='background-color:" << color << ";text-align:center;cursor:pointer'";
        if(requestParameters.portionToDisplay != "none") {
            html <<
                " title='Vertex distance (number of edges) from start vertex. "
                "Click to position graph display at this vertex.'"
                " onClick='positionAtVertex(" << vertex.vertexId << ")'";
        }
        html << ">";
        html << vertex.distance;

        // Add a column before the next vertex.
        if(i != graph.topologicallySortedVertices.size()-1) {
            html << "";
        }
    }

    // Row with marker k-mers.
    html << "
Marker k-mer";
    for(size_t i=0; i<graph.topologicallySortedVertices.size(); i++) {
        const vertex_descriptor v = graph.topologicallySortedVertices[i];
        const LocalMarkerGraph2Vertex& vertex = graph[v];

        // Color.
        string color;
        if(vertex.distance == int(requestParameters.maxDistance)) {
            color = "cyan";
        } else if(vertex.distance == 0) {
            color = "lightGreen";
        } else if(vertex.markerInfos.size() >= requestParameters.minCoverage) {
            color = "green";
        } else {
            color = "red";
        }

        const KmerId kmerId = graph.getKmerId(v);
        const Kmer kmer(kmerId, k);

        html << "<td style='background-color:" << color << ";text-align:center;cursor:pointer'";
        if(requestParameters.portionToDisplay != "none") {
            html <<
                " title='Click to position graph display at this vertex.'"
                " onClick='positionAtVertex(" << vertex.vertexId << ")'";
        }
        html << ">";
        kmer.write(html, k);

        // Add a column before the next vertex.
        if(i != graph.topologicallySortedVertices.size()-1) {
            html << "";
        }
    }

    // Row with assembled sequence.
    html <<
        "
"
        "Assembled sequence";
    const vector<edge_descriptor>& assemblyPath = graph.localAssemblyPath;

    // Verify that rank increases along the assembly path.
    bool assemblyPathViolatesRankOrder = false;
    for(size_t i=0; i<assemblyPath.size(); i++) {
        const edge_descriptor e = assemblyPath[i];
        const vertex_descriptor v0 = source(e, graph);
        const vertex_descriptor v1 = target(e, graph);
        if(graph[v1].rank <= graph[v0].rank) {
            assemblyPathViolatesRankOrder = true;
            break;
        }
    }
    if(assemblyPathViolatesRankOrder) {
        html <<
            "<td colspan=" << 2*graph.topologicallySortedVertices.size()-1 << ">"
            "Assembly path violates rank order.";
    }

    // If necessary, add an empty cell at the beginning, covering up to and excluding
    // the vertex with lowest rank.
    const edge_descriptor firstEdge = assemblyPath.front();
    const vertex_descriptor firstVertex = source(firstEdge, graph);
    const size_t lowestRank = graph[firstVertex].rank;
    if(lowestRank > 0) {
        html << "<td colspan=" << 2*lowestRank << ">";
    }

    // Write the marker of the first vertex.
    const KmerId firstKmerId = graph.getKmerId(firstVertex);
    const Kmer firstKmer(firstKmerId, k);
    html << "";
    for(size_t i=0; i<k; i++) {
        const Base base = firstKmer[i];
        char c = base.character();
        if(graph[firstVertex].markerInfos.size() < 10) {
            c = char(std::tolower(c));
        }
        html << c;
    }

    // To add assembled sequence to the alignment table,
    // loop over edges of the assembly path.
    // The code here is similar to LocalMarkerGraph2::assembleDominantSequence.
    for(const edge_descriptor e: assemblyPath) {
        const LocalMarkerGraph2Edge& edge = graph[e];
        const auto consensus = edge.consensus();
        const vertex_descriptor v0 = source(e, graph);
        const vertex_descriptor v1 = target(e, graph);
        const LocalMarkerGraph2Vertex& vertex0 = graph[v0];
        const LocalMarkerGraph2Vertex& vertex1 = graph[v1];
        const size_t rank0 = vertex0.rank;
        const size_t rank1 = vertex1.rank;
        CZI_ASSERT(rank0 < rank1);  // We checked for this above.

        // Write the edge sequence, if any.
        CZI_ASSERT(!edge.infos.empty());
        const auto& p = edge.infos.front();
        // const auto coverage = p.second.size();
        const auto& edgeSequence = p.first.sequence;
        html << "<td colspan=" << 2*(rank1-rank0) - 1 << ">";
        for(const shasta::Base b: edgeSequence) {
            char c = b.character();
            if(consensus < 10) {
                c = char(std::tolower(c));
            }
            html << c;
        }

        // Write the sequence of the target vertex.
        const KmerId kmerId1 = graph.getKmerId(v1);
        const Kmer kmer1(kmerId1, k);
        const auto coverage1 = graph[v1].markerInfos.size();
        html << "";
        for(size_t i=size_t(p.first.overlappingBaseCount); i<k; i++) {
            const Base b = kmer1[i];
            char c = b.character();
            if(coverage1 < 10) {
                c = char(std::tolower(c));
            }
            html << c;
        }
    }

    // If necessary, also add an empty cell at the end.
    const edge_descriptor lastEdge = assemblyPath.back();
    const vertex_descriptor lastVertex = target(lastEdge, graph);
    const size_t highestRank = graph[lastVertex].rank;
    if(highestRank < graph.topologicallySortedVertices.size()-1) {
        html << "<td colspan=" << 2*(graph.topologicallySortedVertices.size()-1 -highestRank) << ">";
    }

    // Repeat the  loop over edges of the assembly path
    // to add a row with assembled position.
    html << "
"
        "Assembled position";
    if(lowestRank > 0) {
        html << "<td colspan=" << 2*lowestRank << ">";
    }
    size_t position = 0;
    html << "" << position;
    position += k;
    for(const edge_descriptor e: assemblyPath) {
        const LocalMarkerGraph2Edge& edge = graph[e];
        const vertex_descriptor v0 = source(e, graph);
        const vertex_descriptor v1 = target(e, graph);
        const LocalMarkerGraph2Vertex& vertex0 = graph[v0];
        const LocalMarkerGraph2Vertex& vertex1 = graph[v1];
        const size_t rank0 = vertex0.rank;
        const size_t rank1 = vertex1.rank;
        CZI_ASSERT(rank0 < rank1);  // We checked for this above.
        const auto& p = edge.infos.front();
        const auto& edgeSequence = p.first.sequence;

        html <<
            "<td class=centered colspan=" << 2*(rank1-rank0) - 1 <<
            ">" << position;
        position += edgeSequence.size();
        html << "" << position + p.first.overlappingBaseCount;
        position += k - p.first.overlappingBaseCount;
    }
    if(highestRank < graph.topologicallySortedVertices.size()-1) {
        html << "<td colspan=" << 2*(graph.topologicallySortedVertices.size()-1 -highestRank) << ">";
    }

    // Repeat the  loop over edges of the assembly path
    // to add a row for vertex and edge coverage.
    html << "
Coverage";
    if(lowestRank > 0) {
        html << "<td colspan=" << 2*lowestRank << ">";
    }
    html << "" << graph[firstVertex].markerInfos.size();
    for(const edge_descriptor e: assemblyPath) {
        const LocalMarkerGraph2Edge& edge = graph[e];
        const vertex_descriptor v0 = source(e, graph);
        const vertex_descriptor v1 = target(e, graph);
        const LocalMarkerGraph2Vertex& vertex0 = graph[v0];
        const LocalMarkerGraph2Vertex& vertex1 = graph[v1];
        const size_t rank0 = vertex0.rank;
        const size_t rank1 = vertex1.rank;
        CZI_ASSERT(rank0 < rank1);  // We checked for this above.

        html <<
            "<td class=centered colspan=" << 2*(rank1-rank0) - 1 <<
            ">" << edge.coverage() << "" << vertex1.markerInfos.size();
    }
    if(highestRank < graph.topologicallySortedVertices.size()-1) {
        html << "<td colspan=" << 2*(graph.topologicallySortedVertices.size()-1 -highestRank) << ">";
    }

    // Repeat the  loop over edges of the assembly path
    // to add a row for edge consensus.
    html << "
Consensus";
    if(lowestRank > 0) {
        html << "<td colspan=" << 2*lowestRank << ">";
    }
    html << ""; // First vertex
    for(const edge_descriptor e: assemblyPath) {
        const LocalMarkerGraph2Edge& edge = graph[e];
        const vertex_descriptor v0 = source(e, graph);
        const vertex_descriptor v1 = target(e, graph);
        const LocalMarkerGraph2Vertex& vertex0 = graph[v0];
        const LocalMarkerGraph2Vertex& vertex1 = graph[v1];
        const size_t rank0 = vertex0.rank;
        const size_t rank1 = vertex1.rank;
        CZI_ASSERT(rank0 < rank1);  // We checked for this above.

        html <<
            "<td class=centered colspan=" << 2*(rank1-rank0) - 1 <<
            ">" << edge.consensus() << "";
    }
    if(highestRank < graph.topologicallySortedVertices.size()-1) {
        html << "<td colspan=" << 2*(graph.topologicallySortedVertices.size()-1 -highestRank) << ">";
    }

    // Add a row for each oriented read.
    for(const OrientedReadId orientedReadId: graph.orientedReadIds) {
        html <<
            "<tr title='Oriented read " << orientedReadId <<
            "'><a href='exploreRead?readId&" << orientedReadId.getReadId() <<
            "&strand=" << orientedReadId.getStrand() << "'>" <<
            orientedReadId << "";

        // Find the graph vertices corresponding to this oriented read,
        // and the corresponding ordinals.
        vector< pair<uint32_t, vertex_descriptor> > orientedReadVertices;
        graph.getOrientedReadVertices(orientedReadId, orientedReadVertices);

#if 0
        // Write out details of the vertices.
        cout << orientedReadId << " vertices:" << endl;
        for(size_t i=0; i<orientedReadVertices.size(); i++) {
            const auto& p = orientedReadVertices[i];
            const uint32_t ordinal = p.first;
            const vertex_descriptor v = p.second;
            const LocalMarkerGraph2Vertex& vertex = graph[v];
            cout << "Vertex " << vertex.vertexId;
            cout << " distance " << vertex.distance;
            cout << " rank " << vertex.rank;
            cout << " ordinal " << ordinal;
            if(i>0 && graph[orientedReadVertices[i-1].second].rank >= vertex.rank) {
                cout << " rank order violation";
            }
            cout << endl;
        }
#endif

        // Get rid of the vertices that are inconsistent with rank ordering.
        vector< pair<uint32_t, vertex_descriptor> > rankEnforcedOrientedReadVertices;
        graph.enforceRankOrder(orientedReadVertices, rankEnforcedOrientedReadVertices);

#if 0
        // Write out details of the vertices.
        for(size_t i=0; i<rankEnforcedOrientedReadVertices.size(); i++) {
            const auto& p = rankEnforcedOrientedReadVertices[i];
            const uint32_t ordinal = p.first;
            const vertex_descriptor v = p.second;
            const LocalMarkerGraph2Vertex& vertex = graph[v];
            cout << "Vertex " << vertex.vertexId;
            cout << " distance " << vertex.distance;
            cout << " rank " << vertex.rank;
            cout << " ordinal " << ordinal;
            cout << endl;
            if(i>0) {
                CZI_ASSERT(graph[rankEnforcedOrientedReadVertices[i-1].second].rank < vertex.rank);
            }
        }
#endif

        // If we have no vertices, just write an empty cell covering the entire width.
        if(rankEnforcedOrientedReadVertices.empty()) {
            html << "<td colspan=" << 2*graph.topologicallySortedVertices.size()-1 << ">";
            continue;
        }

        // If necessary, add an empty cell at the beginning, covering up to and excluding
        // the vertex with lowest rank.
        const size_t lowestRank = graph[rankEnforcedOrientedReadVertices.front().second].rank;
        if(lowestRank > 0) {
            html << "<td colspan=" << 2*lowestRank << ">";
        }

        // Loop over the vertices.
        size_t skipBaseCount = 0;
        for(size_t i=0; i<rankEnforcedOrientedReadVertices.size(); i++) {

            // Get the information we need about this vertex.
            const auto& p0 = rankEnforcedOrientedReadVertices[i];
            const uint32_t ordinal0 = p0.first;
            const vertex_descriptor v0 = p0.second;
            const LocalMarkerGraph2Vertex& vertex0 = graph[v0];
            const size_t rank0 = vertex0.rank;
            const KmerId kmerId0 = graph.getKmerId(v0);
            const Kmer kmer0(kmerId0, k);
            const MarkerId markerId0 = getMarkerId(orientedReadId, ordinal0);
            const CompressedMarker& marker0 = markers.begin()[markerId0];

            // Write the k-mer.
            html << "<td style='text-align:right' title='Oriented read " << orientedReadId <<
                " marker ordinal " << ordinal0 <<
                ", positions " << marker0.position << "-" << marker0.position+k-1;
            if(skipBaseCount>0) {
                html << " (first " << skipBaseCount << " bases overlap with previous marker and are not displayed)";
            }
            html <<
                "'>"
                "<a style='text-decoration:none;color:black' href='exploreRead?readId=" << orientedReadId.getReadId() <<
                "&strand=" << orientedReadId.getStrand() <<
                "&highlightMarker=" << ordinal0 <<
                "'>";
            for(size_t j=skipBaseCount; j<k; j++) {
                html << kmer0[j];
            }
            html << "";

            // If this is the last vertex, we are done.
            if(i == rankEnforcedOrientedReadVertices.size()-1) {
                continue;
            }

            // Get the information we need about the next vertex.
            const auto& p1 = rankEnforcedOrientedReadVertices[i+1];
            const uint32_t ordinal1 = p1.first;
            const vertex_descriptor v1 = p1.second;
            const LocalMarkerGraph2Vertex& vertex1 = graph[v1];
            const size_t rank1 = vertex1.rank;

            // Write the cell in between these two vertices.
            const MarkerId markerId1 = getMarkerId(orientedReadId, ordinal1);
            const CompressedMarker& marker1 = markers.begin()[markerId1];
            const uint32_t position0 = marker0.position;
            const uint32_t position1 = marker1.position;
            html << "<td colspan=" << 2*(rank1-rank0)-1;
            if(position1-1 >= position0+k) {
                html <<
                    " title='Oriented read " << orientedReadId << " between markers " <<
                    ordinal0 << "-" << ordinal1 <<
                    ", positions " << position0+k << "-" << position1-1 << "'";
            }
            html <<
                ">"
                "<a style='text-decoration:none;color:black' href='exploreRead?readId=" << orientedReadId.getReadId() <<
                "&strand=" << orientedReadId.getStrand() <<
                "&highlightMarker=" << ordinal0 <<
                "&highlightMarker=" << ordinal1 <<
                "'>";

            // Write the sequence in between the two vertices.
            if(position1 > position0+k) {
                if(position1-position0-k > 100) {
                    html << "Too long";
                } else {
                    for(uint32_t position=position0+uint32_t(k); position<position1; position++) {
                        html << getOrientedReadBase(orientedReadId, position);
                    }
                }
                skipBaseCount = 0;
            } else {
                skipBaseCount = position0+k-position1;
            }
            html << "";
        }

        // If necessary, also add an empty cell at the end
        const size_t highestRank = graph[rankEnforcedOrientedReadVertices.back().second].rank;
        if(highestRank < graph.topologicallySortedVertices.size()-1) {
            html << "<td colspan=" << 2*(graph.topologicallySortedVertices.size()-1 - lowestRank) << ">";
        }
    }

    // Finish the table
    html << "
";
}

max_stars_repo_name: jeizenga/shasta

max_issues_repo_name: jeizenga/shasta

max_forks_repo_name: jeizenga/shasta