andrewm@0: /*
andrewm@0:   TouchKeys: multi-touch musical keyboard control software
andrewm@0:   Copyright (c) 2013 Andrew McPherson
andrewm@0: 
andrewm@0:   This program is free software: you can redistribute it and/or modify
andrewm@0:   it under the terms of the GNU General Public License as published by
andrewm@0:   the Free Software Foundation, either version 3 of the License, or
andrewm@0:   (at your option) any later version.
andrewm@0:  
andrewm@0:   This program is distributed in the hope that it will be useful,
andrewm@0:   but WITHOUT ANY WARRANTY; without even the implied warranty of
andrewm@0:   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
andrewm@0:   GNU General Public License for more details.
andrewm@0: 
andrewm@0:   You should have received a copy of the GNU General Public License
andrewm@0:   along with this program.  If not, see <http://www.gnu.org/licenses/>.
andrewm@0:  
andrewm@0:   =====================================================================
andrewm@0: 
andrewm@0:   Node.h: template class which wraps a circular buffer, providing a collection
andrewm@0:   of methods for inserting, accessing and iterating over data (including
andrewm@0:   interpolation). Also provides trigger functionality to notify listeners when
andrewm@0:   new objects are inserted. Unlike conventional containers, indices always increment
andrewm@0:   over time, even though only the last N objects will be held in the buffer. The
andrewm@0:   beginning index will therefore be greater than 0 in many cases, but the index of
andrewm@0:   a particular item will never change, even if the item itself eventually is dropped
andrewm@0:   from the buffer.
andrewm@0: */
andrewm@0: 
andrewm@0: #ifndef KEYCONTROL_NODE_H
andrewm@0: #define KEYCONTROL_NODE_H
andrewm@0: 
andrewm@0: #include <iostream>
andrewm@0: #include <set>
andrewm@20: #include <cmath>
andrewm@20: #include <stdint.h>
andrewm@0: #include <boost/circular_buffer.hpp>
andrewm@0: #include <boost/lambda/lambda.hpp>
andrewm@0: #include "Types.h"
andrewm@0: #include "Trigger.h"
andrewm@20: #include "../JuceLibraryCode/JuceHeader.h"
andrewm@20: 
andrewm@0: 
andrewm@0: template<typename OutputType> class NodeNonInterpolating;
andrewm@0: template<typename OutputType> class Node;
andrewm@0: 
andrewm@0: /*
andrewm@0:  * NodeIterator
andrewm@0:  *
andrewm@0:  * Abstract class that implements common functionality for all types of Sources and Filters
andrewm@0:  * Modeled on (and contains) boost::cb_details::iterator
andrewm@0:  * See boost/circular_buffer/details.hpp for more information
andrewm@0:  *
andrewm@0:  */
andrewm@0: 
andrewm@0: // Custom iterator type to move through the Node buffer
andrewm@0: template <class OutputType, class Traits, class NonConstTraits>
andrewm@0: struct NodeIterator :
andrewm@0: 	public boost::iterator<
andrewm@0: 	std::random_access_iterator_tag,
andrewm@0: 	typename Traits::value_type,
andrewm@0: 	typename Traits::difference_type,
andrewm@0: 	typename Traits::pointer,
andrewm@0: 	typename Traits::reference>
andrewm@0: {
andrewm@0:     typedef boost::iterator<
andrewm@0: 		std::random_access_iterator_tag,
andrewm@0: 		typename Traits::value_type,
andrewm@0: 		typename Traits::difference_type,
andrewm@0: 		typename Traits::pointer,
andrewm@0: 		typename Traits::reference> base_iterator;
andrewm@0: 	
andrewm@0: 	typedef NodeNonInterpolating<OutputType> Buff;
andrewm@0: 	
andrewm@0: 	typedef NodeIterator<Buff, typename Traits::nonconst_self, NonConstTraits> nonconst_self;
andrewm@0: 	typedef typename boost::cb_details::iterator<boost::circular_buffer<OutputType>, NonConstTraits> cb_iterator;
andrewm@0: 	
andrewm@0: 	typedef typename base_iterator::value_type value_type;
andrewm@0: 	typedef typename base_iterator::pointer pointer;
andrewm@0: 	typedef typename base_iterator::reference reference;
andrewm@0: 	typedef typename Traits::size_type size_type;
andrewm@0: 	typedef typename base_iterator::difference_type difference_type;
andrewm@0: 	
andrewm@0: 	// ***** Member Variables *****
andrewm@0:     
andrewm@0:     // Pointer to the Node object
andrewm@0: 	Buff* m_buff;
andrewm@0:     
andrewm@0: 	// Base (non-const) iterator to the circular buffer
andrewm@0: 	cb_iterator m_cb_it;
andrewm@0: 	
andrewm@0: 	// ***** Constructors *****
andrewm@0: 	
andrewm@0: 	// Default constructor
andrewm@0: 	NodeIterator() : m_buff(0), m_cb_it(cb_iterator()) {}
andrewm@0: 	
andrewm@0: 	// Copy constructor
andrewm@0: 	NodeIterator(const nonconst_self& it) : m_cb_it(it.m_cb_it) {}
andrewm@0: 	
andrewm@0: 	// Constructor based on a circular_buffer iterator
andrewm@0: 	NodeIterator(Buff* cb, const cb_iterator cb_it) : m_buff(cb), m_cb_it(cb_it) {}
andrewm@0: 	
andrewm@0: 	// ***** Operators *****
andrewm@0: 	//
andrewm@0: 	// Modeled on boost::cb_details::iterator (boost/circular_buffer/details.hpp)
andrewm@0: 	
andrewm@0:     NodeIterator& operator = (const NodeIterator& it) {
andrewm@0:         if (this == &it)
andrewm@0:             return *this;
andrewm@0:         m_buff = it.m_buff;
andrewm@0:         m_cb_it = it.m_cb_it;
andrewm@0:         return *this;
andrewm@0:     }	
andrewm@0: 	
andrewm@0: 	// Dereferencing operator.  We change the behavior here to evaluate missing values as needed.
andrewm@0: 	// Note that this requires m_cb_it to be a non_const type, even if we are a const iterator.
andrewm@0: 	
andrewm@0:     reference operator * () const {
andrewm@0: 		return *m_cb_it;
andrewm@0: 		//reference val = *m_cb_it;
andrewm@0: 		//if(!missing_value<OutputType>::isMissing(val))
andrewm@0: 		//	return val;
andrewm@0: 		//return (*m_cb_it = m_buff->evaluate(index()));
andrewm@0:     }	
andrewm@0: 	
andrewm@0: 	pointer operator -> () const { return &(operator*()); }
andrewm@0: 	
andrewm@0:     template <class Traits0, class Traits1>
andrewm@0:     difference_type operator - (const NodeIterator<OutputType, Traits0, Traits1>& it) const { return m_cb_it - it.m_cb_it; }
andrewm@0: 	
andrewm@0:     NodeIterator& operator ++ () {			// ++it
andrewm@0: 		++m_cb_it;
andrewm@0: 		return *this;
andrewm@0: 	}
andrewm@0: 	NodeIterator operator ++ (int) {		// it++
andrewm@0: 		NodeIterator<OutputType, Traits, NonConstTraits> tmp = *this;
andrewm@0: 		++m_cb_it;
andrewm@0: 		return tmp;
andrewm@0: 	}
andrewm@0: 	NodeIterator& operator -- () {			// --it
andrewm@0: 		--m_cb_it; 
andrewm@0: 		return *this;
andrewm@0: 	}
andrewm@0: 	NodeIterator operator -- (int) {		// it--
andrewm@0: 		NodeIterator<OutputType, Traits, NonConstTraits> tmp = *this;
andrewm@0: 		m_cb_it--; 
andrewm@0: 		return tmp;
andrewm@0: 	}
andrewm@0:     NodeIterator& operator += (difference_type n) {		// it += n
andrewm@0: 		m_cb_it += n;
andrewm@0:         return *this;
andrewm@0:     }	
andrewm@0:     NodeIterator& operator -= (difference_type n) {		// it -= n
andrewm@0: 		m_cb_it -= n;
andrewm@0:         return *this;
andrewm@0:     }		
andrewm@0: 	
andrewm@0: 	NodeIterator operator + (difference_type n) const { return NodeIterator<OutputType, Traits, NonConstTraits>(*this) += n; }
andrewm@0: 	NodeIterator operator - (difference_type n) const { return NodeIterator<OutputType, Traits, NonConstTraits>(*this) -= n; }
andrewm@0: 	
andrewm@0: 	reference operator [] (difference_type n) const { return *(*this + n); }
andrewm@0: 	
andrewm@0: 	// ***** Comparisons *****
andrewm@0: 	//
andrewm@0: 	// This iterator class implements some unusual comparison behavior: two iterators are evaluated by their offset within
andrewm@0: 	// their respective buffers, even if they point to separate buffers.  When used on synchronized buffers, this allows
andrewm@0: 	// us to evaluate which of two iterators points to the earlier event.
andrewm@0: 	
andrewm@0:     template <class OutputType0, class Traits0, class Traits1>
andrewm@0:     bool operator == (const NodeIterator<OutputType0, Traits0, Traits1>& it) const { 
andrewm@0: 		return index() == it.index(); 
andrewm@0: 	}
andrewm@0: 	
andrewm@0:     template <class OutputType0, class Traits0, class Traits1>
andrewm@0:     bool operator != (const NodeIterator<OutputType0, Traits0, Traits1>& it) const { 
andrewm@0: 		return index() != it.index(); 
andrewm@0: 	}	
andrewm@0: 	
andrewm@0:     template <class OutputType0, class Traits0, class Traits1>
andrewm@0:     bool operator < (const NodeIterator<OutputType0, Traits0, Traits1>& it) const { 
andrewm@0: 		return index() < it.index(); 
andrewm@0: 	}	
andrewm@0: 	
andrewm@0:     template <class OutputType0, class Traits0, class Traits1>
andrewm@0:     bool operator > (const NodeIterator<OutputType0, Traits0, Traits1>& it) const { return it < *this; }
andrewm@0: 	
andrewm@0:     template <class OutputType0, class Traits0, class Traits1>
andrewm@0:     bool operator <= (const NodeIterator<OutputType0, Traits0, Traits1>& it) const { return !(it < *this); }
andrewm@0: 	
andrewm@0:     template <class OutputType0, class Traits0, class Traits1>
andrewm@0:     bool operator >= (const NodeIterator<OutputType0, Traits0, Traits1>& it) const { return !(*this < it); }	
andrewm@0: 	
andrewm@0: 	// ***** Special Methods *****
andrewm@0: 	
andrewm@0: 	// Return the offset within the buffer for this iterator's current location
andrewm@0: 	// Can be used with at() or operator[], and can be used to compare relative locations
andrewm@0: 	// of two iterators, even if they don't refer to the same buffer
andrewm@0: 	
andrewm@0: 	size_type index() const {
andrewm@0: 		return (size_type)(*this - m_buff->begin() + m_buff->firstSampleIndex_);
andrewm@0: 	}
andrewm@0: 	
andrewm@0: 	// Return the timestamp associated with the sample this iterator points to
andrewm@0: 	
andrewm@0: 	timestamp_type timestamp() const { return m_buff->timestampAt(index()); }
andrewm@0: 	
andrewm@0: 	// Tells us whether the index points to a valid place in the buffer.
andrewm@0: 	// TODO: make sure this is right
andrewm@0: 	// bool isValid() const { return (index() >= m_buff->beginIndex() && index() <= (m_buff->endIndex() - 1)); }	
andrewm@0: };
andrewm@0: 
andrewm@0: /*
andrewm@0:  * NodeReverseIterator
andrewm@0:  *
andrewm@0:  * Adapter for reverse iterators on Node classes, preserving some of the
andrewm@0:  * special behavior the iterators implement.
andrewm@0:  */
andrewm@0: 
andrewm@0: template <typename T>
andrewm@0: struct NodeReverseIterator : public boost::reverse_iterator<T> {
andrewm@0: 	NodeReverseIterator() {}
andrewm@0: 	explicit NodeReverseIterator(T baseIt) : boost::reverse_iterator<T>(baseIt) {}
andrewm@0: 	
andrewm@0: 	typedef typename boost::reverse_iterator<T>::base_type::size_type size_type;
andrewm@0: 
andrewm@0: 	size_type index() const { return boost::prior(this->base_reference()).index(); }
andrewm@0: 	timestamp_type timestamp() const { return boost::prior(this->base_reference()).timestamp(); }
andrewm@0: };
andrewm@0: 
andrewm@0: /*
andrewm@0:  * NodeInterpolatedIterator
andrewm@0:  *
andrewm@0:  * Extends the iterator concept to fractional indices, using linear interpolation to return
andrewm@0:  * values and timestamps.  This is always a const iterator class.
andrewm@0:  */
andrewm@0: 
andrewm@0: template<typename OutputType, typename Traits>
andrewm@0: struct NodeInterpolatedIterator :
andrewm@0: 	public boost::iterator<
andrewm@0: 	std::random_access_iterator_tag,
andrewm@0: 	typename Traits::value_type,
andrewm@0: 	typename Traits::difference_type,
andrewm@0: 	typename Traits::pointer,
andrewm@0: 	typename Traits::reference>
andrewm@0: {
andrewm@0: 	typedef NodeInterpolatedIterator<OutputType,Traits> self_type;
andrewm@0: 	
andrewm@0:     typedef boost::iterator<
andrewm@0: 		std::random_access_iterator_tag,
andrewm@0: 		typename Traits::value_type,
andrewm@0: 		typename Traits::difference_type,
andrewm@0: 		typename Traits::pointer,
andrewm@0: 		typename Traits::reference> base_iterator;
andrewm@0: 	
andrewm@0: 	typedef typename Traits::size_type size_type;
andrewm@0: 	typedef typename base_iterator::value_type value_type;
andrewm@0: 	typedef typename base_iterator::pointer pointer;
andrewm@0: 	typedef typename base_iterator::reference reference;	
andrewm@0: 	
andrewm@0: 	// ***** Member Variables *****
andrewm@0: 	
andrewm@0: 	// Reference to the buffer this iterator indexes
andrewm@0: 	Node<OutputType>* m_buff;
andrewm@0: 	
andrewm@0: 	// Index location within the buffer
andrewm@0: 	double m_index;
andrewm@0: 	
andrewm@0: 	// Step size for ++ and similar operators
andrewm@0: 	double m_step;
andrewm@0: 	
andrewm@0: 	// ***** Constructors *****
andrewm@0: 	
andrewm@0: 	// Default (empty) constructor
andrewm@0: 	NodeInterpolatedIterator() : m_buff(0), m_index(0.0), m_step(1.0) {}
andrewm@0: 	
andrewm@0: 	// Constructor that should be used primarily by the Node class itself
andrewm@0: 	NodeInterpolatedIterator(Node<OutputType>* buff, double index, double stepSize) 
andrewm@0: 	: m_buff(buff), m_index(index), m_step(stepSize) {}
andrewm@0: 	
andrewm@0: 	// Copy constructor
andrewm@0: 	NodeInterpolatedIterator(const self_type& obj) : m_buff(obj.m_buff), m_index(obj.m_index), m_step(obj.m_step) {}
andrewm@0: 	
andrewm@0: 	// ***** Operators *****
andrewm@0: 	//
andrewm@0: 	// Modeled on STL iterators, but using fractional indices.  This class should be considered a sort of random access,
andrewm@0: 	// bidirectional iterator.  
andrewm@0: 
andrewm@0:     NodeInterpolatedIterator& operator = (const self_type& it) {
andrewm@0:         if (this == &it)
andrewm@0:             return *this;
andrewm@0:         m_buff = it.m_buff;
andrewm@0:         m_index = it.m_index;
andrewm@0: 		m_step = it.m_step;
andrewm@0:         return *this;
andrewm@0:     }	
andrewm@0: 	
andrewm@0: 	// Dereferencing operators.  Like the non-interpolated version of this iterator, it will calculate the values as needed.
andrewm@0: 	// This happens within the operator[] method of Node, rather than in this class itself.
andrewm@0: 	
andrewm@0:     value_type operator * () const { return m_buff->interpolate(m_index); }
andrewm@0: 	pointer operator -> () const { return &(operator*()); }
andrewm@0: 	
andrewm@0: 	// Difference of two iterators (return the difference in indices)
andrewm@0:     double operator - (const self_type& it) const { return m_index - it.m_index; }
andrewm@0: 	
andrewm@0: 	// Increment and decrement are typically integer operators.  We define their behavior here to change the index by a predetermined
andrewm@0: 	// step size, set at construction but changeable.
andrewm@0: 	
andrewm@0:     self_type& operator ++ () {			// ++it
andrewm@0: 		m_index += m_step;
andrewm@0: 		return *this;
andrewm@0: 	}
andrewm@0: 	self_type operator ++ (int) {		// it++
andrewm@0: 		self_type tmp = *this;
andrewm@0: 		m_index += m_step;
andrewm@0: 		return tmp;
andrewm@0: 	}
andrewm@0: 	self_type& operator -- () {			// --it
andrewm@0: 		m_index -= m_step;
andrewm@0: 		return *this;
andrewm@0: 	}
andrewm@0: 	self_type operator -- (int) {		// it--
andrewm@0: 		self_type tmp = *this;
andrewm@0: 		m_index -= m_step;
andrewm@0: 		return tmp;
andrewm@0: 	}
andrewm@0: 	
andrewm@0: 	// These methods change the iterator location by a fractional amount.  Notice that this is NOT scaled by m_step.
andrewm@0:     self_type& operator += (double n) {		// it += n
andrewm@0: 		m_index += n;
andrewm@0:         return *this;
andrewm@0:     }	
andrewm@0:     self_type& operator -= (double n) {		// it -= n
andrewm@0: 		m_index -= n;
andrewm@0:         return *this;
andrewm@0:     }		
andrewm@0: 	
andrewm@0: 	self_type operator + (double n) const { return NodeInterpolatedIterator<OutputType,Traits>(*this) += n; }
andrewm@0: 	self_type operator - (double n) const { return NodeInterpolatedIterator<OutputType,Traits>(*this) -= n; }
andrewm@0: 	
andrewm@0: 	reference operator [] (double n) const { return *(*this + n); }	
andrewm@0: 	
andrewm@0: 	
andrewm@0: 	// ***** Comparisons *****
andrewm@0: 	//
andrewm@0: 	// The comparison behavior is the same as for NodeIterator: even if two iterators point to different buffers,
andrewm@0: 	// they can be compared on the basis of the indices.  Of course, this is only meaningful if the two buffers are synchronized
andrewm@0: 	// in time.
andrewm@0: 	
andrewm@0: 	template<class OutputType0, class Traits0>
andrewm@0:     bool operator == (const NodeInterpolatedIterator<OutputType0,Traits0>& it) const { return m_index == it.m_index; }
andrewm@0: 	
andrewm@0: 	template<class OutputType0, class Traits0>
andrewm@0:     bool operator != (const NodeInterpolatedIterator<OutputType0, Traits0>& it) const { return m_index != it.m_index; }
andrewm@0: 
andrewm@0: 	template<class OutputType0, class Traits0>	
andrewm@0: 	bool operator < (const NodeInterpolatedIterator<OutputType0, Traits0>& it) const { return m_index < it.m_index; }
andrewm@0: 	
andrewm@0: 	template<class OutputType0, class Traits0>	
andrewm@0: 	bool operator > (const NodeInterpolatedIterator<OutputType0, Traits0>& it) const { return m_index > it.m_index; }
andrewm@0: 	
andrewm@0: 	template<class OutputType0, class Traits0>	
andrewm@0: 	bool operator <= (const NodeInterpolatedIterator<OutputType0, Traits0>& it) const { return !(it < *this); }
andrewm@0: 	
andrewm@0: 	template<class OutputType0, class Traits0>	
andrewm@0: 	bool operator >= (const NodeInterpolatedIterator<OutputType0, Traits0>& it) const { return !(*this < it); }
andrewm@0: 	
andrewm@0: 	// We can also compare interpolated and non-interpolated iterators.
andrewm@0: 	
andrewm@0:     template <class OutputType0, class Traits0, class Traits1>
andrewm@0:     bool operator == (const NodeIterator<OutputType0, Traits0, Traits1>& it) const { return m_index == (double)it.index(); }	
andrewm@0: 	
andrewm@0:     template <class OutputType0, class Traits0, class Traits1>
andrewm@0:     bool operator != (const NodeIterator<OutputType0, Traits0, Traits1>& it) const { return m_index != (double)it.index(); }	
andrewm@0: 	
andrewm@0:     template <class OutputType0, class Traits0, class Traits1>
andrewm@0:     bool operator < (const NodeIterator<OutputType0, Traits0, Traits1>& it) const { return m_index < (double)it.index(); }	
andrewm@0: 	
andrewm@0:     template <class OutputType0, class Traits0, class Traits1>
andrewm@0:     bool operator > (const NodeIterator<OutputType0, Traits0, Traits1>& it) const { return m_index > (double)it.index(); }	
andrewm@0: 	
andrewm@0: 	template <class OutputType0, class Traits0, class Traits1>
andrewm@0:     bool operator <= (const NodeIterator<OutputType0, Traits0, Traits1>& it) const { return m_index <= (double)it.index(); }	
andrewm@0: 	
andrewm@0:     template <class OutputType0, class Traits0, class Traits1>
andrewm@0:     bool operator >= (const NodeIterator<OutputType0, Traits0, Traits1>& it) const { return m_index >= (double)it.index(); }	
andrewm@0: 	
andrewm@0: 	// ***** Special Methods *****
andrewm@0: 	
andrewm@0: 	// Round a fractional index up, down, or to the nearest integer
andrewm@0: 	
andrewm@0:     self_type& roundDown() {
andrewm@0: 		m_index = floor(m_index);	
andrewm@0: 		return *this;
andrewm@0: 	}	
andrewm@0:     self_type& roundUp() {
andrewm@0: 		m_index = ceil(m_index);	
andrewm@0: 		return *this;
andrewm@0: 	}	
andrewm@0:     self_type& round() {
andrewm@0: 		m_index = floor(m_index + 0.5);	
andrewm@0: 		return *this;
andrewm@0: 	}	
andrewm@0: 	
andrewm@0: 	// Increment the iterator by a difference in time rather than a difference in index.  This is less efficient to
andrewm@0: 	// compute, but can be useful for buffers whose samples are not regularly spaced in time.
andrewm@0: 	
andrewm@0: 	self_type& incrementTime(timestamp_diff_type ts) {
andrewm@0: 		if(ts > 0) {
andrewm@0: 			size_type afterIndex = (size_type)ceil(m_index);
andrewm@0: 			if(afterIndex >= m_buff->endIndex()) {
andrewm@0: 				m_index = (double)m_buff->endIndex();
andrewm@0: 				return *this;
andrewm@0: 			}
andrewm@0: 			timestamp_type target = timestamp() + ts;
andrewm@0: 			timestamp_type after = m_buff->timestampAt(afterIndex);
andrewm@0: 			
andrewm@0: 			// First of all, find the first integer index with a timestamp greater than our new target time.
andrewm@0: 			while(after < target) {
andrewm@0: 				afterIndex++;
andrewm@0: 				if(afterIndex >= m_buff->endIndex()) {
andrewm@0: 					m_index = (double)m_buff->endIndex();
andrewm@0: 					return *this;
andrewm@0: 				}				
andrewm@0: 				after = m_buff->timestampAt(afterIndex);
andrewm@0: 			}
andrewm@0: 			
andrewm@0: 			// Then find the timestamp immediately before that.  We'll interpolate between these two to get
andrewm@0: 			// the adjusted index.
andrewm@0: 			timestamp_type before = m_buff->timestampAt(afterIndex-1);
andrewm@0: 			m_index = ((target - before) / (after - before)) + (double)(afterIndex - 1);
andrewm@0: 		}
andrewm@0: 		else if(ts < 0) {
andrewm@0: 			size_type beforeIndex = (size_type)floor(m_index);
andrewm@0: 			if(beforeIndex < m_buff->beginIndex()) {
andrewm@0: 				m_index = (double)m_buff->beginIndex()-1.0;
andrewm@0: 				return *this;
andrewm@0: 			}
andrewm@0: 			timestamp_type target = timestamp() + ts;
andrewm@0: 			timestamp_type before = m_buff->timestampAt(beforeIndex);
andrewm@0: 			
andrewm@0: 			// Find the first integer index with a timestamp less than our new target time.
andrewm@0: 			while(before > target) {
andrewm@0: 				beforeIndex--;
andrewm@0: 				if(beforeIndex < m_buff->beginIndex()) {
andrewm@0: 					m_index = (double)m_buff->beginIndex()-1.0;
andrewm@0: 					return *this;
andrewm@0: 				}
andrewm@0: 				before = m_buff->timestampAt(beforeIndex);
andrewm@0: 			}
andrewm@0: 			
andrewm@0: 			// Now find the timestamp immediately after that.  Interpolated to get the adjusted index.
andrewm@0: 			timestamp_type after = m_buff->timestampAt(beforeIndex+1);
andrewm@0: 			m_index = ((target - before)/(after - before)) + (double)beforeIndex;
andrewm@0: 		}
andrewm@0: 		// if(ts == 0), do nothing
andrewm@0: 		return *this;
andrewm@0: 	}
andrewm@0: 	
andrewm@0: 	
andrewm@0: 	// Return (or change) the step size
andrewm@0: 	double& step() { return m_step; }
andrewm@0: 	
andrewm@0: 	// Return the index within the buffer.  The index is an always-increasing sample number (which means that as the
andrewm@0: 	// buffer fills, an index will continue to point to the same piece of data until that data is overwritten, at which
andrewm@0: 	// point that index is no longer valid for accessing the buffer at all.)
andrewm@0: 	double index() const { return m_index; }
andrewm@0: 	
andrewm@0: 	// Return the timestamp for this particular location in the buffer (using linear interpolation).
andrewm@0: 	timestamp_type timestamp() const { return m_buff->interpolatedTimestampAt(m_index); }
andrewm@0: 	
andrewm@0: 	// Tells us whether the index points to a valid place in the buffer.
andrewm@0: 	bool isValid() const { return (m_index >= m_buff->beginIndex() && m_index <= (m_buff->endIndex() - 1)); }
andrewm@0: };
andrewm@0: 
andrewm@0: /*
andrewm@0:  * NodeBase
andrewm@0:  *
andrewm@0:  * Abstract class that implements common functionality for all Node data types.
andrewm@0:  *
andrewm@0:  */
andrewm@0:  
andrewm@0: class NodeBase : public TriggerSource, public TriggerDestination {	
andrewm@0: public:
andrewm@0: 	typedef uint32_t size_type;
andrewm@0: 	
andrewm@0: 	// ***** Constructors *****
andrewm@0: 	
andrewm@0: 	// Default constructor
andrewm@0: 	NodeBase() {}
andrewm@0: 	
andrewm@0: 	// Copy constructor: can't copy the mutexes
andrewm@0: 	NodeBase(NodeBase const& obj) {}
andrewm@0: 	
andrewm@0: 	NodeBase& operator= (NodeBase const& obj) {
andrewm@0: 		//listeners_ = obj.listeners_;
andrewm@0: 		return *this;
andrewm@0: 	}
andrewm@0: 	
andrewm@0: 	// ***** Destructor *****
andrewm@0: 	
andrewm@0: 	virtual ~NodeBase() {
andrewm@0: 		//clearTriggerSources();
andrewm@0: 	}
andrewm@0: 	
andrewm@0: 	// ***** Modifiers *****
andrewm@0: 	
andrewm@0: 	virtual void clear() = 0;									
andrewm@0: 	//virtual void insertMissing(timestamp_type timestamp) = 0;	
andrewm@0: 	
andrewm@0: 	// ***** Listener Methods *****
andrewm@0: 	//
andrewm@0: 	// We need to keep the buffers of all connected units in sync.  That means any Source or Filter needs to know what its output
andrewm@0: 	// connects to.  That functionality is accomplished by "listeners": any time a new sample is added to the buffer, the listeners
andrewm@0: 	// are notified with a corresponding timestamp.  The latter is to ensure that a buffer does not respond to notifications from multiple
andrewm@0: 	// inputs for the same data point.
andrewm@0: 	
andrewm@0: 	/*void registerListener(NodeBase* listener) {
andrewm@0: 		if(listener != 0) {
andrewm@0: 			listenerAccessMutex_.lock();
andrewm@0: 			listeners_.insert(listener);
andrewm@0: 			listenerAccessMutex_.unlock();
andrewm@0: 		}
andrewm@0: 	}
andrewm@0: 	void unregisterListener(NodeBase* listener) {
andrewm@0: 		listenerAccessMutex_.lock();
andrewm@0: 		listeners_.erase(listener);
andrewm@0: 		listenerAccessMutex_.unlock();
andrewm@0: 	}
andrewm@0: 	void clearListeners() {
andrewm@0: 		listenerAccessMutex_.lock();
andrewm@0: 		listeners_.clear();
andrewm@0: 		listenerAccessMutex_.unlock();
andrewm@0: 	}
andrewm@0: protected:
andrewm@0: 	// Tell all our listeners about a new data point with the given timestamp
andrewm@0: 	void notifyListenersOfInsert(timestamp_type timestamp) {
andrewm@0: 		std::set<NodeBase*>::iterator it;
andrewm@0: 		
andrewm@0: 		listenerAccessMutex_.lock();
andrewm@0: 		for(it = listeners_.begin(); it != listeners_.end(); it++)
andrewm@0: 			(*it)->insertMissing(timestamp);
andrewm@0: 		listenerAccessMutex_.unlock();
andrewm@0: 	}
andrewm@0: 	// Tell all our listeners that the buffer has cleared
andrewm@0: 	void notifyListenersOfClear() {
andrewm@0: 		std::set<NodeBase*>::iterator it;
andrewm@0: 		
andrewm@0: 		listenerAccessMutex_.lock();
andrewm@0: 		for(it = listeners_.begin(); it != listeners_.end(); it++)
andrewm@0: 			(*it)->clear();
andrewm@0: 		listenerAccessMutex_.unlock();
andrewm@0: 	}*/
andrewm@0: 	
andrewm@0: public:	
andrewm@0: 	// ***** Tree-Parsing Methods *****
andrewm@0: 	//
andrewm@0: 	// Sometimes we want to find out properties of the initial data source, regardless of what filters it's passed through.  These virtual
andrewm@0: 	// methods should be implemented differently by Source and Filter classes.
andrewm@0: 	
andrewm@0: 	//virtual SourceBase& source() = 0;		// Return the source at the top of the tree for this unit
andrewm@0: 	
andrewm@0: 	// ***** Mutex Methods *****
andrewm@0: 	//
andrewm@0: 	// These methods should be used to acquire a lock whenever a process wants to read values from the buffer.  This would, for example,
andrewm@0: 	// allow iteration over the contents of the buffer without worrying that the contents will change in the course of the iteration.
andrewm@0: 	
andrewm@0: 	void lock_mutex() { bufferAccessMutex_.enter(); }
andrewm@0: 	bool try_lock_mutex() { return bufferAccessMutex_.tryEnter(); }
andrewm@0: 	void unlock_mutex() { bufferAccessMutex_.exit(); }
andrewm@0: 	
andrewm@0: 	// ***** Circular Buffer (STL) Methods *****
andrewm@0: 	//
andrewm@0: 	// Certain STL methods (and related queries) that do not depend on the specific data type of the buffer should
andrewm@0: 	// be available to any object with a NodeBase reference.
andrewm@0: 	
andrewm@0: 	virtual size_type size() = 0;				// Size: how many elements are currently in the buffer
andrewm@0: 	virtual bool empty() = 0;
andrewm@0: 	virtual bool full() = 0;
andrewm@0: 	virtual size_type reserve() = 0;			// Reserve: how many elements are left before the buffer is full
andrewm@0: 	virtual size_type capacity() const = 0;			// Capacity: how many elements could be in the buffer
andrewm@0: 	
andrewm@0: 	virtual size_type beginIndex() = 0;			// Index of the first sample we still have in the buffer
andrewm@0: 	virtual size_type endIndex() = 0;			// Index just past the end of the buffer	
andrewm@0: 	
andrewm@0: 	// ***** Timestamp Methods *****
andrewm@0: 	//
andrewm@0: 	// Every sample is tagged with a timestamp.  We don't necessarily need to know the type of the sample to retrieve its
andrewm@0: 	// associated timestamp.  However, we DO need to know the type in order to return an iterator.
andrewm@0: 	
andrewm@0: 	virtual timestamp_type timestampAt(size_type index) = 0;
andrewm@0: 	virtual timestamp_type latestTimestamp() = 0;
andrewm@0: 	virtual timestamp_type earliestTimestamp() = 0;
andrewm@0: 	
andrewm@0: 	virtual size_type indexNearestTo(timestamp_type t) = 0;
andrewm@0: 	virtual size_type indexNearestBefore(timestamp_type t) = 0;
andrewm@0: 	virtual size_type indexNearestAfter(timestamp_type t) = 0;	
andrewm@0: 	
andrewm@0: 	// ***** Member Variables *****
andrewm@0: protected:
andrewm@0: 	// A collection of the units that are listening for updates on this unit.
andrewm@0: 	//std::set<NodeBase*> listeners_;
andrewm@0: 
andrewm@0: 	// This mutex protects access to the underlying buffer.  It is locked every time a sample is written to the buffer,
andrewm@0: 	// and external systems reading values from the buffer should also acquire at least a shared lock.
andrewm@0: 	CriticalSection bufferAccessMutex_;
andrewm@0: 	
andrewm@0: 	// This mutex protects the list of listeners.  It prevents a listener from being added or removed while a notification
andrewm@0: 	// is in progress.
andrewm@0: 	//boost::mutex listenerAccessMutex_;
andrewm@0: 	
andrewm@0: 	// Keep an internal registry of who we've asked to send us triggers.  It's important to keep
andrewm@0: 	// a list of these so that when this object is destroyed, all triggers are automatically unregistered.
andrewm@0: 	//std::set<NodeBase*> triggerSources_;	
andrewm@0: 	
andrewm@0: 	// This list tracks the destinations we are *sending* triggers to (as opposed to the sources we're receiving from above)
andrewm@0: 	//std::set<NodeBase*> triggerDestinations_;	
andrewm@0: };
andrewm@0: 
andrewm@0: /*
andrewm@0:  * NodeNonInterpolating
andrewm@0:  *
andrewm@0:  * This class handles all functionality for a Node of a specific data type EXCEPT:
andrewm@0:  *   -- Interpolating accessors (for data types that support interpolation, use the more common Node subclass)
andrewm@0:  *   -- triggerReceived() which should be implemented by a specific subclass.
andrewm@0:  */
andrewm@0: 
andrewm@0: template<typename OutputType>
andrewm@0: class NodeNonInterpolating : public NodeBase {
andrewm@0: public:	
andrewm@0: 	// Useful type shorthands.  See <boost/circular_buffer.hpp> for details.
andrewm@47:     typedef typename boost::container::allocator_traits<std::allocator<OutputType> > Alloc;
andrewm@47:     
andrewm@0: 	typedef typename boost::circular_buffer<OutputType,Alloc>::value_type value_type;
andrewm@0: 	typedef typename boost::circular_buffer<OutputType,Alloc>::pointer pointer;
andrewm@0: 	typedef typename boost::circular_buffer<OutputType,Alloc>::const_pointer const_pointer;
andrewm@0: 	typedef typename boost::circular_buffer<OutputType,Alloc>::reference reference;
andrewm@0: 	typedef typename boost::circular_buffer<OutputType,Alloc>::const_reference const_reference;
andrewm@0: 	typedef typename boost::circular_buffer<OutputType,Alloc>::difference_type difference_type;
andrewm@0: 	//typedef typename boost::circular_buffer<OutputType,Alloc>::size_type size_type;
andrewm@0: 	typedef typename boost::circular_buffer<OutputType,Alloc>::capacity_type capacity_type;
andrewm@0: 	typedef typename boost::circular_buffer<OutputType,Alloc>::array_range array_range;
andrewm@0: 	typedef typename boost::circular_buffer<OutputType,Alloc>::const_array_range const_array_range;
andrewm@20: 	typedef typename boost::circular_buffer<OutputType,Alloc>::param_value_type return_value_type;
andrewm@0: 	
andrewm@0: 	// We only support const iterators.  (Modifying data in the buffer is restricted to only a few specialized instances.)
andrewm@0: 	
andrewm@0: 	typedef NodeIterator<OutputType, boost::cb_details::const_traits<Alloc>,
andrewm@0: 											 boost::cb_details::nonconst_traits<Alloc> > const_iterator;
andrewm@0: 	typedef const_iterator iterator;
andrewm@0: 	typedef NodeReverseIterator<const_iterator> const_reverse_iterator;
andrewm@0: 	typedef const_reverse_iterator reverse_iterator;
andrewm@0: 	
andrewm@0: 	template<class O, class T, class NCT> friend struct NodeIterator;
andrewm@0: 
andrewm@0: 	// ***** Constructors *****
andrewm@0: 	
andrewm@0: 	//Node() : buffer_(0), insertMissingLastTimestamp_(0), numSamples_(0), firstSampleIndex_(0) {}	
andrewm@0: 	
andrewm@0: 	// Recommended constructor: specify the capacity in samples
andrewm@0: 	explicit NodeNonInterpolating(capacity_type capacity) : insertMissingLastTimestamp_(0), buffer_(0), numSamples_(0), firstSampleIndex_(0) {
andrewm@0: 		buffer_ = new boost::circular_buffer<OutputType>(capacity);
andrewm@0: 		timestamps_ = new boost::circular_buffer<timestamp_type>(capacity);
andrewm@0: 	}	
andrewm@0: 	
andrewm@0: 	// Copy constructor
andrewm@0: 	NodeNonInterpolating(const NodeNonInterpolating<OutputType>& obj) : numSamples_(obj.numSamples_), firstSampleIndex_(obj.firstSampleIndex_) {
andrewm@0: 		if(obj.buffer_ != 0)
andrewm@0: 			this->buffer_ = new boost::circular_buffer<OutputType>(*obj.buffer_);
andrewm@0: 		else
andrewm@0: 			this->buffer_ = 0;
andrewm@0: 		if(obj.timestamps_ != 0)
andrewm@0: 			timestamps_ = new boost::circular_buffer<timestamp_type>(*obj.timestamps_);
andrewm@0: 		else
andrewm@0: 			this->timestamps_ = 0;
andrewm@0: 	}
andrewm@0: 
andrewm@0: 	// ***** Destructor *****
andrewm@0: 	
andrewm@0: 	virtual ~NodeNonInterpolating() {
andrewm@0: 		delete buffer_;
andrewm@0: 		delete timestamps_;
andrewm@0: 	}
andrewm@0: 	
andrewm@0: 	// ***** Circular Buffer (STL) Methods *****
andrewm@0: 	//
andrewm@0: 	// In general we support const methods accessing the contents of the buffer, but only in limited cases can the buffer
andrewm@0: 	// contents be modified.  Source objects allow inserting objects into the buffer, but Filters require the buffer to contain
andrewm@0: 	// either the result of the evaluator function or a "missing" value.
andrewm@0: 	
andrewm@0: 	// ***** Accessors *****
andrewm@0: 	
andrewm@0: 	const_iterator begin() { return const_iterator(this, buffer_->begin()); }
andrewm@0: 	const_iterator end() { return const_iterator(this, buffer_->end()); }
andrewm@0: 	const_reverse_iterator rbegin() { return const_reverse_iterator(end()); }
andrewm@0: 	const_reverse_iterator rend() { return const_reverse_iterator(begin()); }
andrewm@0: 	
andrewm@0: 	const_iterator iteratorAtIndex(size_type index) { return const_iterator(this, buffer_->begin()) + (index - firstSampleIndex_); }
andrewm@0: 	const_reverse_iterator riteratorAtIndex(size_type index) { return const_reverse_iterator(iteratorAtIndex(index+1)); }
andrewm@0: 	
andrewm@0: 	return_value_type operator [] (size_type index) { return (*(this->buffer_))[index-this->firstSampleIndex_]; }
andrewm@0: 	return_value_type at(size_type index) { return this->buffer_->at(index-this->firstSampleIndex_); }
andrewm@0: 	return_value_type front() { return this->buffer_->front(); }
andrewm@0: 	return_value_type back() { return this->buffer_->back(); }
andrewm@0: 	
andrewm@0: 	// Two more convenience methods to avoid confusion about what front and back mean!
andrewm@0: 	return_value_type earliest() { return this->buffer_->front(); }
andrewm@0: 	return_value_type latest() { return this->buffer_->back(); }	
andrewm@0: 	
andrewm@0: 	// In the following methods, check whether the value is missing and calculate it as necessary
andrewm@0: 	// These methods return a value_type (i.e. not a reference, can't be used to modify the buffer.)
andrewm@0: 	// However, they internally make use of modifying calls in order to update "missing" values.
andrewm@0: 	
andrewm@0: 	/*return_value_type operator [] (size_type index) {
andrewm@0: 		return_value_type val = (*buffer_)[index-firstSampleIndex_];
andrewm@0: 		if(!missing_value<OutputType>::isMissing(val))
andrewm@0: 			return val;
andrewm@0: 		return ((*buffer_)[index-firstSampleIndex_] = evaluate(index));
andrewm@0: 	}
andrewm@0: 	return_value_type at(size_type index) {
andrewm@0: 		return_value_type val = buffer_->at(index-firstSampleIndex_);
andrewm@0: 		if(!missing_value<OutputType>::isMissing(val))
andrewm@0: 			return val;
andrewm@0: 		return (buffer_->at(index-firstSampleIndex_) = evaluate(index));
andrewm@0: 	}
andrewm@0: 	return_value_type front() {
andrewm@0: 		return_value_type val = buffer_->front();
andrewm@0: 		if(!missing_value<OutputType>::isMissing(val))
andrewm@0: 			return val;
andrewm@0: 		return (buffer_->front() = evaluate(firstSampleIndex_));
andrewm@0: 	}
andrewm@0: 	return_value_type back() {
andrewm@0: 		return_value_type val = buffer_->back();
andrewm@0: 		if(!missing_value<OutputType>::isMissing(val) && buffer_->size() > 0)
andrewm@0: 			return val;
andrewm@0: 		return (buffer_->back() = evaluate(buffer_->size() - 1 + firstSampleIndex_));
andrewm@0: 	}*/
andrewm@0: 	
andrewm@0: 	size_type size() { return buffer_->size(); }					// Size: how many elements are currently in the buffer
andrewm@0: 	bool empty() { return buffer_->empty(); }
andrewm@0: 	bool full() { return buffer_->full(); }
andrewm@0: 	size_type reserve() { return buffer_->reserve(); }				// Reserve: how many elements are left before the buffer is full
andrewm@0: 	size_type capacity() const { return buffer_->capacity(); }		// Capacity: how many elements could be in the buffer
andrewm@0: 	
andrewm@0: 	size_type beginIndex() { return firstSampleIndex_; }					// Index of the first sample we still have in the buffer
andrewm@0: 	size_type endIndex() { return firstSampleIndex_ + buffer_->size(); }	// Index just past the end of the buffer
andrewm@0: 	
andrewm@0: 	// ***** Modifiers *****
andrewm@0: 	
andrewm@0: 	// Clear all stored samples and timestamps
andrewm@0: 	void clear() {
andrewm@0: 		bufferAccessMutex_.enter();
andrewm@0: 		timestamps_->clear();
andrewm@0: 		buffer_->clear();
andrewm@0: 		numSamples_ = firstSampleIndex_ = 0;
andrewm@0: 		bufferAccessMutex_.exit();
andrewm@0: 		
andrewm@0: 		//notifyListenersOfClear();
andrewm@0: 	}
andrewm@0: 	
andrewm@0: 	// Insert a new item into the buffer
andrewm@0: 	void insert(const OutputType& item, timestamp_type timestamp) {
andrewm@0: 		this->bufferAccessMutex_.enter();
andrewm@0: 		if(this->buffer_->full())
andrewm@0: 			this->firstSampleIndex_++;
andrewm@0: 		this->timestamps_->push_back(timestamp);
andrewm@0: 		this->buffer_->push_back(item);
andrewm@0: 		this->numSamples_++;
andrewm@0: 		this->bufferAccessMutex_.exit();
andrewm@0: 		
andrewm@0: 		// Notify anyone who's listening for a trigger
andrewm@0: 		this->sendTrigger(timestamp);
andrewm@0: 	}
andrewm@0: 	
andrewm@0: 	// Insert a "missing" item into the buffer.  This is really for the Filter subclasses, but we should provide an implementation
andrewm@0: 	/*void insertMissing(timestamp_type timestamp) {		
andrewm@0: 		if(timestamp == insertMissingLastTimestamp_)
andrewm@0: 			return;
andrewm@0: 		this->bufferAccessMutex_.lock();
andrewm@0: 		if(this->buffer_->full())
andrewm@0: 			this->firstSampleIndex_++;		
andrewm@0: 		this->timestamps_->push_back(timestamp);
andrewm@0: 		this->buffer_->push_back(missing_value<OutputType>::missing());
andrewm@0: 		this->numSamples_++;
andrewm@0: 		this->bufferAccessMutex_.unlock();
andrewm@0: 		
andrewm@0: 		this->insertMissingLastTimestamp_ = timestamp;
andrewm@0: 		this->notifyListenersOfInsert(timestamp);
andrewm@0: 	}	*/
andrewm@0: 	
andrewm@0: protected:
andrewm@0: 	// Subclasses are allowed to change the values stored in their buffers.  Give this a different
andrewm@0: 	// name to avoid confusion with the behavior of [] and at(), which call evaluate() if the sample
andrewm@0: 	// is missing.
andrewm@0: 	
andrewm@0: 	reference rawValueAt(size_type index) { return (*buffer_)[index-firstSampleIndex_]; }
andrewm@0: 	
andrewm@0: public:
andrewm@0: 	// ***** Timestamp Methods *****
andrewm@0: 	//
andrewm@0: 	// Every sample is tagged with a timestamp.  The Filter classes will look up the chain to find the timestamp associated
andrewm@0: 	// with the Source of any particular sample.  We also support methods to return an iterator to a piece of data most closely
andrewm@0: 	// matching a given timestamp.
andrewm@0: 	
andrewm@0: 	timestamp_type timestampAt(size_type index) { return timestamps_->at(index-this->firstSampleIndex_); }
andrewm@0: 	timestamp_type latestTimestamp() { return timestamps_->back(); }
andrewm@0: 	timestamp_type earliestTimestamp() { return timestamps_->front(); }
andrewm@0: 	
andrewm@0: 	size_type indexNearestBefore(timestamp_type t) {
andrewm@0: 		boost::circular_buffer<timestamp_type>::iterator it = std::find_if(timestamps_->begin(), timestamps_->end(), t < boost::lambda::_1);
andrewm@0: 		if(it == timestamps_->end())
andrewm@0: 			return timestamps_->size()-1+this->firstSampleIndex_;		
andrewm@0: 		if(it - timestamps_->begin() == 0)
andrewm@0: 			return this->firstSampleIndex_;
andrewm@0: 		return (size_type)((--it) - timestamps_->begin()) + this->firstSampleIndex_; 
andrewm@0: 	}
andrewm@0: 	size_type indexNearestAfter(timestamp_type t) {
andrewm@0: 		boost::circular_buffer<timestamp_type>::iterator it = std::find_if(timestamps_->begin(), timestamps_->end(), t < boost::lambda::_1);
andrewm@0: 		return std::min<size_type>((it - timestamps_->begin()), timestamps_->size()-1) + this->firstSampleIndex_;
andrewm@0: 	}
andrewm@0: 	size_type indexNearestTo(timestamp_type t) {
andrewm@0: 		boost::circular_buffer<timestamp_type>::iterator it = std::find_if(timestamps_->begin(), timestamps_->end(), t < boost::lambda::_1);
andrewm@0: 		if(it == timestamps_->end())
andrewm@0: 			return timestamps_->size()-1+this->firstSampleIndex_;
andrewm@0: 		if(it - timestamps_->begin() == 0)
andrewm@0: 			return this->firstSampleIndex_;
andrewm@0: 		timestamp_diff_type after = *it - t;		// Calculate the distance between the desired timestamp and the before/after values,
andrewm@0: 		timestamp_diff_type before = t - *(it-1);	// then return whichever index gets closer to the target.
andrewm@0: 		if(after < before)
andrewm@0: 			return (size_type)(it - timestamps_->begin()) + this->firstSampleIndex_;
andrewm@0: 		return (size_type)((--it) - timestamps_->begin()) + this->firstSampleIndex_;
andrewm@0: 	}	
andrewm@0: 	
andrewm@0: 	const_iterator nearestTo(timestamp_type t) { return begin() + (difference_type)indexNearestTo(t); }
andrewm@0: 	const_iterator nearestBefore(timestamp_type t) { return begin() + (difference_type)indexNearestBefore(t); }
andrewm@0: 	const_iterator nearestAfter(timestamp_type t) { return begin() + (difference_type)indexNearestAfter(t); }
andrewm@0: 	
andrewm@0: 	const_reverse_iterator rnearestTo(timestamp_type t) { return rend() - (difference_type)indexNearestTo(t); }
andrewm@0: 	const_reverse_iterator rnearestBefore(timestamp_type t) { return rend() - (difference_type)indexNearestBefore(t); }
andrewm@0: 	const_reverse_iterator rnearestAfter(timestamp_type t) { return rend() - (difference_type)indexNearestAfter(t); }
andrewm@0: 	
andrewm@0: private:
andrewm@0: 	// Calculate the actual value of one sample.  Behavior of this method will be different for Source and Filter types.
andrewm@0: 	// virtual OutputType evaluate(size_type index) = 0;
andrewm@0: 	
andrewm@0: 	timestamp_type insertMissingLastTimestamp_;	// The last timestamp that came from insertMissing(), so we can avoid duplication	
andrewm@0: 	
andrewm@0: protected:
andrewm@0: 	boost::circular_buffer<OutputType> *buffer_;			// Internal buffer to store or cache values
andrewm@0: 	boost::circular_buffer<timestamp_type> *timestamps_;	// Internal buffer to hold timestamps for each value
andrewm@0: 	
andrewm@0: 	size_type numSamples_;							// How many samples total we've stored in this buffer
andrewm@0: 	size_type firstSampleIndex_;					// Index of the first sample that still remains in the buffer
andrewm@0: };
andrewm@0: 
andrewm@0: /*
andrewm@0:  * Node
andrewm@0:  *
andrewm@0:  * This class handles a node of a specific data type, including the ability to interpolate between samples.  This is the recommended
andrewm@0:  * class to use for numeric data types and others for which linear interpolation makes sense.
andrewm@0:  */
andrewm@0: 
andrewm@0: template<typename OutputType>
andrewm@0: class Node : public NodeNonInterpolating<OutputType> {
andrewm@0: public:	
andrewm@0: 	typedef typename std::allocator<OutputType> Alloc;
andrewm@0: 	typedef NodeInterpolatedIterator<OutputType, boost::cb_details::const_traits<Alloc> > interpolated_iterator;
andrewm@0: 	
andrewm@0: 	typedef typename NodeNonInterpolating<OutputType>::return_value_type return_value_type;
andrewm@0: 	typedef typename NodeNonInterpolating<OutputType>::capacity_type capacity_type;
andrewm@0: 	typedef typename NodeNonInterpolating<OutputType>::size_type size_type;
andrewm@0: 	
andrewm@0: 	// ***** Constructors *****
andrewm@0: 	//
andrewm@0: 	// Use the same constructors as the non-interpolating version.
andrewm@0: 	
andrewm@0: 	explicit Node(capacity_type capacity) : NodeNonInterpolating<OutputType>(capacity) {}
andrewm@0: 	Node(Node<OutputType> const& obj) : NodeNonInterpolating<OutputType>(obj) {}
andrewm@0: 	
andrewm@0: 	// ***** Interpolating Accessors *****
andrewm@0: 	//
andrewm@0: 	// These overloaded methods allow querying a location between two samples, using linear
andrewm@0: 	// interpolation to generate the value.
andrewm@0: 	
andrewm@0: 	return_value_type interpolate(double index) {
andrewm@0: 		size_type before = floor(index);				// Find the sample before the interpolated location
andrewm@0: 		double frac = index - (double)before;			// Find the fractional remainder component
andrewm@0: 		OutputType val1 = this->buffer_->at(before-this->firstSampleIndex_);
andrewm@0: 		if(before == this->endIndex()-1)
andrewm@0: 			return val1;
andrewm@0: 		OutputType val2 = this->buffer_->at(before+1-this->firstSampleIndex_);
andrewm@0: 		//if(missing_value<OutputType>::isMissing(val1))	// Make sure both values have been calculated
andrewm@0: 		//	val1 = (buffer_->at(before-firstSampleIndex_) = evaluate(before));
andrewm@0: 		//if(missing_value<OutputType>::isMissing(val2))
andrewm@0: 		//	val2 = (buffer_->at(before+1-firstSampleIndex_) = evaluate(before+1));		
andrewm@0: 		return val1*(1.0-frac) + val2*frac;				// Return the interpolated value
andrewm@0: 	}		
andrewm@0: 	
andrewm@0: 	interpolated_iterator interpolatedBegin(double step = 1.0) { return interpolated_iterator(this, (double)this->beginIndex(), step); }
andrewm@0: 	interpolated_iterator interpolatedEnd(double step = 1.0) { return interpolated_iterator(this, (double)this->endIndex(), step); }
andrewm@0: 	interpolated_iterator interpolatedIteratorAtIndex(double index, double step = 1.0) { return interpolated_iterator(this, index, step); }	
andrewm@0: 	
andrewm@0: 	// ***** Interpolating Timestamp Methods *****
andrewm@0: 	//
andrewm@0: 	// Using linear interpolation, find the exact relationship between a timestamp and an index in the buffer.
andrewm@0: 	// Designed to be used in conjunction with the interpolate() method for buffer access.
andrewm@0: 	
andrewm@0: 	// Fractional index --> timestamp
andrewm@0: 	timestamp_type interpolatedTimestampAt(double index) {
andrewm@0: 		size_type before = floor(index);
andrewm@0: 		double frac = index - (double)before;
andrewm@0: 		timestamp_type ts1 = timestampAt(before);
andrewm@0: 		if(before == this->endIndex()-1)
andrewm@0: 			return ts1;		
andrewm@0: 		timestamp_type ts2 = timestampAt(before+1);
andrewm@0: 		return ts1*(1.0-frac)+ts2*frac;
andrewm@0: 	}
andrewm@0: 	
andrewm@0: 	// Timestamp --> fractional index
andrewm@0: 	double interpolatedIndexForTimestamp(timestamp_type timestamp) {
andrewm@0: 		size_type before = this->indexNearestBefore(timestamp);
andrewm@0: 		if(before >= this->timestamps_->size() - 1 + this->firstSampleIndex_)		// If it's at the end of the buffer, return the last available timestamp
andrewm@0: 			return (double)before;
andrewm@0: 		timestamp_type beforeTimestamp = this->timestampAt(before);			// Get the timestamp immediately before
andrewm@0: 		if(beforeTimestamp >= timestamp)								// If it comes after the requested timestamp, we're at the beginning of the buffer
andrewm@0: 			return (double)before;
andrewm@0: 		timestamp_type afterTimestamp = this->timestampAt(before+1);
andrewm@0: 		double frac = (timestamp - beforeTimestamp)/(afterTimestamp-beforeTimestamp);
andrewm@0: 		return (double)before + frac;
andrewm@0: 	}		
andrewm@0: };
andrewm@0: 
andrewm@0: #endif /* KEYCONTROL_NODE_H */