diff options
| -rw-r--r-- | obnamlib/__init__.py | 3 | ||||
| -rw-r--r-- | obnamlib/fmt_ga/__init__.py | 3 | ||||
| -rw-r--r-- | obnamlib/fmt_ga/leaf_list.py | 60 | ||||
| -rw-r--r-- | obnamlib/fmt_ga/leaf_list_tests.py | 119 |
4 files changed, 183 insertions, 2 deletions
diff --git a/obnamlib/__init__.py b/obnamlib/__init__.py index bd72f041..1c7ae9ae 100644 --- a/obnamlib/__init__.py +++ b/obnamlib/__init__.py @@ -1,4 +1,4 @@ -# Copyright (C) 2009-2016 Lars Wirzenius +# Copyright (C) 2009-2017 Lars Wirzenius # # This program is free software: you can redistribute it and/or modify # it under the terms of the GNU General Public License as published by @@ -190,6 +190,7 @@ from .fmt_ga import ( LeafStore, CowLeaf, CowTree, + LeafList, ) diff --git a/obnamlib/fmt_ga/__init__.py b/obnamlib/fmt_ga/__init__.py index 8797948a..5803cbe1 100644 --- a/obnamlib/fmt_ga/__init__.py +++ b/obnamlib/fmt_ga/__init__.py @@ -1,4 +1,4 @@ -# Copyright 2015-2016 Lars Wirzenius +# Copyright 2015-2017 Lars Wirzenius # # This program is free software: you can redistribute it and/or modify # it under the terms of the GNU General Public License as published by @@ -19,6 +19,7 @@ from .client_list import GAClientList from .chunk_store import GAChunkStore from .leaf_store import InMemoryLeafStore, LeafStore from .leaf import CowLeaf +from .leaf_list import LeafList from .cowtree import CowTree from .indexes import GAChunkIndexes from .dirobj import GADirectory, GAImmutableError, create_gadirectory_from_dict diff --git a/obnamlib/fmt_ga/leaf_list.py b/obnamlib/fmt_ga/leaf_list.py new file mode 100644 index 00000000..11f0db21 --- /dev/null +++ b/obnamlib/fmt_ga/leaf_list.py @@ -0,0 +1,60 @@ +# Copyright 2016-2017 Lars Wirzenius +# +# This program is free software: you can redistribute it and/or modify +# it under the terms of the GNU General Public License as published by +# the Free Software Foundation, either version 3 of the License, or +# (at your option) any later version. +# +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU General Public License for more details. +# +# You should have received a copy of the GNU General Public License +# along with this program. If not, see <http://www.gnu.org/licenses/>. +# +# =*= License: GPL-3+ =*= + + +class LeafList(object): + + def __init__(self): + self._leaves = [] + + def serialise(self): + return self._leaves + + @classmethod + def unserialise(cls, serialised): + ll = LeafList() + for leaf_info in serialised: + ll.add( + leaf_info['leaf_id'], + leaf_info['first_key'], + leaf_info['last_key'] + ) + return ll + + def __len__(self): + return len(self._leaves) + + def leaves(self): + return [leaf_info['leaf_id'] for leaf_info in self._leaves] + + def add(self, leaf_id, first_key, last_key): + if any(self.find_leaf(k) for k in [first_key, last_key]): + raise Exception( + 'Overlapping key range {}..{}'.format(first_key, last_key)) + + self._leaves.append({ + 'first_key': first_key, + 'last_key': last_key, + 'leaf_id': leaf_id, + }) + self._leaves.sort(key=lambda x: (x['first_key'], x['last_key'])) + + def find_leaf(self, key): + for leaf_info in self._leaves: + if leaf_info['first_key'] <= key <= leaf_info['last_key']: + return leaf_info['leaf_id'] + return None diff --git a/obnamlib/fmt_ga/leaf_list_tests.py b/obnamlib/fmt_ga/leaf_list_tests.py new file mode 100644 index 00000000..ad9541e9 --- /dev/null +++ b/obnamlib/fmt_ga/leaf_list_tests.py @@ -0,0 +1,119 @@ +# Copyright 2017 Lars Wirzenius +# +# This program is free software: you can redistribute it and/or modify +# it under the terms of the GNU General Public License as published by +# the Free Software Foundation, either version 3 of the License, or +# (at your option) any later version. +# +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU General Public License for more details. +# +# You should have received a copy of the GNU General Public License +# along with this program. If not, see <http://www.gnu.org/licenses/>. +# +# =*= License: GPL-3+ =*= + + +import unittest + + +import obnamlib + + +class LeafListTests(unittest.TestCase): + + def test_is_empty_initially(self): + ll = obnamlib.LeafList() + self.assertEqual(len(ll), 0) + + def test_adds_leaf(self): + first_key = 'aaaa' + last_key = 'bbbb' + leaf_id = 'leaf-1' + + ll = obnamlib.LeafList() + ll.add(leaf_id, first_key, last_key) + self.assertEqual(len(ll), 1) + self.assertEqual(ll.leaves(), [leaf_id]) + + def test_adding_overlapping_leaf_raises_exception(self): + first_key = 'a' + last_key = 'b' + leaf_id_1 = 'leaf-1' + leaf_id_2 = 'leaf-2' + + ll = obnamlib.LeafList() + ll.add(leaf_id_1, first_key, last_key) + + with self.assertRaises(Exception): + ll.add(leaf_id_2, first_key, last_key) + + def test_adds_second_leaf(self): + leaf1 = ('leaf-1', 'a', 'b') + leaf2 = ('leaf-2', 'c', 'd') + + ll = obnamlib.LeafList() + # Note that we insert in reverse order to make sure .add puts things + # into the right order. + ll.add(*leaf2) + ll.add(*leaf1) + + self.assertEqual(len(ll), 2) + self.assertEqual(ll.leaves(), [leaf1[0], leaf2[0]]) + + def test_adds_third_leaf_in_the_middle(self): + leaf1 = ('leaf-1', 'a', 'b') + leaf2 = ('leaf-2', 'e', 'f') + leaf3 = ('leaf-2', 'c', 'd') + + ll = obnamlib.LeafList() + ll.add(*leaf1) + ll.add(*leaf3) + ll.add(*leaf2) + + self.assertEqual(len(ll), 3) + self.assertEqual(ll.leaves(), [leaf1[0], leaf2[0], leaf3[0]]) + + def test_finds_correct_leaf(self): + leaf1 = ('leaf-1', 'a', 'b') + leaf2 = ('leaf-2', 'c', 'd') + leaf3 = ('leaf-3', 'e', 'f') + + ll = obnamlib.LeafList() + ll.add(*leaf1) + ll.add(*leaf3) + ll.add(*leaf2) + + found = ll.find_leaf('aaa') + self.assertNotEqual(found, None) + self.assertEqual(found, leaf1[0]) + + def test_finds_none(self): + leaf1 = ('leaf-1', 'a', 'b') + leaf2 = ('leaf-2', 'c', 'd') + leaf3 = ('leaf-3', 'e', 'f') + + ll = obnamlib.LeafList() + ll.add(*leaf1) + ll.add(*leaf3) + ll.add(*leaf2) + + found = ll.find_leaf('z') + self.assertEqual(found, None) + + def test_serialisation_roundtrip(self): + leaf1 = ('leaf-1', 'a', 'b') + leaf2 = ('leaf-2', 'c', 'd') + leaf3 = ('leaf-3', 'e', 'f') + + orig = obnamlib.LeafList() + orig.add(*leaf1) + orig.add(*leaf3) + orig.add(*leaf2) + + serialised = orig.serialise() + new = obnamlib.LeafList.unserialise(serialised) + + self.assertEqual(orig.leaves(), new.leaves()) |