[Tutor] Set changing order of items?

[Danny Yoo]

On Fri, 19 Jan 2007, Adam Cripps wrote:

> I'm adding strings to a Set to prevent duplicates. However, the strings 
> are meant to be in the correct order. When I add the string to the Set, 
> the order seems to change (and I don't seem to be able to predict what 
> order they are in).


Hi Adam,

You can create your own data structure.  You don't have to work with raw 
data structures: you can make your own.


It sounds like you want a few operations from this data structure, which 
we'll call "UniqueList" for the moment:

     append(x): add x to the uniqueList if we don't already have seen it.

     elements(): return all the unique elements, in the order that we saw
                 them.

Does that sound ok, or do you need more operations?



We can even start writing test cases for this, even without writing 
implementation:

#############################################
def simple_test():
    ulist = UniqueList()
    ulist.append("a")
    ulist.append("b")
    ulist.append("b")
    ulist.append("c")
    assert ["a", "b", "c"] == ulist.elements()
#############################################

Would the behavior here be reasonable to you?



There's a naive way to implement this, which is:

##################################
class UniqueList:
     def __init__(self):
         self.elts = []

     def append(self, item):
         if item not in self.elts:
             self.elts.append(item)

     def elements(self):
         return self.elts
##################################


And now we can make instances of UniqueLists, and we can see that it 
passes our simple test function:

###############################################
>>> simple_test()
>>> 
>>> ulist = UniqueList()
>>> ulist.append("hello")
>>> ulist.append("hello")
>>> ulist.append("world")
>>> ulist.append("testing")
>>> ulist.append("hello")
>>> ulist.append("world")
>>> ulist
<__main__.UniqueList instance at 0xb7d1c3cc>
>>> ulist.elements()
['hello', 'world', 'testing']
###############################################


Would you be able to work with UniqueList here?  Would it do the job for 
you?

If not, then we should find out why.  Only after we get the functionality 
down should we think about efficiency.  It does us no good to make things 
fast if they don't do what you want.


Good luck to you!