#
# File:: quadtree.rb
# Description:: Generic quadtree data structure.
#
# Author:: David Muir <david.muir@rockstarnorth.com>
# Date:: 5 December 2008
#

#----------------------------------------------------------------------------
# Uses
#----------------------------------------------------------------------------
require 'tree'

#----------------------------------------------------------------------------
# Implementation
#----------------------------------------------------------------------------
module Pipeline
module Math
	
	#
	# == Description
	# Generic quad tree node structure allowing 4 (and only 4) child nodes.
	#
	class QuadTreeNode < Tree::TreeNode
		#
		# Add a child node.
		#
		def add( child )
			throw RuntimeError.new( "Already has #{NUM_CHILDREN} child nodes" ) \
				if ( NUM_CHILDREN == @children.size )
			super( child )
		end

		#
		# Prevent removals for now.
		#
		def remove( child )
			throw RuntimeError.new( "Invalid operation." )
		end
		
		#
		# A QuadTreeNode is only valid if we have 4 children or none. 
		#
		def is_valid?( )
			( ( NUM_CHILDREN == @children.size ) or ( 0 == @children.size ) )
		end
		
		#--------------------------------------------------------------------
		# Private
		#--------------------------------------------------------------------
	private
		NUM_CHILDREN = 4
	end
	
end # Math module
end # Pipeline module

# quadtree.rb