How can I tell if a structure in Python has order?

Question

I'm writing a set of test cases for users new to Python. One of the problems I've noticed with my tests is that its possible to get false positives. They may have gotten lucky and happened to give every element in the correct order, however they really should be using a structure that is ordered.

So far this is the best solution I could come up with.

self.assertTrue(isinstance(result, Sequence) or
                isinstance(result, GeneratorType) or
                callable(getattr(result, '__reversed__', False)))

However, I don't feel confident GeneratorType is really ordered, or that this test is comprehensive. I feel like there should be a better way to test for this. How do I test that a structure has order?

Answer 1

I think, it is very interesting guestion. There is no way in pure python (without utility code) to check if collection is ordered.

Let's go sequentially =)

To check Sequence or GeneratorType you can use collections.Iterable type.

>>>
>>> import collections
>>>
>>> result = [1,2,3,4,-1]
>>> isinstance(result, collections.Iterable)
True
>>>
>>> def generator_func(arg=10):
...     for i in xrange(arg):
...         yield i
...
>>>
>>> generator_func()
<generator object generator_func at 0x7f667c50f190>
>>>
>>> result = generator_func()
>>> isinstance(result, collections.Iterable)
True

But:

>>>
>>> result = {1,2,3,4,-1}
>>> isinstance(result, collections.Iterable)
True
>>>

It is bad case for you. Because:

>>> x = {1,2,3,-1}
>>> x
set([1, 2, 3, -1])
>>> [_ for _ in x]
[1, 2, 3, -1]
>>> x = {1,2,3,0}
>>> x
set([0, 1, 2, 3])
>>> [_ for _ in x]
[0, 1, 2, 3]
>>> import collections
>>> isinstance(x, collections.Iterable)
True
>>>

Of course for this case you should use a collections.Sequence only.

>>> result = {1,2,3,4,-1}
>>> isinstance(result, collections.Sequence)
False
>>> isinstance({1:2, 3:3}, collections.Sequence)
False
>>>

But:

>>> result = generator_func()
>>> isinstance(result, collections.Sequence)
False
>>> 

Thus, I think that an idea to check Sequence or GeneratorType is nice. Check this link:

• docs.python.org/2/library/collections.html

So:

>>> result = generator_func()
>>> isinstance(result, (collections.Sequence, collections.Iterator))
True
>>> result = [1,2,3,4,5]
>>> isinstance(result, (collections.Sequence, collections.Iterator))
True
>>> result = (1,2,3,4,5)
>>> isinstance(result, (collections.Sequence, collections.Iterator))
True
>>> result = {1,2,3,4,5}
>>> isinstance(result, (collections.Sequence, collections.Iterator))
False
>>> result = {1:1,2:2,3:3,4:4,5:5}
>>> isinstance(result, (collections.Sequence, collections.Iterator))
False
>>> 

Аbout order.

If you are not sure about order of items, I think you should check them explicitly.

«Explicit is better than implicit.»

>>>
>>> def order_check(result, order_rule = cmp_rule):
...     for item, next_item in zip(result, result[1:]):
...         if not order_rule(item, next_item):
...             return False
...     return True
...
>>> def cmp_rule(item, next_item):
...     if item < next_item:
...         return True
...     return False
...
>>>
>>> result = [1,2,3,4,5]
>>> order_check(result)
True
>>> result = [1,2,3,4,5,-1]
>>> order_check(result)
False
>>>

But, honestly, generators guarantee that the order would be the same as you generate in it.

Answer 2

You haven't entirely described what you mean by the property of having "order"; your "callable" is a good idea. I suggest that you read through the "dunder" (double underscore) methods to see whether one of them matches the definition you want. From what you've given us, I strongly suspect that __getitem__ is what you want. There is also the "ask forgiveness" method of setting a try-except block on the structure:

try:
    dummy = (_ for _ in result)
    has_order = True
except:
    has_order = False
return has_order