Chord.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import hashlib \n",
    "import random\n",
    "import math\n",
    "import numpy as np\n",
    "import math\n",
    "import pandas as pd\n",
    "from collections import Counter\n",
    "inf = math.inf\n",
    "def hex_id(id):\n",
    "    return hashlib.md5(str(id).encode()).hexdigest()\n",
    "def random_num(a,b):\n",
    "    return a + random.random()*(b-a)\n",
    "\n",
    "\n",
    "def power_m(M):\n",
    "    return int(math.pow(2,M))\n",
    "\n",
    "def in_range(item,id1,id2,M):\n",
    "    #print(\"in range, \", item, id1, id2 )\n",
    "    if id1 is None or id2 is None or item is None:\n",
    "        return False\n",
    "    item = item%int(power_m(M))\n",
    "    id1 = id1%int(power_m(M))\n",
    "    id2 = id2%int(power_m(M))\n",
    "    if id1 == id2:\n",
    "        return id1 == item\n",
    "    if id1 < id2:\n",
    "        return item >= id1 and item<= id2\n",
    "    else:\n",
    "        return item >= id1 or item <= id2\n",
    "\n",
    "def get_prob_distribution(lst):\n",
    "    \n",
    "    a = Counter(lst)\n",
    "    ct = sum(a.values())\n",
    "\n",
    "    vals = list(a.keys())\n",
    "    probs = [item*1.0/ct for item in a.values()]\n",
    "    idx   = np.argsort(vals)\n",
    "    vals = np.array(vals)[idx]\n",
    "    probs = np.array(probs)[idx]\n",
    "    return vals,probs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "global id_to_node\n",
    "id_to_node = {}\n",
    "\n",
    "class Finger():\n",
    "    def __init__(self,start=None,interval=None,node_id=None):\n",
    "        self.start = start\n",
    "        self.interval = interval\n",
    "        self.node = node_id\n",
    "        return\n",
    "    \n",
    "class Node():\n",
    "    def __init__(self,id,M):\n",
    "        self.id = id\n",
    "        self.M = M\n",
    "        self.finger = []\n",
    "        self.data= {}\n",
    "        for i in range(0,self.M):\n",
    "            start = (id + int(math.pow(2,i)))%int(math.pow(2,self.M))\n",
    "            end = (id + int(math.pow(2,i+1)))%int(math.pow(2,self.M))\n",
    "            self.finger.append(Finger(start,(start,end)))\n",
    "        self.successor = None\n",
    "        self.predecessor = None\n",
    "        \n",
    "        \n",
    "    def print_finger_table(self):\n",
    "        print(\"Node id,\", self.id)\n",
    "        print(\"start         interval       successor\")\n",
    "        for i in range(0,self.M):\n",
    "            print(self.finger[i].start, \"    \" ,self.finger[i].interval, \"    \", self.finger[i].node)\n",
    "        print(\"Predecesssor, \", self.predecessor)\n",
    "        print(\"Successor, \", self.successor)\n",
    "        print(\"###########################\")\n",
    "        return\n",
    "            \n",
    "    def find_successor(self,id,route=False):\n",
    "        #if id == self.id:\n",
    "            #return self.id\n",
    "        if route:\n",
    "            n_,route_ = self.find_predecessor(id,route)\n",
    "            return id_to_node[n_].successor,route_ + [id_to_node[n_].successor]\n",
    "        else:\n",
    "            n_ = self.find_predecessor(id,route)\n",
    "            return id_to_node[n_].successor\n",
    "        #print(\"predecessor,\", n_)\n",
    "        \n",
    "        \n",
    "    def find_predecessor(self,id,route=False):\n",
    "        n_ = self.id\n",
    "        route_ = [n_]\n",
    "        #print(\"find predecessor key, current node , successor \", id,n_,id_to_node[n_].successor)\n",
    "        while not in_range(id,n_+1,id_to_node[n_].successor,self.M):\n",
    "            #print(\"loop\")\n",
    "            n_ = id_to_node[n_].closest_preceding_finger(id)\n",
    "            #print(\"closest preceding finger, \",n_)\n",
    "            route_.append(n_)\n",
    "        if route:\n",
    "            return n_,route_\n",
    "        else:\n",
    "            return n_\n",
    "    def closest_preceding_finger(self,id):\n",
    "        for i in range(self.M-1,-1,-1):\n",
    "            #print(\"in closest precedding, \", self.finger[i].node,self.id,id)\n",
    "            if in_range(self.finger[i].node,self.id+1,id-1,self.M):\n",
    "            #if in_range(id,self.finger[i].interval[0],self.finger[i].interval[1]-1,self.M):\n",
    "                return self.finger[i].node\n",
    "    \n",
    "    def join(self,n_):\n",
    "        if n_ not in id_to_node: ### that means it is first node to join###\n",
    "            for i in range(0,self.M):\n",
    "                self.finger[i].node = self.id\n",
    "            self.predecessor = self.id\n",
    "            self.successor = self.id\n",
    "        else:    ### n_ exists\n",
    "            #print(\"initializing\")\n",
    "            self.initialize_finger(n_)\n",
    "            #print(id_to_node[n_].print_finger_table())\n",
    "            #print(\"updating other nodes\")\n",
    "            self.update_other_nodes()\n",
    "    def initialize_finger(self,n_):\n",
    "        n_ = id_to_node[n_]\n",
    "        #print(self.finger[0].interval)\n",
    "        self.finger[0].node = n_.find_successor(self.finger[0].start)\n",
    "        self.successor = self.finger[0].node\n",
    "        self.predecessor = id_to_node[self.successor].predecessor\n",
    "        id_to_node[self.successor].predecessor = self.id\n",
    "        \n",
    "        for i in range(1,self.M):\n",
    "            self.finger[i].node = n_.find_successor(self.finger[i].start)\n",
    "        \n",
    "    def update_other_nodes(self):\n",
    "        for i in range(0,self.M):\n",
    "            if self.id-int(math.pow(2,i)) == self.predecessor:\n",
    "                id_to_node[self.predecessor].update_finger_table(self.id,i)\n",
    "            else:\n",
    "                #print(\"key to find predecessor\", self.id-int(math.pow(2,i)))\n",
    "                p= self.find_predecessor(self.id-int(math.pow(2,i)))\n",
    "                #print(\"in update other, \",p)\n",
    "                id_to_node[p].update_finger_table(self.id,i)\n",
    "    def update_finger_table(self,node,i):\n",
    "        #print(\"here i , self, self.finger[i] node, self predec\",i ,self.id,self.finger[i].node,self.predecessor)\n",
    "        if self.id == node:\n",
    "            return\n",
    "        if in_range(node,self.id,self.finger[i].node-1,self.M):\n",
    "            self.finger[i].node = node\n",
    "            if i == 0:\n",
    "                self.successor = node\n",
    "            id_to_node[self.predecessor].update_finger_table(node,i)\n",
    "        \n",
    "            \n",
    "    def add_key(self,key,value):\n",
    "        n_ = self.find_successor(key)\n",
    "        id_to_node[n_].add_key_to_itself(key,value)\n",
    "        return\n",
    "    def add_key_to_itself(self,key,value):\n",
    "        self.data[key] = value\n",
    "        return\n",
    "    def return_val_for_key(self,key):\n",
    "        if key in self.data:\n",
    "            return self.data[key]\n",
    "        return None\n",
    "    def find_key(self,key):\n",
    "        n_,route = self.find_successor(key,route = True)\n",
    "        return (id_to_node[n_].return_val_for_key(key), route)\n",
    "        #print(len(route))\n",
    "        \n",
    "    def update(self,delete_node,successor,predecessor):\n",
    "        if self.successor == delete_node:\n",
    "            self.successor = successor\n",
    "        if self.predecessor == delete_node:\n",
    "            self.predecessor = predecessor\n",
    "            \n",
    "        for finger in self.finger:\n",
    "            if finger.node == delete_node:\n",
    "                finger.node = successor\n",
    "                \n",
    "    def delete(self):\n",
    "        successor = self.successor\n",
    "        predecessor  = self.predecessor\n",
    "        for node in id_to_node:\n",
    "            if node != self.id:\n",
    "                id_to_node[node].update(self.id,successor,predecessor)\n",
    "        \n",
    "        return\n",
    "                \n",
    "        \n",
    "        \n",
    "\n",
    "        \n",
    "class Chord():\n",
    "    def __init__(self,N):\n",
    "        print(\"Adding nodes\")\n",
    "        self.seed = False\n",
    "        M = 20\n",
    "        #id_to_node = {}\n",
    "        for i in range(0,N):\n",
    "            id = random.choice(range(0,int(pow(2,M))))\n",
    "            if i ==0:\n",
    "                self.seed = id\n",
    "            node = Node(id,M)\n",
    "            id_to_node[id] = node\n",
    "            if i == 0:\n",
    "                node.join(0)\n",
    "            else:\n",
    "                node.join(self.seed)\n",
    "        self.keys = []\n",
    "    \n",
    "        print(\"Adding keys\")\n",
    "        for i in range(0,10000):\n",
    "            key = random.choice(range(0,int(pow(2,20))))\n",
    "            self.keys.append(key)\n",
    "            id_to_node[self.seed].add_key(key,str(key)+\"_val\")\n",
    "    def find_key(self,key=None):\n",
    "        if key is None:\n",
    "            key = random.choice(self.keys)\n",
    "        if self.seed in id_to_node:\n",
    "            val,route = id_to_node[self.seed].find_key(key)\n",
    "        else:\n",
    "            val,route = id_to_node[list(id_to_node.keys())[0]].find_key(key)\n",
    "        if route is not None:\n",
    "            return len(route)\n",
    "        else:\n",
    "            return None\n",
    "    def find_key_and_route(self):\n",
    "        key = random.choice(self.keys)\n",
    "        if self.seed in id_to_node:\n",
    "            val,route = id_to_node[self.seed].find_key(key)\n",
    "        else:\n",
    "            val,route = id_to_node[list(id_to_node.keys())[0]].find_key(key)\n",
    "        route = \" -> \".join([str(item) for item in route])\n",
    "        print(\"Lookup route of key,\", str(key),\" :\",route)\n",
    "    def delete_nodes(self,N):\n",
    "        import random\n",
    "        for i in range(0,N):\n",
    "            node_id = random.choice(list(id_to_node.keys()))\n",
    "            id_to_node[node_id].delete()\n",
    "            del id_to_node[node_id]\n",
    "    \n",
    "    \n",
    "#chord.delete_node(500)\n",
    "# class Chord():\n",
    "#     def __init__(self,N):\n",
    "#         return\n",
    "            \n",
    "# node = Node(0,3)\n",
    "# node.join(5) ### random number\n",
    "# id_to_node[0] = node\n",
    "# node1 = Node(1,3)\n",
    "# id_to_node[1] = node1\n",
    "# node1.join(0)\n",
    "# # node1.print_finger_table()\n",
    "# # node.print_finger_table()\n",
    "\n",
    "# # print(\"successor, \" ,node1.find_successor(3))\n",
    "# # print(\"predecessor \", node.find_predecessor(0))\n",
    "# node3 = Node(3,3)\n",
    "# id_to_node[3] = node3\n",
    "# node3.join(0)\n",
    "\n",
    "\n",
    "# node6 = Node(6,3)\n",
    "# id_to_node[6] = node6\n",
    "# node6.join(1)\n",
    "# print(\"### after joininng 6 ###\")\n",
    "# # node.print_finger_table()  \n",
    "# # node1.print_finger_table()\n",
    "# # node3.print_finger_table()\n",
    "# # node6.print_finger_table()\n",
    "\n",
    "# node3.find_successor(7,False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Adding nodes\n",
      "Adding keys\n"
     ]
    }
   ],
   "source": [
    "chord = Chord(1000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "243877\n",
      "Node id, 243877\n",
      "start         interval       successor\n",
      "243878      (243878, 243879)      245001\n",
      "243879      (243879, 243881)      245001\n",
      "243881      (243881, 243885)      245001\n",
      "243885      (243885, 243893)      245001\n",
      "243893      (243893, 243909)      245001\n",
      "243909      (243909, 243941)      245001\n",
      "243941      (243941, 244005)      245001\n",
      "244005      (244005, 244133)      245001\n",
      "244133      (244133, 244389)      245001\n",
      "244389      (244389, 244901)      245001\n",
      "244901      (244901, 245925)      245001\n",
      "245925      (245925, 247973)      247058\n",
      "247973      (247973, 252069)      248237\n",
      "252069      (252069, 260261)      252412\n",
      "260261      (260261, 276645)      261174\n",
      "276645      (276645, 309413)      278058\n",
      "309413      (309413, 374949)      311010\n",
      "374949      (374949, 506021)      375505\n",
      "506021      (506021, 768165)      508393\n",
      "768165      (768165, 243877)      769352\n",
      "Predecesssor,  243070\n",
      "Successor,  245001\n",
      "###########################\n"
     ]
    }
   ],
   "source": [
    "id = random.choice(list(id_to_node.keys()))\n",
    "print(id)\n",
    "id_to_node[id].print_finger_table()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Creating network for  100\n",
      "Adding nodes\n",
      "Adding keys\n",
      "Searching,\n",
      "deleting 50% nodes\n",
      "searching for queries\n",
      "Creating network for  500\n",
      "Adding nodes\n",
      "Adding keys\n",
      "Searching,\n",
      "deleting 50% nodes\n",
      "searching for queries\n",
      "Creating network for  1000\n",
      "Adding nodes\n",
      "Adding keys\n",
      "Searching,\n",
      "deleting 50% nodes\n",
      "searching for queries\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYgAAAEWCAYAAAB8LwAVAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjAsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+17YcXAAAgAElEQVR4nO3deXxV1bn/8c8XwhDGMId5limKQABnxQGC1WqttQ44IIhap9pWa3+19ra9t4N2sre1SkEccKxV67UloHWegCAIYVIEZAiBMM+Q4fn9sXfwEE+SA+TkJDnP+/U6r5y91x6evXNynuy19l5LZoZzzjlXVr1EB+Ccc65m8gThnHMuKk8QzjnnovIE4ZxzLipPEM4556LyBOGccy4qTxCuykkySX0SHYerOSSdJWldFWxnt6ReVRGTq5wniCQj6S1J2yQ1SnQsNZ2k1ZL2hV9KGyVNk9SsCrZ5blXFeCwk9QiTeUqiY4mVmTUzs5WJjiNZeIJIIpJ6AKcDBnw9ocHUHheaWTNgKDAcuDeeO6tNX9axqovHlCw8QSSXa4CPgMeAa0tnSjpJUr6k+hHzviFpYfg+VdLj4ZXHUkl3x1BdcK6kz8J1/iJJ4bbqSbpX0heSNkl6QlLLsKz0P9pJkvIkbZD0/YiYRkjKkbQz/I/+99F2HMZ4QcR0iqTNkoZKaixpuqQtkrZLmiupQ2UnzszWAzOAjHCb48P97JK0UtKNEftrK+nVcPtbJb0bHveTQDfg/8KrkrsjjnmCpDXAG5L+Jem2Mse0UNLFUY61dP1rJa0Jj/PHEeX1JN0j6fPwmJ+X1Dosfif8uT2M5+Tw9zIsXHdcuO2B4fRESS+H7xtJ+mP4e8oL3zcKy86StE7SDyXlA9OixH27pCWSukQp6yPpbUk7wuN5LqLMwvJOYcylr72SLGK568PfzzZJMyV1r+j368phZv5KkhewAvgOMAwoBDpElH0OnBcx/XfgnvD9r4G3gVZAF2AhsK6C/RjwKpBG8IVYAGSFZdeHcfQCmgEvAk+GZT3CdZ8BmgLHh+ueG5Z/CFwdvm8GnFTO/u8DnoqY/hqwLHx/I/B/QBOgfnguWpSzndUR++4KLAZ+EbHN3oCAM4G9wNCw7FfAw0CD8HU6oLLbLHPMT4THnApcBsyOWGYwsAVoGCXG0vX/Fq47GDgADAjLv0vwT0EXoBHwCPBMmXVTIrb3BPD98P3k8HNxc0TZneH7n4fbbQ+0Az6IODdnAUXAb8J9pobz1oXlPwE+BtqVc96fAX5M8A9sY+C0Mp+tPlHWeSriuC4m+IwNAFIIrvo+SPTfX218JTwAf1XTLxpOI0gKbcPpZaV/7OH0fwOPhu+bA3uA7uH0SmBMxLITqTxBRP5RP8+XyeY/wHciyvqFcaVEfGH1jyi/H5gavn8H+FnpMVSw/z7ALqBJOP0UcF/4/vrwy+yEGM7ZamA3sB34AngISC1n2ZeBO8L3Pwf+Wc4X2WqiJ4heEfMaAVuBvuH0b4GHytlv6fpdIubNAS4P3y8Fzoko6xjlfEcmiAnAKxHrTgSeDae/4Msk+DlwfsR6Y4DV4fuzgINA44jys4D1wO+B94CWFZz3JwiSU5coZV9JEMAPgXmlvxuCK70JEeX1CBJ490T/Hda2l1cxJY9rgVlmtjmcfpqIaqZw+pKwmuAS4GMz+yIs6wSsjVg28n158iPe7yX4j790W19ElH1B8GUVWc2ztkx5p/D9BOA4YFlYNXQBUZjZCoIvtwslNSFob3k6LH4SmAk8G1aN3C+pQQXHcbGZpZlZdzP7jpntA5A0VtJHYRXSduB8oG24zgME/8HOCquf7qlg+185ZjM7QJBUx0mqB1wRxl2R8s53d+ClsLprO8F5Kebw8x3pbeB0SekEV1jPAacqaL9qCSwIl4v2e+wUMV1gZvvLbDsNmAT8ysx2VHAsdxNcmc2RtFjS9eUtKGkscAfB72lfOLs78GDEMW8Nt9e5gn26KDxBJAFJpdUWZypoa8gH7gQGSxoMYGZLCP7IxwJX8uUXKsAGgiqKUl2PIZw8gj/gUt0IqiM2lrP9buE6mNlnZnYFQbXGb4AXJDUtZz/PEHyxXgQsCZMGZlZoZj8zs4HAKcAFBG0zMQuT6D8I/rPvYGZpwL8JvoQws11m9n0z6wVcCHxP0jnh6uV1n1x2/uPAVcA5wF4z+/BIYoywFhgbJrnSV2ML2lS+Ekt4nvYCtwPvmNkuguQzCXjPzErCRaP9HvMqOB6AbQTne5qkU8sL2MzyzewGM+tEUCX4kKLcNi2pH8F5uszMyv4Dc2OZY041sw/K26eLzhNEcriY4L/GgcCJ4WsA8C6Hfzk+TfDFcAZBG0Sp54EfSWolqTNw6zHE8gxwp6SeCm4Z/SXwnJkVRSzzE0lNJA0CxhP8F1vaaNou/JLaHi5bXM5+ngVGAzcTkewkjZJ0vIIG+Z0E1S3lbaM8DQmqgQqAovC/2NER+7ggbEhVuI/iiH1sJGh/qVCYEEqA31H51UNFHgb+p7SRVlI7SReFZQXhPsrG8zbB7/jtcPqtMtMQ/B7vDbfXlqDdZ3plwZjZWwSJ7yVJI6MtI+lbEY3X2wiSTXGZZVoQVOPda2bvRTnmH4WfHyS1lPStymJzUSS6jstf8X8B2cDvosy/jOC/w5RwuhvBF8a/yizXlOBLqrSK4l7g8wr2d1g9McFdU/8dvq9H8GWyluALajrQKizrEa47ieC/0Xzg7ojtTAc2EbQLLCaoVqjouP9DcHWSHjHvCmA5QRvLRuBPRNTBl1l/NRHtBWXKbgnX3x6em2cjjvHOcN09wDrgJxHrXQSsCdf7AVHaASKWvZcy7RNRlvnK+gRf6BMjzvf3wmPeRdB28MuIZX8e/h62Ezb6E/zXbnzZBnVBOD0yYr3G4bnbEL7+RNjmQESDdMTyh80jaOTfCAyLckz3E7RX7A7jnVT2sxVuz8JlDr0ilrsaWESQoNcStq/568hepXdWOBczSTcTNIKeWcXb7QGsAhrY4VcUSUnSNQRfjqclOhaXnLyKyVVKUkdJp4b31PcDvg+8lOi46rKwcf07BHfzOJcQniBcLBoS3D+/C3iDoO73oYRGVIdJGkNQ7bORw28WcK5aeRWTc865qPwKwjnnXFR1qhOttm3bWo8ePRIdhnPO1Rrz5s3bbGbtopXVqQTRo0cPcnJyEh2Gc87VGpK+KK/Mq5icc85F5QnCOedcVJ4gnHPOReUJwjnnXFSeIJxzzkVVp+5ics65ZPLy/PU8MHM5edv30SktlbvG9OPiIVU37IUnCOecq4Venr+eH724iH2FQU/o67fv40cvLgKosiThVUzOOVcLPTBz+aHkUGpfYTEPzFxeZfvwKwjnnKtFduwt5PWlG1m/fV/U8rxy5h8NTxDOOVfDbd59gFmLN5K9OJ8PVmymqMSoJyiJ0tdqp7TUKtuvJwjnnKuBNuzYR3ZuPtm5+cxdvZUSg+5tmjDh9J6MzejIqoLd/L+Xcg+rZkptUJ+7xvSrshg8QTjnXA3xxZY9zAiTwoK1wbDrx3Voxq1n92VsRjr905sTDHUOJ3ZNQ5LfxeScc3WRmfHZpt1k5+YzIzefpRt2AnB855bcNaYfWRnp9G7XrNz1Lx7SuUoTQlmeIJxzrhqZGbnrd5K9eAMzcvNZWbAHCYZ1a8W9XxtAVkY6XVo1SXSYQJwThKQ0YAqQARhwvZl9GFF+F3BVRCwDgHZmtlXSaoIhLouBIjPLjGeszjkXLyUlxsdrtgVtCovzWbdtH/XriZN6tWb8qT0ZM7AD7Vs0TnSYXxHvK4gHgWwzu1RSQ+CwtGhmDwAPAEi6ELjTzLZGLDLKzDbHOUbnnKtyRcUlzF61lezcfGYuzmfTrgM0rF+P0/q25fZz+nLegA60atow0WFWKG4JQlIL4AzgOgAzOwgcrGCVK4Bn4hWPc87F24GiYt5fsZns3HxeW7KRbXsLSW1Qn7P6tSMrI52z+7eneeMGiQ4zZvG8gugFFADTJA0G5gF3mNmesgtKagJkAbdGzDZgliQDHjGzydF2ImkSMAmgW7duVXsEzjlXib0Hi3jn0wJm5ObzxtJN7DpQRPNGKZwzoD1ZGR0587h2pDasn+gwj0o8E0QKMBS4zcxmS3oQuAf4SZRlLwTeL1O9dKqZ5UlqD7wmaZmZvVN2xTBxTAbIzMyM8tiIc85VrZ37C3lz2SZmLMrnrU83sb+whFZNGnD+8R3JOj6dU3q3oVFK7UwKkeKZINYB68xsdjj9AkGCiOZyylQvmVle+HOTpJeAEcBXEoRzzlWHrXsO8vqSjczI3cD7K7ZwsLiE9s0bcVlmV7Iy0hnRozUp9etW93ZxSxBmli9praR+ZrYcOAdYUnY5SS2BM4FxEfOaAvXMbFf4fjTw83jF6pxz0WzcuZ9Zi4NnFGav2kpxidGlVSrXntKdrIx0hnRtRb16SnSYcRPvu5huA54K72BaCYyXdBOAmT0cLvMNYFaZtokOwEvhE4MpwNNmlh3nWJ1zjrVb9zIzTAofr9mGGfRu15Sbz+xNVkY6gzq1OPQ0c10ns7pTbZ+ZmWk5OTmJDsM5V8us2LQ7TAobyF0fPM08sGMLxmakk5WRTt8OzRMcYfxImlfec2b+JLVzLumYGUs27GRm2MXFZ5t2AzCkWxo/GtufrIx0urdpmuAoE88ThHMuKZSUGJ+s236o36M1W/dSTzCiZ2uuGjmQMRnpdGxZdV1l1wWeIJxzdVZxiTF39dZD3Wbn79xPg/rilN5tufms3pw3sANtmzVKdJg1licI51ydcrCohA9XbiE7dwOzFm9ky56DNEqpx5nHtePujH6cM6ADLVNrz9PMieQJwjlX6+0vLOadTwvIzs3n9aUb2bm/iKYN63P2gA5kDUrnrH7taNrIv+6OlJ8x51yttPtAEW8u20R2bj5vLt/E3oPFtExtwHkD0xmbkc5pfdvSuEHtf5o5kTxBOOdqje17D/L60k1k527gnc82c7CohLbNGnLxkM6MzUjnpF5taFDHnmZOJE8QzrkarWDXAWYtCRqZP/x8C0UlRqeWjblqZDfGZnRkWPdW1K/DTzMnkicI51yNk7d936E7j+Z+sRUz6NGmCRNP78XYjHRO6NIyaZ5mTiRPEM65GmH15j3MyM0nO3cDn6zbAUC/Ds25/ey+jD0+nX4dmntSqGaeIJxzCWFmfLpxNzNyN5Cdm8+y/F0AnNClJXdn9SNrUDq92jVLcJTJzROEc67amBmL1u8IrxTyWbV5DxJkdm/FTy4YSFZGOp3T/GnmmsIThHMuropLjI/XbGPGomBs5vXb91G/nji5VxsmnNaT0YM60L5540SH6aLwBOGcq3KFxSXMXrmVGbkbmLVkIwW7DtCwfj1O79uW757bl/MGdiCtScNEh+kq4QnCOVclDhQV895nm5kRPs28fW8hqQ3qM6p/O7IyOjKqXzuaN/YuLmoTTxDOuaO292ARby0vYEZuPm8u28TuA0U0b5zCuQM6kJWRzhl925Ha0J9mrq08QTjnjsiOfYW8sWwjMxbl8/anBRwoKqF104ZccEJHsjLSOaV3Wxqm+NPMdYEnCOdcpbbsPsBrSzYyIzefDz7fTGGx0aFFIy4f3pWsjI4M79GKFO/ios7xBOGciyp/x/5Dw3DOWbWVEoOurVMZf2pPsjLSObFLGvW8i4s6zROEc+6QtVv3MiN3AzNy85m/ZjsAfdo345ZRfRgzKJ1BnVr408xJxBOEc0luxaZdzFiUT/bifBbn7QRgUKcW/GD0cWRlpNOnffMER+gSJa4JQlIaMAXIAAy43sw+jCg/C/gnsCqc9aKZ/TwsywIeBOoDU8zs1/GM1blkYWYsztsZjs28gc8L9gAwtFsaPz5/AGMGpdOtTZMER+lqgnhfQTwIZJvZpZIaAtE+de+a2QWRMyTVB/4CnAesA+ZKesXMlsQ5XufqpJISY/7a7WTnbiB7cT5rt+6jnmBkzzZce0oPRg9MJ72lP83sDhe3BCGpBXAGcB2AmR0EDsa4+ghghZmtDLf1LHAR4AnCuRgVFZcwZ/VWsnODLi427jxAg/ri1D5tuXVUH84d0IE2zRolOkxXg8XzCqIXUABMkzQYmAfcYWZ7yix3sqRPgDzgB2a2GOgMrI1YZh0wMtpOJE0CJgF069atao/AuVrmYFEJ73++mexF+by2dCNb9xykcYN6nHlcO7Iy0jm7fwdapvrTzC428UwQKcBQ4DYzmy3pQeAe4CcRy3wMdDez3ZLOB14G+gLRbpOwaDsxs8nAZIDMzMyoyzhXl+07WMzbnxaQnbuB/yzbxK79RTRrlMLZ/duTlZHOWf3a0aSh34/ijlw8PzXrgHVmNjucfoEgQRxiZjsj3v9b0kOS2obrdo1YtAvBFYZzDti1v5A3lm0iOzeft5YXsK+wmLQmDcgalE5WRjqn9mlL4wbexYU7NnFLEGaWL2mtpH5mthw4hzJtCJLSgY1mZpJGAPWALcB2oK+knsB64HLgynjF6lxtsG3PQV5bupHs3Hze+2wzB4tLaNusEZcM7czYjI6M7NWaBv40s6tC8b7uvA14KryDaSUwXtJNAGb2MHApcLOkImAfcLmZGVAk6VZgJsFtro+GbRPOJZVNu/Yzc/FGZubm8+HKLRSXGJ3TUhl3UnfGHp/O0G6tqO9PM7s4UfB9XDdkZmZaTk5OosNw7pis27b30J1HOV9swwx6tm1KVkY6YzPSOb5zS3+a2VUZSfPMLDNambdcOVcDrCzYzYwwKSxctwOA/unNueOcvozN6MhxHZp5UnDVzhOEcwlgZizL3xUkhdx8lm/cBcDgLi35YVZ/sjLS6dm2aYKjdMnOE4Rz1cTM+GTdDmbkbmBmbj6rt+xFguHdW3PfBQMZk5FO57TURIfp3CGeIJyLo+ISI2f1VrIXB1cKeTv2k1JPnNy7DTec0YvRA9Np19yfZnY1kycI56pYYXEJH36+hezF+cxanM/m3QdpmFKPM/q25Xuj+3HugPakNWmY6DCdq5QnCOeqwP7CYt79bDPZufm8vnQjO/YV0qRhfUb1C55mHtW/Pc0a+Z+bq138E+vcUdpzoIg3lwdPM7+5bBN7DhbTvHEK5w3oQFZGOmcc186fZna1micI58rx8vz1PDBzOXnb99EpLZW7xvRjVL/2vL50I9mL83nn0wIOFJXQpmlDvn5iJ7IyOnJyrzY0TPGnmV3dUG6CkNS6ohXNbGvVh+NczfDy/PX86MVF7CssBmD99n187/kFmAW9Rqa3aMwVI7qRlZHO8B6t/WlmVydVdAUxj+BvQUA3YFv4Pg1YA/SMe3TOJcgDM5cfSg6lSgyaNUrhyQkjGNwljXqeFFwdV+61sJn1NLNeBP0hXWhmbc2sDXAB8GJ1BehcIuRt3xd1/p4DRQzp1sqTg0sKsVSWDjezf5dOmNkM4Mz4heRc4jUt546jTv4gm0sisTRSb5Z0LzCdoMppHEGX3M7VSQ+9tYLdB4qoX08Ul3zZmWVqg/rcNaZfAiNzrnrFcgVxBdAOeCl8tQvnOVfnPPHhau7PXs7XB3figW+eQOe0VAR0TkvlV5ccz8VDOic6ROeqTaVXEOHdSndIamZmu6shJucS4oV567jvn4s5d0B7fnfZYBrUr8clw7okOiznEqbSKwhJp0haQjganKTBkh6Ke2TOVaMZizZw9wufcErvNvz5yqE+MptzxFbF9AdgDGG7g5l9ApwRz6Ccq05vf1rA7c/OZ3DXNP52TaY//excKKZ/k8xsbZlZxVEXdK6WmbNqKzc+mUOf9s157LoR5d695FwyiuWvYa2kUwALx5a+HVga37Cci7+F67Zz/WNz6ZSWypMTRtCySYNEh+RcjRLLFcRNwC1AZ2AdcGI47Vyt9enGXVz76BxapjZg+oSRtG3mYzI4V1aFVxCS6gNXm9lV1RSPc3H3xZY9jJsym5T69Xhq4kh/+M25clR4BWFmxcBFR7txSWmSXpC0TNJSSSeXKb9K0sLw9YGkwRFlqyUtkrRAUs7RxuBcpA079nHVlNkcLC5h+oSR9PBxn50rVyxtEO9L+jPwHLCndKaZfRzDug8C2WZ2adh+0aRM+SrgTDPbJmksMBkYGVE+ysw2x7Af5yq1efcBxk2Zzfa9hTx9w0j6pTdPdEjO1WixJIhTwp8/j5hnwNkVrSSpBcHtsNcBmNlB4GDkMmb2QcTkR4A/leTiYse+Qq6ZOof12/fxxPUjOaFLWqJDcq7Gi+VJ6lFHue1eQAEwLaw6mgfcYWZ7yll+AjAjctfALEkGPGJmk6OtJGkSMAmgW7duRxmqq8v2HChi/LQ5fLZpF3+7JpMRPSsc6sQ5F6powKBxZjZd0veilZvZ72PY9lDgNjObLelB4B7gJ1H2NYogQZwWMftUM8uT1B54TdIyM3snShyTCaqmyMzMtLLlLrntLyxm0pM5LFi7nb9cOZSz+rVPdEjO1RoVNVKXtt41L+dVmXXAOjObHU6/QJAwDiPpBGAKcJGZHeol1szywp+bCDoJHBHDPp07pLC4hNuemc/7K7Zw/6WDGXt8x0SH5FytUu4VhJk9Ev782dFs2MzyJa2V1M/MlgPnEPbnVEpSN4LBh642s08j5jcF6pnZrvD9aA5vA3GuQsUlxg/+/gmvLdnIz74+iEu90z3njlilbRCSphG0BxzGzK6PYfu3AU+FdzCtBMZLuilc/2HgPqAN8JAkgCIzywQ6AC+F81KAp80sO6YjcknPzLj35Vz+uSCPu8b049pTeiQ6JOdqpVjuYno14n1j4BtAXiwbN7MFQGaZ2Q9HlE8EJkZZbyUwuOx85ypjZvzy30t5Zs4abj6rN7eM6pPokJyrtWK5i+kfkdOSngFej1tEzh2D/31jBX97dxVXn9Sdu330N+eOydF0et8X8PtJXY0z9b1V/P61T7lkSGd+9vVBhFWUzrmjFEsbxC6CNgiFP/OBH8Y5LueOyHNz1/CLV5cwZlAH7r/0BOrV8+Tg3LGKpYrJ+yNwNdr/fZLHPS8u4vS+bfnTFUNI8dHgnKsSsVxBfOXZhUgx9snkXFy8sWwjdz63gMzurZh8dSaNUnw0OOeqSix3MT1E8IDbQoJqphOA2UAhMfTJ5Fy8fPD5Zm6a/jEDOrZg6nXDSW3oycG5qhTLtfhqYJiZZZrZMGAIsMLMRpmZJweXEPPXbOOGx3Po3roJj18/ghaNfTQ456paLAmiv5ktKp0ws1yCUeWcS4ilG3Zy3bS5tGnWiOkTR9K6acNEh+RcnRRLFdNSSVOA6QRVSuPwMaldgqws2M3VU+eQ2qA+T00cSYcWjRMdknN1ViwJYjxwM3BHOP0O8Ne4ReRcOdZv38e4KbMpMWP6xJPo2rrs+FPOuaoUy22u+yU9DPw77HTPuWq3add+rvrbR+w6UMQzN5xEn/bNEh2Sc3VepW0Qkr4OLACyw+kTJb0S78CcK7V970GumTqHjTsP8Nj44WR0bpnokJxLCrE0Uv+UYCyG7XCoA74ecYzJuUN2Hyji2mlzWVmwh79dk8mw7j4anHPVJZYEUWRmO+IeiXNl7C8sZsJjc8ldv4M/XzmE0/q2TXRIziWVWBqpcyVdCdSX1Be4HfggvmG5ZHewqISbp89jzuqt/OGyExk9KD3RITmXdGK5grgNGAQcAJ4GdgDfjWdQLrkVlxh3PreAN5cX8N8XZ3DxkM6JDsm5pFThFYSk+sDPzOwu4MfVE5JLZiUlxj3/WMi/Fm3g/53fn6tGdk90SM4lrQqvIMysGBhWTbG4JGdm/PzVJfx93jpuP7sPk87oneiQnEtqsbRBzA9va/07sKd0ppm9GLeoXFL6w2uf8tgHqxl/ag/uPO+4RIfjXNKLJUG0BrZweK+tBniCcFXmkbc/509vrODbmV2574KBPhqcczVALE9Sj6+OQFzyemr2F/xqxjK+dkJHfnnJ8Z4cnKsh4jr0lqQ0SS9IWiZpqaSTy5RL0p8krZC0MHJwIknXSvosfF0bzzhd4rw8fz33vpzL2f3b84fLTqS+DxXqXI0RSxXTsXgQyDazSyU1BMr2rjYW6Bu+RhJ0AjhSUmuCJ7gzCaqz5kl6xcy2xTleV41mLc7n+3//hJE9W/PQVUNpmOJDhTpXk8TtL1JSC+AMYCqAmR00s+1lFrsIeMICHwFpkjoCY4DXzGxrmBReA7LiFaurfu99tplbn55PRueWTLl2OI0b+GhwztU0sXTWd4ekFmF10FRJH0saHcO2ewEFwDRJ8yVNkdS0zDKdgbUR0+vCeeXNjxbfJEk5knIKCgpiCMsl2rwvtnLDEzn0ateUx8cPp1mjeF/IOueORixXENeb2U5gNNCOYHyIX8ewXgrBWNZ/NbMhBLfI3lNmmWgVzlbB/K/ONJscDoea2a5duxjCcomUu34H102bS3rLxjwxYQRpTXw0OOdqqlgSROmX9fnANDP7hOhf4GWtA9aZ2exw+gWChFF2ma4R012AvArmu1psxaZdXPPoHJo3SmH6xJG0b+6jwTlXk8WSIOZJmkWQIGZKag6UVLaSmeUDayX1C2edAywps9grwDVh9dVJwA4z2wDMBEZLaiWpFcHVy8zYDsnVRGu37mXclDnUk3jqhpPonJaa6JCcc5WIpfJ3AnAisNLM9kpqQ1DNFIvbgKfCO5hWAuMl3QRgZg8D/yZIPCuAvaXbNbOtkn4BzA2383Mz2xrjPl0Nk79jP1dO+Yh9hcU8O+kkerYt2xTlnKuJZBa1av/whaRLgNMI2gHeM7OX4h3Y0cjMzLScnJxEh+EibN1zkMse+ZAN2/cxfeJIhnRrleiQnHMRJM0zs8xoZbHcxfQQcBOwCMgFbpT0l6oN0dVFO/cXcs2js1m7dS9Trh3uycG5WiaWKqYzgQwLLzUkPU6QLJwr196DRVw/bS7LNuxi8jXDOLl3m0SH5Jw7QrE0Ui8HukVMdwUWxiccVxccKCrmxifn8fGabfzx8hM5u3+HRIfknDsKsVxBtAGWSpoTTg8HPgy7AMfMvh6v4FztU1Rcwu3PzOfdzzZz/zdP4IITOiU6JOfcUYolQdwX9yhcnVBSYtz9wkJmLt7IfRcM5LLhXStfyTlXY8XS3ffbkjoQXHMS4mcAABXBSURBVDkAzDGzTfENy9U2ZsZPX1nMi/PX8/3zjuP603omOiTn3DGK5S6my4A5wLeAy4DZki6Nd2Cudrl/5nKe/OgLbjyjF7ee3SfR4TjnqkAsVUw/BoaXXjVIage8TtB1hnP85c0V/PWtz7lqZDfuGdvfB/xxro6I5S6memWqlLbEuJ5LAo9/sJoHZi7n4hM78YuLMjw5OFeHxHIFkS1pJvBMOP1tgi4yXJJ7Yd46fvrKYs4b2IEHvjWYej4anHN1SiyN1HdJ+iZwKkEvrpNralcbrvrMWLSBu1/4hNP6tOV/rxhCg/p+UelcXRPTSC1m9g/gH3GOxdUSby3fxO3PzmdIt1ZMvmaYjwbnXB0Vy11Ml0j6TNIOSTsl7ZK0szqCczXP7JVbuGn6PPq2b86j1w2nSUMfDc65uiqWv+77gQvNbGm8g3E12ydrtzPh8Rw6p6Xy5IQRtExtkOiQnHNxFEvF8UZPDm55/i6unTaHtCYNmD5xJG2aNUp0SM65OCv3CiIcAwIgR9JzwMvAgdJyM3sxzrG5GmL15j2MmzqbhvXr8dTEkXRs6aPBOZcMKqpiujDi/V6CYT9LGeAJIgnkbd/HVVNmU1RcwvM3nkz3Nj4anHPJotwEYWaxDivq6qjNuw8wbspsdu4r5OkbTqJvh+aJDsk5V438FhQX1Y69hVw9dQ55O/bx5ISRHN+lZaJDcs5VM3+6yX3FngNFXPfYHD7ftJvJV2cyvEfrRIfknEsAv4Jwh9lfWMwNT+SwcN0O/nLlUM44rl2iQ3LOJchRJQhJQ83s4xiWWw3sAoqBIjPLLFN+F3BVRCwDgHZmtrWydV3VKywu4danP+aDz7fw+8sGk5WRnuiQnHMJdLRXEDcDN8S47Cgz2xytwMweAB4AkHQhcKeZbY1lXVe1ikuM7z//Ca8v3cQvLhrEJUO7JDok51yCHVUbhJnFmhyOxBV82WOsq0Zmxr0vL+KVT/L4YVZ/rj65R6JDcs7VAJVeQUgaGmX2DuALMyuqZHUDZkky4BEzm1zOPpoAWcCtR7HuJGASQLdu3SoJx5VlZvzPv5byzJy13DKqNzef1TvRITnnaohYqpgeAoYCCwm6+84I37eRdJOZzapg3VPNLE9Se+A1ScvM7J0oy10IvF+meimmdcPEMRkgMzPTYjgeF+FP/1nBlPdWce3J3fnB6H6JDsc5V4PEUsW0GhhiZplmNgwYAuQC5xJ05FcuM8sLf24CXgJGlLPo5ZSpXjqCdd1RmvLuSv7w+qd8c2gXfnrhIB8Nzjl3mFgSRH8zW1w6YWZLCBLGyopWktRUUvPS9wRddeRGWa4lcCbwzyNd1x29Z+es4b//tZSxGen85pvH+2hwzrmviKWKabmkvwLPhtPfBj6V1AgorGC9DsBL4X+lKcDTZpYt6SYAM3s4XO4bwCwz21PZujEek6vEK5/k8aOXFnHmce344+UnkuKjwTnnopBZxdX2klKB7wCnEbRBvEfQLrEfaGJmu+MdZKwyMzMtJycn0WHUaK8v2chN0+cxtHsrHh8/gtSGPhqcc8lM0rzynjOL5QoiC/izmf0uSlmNSQ6uch+s2Mx3nv6YgZ1aMPXaTE8OzrkKxVK38HWCKqUnJX1NknfPUQt9vGYbE5/IoUebJjw+fgTNG/tocM65ilWaIMJuv/sAfweuBD6XNCXegbmqsyRvJ9c9Ood2zRsxfcJIWjVtmOiQnHO1QExXA2ZWKGkGwcNrqcBFwMR4BuaqxucFu7nm0dk0bZTC9Akjad+icaJDcs7VEpVeQUjKkvQYsAK4FJgCdIxzXK4KrNu2l3FTZmMG0yeOpGvrJokOyTlXi8RyBXEdwS2uN5rZgUqWdTXEpp37uWrKbPYcKOLZSSfTu12zRIfknKtlKk0QZnZ55LSkU4ErzeyWuEXljsm2PQe5euocCnYd4MkJIxnYqUWiQ3LO1UIxtUFIOpGggfoyYBXwYjyDckdv1/5Crps2h1Vb9jDtuuEM694q0SE552qpchOEpOMI+ki6AtgCPEfwYN2oaorNHaF9B4uZ8HgOuXk7eWTcME7t0zbRITnnarGKriCWAe8CF5rZCgBJd1ZLVO6IHSwq4ean5jF39Vb++O0TOXdgh0SH5Jyr5Sq6i+mbQD7wpqS/STqHoKsNV8MUFZfw3efm89byAn75jeO56MTOiQ7JOVcHlJsgzOwlM/s20B94C7gT6CDpr5JGV1N8rhIlJcY9Ly7i34vyufdrA7hihA+a5JyrGrE8Sb3HzJ4yswuALsAC4J64R+YqZWb8/NUlvDBvHXec05eJp/dKdEjOuTrkiPp5NrOtZvaImZ0dr4Bc7H4361Me+2A1E07ryXfP7ZvocJxzdYwPBFBL/fWtz/nzmyu4fHhX7v3aAB8NzjlX5TxB1EJPfria32Qv48LBnfifbxzvycE5FxeeIGqZFz9ex0/+uZhzB7Tn95cNpr4PFeqcixNPELVIdm4+d72wkFN6t+HPVw6lgQ8V6pyLI/+GqSXe+bSA25+ZzwldWvK3azJp3MBHg3POxZcniFpg7uqtTHoyh17tmvLYdSNo2sgH9XPOxZ8niBoud/0Orp82l04tU3lywkhaNvGhQp1z1SOuCULSakmLJC2QlBOl/CxJO8LyBZLuiyjLkrRc0gpJSflg3mcbd3H11Nm0SG3A9Ikjade8UaJDcs4lkeqoqxhlZpsrKH83fEr7EEn1gb8A5wHrgLmSXjGzJXGMs0ZZs2Uv46bOJqV+PZ6aOJJOaamJDsk5l2RqahXTCGCFma00s4MEI9pdlOCYqk3+jv1cNfUjDhSVMH3CSHq0bZrokJxzSSjeCcKAWZLmSZpUzjInS/pE0gxJg8J5nYG1EcusC+d9haRJknIk5RQUFFRd5AmyZfcBxk2dzdbdB3l8/Aj6pTdPdEjOuSQV7yqmU80sT1J74DVJy8zsnYjyj4HuZrZb0vnAy0BfoncrbtF2YGaTgckAmZmZUZepLXbuL+SaR+ewduteHr9+BIO7piU6JOdcEovrFYSZ5YU/NwEvEVQdRZbvNLPd4ft/Aw0ktSW4YugasWgXIC+esSba3oNFXD9tLp9u3MXDVw/jpF5tEh2Scy7JxS1BSGoqqXnpe2A0kFtmmXSFHQlJGhHGswWYC/SV1FNSQ4KhT1+JV6yJdqComBufnMfHa7bx4OVDGNWvfaJDcs65uFYxdQBeCr//U4CnzSxb0k0AZvYwcClws6QiYB9wuZkZUCTpVmAmUB941MwWxzHWhCksLuG2p+fz7mebeeDSEzj/+I6JDsk55wBQ8H1cN2RmZlpOzlcet6ixSkqM7z2/gJcX5PFfFw7kulN7Jjok51ySkTTPzDKjldXU21zrPDPjJ//M5eUFedw1pp8nB+dcjeMJIgHMjF/PWMZTs9dw05m9+c5ZvRMdknPOfYUniAT4y5sreOSdlYw7qRs/zOrnA/4452okTxDVbNr7q/jtrE+5ZEhnfv71DE8OzrkayxNENXo+Zy0/+78ljBnUgfsvPYF6Phqcc64G8wRRTf61cAP3/GMhp/dty5+uGEKKjwbnnKvh/FuqGry5bBPffW4+Q7u14pGrh9EoxUeDc87VfJ4g4uyjlVu4afo8+qU359Hxw2nS0EeDc87VDp4g4mjB2u1MeGwuXVs34fHxI2jR2EeDc87VHp4g4mRZ/k6ufXQOrZs1ZPqEkbRp5qPBOedqF08QcbBq8x7GTZlD4wb1eGrCSaS3bJzokJxz7oh5hXgVy9u+j3FTZlNixrMTT6JbmyaJDsk5546KX0FUoYJdBxg3ZTY79xfyxPUj6NPeR4NzztVeniCqyI69hVw9dTYbduxn2nXDyejcMtEhOefcMfEEUQV2Hyji2mlzWFmwh8nXDCOzR+tEh+Scc8fM2yCO0f7CYm54PIdF63fw0FVDOb1vu0SH5JxzVcKvII5BYXEJ33nqYz5atYXffusExgxKT3RIzjlXZTxBHKXiEuPO5xbwxrJN/OKiDL4xpEuiQ3LOuSrlCeIomBn/78VFvLpwAz8a259xJ3VPdEjOOVflPEEcITPjF68u5bmctdx2dh9uPNNHg3PO1U2eII7QH1//jEffX8V1p/Tge+cdl+hwnHMubuJ6F5Ok1cAuoBgoMrPMMuVXAT8MJ3cDN5vZJ7Gsmwh/e2clD/7nM741rAv3XTDQR4NzztVp1XGb6ygz21xO2SrgTDPbJmksMBkYGeO61erp2Wv4n38v5WvHd+TX3/TR4JxzdV9Cn4Mwsw8iJj8CauStQP9csJ4fv7yIs/q14w/fPpH6nhycc0kg3m0QBsySNE/SpEqWnQDMONJ1JU2SlCMpp6CgoApCPtxrSzbyvec/YUSP1jw8bhgNU7zZxjmXHOJ9BXGqmeVJag+8JmmZmb1TdiFJowgSxGlHuq6ZTSaomiIzM9OqMvj3V2zmlqc/JqNzS6ZeN5zGDXyoUOdc8ojrv8Nmlhf+3AS8BIwou4ykE4ApwEVmtuVI1o2neV9s44YncujZpimPjx9Os0beK4lzLrnELUFIaiqpeel7YDSQW2aZbsCLwNVm9umRrBtPi/N2MH7aHNo3b8STE0eQ1qRhde3aOedqjHj+W9wBeCm8FTQFeNrMsiXdBGBmDwP3AW2Ah8LlSm9njbpuHGM95POC3VwzdQ7NGqUwfeJI2jf30eCcc8lJZlVabZ9QmZmZlpOTc9Trr926l8se+ZDC4hKev/FkerVrVoXROedczSNpXnnPmSV9xfrL89fzwMzl5G3fR716okE9eOmW0zw5OOeSXlLfs/ny/PX86MVFrN++DyPoodUQy/N3JTo055xLuKROEA/MXM6+wuLD5h0oKuGBmcsTFJFzztUcSZ0g8rbvO6L5zjmXTJI6QXRKSz2i+c45l0ySOkHcNaYfqWWejk5tUJ+7xvRLUETOOVdzJPVdTBcP6Qxw6C6mTmmp3DWm36H5zjmXzJI6QUCQJDwhOOfcVyV1FZNzzrnyeYJwzjkXlScI55xzUXmCcM45F5UnCOecc1HVqd5cJRUAXyQ6jmPUFtic6CBqCD8Xh/PzcTg/H186lnPR3czaRSuoUwmiLpCUU17Xu8nGz8Xh/Hwczs/Hl+J1LryKyTnnXFSeIJxzzkXlCaLmmZzoAGoQPxeH8/NxOD8fX4rLufA2COecc1H5FYRzzrmoPEE455yLyhNENZLUVdKbkpZKWizpjnB+a0mvSfos/NkqnC9Jf5K0QtJCSUMTewRVT1J9SfMlvRpO95Q0OzwXz0lqGM5vFE6vCMt7JDLueJCUJukFScvCz8jJSf7ZuDP8O8mV9Iykxsn0+ZD0qKRNknIj5h3x50HSteHyn0m69khi8ARRvYqA75vZAOAk4BZJA4F7gP+YWV/gP+E0wFigb/iaBPy1+kOOuzuApRHTvwH+EJ6LbcCEcP4EYJuZ9QH+EC5X1zwIZJtZf2AwwXlJys+GpM7A7UCmmWUA9YHLSa7Px2NAVpl5R/R5kNQa+CkwEhgB/LQ0qcTEzPyVoBfwT+A8YDnQMZzXEVgevn8EuCJi+UPL1YUX0CX8kJ8NvAqI4GnQlLD8ZGBm+H4mcHL4PiVcTok+hio8Fy2AVWWPKYk/G52BtUDr8Pf9KjAm2T4fQA8g92g/D8AVwCMR8w9brrKXX0EkSHgJPASYDXQwsw0A4c/24WKlfySl1oXz6oo/AncDJeF0G2C7mRWF05HHe+hchOU7wuXril5AATAtrHKbIqkpSfrZMLP1wG+BNcAGgt/3PJL381HqSD8Px/Q58QSRAJKaAf8AvmtmOytaNMq8OnFfsqQLgE1mNi9ydpRFLYayuiAFGAr81cyGAHv4svogmjp9PsJqkIuAnkAnoClBNUpZyfL5qEx5x39M58UTRDWT1IAgOTxlZi+GszdK6hiWdwQ2hfPXAV0jVu8C5FVXrHF2KvB1SauBZwmqmf4IpEkqHQo38ngPnYuwvCWwtToDjrN1wDozmx1Ov0CQMJLxswFwLrDKzArMrBB4ETiF5P18lDrSz8MxfU48QVQjSQKmAkvN7PcRRa8ApXcXXEvQNlE6/5rwDoWTgB2ll5e1nZn9yMy6mFkPgsbHN8zsKuBN4NJwsbLnovQcXRouX2f+QzSzfGCtpH7hrHOAJSThZyO0BjhJUpPw76b0fCTl5yPCkX4eZgKjJbUKr8pGh/Nik+hGmGR6AacRXN4tBBaEr/MJ6kr/A3wW/mwdLi/gL8DnwCKCOzoSfhxxOC9nAa+G73sBc4AVwN+BRuH8xuH0irC8V6LjjsN5OBHICT8fLwOtkvmzAfwMWAbkAk8CjZLp8wE8Q9D+UkhwJTDhaD4PwPXheVkBjD+SGLyrDeecc1F5FZNzzrmoPEE455yLyhOEc865qDxBOOeci8oThHPOuag8QbikIckk/S5i+geS/quSdc6SdEocYrlO0p+PYr1Okl6o6nici8YThEsmB4BLJLU9gnXOIniCt8pEPAl8xMwsz8wurXxJ546dJwiXTIoIxu69s2yBpHaS/iFpbvg6NexQ8SbgTkkLJJ0paWX4tGqapBJJZ4TrvyupT9hf/8thn/wfSTohLP8vSZMlzQKeKLPvr0n6sGziCve3IHzNl9RcUo/S8QHCDv1Kywsk/TScf1d4DAsl/azKz6JLGkf9n4xztdRfgIWS7i8z/0GCcQbek9SNoBvpAZIeBnab2W8BJH0KDCToRG4ecLqk2UAXM1sh6X+B+WZ2saSzCZLBieE+hgGnmdk+SdeF2/sG8D3gfDPbViamHwC3mNn7YQeP+yMLzWxiuI3uBN0nPCZpNMGYACMInq59RdIZZvbOMZwzl6Q8QbikYmY7JT1BMBjNvoiic4GBQbc/ALSQ1DzKJt4FziBIEL8CbgDeBuaG5acB3wz39YakNpJahmWvmFnkPkcBmcBoi96r7/vA7yU9BbxoZusi4gNAUmkXE7ea2ReSbiPob2d+uEgzgoThCcIdMa9icsnojwT92jSNmFePYMCZE8NXZzPbFWXdd4HTCf5D/zeQRtBOUfoFXFH3ynvKzF8JNAeOixakmf0amAikAh9J6h9lsYcJksfrEfv/VcRx9DGzqdG271xlPEG4pGNmW4Hn+XK4SoBZwK2lE5JKq4V2EXyJl5pN0GhdYmb7CTpcvJEgcUCQKK4Kt3EWsLmcqwOAL4BLgCckDSpbKKm3mS0ys98QdOLXv0z5LUDzMJGUmglcH1ZJIamzpPY4dxQ8Qbhk9TsgslH4diAzbNhdQtA4DfB/wDfChuDTzewAwQhdH4Xl7xIkkEXh9H+Vbgf4NV92zRyVmS0nSCh/l9S7TPF3JeVK+oSgOmxGmfIfAMdHNFTfZGazgKeBDyUtIhhXIlpVmXOV8t5cnXPOReVXEM4556LyBOGccy4qTxDOOeei8gThnHMuKk8QzjnnovIE4ZxzLipPEM4556L6/7qRVjGFGqQ2AAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "num_of_nodes = [100,500,1000]\n",
    "hops_per_nodes = []\n",
    "for nodes in num_of_nodes:\n",
    "    print(\"Creating network for \", nodes)\n",
    "    chord = Chord(nodes)\n",
    "    hops_needed = []\n",
    "    print(\"Searching,\")\n",
    "    for i in range(0,1000000):\n",
    "        key = random.choice(chord.keys)\n",
    "        hops = chord.find_key(key)\n",
    "        if hops is not None:\n",
    "            hops_needed.append(hops)\n",
    "    hops_per_nodes.append(np.mean(hops_needed))\n",
    "    vals,probs = get_prob_distribution(hops_needed)\n",
    "    plt.clf()\n",
    "    plt.bar(vals, probs,width=0.3)\n",
    "    #plt.hist(hops_needed) # density\n",
    "    plt.ylabel('Probability')\n",
    "    plt.xlabel('Number of hops')\n",
    "    plt.title(\"Distribution of hops required for 1 million queries in \"+str(nodes) +\" size network\")\n",
    "    plt.savefig(str(nodes)+\"_chord_search_queries.svg\")\n",
    "    print(\"deleting 50% nodes\")\n",
    "    chord.delete_nodes(int(nodes*.5))\n",
    "    print(\"searching for queries\")\n",
    "    for i in range(0,1000000):\n",
    "        key = random.choice(chord.keys)\n",
    "        hops = chord.find_key(key)\n",
    "        if hops is not None:\n",
    "            hops_needed.append(hops)\n",
    "    vals,probs = get_prob_distribution(hops_needed)\n",
    "    plt.clf()\n",
    "    plt.bar(vals, probs,width=0.3)\n",
    "    #plt.hist(hops_needed) # density\n",
    "    plt.ylabel('Probability')\n",
    "    plt.xlabel('Number of hops')\n",
    "    plt.title(\"Distribution of hops required for 1 million queries after deletion\")\n",
    "    plt.savefig(str(nodes)+\"_chord_delete_search_queries.svg\")\n",
    "    \n",
    "plt.clf()\n",
    "plt.plot(num_of_nodes, hops_per_nodes,'o-')\n",
    "#plt.hist(hops_needed) # density\n",
    "plt.ylabel('Avg. hops required')\n",
    "plt.xlabel('Network size')\n",
    "plt.title(\"Avg hops vs Pastry network size\")\n",
    "plt.savefig(\"chord_avg_hops_needed.svg\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Lookup route of key, 443636  : 339802 -> 406612 -> 439539 -> 443008 -> 443620 -> 445408\n",
      "\n",
      "Lookup route of key, 793980  : 339802 -> 604542 -> 737729 -> 773200 -> 789882 -> 793125 -> 794210\n",
      "\n",
      "Lookup route of key, 581388  : 339802 -> 473113 -> 541369 -> 574480 -> 579174 -> 581268 -> 581785\n",
      "\n",
      "Lookup route of key, 677453  : 339802 -> 604542 -> 670131 -> 675207 -> 676548 -> 677094 -> 678426\n",
      "\n",
      "Lookup route of key, 312023  : 339802 -> 864870 -> 80052 -> 211957 -> 279246 -> 297321 -> 306900 -> 311378 -> 312498\n",
      "\n",
      "Lookup route of key, 492485  : 339802 -> 473113 -> 490930 -> 492425 -> 492964\n",
      "\n",
      "Lookup route of key, 1001091  : 339802 -> 864870 -> 995976 -> 1000543 -> 1008914\n",
      "\n",
      "Lookup route of key, 915454  : 339802 -> 864870 -> 897943 -> 906407 -> 910892 -> 913026 -> 913952 -> 918690\n",
      "\n",
      "Lookup route of key, 189274  : 339802 -> 864870 -> 80052 -> 148233 -> 181162 -> 185383 -> 187565 -> 188668 -> 189191 -> 190928\n",
      "\n",
      "Lookup route of key, 632042  : 339802 -> 604542 -> 623331 -> 632006 -> 632873\n",
      "\n"
     ]
    }
   ],
   "source": [
    "for i in range(0,10):\n",
    "    chord.find_key_and_route()\n",
    "    print()\n",
    "id_to_node[list(id_to_node.keys())[0]].print_finger_table()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6.643856189774725"
      ]
     },
     "execution_count": 103,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "math.log(100,2)"
   ]
  },
  {
   "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}