From: Stephen Burrows <stephen.r.burrows@gmail.com>
Date: Thu, 4 Nov 2010 18:59:20 +0000 (-0400)
Subject: Improved general efficiency of TreeManager's get_with_path method in terms of number... 
X-Git-Tag: philo-0.9~26^2~7
X-Git-Url: http://git.ithinksw.org/philo.git/commitdiff_plain/bce7b7c4d0308a1d9a2e450b83ba1dac99e57d5b

Improved general efficiency of TreeManager's get_with_path method in terms of number of queries by implementing a halving algorithm. Can require more queries than the previous algorithm in cases where the remainder following the deepest node is relatively long.
---

diff --git a/models/base.py b/models/base.py
index fdfe75c..dabe491 100644
--- a/models/base.py
+++ b/models/base.py
@@ -282,34 +282,74 @@ class TreeManager(models.Manager):
 	def roots(self):
 		return self.filter(parent__isnull=True)
 	
-	def get_with_path(self, path, root=None, absolute_result=True, pathsep='/'):
+	def get_with_path(self, path, root=None, absolute_result=True, pathsep='/', field='slug'):
 		"""
-		Returns the object with the path, or None if there is no object with that path,
-		unless absolute_result is set to False, in which case it returns a tuple containing
-		the deepest object found along the path, and the remainder of the path after that
-		object as a string (or None in the case that there is no remaining path).
+		Returns the object with the path, unless absolute_result is set to False, in which
+		case it returns a tuple containing the deepest object found along the path, and the
+		remainder of the path after that object as a string (or None if there is no remaining
+		path). Raises a DoesNotExist exception if no object is found with the given path.
 		"""
-		slugs = path.split(pathsep)
-		obj = root
-		remaining_slugs = list(slugs)
-		remainder = None
-		for slug in slugs:
-			remaining_slugs.remove(slug)
-			if slug: # ignore blank slugs, handles for multiple consecutive pathseps
+		segments = path.split(pathsep)
+		
+		# Clean out blank segments. Handles multiple consecutive pathseps.
+		while True:
+			try:
+				segments.remove('')
+			except ValueError:
+				break
+		
+		# Special-case a lack of segments. No queries necessary.
+		if not segments:
+			if root is not None:
+				return root, None
+			else:
+				raise self.model.DoesNotExist('%s matching query does not exist.' % self.model._meta.object_name)
+		
+		def make_query_kwargs(segments):
+			kwargs = {}
+			prefix = ""
+			revsegs = list(segments)
+			revsegs.reverse()
+			
+			for segment in revsegs:
+				kwargs["%s%s__exact" % (prefix, field)] = segment
+				prefix += "parent__"
+			
+			kwargs[prefix[:-2]] = root
+			return kwargs
+		
+		def find_obj(segments, depth, deepest_found):
+			try:
+				obj = self.get(**make_query_kwargs(segments[:depth]))
+			except self.model.DoesNotExist:
+				if absolute_result:
+					raise
+				
+				depth = (deepest_found + depth)/2
+				if deepest_found == depth:
+					# This should happen if nothing is found with any part of the given path.
+					raise
+				
+				# Try finding one with half the path since the deepest find.
+				return find_obj(segments, depth, deepest_found)
+			else:
+				# Yay! Found one! Could there be a deeper one?
+				if absolute_result:
+					return obj
+				
+				deepest_found = depth
+				depth = (len(segments) + depth)/2
+				
+				if deepest_found == depth:
+					return obj, pathsep.join(segments[deepest_found:]) or None
+				
 				try:
-					obj = self.get(slug__exact=slug, parent__exact=obj)
+					return find_obj(segments, depth, deepest_found)
 				except self.model.DoesNotExist:
-					if absolute_result:
-						obj = None
-					remaining_slugs.insert(0, slug)
-					remainder = pathsep.join(remaining_slugs)
-					break
-		if obj:
-			if absolute_result:
-				return obj
-			else:
-				return (obj, remainder)
-		raise self.model.DoesNotExist('%s matching query does not exist.' % self.model._meta.object_name)
+					# Then the deepest one was already found.
+					return obj, pathsep.join(segments[deepest_found:])
+		
+		return find_obj(segments, len(segments), 0)
 
 
 class TreeModel(models.Model):