Merge pull request #37 from cloudsmith-io/bugfix-ordering
Make variable ordering deterministic
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 @@
This module contains the very simple API provided by uritemplate.
"""
+
+from uritemplate.orderedset import OrderedSet
from uritemplate.template import URITemplate
@@ -68,4 +70,4 @@
# => {'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 @@
"""
import re
+from uritemplate.orderedset import OrderedSet
from uritemplate.variable import URIVariable
template_re = re.compile('{([^}]+)}')
@@ -71,9 +72,10 @@
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
