soar_module.h

/*************************************************************************
 * PLEASE SEE THE FILE "license.txt" (INCLUDED WITH THIS SOFTWARE PACKAGE)
 * FOR LICENSE AND COPYRIGHT INFORMATION. 
 *************************************************************************/

/*************************************************************************
 *
 *  file:  soar_module.h
 *
 * =======================================================================
 */

#ifndef SOAR_MODULE_H
#define SOAR_MODULE_H

#include <portability.h>

#include <map>
#include <string>
#include <set>
#include <list>
#include <functional>
#include <assert.h>
#include <cmath>

#include "misc.h"
#include "symtab.h"
#include "mem.h"

typedef struct wme_struct wme;
typedef struct preference_struct preference;

// separates this functionality
// just for Soar modules
namespace soar_module
{
	/////////////////////////////////////////////////////////////
	// Utility functions
	/////////////////////////////////////////////////////////////

	typedef std::set< wme* > wme_set;
	
	typedef struct symbol_triple_struct
	{
		Symbol* id;
		Symbol* attr;
		Symbol* value;

		symbol_triple_struct( Symbol* new_id, Symbol* new_attr, Symbol* new_value ): id(new_id), attr(new_attr), value(new_value) {}
	} symbol_triple;
	typedef std::list< symbol_triple* > symbol_triple_list;
	
	wme *add_module_wme( agent *my_agent, Symbol *id, Symbol *attr, Symbol *value );
	void remove_module_wme( agent *my_agent, wme *w );
	instantiation* make_fake_instantiation( agent* my_agent, Symbol* state, wme_set* conditions, symbol_triple_list* actions );
	
	///////////////////////////////////////////////////////////////////////////
	// Predicates
	///////////////////////////////////////////////////////////////////////////
	
	// a functor for validating parameter values
	template <typename T>
	class predicate: public std::unary_function<T, bool>
	{
		public:
			virtual ~predicate() {}
			virtual bool operator() ( T /*val*/ ) { return true; }
	};	

	// a false predicate
	template <typename T>
	class f_predicate: public predicate<T>
	{
		public:			
			virtual bool operator() ( T /*val*/ ) { return false; }
	};

	// predefined predicate for validating
	// a value between two values known at
	// predicate initialization
	template <typename T>
	class btw_predicate: public predicate<T>
	{
		private:
			T my_min;
			T my_max;
			bool inclusive;
		
		public:
			btw_predicate( T new_min, T new_max, bool new_inclusive ): my_min( new_min ), my_max( new_max ), inclusive( new_inclusive ) {}

			bool operator() ( T val )
			{
				return ( ( inclusive )?( ( val >= my_min ) && ( val <= my_max ) ):( ( val > my_min ) && ( val < my_max ) ) );
			}
	};
	
	// predefined predicate for validating
	// a value greater than a value known at
	// predicate initialization
	template <typename T>
	class gt_predicate: public predicate<T>
	{
		private:
			T my_min;			
			bool inclusive;
		
		public:
			gt_predicate( T new_min, bool new_inclusive ): my_min( new_min ), inclusive( new_inclusive ) {}
			
			bool operator() ( T val )
			{
				return ( ( inclusive )?( ( val >= my_min ) ):( ( val > my_min ) ) );
			}
	};
		
	// predefined predicate for validating
	// a value less than a value known at
	// predicate initialization
	template <typename T>
	class lt_predicate: public predicate<T>
	{
		private:
			T my_max;			
			bool inclusive;
		
		public:
			lt_predicate( T new_max, bool new_inclusive ): my_max( new_max ), inclusive( new_inclusive ) {}		
			
			bool operator() ( T val )
			{
				return ( ( inclusive )?( ( val <= my_max ) ):( ( val < my_max ) ) );
			}
	};

	// superclass for predicates needing
	// agent state
	template <typename T>
	class agent_predicate: public predicate<T>
	{
		protected:
			agent *my_agent;

		public:
			agent_predicate( agent *new_agent ): my_agent( new_agent ) {}
	};


	///////////////////////////////////////////////////////////////////////////
	// Common for params, stats, timers, etc.
	///////////////////////////////////////////////////////////////////////////

	class named_object
	{
		private:
			const char *name;

		public:
			named_object( const char *new_name ): name( new_name ) {}
			virtual ~named_object() {}

			//

			const char *get_name()
			{
				return name;
			}

			//

			virtual char *get_string() = 0;
	};


	template <typename T>
	class accumulator: public std::unary_function<T, void>
	{
		public:
			virtual ~accumulator() {}

			virtual void operator() ( T /*val*/ ) {}
	};

		
	// this class provides for efficient 
	// string->object access
	template <class T>
	class object_container
	{					
		protected:
			agent *my_agent;
			std::map<std::string, T *> *objects;
			
			void add( T *new_object )
			{
				std::string temp_str( new_object->get_name() );
				(*objects)[ temp_str ] = new_object;
			}

		public:
			object_container( agent *new_agent ): my_agent( new_agent ), objects( new std::map<std::string, T *> ) {}
			
			virtual ~object_container()
			{
				typename std::map<std::string, T *>::iterator p;

				for ( p=objects->begin(); p!=objects->end(); p++ )
					delete p->second;

				delete objects;
			}

			//

			T *get( const char *name )
			{
				std::string temp_str( name );
				typename std::map<std::string, T *>::iterator p = objects->find( temp_str );

				if ( p == objects->end() )
					return NULL;
				else
					return p->second;
			}

			void for_each( accumulator<T *> &f  )
			{
				typename std::map<std::string, T *>::iterator p;

				for ( p=objects->begin(); p!=objects->end(); p++ )
				{
					f( p->second );
				}
			}
	};


	///////////////////////////////////////////////////////////////////////////
	// Parameters
	///////////////////////////////////////////////////////////////////////////
	
	// all parameters have a name and
	// can be manipulated generically
	// via strings
	class param: public named_object
	{			
		public:		
			param( const char *new_name ): named_object( new_name ) {}
			virtual ~param() {}

			//

			virtual bool set_string( const char *new_string ) = 0;
			virtual bool validate_string( const char *new_string ) = 0;			
	};

	
	// a primitive parameter can take any primitive
	// data type as value and is validated via
	// any unary predicate
	template <typename T>
	class primitive_param: public param
	{
		protected:
			T value;
			predicate<T> *val_pred;
			predicate<T> *prot_pred;
		
		public:
			primitive_param( const char *new_name, T new_value, predicate<T> *new_val_pred, predicate<T> *new_prot_pred ): param( new_name ), value( new_value ), val_pred( new_val_pred ), prot_pred( new_prot_pred ) {}
			
			virtual ~primitive_param()
			{
				delete val_pred;
				delete prot_pred;
			}
			
			//
			
			virtual char *get_string()
			{
				std::string temp_str;
				to_string( value, temp_str );
				return strdup( temp_str.c_str() );
			}

			virtual bool set_string( const char *new_string )
			{
				T new_val;
				from_string( new_val, new_string );

				if ( !(*val_pred)( new_val ) || (*prot_pred)( new_val ) )
				{
					return false;
				}
				else
				{
					set_value( new_val );
					return true;
				}
			}

			virtual bool validate_string( const char *new_string )
			{
				T new_val;
				from_string( new_val, new_string );

				return (*val_pred)( new_val );
			}
			
			//
			
			virtual T get_value()
			{
				return value;
			}

			virtual void set_value( T new_value )
			{
				value = new_value;
			}
	};
	
	// these are easy definitions for int and double parameters
	typedef primitive_param<int64_t> integer_param;
	typedef primitive_param<double> decimal_param;
	

	// a string param deals with character strings
	class string_param: public param
	{
		protected:
			std::string *value;
			predicate<const char *> *val_pred;
			predicate<const char *> *prot_pred;
		
		public:
			string_param( const char *new_name, const char *new_value, predicate<const char *> *new_val_pred, predicate<const char *> *new_prot_pred ): param( new_name ), value( new std::string( new_value ) ), val_pred( new_val_pred ), prot_pred( new_prot_pred ) {}

			virtual ~string_param()
			{
				delete value;
				delete val_pred;
				delete prot_pred;
			}
			
			//
			
			virtual char *get_string()
			{
				char *return_val = new char[ value->length() + 1 ];
				strcpy( return_val, value->c_str() );
				return_val[ value->length() ] = '\0';

				return return_val;
			}

			virtual bool set_string( const char *new_string )
			{
				if ( !(*val_pred)( new_string ) || (*prot_pred)( new_string ) )
				{
					return false;
				}
				else
				{
					set_value( new_string );
					return true;
				}
			}

			virtual bool validate_string( const char *new_value )
			{
				return (*val_pred)( new_value );
			}
			
			//
			
			virtual const char *get_value()
			{
				return value->c_str();
			}

			virtual void set_value( const char *new_value )
			{
				value->assign( new_value );
			}
	};

	// a primitive_set param maintains a set of primitives
	template <typename T>
	class primitive_set_param: public param
	{
		protected:
			std::set< T > *my_set;
			std::string *value;
			predicate< T > *prot_pred;

		public:
			primitive_set_param( const char *new_name, predicate< T > *new_prot_pred ): param( new_name ), my_set( new std::set< T >() ), value( new std::string ), prot_pred( new_prot_pred ) {}

			virtual ~primitive_set_param()
			{
				delete my_set;
				delete value;
				delete prot_pred;
			}

			virtual char *get_string()
			{
				char *return_val = new char[ value->length() + 1 ];
				strcpy( return_val, value->c_str() );
				return_val[ value->length() ] = '\0';

				return return_val;
			}

			virtual bool validate_string( const char *new_value )
			{
				T test_val;

				return from_string( test_val, new_value );
			}

			virtual bool set_string( const char *new_string )
			{
				T new_val;
				from_string( new_val, new_string );
				
				if ( (*prot_pred)( new_val ) )
				{
					return false;
				}
				else
				{
					typename std::set< T >::iterator it = my_set->find( new_val );
					std::string temp_str;

					if ( it != my_set->end() )
					{
						my_set->erase( it );

						// regenerate value from scratch
						value->clear();
						for ( it=my_set->begin(); it!=my_set->end(); )
						{
							to_string( *it, temp_str );
							value->append( temp_str );

							it++;

							if ( it != my_set->end() )
								value->append( ", " );
						}
					}
					else
					{
						my_set->insert( new_val );

						if ( !value->empty() )
							value->append( ", " );

						to_string( new_val, temp_str );
						value->append( temp_str );
					}


					return true;
				}
			}

			virtual bool in_set( T test_val )
			{
				return ( my_set->find( test_val ) != my_set->end() );
			}

			virtual typename std::set< T >::iterator set_begin()
			{
				return my_set->begin();
			}

			virtual typename std::set< T >::iterator set_end()
			{
				return my_set->end();
			}
	};

	// these are easy definitions for sets
	typedef primitive_set_param< int64_t > int_set_param;

	// a sym_set param maintains a set of strings
	class sym_set_param: public param
	{
		protected:
			std::set<Symbol *> *my_set;
			std::string *value;
			predicate<const char *> *prot_pred;

			agent *my_agent;

		public:
			sym_set_param( const char *new_name, predicate<const char *> *new_prot_pred, agent *new_agent ): param( new_name ), my_set( new std::set<Symbol *>() ), value( new std::string ), prot_pred( new_prot_pred ), my_agent( new_agent ) {}

			virtual ~sym_set_param()
			{
				for ( std::set<Symbol *>::iterator p=my_set->begin(); p!=my_set->end(); p++ )
					symbol_remove_ref( my_agent, (*p) );
				
				delete my_set;
				delete value;
				delete prot_pred;
			}

			//

			virtual char *get_string()
			{
				char *return_val = new char[ value->length() + 1 ];
				strcpy( return_val, value->c_str() );
				return_val[ value->length() ] = '\0';

				return return_val;
			}

			virtual bool set_string( const char *new_string )
			{
				if ( (*prot_pred)( new_string ) )
				{
					return false;
				}
				else
				{
					set_value( new_string );
					return true;
				}
			}

			virtual bool validate_string( const char * /*new_value*/ )
			{
				return true;
			}

			//

			virtual bool in_set( Symbol *test_sym )
			{
				bool return_val = false;

				if ( ( test_sym->common.symbol_type == SYM_CONSTANT_SYMBOL_TYPE ) ||
					 ( test_sym->common.symbol_type == INT_CONSTANT_SYMBOL_TYPE ) ||
					 ( test_sym->common.symbol_type == FLOAT_CONSTANT_SYMBOL_TYPE ) )
				{
					Symbol *my_sym = test_sym;

					if ( my_sym->common.symbol_type != SYM_CONSTANT_SYMBOL_TYPE )
					{
						std::string temp_str;

						if ( my_sym->common.symbol_type == INT_CONSTANT_SYMBOL_TYPE )
						{
							to_string( my_sym->ic.value, temp_str );
						}
						else
						{
							to_string( my_sym->fc.value, temp_str );
						}

						my_sym = make_sym_constant( my_agent, temp_str.c_str() );
					}

					std::set<Symbol *>::iterator p = my_set->find( my_sym );
					return_val = ( p != my_set->end() );

					if ( test_sym != my_sym )
					{
						symbol_remove_ref( my_agent, my_sym );
					}
				}

				return return_val;
			}

			virtual void set_value( const char *new_value )
			{
				Symbol *my_sym = make_sym_constant( my_agent, new_value );
				std::set<Symbol *>::iterator p = my_set->find( my_sym );

				if ( p != my_set->end() )
				{
					my_set->erase( p );

					// remove for now and when added to the set
					symbol_remove_ref( my_agent, my_sym );
					symbol_remove_ref( my_agent, my_sym );

					// regenerate value from scratch
					value->clear();
					for ( p=my_set->begin(); p!=my_set->end(); )
					{
						value->append( (*p)->sc.name );

						p++;

						if ( p != my_set->end() )
							value->append( ", " );
					}
				}
				else
				{
					my_set->insert( my_sym );

					if ( !value->empty() )
						value->append( ", " );

					value->append( my_sym->sc.name );
				}
			}
	};

	// a constant parameter deals in discrete values
	// for efficiency, internally we use enums, elsewhere
	// strings for user-readability
	template <typename T>
	class constant_param: public param
	{
		protected:		
			T value;
			std::map<T, const char *> *value_to_string;
			std::map<std::string, T> *string_to_value;
			predicate<T> *prot_pred;			
			
		public:						
			constant_param( const char *new_name, T new_value, predicate<T> *new_prot_pred ): param( new_name ), value( new_value ), value_to_string( new std::map<T, const char *>() ), string_to_value( new std::map<std::string, T> ), prot_pred( new_prot_pred ) {}
			
			virtual ~constant_param()
			{
				delete value_to_string;
				delete string_to_value;
				delete prot_pred;
			}
			
			//
			
			virtual char *get_string()
			{
				typename std::map<T, const char *>::iterator p;
				p = value_to_string->find( value );

				if ( p == value_to_string->end() )
					return NULL;
				else
				{
					size_t len = strlen( p->second );
					char *return_val = new char[ len + 1 ];

					strcpy( return_val, p->second );
					return_val[ len ] = '\0';

					return return_val;
				}
			}

			virtual bool set_string( const char *new_string )
			{
				typename std::map<std::string, T>::iterator p;
				std::string temp_str( new_string );

				p = string_to_value->find( temp_str );

				if ( ( p == string_to_value->end() ) || (*prot_pred)( p->second ) )
				{
					return false;
				}
				else
				{
					set_value( p->second );
					return true;
				}
			}

			virtual bool validate_string( const char *new_string )
			{
				typename std::map<std::string, T>::iterator p;
				std::string temp_str( new_string );

				p = string_to_value->find( temp_str );

				return ( p != string_to_value->end() );
			}

			//
			
			virtual T get_value()
			{
				return value;
			}

			virtual void set_value( T new_value )
			{
				value = new_value;
			}
			
			//
			
			virtual void add_mapping( T val, const char *str )
			{
				std::string my_string( str );

				// string to value
				(*string_to_value)[ my_string ] = val;

				// value to string
				(*value_to_string)[ val ] = str;
			}
	};

	// this is an easy implementation of a boolean parameter
	enum boolean { off, on };
	class boolean_param: public constant_param<boolean>
	{
		public:
			boolean_param( const char *new_name, boolean new_value, predicate<boolean> *new_prot_pred ): constant_param<boolean>( new_name, new_value, new_prot_pred )
			{
				add_mapping( off, "off" );
				add_mapping( on, "on" );
			}
	};
	

	///////////////////////////////////////////////////////////////////////////
	// Parameter Container
	///////////////////////////////////////////////////////////////////////////

	typedef object_container<param> param_container;


	///////////////////////////////////////////////////////////////////////////
	// Statistics
	///////////////////////////////////////////////////////////////////////////
	
	// all statistics have a name and
	// can be retrieved generically
	// via strings
	class stat: public named_object
	{			
		public:		
			stat( const char *new_name ): named_object( new_name ) {}
			virtual ~stat() {}
			
			//
			
			virtual void reset() = 0;
	};


	// a primitive statistic can take any primitive
	// data type as value
	template <typename T>
	class primitive_stat: public stat
	{
		private:
			T value;
			T reset_val;
			predicate<T> *prot_pred;
		
		public:
			primitive_stat( const char *new_name, T new_value, predicate<T> *new_prot_pred ): stat( new_name ), value( new_value ), reset_val( new_value ), prot_pred( new_prot_pred ) {}			
			
			virtual ~primitive_stat()
			{
				delete prot_pred;
			}
			
			//
			
			virtual char *get_string()
			{
				T my_val = get_value();

				std::string temp_str;
				to_string( my_val, temp_str );
				return strdup(temp_str.c_str());
			}

			void reset()
			{
				if ( !(*prot_pred)( value ) )
					value = reset_val;
			}
			
			//
			
			virtual T get_value()
			{
				return value;
			}

			virtual void set_value( T new_value )
			{
				value = new_value;
			}
	};

	// these are easy definitions for int and double stats
	typedef primitive_stat<int64_t> integer_stat;
	typedef primitive_stat<double> decimal_stat;	
	
	///////////////////////////////////////////////////////////////////////////
	// Statistic Containers
	///////////////////////////////////////////////////////////////////////////

	class stat_container: public object_container<stat>
	{
		public:
			stat_container( agent *new_agent ): object_container<stat>( new_agent ) {}

			//

			void reset()
			{
				for ( std::map<std::string, stat *>::iterator p=objects->begin(); p!=objects->end(); p++ )
					p->second->reset();
			}
	};


	///////////////////////////////////////////////////////////////////////////
	// timers
	///////////////////////////////////////////////////////////////////////////	

	class timer: public named_object
	{
		public:
			enum timer_level { zero, one, two, three, four, five };
	
		protected:
			agent *my_agent;
			
			soar_process_timer stopwatch;
			soar_timer_accumulator accumulator;

			timer_level level;
			predicate<timer_level> *pred;			

		public:

			timer( const char *new_name, agent *new_agent, timer_level new_level, predicate<timer_level> *new_pred, bool soar_control = true );

			virtual ~timer()
			{
				delete pred;
			}

			//

			virtual char *get_string()
			{
				double my_value = value();

				std::string temp_str;
				to_string( my_value, temp_str );
				return strdup(temp_str.c_str());
			}

			//

			virtual void reset()
			{
				stopwatch.stop();
				accumulator.reset();
			}

			virtual double value()
			{
				return accumulator.get_sec();
			}

			//

			virtual void start()
			{
				if ( (*pred)( level ) )
				{
					stopwatch.start();
				}
			}

			virtual void stop()
			{
				if ( (*pred)( level ) )
				{
					stopwatch.stop();
					accumulator.update(stopwatch);
				}
			}
	};


	///////////////////////////////////////////////////////////////////////////
	// Timer Containers
	///////////////////////////////////////////////////////////////////////////

	class timer_container: public object_container<timer>
	{
		public:
			timer_container( agent *new_agent ): object_container<timer>( new_agent ) {}

			//

			void reset()
			{
				for ( std::map<std::string, timer *>::iterator p=objects->begin(); p!=objects->end(); p++ )
					p->second->reset();
			}
	};


	///////////////////////////////////////////////////////////////////////////
	// Memory Pool Allocators
	///////////////////////////////////////////////////////////////////////////

#define USE_MEM_POOL_ALLOCATORS 1

#ifdef USE_MEM_POOL_ALLOCATORS

	memory_pool* get_memory_pool( agent* my_agent, size_t size );

	template <class T>
	class soar_memory_pool_allocator
	{
	public:
		typedef T			value_type;
		typedef size_t		size_type;
		typedef ptrdiff_t	difference_type;

		typedef T*			pointer;
		typedef const T*	const_pointer;

		typedef T&			reference;
		typedef const T&	const_reference;

	public:
		agent* get_agent() const { return my_agent; }

		soar_memory_pool_allocator( agent* new_agent ): my_agent(new_agent), mem_pool(NULL), size(sizeof(value_type))
		{
			// useful for debugging
			// std::string temp_this( typeid( value_type ).name() );
		}

		soar_memory_pool_allocator( const soar_memory_pool_allocator& obj ): my_agent(obj.get_agent()), mem_pool(NULL), size(sizeof(value_type))
		{
			// useful for debugging
			// std::string temp_this( typeid( value_type ).name() );
		}

		template <class _other>
		soar_memory_pool_allocator( const soar_memory_pool_allocator<_other>& other ): my_agent(other.get_agent()), mem_pool(NULL), size(sizeof(value_type))
		{
			// useful for debugging
			// std::string temp_this( typeid( T ).name() );
			// std::string temp_other( typeid( _other ).name() );
		}

		pointer allocate( size_type
#ifndef NDEBUG
			n
#endif
			, const void* = 0 )
		{
			assert( n == 1 );
			
			if ( !mem_pool )
			{
				mem_pool = get_memory_pool( my_agent, size );
			}
			
			pointer t;
			allocate_with_pool( my_agent, mem_pool, &t );

			return t;
		}

		void deallocate( void* p, size_type 
#ifndef NDEBUG
			n
#endif
			)
		{
			assert( n == 1 );

			// not sure if this is correct...
			// it only comes up if an object uses another object's
			// allocator to deallocate memory that it allocated.
			// it's quite possible, then, that the sizes would be off
			if ( !mem_pool )
			{
				mem_pool = get_memory_pool( my_agent, size );
			}
			
			if ( p )
			{
				free_with_pool( mem_pool, p );
			}
		}

		void construct( pointer p, const_reference val )
		{
			new (p) T( val );
		}

		void destroy( pointer p )
		{
			p->~T();
		}

		size_type max_size() const
		{
			return static_cast< size_type >( -1 );
		}

		const_pointer address( const_reference r ) const
		{
			return &r;
		}

		pointer address( reference r ) const
		{
			return &r;
		}

		template <class U>
		struct rebind
		{
			typedef soar_memory_pool_allocator<U> other;
		};


	private:
		agent* my_agent;
		memory_pool* mem_pool;
		size_type size;

		soar_memory_pool_allocator() {}

	};

#endif

	///////////////////////////////////////////////////////////////////////////
	// Object Store Management
	//
	// Model:
	// 1) Store consists of a set of "objects"
	// 2) Time proceeds forward in discrete "steps"
	// 3) Objects decay according to arbitrary decay function
	// 4) Object references may occur multiple times within each step
	//
	// Implementation:
	// A) Templated object store (internally maintains pointers to type T)
	// B) Bounded history (template parameter N)
	// C) Subclasses implement decay
	///////////////////////////////////////////////////////////////////////////

	template <class T, int N>
	class object_memory
	{
	public:
		typedef uint64_t time_step;
		typedef uint64_t object_reference;

		typedef std::set< const T* > object_set;

	protected:
		typedef struct object_time_reference_struct
		{
			object_reference num_references;
			time_step t_step;
		} object_time_reference;

		typedef struct object_history_struct
		{
			object_time_reference reference_history[ N ];
			unsigned int next_p;
			unsigned int history_ct;

			object_reference history_references;
			object_reference total_references;
			time_step first_reference;

			time_step decay_step;

			object_reference buffered_references;

			//

			const T* this_object;

			//

			object_history_struct( const T* obj )
			{
				this_object = obj;

				buffered_references = 0;

				decay_step = 0;

				history_references = 0;
				total_references = 0;
				first_reference = 0;

				next_p = 0;
				history_ct = 0;
				for ( int i=0; i<N; i++ )
				{
					reference_history[ i ].num_references = 0;
					reference_history[ i ].t_step = 0;
				}
			}

		} object_history;

		unsigned int history_next( unsigned int current )
		{
			return ( ( current == ( N - 1 ) )?( 0 ):( current + 1 ) );
		}

		unsigned int history_prev( unsigned int current )
		{
			return ( ( current == 0 )?( N - 1 ):( current - 1 ) );
		}
		
	private:
		typedef std::map< const T*, object_history > object_history_map;
		typedef std::set< object_history* > history_set;
		typedef std::set< time_step > time_set;
		typedef std::map< time_step, history_set > forgetting_map;
		
	protected:
		const object_history* get_history( const T* obj )
		{			
			typename object_history_map::iterator p = object_histories.find( obj );
			if ( p != object_histories.end() )
			{
				return &( p->second );
			}
			else
			{
				return NULL;
			}
		}

		time_step get_current_time()
		{
			return step_count;
		}

		bool is_initialized()
		{
			return initialized;
		}

		virtual time_step estimate_forgetting_time( const object_history* h, time_step t, bool fresh_reference ) = 0;
		virtual bool should_forget( const object_history* h, time_step t ) = 0;

		virtual void _init() = 0;
		virtual void _down() = 0;
		
	public:
		object_memory(): initialized( false )
		{
		}

		void initialize()
		{
			if ( !initialized )
			{
				step_count = 1;

				_init();
				
				initialized = true;
			}
		}

		void teardown()
		{
			if ( initialized )
			{				
				touched_histories.clear();
				touched_times.clear();
				forgetting_pq.clear();
				forgotten.clear();
				object_histories.clear();

				_down();
				
				initialized = false;
			}
		}

		// return: was this a new object?
		bool reference_object( const T* obj, object_reference num )
		{
			object_history* h = NULL;
			bool return_val = false;
			
			typename object_history_map::iterator p = object_histories.find( obj );
			if ( p != object_histories.end() )
			{
				h = &( p->second );
			}
			else
			{
				std::pair< typename object_history_map::iterator, bool > ip = object_histories.insert( std::make_pair< const T*, object_history >( obj, object_history( obj ) ) );
				assert( ip.second );

				h = &( ip.first->second );

				return_val = true;
			}

			h->buffered_references += num;
			touched_histories.insert( h );

			return return_val;
		}

		void remove_object( const T* obj )
		{
			typename object_history_map::iterator p = object_histories.find( obj );
			if ( p != object_histories.end() )
			{
				touched_histories.erase( &( p->second ) );
				remove_from_pq( &( p->second ) );
				object_histories.erase( p );
			}
		}

		void process_buffered_references()
		{
			typename history_set::iterator h_p;
			object_history* h;

			// add to history for changed histories
			for ( h_p=touched_histories.begin(); h_p!=touched_histories.end(); h_p++ )
			{
				h = *h_p;

				// update number of references in the current history
				// (has to come before history overwrite)
				h->history_references += ( h->buffered_references - h->reference_history[ h->next_p ].num_references );

				// set history
				h->reference_history[ h->next_p ].t_step = step_count;
				h->reference_history[ h->next_p ].num_references = h->buffered_references;

				// keep track of first reference
				if ( h->total_references == 0 )
				{
					h->first_reference = step_count;
				}

				// update counters
				if ( h->history_ct < N )
				{
					h->history_ct++;
				}
				h->next_p = history_next( h->next_p );
				h->total_references += h->buffered_references;

				// reset buffer counter
				h->buffered_references = 0;

				// update p-queue
				if ( h->decay_step != 0 )
				{
					move_in_pq( h, estimate_forgetting_time( h, step_count, true ) );
				}
				else
				{
					add_to_pq( h, estimate_forgetting_time( h, step_count, true ) );
				}
			}

			touched_histories.clear();
		}

		typename object_set::iterator forgotten_begin()
		{
			return forgotten.begin();
		}

		typename object_set::iterator forgotten_end()
		{
			return forgotten.end();
		}

		void forget()
		{
			forgotten.clear();
			
			if ( !forgetting_pq.empty() )
			{
				typename forgetting_map::iterator pq_p = forgetting_pq.begin();

				// check if we even have to do anything this time step
				if ( pq_p->first == step_count )
				{
					typename history_set::iterator d_p=pq_p->second.begin();
					typename history_set::iterator current_p;

					while ( d_p != pq_p->second.end() )
					{
						current_p = d_p++;

						if ( should_forget( *current_p, step_count ) )
						{
							forgotten.insert( (*current_p)->this_object );
							remove_from_pq( *current_p );
						}
						else
						{
							move_in_pq( *current_p, estimate_forgetting_time( *current_p, step_count, false ) );
						}
					}

					// clean up set
					touched_times.insert( pq_p->first );
					pq_p->second.clear();
				}

				// clean up touched time sets
				for ( time_set::iterator t_p=touched_times.begin(); t_p!=touched_times.end(); t_p++ )
				{
					pq_p = forgetting_pq.find( *t_p );
					if ( ( pq_p != forgetting_pq.end() ) && pq_p->second.empty() )
					{
						forgetting_pq.erase( pq_p );
					}
				}

				touched_times.clear();
			}
		}

		void time_forward()
		{
			step_count++;
		}

		void time_back()
		{
			step_count--;
		}

	private:

		void add_to_pq( object_history* h, time_step t )
		{
			assert( h->decay_step == 0 );
			
			h->decay_step = t;
			forgetting_pq[ t ].insert( h );
		}

		void remove_from_pq( object_history* h )
		{
			if ( h->decay_step )
			{
				typename forgetting_map::iterator f_p = forgetting_pq.find( h->decay_step );
				if ( f_p != forgetting_pq.end() )
				{
					f_p->second.erase( h );
					touched_times.insert( h->decay_step );
				}

				h->decay_step = 0;
			}
		}

		void move_in_pq( object_history* h, time_step new_t )
		{
			if ( h->decay_step != new_t )
			{
				remove_from_pq( h );
				add_to_pq( h, new_t );
			}
		}

		bool initialized;

		time_step step_count;

		object_history_map object_histories;
		history_set touched_histories;
		time_set touched_times;
		forgetting_map forgetting_pq;

		object_set forgotten;
	};

	///////////////////////////////////////////////////////////////////////////
	// Base-Level Activation (BLA) Object Store Management
	//
	// Notes:
	// - Approximation of decay time depends upon an estimate of
	//   max reference/time step (template parameter R)
	// - Smallest activation is bounded by activation_low constant
	///////////////////////////////////////////////////////////////////////////

	template <class T, int N, unsigned int R>
	class bla_object_memory : public object_memory<T,N>
	{
	protected:
		// helps avoid verbose types below
		typedef typename object_memory<T, N>::time_step time_step;
		typedef typename object_memory<T, N>::object_reference object_reference;
		typedef typename object_memory<T, N>::object_history object_history;
		
	private:
		double activation_none;
		double activation_low;
		double time_sum_none;
		
		bool use_petrov;
		double decay_rate;
		double decay_thresh;
		uint64_t pow_cache_bound;

	public:
		bla_object_memory(): activation_none( 1.0 ), activation_low( -1000000000 ), time_sum_none( 2.71828182845905 ), use_petrov( true ), decay_rate( -0.5 ), decay_thresh( -2.0 ), pow_cache_bound( 10 )
		{
		}

		// return: was the setting accepted?
		bool set_petrov( bool new_petrov )
		{
			if ( !this->is_initialized() )
			{
				use_petrov = new_petrov;
				return true;
			}

			return false;
		}

		// takes positive, stores negative
		// return: was the value accepted (0, 1)
		bool set_decay_rate( double new_decay_rate )
		{
			if ( ( new_decay_rate > 0 ) && ( new_decay_rate < 1 ) && !this->is_initialized() )
			{
				decay_rate = -new_decay_rate;
				return true;
			}

			return false;
		}

		// return: was the setting accepted?
		bool set_decay_thresh( double new_decay_thresh )
		{
			if ( !this->is_initialized() )
			{
				decay_thresh = new_decay_thresh;
				return true;
			}

			return false;
		}

		// input: cache size in megabytes (0, inf)
		// return: was the setting accepted?
		bool set_pow_cache_bound( uint64_t new_pow_cache_bound )
		{
			if ( ( new_pow_cache_bound > 0 ) && !this->is_initialized() )
			{
				pow_cache_bound = new_pow_cache_bound;
				return true;
			}

			return false;
		}

		double get_object_activation( T* obj, bool log_result )
		{
			return compute_history_activation( get_history( obj ), this->get_current_time(), log_result );
		}

	protected:
		void _init()
		{
			// Pre-compute the integer powers of the decay exponent in order to avoid
			// repeated calls to pow() at runtime
			{
				// determine cache size
				{
					// computes how many powers to compute
					// basic idea: solve for the time that would just fall below the decay threshold, given decay rate and assumption of max references/time step
					// t = e^( ( thresh - ln( max_refs ) ) / -decay_rate )
					double cache_full = static_cast<double>( exp( ( decay_thresh - log( static_cast<double>( R ) ) ) / decay_rate ) );

					// we bound this by the max-pow-cache parameter to control the space vs. time tradeoff the cache supports
					// max-pow-cache is in MB, so do the conversion:
					// MB * 1024 bytes/KB * 1024 KB/MB
					double cache_bound_unit = ( static_cast<unsigned int>( pow_cache_bound * 1024 * 1024 ) / static_cast<unsigned int>( sizeof( double ) ) );

					pow_cache_size = static_cast< unsigned int >( ceil( ( cache_full > cache_bound_unit )?( cache_bound_unit ):( cache_full ) ) );
				}

				pow_cache = new double[ pow_cache_size ];

				pow_cache[0] = 0.0;
				for( unsigned int i=1; i<pow_cache_size; i++ )
				{
					pow_cache[ i ] = pow( static_cast<double>( i ), decay_rate );
				}
			}

			// calculate the pre-log'd forgetting threshold, to avoid most
			// calls to log
			decay_thresh_exp = exp( decay_thresh );

			// approximation cache
			{
				approx_cache[0] = 0;
				for ( int i=1; i<R; i++ )
				{
					approx_cache[i] = static_cast< time_step >( ceil( exp( static_cast<double>( decay_thresh - log( static_cast<double>(i) ) ) / static_cast<double>( decay_rate ) ) ) );
				}
			}
		}

		void _down()
		{
			// release power array memory
			delete[] pow_cache;
		}

		time_step estimate_forgetting_time( const object_history* h, time_step t, bool fresh_reference )
		{
			time_step return_val = t;

			// if new reference, we can cheaply under-estimate decay time
			// by treating all reference time steps independently
			// see AAAI FS: (Derbinsky & Laird 2011)
			if ( fresh_reference )
			{
				time_step to_add = 0;

				unsigned int p = h->next_p;
				unsigned int counter = h->history_ct;
				time_step t_diff = 0;
				object_reference approx_ref;

				while ( counter )
				{
					p = this->history_prev( p );

					t_diff = ( return_val - h->reference_history[ p ].t_step );

					approx_ref = ( ( h->reference_history[ p ].num_references < R )?( h->reference_history[ p ].num_references ):( R-1 ) );
					if ( approx_cache[ approx_ref ] > t_diff )
					{
						to_add += ( approx_cache[ approx_ref ] - t_diff );
					}

					counter--;
				}

				return_val += to_add;
			}

			// if approximation wasn't useful, or we used it previously and are now
			// beyond the underestimate, use binary parameter search to exactly
			// compute the time of forgetting
			if ( return_val == t )
			{
				time_step to_add = 1;

				if ( !should_forget( h, ( return_val + to_add ) ) )
				{					
					// find absolute upper bound
					do
					{
						to_add *= 2;
					} while ( !should_forget( h, ( return_val + to_add ) ) );

					// vanilla binary search within range: (upper/2, upper)
					time_step upper_bound = to_add;
					time_step lower_bound, mid;
					if ( to_add < 4 )
					{
						lower_bound = upper_bound;
					}
					else
					{
						lower_bound = ( to_add / 2 );
					}

					while ( lower_bound != upper_bound )
					{
						mid = ( ( lower_bound + upper_bound ) / 2 );

						if ( should_forget( h, ( return_val + mid ) ) )
						{
							upper_bound = mid;

							if ( upper_bound - lower_bound <= 1 )
							{
								lower_bound = mid;
							}
						}
						else
						{
							lower_bound = mid;

							if ( upper_bound - lower_bound <= 1 )
							{
								lower_bound = upper_bound;
							}
						}
					}

					to_add = upper_bound;
				}

				return_val += to_add;
			}
			
			return return_val;
		}

		bool should_forget( const object_history* h, time_step t )
		{
			return ( compute_history_activation( h, t, false ) < decay_thresh_exp );
		}

	private:	
		double _pow( time_step t_diff )
		{
			if ( t_diff < pow_cache_size )
			{
				return pow_cache[ t_diff ];
			}
			else
			{
				return pow( static_cast<double>( t_diff ), decay_rate );
			}
		}

		double compute_history_activation( const object_history* h, time_step t, bool log_result )
		{
			double return_val = ( ( log_result )?( activation_none ):( time_sum_none ) );

			if ( h && h->history_ct )
			{
				return_val = 0.0;
				
				// sum history
				{
					unsigned int p = h->next_p;
					unsigned int counter = h->history_ct;
					time_step t_diff = 0;

					//

					while ( counter )
					{
						p = this->history_prev( p );

						t_diff = ( t - h->reference_history[ p ].t_step );
						assert( t_diff > 0 );

						return_val += ( h->reference_history[ p ].num_references * _pow( t_diff ) );
						
						counter--;
					}

					// tail approximation for a bounded history, see (Petrov 2006)
					if ( use_petrov )
					{
						// if ( n > k )
						if ( h->total_references > h->history_references )
						{
							// ( n - k ) * ( tn^(1-d) - tk^(1-d) )
							// -----------------------------------
							// ( 1 - d ) * ( tn - tk )

							// decay_rate is negated (for nice printing)
							double d_inv = ( 1 + decay_rate );
							
							return_val += ( ( ( h->total_references - h->history_references ) * ( pow( static_cast<double>( t - h->first_reference ), d_inv ) - pow( static_cast<double>( t_diff ), d_inv ) ) ) / 
											( d_inv * ( ( t - h->first_reference ) - t_diff ) ) );
						}
					}
				}

				if ( log_result )
				{
					if ( return_val > 0.0 )
					{
						return_val = log( return_val );
						if ( return_val < activation_low )
						{
							return_val = activation_low;
						}
					}
					else
					{
						return_val = activation_low;
					}
				}
			}
			
			return return_val;
		}

		double decay_thresh_exp;

		unsigned int pow_cache_size;
		double* pow_cache;

		time_step approx_cache[ R ];
	};

}

#endif