# inspired by
# http://techspot.zzzeek.org/2012/07/07/the-absolutely-simplest-consistent-hashing-example/
import hashlib
import bisect
import random

from collections import defaultdict


class Servers(object):

    def __init__(self, ips=[]):
        self._ips = {}
        self._hashed_ips = []
        for ip in ips:
            self.add(ip)

    def add(self, ip):
        hashed = self._hash(ip)
        self._ips[hashed] = ip
        bisect.insort(self._hashed_ips, hashed)

    def remove(self, ip):
        hashed = self._hash(ip)
        del self._ips[hashed]
        index = bisect.bisect_left(self._hashed_ips, hashed)
        del self._hashed_ips[index]

    def _hash(self, key):
        def _hexhash(key):
            return hashlib.md5(key).hexdigest()
        hash = _hexhash(key)
        return long(hash, 16)

    def select(self, username):
        hashed = self._hash(username)
        start = bisect.bisect(self._hashed_ips, hashed)
        if start == len(self._hashed_ips):
            start = 0
        return self._ips[self._hashed_ips[start]]


if __name__ == '__main__':
    selection = defaultdict(list)
    servers = Servers(['postgres1', 'postgres2', 'postgres3', 'postgres4',
                       'postgres5'])
    users = ['%06d' % i for i in range(100000)]

    for user in users:
        user_db = servers.select(user)
        selection[user_db].append(user)

    for db in selection:
        print('%d users in %s' % (len(selection[db]), db))

    # removing server 2 and 4
    servers.remove('postgres2')
    servers.remove('postgres4')
    print '===='

    selection = defaultdict(list)
    for user in users:
        user_db = servers.select(user)
        selection[user_db].append(user)

    for db in selection:
        print('%d users in %s' % (len(selection[db]), db))