# HG changeset patch # User Jeff Hammel # Date 1498407228 25200 # Node ID 254195d0bac2c7dc2ce84dfed498189e7abbf487 # Parent 316e1d54ffd44a4048e55e7aeb653f69aef8b9ad partial implementation of autocomplete using jqueryui; easyautocomplete.com may be more what we want diff -r 316e1d54ffd4 -r 254195d0bac2 globalneighbors/distance.py --- a/globalneighbors/distance.py Sat Jun 24 15:47:59 2017 -0700 +++ b/globalneighbors/distance.py Sun Jun 25 09:13:48 2017 -0700 @@ -38,6 +38,9 @@ keeping distances in order with maximum of size `k` """ + if len(distances) == k and new_distance >= distances[-1][-1]: + return + # TODO: Binary Search Tree for _index, (geoid, old_distance) in enumerate(distances): if new_distance < old_distance: @@ -48,14 +51,18 @@ else: distances.append((i, new_distance)) -# def insert_distance(distances, i, new_distance, k): -# if not distances: -# distances.append((i, new_distance)) -# return -# if new_distance >= distances[-1][-1]: -# if len(distances) < k: -# distances.append((i, new_distance)) -# return + +def insert_distance_bisect(distances, i, new_distance, k): + if not distances: + distances.append((i, new_distance)) + return + if new_distance >= distances[-1][-1]: + if len(distances) < k: + distances.append((i, new_distance)) + return + indices = [0, len(distances)] + while True: + midpoint = int((indices[-1] - indices[0])/2) def calculate_distances(locations, r=Rearth): @@ -124,8 +131,6 @@ # insert in order for i in (id1, id2): distances = neighbors.setdefault(i, []) - if len(distances) == k and new_distance >= distances[-1][-1]: - continue insert_distance(distances, i, new_distance, k) diff -r 316e1d54ffd4 -r 254195d0bac2 globalneighbors/grid.py --- a/globalneighbors/grid.py Sat Jun 24 15:47:59 2017 -0700 +++ b/globalneighbors/grid.py Sun Jun 25 09:13:48 2017 -0700 @@ -35,10 +35,24 @@ """ return neighbors of points i, j """ - imat = [] - jmat = [] + imat = [i] + jmat = [j] # latitude if i: imat.append(i-1) - raise NotImplementedError('TODO') + if i < self.n[0]-1: + imat.append(i+1) + + # longitude: wraps around + if j: + jmat.append(j-1) + else: + jmat.append(self.n[-1] - 1) + if j == self.n[-1] - 1: + jmat.append(0) + else: + jmat.append(j+1) + + return [(_i, _j) for _i in imat for _j in jmat + if (_i,_j) != (i,j)] diff -r 316e1d54ffd4 -r 254195d0bac2 globalneighbors/templates/index.html --- a/globalneighbors/templates/index.html Sat Jun 24 15:47:59 2017 -0700 +++ b/globalneighbors/templates/index.html Sun Jun 25 09:13:48 2017 -0700 @@ -2,9 +2,27 @@ Global Neighbors + + +

Global Neighbors

Serving {{ n_cities }} cities

+ +

+ Enter a city: + +

+ diff -r 316e1d54ffd4 -r 254195d0bac2 globalneighbors/web.py --- a/globalneighbors/web.py Sat Jun 24 15:47:59 2017 -0700 +++ b/globalneighbors/web.py Sun Jun 25 09:13:48 2017 -0700 @@ -22,21 +22,20 @@ from .template import TemplateLoader -def autocomplete(cities, startswith=None): +def autocomplete(cities, startswith=None, limit=None): """autocomplete function for city names""" - ### TODO: sort once, ahead of time + ### TODO: + # - sort once, ahead of time + # - return most populous cities if startswith: retval = [] for i in cities: - try: - if i[name].startswith(startswith): + if i[name].startswith(startswith): retval.append(i[name]) - except Exception as e: - import pdb; pdb.set_trace() - return sorted(retval) + return sorted(retval)[:limit] else: - return sorted([i[name] for i in cities]) + return sorted([i[name] for i in cities])[:limit] class Handler(object): @@ -71,7 +70,7 @@ def GET(self, request): return Response(content_type=self.content_type, body=json.dumps(self.cities( - startswith=request.GET.get('q')))) + startswith=request.GET.get('term')))) class GlobalHandler(Handler): diff -r 316e1d54ffd4 -r 254195d0bac2 tests/test_distance.py --- a/tests/test_distance.py Sat Jun 24 15:47:59 2017 -0700 +++ b/tests/test_distance.py Sun Jun 25 09:13:48 2017 -0700 @@ -6,6 +6,7 @@ import math import os +import random import unittest from globalneighbors import distance from globalneighbors.constants import Rearth @@ -127,6 +128,23 @@ distances = [i[-1] for i in value] assert distances == sorted(distances) + def test_insert_distances(self): + """test insert distances algorithm""" + + values = [(i, random.random()) + for i in range(1500)] + for k in (10, 100, 1000): + _distances = [] + for i, value in values: + distance.insert_distance(_distances, + i, + value, + k) + # since k is < 1500 + assert len(_distances) == k + ordered = [value[-1] for value in _distances] + assert sorted(ordered) == ordered + if __name__ == '__main__': unittest.main() diff -r 316e1d54ffd4 -r 254195d0bac2 tests/test_grid.py --- a/tests/test_grid.py Sat Jun 24 15:47:59 2017 -0700 +++ b/tests/test_grid.py Sun Jun 25 09:13:48 2017 -0700 @@ -54,6 +54,17 @@ city_locations = locations(read_cities(f)) self.grid_locations(city_locations) + def test_neighbors(self): + """test grid neighbor indexing""" + + grid = LatLonGrid(9, 9) + + neighbors = grid.neighbors(5,5) + expected = [(4,4), (4,5), (4,6), + (5,4), (5,6), + (6,4), (6,5), (6,6)] + assert sorted(neighbors) == sorted(expected) + ### generic (utility) functions