diff options
author | Ian Stapleton Cordasco <graffatcolmingov@gmail.com> | 2018-09-19 16:33:54 -0500 |
---|---|---|
committer | GitHub <noreply@github.com> | 2018-09-19 16:33:54 -0500 |
commit | e03fe75a0e3bcd55c545e94aa6ced0b4bb689f5a (patch) | |
tree | 12cf3ed26986e9ff025b9cb2f66bac8d0a169b2c | |
parent | 86f495286ba47fe825878c32d7fa3ea4a1c10c87 (diff) | |
parent | 0823f1131022d1bdf89a083dbe060fe110ea6cd6 (diff) | |
download | uritemplates-e03fe75a0e3bcd55c545e94aa6ced0b4bb689f5a.tar.gz |
Merge pull request #37 from cloudsmith-io/bugfix-ordering
Make variable ordering deterministic
-rw-r--r-- | uritemplate/api.py | 4 | ||||
-rw-r--r-- | uritemplate/orderedset.py | 86 | ||||
-rw-r--r-- | uritemplate/template.py | 6 |
3 files changed, 93 insertions, 3 deletions
diff --git a/uritemplate/api.py b/uritemplate/api.py index 37c7c45..5ad2815 100644 --- a/uritemplate/api.py +++ b/uritemplate/api.py @@ -6,6 +6,8 @@ uritemplate.api This module contains the very simple API provided by uritemplate. """ + +from uritemplate.orderedset import OrderedSet from uritemplate.template import URITemplate @@ -68,4 +70,4 @@ def variables(uri): # => {'username', 'repository'} """ - return set(URITemplate(uri).variable_names) + return OrderedSet(URITemplate(uri).variable_names) diff --git a/uritemplate/orderedset.py b/uritemplate/orderedset.py new file mode 100644 index 0000000..7a9d33e --- /dev/null +++ b/uritemplate/orderedset.py @@ -0,0 +1,86 @@ +# From: https://github.com/ActiveState/code/blob/master/recipes/Python/576696_OrderedSet_with_Weakrefs/ # noqa + +import collections +from weakref import proxy + + +class Link(object): + __slots__ = 'prev', 'next', 'key', '__weakref__' + + +class OrderedSet(collections.MutableSet): + 'Set the remembers the order elements were added' + # Big-O running times for all methods are the same as for regular sets. + # The internal self.__map dictionary maps keys to links in a doubly linked + # list. The circular doubly linked list starts and ends with a sentinel + # element. The sentinel element never gets deleted (this simplifies the + # algorithm). The prev/next links are weakref proxies (to prevent circular + # references). Individual links are kept alive by the hard reference in + # self.__map. Those hard references disappear when a key is deleted from + # an OrderedSet. + + def __init__(self, iterable=None): + self.__root = root = Link() # sentinel node for doubly linked list + root.prev = root.next = root + self.__map = {} # key --> link + if iterable is not None: + self |= iterable + + def __len__(self): + return len(self.__map) + + def __contains__(self, key): + return key in self.__map + + def add(self, key): + # Store new key in a new link at the end of the linked list + if key not in self.__map: + self.__map[key] = link = Link() + root = self.__root + last = root.prev + link.prev, link.next, link.key = last, root, key + last.next = root.prev = proxy(link) + + def discard(self, key): + # Remove an existing item using self.__map to find the link which is + # then removed by updating the links in the predecessor and successors. + if key in self.__map: + link = self.__map.pop(key) + link.prev.next = link.next + link.next.prev = link.prev + + def __iter__(self): + # Traverse the linked list in order. + root = self.__root + curr = root.next + while curr is not root: + yield curr.key + curr = curr.next + + def __reversed__(self): + # Traverse the linked list in reverse order. + root = self.__root + curr = root.prev + while curr is not root: + yield curr.key + curr = curr.prev + + def pop(self, last=True): + if not self: + raise KeyError('set is empty') + key = next(reversed(self)) if last else next(iter(self)) + self.discard(key) + return key + + def __repr__(self): + if not self: + return '%s()' % (self.__class__.__name__,) + return '%s(%r)' % (self.__class__.__name__, list(self)) + + def __str__(self): + return self.__repr__() + + def __eq__(self, other): + if isinstance(other, OrderedSet): + return len(self) == len(other) and list(self) == list(other) + return not self.isdisjoint(other) diff --git a/uritemplate/template.py b/uritemplate/template.py index ceca8eb..0df0da6 100644 --- a/uritemplate/template.py +++ b/uritemplate/template.py @@ -16,6 +16,7 @@ What do you do? """ import re +from uritemplate.orderedset import OrderedSet from uritemplate.variable import URIVariable template_re = re.compile('{([^}]+)}') @@ -71,9 +72,10 @@ class URITemplate(object): URIVariable(m.groups()[0]) for m in template_re.finditer(self.uri) ] #: A set of variable names in the URI. - self.variable_names = set() + self.variable_names = OrderedSet() for variable in self.variables: - self.variable_names.update(variable.variable_names) + for name in variable.variable_names: + self.variable_names.add(name) def __repr__(self): return 'URITemplate("%s")' % self |