Разработване на он-лайн информационна система за резервация на места в пътническия железопътен транспорт

func StartServer() {
  // Създаване на нова глобална променлива за данните
  razpisanie = NewRazpisanie()
  // Зареждане на входящите данни
  razpisanie.LoadFromFile("data/paths.txt")
  // Обработка на данните
  razpisanie.Process()

  log.Println("Server operational")
  // Дефиниране на услугите на сървъра
  http.Handle("/route", http.HandlerFunc(routeHandler))
  http.Handle("/distance", http.HandlerFunc(distanceHandler))
  // Стартиране на сървъра
  log.Fatal(http.ListenAndServe(":8080", nil))
}

// Основна функционална структура
type Razpisanie struct {
  tempList   TempList   // Временен списък за данните при зареждане
  stations   *Dictionary  // Речник на гарите
  trains     *Dictionary  // Речник на превозните средства
  floydGraph FloydGraph // Матрица на теглата
  dfsGraph   DFSGraph   // Разширен граф
}

// Зареждане на данните от файл
func (raz *Razpisanie) LoadFromFile(file_name string) {
  // Отваряне на файла за четене
  f, err := os.Open(file_name)
  if err != nil {
    // В случай на грешка прекъсваме работата на модула
    panic(err)
  }
  // Заявка за затваряне на файла след приключване на работа с него
  defer f.Close()

  // Обект за буферирано четене от файлов дескриптор
  reader := bufio.NewReader(f)

  line := 1 // Брояч на редове
  for {
    // Прочитане на ред от файла
    rline, _, err := reader.ReadLine()

    if err != nil {
      break // Приключване на четенето
    }
    // Разделяне на реда на елементи
    array := strings.Split(string(rline), SEPARATOR)

    train_id, _ := strconv.Atoi(array[0]) // Идентификатор на превозно средство
    train_name := array[1]  // Име на превозно средство
    station_id, _ := strconv.Atoi(array[2]) // Идентификатор на гара
    station_name := array[3]  // Име на гара

    var row TRow  // Нов ред-контейнер за временния списък

    row.arrival, _ = strconv.Atoi(array[4]) // Час на пристигане
    row.departure, _ = strconv.Atoi(array[5]) // Час на заминаване
    row.length, _ = strconv.Atoi(array[6]) // Дължина пътуването от началната точка

    // Добавяне на името и идентификатора на гара в речника за гари и
    // указване на вътрешния идентификатор във реда-контейнер
    row.station = raz.stations.Add(station_id, station_name)
    // Добавяне на името и идентификатора на превозно средство в речника за превозни
    // средства и указване на вътрешния идентификатор във реда-контейнер
    row.train = raz.trains.Add(train_id, train_name)

    // Добавяне на реда-контейнер във временния списък
    raz.tempList = append(raz.tempList, &row)
    line++ // Увеличаване на брояча на редове
  }
  log.Printf("Loaded %d lines from \"%s\"\n", line, file_name)
}

// Обработка на временния списък
func (raz *Razpisanie) Process() {
  // Създаване на структурата за матрица на теглата
  (*raz).floydGraph = *(NewFloydGraph((*raz).stations.Len()))
  // Създаване на структурата за разширен граф
  (*raz).dfsGraph = *(NewDFSGraph((*raz).stations.Len()))

  // Инициализация на променливите
  var (
    last_station  int = -1
    last_train    int = -1
    last_distance     = 0
    distance          = 0

    node1 *DFSNode = nil
    node2 *DFSNode = nil
  )


  // Обработка на входящите данни
  for _, row := range (*raz).tempList {
    if row.length == 0 {
      last_distance = 0
    }
    distance = row.length - last_distance
    //Floyd
    if last_station != -1 && row.train == last_train {
      if row.length == 0 {
        last_distance = 0
      }
      // Добавяме разстоянието в матрицата на теглата
      (*raz).floydGraph.Add(last_station, row.station, distance)
      last_distance = row.length
    }
    //DFS
    if row.arrival != 0 {
      // Добавяме нов връх от тип "пристигане"
      node1 = (*raz).dfsGraph.AddTrainStation(row.train, row.station, row.arrival, ARRIVAL)
    } else {
      node1 = nil
    }
    if node1 != nil && node2 != nil {
      // Добавяме дъга за продължаване на пътуването
      node2.addArc(node1, distance, CONTINUE)
    }
    if row.departure != 0 {
      // Добавяме нов връх от тип "заминаване"
      node2 = (*raz).dfsGraph.AddTrainStation(row.train, row.station, row.departure, DEPARTURE)
    } else {
      node2 = nil
    }
    if node1 != nil && node2 != nil {
      // Добавяме дъга за продължаване на пътуването
      node1.addArc(node2, 0, CONTINUE)
    }

    last_station = row.station
    last_train = row.train
  }
  // Обработка на матрица на теглата
  (*raz).floydGraph.Resolve()
  // Обработка на разширен граф
  (*raz).dfsGraph.Init()
}

type FloydGraph [][]int

// Създаване на нова матрица на теглата и инициализиране
// на всички клетки с INFINITY
func NewFloydGraph(num_stations int) *FloydGraph {
  // създаване на първото измерение на матрицата
  fg := make(FloydGraph, num_stations)
  for x := range fg {
    // създаване на второто измерение
    fg[x] = make([]int, num_stations)
    for y := range fg[x] {
      // инициализиране на клетките
      fg[x][y] = INFINITY
    }
  }
  return &fg
}

  // Обработка на входящите данни
  for _, row := range (*raz).tempList {
    if row.length == 0 {
      last_distance = 0
    }
    distance = row.length - last_distance
    //Floyd
    if last_station != -1 && row.train == last_train {
      if row.length == 0 {
        last_distance = 0
      }
      // Добавяме разстоянието в матрицата на теглата
      (*raz).floydGraph.Add(last_station, row.station, distance)
      last_distance = row.length
    }

    // ....

    last_station = row.station
    last_train = row.train
  }

// връщаме по-малкото от две цели числа
func MinInt(v1, v2 int) int {
  if v1 <= v2 {
    return v1
  }
  return v2
}

// Определяне на минимални пътища между върхове на граф
// по алгоритъм на Флойд-Уоршал
func (fg *FloydGraph) Resolve() {
  n := len(*fg) // Размерността на матрицата
  for k := 0; k < n; k++ {
    for i := 0; i < n; i++ {
      for j := 0; j < n; j++ {
        if i == j {
          (*fg)[i][j] = 0 // Разстоянието от гарата до самата нея винаги е 0
        } else {
          (*fg)[i][j] = MinInt((*fg)[i][j], (*fg)[i][k]+(*fg)[k][j])
        }
      }
    }
  }
}

// Разстояние между гари x и y
func (fg *FloydGraph) GetDistance(x, y int) int {
  return (*fg)[x][y]
}

// Разширен граф
type DFSGraph []*NodeColumn

// Колона на гара
type NodeColumn []*DFSNode

// Връх
type DFSNode struct {
  station int     // гара
  train   int     // влак
  time    int     // време(минути)
  ntype   bool    // тип на върха
  arcs    []*DFSArc   // списък дъги
}

// Дъга
type DFSArc struct {
  next   *DFSNode   // връх
  length int      // тегло (дължина)
  atype  bool     // тип на дъгата
}

const (
  // ...
  DEPARTURE = true  // заминаване
  ARRIVAL   = false // пристигане
  // ...
)

const (
  // ...
  CONTINUE = true   // движение на влака
  TRANSFER = false  // трансфер
  // ...
)

// Създаване на нов разширен граф
func NewDFSGraph(num_stations int) *DFSGraph {
  dfs := make(DFSGraph, num_stations)
  for i := 0; i < num_stations; i++ {
    // Създаване на колона за всяка гара
    dfs[i] = NewNodeColumn()
  }
  return &dfs
}

  // Обработка на входящите данни
  for _, row := range (*raz).tempList {
    if row.length == 0 {
      last_distance = 0
    }
    distance = row.length - last_distance

    // ....

    if row.arrival != 0 {
      // Добавяме нов връх от тип "пристигане"
      node1 = (*raz).dfsGraph.AddTrainStation(row.train, row.station, row.arrival, ARRIVAL)
    } else {
      node1 = nil
    }
    if node1 != nil && node2 != nil {
      // Добавяме дъга за продължаване на пътуването
      node2.addArc(node1, distance, CONTINUE)
    }
    if row.departure != 0 {
      // Добавяме нов връх от тип "заминаване"
      node2 = (*raz).dfsGraph.AddTrainStation(row.train, row.station, row.departure, DEPARTURE)
    } else {
      node2 = nil
    }
    if node1 != nil && node2 != nil {
      // Добавяме дъга за продължаване на пътуването
      node1.addArc(node2, 0, CONTINUE)
    }

    last_station = row.station
    last_train = row.train
  }

// Създаване на нов връх
func NewNode(station, train, time int, ntype bool) *DFSNode {
  return &DFSNode{station, train, time, ntype, nil}
}

//Добавяне на връх в графа
func (dfs *DFSGraph) addNode(station int, node *DFSNode) {
  nc := (*dfs)[station]
  nnc := append(*nc, node)
  (*dfs)[station] = &nnc
}

// Добавяне на връх
func (dfs *DFSGraph) AddTrainStation(train int, station int, time int, ntype bool) *DFSNode {
  node := NewNode(station, train, time, ntype)  //Създаваме нов връх
  dfs.addNode(station, node) // Добавяме върхът в графа
  return node
}

// Създаване на нова дъга
func NewArc(next *DFSNode, length int, atype bool) *DFSArc {
  return &DFSArc{next, length, atype}
}

// Добавяне на дъга между два върха
func (node *DFSNode) addArc(next *DFSNode, length int, atype bool) {
  // Добавя нов дъга към списъка с дъги на текущия връх
  node.arcs = append(node.arcs, NewArc(next, length, atype))
}

// Проверка за възможен трансфер между влакове
func (node *DFSNode) canTransferTo(next *DFSNode) bool {
  return node.ntype == ARRIVAL && // Влак 1 пристига
    next.ntype == DEPARTURE && // Влак 2 заминава
    node.train != next.train && // Влак 1 <> Влак 2
    next.time-node.time >= MIN_TRANSFER_TIME && // Времето между двете събития е по-голямо или равно на минималното трансферно време
    next.time-node.time <= MAX_TRANSFER_TIME // Времето между двете събития е по-малко или равно на максималното трансферно време
}

// Инициализиране на трансферните дъги
func (dfs *DFSGraph) Init() {
  for _, nc := range *dfs {
    sort.Sort(nc) // Сортираме върховете във всяка гара по време
    c := nc.Len()
    for i, node := range *nc {
      for j := i; j < c; j++ {
        // Ако е възможен трансферът между два върха
        if node.canTransferTo((*nc)[j]) {
          // Създаваме трансферна дъга
          node.addArc((*nc)[j], 0, TRANSFER)
        }
      }
    }
  }
}

// Брой елементи в колоната
func (nc *NodeColumn) Len() int {
  return len(*nc)
}

// Компаратор
func (nc *NodeColumn) Less(i, j int) bool {
  return (*nc)[i].time < (*nc)[j].time // Сравняваме по време
}

// Разменяне на местата на два върха
func (nc *NodeColumn) Swap(i, j int) {
  (*nc)[i], (*nc)[j] = (*nc)[j], (*nc)[i]
}

func StartServer() {
  // Създаване на нова глобална променлива за данните
  razpisanie = NewRazpisanie()
  // Зареждане на входящите данни
  razpisanie.LoadFromFile("data/paths.txt")
  // Обработка на данните
  razpisanie.Process()

  log.Println("Server operational")
  // Дефиниране на услугите на сървъра
  http.Handle("/route", http.HandlerFunc(routeHandler))
  http.Handle("/distance", http.HandlerFunc(distanceHandler))
  // Стартиране на сървъра
  log.Fatal(http.ListenAndServe(":8080", nil))
}

// Реализация на услугата distance
func distanceHandler(w http.ResponseWriter, r *http.Request) {
  // Идентификатор на начална гара
  fromid, _ := strconv.Atoi(r.FormValue("from"))
  // Идентификатор на крайна гара
  toid, _ := strconv.Atoi(r.FormValue("to"))
  // Вътрешен идентификатор на начална гара
  from := razpisanie.stations.FindId(fromid)
  // Вътрешен идентификатор на крайна гара
  to := razpisanie.stations.FindId(toid)

  log.Printf("Distance from: %d\tto: %d", from, to)
  // Разстоянието се получава директно от матрицата на теглата
  p := razpisanie.FindDistance(from, to)
  // Връщане на резултата към клиента
  fmt.Fprint(w, p)
}

func (raz *Razpisanie) FindDistance(from, to int) int {
  return (*raz).floydGraph.GetDistance(from, to)
}

// Реализация на услугата route
func routeHandler(w http.ResponseWriter, r *http.Request) {
  // Идентификатор на начална гара
  fromid, _ := strconv.Atoi(r.FormValue("from"))
  // Идентификатор на крайна гара
  toid, _ := strconv.Atoi(r.FormValue("to"))
  // Вътрешен идентификатор на начална гара
  from := razpisanie.stations.FindId(fromid)
  // Вътрешен идентификатор на крайна гара
  to := razpisanie.stations.FindId(toid)

  log.Printf("Search from: %d\tto: %d", from, to)
  // Търсене на маршрути
  p := razpisanie.FindRoutes(from, to)
  // Изграждане на JSON формат на резултата
  fmt.Fprint(w, Encode(p))
}

// Търсене на близки до оптималния маршрути
func (raz *Razpisanie) FindRoutes(from, to int) *Paths {
  // Минимално разстояние между две гари
  min_distance := (*raz).floydGraph.GetDistance(from, to)
  var p *Paths = nil // Нов контейнер за маршрути
  // Започва проверката от маршрути без прехвърляне като се увеличават възможните
  // прехвърляния с единица докато не се получи възможен по смисъла на ограниченията
  // маршрут(и)
  for max_transfers := 0; max_transfers <= MAX_TRANSFERS; max_transfers++ {
    // Търсене в дълбочина на разширен граф
    p = (*raz).dfsGraph.FindRoutes(from, to, int(float64(min_distance)*DISTANCE_COEF), &(*raz).floydGraph, max_transfers)
    // В случай на резултат търсенето се прекратява
    if len((*p).paths) > 0 {
      // Връщане на откритите резултати
      return p
    }
  }
  return p
}

  MAX_TRANSFERS = 4 // Максимален брой прехвърляния

  DISTANCE_COEF = 1.2 // Коефициент на разстояние

// Търсене в дълбочина на граф
func (p *Paths) FindWay(node *DFSNode, end_station, length, transfers, max_transfers int) {
  // При достигане на крайната гара
  if node.station == end_station {
    // Добавяне на крайната гара в стека
    p.stack.Push(NewStackNode(node, nil))
    // Копиране на стека в списъка с маршрути
    p.AddPath()
    // Изкарване на последната гара от стека
    _ = p.stack.Pop()
  } else {
    // Обхождане на всички дъги за върха
    for _, arc := range node.arcs {
      // Ако дъгата не е крайна т.е последна гара
      if arc.next != nil {
        // Забранява прехвърлянето за начална гара
        if length == 0 && arc.atype == TRANSFER {
          continue
        }
        // Разстоянието от текущата гара до крайната гара
        now := (*p).floyd.GetDistance(node.station, end_station)
        // Разстоянието от следващата гара до крайната гара
        next := (*p).floyd.GetDistance(arc.next.station, end_station)
        // Проверка дали следваща гара ни доближава до целта,
        // дали разстоянието не надхвърля максималното разстояние,
        // дали броят прехвърляния не надхвърля максималният брой прехвърляния
        if now >= next && arc.length+length <= (*p).max_distance && transfers <= max_transfers {
          // Добавяме следващия връх и дъгата до него в стека
          p.stack.Push(NewStackNode(node, arc))
          // Ако дъгата е прехвърляне, увеличаваме броят на прехвърлянията
          add := 0
          if arc.atype == TRANSFER {
            add = 1
          }
          // Викаме търсене в дълбочина с новия връх
          p.FindWay(arc.next, end_station, length+arc.length, (transfers + add), max_transfers)
          // Изваждаме последния елемент от стека
          _ = p.stack.Pop()
        }
      }
    }
  }
}

type StackNode struct {
  node *DFSNode // Връх
  arc  *DFSArc  // Дъга
}

// Създаване на нов елемент за стека
func NewStackNode(node *DFSNode, arc *DFSArc) *StackNode {
  return &StackNode{node, arc}
}

// Добавяне на стек към списъкът с маршрути
func (p *Paths) AddPath() {
  //Създаване на копие на текущия стек
  ns := (*p).stack.Copy()
  p.paths = append(p.paths, ns)
}

type Paths struct {
  max_distance int      // Максимално разстояние
  floyd        *FloydGraph  // Матрица на теглата
  stack        *Stack     // Текущ стек
  paths        []*Stack   // Списък маршрути
}

// Експортна структура
type JSONStack []JSONPath

// Маршрут
type JSONPath struct {
  From_Station_Id int       `json:"from_station_id"`
  To_Station_Id   int       `json:"to_station_id"`
  Distance        int       `json:"distance"`
  Transfers       int       `json:"transfers"`
  Departure_Time  int       `json:"departure_time"`
  Arrival_Time    int       `json:"arrival_time"`
  Details         []JSONDetail  `json:"details"`
}

// Сегмент от маршрута
type JSONDetail struct {
  Train_Id        int       `json:"train_id"`
  From_Station_Id int       `json:"from_station_id"`
  To_Station_Id   int       `json:"to_station_id"`
  Distance        int       `json:"distance"`
  Departure_Time  int       `json:"departure_time"`
  Arrival_Time    int       `json:"arrival_time"`
}

// Подготвяне на маршрутите за връщане към клиента
func Encode(p *Paths) string {
  // Създаване и запълване нова експортна структура
  js := p.CreateJSONStack(razpisanie.stations, razpisanie.trains)
  // Преобразуване на структурата в JSON запис
  b, err := json.Marshal(js)
  if err != nil {
    log.Println(err)
    b = []byte("{'err': 'Marshal Failure'}")
  }
  // Връщане на JSON текста
  return string(b)
}

// Създаване и запълване нова експортна структура
func (p *Paths) CreateJSONStack(stations, trains *Dictionary) JSONStack {
  var js JSONStack
  for _, s := range p.paths {
    // Добавяне към експортната структура на всеки маршрут
    js = append(js, s.DumpJSON(stations, trains))
  }
  return js
}

// Експорт на заглавна част на маршрута
func (s *Stack) DumpJSON(stations, trains *Dictionary) JSONPath {
  var jp JSONPath
  // Начална гара
  jp.From_Station_Id = (*stations)[(*s)[0].node.station].id
  // Крайна гара
  jp.To_Station_Id = (*stations)[(*s)[len(*s)-1].node.station].id
  // Разстояние и брой прехвърляния
  jp.Distance, jp.Transfers = s.GetDistanceAndTransfers()
  // Час на потегляне за маршрута
  jp.Departure_Time = (*s)[0].node.time
  // Час на пристигане за маршрута
  jp.Arrival_Time = (*s)[len(*s)-1].node.time
  // Експорт на сегментите на маршрута
  jp.Details = (*s).DumpRouteDeatilsJSON(stations, trains)
  return jp
}

// Експорт на сегментите на маршрута
func (s *Stack) DumpRouteDeatilsJSON(stations, trains *Dictionary) []JSONDetail {
  var jds []JSONDetail
  var jd JSONDetail
  jd.Distance = 0     // Разстояние за сегмента
  jd.To_Station_Id = 0  // Крайна гара за сегмента
  jd.Arrival_Time = 0   // Час на пристигане за сегмента
  // Идентификатор на влак за сегмента
  jd.Train_Id = (*trains)[(*s)[0].node.train].id
  // Начална гара за сегмента
  jd.From_Station_Id = (*stations)[(*s)[0].node.station].id
  // Час на потегляне за сегмента
  jd.Departure_Time = (*s)[0].node.time
  // Обхождане на всички елементи на маршрута
  for _, path := range *s {
    // Промяна на крайната гара
    jd.To_Station_Id = (*stations)[path.node.station].id
    // Промяна на часа на пристигане
    jd.Arrival_Time = path.node.time
    // Ако има следващ връх
    if path.arc != nil {
      // Добавяме разстоянието на дъгата към сегмента
      jd.Distance += path.arc.length
      // Ако дъгата е за прехвърляне
      if path.arc.atype == TRANSFER {
        // Добавяме сегмента към резултата
        jds = append(jds, jd)
        // Инициализираме променливите за новия сегмент
        jd.Distance = 0
        jd.Train_Id = (*trains)[path.node.train].id
        jd.From_Station_Id = (*stations)[path.node.station].id
        jd.Departure_Time = path.node.time
      }
    }
  }
  // Добавяме последния сегмент
  jds = append(jds, jd)
  return jds
}

func (p *Paths) FindWay(node *DFSNode, end_station, length, transfers, max_transfers int) {
  if node.station == end_station {
    p.stack.Push(NewStackNode(node, nil))
    p.AddPath()
    _ = p.stack.Pop()
  } else {
    for _, arc := range node.arcs {
      if arc.next != nil {
        // Без прехвърляне на първа станция
        if length == 0 && arc.atype == TRANSFER {
          continue
        }
        // Избор на дъга само ако ни приближава към целта
        now := (*p).floyd.GetDistance(node.station, end_station)
        next := (*p).floyd.GetDistance(arc.next.station, end_station)
        if now >= next && arc.length+length <= (*p).max_distance && transfers <= max_transfers {
          p.stack.Push(NewStackNode(node, arc))
          add := 0
          if arc.atype == TRANSFER {
            add = 1
          }
          p.FindWay(arc.next, end_station, length+arc.length, (transfers+add), max_transfers)
          _ = p.stack.Pop()
        }
      }
    }
  }
}