diff options
| -rw-r--r-- | git/objects/tree.py | 52 | ||||
| -rw-r--r-- | git/test/test_tree.py | 55 |
2 files changed, 64 insertions, 43 deletions
diff --git a/git/objects/tree.py b/git/objects/tree.py index e7d579d0..4f853f92 100644 --- a/git/objects/tree.py +++ b/git/objects/tree.py @@ -35,33 +35,42 @@ def git_cmp(t1, t2): if min_cmp: return min_cmp - return len_b - len_a + return len_a - len_b -if PY3: - # taken from https://wiki.python.org/moin/HowTo/Sorting#The_Old_Way_Using_the_cmp_Parameter - class CmpToKey(object): - __slots__ = 'obj' - def __init__(self, obj, *args): - self.obj = obj +def merge_sort(a, cmp): + if len(a) < 2: + return - def __lt__(self, other): - return git_cmp(self.obj, other.obj) < 0 + mid = len(a) // 2 + lefthalf = a[:mid] + righthalf = a[mid:] - def __gt__(self, other): - return git_cmp(self.obj, other.obj) > 0 + merge_sort(lefthalf, cmp) + merge_sort(righthalf, cmp) - def __eq__(self, other): - return git_cmp(self.obj, other.obj) == 0 + i = 0 + j = 0 + k = 0 - def __le__(self, other): - return git_cmp(self.obj, other.obj) <= 0 + while i < len(lefthalf) and j < len(righthalf): + if cmp(lefthalf[i], righthalf[j]) <= 0: + a[k] = lefthalf[i] + i = i + 1 + else: + a[k] = righthalf[j] + j = j + 1 + k = k + 1 - def __ge__(self, other): - return git_cmp(self.obj, other.obj) >= 0 + while i < len(lefthalf): + a[k] = lefthalf[i] + i = i + 1 + k = k + 1 - def __ne__(self, other): - return git_cmp(self.obj, other.obj) != 0 + while j < len(righthalf): + a[k] = righthalf[j] + j = j + 1 + k = k + 1 class TreeModifier(object): @@ -90,10 +99,7 @@ class TreeModifier(object): It may be called several times, but be aware that each call will cause a sort operation :return self:""" - if PY3: - self._cache.sort(key=CmpToKey) - else: - self._cache.sort(cmp=git_cmp) + merge_sort(self._cache, git_cmp) return self #} END interface diff --git a/git/test/test_tree.py b/git/test/test_tree.py index 5e94e70b..a7cdd9c6 100644 --- a/git/test/test_tree.py +++ b/git/test/test_tree.py @@ -77,30 +77,10 @@ class TestTree(TestBase): # del again, its fine del(mod[invalid_name]) - # SPECIAL ORDERING ! - # Add items which should sort differently from standard alum sort order - mod.add(hexsha, Tree.blob_id << 12, 'fild') - mod.add(hexsha, Tree.blob_id << 12, 'file') - mod.add(hexsha, Tree.blob_id << 12, 'file.second') - mod.add(hexsha, Tree.blob_id << 12, 'filf') - - def names_in_mod_cache(): - return [t[2] for t in mod._cache] - - def chunk_from(a, name, size): - index = a.index(name) - return a[index:index + size] - - assert chunk_from(names_in_mod_cache(), 'fild', 4) == ['fild', 'file', 'file.second', - 'filf'] - # have added one item, we are done mod.set_done() mod.set_done() # multiple times are okay - assert chunk_from(names_in_mod_cache(), 'fild', 4) == ['fild', 'file.second', 'file', - 'filf'] - # serialize, its different now stream = BytesIO() testtree._serialize(stream) @@ -114,6 +94,41 @@ class TestTree(TestBase): assert invalid_name not in testtree # END for each item in tree + def test_tree_modifier_ordering(self): + hexsha = '6c1faef799095f3990e9970bc2cb10aa0221cf9c' + roottree = self.rorepo.tree(hexsha) + blob_mode = Tree.blob_id << 12 + tree_mode = Tree.tree_id << 12 + + files_in_desired_order = [ + (blob_mode, '_.htaccess'), + (tree_mode, 'fileadmin'), + (blob_mode, 'index.php'), + (tree_mode, 'typo3'), + (tree_mode, 'typo3_src-6.2.12'), + (tree_mode, 'typo3_src'), + (blob_mode, 'typo3cms'), + (tree_mode, 'typo3conf'), + (tree_mode, 'uploads'), + ] + mod = roottree.cache + for (file_mode, file_name) in files_in_desired_order: + mod.add(hexsha, file_mode, file_name) + # end for each file + + def file_names_in_order(): + return [t[1] for t in files_in_desired_order] + + def names_in_mod_cache(): + a = [t[2] for t in mod._cache] + here = file_names_in_order() + return [e for e in a if e in here] + + assert names_in_mod_cache() == file_names_in_order(), 'add() keeps order' + + mod.set_done() + assert names_in_mod_cache() == file_names_in_order(), 'set_done() performs git-sorting' + def test_traverse(self): root = self.rorepo.tree('0.1.6') num_recursive = 0 |