a Stack in python



I have went through my original code and updated and fixed it.  It is now tested and a StackNode class   and    a Stack List class.   Originally I had all of this as my Single Linked List, and I honestly thought this is how they worked.  I didn't understand why Zed kept saying it was backwards... Like no... all my tests pass... HUH????

I finally got the nerve up to discuss it with him, and he explained it.  There's a reason he's so good at this!
 
Holy cow.  A simple misunderstanding led to all of this.  But now when we get to doing the stacks in my class, I'm done.

Here's the code:


class StackNode(object):
    # Value is like the item in the list
    def __init__(self, value, prev):
        self.value = value
        # next is a reference to the previous node in the list
        self.next = prev

    def __repr__(self):
        # this creates a string representation of  the value and next
        pval = self.next and self.next.value or None
        # nval is the next node, so it needs the (next it's value) or None
        return f"[{self.value}:{repr(pval)}]"  

class StackList(object):
    # start off with None, list is empty
    def __init__(self):
        self.stack = None

    def push(self, obj):
        # add node to the list, value=obj
        node = self.stack
        if node == None:
            # define the node if list is empty
            node = StackNode(obj, None)
            # set the self.stack to that node
            self.stack = node
        else:
            # if there is already a start node, add the next one
            # create the node, the reference to the previous node
            # is stored in the original self.stack
            node = StackNode(obj, self.stack)
            # now store the new node as self.stack
            self.stack = node

    def what(self):
        # A way to print off what's going on in my node list
        node = self.stack
        if node == None:
            print(" Empty list! ")
            return None
        else:
            while node:
                print(node)
                # go to the next node until we reach the original
                # node which has a self.next of None
                node = node.next

    def pop(self):
        # remove last item in list
        node = self.stack
        if node == None:
            return( " Empty List ")
        elif node.next == None:
            self.stack = None
            return(node.value)
        else:
            node = self.stack
            # go to previous node, set it to self.stack
            self.stack = node.next
            return(node.value)

    def count(self):
        # count the number of nodes
        node = self.stack

        count = 0
        if node == None:
            # if list is empty return 0
            return count
        else:
            while node:
                count += 1
                # go through the nodes until it reaches None
                node = node.next
            return count

    def get(self, index):
        length = self.count()
        # count isn't being used... need to delete it
        count = 0
        
        if length == 0:
            # for testing, None works better then "Empty list!"
            return(None)
        elif index > (length - 1):
            # now I know what this message is all about.
            # the index is greater then the length of the list
            # remember index starts at 0
            return(" index out of range! ")
        else:
            node = self.stack
            while node:
                # check for the item you want first, then increment
                if (length - 1)  == index:
                    return(node.value)
                else:
                    node = node.next
                    # the node.next runs from the last created node,
                    # to the first created node, so length needs to 
                    # decrease to match index
                    length = length - 1

    def insert(self, obj, index):
        # put a new node into the list at given index
        node = self.stack
        length = self.count()
        # make sure the index given is an integer.
        try:
            index = int(index)
        except TypeError:
            print(" index arguement must be an integer ")
        # if the try fails and goes to except, this still runs
        # but they'll have that little message in there error somewhere
        if int(index) > length - 1:
            # if they want to insert at the end.
            return(" Use push to do that! ")
        elif index == 0 and node == None:
            # if list is empty.  Could tell them to push to do this too.
            self.stack = StackNode(obj, None)
        elif index == 0 and node.next == None:
            # NoneType is not the same as None
            node = StackNode(obj, None)
####!!!! check !!!!##### This might be an error,  Check later
            newnode = StackNode(self.stack.value, node)
            self.stack = newnode
        else:
            print("else inserting ...")
            # I've checked for 0 index's above, so the -1 won't screw up
            previous = self.get(index - 1)
            # you need the previous to get link (self.next) so you can 
            # connect the new node
            replace = self.get(index)
            ## change the replace nodes' link to add the new node
            node = self.stack
            newnode = None
            
            while node:
                if node.value == previous:
                    link = node
                    # create the newnode to add to list
                    newnode = StackNode(obj, link)
                    node = node.next
                    # I don't know why but putting break here seemed to keep
                    # the newnode from setting.
          
                else:
                    node = node.next
            
            # if the newnode was set get the replace node and put it in it.
            if newnode:
                node = self.stack
                #print(" newnode ")
                while node:
                    if node.value == replace:
                        node.next = newnode
                        break
                    else:
                        node = node.next


    def remove(self, index):
        # it's going to be the reverse of insert.
        node = self.stack
        length = self.count()
        try:
            index = int(index)
        except TypeError:
            print(" index must be an integer! ")
            # give them a message they can see in errors
        if node == None or length == 0:
            # check for 0's
            return(" Empty list! ")
        elif int(index) > length - 1:
            return(" index out of range! ")
        elif length == 1 and index == 0:
            # i did this wrong the first time, and checked if the node
            # self.next value was none and emptied the list
            # the first (0) index node always has a None link, so 
            # I wasn't deleting an empty list necessarily
            self.stack = None
        else:
            #  change it is the node we need to change the link in
            # remove it, is the node we want to delete link to
            print(" Else executing ")
            changeit = self.get(index + 1)
            removeit = self.get(index)
            node = self.stack
            link = None
            removing = False

            while node:
                if node.value == removeit:
                    link = node.next
                    print(" link changed. ")
                    removing = True
                    node = node.next
                else:
                    node = node.next
            print(removing)
            
            if removing:
                node = self.stack
                while node:
                    if node.value == changeit:
                        node.next = link
                        break
                    else:
                        node = node.next
    def dump(self):
        #prompt = input(">  are you sure you want to delete entire list?")
        #if prompt in ['y', 'yes']:
        # pytest doesn't like 'input' 
        self.stack = None
        #else:
        #    print("List not deleted, no confirmation given.")

    def first(self):
        # return the first item on the list
        # for me that would be the original node... 
        # I think traditionally people read it the other way
        node = self.stack
        if node == None:
            return None
        else:
            while node:
                # stop at node that has None for self.next
                if node.next == None:
                    return(node.value)
                    #return(node) returning node won't work.
                    # I don't think this saves any time, but eh.
                    # the loop will stop on next run anyways.
                    break
                else:
                    node = node.next

    def last(self):
        # return the last node added to the list,
        # once again I think other read it the other way around...
        # for me the last would be the final node that links through to the 
        # original
        node = self.stack
        if node == None:
            return None
        else:
            node = self.stack
            # want to make a string repr...
            # going to look at the node one to create...
            # Works.  Sweet 
            nval = node.next and node.next.value or None
            print(f"[{node.value}: {repr(nval)}]")
            return(node.value)

    def unshift(self):
        # it's like a reverse pop() It'll remove the first item... 
        # so maybe a shortcut and use the remove() I already made?
        node = self.stack
        if node == None:
            print(" Empty list! ")
            return(None)
        else:
            #shortcut!   but I don't know if this is ok to do....
            first = self.first()
            self.remove(0)
            return first


colors = StackList()
colors.push("green")
colors.push("red")
colors.push("yellow")
print(colors.unshift())
colors.what()

Comments

Popular posts from this blog

Statistics, Python, Making a Stem Plot

Pandas Python and a little probability

JavaScript Ascii animation with while loops and console.log