Sorting without transitivity

[Anton Vredegoor]

Frank Niessink <frank at niessink.com> wrote:

>There is no indentation error. In Python, for loops can have an else
>clause. The else clause is executed if the for loop is completed.
>If the for loop is exited with a break statement the else clause is
>not performed.

Thanks. Years of programming in Basic must have clouded my mind.
However, now that the else clause is visible, the implementation below
seems more natural.

Anton


class TopList(list):
    ''' Topological list class. This class uses topological sort to
        sort its contents. List items should provide __lt__ and 
        __eq__ methods. '''
        
    def topSort(self):
        self[:] = [self.popMin() for i in range(len(self))]

    def popMin(self):
        return self.pop(self.findMin())

    def findMin(self):
        R = range(len(self))
        i = R.pop(0)
        while True:
            for j,k in enumerate(R):
                if self[k] < self[i]:
                    i = R.pop(j)
                    break
            else:
                return i
                
def test():
    T = TopList([3,2,1])
    T.topSort()
    print T

if __name__=='__main__':
    test()