"""
find a unique name based on a prefix for a content in a container
(eg. a file in a directory) adding a digit to the name
Does it in log2(n) + log2(n/2) were n is the number of duplicates
"""
def go_down(name, exists, lower, upper):
"""bisection to find first free slot
"""
if upper - lower < 2:
if exists(name + '-%d' % lower):
return name + '-%d' % upper
else:
return name + '-%d' % lower
else:
mid = (upper + lower) // 2
if exists(name + '-%d' % mid):
return go_down(name, exists, mid, upper)
else:
return go_down(name, exists, lower, mid)
def go_up(name, exists, n):
"""find a free slot in log2(n) time
"""
if exists(name + '-%d' % n):
return go_up(name, exists, n * 2)
else:
# NOTE : 'or 1' for we don't want <name>-0
return go_down(name, exists, n // 2 or 1, n)
def getname(name, exists):
"""return a unique name, using name as suffix
exists is a function that will test existence
"""
if not exists(name):
return name
else:
return go_up(name, exists, 1)
if __name__ == '__main__':
# quick test
import os
import glob
import tempfile
import shutil
cwd = os.getcwd()
tmpdir = tempfile.mkdtemp()
try:
os.chdir(tmpdir)
for i in xrange(50):
name = getname('a', os.path.exists)
with open(name, 'w') as f:
f.write(str(i))
# verify (do not verify 0 as it is a special case)
assert set(glob.glob('a-*')) == set('a-%d' % i for i in xrange(1, 50))
# verify content to assert order of allocation was correct
for i in xrange(1, 50):
with open('a-%d' % i) as f:
assert f.read() == str(i)
finally:
os.chdir(cwd)
os.chdir(tmpdir)
shutil.rmtree(tmpdir)
