Bimba/app/src/main/java/ml/adamsprogs/bimba/RouteFinder.kt

package ml.adamsprogs.bimba

import android.content.Context
import android.database.sqlite.SQLiteDatabase
import android.database.sqlite.SQLiteException
import ml.adamsprogs.bimba.models.Timetable
import ml.adamsprogs.bimba.models.gtfs.Calendar
import java.io.File
import java.util.*
import java.util.Calendar as JCalendar


class RouteFinder {
    companion object {
        private lateinit var timetable: Timetable
        private const val tramSpeed = 20 //heuristic value, needs experiments
        private const val walkSpeed = 5
        private const val bikeSpeed = 10
        private var db: SQLiteDatabase? = null
        private lateinit var stops: HashMap<String, SimpleStop>
        private const val numberOfpeople = 2
        private const val wantBikes = true
        private const val computingTime = 2000 //in miliseconds
        private const val changes = false

        private const val bikes = " 16.83362,52.3832,Junikowo\n" +
                " 16.80386,52.39727,Malwowa/Złotowska\n" +
                " 16.9116229,52.4028313,Poznań Główny\n" +
                " 16.9128835,52.4105153,Most Teatralny\n" +
                " 16.9252069,52.4083807,Pl. Wolności\n" +
                " 16.9378683,52.4104498,Małe Garbary\n" +
                " 16.9553804,52.4092652,Rondo Śródka\n" +
                " 16.9501609,52.3963767,Rondo Rataje\n" +
                " 16.9282258,52.4008945,Półwiejska\n" +
                " 16.9523442,52.4122659,Brama Poznania\n" +
                " 16.8822312,52.4169808,Ogrody\n" +
                " 16.8893659,52.4093307,Bukowska / Przybyszewskiego\n" +
                " 16.9038713,52.4124426,Rynek Jeżycki\n" +
                " 16.9215095,52.3934764,Rynek Wildecki\n" +
                " 16.920619,52.4273709,Słowiańska\n" +
                " 16.9475449,52.4557701,Boranta\n" +
                " 16.9178295,52.4637887,Os. Sobieskiego\n" +
                " 16.902616,52.3979413,Park Wilsona\n" +
                " 16.9499141,52.4028182,Politechnika Centrum Wykładowe\n" +
                " 16.9087744,52.4210966,Park Sołacki\n" +
                " 16.8953902,52.3898524,Głogowska / Hetmańska\n" +
                " 16.975615,52.4056982,Termy Maltańskie\n" +
                " 16.9029925,52.3721516,Dębiec\n" +
                " 16.8765342,52.399447,Grunwaldzka / Grochowska\n" +
                " 16.8814105,52.3815165,Górczyn\n" +
                " 16.9350171,52.3986614,AWF\n" +
                " 16.9435573,52.3807863,Rondo Starołęka\n" +
                " 16.9374096,52.4338602,Rondo Solidarności\n" +
                " 16.9414008,52.4676583,UAM Pływalnia\n" +
                " 16.9433852,52.4481549,Os. Łokietka\n" +
                " 16.925388,52.4656288,UAM Wydział Nauk Politycznych i Dziennikarstwa\n" +
                " 16.9197235,52.4511427,Kurpińskiego\n" +
                " 16.9472694,52.4275148,Wilczak\n" +
                " 16.9389224,52.4164704,Garbary\n" +
                " 16.9353014,52.4043466,Zielona\n" +
                " 16.9785547,52.3999085,Malta SKI\n" +
                " 16.9194925,52.4075145,Zamek\n" +
                " 16.9773316,52.389895,Os. Lecha\n" +
                " 16.9141012,52.3849938,Traugutta\n" +
                " 16.8343441,52.4112577,Brzechwy / Maklakiewicza\n" +
                " 16.86208,52.396,Bułgarska\n" +
                " 16.9393784,52.4077534,Ewangelicka\n" +
                " 16.90663,52.41705,Kościelna\n" +
                " 16.93543,52.40704,Kozia\n" +
                " 16.92216,52.41111,Libelta\n" +
                " 16.87527,52.40442,Marcelińska / Grochowska\n" +
                " 16.932646,52.409455,Masztalarska\n" +
                " 16.89995,52.40338,Matejki\n" +
                " 16.97857,52.41499,Nieszawska\n" +
                " 16.9248,52.40953,Pl. Cyryla Ratajskiego\n" +
                " 16.91564,52.38905,Prądzyńskiego / Kosińskiego\n" +
                " 16.9115746,52.4081592,Rondo Kaponiera\n" +
                " 16.90098,52.3944,Rynek Łazarski\n" +
                " 16.85124,52.40647,Strzegomska / Gałczyńskiego\n" +
                " 16.89953,52.41087,Szamarzewskiego / Wawrzyniaka\n" +
                " 16.87696,52.41107,Szpitalna\n" +
                " 16.9259351,52.4149588,Św. Barbary\n" +
                " 16.92028,52.40571,Taczaka\n" +
                " 16.916939,52.4060222,Towarowa\n" +
                " 16.90508,52.42647,Uniwersytet Przyrodniczy\n" +
                " 16.9209,52.4015,Wierzbięcice\n" +
                " 16.939228,52.405068,Mostowa\n" +
                " 16.92962,52.41025,Aleje Marcinkowskiego\n" +
                " 16.9205,52.43632,Aleje Solidarności\n" +
                " 16.87798,52.40683,Brzask / Międzychodzka\n" +
                " 16.92442,52.42544,Dożynkowa\n" +
                " 16.91491,52.40203,Dworzec Autobusowy\n" +
                " 16.9097,52.40114,Dworzec Zachodni\n" +
                " 16.88617,52.38759,Jarochowskiego / Palacza\n" +
                " 16.89209,52.39329,Jarochowskiego / Potworowskiego\n" +
                " 16.93598,52.43017,Murawa / Słowiańska\n" +
                " 16.90415,52.36353,Os. Dębina\n" +
                " 16.9572687,52.3905825,Os. Oświecenia\n" +
                " 16.92602,52.42855,Os. Przyjaźni\n" +
                " 16.9404781,52.4385695,Os. Wichrowe Wzgórze\n" +
                " 16.9317176,52.4048833,Plac Wiosny Ludów\n" +
                " 16.91207,52.41376,Poznańska / Jeżycka\n" +
                " 16.88974,52.40309,Rondo Jana Nowaka Jeziorańskiego\n" +
                " 16.891401,52.412057,Szamarzewskiego / Długosza\n" +
                " 16.86674,52.40465,Bułgarska / Marcelińska\n" +
                " 16.89584,52.39876,Wyspiańskiego / Ułańska\n" +
                " 16.89119,52.38711,Głogowska / ul. Krauthofera\n" +
                " 16.93096,52.4388,Połabska\n" +
                " 16.97072,52.42123,ul. Główna rejon Rynek Wschodni\n" +
                " 16.96008,52.41643,Koronkarska\n" +
                " 16.82359,52.40972,Złotowska\n" +
                " 16.92183,52.40354,Kościuszki\n" +
                " 16.90436,52.456372,os. Jagiełły\n" +
                " 16.915363,52.430559,Nasienna\n" +
                " 16.94411,52.39038,os. Piastowskie\n" +
                " 16.95765,52.38087,os. Stare Żegrze\n" +
                " 16.98327,52.38755,Piaśnicka Rynek\n" +
                " 16.97061,52.38231,os. Orła Białego\n" +
                " 16.98146,52.39383,os. Rusa/Chartowo\n" +
                " 16.96276,52.38567,Inflancka\n" +
                " 16.86391,52.39078,Keplera\n" +
                " 16.95297,52.39908,Kórnicka\n" +
                " 16.96224,52.3989,Polanka\n" +
                " 16.88343,52.36436,Buczka/Kołłątaja\n" +
                " 16.91482,52.42408,Maczka\n" +
                " 16.90034,52.3917,Dmowskiego/Stablewskiego\n" +
                " 16.9069,52.40652,Targi\n" +
                " 16.928468,52.40695,Marcinkowskiego/Podgórna\n" +
                " 16.92564,52.39787,Spadzista\n" +
                " 16.931681,52.407956,Sieroca\n" +
                " 16.946632,52.445027,Karpia\n" +
                " 16.94206,52.45386,Jasna Rola"

        private class SimpleStop {
            var latitude: Float = .0F
            var longitude: Float = .0F
            var name: String = ""
            var bike: Boolean = false
            var trips: Boolean = true
            var bikes: Int = 0
        }

        private class Proposition(stop: String, t1: Long, t2: Long, hist: String) {
            var name: String = stop
            var time: Long = t1
            var finish: Long = time + t2
            var history: String = hist
        }

        private fun time(distance: Float, speed: Int): Long {
            return (distance * 3600 / speed).toLong()
        }

        private fun findKClosest(stops: HashMap<String, SimpleStop>, stop: SimpleStop?, k: Int): Array<Pair<Long, SimpleStop>> {
            val res: Array<Pair<Long, SimpleStop>> = Array(k + 1) { Pair(Long.MAX_VALUE, SimpleStop()) }
            for (s in stops.values) {
                res[k] = Pair(time(distance(stop, s), walkSpeed), s)
                var i: Int = k - 1
                while (i >= 0) {
                    if (res[i + 1].first < res[i].first) {
                        val tmp = res[i]
                        res[i] = res[i + 1]
                        res[i + 1] = tmp
                    } else {
                        break
                    }
                    i--
                }
            }
            return res
        }

        private fun findForBike(stop: SimpleStop?, stops: HashMap<String, SimpleStop>): ArrayList<Pair<Long, SimpleStop>> {
            val result: ArrayList<Pair<Long, SimpleStop>> = ArrayList(20)
            for (s in stops.values) {
                if (!s.bike) continue
                var t = time(distance(stop, s), bikeSpeed)
                if (t > 15 * 60 * 1000) continue
                if (s.trips) t += 30 * 1000
                result.add(Pair(t + 60 * 1000, s))
            }
            return result
        }

        private fun eucildeanDistance(lat1: Float?, lng1: Float?, lat2: Float?, lng2: Float?): Float {
            val earthRadius = 6371000.0 //meters
            val dLat = Math.toRadians((lat2!! - lat1!!).toDouble())
            val dLng = Math.toRadians((lng2!! - lng1!!).toDouble())
            val a = Math.sin(dLat / 2) * Math.sin(dLat / 2) + Math.cos(Math.toRadians(lat1.toDouble())) * Math.cos(Math.toRadians(lat2.toDouble())) *
                    Math.sin(dLng / 2) * Math.sin(dLng / 2)
            val c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a))

            return (earthRadius * c).toFloat()
        }

        private fun manhattanDistance(lat1: Float?, lng1: Float?, lat2: Float?, lng2: Float?): Float {
            return eucildeanDistance(lat1, lng1, lat2, lng1) + eucildeanDistance(lat2, lng2, lat2, lng1)
        }

        private fun distance(s0: SimpleStop?, s1: SimpleStop?): Float {
            return manhattanDistance(s0!!.latitude, s0.longitude, s1!!.latitude, s1.longitude)
        }

        private fun distanceToEnd(lat: Float?, lng: Float?, ends: HashSet<String>): Float {
            var min = Float.MAX_VALUE
            for (stop in ends) {
                val dist = manhattanDistance(lat, lng, stops[stop]!!.latitude, stops[stop]!!.longitude)
                if (dist < min) min = dist
            }
            return min
        }

        private fun getStops(context: Context): HashMap<String, SimpleStop> {
            val filesDir = context.getSecondaryExternalFilesDir()
            val dbFile = File(filesDir, "timetable.db")
            db = try {
                SQLiteDatabase.openDatabase(dbFile.path, null, SQLiteDatabase.OPEN_READONLY)
            } catch (e: SQLiteException) {
                null
            }
            val cursor = db!!.rawQuery("select stop_lat, stop_lon, stop_name from stops", emptyArray())
            val result: HashMap<String, SimpleStop> = HashMap(cursor.count / 3)
            while (cursor.moveToNext()) {
                val stop = SimpleStop()
                stop.latitude = cursor.getFloat(0)
                stop.longitude = cursor.getFloat(1)
                stop.name = cursor.getString(2)
                result[stop.name] = stop
            }
            cursor.close()
            if (wantBikes) {
                for (line in bikes.split("\n")) {
                    val bikeStop = line.split(",")
                    if (bikeStop[2] in result.keys) {
                        result[bikeStop[2]]!!.bike = true
                        result[bikeStop[2]]!!.bikes = 5
                    } else {
                        val stop = SimpleStop()
                        stop.latitude = bikeStop[1].toFloat()
                        stop.longitude = bikeStop[0].toFloat()
                        stop.bike = true
                        stop.bikes = 5
                        stop.trips = false
                        stop.name = bikeStop[2]
                        result[stop.name] = stop
                    }
                }
            }
            return result
        }

        private fun pickBest(propositions: HashMap<String, Proposition>): Proposition {
            var best = Proposition("", Long.MAX_VALUE, 0, "")
            for (p in propositions.values) {
                if (p.finish < best.finish) {
                    best = p
                }
            }
            return best
        }

        private fun addToPropositions(propositions: HashMap<String, Proposition>, visited: HashMap<String, Proposition>, prop: Proposition) {
            if (prop.name in visited.keys) {
                if (prop.finish >= visited[prop.name]!!.finish) {
                    return
                }
            }

            propositions[prop.name] = prop
            visited[prop.name] = prop
        }


        fun findRoute(start: HashSet<String>, end: HashSet<String>, time: JCalendar, context: Context): String {
            val startTime: Long = System.currentTimeMillis()
            stops = getStops(context)
            val visited: HashMap<String, Proposition> = HashMap(500)
            timetable = Timetable.getTimetable(context)
            val propositions: HashMap<String, Proposition> = HashMap(300)
            for (stop in start) {
                val startStop = stops[stop]
                propositions[stop] = Proposition(stop, time.timeInMillis,
                        time(distanceToEnd(startStop!!.latitude, startStop.longitude, end), tramSpeed), "")
            }
            var best = Proposition("", Long.MAX_VALUE, 0, "")
            var done = false
            while (true) {
                val pop = pickBest(propositions)
                propositions.remove(pop.name)
                if (pop.name in end && pop.time < best.time) {
                    best = pop
                    done = true
                }
                if (done && System.currentTimeMillis() - startTime > computingTime || pop.name == "") {
                    val x = java.util.Calendar.getInstance()
                    x.timeInMillis = best.time
                    System.out.println(x.get(java.util.Calendar.HOUR_OF_DAY).toString() + " " + x.get(java.util.Calendar.MINUTE).toString())
                    return best.history
                }
                if (stops[pop.name]!!.trips) {
                    val x = java.util.Calendar.getInstance()
                    x.timeInMillis = pop.time
                    val options = timetable.getTripFrom(pop.name, x)
                    for (opt in options) {
                        for (stop in opt.sequence) {
                            addToPropositions(propositions, visited, Proposition(stop.second.name, stop.first.timeInMillis,
                                    time(distanceToEnd(stop.second.latitude, stop.second.Longitude, end), tramSpeed),
                                    pop.history + " " + pop.name + "-" + opt.route + "-" + stop.second.name))
                        }
                    }
                }
                for (opt in findKClosest(stops, stops[pop.name], 5)) {
                    addToPropositions(propositions, visited, Proposition(opt.second.name, pop.time + opt.first,
                            time(distanceToEnd(opt.second.latitude, opt.second.longitude, end), tramSpeed),
                            pop.history + " " + pop.name + "-" + "walk" + "-" + opt.second.name))
                }
                for (stop in end) {
                    addToPropositions(propositions, visited, Proposition(stop,
                            pop.time + time(distance(stops[pop.name], stops[stop]), walkSpeed), 0,
                            pop.history + " " + pop.name + "-" + "walk" + "-" + stop)
                    )
                }
                if (wantBikes && stops[pop.name]!!.bike && stops[pop.name]!!.bikes > numberOfpeople) {
                    for (opt in findForBike(stops[pop.name], stops)) {
                        addToPropositions(propositions, visited, Proposition(opt.second.name, pop.time + opt.first,
                                time(distanceToEnd(opt.second.latitude, opt.second.longitude, end), tramSpeed),
                                pop.history + " " + pop.name + "-" + "bike" + "-" + opt.second.name)
                        )
                    }
                }
            }
        }
    }
}