from numpy import *
import operator

def createdataset():
        group = array([
                        [0, 0],[0, 0.5],[0, 1],
                        [1.0, 1.1], [1.0, 1.5],[1.0, 2.0],
                        [2.0,2.0],[2.0,2.5],[2.0,3.0],
                        [3.0,3.0],[3.0,3.5],[3.0,4.0],
                        [4.0,4.0],[4.0,4.5],[4.0,5.0],
                        [5.0,5.0],[5.0,5.5],[5.0,6.0],
                        [6.0,6.0],[6.0,6.5],[6.0,7.0],
                        [7.0,7.0],[7.0,7.5],[7.0,8.0],
                        [8.0,8.0],[8.0,8.5],[8.0,9.0],
                        [9.0,9.0],[9.0,9.5],[9.0,10.0],
                        [10.0,10.0],[10.0,10.5],[10.0,11.0],
                        [11.0,11.0],[11.0,11.5],[11.0,12.0],
                        [12.0,12.0],[12.0,12.5],[12.0,13.0],
                        [13.0,13.0],[13.0,13.5],[13.0,14.0],
                        [14.0,14.0],[14.0,14.5],[14.0,15.0],
                        [15.0,15.0],[15.0,15.5],[15.0,16.0],
                        [16.0,16.0],[16.0,16.5],[16.0,17.0],
                        [17.0,17.0],[17.0,17.5],[17.0,18.0],
                        [18.0,18.0],[18.0,18.5],[18.0,19.0],
                        [19.0,19.0],[19.0,19.5],[19.0,20.0],
                        [20.0,20.0],[20.0,20.5],[20.0,21.0],
                        [21.0,21.0],[21.0,21.5],[21.0,22.0],
                        [22.0,22.0]])
        labels = ['A', 'a', 'B', 'b', 'C', 'c', 'D', 'd', 'E', 'e', 'F', 'f', 'G', 'g', 'H', 'h', 'I', 'i', 'J', 'j', 'K', 'k', 'L', 'l', 'M', 'm', 'N', 'n', 'O', 'o', 'P', 'p', 'Q', 'q', 'R', 'r', 'S', 's', 'T', 't', 'U', 'u', 'V', 'v', 'W', 'w', 'X', 'x', 'Y', 'y', 'Z', 'z','@','!','_','%','~','1','2','3','4','5','6','7','8','9','0']
        return group, labels
def KNN_run(inx, data_set, labels, k):
        data_set_size = data_set.shape[0] 
        diff_mat = tile(inx, (data_set_size, 1)) - data_set
        sq_diff_mat = diff_mat**2
        sq_distances = sq_diff_mat.sum(axis=1)
        distances = sq_distances**0.5
        orted_dist_indicies = distances.argsort()
        class_count = {} 

        for i in range(k):
                vote_label = labels[orted_dist_indicies[i]]  
                class_count[vote_label] = class_count.get(vote_label, 0) + 1
        sorted_class_count = sorted(class_count.items(),
key=operator.itemgetter(1), reverse=True)
        return sorted_class_count[0][0]

#data=[[20,13],[9,5],[47,73],[11,54],[36,34],[90,60],[69,26],[69,59],[8,75],[44,18],[18,90],[68,71],[37,88],[16,21],[58,9],[96,77],[35,54],[23,33],[97,77],[76,47],[67,16],[28,13],[1,93],[45,12],[66,87],[15,74],[28,39],[99,1],[82,17],[99,42],[17,46],[75,21],[42,24],[97,15],[60,27],[60,35],[70,75],[18,89],[65,74],[73,30],[47,13],[93,39],[25,63]]
#K=5