Check if the iterator is sorted

Question

I have an iterator it , which I assume is already sorted, but I would like to throw an exception if that is not the case.

The data from the iterator is not stored in memory, so I do not want to use sorted() builtin, because AFAIK puts the entire iterator in the list.

The solution I'm using now is to wrap an iterator in a generator function as follows:

 def checkSorted(it): prev_v = it.next() yield prev_v for v in it: if v >= prev_v: yield v prev_v = v else: raise ValueError("Iterator is not sorted") 

So that I can use it as follows:

 myconsumer(checkSorted(it)) 

Does anyone know if there are better solutions?

I know that my solution works, but it seems rather strange to me (at least for me) to create my own module to perform such a trivial task. I am looking for a simple one liner or inline solution (if one exists)

Answer 1

Basically, your solution is almost as elegant as it turns out (you could, of course, put it in the service module if you find it generally useful). You could if you wanted it to use the infinity object to shorten the code a bit, but then you should also include a class definition that extends the code again (if you haven't entered a class definition):

 def checkSorted(it): prev = type("", (), {"__lt__": lambda a, b: False})() for x in it: if prev < x: raise ValueError("Not sorted") prev = x yield x 

The first line uses type to create the class first and then instantiate it. Objects of this class are compared less than anything (an infinity object).

The problem with executing a single-line interface is that you need to deal with three constructs: you need to update the state (assignment), throw an exception, and execute a loop. You can easily execute them with statements, but including them in oneliner will mean that you have to try to put the instructions on one line, which in turn will cause a problem with the loop and if -constructs.

If you want to put all this into an expression, you will have to use dirty tricks for this, it can be the assignment and cyclization of iterutils , and throwing can be done using the throw method in the generator (which can also be represented in the expression):

 imap( lambda i, j: (i >= j and j or (_ for _ in ()).throw(ValueError("Not sorted"))), *(lambda pre, it: (chain([type("", (), {"__ge__": lambda a, b: True})()], pre), it))(*tee(it))) 

The last it is the iterator you want to test, and the expression is evaluated by a validated iterator. I agree that it doesn’t look good and it’s not obvious what he is doing, but you asked for it (and I don’t think you wanted it).

Answer 2

As an alternative, I suggest using itertools.izip_longest (and zip_longest in python 3) to create a generator containing consecutive pairs:

You can use tee to create 2 independent iterators from the first iterable.

 from itertools import izip_longest,tee def checkSorted(it): pre,it=tee(it) next(it) for i,j in izip_longest(pre,it): if j: if i >= j: yield i else: raise ValueError("Iterator is not sorted") else : yield i 

Demo:

 it=iter([5,4,3,2,1]) print list(checkSorted(it)) [5, 4, 3, 2, 1] it=iter([5,4,3,2,3]) print list(checkSorted(it)) Traceback (most recent call last): File "/home/bluebird/Desktop/ex2.py", line 19, in <module> print list(checkSorted(it)) File "/home/bluebird/Desktop/ex2.py", line 10, in checkSorted raise ValueError("Iterator is not sorted") ValueError: Iterator is not sorted 

Note: in fact, I think there is no need to give your iterable values ​​if you already have them. Since a more elegant way, I suggest using the generator expression in the all function and returning the value bool:

 from itertools import izip,tee def checkSorted(it): pre,it=tee(it) next(it) return all(i>=j for i,j in izip(pre,it))