Data structure help, linked lists?

This is the place for queries that don't fit in any of the other categories.

Data structure help, linked lists?

Postby hrs » Fri Mar 15, 2013 11:38 pm

When you search for "python linked list" you'll find comments about how you shouldn't use them and just use the plain list type instead so maybe I'm over-complicating things but ...

I have an m*n nested list of nodes like this:
Code: Select all
B = Begin node, O = Middle node, E = End node

[[B, O, O, O, E],
 [B, O, O, O, E],
 [B, O, O, O, E],
 [B, O, O, O, E]]

The begin and end nodes are more or less defined and fixed, middle nodes are derived from surrounding nodes.
Eventually I need to have the following access patterns from the "current" node:
Code: Select all
P = previous, C = current, N = next
No = north, S = south

First row
P--C--N
  /
 /
PS

Middle rows
PNo No
 \  |
  \ |
   \|
 P--C--N
   /|
  / |
 /  |
PS  S


Last row
PNo No
 \  |
  \ |
   \|
 P--C--N

For now I'm working along each individual row only and I found something[1] that works nicely.
Code: Select all
class Node(object):
    def __init__(self, a, b, c):
        self.a = a
        self.b = b
        self.c = c

    def calculate_c(self, previous, next):
        self.c = (next.a - previous.a) / (next.b - previous.b)

def previous_and_next(some_iterable):
    prevs, items, nexts = tee(some_iterable, 3)
    prevs = chain([None], prevs)
    nexts = chain(islice(nexts, 1, None), [None])
    return izip(prevs, items, nexts)

for row in MyNestedListOfNodes:
    previous, current, next = previous_and_next(row)
    current.calculate_c(previous, next)

but I don't know how to extend that to the required access patterns listed above.

I could do something like this:
Code: Select all
for i, row in enumerate(MyList):
    for j, node in enumerate(row):
        # all kinds of index magic here
        # hoping it wont go out of range

but past experiments have shown that this will likely turn into an unreadable mess, especially when you read it back after a few months.

Do you have some advise on what data structure or method to use for this?


[1] http://stackoverflow.com/questions/1011 ... ide-a-loop
hrs
 
Posts: 86
Joined: Thu Feb 07, 2013 9:26 pm

Re: Data structure help, linked lists?

Postby hrs » Sat Mar 30, 2013 9:33 pm

I came up with this
Code: Select all
class Node(object):
    def __init__(self, val):
        self.prev = self
        self.next = self
        self.up   = self
        self.down = self
     
        self.val = val


class Grid(object):
    def __init__(self, data):
        self.data = data
        self.max_x = len(self.data[:][0]) - 1
        self.max_y = len(self.data) - 1
       
        self.linkGrid()

    def addNode(self, x, y):
        self.data[y][x] = Node(self.data[y][x])

    def linkGrid(self):
        for y, row in enumerate(self.data):
            for x, item in enumerate(row):
                self.addNode(x,y)
                if x == 0:
                    self.data[y][x].prev = None
                elif x == self.max_x:
                    self.data[y][x].prev = self.data[y][x - 1]
                    self.data[y][x].prev.next = self.data[y][x]
                    self.data[y][x].next = None
                else:
                    self.data[y][x].prev = self.data[y][x - 1]
                    self.data[y][x].prev.next = self.data[y][x]
               
                if y == 0:
                    self.data[y][x].up = None
                elif y == self.max_y:
                    self.data[y][x].up = self.data[y - 1][x]
                    self.data[y][x].up.down = self.data[y][x]
                    self.data[y][x].down = None
                else:
                    self.data[y][x].up = self.data[y - 1][x]
                    self.data[y][x].up.down = self.data[y][x]

    def traverse(self, func):
        for y, row in enumerate(self.data):
            for x, node in enumerate(row):
                print func(node),
            print

    def horizontalAverage(self, node):
        if node.prev != None and node.next != None:
            node.h_avg = (node.prev.val + node.next.val) / 2
            return node.h_avg

    def verticalAverage(self, node):
        if node.up != None and node.down != None:
            node.v_avg = (node.up.val + node.down.val) / 2
            return node.v_avg

    def ldiagonalAverage(self, node):
        if node.prev != None and node.up != None and node.next != None and node.down !=None:
            node.ldiag_avg = (node.prev.up.val + node.next.down.val) / 2
            return node.ldiag_avg

    def rdiagonalAverage(self, node):
        if node.prev != None and node.down != None and node.next != None and node.up !=None:
            node.rdiag_avg = (node.prev.down.val + node.next.up.val) / 2
            return node.rdiag_avg


grid_data = [[00., 03., 05., 07., 09., 11.],
             [12., 10., 08., 06., 04., 02.],
             [21., 31., 41., 51., 61., 71.],
             [111., 222., 333., 444., 555., 666.]]


MyGrid = Grid(grid_data)
print "\nhorizontal average"
MyGrid.traverse(MyGrid.horizontalAverage),
print "\nvertical average"
MyGrid.traverse(MyGrid.verticalAverage),
print "\nldiagonal averge"
MyGrid.traverse(MyGrid.ldiagonalAverage),
print "\nrdiagonal average"
MyGrid.traverse(MyGrid.rdiagonalAverage),


Looking at it now, it seems more logical to put the average methods in the Node class rather than the Grid class but then I don't know how to pass those methods to Grid.traverse(). Any ideas? Other comments on how this code could be better?
hrs
 
Posts: 86
Joined: Thu Feb 07, 2013 9:26 pm


Return to General Coding Help

Who is online

Users browsing this forum: No registered users and 1 guest