diff options
author | Lee Skillen <lskillen@cloudsmith.io> | 2018-01-31 16:21:43 +0000 |
---|---|---|
committer | Lee Skillen <lskillen@cloudsmith.io> | 2018-09-10 00:40:45 +0100 |
commit | 12c9fdf6cc413d2b227302181d20456361d94e3b (patch) | |
tree | 4ef27fa132be344b3d90260309f443eb09b0520d | |
parent | 86f495286ba47fe825878c32d7fa3ea4a1c10c87 (diff) | |
download | uritemplates-12c9fdf6cc413d2b227302181d20456361d94e3b.tar.gz |
Make variable ordering deterministic
-rw-r--r-- | uritemplate/api.py | 4 | ||||
-rw-r--r-- | uritemplate/orderedset.py | 83 | ||||
-rw-r--r-- | uritemplate/template.py | 6 |
3 files changed, 90 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..94f4733 --- /dev/null +++ b/uritemplate/orderedset.py @@ -0,0 +1,83 @@ +# From: https://github.com/ActiveState/code/blob/master/recipes/Python/576696_OrderedSet_with_Weakrefs/ + +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 |