Mercurial > hg > GlobalNeighbors

comparison globalneighbors/distance.py @ 8:e3d6919130ca

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
insert via BST
author Jeff Hammel <k0scist@gmail.com>
date Sun, 25 Jun 2017 11:21:28 -0700
parents 254195d0bac2
children 638fad06e556
comparison
equal deleted inserted replaced
7:254195d0bac2 8:e3d6919130ca
1 """ 1 """
2 distance functionality 2 distance functionality
3 """ 3 """
4 4
5 import argparse 5 import argparse
6 import bisect
6 import json 7 import json
7 import sys 8 import sys
8 import time 9 import time
9 from math import asin, sin, cos, sqrt, pi, fabs 10 from math import asin, sin, cos, sqrt, pi, fabs
10 from .cli import CitiesParser 11 from .cli import CitiesParser
49 distances.pop() 50 distances.pop()
50 break 51 break
51 else: 52 else:
52 distances.append((i, new_distance)) 53 distances.append((i, new_distance))
53 54
55 class KeyWrapper:
56 def __init__(self, iterable, key):
57 self.it = iterable
58 self.key = key
59
60 def __getitem__(self, i):
61 return self.key(self.it[i])
62
63 def __len__(self):
64 return len(self.it)
54 65
55 def insert_distance_bisect(distances, i, new_distance, k): 66 def insert_distance_bisect(distances, i, new_distance, k):
67
56 if not distances: 68 if not distances:
57 distances.append((i, new_distance)) 69 distances.append((i, new_distance))
58 return 70 return
59 if new_distance >= distances[-1][-1]: 71 if new_distance >= distances[-1][-1]:
60 if len(distances) < k: 72 if len(distances) < k:
61 distances.append((i, new_distance)) 73 distances.append((i, new_distance))
62 return 74 return
63 indices = [0, len(distances)]
64 while True:
65 midpoint = int((indices[-1] - indices[0])/2)
66 75
76 point = bisect.bisect_left(KeyWrapper(distances,
77 key=lambda x: x[-1]),
78 new_distance)
79 distances.insert(point, (i, new_distance))
80 if len(distances) == k+1:
81 distances.pop()
67 82
68 def calculate_distances(locations, r=Rearth): 83 def calculate_distances(locations, r=Rearth):
69 """ 84 """
70 WARNING! This is an N-squared approach 85 WARNING! This is an N-squared approach
71 """ 86 """