Featured Post

Introduction to Python Tales

Hello my friends, my name is Nelson Carrasquel, and perhaps as you I have the philosophy of coding for life, since 2013 when I started programming with Python (I have started before in 2008 with Delphi and some Visual Basic, but that is my dark past) my value as a Developer really increased due to the things that I found that could be possible with Python, now Python (with some Javascript) are the core languages for almost every challenge that I face in the programming world. I am a Chemical Engineer graduated from the UCV (Central University of Venezuela) in 2015, was working as an engineer for almost two years for an Automation and Control Systems Company, programming with LabVIEW almost all the time, but also I was tutoring as a part time job, helping students from all around the world (Not all the world but all the America) in their Python and Javascript assignments and projects; I found out that I really enjoy teaching and tutoring programming languages, and from that on I was kin…

A Python Tale of Iterators and Generators

Hello my friends in this Entry we are going to talk about a really cool topic (Well that's what I think) that is Iterators and Generators with the Python Programming Language, and for explaining each of this I'm going to build a class representing a Linked List data structure and how you can use Python Built-in Functions to iterate, create iterators or generators on custom classes.



Linked List


Accordinly to the Wikipedia, “a linked list is a linear collection of data elements, in which linear order is not given by their physical placement in memory. Each pointing to the next node by means of a pointer. It is a data structure consisting of a group of nodes which together represent a sequence”.

And here I give you a class implementation of the Linked List already built with some basics helper methods, most of this code I took it from the blog article of Adnan Alam, he explains really well this class, though I made some changes from the original code.
## linkedlist.py
 
class Node:
    
    def __init__(self,data=None,next_node=None):
        self.data = data
        self.next_node = next_node
    
    def get_data(self):
        return self.data
 
    def set_data(self, data):
        self.data = data
    
    def get_next(self):
        return self.next_node
    
    def set_next(self,new_node):
        self.next_node = new_node
 
    def __str__(self):
 
        return self.data.__str__()
 
class LinkedList:
    
    def __init__(self, front=None):
        self.front = front
 
    def insert_front(self, data):
        new_node = Node(data)
        new_node.set_next(self.front)
        self.front = new_node
 
    def insert_rear(self, data):
 
        new_node = Node(data)
        if self.front is None:
            self.front = new_node
        else:
            current = self.front
            while current.get_next():
                current = current.get_next()
            current.set_next(new_node)
 
    def delete(self, data):
 
        current = self.front
        prev = None
        while current:
            if current.get_data() == data:
                if prev:
                    prev.set_next(current.get_next())
                else:
                    self.front = current.get_next()
                break
            else:
                prev = current
                current = current.get_next()
 
    def search(self, data):
        current = self.front
        while current:
            if current.get_data() == data:
                return True
            else:
                current = current.get_next()
        return False
 
    def __len__(self):
        current = self.front
        count = 0
        while current:
            count +=1
            current = current.get_next()
        return count
 
    def __str__(self):
        current = self.front
        temp = []
        while current:
            temp.append(current.get_data())
            current = current.get_next()
 
        return temp.__str__()

Here we have two classes, a class for Node and a class for LinkedList, if you are not used to Object Oriented Programming in Python take a look at my two earlier entries in this topic.
Now as mentioned it before, this data structure could represent a sequence, so this could mean that we can index or iterate through it, well not yet, we need to provide to this class the methods that will allow us to perform these operations.

Set and Get Item

In our own data structures sometimes we want to have the capability to perform indexing access to the sequences, in same way we get and set elements in a Python List, we can achieved this by implementing __getitem__ and __setitem__ methods to our class, Python List are really versatile in this kind of operations, you can even slice using square  brackets, but we are going to go that far, we are going to implement simple index access capable of doing even negatives, some validations must be done like only integers and values less or equal than the size of the sequence, let's build these methods.
    def __getitem__(self, key):
 
        if type(key) != int:
 
            raise TypeError
 
        size = self.__len__()
 
        if key  < 0 and abs(key) > size:
 
            raise IndexError
 
        if key  < 0:
 
            key = size + key
 
        if key >  size - 1:
 
            raise IndexError
 
        current = self.front
        counter = 0
        while current:
            if counter == key:
                return current
            else:
                current = current.get_next()
                counter += 1
 
    def __setitem__(self, key, data):
 
        if type(key) != int:
 
            raise TypeError
 
        size = self.__len__()
 
        if key  < 0 and abs(key) > size:
 
            raise IndexError
 
        if key  < 0:
 
            key = size + key
 
        if key >  size - 1:
 
            raise IndexError
 
        current = self.front
        counter = 0
        while current:
            if counter == key:
                current.set_data = data
            else:
                current = current.get_next()
                counter += 1

Now let's make some tests on this
>>> item1 = 2020
>>> item2 = 4040
>>> item3 = 6060
>>> item4 = 8080
>>> linked = LinkedList()
>>> linked.insert_front(item1)
>>> linked.insert_front(item2)
>>> linked.insert_front(item3)
>>> linked.insert_front(item4)
>>> print linked
[8080, 6060, 4040, 2020]
>>> linked[1]
6060
>>> linked[2]
4040
>>> linked[-1]
2020
>>> linked[2] = 3030
>>> print linked
[8080, 6060, 3030, 2020]

Pretty cool right? Now If we want to iterate through this linked list using a for loop, is not possible yet and that is because, so far this class is not an iterator.

Iterators

we turn these objects into iterators if we build  the __iter__ and next methods to our LinkedList class, these methods are used by the for loop for  iteration, and the code is as follow.
    def __iter__(self):
        self.n = 0
        return self
 
    def next(self):
        if self.n < self.__len__():
            result = self.__getitem__(self.n)
            self.n += 1
            return result
        else:
            raise StopIteration

As you can see if there is no more elements to iterate we need to raise a stop iteration error, this will indicate the for loop to stop, let's try this now.
>>> item1 = 101
>>> item2 = 102
>>> item3 = 103
>>> item4 = 104
>>> linked = LinkedList()
>>> linked.insert_front(item1)
>>> linked.insert_front(item2)
>>> linked.insert_front(item3)
>>> linked.insert_front(item4)
>>> print linked
[104, 103, 102, 101]
>>> for i in linked:
         print i
 
         
104
103
102
101

Something to keep in mind is that for Python 3, next for classes is used with double underscore __next__; now that we have cover iterators let's talk about generators.

Generators

Generators are a kind of iterators, well they behave like iterators, but they are implemented as functions and instead of returning a value they yield a value, the main advantage of this is that they do not allocate all the values in memory rather calculated on the fly, that is why is called generators, you won't find too much differences in terms of performance until you find you self in need of processing really large data sets.
A really simple generator is the calculation of Fibonacci numbers; here I show you a simple code for this.
def fibonacci(n):
    """
    Yields the first n elements of the Fibonnaci
    """
    a = b = 1
    for i in range(n):
        yield a
        a, b = b, a + b

Now let's test this
>>> gen1 = fibonacci(4)
>>> gen1.next()
1
>>> gen1.next()
1
>>> gen1.next()
2
>>> gen1.next()
3
>>> gen1.next()
 
Traceback (most recent call last):
  File "<pyshell#13>", line 1, in <module>
    gen1.next()
StopIteration
>>> for i in fibonacci(10):
         print i
 
         
1
1
2
3
5
8
13
21
34
55

Something to point out here is that generators as well iterators can only be iterated with next once until they reach the end, and they can be easily used with for loops, now let's say we want to convert our Linked List into a generator; we can build a generator method and yield each value at a time.
    def gen(self, n=None):
 
        if n == None:
 
            n = self.__len__()
 
        for i in range(n):
 
            yield self.__getitem__(i)

And finally let's test this
>>> item1 = 2020
>>> item2 = 4040
>>> item3 = 6060
>>> item4 = 8080
>>> linked = LinkedList()
>>> linked.insert_front(item1)
>>> linked.insert_front(item2)
>>> linked.insert_front(item3)
>>> linked.insert_front(item4)
>>> print linked
[8080, 6060, 4040, 2020]
for i in linked.gen():
         print i
 
         
8080
6060
4040
2020

Well remember that this has meaning if there are too much elements in the LinkedList, so technics to process this information is required in order to improve execution performance.
We have come to the end of this entry; well I hope you have found this entry helpful to you. So thanks for coming by my new entry and I hope you have enjoyed this as much as I enjoyed writing it, stop by the comments if you want to discuss about this, share in your social media and subscribe. Cheers my friends.