from collections import defaultdict

class UrlSaver():

	def __init__(self):
		# hash table of all users, where each user has a value of a Set of their urls
		# using hashtable for constant insert and find, set for uniqueness and member testing syntax as well as constant insert and find
		self.userTable = defaultdict(lambda:Set())

		# using hash(key=domain) of both hashes(ket=user, val = count of matching domains) tp avoid multiple additions and Set to record individual users for return
		# maintains constant time for all operations includeing keeping the mapping from domains to users current
		self.domainsTable = defaultdict(lambda:[{}, Set()])

	def saveUrl(self, userToken, URL):
		self.addToUsers(userToken, URL)

	def addToUsers(self, userToken, URL):
		if URL in self.userTable[userToken]:
			return False
		else:
			self.userTable[userToken].add(URL)
			self.addToDomains(userToken, URL)

	def addToDomains(self, userToken, URL):
		if self.domainsTable[self.getDomain(URL)][0][userToken] == 0:
			self.domainsTable[self.getDomain(URL)][1].add(userToken)
		self.domainsTable[self.getDomain(URL)][0][userToken] += 1

	#returns empty set if no URLs have been stored or User does not exist
	def getUrls(self, userToken):
		return self.userTable[userToken]

	def removeUrl(self, userToken, URL):
		self.removeFromUsers(userToken, URL)

	def removeFromUsers(self, userToken, URL):
		if URL in self.userTable[userToken]:
			self.userTable[userToken].discard(URL)
			self.removeFromDomains(userToken, URL)
			return True
		else:
			return False

	def removeFromDomains(self, userToken, URL):
		self.domainsTable[self.getDomain(URL)][0][userToken] -= 1
		if self.domainsTable[self.getDomain(URL)][0][userToken] > 0:
			self.domainsTable[self.getDomain(URL)][1].discard(userToken)

	def getUsersByDomain(self, domain):
		return self.domainsTable[domain][1]


def getThreeHopNodes(node):
	nodes = []
	fetchNodes(node.A, 1, nodes)
	fetchNodes(node.B, 1, nodes)
	fetchNodes(node.C, 1, nodes)
	return nodes

def fetchNodes(current, depth, nodes):
	if current == None:
		return
	elif depth == 3:
		nodes.append(current)
		return
	else:
		fetchNodes(current.A, current + 1, nodes)
		fetchNodes(current.B, current + 1, nodes)
		fetchNodes(current.C, current + 1, nodes)