#!/usr/bin/python
# -*- coding: koi8-r -*-
# This file is part of the metromap
#
# Copyright(c) 2010, Sergey Pinaev
# http://metromap.antex.ru/
#
# This file may be licensed under the terms of of the
# GNU General Public License Version 2 (the ``GPL'').
#
# Software distributed under the License is distributed
# on an ``AS IS'' basis, WITHOUT WARRANTY OF ANY KIND, either
# express or implied. See the GPL for the specific language
# governing rights and limitations.
#
# You should have received a copy of the GPL along with this
# program. If not, go to http://www.gnu.org/licenses/gpl.html
# or write to the Free Software Foundation, Inc.,
# 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.

import copy

class FindPath:
        def __init__(self, graph, delta):
                self.set_graph(graph)
                self.maxerror = delta  #number of minutes on which path can be longer
                                       #than shortest already found path

        def set_graph(self, graph):
                self.graph = graph
                self.helper = dict()
                for f in xrange(len(self.graph)):
                        for t in self.graph[f]:
                                if t[1] != 0:
                                        self.helper[(f, t[0])] = 1
                                        self.helper[(t[0], f)] = 1

        def __mj_rec__(self, num, target, path, jumps, pathjumps):
                path.append(num)
                if num == target:
                        self.PathList.append(copy.copy(path))
                        return -1
                for i in xrange(len(self.graph[num])):
                        if self.graph[num][i][0] not in path:
                                if self.graph[num][i][2] != self.graph[num][i][3]:
                                        if pathjumps + 1 > jumps:
                                                continue
                                        pathjumps += 1
                                ret = self.__mj_rec__(self.graph[num][i][0], target, path, jumps, pathjumps)
                                if self.graph[num][i][2] != self.graph[num][i][3]:
                                        pathjumps -= 1
                                path.pop()
                                if ret == -1:
                                        return 0
                return 0

        def minjumps(self, sfrom, sto, limit):
                self.PathList = list()
                jumps = 0
                while not len(self.PathList) and jumps < limit:
                        path = list()
                        self.__mj_rec__(sfrom, sto, path, jumps, 0)
                        jumps += 1
                return copy.copy(self.PathList)

        def waves_accurate(self, sfrom, sto, waitlenfunc):
                BIGNUM = 9999999
                maxerror = self.maxerror
                self.PathList = list()
                pl = list()        #array of pathes
                pll = list()       #array of "length" of pathes
                plj = list()       #array of jump/not jump flags
                minlens = [0] * len(self.graph)

                pl.append(list())
                pll.append(list())
                plj.append([0, 0])
                pl[0].append(sfrom)
                pll[0].append(waitlenfunc(sfrom))
                minlen = BIGNUM

                while len(pl):
                        nl = list()      #same as pl/pll/plj/pldict. for next iteration.
                        nll = list()
                        nlj = list()

                        #print len(pl)
                        for i in xrange(len(pl)):
                                if len(pl[i]):
                                        for s in self.graph[pl[i][-1]]:
                                                if s[1] == 0: #station is "under construction"?
                                                        continue
                                                curtime = pll[i][-1] + s[1]
                                                if s[0] == sto:
                                                        #path found, store it
                                                        jmp = 0
                                                        if s[2] != s[3]:
                                                                jmp = 1
                                                                if len(pl[i]) == 1 or plj[i][0]:
                                                                        curtime -= waitlenfunc(pl[i][-1])
                                                        minlen = min(minlen, curtime)
                                                        self.PathList.append([curtime, plj[i][1] + jmp] + pl[i] + [sto])
                                                elif not s[0] in pl[i] and (minlen == BIGNUM or curtime < minlen + maxerror):
                                                        app = 0
                                                        jmp = 0
                                                        if s[2] != s[3]:
                                                                #dont do useles jumps
                                                                if len(pl[i]) > 1 and self.helper.has_key((s[0], pl[i][-2])):
                                                                                continue
                                                                if len(pl[i]) == 1 or plj[i][0]:
                                                                        curtime -= waitlenfunc(pl[i][-1])
                                                                app = waitlenfunc(s[0])
                                                                jmp = 1
                                                        if minlens[s[0]] == 0 or minlens[s[0]] + maxerror > curtime:
                                                                curtime = curtime + app
                                                                nl.append(pl[i] + [s[0]])
                                                                nll.append(pll[i] + [curtime])
                                                                nlj.append([jmp, plj[i][1] + jmp])
                                                                if minlens[s[0]] == 0 or minlens[s[0]] > curtime:
                                                                        minlens[s[0]] = curtime

                        pl = nl
                        pll = nll
                        plj = nlj

                return copy.copy(self.PathList)

        def waves(self, sfrom, sto, waitlenfunc):
                self.PathList = list()
                pl = list()
                pl.append(list())
                pl[0].append(waitlenfunc(sfrom))
                pl[0].append(sfrom)
                minlen = -1

                while len(pl):
                        nl = list()
                        for l in pl:
                                for s in self.graph[l[-1]]:
                                        if s[0] == sto:
                                                fp = l[1:] + [sto]
                                                self.PathList.append(fp)
                                                fpl = l[0] + s[1]
                                                if minlen == -1 or fpl < minlen:
                                                        minlen = fpl
                                        #there is one error - station should be
                                        #dropped only if previous found path is shorter
                                        #then current path _in seconds_, not in "hops".
                                        #thats done in waves_accurate, which is slower than
                                        #this function
                                        elif minlen == -1 or l[0] < minlen:
                                                if not filter(lambda a: a, map(lambda a: s[0] in a[1:], pl)):
                                                        app = 0
                                                        if s[2] != s[3]:
                                                                app = waitlenfunc(s[0])
                                                        nl.append([l[0] + s[1] + app] + l[1:] + [s[0]])
                        pl = nl

                return copy.copy(self.PathList)

class PathFinder:
        def __init__(self, metromap, delta):
                self.metromap = metromap
                self.maxdelta = delta  #number of minutes on which path can be longer
                                       #than shortest already found path

        def find(self, st_from, st_to):
                path_list = list()

                pl = list()
                plw = list()
                pl.append([st_from])
                plw.append(self.metromap.get_wait(st_from))
                shortest = None
                drv_type = self.metromap.get_line_type(self.metromap.get_station_line(st_from))

                while len(pl):
                        nl = list()
                        nlw = list()
                        for i in xrange(len(pl)):
                                neigh = self.metromap.get_neighbours(pl[i][-1])
                                last_st_line = self.metromap.get_station_line(pl[i][-1])
                                if len(pl[i]) > 1 and last_st_line == self.metromap.get_station_line(pl[i][-2]):
                                        if pl[i][-1] == pl[i][-2]:
                                                if len(pl[i]) > 2:
                                                        if pl[i][-1] > pl[i][-3]:
                                                                neighbours = neigh[1]
                                                        else:
                                                                neighbours = neigh[0]
                                                else:
                                                        #useless direction change on first step
                                                        continue
                                        else:
                                                if pl[i][-1] > pl[i][-2]:
                                                        neighbours = neigh[0]
                                                else:
                                                        neighbours = neigh[1]
                                                #append path with changing driving direction
                                                nl.append(pl[i] + [pl[i][-1]])
                                                nlw.append(plw[i] + self.metromap.get_wait(pl[i][-1]))
                                else:
                                        neighbours = neigh[0]
                                        neighbours.update(neigh[1])
                                for n in neighbours.keys():
                                        if neighbours[n]['cost'] and drv_type == self.metromap.get_line_type(self.metromap.get_station_line(n)):
                                                if not n in pl[i]:
                                                        if last_st_line != self.metromap.get_station_line(n):
                                                                if len(pl[i]) > 1 and last_st_line != self.metromap.get_station_line(pl[i][-2]):
                                                                        ljump_neigh = self.metromap.get_neighbours(pl[i][-2])
                                                                        if ljump_neigh[0].has_key(n) or ljump_neigh[1].has_key(n):
                                                                                #path with useles transfer
                                                                                continue
                                                                if len(pl[i]) > 1 and pl[i][-1] == pl[i][-2]:
                                                                        #path with useles direction change
                                                                        continue
                                                                if len(pl[i]) == 1:
                                                                        plw[i] = 0
                                                                path_cost = plw[i] + neighbours[n]['cost'] + self.metromap.get_wait(n)
                                                        else:
                                                                if len(pl[i]) > 2 and pl[i][-1] == pl[i][-2] and \
                                                                   self.metromap.get_station_line(pl[i][-3]) == self.metromap.get_station_line(n) and \
                                                                   n < pl[i][-3]:
                                                                        #path with useles train change
                                                                        continue
                                                                path_cost = plw[i] + neighbours[n]['cost']
                                                        if shortest == None or path_cost <= shortest + self.maxdelta:
                                                                if n == st_to:
                                                                        path_list.append(pl[i] + [n])
                                                                        if shortest == None or path_cost < shortest:
                                                                                shortest = path_cost
                                                                else:
                                                                        nl.append(pl[i] + [n])
                                                                        nlw.append(path_cost)
                        pl = nl
                        plw = nlw
                return path_list
