vendredi 10 juin 2016

Raising index error for __getitem__ method


I'm creating a LinkedList class to get a better feel for the python language and its doubly linked nodes. My overall task being to not make use of python's built-in list data structure, while also trying to optimize the time efficiency of the code. What would be the best way to go about fixing the getitem, and setitem methods?

    class LinkedList:
        class Node:
            def __init__(self, val, prior=None, next=None):
                self.val = val
                self.prior = prior
                self.next  = next

        def __init__(self):
            self.head = LinkedList.Node(None) # sentinel node (never to be removed)
            self.head.prior = self.head.next = self.head # set up "circular" topology
            self.length = 0


        ### prepend and append

        def prepend(self, value):
            n = LinkedList.Node(value, prior=self.head, next=self.head.next)
            self.head.next.prior = self.head.next = n
            self.length += 1

        def append(self, value):
            n = LinkedList.Node(value, prior=self.head.prior, next=self.head)
            n.prior.next = n.next.prior = n
            self.length += 1


        ### subscript-based access ###

        def _normalize_idx(self, idx):
            nidx = idx
            if nidx < 0:
                nidx += len(self)
                if nidx < 0:
                    nidx = 0
            return nidx

        def __getitem__(self, idx):
            """Implements `x = self[idx]`"""
        nidx = self._normalize_idx(idx)
        currNode = self.head.next
        for i in range(nidx):
                currNode = currNode.next
        return currNode.val
        else:
            raise IndexError


        def __setitem__(self, idx, value):
            """Implements `self[idx] = x`"""
            assert(isinstance(idx, int))
            nidx = self._normalize_idx(idx)
            if nidx >= len(self):
                raise IndexError
            self[nidx] = value

Testing this code using:

from unittest import TestCase
import random

tc = TestCase()
data = [1, 2, 3, 4]
lst = LinkedList()
for d in data:
    lst.append(d)

for i in range(len(data)):
    tc.assertEqual(lst[i], data[i])

with tc.assertRaises(IndexError):
x = lst[100]

I'd get an error saying the IndexError wasn't rasied. Writing these class methods always seems to trip me up, what might I be missing? I'm not exactly sure how this differs from the typical array backed list


Aucun commentaire:

Enregistrer un commentaire