test_trie.py 4.84 KB
Newer Older
Jeroen F.J. Laros's avatar
Jeroen F.J. Laros committed
1
"""Tests for the trie library.
2 3 4 5 6 7 8 9 10 11 12
"""
#from __future__ import (
#    absolute_import, division, print_function, unicode_literals)
#from future.builtins import str, zip

from dict_trie import Trie

class TestTrie(object):
    def setup(self):
        self._trie = Trie(['abc', 'abd', 'test', 'te'])

Jeroen F.J. Laros's avatar
Jeroen F.J. Laros committed
13 14 15
    def test_empty(self):
        assert Trie().root == {}

Jeroen F.J. Laros's avatar
Jeroen F.J. Laros committed
16
    def test_root(self):
17 18 19 20 21 22 23 24 25
        assert self._trie.root == {
            'a': {
                'b': {
                    'c': {'': {}},
                    'd': {'': {}}}},
            't': {'e': {
                '': {},
                's': {'t': {'': {}}}}}}

Jeroen F.J. Laros's avatar
Jeroen F.J. Laros committed
26
    def test_word_present(self):
27 28
        assert 'abc' in self._trie

Jeroen F.J. Laros's avatar
Jeroen F.J. Laros committed
29 30 31 32 33 34 35 36 37 38 39
    def test_word_absent(self):
        assert 'abx' not in self._trie

    def test_empty_string_present(self):
        assert '' in Trie([''])

    def test_empty_string_absent(self):
        assert '' not in self._trie

    def test_prefix_absent_as_word(self):
        assert 'ab' not in self._trie
40

Jeroen F.J. Laros's avatar
Jeroen F.J. Laros committed
41 42
    def test_too_long_absent(self):
        assert 'abcd' not in self._trie
43

Jeroen F.J. Laros's avatar
Jeroen F.J. Laros committed
44
    def test_prefix_present(self):
45 46
        assert self._trie.has_prefix('ab')

Jeroen F.J. Laros's avatar
Jeroen F.J. Laros committed
47 48 49
    def test_prefix_absent(self):
        assert not self._trie.has_prefix('ac')

50 51 52
    def test_word_is_prefix(self):
        assert self._trie.has_prefix('abc')

Jeroen F.J. Laros's avatar
Jeroen F.J. Laros committed
53
    def test_too_long_prefix_absent(self):
54 55 56 57
        assert not self._trie.has_prefix('abcd')

    def test_prefix_order(self):
        assert Trie(['test', 'te']).root == Trie(['te', 'test']).root
58

Jeroen F.J. Laros's avatar
Jeroen F.J. Laros committed
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 87 88 89 90 91 92 93 94 95 96
    def test_add(self):
        self._trie.add('abx')
        assert 'abx' in self._trie

    def test_remove_present(self):
        assert self._trie.remove('test')
        assert 'test' not in self._trie
        assert 'te' in self._trie

    def test_remove_prefix_present(self):
        assert self._trie.remove('te')
        assert 'te' not in self._trie
        assert 'test' in self._trie

    def test_remove_absent(self):
        assert not self._trie.remove('xxxx')

    def test_remove_prefix_absent(self):
        assert not self._trie.remove('ab')

    def test_iter(self):
        assert list(self._trie) == ['abc', 'abd', 'te', 'test']

    def test_fill(self):
        trie = Trie()
        trie.fill(('a', 'b'), 3)
        assert list(trie) == [
            'aaa', 'aab', 'aba', 'abb', 'baa', 'bab', 'bba', 'bbb']

    def test_all_hamming_1_perfect(self):
        assert list(self._trie.all_hamming('abc', 1)) == ['abc', 'abd']

    def test_all_hamming_1_not_perfect(self):
        assert list(self._trie.all_hamming('abx', 1)) == ['abc', 'abd']

    def test_all_hamming_1_no_match(self):
        assert not list(self._trie.all_hamming('xbx', 1))

97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123
    def test_hamming_0_no_prefix(self):
        assert self._trie.hamming('ab', 0) == ''

    def test_hamming_0_match(self):
        assert self._trie.hamming('abc', 0) == 'abc'

    def test_hamming_0_match_sub(self):
        assert self._trie.hamming('te', 0) == 'te'

    def test_hamming_0_too_long(self):
        assert self._trie.hamming('abcd', 0) == ''

    def test_hamming_1_match(self):
        assert self._trie.hamming('abc', 1) == 'abc'

    def test_hamming_1_match_sub(self):
        assert self._trie.hamming('te', 1) == 'te'

    def test_hamming_1_match_1(self):
        assert self._trie.hamming('xbc', 1) == 'abc'

    def test_hamming_1_match_2(self):
        assert self._trie.hamming('axc', 1) == 'abc'

    def test_hamming_1_match_3(self):
        assert self._trie.hamming('abx', 1) == 'abc'

124 125 126
    def test_hamming_1_match_4(self):
        assert self._trie.hamming('abd', 1) == 'abc'

127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143
    def test_hamming_1_no_prefix(self):
        assert self._trie.hamming('ab', 1) == ''

    def test_hamming_1_too_long(self):
        assert self._trie.hamming('abcd', 1) == ''

    def test_hamming_1_match_sub_1(self):
        assert self._trie.hamming('tx', 1) == 'te'

    def test_hamming_1_match_sub_2(self):
        assert self._trie.hamming('xe', 1) == 'te'

    def test_hamming_1_mismatch(self):
        assert self._trie.hamming('txxt', 1) == ''

    def test_hamming_2_match(self):
        assert self._trie.hamming('txxt', 2) == 'test'
144 145 146

    def test_best_hamming_match(self):
        assert self._trie.best_hamming('abd', 1) == 'abd'
147

Jeroen F.J. Laros's avatar
Jeroen F.J. Laros committed
148 149 150
    def test_all_levenshtein_1_not_perfect(self):
        assert list(self._trie.all_levenshtein('tes', 1)) == ['te', 'test']

151 152 153 154 155 156 157 158 159 160 161 162
    def test_levenshtein_0_match_1(self):
        assert self._trie.levenshtein('abc', 0) == 'abc'

    def test_levenshtein_0_match_2(self):
        assert self._trie.levenshtein('te', 0) == 'te'

    def test_levenshtein_1_subst(self):
        assert self._trie.levenshtein('axc', 1) == 'abc'

    def test_levenshtein_1_del(self):
        assert self._trie.levenshtein('ac', 1) == 'abc'

163 164 165
    def test_levenshtein_1_prefex(self):
        assert self._trie.levenshtein('ab', 1) == 'abc'

166 167
    def test_levenshtein_1_ins(self):
        assert self._trie.levenshtein('abbc', 1) == 'abc'