# Path: tutelary/wildtree.py
# class WildTree(MutableMapping):
#     """
#     Data structure for mapping between segmented paths
#     (e.g. ``a/b/c/d``) and values, allowing for wildcards
#     (e.g. ``a/*/c/*``), where later key path insertions override
#     earlier ones.
# 
#     Provides JSON serialisation (via ``to_json()``) and deserialisation
#     (via constructor).
# 
#     """
#     def __init__(self, json=None):
#         """
#         By default, all new ``WildTree`` objects are empty.  They can also
#         be deserialised from a JSON representation.  We store the
#         optional value at the endpoint of the path to this node, plus
#         a list of subtrees.  Each subtree is a pair whose first
#         element is a key value (which may be a ``*`` wildcard) and
#         whose second element is a ``WildTree``.
# 
#         """
#         if json is None:
#             self.root = {'item': None, 'subtrees': []}
#         else:
#             self.root = loads(json)
# 
#     def __repr__(self):
#         return pformat(self.root)
# 
#     def to_json(self):
#         """
#         Serialisation to JSON.
#         """
#         return dumps(self.root)
# 
#     def __contains__(self, key):
#         """
#         Exact path membership: wildcards must be matched explicitly.
#         """
#         node = self.root
#         while len(key) > 0:
#             head, key = key[0], key[1:]
#             found = False
#             for st in node['subtrees']:
#                 if st[0] == head:
#                     found = True
#                     node = st[1]
#                     break
#             if not found:
#                 return False
#         return node['item'] is not None
# 
#     def __len__(self):
#         """
#         Effective number of keys in the tree.  Note that inserting keys
#         that override other keys leads to the overridden keys being
#         purged from the tree, so the key count does not necessarily
#         increase monotonically as keys are inserted.
# 
#         """
#         def _len_help(tree):
#             n = sum(_len_help(t[1]) for t in tree['subtrees'])
#             return n + 1 if tree['item'] is not None else n
#         return _len_help(self.root)
# 
#     def __iter__(self):
#         """
#         Iterate over keys in the tree in "domination order".
#         """
#         def _iter_help(tree):
#             if tree['item'] is not None:
#                 yield ()
#             for st in tree['subtrees']:
#                 for tail in _iter_help(st[1]):
#                     yield (st[0],) + tail
#         yield from _iter_help(self.root)
# 
#     def __getitem__(self, key):
#         """
#         Key lookup with wildcards.
#         """
#         return find_in_tree(self.root, key)[0]
# 
#     def __setitem__(self, key, value):
#         """
#         Insert a new key path, potentially overriding and hence purging
#         existing key paths.
# 
#         """
#         self._purge_unreachable(key)
#         node = self.root
#         while len(key) > 0:
#             found = False
#             for st in node['subtrees']:
#                 if st[0] == key[0]:
#                     found = True
#                     node = st[1]
#                     break
#                 elif st[0] == '*':
#                     break
#             if not found:
#                 default = {'item': None, 'subtrees': []}
#                 node['subtrees'].insert(0, (key[0], default))
#                 node = default
#             key = key[1:]
#         node['item'] = value
# 
#     def __delitem__(self, key):
#         """
#         Key deletion: wildcards must be matched explicitly.
#         """
#         _, idxs = find_in_tree(self.root, key, perfect=True)
#         del_by_idx(self.root, idxs)
# 
#     def find(self, key, perfect=False):
#         """
#         Find a key path in the tree, matching wildcards.  Return value for
#         key, along with index path through subtree lists to the result.  Throw
#         ``KeyError`` if the key path doesn't exist in the tree.
# 
#         """
#         return find_in_tree(self.root, key, perfect)
# 
#     def _purge_unreachable(self, key):
#         """
#         Purge unreachable dominated key paths before inserting a new key
#         path.
# 
#         """
#         dels = []
#         for p in self:
#             if dominates(key, p):
#                 dels.append(p)
#         for k in dels:
#             _, idxs = find_in_tree(self.root, k, perfect=True)
#             del_by_idx(self.root, idxs)


import pytest
from tutelary.wildtree import WildTree


def test_wildtree_1():
    t = WildTree()
    t[('a', 'b', 'c')] = 1
    t[('a', 'b', 'd')] = 2
    t[('a', 'b', 'e')] = 3
    assert len(t) == 3
    assert ('a', 'b', 'c') in t
    assert ('a', 'b', 'x') not in t
    assert t[('a', 'b', 'c')] == 1
    assert t[('a', 'b', 'd')] == 2
    assert t[('a', 'b', 'e')] == 3
    del t[('a', 'b', 'e')]
    assert ('a', 'b', 'e') not in t
    assert t.find(('a', 'b', 'd'))[0] == 2
    with pytest.raises(KeyError):
        assert t[('a', 'c', 'e')] == 1

# Path: tutelary/wildtree.py
# class WildTree(MutableMapping):
#     """
#     Data structure for mapping between segmented paths
#     (e.g. ``a/b/c/d``) and values, allowing for wildcards
#     (e.g. ``a/*/c/*``), where later key path insertions override
#     earlier ones.
# 
#     Provides JSON serialisation (via ``to_json()``) and deserialisation
#     (via constructor).
# 
#     """
#     def __init__(self, json=None):
#         """
#         By default, all new ``WildTree`` objects are empty.  They can also
#         be deserialised from a JSON representation.  We store the
#         optional value at the endpoint of the path to this node, plus
#         a list of subtrees.  Each subtree is a pair whose first
#         element is a key value (which may be a ``*`` wildcard) and
#         whose second element is a ``WildTree``.
# 
#         """
#         if json is None:
#             self.root = {'item': None, 'subtrees': []}
#         else:
#             self.root = loads(json)
# 
#     def __repr__(self):
#         return pformat(self.root)
# 
#     def to_json(self):
#         """
#         Serialisation to JSON.
#         """
#         return dumps(self.root)
# 
#     def __contains__(self, key):
#         """
#         Exact path membership: wildcards must be matched explicitly.
#         """
#         node = self.root
#         while len(key) > 0:
#             head, key = key[0], key[1:]
#             found = False
#             for st in node['subtrees']:
#                 if st[0] == head:
#                     found = True
#                     node = st[1]
#                     break
#             if not found:
#                 return False
#         return node['item'] is not None
# 
#     def __len__(self):
#         """
#         Effective number of keys in the tree.  Note that inserting keys
#         that override other keys leads to the overridden keys being
#         purged from the tree, so the key count does not necessarily
#         increase monotonically as keys are inserted.
# 
#         """
#         def _len_help(tree):
#             n = sum(_len_help(t[1]) for t in tree['subtrees'])
#             return n + 1 if tree['item'] is not None else n
#         return _len_help(self.root)
# 
#     def __iter__(self):
#         """
#         Iterate over keys in the tree in "domination order".
#         """
#         def _iter_help(tree):
#             if tree['item'] is not None:
#                 yield ()
#             for st in tree['subtrees']:
#                 for tail in _iter_help(st[1]):
#                     yield (st[0],) + tail
#         yield from _iter_help(self.root)
# 
#     def __getitem__(self, key):
#         """
#         Key lookup with wildcards.
#         """
#         return find_in_tree(self.root, key)[0]
# 
#     def __setitem__(self, key, value):
#         """
#         Insert a new key path, potentially overriding and hence purging
#         existing key paths.
# 
#         """
#         self._purge_unreachable(key)
#         node = self.root
#         while len(key) > 0:
#             found = False
#             for st in node['subtrees']:
#                 if st[0] == key[0]:
#                     found = True
#                     node = st[1]
#                     break
#                 elif st[0] == '*':
#                     break
#             if not found:
#                 default = {'item': None, 'subtrees': []}
#                 node['subtrees'].insert(0, (key[0], default))
#                 node = default
#             key = key[1:]
#         node['item'] = value
# 
#     def __delitem__(self, key):
#         """
#         Key deletion: wildcards must be matched explicitly.
#         """
#         _, idxs = find_in_tree(self.root, key, perfect=True)
#         del_by_idx(self.root, idxs)
# 
#     def find(self, key, perfect=False):
#         """
#         Find a key path in the tree, matching wildcards.  Return value for
#         key, along with index path through subtree lists to the result.  Throw
#         ``KeyError`` if the key path doesn't exist in the tree.
# 
#         """
#         return find_in_tree(self.root, key, perfect)
# 
#     def _purge_unreachable(self, key):
#         """
#         Purge unreachable dominated key paths before inserting a new key
#         path.
# 
#         """
#         dels = []
#         for p in self:
#             if dominates(key, p):
#                 dels.append(p)
#         for k in dels:
#             _, idxs = find_in_tree(self.root, k, perfect=True)
#             del_by_idx(self.root, idxs)


# Path: tests/test_wildtree.py
import pytest
from tutelary.wildtree import WildTree



def test_wildtree_1():
    t = WildTree()
    t[('a', 'b', 'c')] = 1
    t[('a', 'b', 'd')] = 2
    t[('a', 'b', 'e')] = 3
    assert len(t) == 3
    assert ('a', 'b', 'c') in t
    assert ('a', 'b', 'x') not in t
    assert t[('a', 'b', 'c')] == 1
    assert t[('a', 'b', 'd')] == 2
    assert t[('a', 'b', 'e')] == 3
    del t[('a', 'b', 'e')]
    assert ('a', 'b', 'e') not in t
    assert t.find(('a', 'b', 'd'))[0] == 2
    with pytest.raises(KeyError):
        assert t[('a', 'c', 'e')] == 1

    assert WildTree(json=t.to_json()) == t