Newer
Older
# -*- coding: utf-8 -*-
# Copyright 2020 The Matrix.org Foundation C.I.C.
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
# http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
Erik Johnston
committed
from typing import Dict, List
from synapse.util.iterutils import chunk_seq, sorted_topologically
from tests.unittest import TestCase
class ChunkSeqTests(TestCase):
def test_short_seq(self):
parts = chunk_seq("123", 8)
self.assertEqual(
list(parts), ["123"],
)
def test_long_seq(self):
parts = chunk_seq("abcdefghijklmnop", 8)
self.assertEqual(
list(parts), ["abcdefgh", "ijklmnop"],
)
def test_uneven_parts(self):
parts = chunk_seq("abcdefghijklmnop", 5)
self.assertEqual(
list(parts), ["abcde", "fghij", "klmno", "p"],
)
def test_empty_input(self):
parts = chunk_seq([], 5)
self.assertEqual(
list(parts), [],
)
Erik Johnston
committed
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
class SortTopologically(TestCase):
def test_empty(self):
"Test that an empty graph works correctly"
graph = {} # type: Dict[int, List[int]]
self.assertEqual(list(sorted_topologically([], graph)), [])
def test_disconnected(self):
"Test that a graph with no edges work"
graph = {1: [], 2: []} # type: Dict[int, List[int]]
# For disconnected nodes the output is simply sorted.
self.assertEqual(list(sorted_topologically([1, 2], graph)), [1, 2])
def test_linear(self):
"Test that a simple `4 -> 3 -> 2 -> 1` graph works"
graph = {1: [], 2: [1], 3: [2], 4: [3]} # type: Dict[int, List[int]]
self.assertEqual(list(sorted_topologically([4, 3, 2, 1], graph)), [1, 2, 3, 4])
def test_subset(self):
"Test that only sorting a subset of the graph works"
graph = {1: [], 2: [1], 3: [2], 4: [3]} # type: Dict[int, List[int]]
self.assertEqual(list(sorted_topologically([4, 3], graph)), [3, 4])
def test_fork(self):
"Test that a forked graph works"
graph = {1: [], 2: [1], 3: [1], 4: [2, 3]} # type: Dict[int, List[int]]
# Valid orderings are `[1, 3, 2, 4]` or `[1, 2, 3, 4]`, but we should
# always get the same one.
self.assertEqual(list(sorted_topologically([4, 3, 2, 1], graph)), [1, 2, 3, 4])