# HG changeset patch
# User Laman
# Date 2017-10-19 10:15:32
# Node ID 2e5828ec7d49da63f4c454086891bfdbd4aa5e00
# Parent  5813971dbeccbe1c8b6455fd70ed75ed8693d712

fixed order of negotiation to a "batch DFS"

diff --git a/src/client.py b/src/client.py
--- a/src/client.py
+++ b/src/client.py
@@ -44,6 +44,11 @@ class Client:
 		print(datetime.now(), "initializing...")
 		self._localTree=HashTree.fromFile(self._filename)
 
+	## Asks server for node hashes to determine which are to be transferred.
+	#
+	# Uses a binary HashTree, where item at k is hash of items at 2k+1, 2k+2.
+	#
+	# Requests nodes in order of a batch DFS. Needs stack of size O(treeDepth*batchSize). Nodes in each tree level are accessed in order.
 	def negotiate(self):
 		localTree=self._localTree
 		blocksToTransfer=[]
@@ -63,7 +68,6 @@ class Client:
 			for i in range(256):
 				indices.append(nodeStack.pop())
 				if len(nodeStack)==0: break
-			indices.sort()
 			self._outcoming.writeMsg({"command":"req", "index":indices, "dataType":"hash"})
 
 			jsonData,binData=self._incoming.readMsg()
@@ -71,18 +75,20 @@ class Client:
 			assert jsonData["dataType"]=="hash"
 			stats.logExchangedNode(len(indices))
 
+			frontier=[]
 			for (j,i) in enumerate(indices):
 				(j1,j2)=[HashTree.HASH_LEN*ji for ji in (j,j+1)]
 				if localTree.store[i]!=binData[j1:j2]:
 					if 2*i+3<len(localTree.store): # inner node
-						nodeStack.append(2*i+2)
-						nodeStack.append(2*i+1)
+						frontier.append(2*i+1)
+						frontier.append(2*i+2)
 					else:
 						blocksToTransfer.append(i-localTree.leafStart) # leaf
 						progress.p(i-localTree.leafStart)
+			nodeStack.extend(reversed(frontier))
 		progress.done()
 
-		return sorted(blocksToTransfer)
+		return blocksToTransfer
 
 	def sendData(self,blocksToTransfer):
 		log.info(blocksToTransfer)