Tuesday, May 5, 2015

Map ADT using Python

I start to go through Data Structure and Algorithm Using Python to get familiar on how to write classes using Python. The first thing is my favorite map. This structure is not the fancy hashmap, it's the simplest key - value pair structure. This map is a list implementation.
Basic structure:

a private mapEntry class which is used to store the key - value pair.

Note:
private classes, methods are identified by an underscore, e.g., _add(self, value).

add method to add key - value pairs
valueOf method to find the value of a given key, assume the key exists
remove method to remove the key - value pair given the key, assume the key exists
_iter_ method that returns an iterator of the key value pairs
a helper method findPosition that will find the position given the key, return None if no such key


__author__ = 'shirleyyoung'

class Map:
    # creates an empty map instance
    #like constructor, self: this object
    def __init__(self):
        #create empty list
        self._entryList=list()

    #when call map.len(), it will call __len__(map) and get the length of the object
    def __len__(self):
        return len(self._entryList)

    #determine if the map contains the given key
    def __contains__(self, key):
        ndx = self._findPosition(key)
        return ndx is not None

    #adds a new entry to the map if the key does not exist
    #otherwise replace the old value with the new value
    def add(self, key, value):
        ndx = self._findPosition(key)
        if ndx is not None:
            self._entryList[ndx].value = value
            return False
        else:
            entry = _MapEntry(key,value)
            self._entryList.append(entry)
            return True

    def valueOf(self, key):
        ndx = self._findPosition(key)
        assert ndx is not None, "Invalid map key"
        return self._entryList[ndx].value

    def remove(self, key):
        ndx = self._fndPosition(key)
        assert ndx is not None, "Invalid map key."
        self._entryList.pop(ndx)

    #return an iterator for traversing the keys in the map
    def __iter__(self):
        return iter(self._entryList)

    #find the index position of a category
    #if key is not found, none is returned
    def _findPosition(self, key):
        for i in range(len(self)):
            if self._entryList[i].key == key:
                return i
        return None

#private class
class _MapEntry:
    def __init__(self, key, value):
        self.key = key
        self.value = value

map = Map()
map.add(1, 1)
map.add(2, 2)
map.add(3, 3)
for entry in iter(map):
    print(entry.key)
print(len(map))
print(map.valueOf(1))

If you are interested in how Python implements dictionary, click here.

*********************************************************************************
I become interested in viewing source code since the time I was looking for jobs. And besides the one I mentioned in my previous couple blogs, I found two more interesting website.

GrepCode: this one provides Java src as well as interesting projects written in Java, e.g., Hadoop, Android.
searchcode: this one is neater, and provides code/projects written in various languages from C++ to Python. They also provides code from multiple sources, e.g., Github, Google Code, BitBucket (I didn't know this one before), etc. Interestingly, they also have an API.
Codatlas: this delicate website is the one I referred in couple of my previous posts. They claim to be IDE based, which is pretty impressive. One interesting feature is that they allow you to upload your own code. However, most of their projects are from Github, it could be better if they provide more projects from more sources.


1 comment:


  1. The development of artificial intelligence (AI) has propelled more programming architects, information scientists, and different experts to investigate the plausibility of a vocation in machine learning. Notwithstanding, a few newcomers will in general spotlight a lot on hypothesis and insufficient on commonsense application. IEEE final year projects on machine learning In case you will succeed, you have to begin building machine learning projects in the near future.

    Projects assist you with improving your applied ML skills rapidly while allowing you to investigate an intriguing point. Furthermore, you can include projects into your portfolio, making it simpler to get a vocation, discover cool profession openings, and Final Year Project Centers in Chennai even arrange a more significant compensation.


    Data analytics is the study of dissecting crude data so as to make decisions about that data. Data analytics advances and procedures are generally utilized in business ventures to empower associations to settle on progressively Python Training in Chennai educated business choices. In the present worldwide commercial center, it isn't sufficient to assemble data and do the math; you should realize how to apply that data to genuine situations such that will affect conduct. In the program you will initially gain proficiency with the specialized skills, including R and Python dialects most usually utilized in data analytics programming and usage; Python Training in Chennai at that point center around the commonsense application, in view of genuine business issues in a scope of industry segments, for example, wellbeing, promoting and account.

    ReplyDelete