Doubly linked list with reverse flag

Updated TrustyTony 0 Tallied Votes 311 Views Share

Here is code, which you can play with before installing and using the superior blist package from pypi. I did it as therapy after doing programming test answer using zillion of setters and getters. Motivation is basically to show why you should use properties after you need them and attribute access before that. The function of before and after links is exchangable, so you can do reversing of directions of double linked list by just sweeping through list and toggling the flag. If that quite a hackish feature would not be there we would not need to use property. Here it is done only to demostrate the ease of making attributes to properties afterwards.

def insert_ordered(at_me, new_dlist):
    """
    at_me: a DoublyLinked that is part of a doubly linked list
    new_dlist:  a DoublyLinked with no links 
    This procedure appropriately inserts new_dlist into the linked list that at_me is a part of.    
    """
    new_name = new_dlist.name
    while at_me.before and new_name <= at_me.name:
        at_me = at_me.before
    while at_me.after and at_me.after.name < new_name:
        at_me = at_me.after
    if at_me.before is None and new_name < at_me.name:
        new_dlist.after, at_me.before = at_me, new_dlist
    elif at_me.after is None and new_name > at_me.name:
        at_me.after, new_dlist.before = new_dlist, at_me
    else:
        if at_me.after:
            at_me.after.before = new_dlist
        new_dlist.before, new_dlist.after, at_me.after = at_me, at_me.after, new_dlist
    
def find_front(start):
    #return find_front(start.before) if start.before else start
    while start.before is not None:
        start = start.before
    return start
        
def find_end(start):
    #return find_front(start.before) if start.before else start
    while start.after is not None:
        start = start.after
    return start
        
def print_dl(here):
    print '<->'.join(find_front(here))

def link_check(start):
    here = find_front(start)
    while here.after:
        check = here
        here = here.after
        assert here.before == check, '%s before links inconsistent: %s != %s' % (
                                            here, here.before, check)
        assert here.name == check.name or (here.name > check.name) == (not here.reversed), '%s before name more than this word: %s < %s' % (here, here.name, check.name)

class DoublyLinked(object):
    def __init__(self, name, before=None, after=None):
        self.name = name
        self._before = before
        self._after = after
        self.reversed = False
    insert_ordered = insert_ordered
    find_front, find_end = find_front, find_end
    start_node, end_node = property(find_front), property(find_end)
    @property
    def before(self):
        return self._after if self.reversed else self._before
    @before.setter
    def before(self, value):
        if self.reversed:
            self._after = value
        else:
            self._before = value   
    @property
    def after(self):
        return self._before if self.reversed else self._after   
    @after.setter
    def after(self, value):
        if self.reversed:
            self._before = value
        else:
            self._after = value
    def reverse(self):
        node = self.find_front()
        while node is not None:
            node.reversed = not node.reversed
            # old node after is changed to before because of reverse, so we must use that
            node = node.before
    def __getitem__(self, n):
        if n >= 0:
            place = self.start_node
            reverse = False
        else:
            n = -n + 1
            reverse = True
            place = self.end_node
        for _ in range(n):
            try:
                place = place.after if not reverse else place.before
            except AttributeError as e:
                raise IndexError('Index out of bounds!')
        return place.name

    def __len__(self):
        return sum(1 for _ in self)

    def __iter__(self):
        here = self.start_node
        while here is not None:
            yield here.name
            here = here.after

    def find(self, value):
        for ind, v in enumerate(self.start_node):
            if v == value:
                return ind
            
    def __str__(self):
        return '%s <- %s -> %s' % (
            (self.name if self.before else None),
            self.name,
            (self.after.name  if self.after else None))
    def __repr__(self):
        return 'DoublyLinked(%r, %r, %r)' % (self.name,
                                             self.before.name if self.before else None,
                                             self.after.name if self.after else None)

if __name__ == '__main__':
    import random
    p = ['eric', 'andrew','fred', 'martha', 'ruth']
    p += random.sample(p, 2)
    random.shuffle(p)
    p = ['eda']*2 + p
    ##p = ['eda', 'eda', 'martha', 'andrew', 'ruth', 'andrew', 'eric', 'fred', 'ruth']
    for test in range(len(p)):
        s = iter(p)
        double_list = DoublyLinked(next(s))
        print_dl(double_list)
        for name in s:
            insert_ordered(double_list, DoublyLinked(name))
            print_dl(double_list)
        p.insert(0, p.pop())
        print ('='*30)
    double_list.reverse()
    print 'reversed'
    print_dl(double_list)
    print 'Name at %ith position is: %s' % (4, double_list[4])
    print 'Name at %ith position is: %s' % (-2, double_list[-2])
    double_list.reverse()
    link_check(double_list)
    print 'reversed back'
    print_dl(double_list)
    link_check(double_list)
    print 'Name at %ith position is: %s' % (4, double_list[4])
    for v in 'eda', 'dea':
        print "%r is in double_list: %s" % (v, v in double_list)
        print "index is %s" % (double_list.find(v))
    print 'Length of the list is', len(double_list)