class btree_node:
	extends RefCounted
	var present = false		#recursion stopper
	var dictkey
	var dictvalue
	var denominator
	var children
	static func create(k,v):
		var ret = btree_node.new()
		ret.dictkey = k
		ret.dictvalue = v
		ret.children = [btree_node.new(),btree_node.new()]
		ret.present = true
		return ret
func shuffle_dictionary(dict: Dictionary):
	var tree = btree_node.create("",null)		#NOTE empty key is reserved
	tree.denominator = (1<<63)-1	#optimal
	var insert = func(dictkey,dictvalue):
		var new = btree_node.create(dictkey,dictvalue)
		new.denominator = rng.randi()
		var currnode = tree
		while true:
			var i = 1 if new.denominator > currnode.denominator else 0
			if !currnode.children[i].present:
				currnode.children[i] = new
				new.present = true
				break
			else:
				currnode = currnode.children[i]
		return
	for key in dict.keys():
		insert.call(key,dict[key])
	var unwrap = func()->Dictionary:
		var ret = {}
		var abstract = func(currnode,prox):
			for ch in currnode.children:
				if ch.present:
					prox.call(ch,prox)
			if currnode != tree:
				ret[currnode.dictkey] = currnode.dictvalue
			return
		abstract.call(tree,abstract)
		return ret
	return unwrap.call()
func shuffle_array(array):			#don't want to write the boilerplate right now, sorry, NOTE OPTIMIZATION
	var dictver = arraytodict(array)
	return dicttoarray(shuffle_dictionary(dictver))
func arraytodict(array):
	var ret = {}
	var i = 0
	while i < array.size():
		ret[str(i)] = array[i]
		i += 1
	return ret
func dicttoarray(dict):
	var ret = []
	for val in dict.values():
		ret.push_back(val)
	return ret