This is a JavaScript implementation of the algorithms composing GTFSCompress by Sebastian Wandelt, Xiaoqian Sun and Yanbo Zhu.
I'm in no way affiliated to the authors of the paper.
Time.js — Provides the class Time to operate over only time values, which is not possible with the Date class.
gtfscompress.js — Provides the functions implementing the algorithims described in the paper.
| /* GTFS Compress */ | |
| /** | |
| * | |
| * @param {Array<Array<String>>} stop_times to-be-compressed GTFS relation | |
| * @param {number} window_size | |
| * @returns {Array<Array<Strig>>} Referentially compressed GTFS relation | |
| */ | |
| function compress_stop_times(stop_times,window_size){ | |
| heads = stop_times[0]; | |
| RCQ = {} | |
| stop_id_index = heads.indexOf("stop_id"); | |
| arrival_time_index = heads.indexOf("arrival_time"); | |
| departure_time_index = heads.indexOf("departure_time"); | |
| for (m=0;m<heads.length;m++) { | |
| RCQ[heads[m]] = [`R${stop_times[0][m]}`] | |
| } | |
| for (m=1;m<stop_times.length;m++){ | |
| avaliable_window_size = (window_size-(stop_times.length-m))-1; //to avoid undefineds | |
| for (o=0;o<heads.length;o++){ | |
| if(heads[o]=="trip_id"||heads[o]=="stop_sequence"){ | |
| RCQ[heads[o]].push(encodeINC(stop_times[m][o],stop_times[m-1][o])); | |
| } | |
| else{ | |
| if(heads[o]=="stop_id"){ | |
| RCQ[heads[o]].push(encodeSUCC(stop_times[m][o], | |
| getCol(stop_times.slice(m-avaliable_window_size,m-1),stop_id_index) | |
| )); | |
| } | |
| else{ | |
| if(heads[o]=="arrival_time"){ | |
| RCQ[heads[o]].push(encodeAT(stop_times[m][o], | |
| stop_times[m][stop_id_index], | |
| getCol(stop_times.slice(m-avaliable_window_size,m-1),arrival_time_index),getCol(stop_times.slice(m-avaliable_window_size,m-1),departure_time_index),getCol(stop_times.slice(m-avaliable_window_size,m-1),stop_id_index) | |
| )); | |
| } | |
| else{ | |
| if(heads[o]=="departure_time"){ | |
| RCQ[heads[o]].push(encodeDT(stop_times[m][o], | |
| stop_times[m][stop_id_index],stop_times[m][arrival_time_index], | |
| getCol(stop_times.slice(m-avaliable_window_size,m-1),arrival_time_index),getCol(stop_times.slice(m-avaliable_window_size,m-1),departure_time_index),getCol(stop_times.slice(m-avaliable_window_size,m-1),stop_id_index) | |
| )); | |
| } | |
| else{ | |
| RCQ[heads[o]].push(stop_times[m][o]); | |
| } | |
| } | |
| } | |
| } | |
| } | |
| } | |
| RCR = [] | |
| for (m=0;m<heads.length;m++) { | |
| RCR.push(RCQ[heads[m]]); | |
| } | |
| return RCR; | |
| } | |
| /** | |
| * | |
| * @param {String} cur Current Item | |
| * @param {String} prev Preceding Item | |
| * @returns {String} Code for `cur` compressed against `prev` | |
| */ | |
| function encodeINC(cur,prev){ | |
| sufcur= cur.substring(cur.search("[0-9]")); | |
| prefcur= cur.substring(0,cur.search("[0-9]")); | |
| sufprev= prev.substring(prev.search("[0-9]")); | |
| prefprev= prev.substring(0,prev.search("[0-9]")); | |
| if(cur.localeCompare(prev)==0){ | |
| code = "I" | |
| } | |
| else{ | |
| if(prefcur.localeCompare(prefprev)==0 && (sufcur.length > 0 && sufprev > 0)){ | |
| code = `D${parseInt(sufcur)-parseInt(sufprev)}`; | |
| } | |
| else{ | |
| code = `R${cur}` | |
| } | |
| } | |
| return code; | |
| } | |
| /** | |
| * | |
| * @param {String} cur Current Item | |
| * @param {Array<String>} window Preceding Items in Window | |
| * @returns {String} Code for `cur` compressed against `window` | |
| */ | |
| function encodeSUCC(cur,window){ | |
| code = ""; | |
| pos = -1; | |
| for(let m=1;m<window.length;m++){ | |
| if(window[window.length-1]=window[m]){ | |
| pos = m; | |
| break; | |
| } | |
| } | |
| if(pos>=0 && (window[pos+1]==cur)){ | |
| code = "M"; | |
| } | |
| else{ | |
| code = `R${cur}`; | |
| } | |
| return code; | |
| } | |
| /** | |
| * | |
| * @param {string} arrival_time Current Arrival Time | |
| * @param {string} stop_id Current Stop ID | |
| * @param {Array<String>} arrival_time_window preceding items in arrival time window | |
| * @param {Array<String>} departure_time_window preceding items in departure time window | |
| * @param {Array<String>} stop_id_window preceding items in stop id window | |
| * @returns {string} Code for `arrival_time` compressed against `stop_id` and the input windows | |
| */ | |
| function encodeAT(arrival_time,stop_id,arrival_time_window,departure_time_window,stop_id_window){ | |
| arrival_time = Time.parse(arrival_time); //Has trouble with +24 hour schedules | |
| for(let m=0;m<arrival_time_window.length;m++){ | |
| arrival_time_window[m] = Time.parse(arrival_time_window[m]); | |
| departure_time_window[m] = Time.parse(departure_time_window[m]); | |
| } | |
| for(let m=1;m<arrival_time_window.length;m++){ | |
| timediff = arrival_time.difference(departure_time_window[departure_time_window.length-1]); | |
| if((stop_id==stop_id_window[m-1]) && (stop_id_window[stop_id_window.length-1]==stop_id_window[m]) && (arrival_time_window[m-1].difference(departure_time_window[m]).isEqual(timediff)) ){ // Review for string comparison | |
| return "M"; | |
| } | |
| else{ | |
| if((stop_id==stop_id_window[m-1])&&(stop_id_window[stop_id_window.length-1]==stop_id_window[m])){ | |
| return `D${timediff.difference(arrival_time_window[m-1].difference(departure_time_window[m])).toSeconds()}`; // Review for integer conversion and comparison | |
| } | |
| } | |
| } | |
| return `R${arrival_time}`; | |
| } | |
| /** | |
| * | |
| * @param {String} departure_time Current departure time | |
| * @param {String} stop_id Current Stop ID | |
| * @param {String} arrival_time Current Arrival Time | |
| * @param {Array<String>} arrival_time_window Preceding items in Arrival Time Window | |
| * @param {Array<String>} departure_time_window Preceding items in Departure Time Window | |
| * @param {Array<String>} stop_id_window Preceding items in Stop ID Window | |
| * @returns {String} Code for `departure_time` compressed against `stop_id`, `arrival_time`, and the input windows | |
| */ | |
| function encodeDT(departure_time,stop_id,arrival_time,arrival_time_window,departure_time_window,stop_id_window){ | |
| departure_time = Time.parse(departure_time); //Has trouble with +24 hour schedules | |
| arrival_time = Time.parse(arrival_time); //Has trouble with +24 hour schedules | |
| for(let m=0;m<arrival_time_window.length;m++){ | |
| arrival_time_window[m] = Time.parse(arrival_time_window[m]); | |
| departure_time_window[m] = Time.parse(departure_time_window[m]); | |
| } | |
| timediff = departure_time.difference(arrival_time); | |
| if(timediff==0){ | |
| return "A"; | |
| } | |
| for(let m=1;m<arrival_time_window.length;m++){ | |
| if((stop_id==stop_id_window[m])&&(departure_time_window[m].difference(arrival_time_window[m]).isEqual(timediff))){ /* Review for integer conversion and comparison |Review for string comparison */ | |
| return "M"; | |
| } | |
| else{ | |
| if(stop_id==stop_id_window[m]){/* Review for string comparison */ | |
| return `D${timediff.difference(departure_time_window[m].difference(arrival_time_window[m]))}` /* Review for integer conversion and comparison */ | |
| } | |
| } | |
| } | |
| return `S${timediff.toSeconds()}`; | |
| } | |
| /** | |
| * | |
| * @param {Array<Array<String>} shapes to-be-compressed GTFS relation | |
| * @param {number} window_size | |
| * @returns {Array<Array<String>>} Referentially compressed GTFS relation | |
| */ | |
| function compress_shapes(shapes,window_size){ | |
| heads = shapes[0]; | |
| RCQ = {} | |
| shape_pt_lat_index = heads.indexOf("shape_pt_lat"); | |
| shape_pt_lon_index = heads.indexOf("shape_pt_lon"); | |
| for (m=0;m<heads.length;m++) { | |
| RCQ[heads[m]] = [`R${shapes[0][m]}`] | |
| } | |
| for (m=1;m<shapes.length;m++){ | |
| for (o=0;o<heads.length;o++){ | |
| if(heads[o]=="shape_id"||heads[o]=="shape_pt_sequence"){ | |
| RCQ[heads[o]].push(encodeINC(shapes[m][o],shapes[m-1][o])); | |
| } | |
| else{ | |
| if(heads[o]=="shape_dist_traveled"){ | |
| RCQ[heads[o]].push(encodeDIST(shapes[m][o], | |
| shapes[m][shape_pt_lat_index],shapes[m][shape_pt_lon_index], | |
| shapes[m-1][shape_pt_lat_index],shapes[m-1][shape_pt_lon_index], | |
| shapes[m-1][o])) | |
| } | |
| else{ | |
| RCQ[heads[o]].push(`R${shapes[m][o]}`) | |
| } | |
| } | |
| } | |
| } | |
| RCR = [] | |
| for (m=0;m<heads.length;m++) { | |
| RCR.push(RCQ[heads[m]]); | |
| } | |
| return RCR; | |
| } | |
| /** | |
| * | |
| * @param {*} cur | |
| * @param {*} lat1 | |
| * @param {*} lon1 | |
| * @param {*} lat2 | |
| * @param {*} lon2 | |
| * @param {*} dist Previous Distance | |
| * @returns | |
| */ | |
| function encodeDIST(cur, lat1, lon1, lat2, lon2, dist){ | |
| cur = parseFloat(cur); | |
| lat1 = parseFloat(lat1); | |
| lat2 = parseFloat(lat2); | |
| lon1 = parseFloat(lon1); | |
| lon2 = parseFloat(lon2); | |
| dist = parseFloat(dist); | |
| a = Math.pow(Math.sin((lat2-lat1).toRad()/2),2)+(Math.cos(lat1.toRad())*Math.cos(lat2.toRad())*Math.pow(Math.sin((lon2-lon1).toRad()/2),2)); | |
| c = 2 * Math.atan2(Math.sqrt(a),Math.sqrt(1-a)); | |
| stepKM = c * 6371; | |
| stepMI = c * 3959; | |
| if(dist+stepKM==cur){ | |
| return "K"; | |
| } | |
| else{ | |
| if(dist+stepMI==cur){ | |
| return "M"; | |
| } | |
| else{ | |
| if(dist+(stepKM/1000)==cur){ | |
| return "E"; | |
| } | |
| else{ | |
| if(dist+(stepMI/5280)==cur){ | |
| return "F"; | |
| } | |
| else{ | |
| return `R${cur}` | |
| } | |
| } | |
| } | |
| } | |
| } | |
| /** | |
| * | |
| * @param {Array<Array<String>>} trips | |
| * @param {number} window_size | |
| * @returns | |
| */ | |
| function compress_trips(trips, window_size){ | |
| heads = trips[0]; | |
| RCQ = {}; | |
| for (m=0;m<heads.length;m++) { | |
| RCQ[heads[m]] = [`R${trips[0][m]}`] | |
| } | |
| for(let m=1;m<trips.length;m++){ | |
| for(o=0;o<heads.length;o++){ | |
| if(heads[o]=="route_id"||heads[o]=="service_id"||heads[o]=="trip_id"||heads[o]=="shape_id"||heads[o]=="block_id"){ | |
| RCQ[heads[o]].push(encodeINC(trips[m][o],trips[m-1][o])); | |
| } | |
| else{ | |
| RCQ[heads[o]].push(`R${trips[m][o]}`); | |
| } | |
| } | |
| } | |
| RCR = [] | |
| for (m=0;m<heads.length;m++) { | |
| RCR.push(RCQ[heads[m]]); | |
| } | |
| return RCR; | |
| } | |
| /* UTILS */ | |
| function getCol(matrix, col){ | |
| var column = []; | |
| for(let m=0; m<matrix.length; m++){ | |
| column.push(matrix[m][col]); | |
| } | |
| return column; | |
| } | |
| Number.prototype.toRad = function() { | |
| return this * Math.PI / 180; | |
| } |
| class Time{ | |
| constructor(hour,minutes,seconds){ | |
| this.hour = hour; | |
| this.minutes = minutes; | |
| this.seconds = seconds; | |
| } | |
| static parse(formattedString) { | |
| let re = new RegExp(/(?:(\d\d)(?::?(\d\d)(?::?(\d\d)(?:[.,](\d+))?)?)?)/); | |
| let match = formattedString.match(re); | |
| if (match != null) { | |
| function parseIntOrZero(matched){ | |
| if (matched == null) return 0; | |
| return parseInt(matched); | |
| } | |
| let hour = parseIntOrZero(match[1]); | |
| let minute = parseIntOrZero(match[2]); | |
| let second = parseIntOrZero(match[3]); | |
| return new Time(hour, minute, second) | |
| } | |
| else{ | |
| throw `Invalid time format ${formattedString}` | |
| } | |
| } | |
| toSeconds(){ | |
| return (this.hour*3600)+(this.minutes*60)+this.seconds; | |
| } | |
| toString(){ | |
| function twoDigits(n){ | |
| if (n >= 10) return `${n}`; | |
| return `0${n}`; | |
| } | |
| return `${twoDigits(this.hour)}:${twoDigits(this.minutes)}:${twoDigits(this.seconds)}`; | |
| } | |
| addition(other){ | |
| let seconds = this.seconds + other.seconds; | |
| let minutes = this.minutes + other.minutes + Math.floor(this.seconds/60); | |
| let hours = this.hour + other.hour + Math.floor(this.minutes/60); | |
| return Time(hours,minutes%60,seconds%60); | |
| } | |
| difference(other){ | |
| if (this.seconds < other.seconds){ | |
| --this.minutes; | |
| this.seconds += 60; | |
| } | |
| if (this.minutes < other.minute){ | |
| --this.hour; | |
| this.minutes +=60; | |
| } | |
| if (this.hour < other.hour){ | |
| this.hour += 24; | |
| } | |
| return new Time(this.hour-other.hour,this.minutes-other.minutes,this.seconds-other.seconds); | |
| } | |
| isEqual(other){ | |
| return (this.hour == other.hour) && (this.minutes==other.minutes) && (this.seconds == other.seconds); | |
| } | |
| } |