DSImplement.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n",
      "1\n",
      "True\n",
      "Hi\n"
     ]
    }
   ],
   "source": [
    "# Use deque() and not python list([])\n",
    "# to not increase capacity x2 each time\n",
    "from collections import deque\n",
    "\n",
    "# Implement Stack\n",
    "class Stack:\n",
    "    def __init__(self):\n",
    "        self.data = deque()\n",
    "    def push(self,elem):\n",
    "        self.data.append(elem)\n",
    "    def pop(self):\n",
    "        return self.data.pop()\n",
    "    def peek(self):\n",
    "        return self.data[-1]\n",
    "    def size(self):\n",
    "        return len(self.data)\n",
    "    def isempty(self):\n",
    "        return True if self.size()==0 else False\n",
    "\n",
    "stack = Stack()\n",
    "stack.push(3)\n",
    "stack.push(5)\n",
    "print(stack.pop())\n",
    "print(stack.size())\n",
    "\n",
    "stack.pop()\n",
    "print(stack.isempty())\n",
    "print(\"Hi\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "1\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "from collections import deque\n",
    "\n",
    "# Implement Queue\n",
    "class Queue:\n",
    "    def __init__(self):\n",
    "        self.data = deque()\n",
    "    def enqueue(self,elem):\n",
    "        self.data.appendleft(elem)\n",
    "    def dequeue(self):\n",
    "        return self.data.pop()\n",
    "    def front(self):\n",
    "        return self.data[0] if self.size()>0 else -1\n",
    "    def size(self):\n",
    "        return len(self.data)\n",
    "    def isempty(self):\n",
    "        return True if self.size()==0 else False\n",
    "    \n",
    "queue = Queue()\n",
    "queue.enqueue(3)\n",
    "queue.enqueue(5)\n",
    "print(queue.dequeue())\n",
    "print(queue.size())\n",
    "\n",
    "queue.dequeue()\n",
    "print(queue.isempty())\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "14\n",
      "12\n",
      "7\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "# Implementing priority queues\n",
    "\n",
    "class PriorityQueue:\n",
    "    def __init__(self):\n",
    "        self.data = deque()\n",
    "        \n",
    "    def enqueue(self,elem):\n",
    "        self.data.append(elem)\n",
    "    \n",
    "    def dequeue(self):\n",
    "        if self.isEmpty():\n",
    "            return -1\n",
    "        idx = self.data.index(max(self.data))\n",
    "        itm = self.data[idx]\n",
    "        del self.data[idx]\n",
    "        return itm\n",
    "    \n",
    "    def size(self):\n",
    "        return len(self.data)\n",
    "    def isEmpty(self):\n",
    "        return True if self.size()==0 else False\n",
    "    \n",
    "\n",
    "myQueue = PriorityQueue() \n",
    "myQueue.enqueue(12) \n",
    "myQueue.enqueue(1) \n",
    "myQueue.enqueue(14) \n",
    "myQueue.enqueue(7)  \n",
    "\n",
    "while (not myQueue.isEmpty()):\n",
    "    print(myQueue.dequeue())\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "#9 -> #3 -> #4 -> #5 -> #6 -> #7 -> #8\n"
     ]
    }
   ],
   "source": [
    "# Linkedlist implementation\n",
    "\n",
    "class Node:\n",
    "    def __init__(self,data,nxt=None):\n",
    "        self.data = data\n",
    "        self.next = nxt\n",
    "        \n",
    "class LinkedList:\n",
    "    def __init__(self, data):\n",
    "        self.head = Node(data)\n",
    "    \n",
    "    def addTail(self, newData):\n",
    "        tmp = self.head\n",
    "        while tmp.next != None:\n",
    "            tmp = tmp.next\n",
    "        tmp.next = Node(newData)\n",
    "        \n",
    "    def addHead(self, newData):\n",
    "        tmp = self.head\n",
    "        self.head = Node(newData)\n",
    "        self.head.next = tmp\n",
    "        \n",
    "    def __str__(self):\n",
    "        s = \"\"\n",
    "        tmp = self.head\n",
    "        while tmp != None:\n",
    "            s+=f\"#{tmp.data} -> \"\n",
    "            tmp = tmp.next\n",
    "        return s[:len(s)-4]\n",
    "    \n",
    "lklst = LinkedList(3)\n",
    "lklst.addTail(4)\n",
    "lklst.addTail(5)\n",
    "lklst.addTail(6)\n",
    "lklst.addTail(7)\n",
    "lklst.addTail(8)\n",
    "lklst.addHead(9)\n",
    "print(lklst)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "#9 -> #8 -> #7 -> #6 -> #5 -> #4 -> #3\n"
     ]
    }
   ],
   "source": [
    "# Doubly LinkedList implementation\n",
    "\n",
    "class Node:\n",
    "    def __init__(self,data,prev=None,nxt=None):\n",
    "        self.data = data\n",
    "        self.prev = prev\n",
    "        self.next = nxt\n",
    "        \n",
    "class LinkedList:\n",
    "    def __init__(self, data):\n",
    "        self.head = Node(data)\n",
    "        self.tail = self.head\n",
    "    \n",
    "    def addTail(self, newData):\n",
    "        tmp = self.head\n",
    "        while tmp.next != None:\n",
    "            tmp = tmp.next\n",
    "        tmp.next = Node(newData)\n",
    "        tmp.next.prev = tmp\n",
    "        self.tail = tmp.next\n",
    "        \n",
    "    def addHead(self, newData):\n",
    "        tmp = self.head\n",
    "        self.head = Node(newData)\n",
    "        self.head.next = tmp\n",
    "        self.head.next.prev = self.head\n",
    "        \n",
    "        # if only used addHead() so far\n",
    "        if self.head.next.next == None:\n",
    "            self.tail = self.head.next\n",
    "        \n",
    "    # reverse str\n",
    "    def __str__(self):\n",
    "        s = \"\"\n",
    "        tmp = self.tail\n",
    "        while tmp != None:\n",
    "            s+=f\"#{tmp.data} -> \"\n",
    "            tmp = tmp.prev\n",
    "        return s[:len(s)-4]\n",
    "    \n",
    "lklst = LinkedList(3)\n",
    "lklst.addTail(4)\n",
    "lklst.addTail(5)\n",
    "lklst.addTail(6)\n",
    "lklst.addTail(7)\n",
    "lklst.addTail(8)\n",
    "lklst.addTail(9)\n",
    "print(lklst)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Hashmap implementation\n",
    "# key = str\n",
    "class HashMap:\n",
    "    def __init__(self,capacity=100):\n",
    "        self.capacity = capacity\n",
    "        self.data = [-1 for _ in range(capacity)]\n",
    "        \n",
    "    def hashfunction(self,key):\n",
    "        num = 0\n",
    "        for char in key:\n",
    "            num+=ord(char)\n",
    "        return num % self.capacity\n",
    "    \n",
    "    def __getitem__(self,key):\n",
    "        idx = self.hashfunction(key)\n",
    "        return self.data[idx]\n",
    "    \n",
    "    def __setitem__(self,key,val):\n",
    "        idx = self.hashfunction(key)\n",
    "        self.data[idx] = val\n",
    "        \n",
    "    def delete(self,key):\n",
    "        idx = self.hashfunction(key)\n",
    "        del self.data[idx]\n",
    "\n",
    "hamp = HashMap()\n",
    "hamp[\"Amanuel\"] = \"Python\"\n",
    "hamp[\"Tilahun\"] = \"Java\"\n",
    "hamp[\"Etaferahu\"] = \"C#\"\n",
    "\n",
    "print(hamp[\"Etaferahu\"])\n",
    "print(hamp[\"Amanuel\"])\n",
    "print(hamp[\"Tilahun\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Hashset Implementation\n",
    "class HashSet:\n",
    "    def __init__(self,capacity=200):\n",
    "        self.capacity = capacity\n",
    "        self.data = [-1 for _ in range(capacity)]\n",
    "        \n",
    "    def hashfunction(self,key):\n",
    "        num = 0\n",
    "        for char in key:\n",
    "            num+=ord(char)\n",
    "        return num % self.capacity\n",
    "    \n",
    "    def insert(self,val):\n",
    "        idx = self.hashfunction(val)\n",
    "        self.data[idx] = val\n",
    "        \n",
    "    def __contains__(self,val):\n",
    "        idx = self.hashfunction(val)\n",
    "        return True if self.data[idx]!=-1 else False\n",
    "    \n",
    "hset = HashSet()\n",
    "hset.insert(\"Cat\")\n",
    "hset.insert(\"Dog\")\n",
    "hset.insert(\"Bird\")\n",
    "hset.insert(\"Chicken\")\n",
    "\n",
    "print(\"Cat\" in hset)\n",
    "print(\"Dog\" in hset)\n",
    "print(\"Fail\" in hset)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 117,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1->8->2->9->12->5->3\n",
      "2->8->3->9->12->5\n"
     ]
    }
   ],
   "source": [
    "\n",
    "# Implement min-heap\n",
    "# l:2n+1, r:2n+2, p:(n-1)/2\n",
    "class MinHeap:\n",
    "    def __init__(self,val):\n",
    "        self.data = [val]\n",
    "        \n",
    "    def swap(self,i,j):\n",
    "        self.data[i],self.data[j] = self.data[j],self.data[i]\n",
    "        return True\n",
    "    \n",
    "    def __str__(self):\n",
    "        s = \"\"\n",
    "        for i in self.data:\n",
    "            s+=(str(i) + \"->\")\n",
    "        return s[:len(s)-2]\n",
    "    \n",
    "    def insert(self,val):\n",
    "        self.data.append(val)\n",
    "        self.heapifyup()\n",
    "        \n",
    "    def popfront(self):\n",
    "        self.swap(0,len(self.data)-1)\n",
    "        self.data.pop()\n",
    "        self.heapifydown()\n",
    "        \n",
    "    def heapifyup(self):\n",
    "        \n",
    "        # last-elem and its parent\n",
    "        n = len(self.data)-1\n",
    "        p = (n-1)//2\n",
    "        \n",
    "        # keep heapify-ing up until parent less than\n",
    "        while(p>=0 and self.data[p]>self.data[n]):\n",
    "            self.swap(n,p)\n",
    "            n = p\n",
    "            p = (n-1)//2\n",
    "        \n",
    "    def heapifydown(self):\n",
    "        n = 0\n",
    "        l = (2*n)+1\n",
    "        r = (2*n)+2\n",
    "        \n",
    "        while(n<len(self.data) and l<len(self.data)):\n",
    "            m = 0\n",
    "            if r>=len(self.data):\n",
    "                m = min(self.data[n],self.data[l])\n",
    "            else:\n",
    "                m = min(min(self.data[n], self.data[l]),self.data[r])\n",
    "                \n",
    "            # parent is less than both\n",
    "            if m == self.data[n]:\n",
    "                break\n",
    "            \n",
    "            # left child smallest\n",
    "            elif m == self.data[l]:\n",
    "                self.swap(n,l)\n",
    "                n = l\n",
    "            \n",
    "            # right child smallest\n",
    "            else:\n",
    "                self.swap(n,r)\n",
    "                n = r\n",
    "            \n",
    "            # re-structure\n",
    "            l = (2*n)+1\n",
    "            r = (2*n)+2\n",
    "        \n",
    "minh = MinHeap(5)\n",
    "minh.insert(8)\n",
    "minh.insert(3)\n",
    "minh.insert(9)\n",
    "minh.insert(12)\n",
    "minh.insert(1)\n",
    "minh.insert(2)\n",
    "print(minh)\n",
    "\n",
    "minh.popfront()\n",
    "print(minh)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 130,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 8, 2, 9, 12, 3, 5]\n",
      "[2, 8, 3, 9, 12, 5]\n",
      "[-1, 8, 2, 9, 12, 5, 3]\n",
      "[12, 9, 8]\n",
      "[1, 3, 7, 8, 8, 9, 10, 12]\n"
     ]
    }
   ],
   "source": [
    "# Using Python's HeapQ Library\n",
    "import heapq\n",
    "\n",
    "# 'heapify', 'heappop', 'heappush', 'heappushpop', 'heapreplace', 'merge', 'nlargest', 'nsmallest'\n",
    "# print(dir(heapq))\n",
    "\n",
    "\n",
    "arr = [5,8,3,9,12,1,2]\n",
    "heapq.heapify(arr)\n",
    "print(arr)\n",
    "\n",
    "# pop min/max element\n",
    "heapq.heappop(arr)\n",
    "print(arr)\n",
    "\n",
    "# push element to min/max heap\n",
    "heapq.heappush(arr,-1)\n",
    "print(arr)\n",
    "\n",
    "lst = heapq.nlargest(3,arr)\n",
    "print(lst)\n",
    "\n",
    "\n",
    "lst = [1,8,9,10]\n",
    "lst2 = [3,7,8,12]\n",
    "mlst = heapq.merge(lst,lst2)\n",
    "print(list(mlst))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 138,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4 : {10,5}\n",
      "10 : {4,8}\n",
      "5 : {4,6,3}\n",
      "8 : {10,6,9}\n",
      "3 : {5,6,9}\n",
      "9 : {8,6,5}\n",
      "6 : {5,8,9,3}\n",
      "\n",
      "4 : {10,5}\n",
      "10 : {4,8}\n",
      "5 : {4,3}\n",
      "8 : {10,9}\n",
      "3 : {5,9}\n",
      "9 : {8,5}\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# Graph Implementation\n",
    "            \n",
    "# Node based Graph\n",
    "class GraphNode:\n",
    "    def __init__(self,val):\n",
    "        self.val = val\n",
    "        \n",
    "class Graph:\n",
    "    def __init__(self):\n",
    "        self.nodes = []\n",
    "        self.edges = {}\n",
    "    \n",
    "    def __str__(self):\n",
    "        s = \"\"\n",
    "        for key in self.edges:\n",
    "            s+=(str(key.val)+\" : {\")\n",
    "            for val in self.edges[key]:\n",
    "                s+=(str(val.val)+\",\")\n",
    "            s=s[:len(s)-1]\n",
    "            s+=\"}\\n\"\n",
    "        return s\n",
    "    \n",
    "    def add(self, val):\n",
    "        node = GraphNode(val)\n",
    "        self.nodes.append(node)\n",
    "        return node\n",
    "        \n",
    "    def create_edge(self,edge,*edges):\n",
    "        self.edges[edge] = [edge for edge in edges]\n",
    "    \n",
    "    def remove(self, edge):\n",
    "        if edge in self.nodes:\n",
    "            del self.nodes[self.nodes.index(edge)]\n",
    "        else:\n",
    "            raise Exception(\"Node not available\")\n",
    "            \n",
    "        # remove key\n",
    "        if edge in self.edges:\n",
    "            del self.edges[edge]\n",
    "            \n",
    "        # remove value\n",
    "        for loop_edge in self.edges:\n",
    "            if edge in self.edges[loop_edge]:\n",
    "                #print(type(self.edges[loop_edge]))\n",
    "                del self.edges[loop_edge][self.edges[loop_edge].index(edge)]\n",
    "                \n",
    "\n",
    "# Testing\n",
    "\n",
    "graph = Graph()\n",
    "node3  = graph.add(3)\n",
    "node4  = graph.add(4)\n",
    "node5  = graph.add(5)\n",
    "node6  = graph.add(6)\n",
    "node8  = graph.add(8)\n",
    "node9  = graph.add(9)\n",
    "node10 = graph.add(10)\n",
    "\n",
    "\n",
    "graph.create_edge(node4, node10, node5)\n",
    "\n",
    "graph.create_edge(node10, node4, node8)\n",
    "graph.create_edge(node5, node4, node6, node3)\n",
    "\n",
    "graph.create_edge(node8, node10, node6, node9)\n",
    "graph.create_edge(node3, node5, node6, node9)\n",
    "\n",
    "graph.create_edge(node9, node8, node6, node5)\n",
    "graph.create_edge(node6, node5, node8, node9,node3)\n",
    "print(graph)\n",
    "\n",
    "\n",
    "graph.remove(node6)\n",
    "print(graph)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 141,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n"
     ]
    }
   ],
   "source": [
    "# Graph Implentation\n",
    "\n",
    "# Adjancey Matrix Implementation\n",
    "class AdjMatrix:\n",
    "    def __init__(self, nodes, edges):\n",
    "        self.matrix = self.initmat(nodes, edges)\n",
    "        pass\n",
    "    \n",
    "    def initmat(self,nodes, edges):\n",
    "        n = len(nodes)\n",
    "        res = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        \n",
    "        ktv,i = {},0\n",
    "        for node in nodes:\n",
    "        \n",
    "        # 4 : {10,5}\n",
    "        for edge in edges:\n",
    "\n",
    "            for val in edges[edge]:\n",
    "                res[edge][val] = 1 # Wrong\n",
    "        \n",
    "        return res\n",
    "    \n",
    "print(len(graph.nodes))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}