##########################################################################
#  
#  Copyright (c) 2012, John Haddon. All rights reserved.
#  Copyright (c) 2013, Image Engine Design Inc. All rights reserved.
#  
#  Redistribution and use in source and binary forms, with or without
#  modification, are permitted provided that the following conditions are
#  met:
#  
#      * Redistributions of source code must retain the above
#        copyright notice, this list of conditions and the following
#        disclaimer.
#  
#      * Redistributions in binary form must reproduce the above
#        copyright notice, this list of conditions and the following
#        disclaimer in the documentation and/or other materials provided with
#        the distribution.
#  
#      * Neither the name of John Haddon nor the names of
#        any other contributors to this software may be used to endorse or
#        promote products derived from this software without specific prior
#        written permission.
#  
#  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
#  IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
#  THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
#  PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
#  CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
#  EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
#  PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
#  PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
#  LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
#  NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
#  SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
#  
##########################################################################

import unittest
import random

import IECore

import Gaffer
import GafferScene

class PathMatcherTest( unittest.TestCase ) :

	@staticmethod
	def generatePaths( seed, depthRange, numChildrenRange ) :
	
		nouns = [
			"Ball", "Building", "Car", "Tree", "Rampart", "Head", "Arm", 
			"Window", "Door", "Trailer", "Light", "FlockOfBirds", "Herd", "Sheep", 
			"Cow", "Wing", "Engine", "Mast", "Rock", "Road", "Sign", 
		]
		
		adjectives = [
			"big", "red", "metallic", "left", "right", "top", "bottom", "wooden",
			"front", "back", "lower", "upper", "magnificent", "hiRes", "loRes",
		]
		
		paths = []
		def buildWalk( parent="", depth=1 ) :
			
			if depth > random.randint( *depthRange ) :
				return
				
			for i in range( 0, random.randint( *numChildrenRange ) ) :
				path = parent + "/" + random.choice( adjectives ) + random.choice( nouns ) + str( i )
				paths.append( path )
				buildWalk( path, depth + 1 )
						
		random.seed( seed )
		buildWalk()
	
		return paths
	
	def testMatch( self ) :
	
		m = GafferScene.PathMatcher( [ "/a", "/red", "/b/c/d" ] )
	
		for path, result in [
			( "/a", GafferScene.Filter.Result.Match ),
			( "/red", GafferScene.Filter.Result.Match ),
			( "/re", GafferScene.Filter.Result.NoMatch ),
			( "/redThing", GafferScene.Filter.Result.NoMatch ),
			( "/b/c/d", GafferScene.Filter.Result.Match ),
			( "/c", GafferScene.Filter.Result.NoMatch ),
			( "/a/b", GafferScene.Filter.Result.NoMatch ),
			( "/blue", GafferScene.Filter.Result.NoMatch ),
			( "/b/c", GafferScene.Filter.Result.DescendantMatch ),
		] :
			self.assertEqual( m.match( path ), result )
	
	def testLookupScaling( self ) :
	
		# this test provides a useful means of measuring performance when
		# working on the PatchMatcher algorithm. it tests matchers
		# for each of two different hierarchies :
		#
		#    * a deep hierarchy with relatively few children at each branch point
		#	 * a shallow hierarchy with large numbers of children at each branch point
		#
		# the tests build a matcher, and then assert that every path in the hierarchy is
		# matched appropriately. uncomment the timers to get useful information printed out.
			
 		match = GafferScene.Filter.Result.Match

		# deep hierarchy
		paths = self.generatePaths( seed = 10, depthRange = ( 3, 14 ), numChildrenRange = ( 2, 6 ) )
 		t = IECore.Timer()
		matcher = GafferScene.PathMatcher( paths )
 		#print "BUILD DEEP", t.stop()
		 		
 		t = IECore.Timer()
		for path in paths :
			self.assertEqual( matcher.match( path ), match )
		#print "LOOKUP DEEP", t.stop()
		
		# shallow hierarchy
		paths = self.generatePaths( seed = 10, depthRange = ( 2, 2 ), numChildrenRange = ( 500, 1000 ) )
 		t = IECore.Timer()
		matcher = GafferScene.PathMatcher( paths )
 		#print "BUILD SHALLOW", t.stop()
		 		
 		t = IECore.Timer()
		for path in paths :
			self.assertEqual( matcher.match( path ), match )
		#print "LOOKUP SHALLOW", t.stop()
			
	def testDefaultConstructor( self ) :
	
		m = GafferScene.PathMatcher()
		self.assertEqual( m.match( "/" ), GafferScene.Filter.Result.NoMatch )
	
	def testWildcards( self ) :
	
		f = GafferScene.PathFilter()
		f["paths"].setValue(
			IECore.StringVectorData( [
				"/a",
				"/red*",
				"/green*Bloke*",
				"/somewhere/over/the/*",
				"/somewhere/over/the/*/skies/are/blue",
			] )
		)
	
		for path, result in [
			( "/a", f.Result.Match ),
			( "/redBoots", f.Result.Match ),
			( "/red", f.Result.Match ),
			( "/redWellies", f.Result.Match ),
			( "/redWellies/in/puddles", f.Result.NoMatch ),
			( "/greenFatBloke", f.Result.Match ),
			( "/greenBloke", f.Result.Match ),
			( "/greenBlokes", f.Result.Match ),
			( "/somewhere/over/the/rainbow", f.Result.Match ),
			( "/somewhere/over/the", f.Result.DescendantMatch ),
			( "/somewhere/over", f.Result.DescendantMatch ),
			( "/somewhere", f.Result.DescendantMatch ),
			( "/somewhere/over/the/rainbow/skies/are/blue", f.Result.Match ),
			( "/somewhere/over/the/rainbow/skies/are", f.Result.DescendantMatch ),
			( "/somewhere/over/the/astonExpressway/skies/are", f.Result.DescendantMatch ),
			( "/somewhere/over/the/astonExpressway/skies/are/blue", f.Result.Match ),		
			( "/somewhere/over/the/astonExpressway/skies/are/grey", f.Result.NoMatch ),		
		] :
		
			c = Gaffer.Context()
			c["scene:path"] = IECore.InternedStringVectorData( path[1:].split( "/" ) )
			with c :
				self.assertEqual( f["match"].getValue(), int( result ) )
				
	def testWildcardsWithSiblings( self ) :
	
		f = GafferScene.PathFilter()
		f["paths"].setValue(
			IECore.StringVectorData( [
				"/a/*/b",
				"/a/a*/c",
			] )
		)
	
		for path, result in [
			( "/a/aThing/c", f.Result.Match ),
			( "/a/aThing/b", f.Result.Match ),
		] :
		
			c = Gaffer.Context()
			c["scene:path"] = IECore.InternedStringVectorData( path[1:].split( "/" ) )
			with c :
				self.assertEqual( f["match"].getValue(), int( result ) )

	def testRepeatedWildcards( self ) :
	
		f = GafferScene.PathFilter()
		f["paths"].setValue(
			IECore.StringVectorData( [
				"/a/**s",
			] )
		)
		
		c = Gaffer.Context()
		c["scene:path"] = IECore.InternedStringVectorData( [ "a", "s" ] )
		with c :
			self.assertEqual( f["match"].getValue(), int( GafferScene.Filter.Result.Match ) )