# -*- coding: utf-8 -*-

import io
import math
import sys
import os

sys.stdout = io.TextIOWrapper(sys.stdout.buffer, encoding='utf-8')
import requests
import re
import time


def spider():
	url = "http://bj.bendibao.com"
	headers = {
		'Accept': 'text/html,application/xhtml+xml,application/xml;q=0.9,image/webp,image/apng,*/*;q=0.8',
		'Accept-Encoding': 'gzip, deflate, br',
		'Accept-Language': 'zh-CN,zh;q=0.8,zh-TW;q=0.7,zh-HK;q=0.5,en-US;q=0.3,en;q=0.2',
		'Connection': 'keep-alive',
		# 'Host': 'baike.baidu.com',
		'Cookie': '0',
		'User-Agent': 'Mozilla/5.0 (Windows NT 10.0; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/69.0.3497.100 Safari/537.36',
		'Upgrade-Insecure-Requests': '1',
	}
	response = requests.get(url + '/ditie/linemap.shtml', headers=headers)
	content = response.content.decode('utf-8')
	line_pattern = re.compile(
		r'<strong><a href="(/ditie/.*?.shtml)" target="_blank">([\u4e00-\u9fa5]+\d+[\u4e00-\u9fa5]+).*?</a></strong>')
	line_result = re.findall(line_pattern, content)
	site_pattern = re.compile(r'<a.*?class="link".*?>([\u4e00-\u9fa5]+)</a>')
	sites = {}
	for line in line_result:
		response = requests.get(url + line[0], headers=headers)
		content = response.content.decode('utf-8')
		sites[line[1]] = re.findall(site_pattern, content)

	# print(sites)

	location_search_url = 'http://api.map.baidu.com/geocoder?address={}&output=json&key=37492c0ee6f924cb5e934fa08c6b1676&city=%E5%8C%97%E4%BA%AC%E5%B8%82'
	site_location = {}
	for site in sites:
		for location in sites[site]:
			time.sleep(1)
			r = requests.get(location_search_url.format(location), headers=headers)
			json_dict = r.json()
			if json_dict["status"] == "OK":
				if len(json_dict["result"]) != 0:
					site_location[location] = (
					json_dict["result"]["location"]["lng"], json_dict["result"]["location"]["lat"])
				else:
					site_location[location] = (116.000001, 40.000001)

			# 	print(location)
			# 	break
			#
	return site, site_location


##地铁站经纬度 部分地点手动修正 API没有值（动物园，潞城，首经贸，枣庄，化工，草房等）大部分是接口返回值
##
site_location = {'苹果园': [116.189634, 39.934641], '古城': [100.23248, 26.883162], '八角游乐园': [116.218842, 39.913065],
				 '八宝山': [116.243273, 39.920912], '玉泉路': [116.259636, 39.921884], '五棵松': [116.282178, 39.941871],
				 '万寿路': [116.301316, 39.916633], '公主坟': [116.194292, 39.810747], '军事博物馆': [116.330782, 39.915601],
				 '木樨地': [116.340494, 39.914067], '南礼士路': [116.360047, 39.921459], '复兴门': [116.359854, 39.913661],
				 '西单': [116.379282, 39.916798], '天安门西': [116.397014, 39.913675], '天安门东': [116.40726, 39.914107],
				 '王府井': [116.467388, 39.887659], '东单': [116.424934, 39.914785], '建国门': [116.442268, 39.91453],
				 '永安里': [116.459056, 39.910516], '国贸': [116.467831, 39.9188], '大望路': [116.481599, 39.921828],
				 '四惠': [116.514631, 39.911666], '四惠东': [116.522522, 39.91424], '西直门': [116.359764, 39.94746],
				 '车公庄': [116.360669, 39.94044], '阜成门': [116.361681, 39.929361], '长椿街': [116.370073, 39.902824],
				 '宣武门': [116.381491, 39.902996], '和平门': [116.392749, 39.906933], '前门': [116.407808, 39.907456],
				 '崇文门': [116.428209, 39.907086], '北京站': [116.426105, 39.908479], '朝阳门': [116.440191, 39.929785],
				 '东四十条': [116.432567, 39.939804], '东直门': [116.44965, 39.937162], '雍和宫': [116.423785, 39.953237],
				 '安定门': [116.413076, 39.96707], '鼓楼大街': [116.401304, 39.959605], '积水潭': [116.381024, 39.951854],
				 '安河桥北': [116.276563, 40.019218], '北宫门': [116.281372, 40.009166], '西苑': [116.292194, 40.002159],
				 '圆明园': [116.303374, 40.015009], '北京大学东门': [116.322123, 39.997986], '中关村': [116.344895, 39.98727],
				 '海淀黄庄': [116.323948, 39.982301], '人民大学': [116.327792, 39.973539], '魏公村': [116.328927, 39.96029],
				 '国家图书馆': [116.330736, 39.948999], '动物园': [116.000001, 40.000001], '新街口': [116.376298, 39.951552],
				 '平安里': [116.375904, 39.93743], '西四': [116.375239, 39.931991], '灵境胡同': [116.385402, 39.920665],
				 '菜市口': [116.37963, 39.89629], '陶然亭': [116.38174, 39.884035], '北京南站': [116.384898, 39.871343],
				 '马家堡': [116.384454, 39.848934], '角门西': [116.377657, 39.852308], '公益西桥': [116.376253, 39.837153],
				 '新宫': [116.367656, 39.823778], '西红门': [116.398381, 39.754615], '高米店北': [116.347621, 39.773381],
				 '高米店南': [116.347621, 39.773381], '枣园': [116.340682, 39.758825], '清源路': [116.341653, 39.748349],
				 '黄村西大街': [116.336403, 39.737385], '黄村火车站': [116.338019, 39.726571], '义和庄': [116.394219, 39.768616],
				 '生物医药基地': [116.322221, 39.507914], '天宫院': [116.332579, 39.684622], '宋家庄': [116.434447, 39.849016],
				 '刘家窑': [116.420749, 39.866428], '蒲黄榆': [116.424899, 39.871163], '天坛东门': [116.427279, 39.890061],
				 '磁器口': [116.426226, 39.898671], '灯市口': [116.421831, 39.925202], '东四': [116.429331, 39.934867],
				 '张自忠路': [116.418395, 39.939625], '北新桥': [116.446087, 39.974163], '和平里北街': [116.425575, 39.965527],
				 '和平西桥': [116.426519, 39.975326], '惠新西街南口': [116.424023, 39.983317], '惠新西街北口': [116.423663, 39.993785],
				 '大屯路东': [116.423816, 40.009929], '北苑路北': [116.424466, 40.035832], '立水桥南': [116.41746, 40.050757],
				 '立水桥': [116.418465, 40.053024], '天通苑南': [116.419493, 40.073084], '天通苑': [116.42267, 40.068559],
				 '天通苑北': [116.420729, 40.081603], '海淀五路居': [116.291067, 39.940997], '慈寿寺': [116.299481, 39.934958],
				 '花园桥': [116.316542, 39.938302], '白石桥南': [116.332443, 39.95194], '车公庄西': [116.332944, 39.936058],
				 '北海北': [109.126533, 21.486836], '南锣鼓巷': [116.409524, 39.942648], '东大桥': [116.45853, 39.929006],
				 '呼家楼': [116.470752, 39.925326], '金台路': [116.484674, 39.92498], '十里堡': [116.509557, 39.921067],
				 '青年路': [116.522719, 39.960801], '褡裢坡': [116.569397, 39.928846], '黄渠': [116.575224, 39.930072],
				 '常营': [116.58837, 39.933995], '草房': [116.622546, 39.930673], '物资学院路': [116.645993, 39.928854],
				 '通州北关': [116.660726, 39.925898], '北运河西': [116.754103, 39.873586], '郝家府': [116.725215, 39.907673],
				 '东夏园': [116.749089, 39.903107], '潞城': [116.754799, 39.90889], '北京西站': [116.327694, 39.903473],
				 '湾子': [116.333131, 39.895712], '达官营': [116.347996, 39.895496], '广安门内': [116.376708, 39.899212],
				 '虎坊桥': [116.393653, 39.894439], '珠市口': [116.406109, 39.897542], '桥湾': [116.415142, 39.899084],
				 '广渠门内': [116.435477, 39.899209], '广渠门外': [116.49167, 39.898773], '双井': [116.45556, 39.904957],
				 '九龙山': [116.054634, 39.958654], '大郊亭': [116.497375, 39.894153], '百子湾': [116.480353, 39.906907],
				 '化工': [116.510091, 39.893222], '南楼梓庄': [116.497188, 39.881395], '欢乐谷景区': [116.496648, 39.872999],
				 '垡头': [116.522126, 39.864712], '双合': [116.533265, 39.866414], '焦化厂': [116.538157, 39.862384],
				 '朱辛庄': [116.308545, 40.098752], '育知路': [116.335088, 40.084853], '平西府': [116.37599, 40.105565],
				 '回龙观东大街': [116.367616, 40.086892], '霍营': [116.379708, 40.085384], '育新': [116.353997, 40.066124],
				 '西小口': [116.355423, 40.054046], '永泰庄': [116.226477, 40.124017], '林萃桥': [116.382609, 40.02879],
				 '森林公园南门': [116.204771, 39.973174], '奥林匹克公园': [116.399127, 40.00121], '奥体中心': [116.400195, 39.992095],
				 '北土城': [116.400623, 39.983231], '安华桥': [116.401461, 39.974291], '什刹海': [116.380751, 39.952105],
				 '郭公庄': [116.310779, 39.814246], '丰台科技园': [116.285784, 39.837047], '科怡路': [116.30387, 39.839081],
				 '丰台南路': [116.307588, 39.847916], '丰台东大街': [116.300838, 39.870082], '七里庄': [116.30401, 39.868291],
				 '六里桥': [116.318063, 39.890607], '六里桥东': [116.318063, 39.890607], '白堆子': [116.33017, 39.932407],
				 '巴沟': [116.30052, 39.975021], '苏州街': [116.31233, 39.985611], '知春里': [116.326487, 39.980245],
				 '知春路': [116.34177, 39.982208], '西土城': [116.362628, 39.964743], '牡丹园': [116.484888, 39.877726],
				 '健德门': [116.386753, 39.982494], '安贞门': [116.413183, 39.983313], '芍药居': [116.441573, 39.988028],
				 '太阳宫': [116.446059, 39.978245], '三元桥': [116.460972, 39.963256], '亮马桥': [116.481957, 39.963252],
				 '农业展览馆': [116.470462, 39.947098], '团结湖': [116.476639, 39.935523], '金台夕照': [116.466402, 39.921094],
				 '劲松': [116.457353, 39.888495], '潘家园': [116.4568, 39.883743], '十里河': [116.450961, 39.875618],
				 '分钟寺': [116.459899, 39.863038], '成寿寺': [116.443454, 39.858582], '石榴庄': [116.433628, 39.847381],
				 '大红门': [116.423417, 39.807916], '角门东': [116.396398, 39.854743], '草桥': [116.309674, 39.99305],
				 '纪家庙': [116.353416, 39.827359], '首经贸': [116.326613, 39.85032], '丰台站': [116.295648, 39.854462],
				 '泥洼': [116.000001, 40.000001], '西局': [116.312747, 39.877025], '莲花桥': [116.316222, 39.902347],
				 '西钓鱼台': [116.306415, 39.925659], '车道沟': [116.306391, 39.952454], '长春桥': [116.300448, 39.963198],
				 '火器营': [116.293443, 39.971527], '大钟寺': [116.326642, 39.96292], '五道口': [116.346355, 39.991042],
				 '上地': [116.321306, 40.041169], '西二旗': [116.315053, 40.06149], '龙泽': [116.330635, 40.07754],
				 '回龙观': [116.338644, 40.08243], '北苑': [116.427719, 40.03445], '望京西': [116.453997, 40.000755],
				 '光熙门': [116.438824, 39.974318], '柳芳': [116.44511, 39.961223], '永定门外': [116.409196, 39.872934],
				 '景泰': [104.069444, 37.187406], '方庄': [116.438453, 39.865144], '北工大西门': [116.420498, 39.908814],
				 '枣营': [116.48155, 39.950188], '东风北桥': [116.494341, 39.96362], '将台': [116.536017, 39.986811],
				 '望京南': [116.489347, 40.00241], '阜通': [116.477642, 39.997887], '望京': [116.489347, 40.00241],
				 '东湖渠': [116.468512, 40.011477], '来广营': [116.479153, 40.001566], '善各庄': [116.490034, 40.032611],
				 '张郭庄': [116.202973, 39.854011], '园博园': [116.196619, 39.882144], '大瓦窑': [116.235286, 39.862412],
				 '郭庄子': [116.267079, 39.873678], '大井': [116.280742, 39.877991], '俸伯': [116.724595, 40.142113],
				 '顺义': [116.661424, 40.136351], '石门': [111.386451, 29.590366], '南法信': [116.607481, 40.126955],
				 '后沙峪': [116.551449, 40.111767], '花梨坎': [116.553741, 40.084359], '国展': [116.449021, 39.96729],
				 '孙河': [116.546719, 40.057928], '马泉营': [116.515813, 40.043889], '崔各庄': [116.468636, 40.055808],
				 '关庄': [116.440955, 40.008748], '安立路': [116.414411, 40.025849], '北沙滩': [116.380989, 40.010688],
				 '六道口': [116.476852, 39.854528], '清华东路西口': [116.344839, 40.006275]}

##接口返回值
site = {
	'北京地铁1号线': ['苹果园', '古城', '八角游乐园', '八宝山', '玉泉路', '五棵松', '万寿路', '公主坟', '军事博物馆', '木樨地', '南礼士路', '复兴门', '西单', '天安门西',
				'天安门东', '王府井', '东单', '建国门', '永安里', '国贸', '大望路', '四惠', '四惠东'],
	'北京地铁2号线': ['西直门', '车公庄', '阜成门', '复兴门', '长椿街', '宣武门', '和平门', '前门', '崇文门', '北京站', '建国门', '朝阳门', '东四十条', '东直门', '雍和宫',
				'安定门', '鼓楼大街', '积水潭'],
	'北京地铁4号线': ['安河桥北', '北宫门', '西苑', '圆明园', '北京大学东门', '中关村', '海淀黄庄', '人民大学', '魏公村', '国家图书馆', '动物园', '西直门', '新街口', '平安里',
				'西四', '灵境胡同', '西单', '宣武门', '菜市口', '陶然亭', '北京南站', '马家堡', '角门西', '公益西桥', '新宫', '西红门', '高米店北', '高米店南',
				'枣园', '清源路', '黄村西大街', '黄村火车站', '义和庄', '生物医药基地', '天宫院'],
	'北京地铁5号线': ['宋家庄', '刘家窑', '蒲黄榆', '天坛东门', '磁器口', '崇文门', '东单', '灯市口', '东四', '张自忠路', '北新桥', '雍和宫', '和平里北街', '和平西桥',
				'惠新西街南口', '惠新西街北口', '大屯路东', '北苑路北', '立水桥南', '立水桥', '天通苑南', '天通苑', '天通苑北'],
	'北京地铁6号线线路图': ['海淀五路居', '慈寿寺', '花园桥', '白石桥南', '车公庄西', '车公庄', '平安里', '北海北', '南锣鼓巷', '东四', '朝阳门', '东大桥', '呼家楼', '金台路',
				   '十里堡', '青年路', '褡裢坡', '黄渠', '常营', '草房', '物资学院路', '通州北关', '北运河西', '郝家府', '东夏园', '潞城'],
	'北京地铁7号线线路图': ['北京西站', '湾子', '达官营', '广安门内', '菜市口', '虎坊桥', '珠市口', '桥湾', '磁器口', '广渠门内', '广渠门外', '双井', '九龙山', '大郊亭',
				   '百子湾', '化工', '南楼梓庄', '欢乐谷景区', '垡头', '双合', '焦化厂'],
	'北京地铁8号线': ['朱辛庄', '育知路', '平西府', '回龙观东大街', '霍营', '育新', '西小口', '永泰庄', '林萃桥', '森林公园南门', '奥林匹克公园', '奥体中心', '北土城',
				'安华桥', '鼓楼大街', '什刹海', '南锣鼓巷'],
	'北京地铁9号线': ['郭公庄', '丰台科技园', '科怡路', '丰台南路', '丰台东大街', '七里庄', '六里桥', '六里桥东', '北京西站', '军事博物馆', '白堆子', '白石桥南', '国家图书馆'],
	'北京地铁10号线线路图': ['巴沟', '苏州街', '海淀黄庄', '知春里', '知春路', '西土城', '牡丹园', '健德门', '北土城', '安贞门', '惠新西街南口', '芍药居', '太阳宫', '三元桥',
					'亮马桥', '农业展览馆', '团结湖', '呼家楼', '金台夕照', '国贸', '双井', '劲松', '潘家园', '十里河', '分钟寺', '成寿寺', '宋家庄', '石榴庄',
					'大红门', '角门东', '角门西', '草桥', '纪家庙', '首经贸', '丰台站', '泥洼', '西局', '六里桥', '莲花桥', '公主坟', '西钓鱼台', '慈寿寺',
					'车道沟', '长春桥', '火器营'],
	'北京地铁13号线': ['西直门', '大钟寺', '知春路', '五道口', '上地', '西二旗', '龙泽', '回龙观', '霍营', '立水桥', '北苑', '望京西', '芍药居', '光熙门', '柳芳',
				 '东直门'],
	'北京地铁14号线东段线路图': ['北京南站', '永定门外', '景泰', '蒲黄榆', '方庄', '十里河', '北工大西门', '九龙山', '大望路', '金台路', '枣营', '东风北桥', '将台', '望京南',
					  '阜通', '望京', '东湖渠', '来广营', '善各庄'],
	'北京地铁14号线西段线路图': ['张郭庄', '园博园', '大瓦窑', '郭庄子', '大井', '七里庄', '西局'],
	'北京地铁15号线线路图': ['俸伯', '顺义', '石门', '南法信', '后沙峪', '花梨坎', '国展', '孙河', '马泉营', '崔各庄', '望京', '望京西', '关庄', '安立路', '奥林匹克公园',
					'北沙滩', '六道口', '清华东路西口']}


def geo_distance(origin, destination):
	lng1, lat1 = origin
	lng2, lat2 = destination
	redius = 6371  # km
	dlat = math.radians(lat2 - lat1)
	dlng = math.radians(lng2 - lng1)
	a = (math.sin(dlat / 2) ** 2 + math.cos(math.radians(lat2)*math.radians(lat1)) * math.sin(dlng / 2) ** 2)
	c = 2 * math.asin(math.sqrt(a))*redius*1000
	c=round(c/1000,3)
	# d = redius * c
	return c


def get_geo_distance(site1, site2,site_location):
	print(tuple(site_location[site1]), tuple(site_location[site2]))
	return geo_distance(tuple(site_location[site1]), tuple(site_location[site2]))


# import networkx as nx
#
# subway_graph = nx.Graph()
# subway_graph.add_nodes_from(site_location.keys())
# import matplotlib
# print(matplotlib.__path__)
import matplotlib.pyplot as plt
from matplotlib.font_manager import FontProperties

# myfont = FontProperties(fname='/Users/yaphets/simhei.ttf')
# plt.rcParams['font.sans-serif'] = 'SimHei'
# plt.rcParams['font.family'] = 'sans-serif'
# plt.rcParams['axes.unicode_minus'] = False
# plt.rcParams['figure.figsize'] = [10.0, 6.0]
# nx.draw(subway_graph, site_location, with_labels=True, node_size=3)
# plt.show()
# print(site_location)

import collections

##转换线路站点site信息 使成为 site_connection[站点:[相邻的站点...]...]的结构
def values_sort(site):
	site_connection = collections.defaultdict(list)
	for values in site.values():
		for x in range(len(values) - 1):
			if x == 0:
				if values[x + 1] not in site_connection[values[x]]:
					site_connection[values[x]].append(values[x + 1])
			if x > 0:
				if values[x + 1] not in site_connection[values[x]]:
					site_connection[values[x]].append(values[x + 1])
				if values[x - 1] not in site_connection[values[x]]:
					site_connection[values[x]].append(values[x - 1])
	return site_connection

def bfs(graph, start, end):
	visited = [start]
	seen = []
	while visited:
		front = visited.pop()
		if front in seen: continue
		for behinder in graph[front]:
			if behinder in seen: continue
			if behinder == end:
				break
			else:
				# visited.append(behinder)

				visited = visited + [behinder]
		seen.append(front)
	seen.append(end)
	return seen


def search(start, dest, connection_graph):
	path_right_dataset = []
	paths = [[start]]
	visited = set()
	while paths:
		path = paths.pop(0)
		froninter = path[-1]
		if froninter in visited:
			continue
		successor = connection_graph[froninter]
		for new_subway_station in successor:
			if new_subway_station in path:
				continue
			new_path = path + [new_subway_station]

			if new_subway_station == dest:
				path_right_dataset.append(new_path)
			else:
				paths.append(new_path)
		visited.add(froninter)

	return path_right_dataset


def main():
	#site,site_location=spider()
	site_connection=values_sort(site)
	print(bfs(site_connection, '回龙观东大街', '人民大学'))
	ways = search('回龙观东大街', '北土城', site_connection)
	print(ways)
	least_transfer_way = []
	distance_list = []
	for way in ways:
		distance = 0
		for i in range(len(way) - 2):
			distance += get_geo_distance(way[i], way[i + 1],site_location)
		distance_list.append(distance)

		if len(way) < len(least_transfer_way):
			least_transfer_way = way
		else:
			if len(least_transfer_way) == 0:
				least_transfer_way = way
			continue

	shortest_way_order_num = 0
	tmp_number = 0
	for i in range(len(distance_list) - 1):
		if distance_list[i] < tmp_number:
			tmp_number = distance_list
			shortest_way_order_num = i
		else:
			if tmp_number == 0:
				tmp_number = distance_list[i]
				shortest_way_order_num = i
			continue
	print("最少换乘选择 L:{}".format(least_transfer_way))
	print("最短距离选择 S:{}".format(ways[shortest_way_order_num]))


if __name__ == '__main__':
	main()
