Indexing error with an empty sublist

Question

I am trying to implement a tree data structure. One of the methods in my tree object associates nodes with coordinates whilst mapping the children to the parent nodes & vice-verse.

Initially I gave each node a list of children which turned out to be incorrect. So to remedy that I decided to just initialize nodes with an empty list and that's where the trouble started.

First the code that works...

    def treeSetUp(self):

        '''Set tree's initial structure
        For each level in treeArray
        [level, leaf, [node number, parent, full, [coordinates], [centroid], [children]], [node number, leaf, full, [coordinates], [centroid], [children]], ...]'''


        # Create root level & node    
        leaf = False    
        numChildren = (self.dims[0] * self.dims[1] * self.dims[2])/self.diameters[0]**3 # This maybe whay it only works for cubes
        children = [(kids) for kids in xrange(numChildren)]
        rootCoords = np.array([[0, 0, 0], [0, self.dims[0], 0], [self.dims[0], 0, 0], [self.dims[0], self.dims[1], 0], [0, 0, self.dims[2]], [0, self.dims[1], self.dims[2]], [self.dims[0], 0, self.dims[2]], [self.dims[0], self.dims[1], self.dims[2]]])
        xCentroid = np.sum(rootCoords[:,0])/8.0
        yCentroid = np.sum(rootCoords[:,1])/8.0
        zCentroid = np.sum(rootCoords[:,2])/8.0
        rootCentroids = [xCentroid, yCentroid, zCentroid]
        rootNode = [0, None, False, rootCoords, rootCentroids, copy.copy(children)]

        treeArray = []
        treeArray.append([0, leaf, [rootNode]])
        allCoordinates = []
        allCoordinates.append(rootCoords)
        allCentroids = []
        allCentroids.append(rootCentroids)

        for idx in xrange(self.depth):

            # self.coordGenerator splits a given domain into cubes & returns the
            # coordinates of each cube as well as its associated centroid
            # This is done at different resolutions at different levels
            levelCoordinates, levelCentroid = self.coordGenerator(idx+1)
            allCoordinates.append(levelCoordinates)
            allCentroids.append(levelCentroid)

            nodeCount = 0            
            if idx == self.depth-1:
                leaf = True 

            # Generate level's nodes            
            newNodes = []
            for parentNode, node in enumerate(treeArray[idx][2]):

                # Generate nodes's child list                
                children = []
                for nodeNumber, child in enumerate(node[5]):

                    # Gereate child list                    
                    if leaf:
                        children = [None]
                    else:
                        numChildren = (self.diameters[idx]**3)/(self.diameters[idx+1]**3)
                        children = [(kids + nodeCount*numChildren) for kids in xrange(numChildren)]

                    # Assign coordinates to level 1 nodes else generate placeholders      
                    if idx == 0:
                        nodeCoords = levelCoordinates[nodeNumber]
                        nodeCentroid = levelCentroid[nodeNumber]
                    else:
                        nodeCoords = []
                        nodeCentroid = []

                    newNodes.append([nodeCount, parentNode, False, copy.deepcopy(nodeCoords), copy.deepcopy(nodeCentroid), copy.copy(children)])
                    nodeCount += 1

            newLevel = [idx+1, leaf, copy.deepcopy(newNodes)]
            treeArray.append(newLevel)

        # Operation find parents
        for level in xrange(1, self.depth):
            for childNode, centroid in enumerate(allCentroids[level+1]):

                for node in treeArray[level][2]:

                    # bounding box of parent node
                    boundary = node[3]
                    xBound = [np.min(boundary[:,0]), np.max(boundary[:,0])]
                    yBound = [np.min(boundary[:,1]), np.max(boundary[:,1])]
                    zBound = [np.min(boundary[:,2]), np.max(boundary[:,2])]

                    # Is child's centroid in parents ounding box?
                    if (xBound[0] <= centroid[0] <= xBound[1]) and (yBound[0] <= centroid[1] <= yBound[1]) and (zBound[0] <= centroid[2] <= zBound[1]):
                        treeArray[level+1][2][childNode][1] = node[0]       # Add parent node to child
                        treeArray[level+1][2][childNode][3] = allCoordinates[level+1][childNode]
                        treeArray[level+1][2][childNode][4] = centroid
#                        treeArray[level][2][node[0]][5].append(childNode)   # Add child to parents list of children
                        break

And now the code that doesnt...

   def treeSetUp(self):

        '''Set tree's initial structure
        For each level in treeArray
        [level, leaf, [node number, parent, full, [coordinates], [centroid], [children]], [node number, leaf, full, [coordinates], [centroid], [children]], ...]'''


        # Create root level & node    
        leaf = False    
        numChildren = (self.dims[0] * self.dims[1] * self.dims[2])/self.diameters[0]**3 # This maybe whay it only works for cubes
        children = [(kids) for kids in xrange(numChildren)]
        rootCoords = np.array([[0, 0, 0], [0, self.dims[0], 0], [self.dims[0], 0, 0], [self.dims[0], self.dims[1], 0], [0, 0, self.dims[2]], [0, self.dims[1], self.dims[2]], [self.dims[0], 0, self.dims[2]], [self.dims[0], self.dims[1], self.dims[2]]])
        xCentroid = np.sum(rootCoords[:,0])/8.0
        yCentroid = np.sum(rootCoords[:,1])/8.0
        zCentroid = np.sum(rootCoords[:,2])/8.0
        rootCentroids = [xCentroid, yCentroid, zCentroid]
        rootNode = [0, None, False, rootCoords, rootCentroids, copy.copy(children)]

        treeArray = []
        treeArray.append([0, leaf, [rootNode]])
        allCoordinates = []
        allCoordinates.append(rootCoords)
        allCentroids = []
        allCentroids.append(rootCentroids)

        for idx in xrange(self.depth):

            # self.coordGenerator splits a given domain into cubes & returns the
            # coordinates of each cube as well as its associated centroid
            # This is done at different resolutions at different levels
            levelCoordinates, levelCentroid = self.coordGenerator(idx+1)
            allCoordinates.append(levelCoordinates)
            allCentroids.append(levelCentroid)

            nodeCount = 0            
            if idx == self.depth-1:
                leaf = True  

            # Generate level's nodes            
            newNodes = []
            for parentNode, node in enumerate(treeArray[idx][2]):

                # Generate nodes's child list                
                children = []
                for nodeNumber, child in enumerate(node[5]):

                    # Gereate child list                    
                    if leaf:
                        children = [None]
                    else:
                        numChildren = (self.diameters[idx]**3)/(self.diameters[idx+1]**3)
                        children = [(kids + nodeCount*numChildren) for kids in xrange(numChildren)]

                    # Assign coordinates to level 1 nodes else generate placeholders      
                    if idx == 0:
                        nodeCoords = levelCoordinates[nodeNumber]
                        nodeCentroid = levelCentroid[nodeNumber]
                    else:
                        nodeCoords = []
                        nodeCentroid = []

                    newNodes.append([nodeCount, parentNode, False, copy.deepcopy(nodeCoords), copy.deepcopy(nodeCentroid), []]) #copy.copy(children)])
                    nodeCount += 1

            newLevel = [idx+1, leaf, copy.deepcopy(newNodes)]
            treeArray.append(newLevel)

        # Operation find parents
        for level in xrange(1, self.depth):
            for childNode, centroid in enumerate(allCentroids[level+1]):

                for node in treeArray[level][2]:

                    # bounding box of parent node
                    boundary = node[3]
                    xBound = [np.min(boundary[:,0]), np.max(boundary[:,0])]
                    yBound = [np.min(boundary[:,1]), np.max(boundary[:,1])]
                    zBound = [np.min(boundary[:,2]), np.max(boundary[:,2])]

                    # Is child's centroid in parents ounding box?
                    if (xBound[0] <= centroid[0] <= xBound[1]) and (yBound[0] <= centroid[1] <= yBound[1]) and (zBound[0] <= centroid[2] <= zBound[1]):
                        treeArray[level+1][2][childNode][1] = node[0]       # Add parent node to child
                        treeArray[level+1][2][childNode][3] = allCoordinates[level+1][childNode]
                        treeArray[level+1][2][childNode][4] = centroid
#                        treeArray[level][2][node[0]][5].append(childNode)   # Add child to parents list of children
                        break

The only difference being that instead of supplying the erroneous list of child nodes, I supplied an empty list.

The error it gives..

treeArray[level+1][2][childNode][1] = node[0]       # Add parent node to child IndexError: list index out of range

So why would adding an empty list instead of an occupied list change indexing?

I dont have the privilege to share the rest of the code unfortunately, I have tried to replicate this error in a simplified code but so far no luck.

I suspect that there is something obvious here but after a day of staring at it with incredulity, well its making less sense.

Answer 1

I believe if you print

treeArray[level+1][2][childNode]

right before the line where the error occurs, you will find that it is [] in the code that doesn't work and equal to something else in the code that does work. So when you set ...[childNode][1] to have a value, you're running into the same error you would if you had

a = []
a[1]=1
> IndexError: list assignment index out of range

Whereas in the working code you're seeing something like:

a=[4,6]
a[1]=1
print a
>[4,1]

When you don't send it an empty list, but rather a copy of a child, then when it tries to set that entry, it is successful because that entry is already in the list, it's just changing the value. On the other hand if it's trying to set the [1] entry of an empty list, then it's going to fail because the list entry doesn't exist yet. Think of a[n]=x as being like filing the legal forms required to change the identity of a[n]. The process does not work if you file the forms for a person who does not exist. To actually create a[n] requires some other processes to happen.

You should simplify the code significantly. Rather than having lists of things like: [nodeCount, parentNode, False, copy.deepcopy(nodeCoords), copy.deepcopy(nodeCentroid), []], I think you'll be better off defining an object that contains all of this. It will be easier to debug.