path: root/backend-go/internal/core/route.go

package core

import (
	"container/heap"
	"log"
	"sort"
)

const (
	MaxCapital           = 100000000000.0 // 100B
	MaxTradesToConsider  = 200 // Keep bound so we don't evaluate forever, python doesn't effectively bound it
)

type Action struct {
	ActionType string  `json:"action_type"` // "buy" or "sell"
	Item       string  `json:"item"`
	TypeID     int     `json:"type_id"`
	Quantity   int     `json:"quantity"`
	Price      float64 `json:"price"`
}

type RouteStep struct {
	ID           int      `json:"id"`
	LocationID   int      `json:"location_id"`
	Location     string   `json:"location"`
	LocationType string   `json:"location_type"`
	SystemID     int      `json:"system_id,omitempty"`
	SystemName   string   `json:"system_name,omitempty"`
	StationName  string   `json:"station_name,omitempty"`
	Security     float64  `json:"security,omitempty"`
	RegionID     int      `json:"region_id,omitempty"`
	Actions      []Action `json:"actions"`
}

type RouteInfo struct {
	ProfitRate    float64 `json:"profit_rate"`
	Risk          float64 `json:"risk"`
	Capital       float64 `json:"capital"`
	TransportTime float64 `json:"transport_time"`
	GrossProfit   float64 `json:"gross_profit"`
	NetProfit     float64 `json:"net_profit"`
}

type RoutePlan struct {
	Route          []RouteStep
	Info           *RouteInfo
	OptimizedTrades []Trade
	Path           []int
	RawOffsets     []int
}

type Ship struct {
TaxRate          float64            `json:"tax_rate"`
ProfitThreshold  float64            `json:"profit_threshold"`
MaxCapital       float64            `json:"max_capital"`
SnipeThreshold   float64            `json:"snipe_profit_threshold"`
Location         int                `json:"location"`
Cargo            float64            `json:"cargo"`
MaxWarpSpeed     float64            `json:"max_warp_speed"`
MaxSubwarpSpeed  float64            `json:"max_subwarp_speed"`
GankersAreas     map[string]float64 `json:"gankers_areas"`
PlayerCost       float64            `json:"player_cost"`
RiskCost         float64            `json:"risk_cost"`
ShipCost         float64            `json:"ship_cost"`
}

type tradeDensityHeap struct {
	trades []Trade
}
func (h tradeDensityHeap) Len() int { return len(h.trades) }
func (h tradeDensityHeap) Less(i, j int) bool {
	// Reverse sorted by profit density
	di := h.trades[i].GrossProfit / h.trades[i].Cargo
	dj := h.trades[j].GrossProfit / h.trades[j].Cargo
	return di > dj
}
func (h tradeDensityHeap) Swap(i, j int) { h.trades[i], h.trades[j] = h.trades[j], h.trades[i] }
func (h *tradeDensityHeap) Push(x any)    { h.trades = append(h.trades, x.(Trade)) }
func (h *tradeDensityHeap) Pop() any {
	old := h.trades
	n := len(old)
	x := old[n-1]
	h.trades = old[0 : n-1]
	return x
}

func tradeCapitalEfficiency(t Trade) float64 {
	invested := t.FromPrice * float64(t.Quantity)
	if invested > 0 {
		return t.GrossProfit / invested
	}
	return 0.0
}

func minInt(vars ...int) int {
	m := vars[0]
	for _, v := range vars[1:] {
		if v < m {
			m = v
		}
	}
	return m
}

func maxFloat(vars ...float64) float64 {
	m := vars[0]
	for _, v := range vars[1:] {
		if v > m {
			m = v
		}
	}
	return m
}

func buildRankedTriplets(trades []Trade, shipLoc int) [][3]int {
	// Sort by capital efficiency descending
	sorted := make([]Trade, len(trades))
	copy(sorted, trades)
	sort.Slice(sorted, func(i, j int) bool {
		return tradeCapitalEfficiency(sorted[i]) > tradeCapitalEfficiency(sorted[j])
	})

	var ranked [][3]int
	seen := make(map[[3]int]bool)

	for _, t := range sorted {
		trip := [3]int{shipLoc, t.FromStation, t.ToStation}
		if !seen[trip] {
			seen[trip] = true
			ranked = append(ranked, trip)
		}
	}
	return ranked
}

func buildStationPairIndex(trades []Trade) map[[2]int][]Trade {
	index := make(map[[2]int][]Trade)
	for _, t := range trades {
		pair := [2]int{t.FromStation, t.ToStation}
		index[pair] = append(index[pair], t)
	}
	for k := range index {
		sort.Slice(index[k], func(i, j int) bool {
			di := index[k][i].GrossProfit / index[k][i].Cargo
			dj := index[k][j].GrossProfit / index[k][j].Cargo
			return di > dj
		})
	}
	return index
}

func selectTrades(routeStations [3]int, tradesByPair map[[2]int][]Trade, ship Ship) []Trade {
	var candidatePairs [][2]int
	for i, fromStation := range routeStations {
		for _, toStation := range routeStations[i+1:] {
			pair := [2]int{fromStation, toStation}
			
			// ensure unique pairs
			exists := false
			for _, cp := range candidatePairs {
				if cp == pair {
					exists = true
					break
				}
			}
			if !exists {
				candidatePairs = append(candidatePairs, pair)
			}
		}
	}

	// merge candidates into max heap based on profit density
	h := &tradeDensityHeap{}
	heap.Init(h)
	for _, pair := range candidatePairs {
		if ts, ok := tradesByPair[pair]; ok {
			for _, t := range ts {
				heap.Push(h, t)
			}
		}
	}

	usedOrders := make(map[int]int)
	var optimized []Trade
	var cargo, capital float64

	for h.Len() > 0 {
		t := heap.Pop(h).(Trade)
		
		fromRemaining, ok := usedOrders[t.FromOrderID]
		if !ok {
			fromRemaining = t.Quantity
		}
		toRemaining, ok := usedOrders[t.ToOrderID]
		if !ok {
			toRemaining = t.Quantity
		}

		maxQtyCargo := int((ship.Cargo - cargo) / (t.Cargo / float64(t.Quantity))) // rough item volume
		itemVol := t.Cargo / float64(t.Quantity)
		if itemVol == 0 {
			itemVol = 0.01 // avoid divide by zero just in case
			maxQtyCargo = t.Quantity
		} else {
			maxQtyCargo = int((ship.Cargo - cargo) / itemVol)
		}
		
		maxQtyCapital := int((MaxCapital - capital) / t.FromPrice)

		maxQty := minInt(t.Quantity, fromRemaining, toRemaining, maxQtyCargo, maxQtyCapital)
		
		if maxQty <= 0 {
			continue
		}

		cargo += itemVol * float64(maxQty)
		capital += t.FromPrice * float64(maxQty)

		usedOrders[t.FromOrderID] = fromRemaining - maxQty
		usedOrders[t.ToOrderID] = toRemaining - maxQty

		updated := t
		updated.Quantity = maxQty
		updated.Cargo = itemVol * float64(maxQty)
		if t.Quantity > 0 {
			updated.GrossProfit = t.GrossProfit * (float64(maxQty) / float64(t.Quantity))
		} else {
			updated.GrossProfit = 0
		}
		
		optimized = append(optimized, updated)

		if cargo >= ship.Cargo || capital >= MaxCapital {
			break
		}
	}
	return optimized
}

func calculatePeakCapital(locationIDs []int, trades []Trade, shipCost float64) float64 {
	if len(trades) == 0 {
		return shipCost
	}

	remainingLocs := make(map[int]bool)
	for _, l := range locationIDs {
		remainingLocs[l] = true
	}

	committed := shipCost
	for _, t := range trades {
		if !remainingLocs[t.FromStation] {
			committed += t.FromPrice * float64(t.Quantity)
		}
	}

	peak := committed
	for _, loc := range locationIDs {
		// sell
		for _, t := range trades {
			if t.ToStation == loc {
				committed -= t.FromPrice * float64(t.Quantity)
			}
		}
		committed = maxFloat(shipCost, committed)

		// buy
		for _, t := range trades {
			if t.FromStation == loc {
				committed += t.FromPrice * float64(t.Quantity)
			}
		}
		peak = maxFloat(peak, committed)
	}

	return peak
}

func buildRouteInfo(locationIDs []int, trades []Trade, ship Ship, time, risk float64) *RouteInfo {
	if len(trades) == 0 {
		return nil
	}
	
	capital := calculatePeakCapital(locationIDs, trades, ship.ShipCost)
	
	var gross float64
	for _, t := range trades {
		gross += t.GrossProfit
	}

	net := gross - risk*capital
	rate := 0.0
	if time > 0 {
		rate = net / time
	}

	return &RouteInfo{
		ProfitRate:    rate,
		Risk:          risk,
		Capital:       capital,
		TransportTime: time,
		GrossProfit:   gross,
		NetProfit:     net,
	}
}

func RouteOptimizer(trades []Trade, graph *Graph, ship Ship, legMetrics map[[2]int]*LegMetrics) *RoutePlan {
	if len(trades) == 0 {
		return &RoutePlan{Route: []RouteStep{}, OptimizedTrades: []Trade{}, Path: []int{}, RawOffsets: []int{}}
	}

	rankedTriplets := buildRankedTriplets(trades, ship.Location)
	tradesByPair := buildStationPairIndex(trades)

	if legMetrics == nil {
		legMetrics = BuildTradeLegMetrics(graph, ship.Location, trades)
	}

	var bestRate float64
	var bestInfo *RouteInfo
	var bestStations []int
	var bestTrades []Trade

	limit := MaxTradesToConsider
	if len(rankedTriplets) < limit {
		limit = len(rankedTriplets)
	}

	for _, trip := range rankedTriplets[:limit] {
		optimized := selectTrades(trip, tradesByPair, ship)
		if len(optimized) == 0 {
			continue
		}

		sLeg, sOk := legMetrics[[2]int{trip[0], trip[1]}]
		dLeg, dOk := legMetrics[[2]int{trip[1], trip[2]}]
		if !sOk || !dOk || sLeg == nil || dLeg == nil {
			continue
		}

		risk := sLeg.Risk + dLeg.Risk
		time := sLeg.Time + dLeg.Time

		locs := []int{trip[0], trip[1], trip[2]}
		info := buildRouteInfo(locs, optimized, ship, time, risk)
		if info == nil {
			continue
		}

		if info.ProfitRate > bestRate {
			bestRate = info.ProfitRate
			bestInfo = info
			bestStations = locs
			bestTrades = optimized
			log.Printf("New best profit rate: %.2f/hr", bestRate*3600)
		}
	}

	if bestStations == nil || bestTrades == nil {
		return &RoutePlan{Route: []RouteStep{}, OptimizedTrades: []Trade{}, Path: []int{}, RawOffsets: []int{}}
	}

	// Reconstruct path
	sRes := graph.ShortestPath(bestStations[0], bestStations[1])
	dRes := graph.ShortestPath(bestStations[1], bestStations[2])

	var path []int
	if len(sRes) > 0 {
		path = append(path, sRes[:len(sRes)-1]...)
		path = append(path, dRes...)
	} else {
		// fallback
		path = append(path, dRes...)
	}

	// Formatted route (this needs more detailed graph metadata merging, we'll build a simplified version)
	formatted, offsets := graph.FormattedRouteWithOffsets(path)

	// Set Actions
	actionsRoute := setActions(formatted, bestTrades)

	return &RoutePlan{
		Route:          actionsRoute,
		Info:           bestInfo,
		OptimizedTrades: bestTrades,
		Path:           path,
		RawOffsets:     offsets,
	}
}

func setActions(route []RouteStep, trades []Trade) []RouteStep {
	bought := make(map[int]bool)
	for _, t := range trades {
		for i := range route {
			if t.FromStation == route[i].LocationID {
				route[i].Actions = append(route[i].Actions, Action{
					ActionType: "buy",
					Item:       t.ItemName,
					TypeID:     t.TypeID,
					Quantity:   t.Quantity,
					Price:      t.FromPrice,
				})
				bought[t.TypeID] = true
			}
			
			if t.ToStation == route[i].LocationID && bought[t.TypeID] {
				route[i].Actions = append(route[i].Actions, Action{
					ActionType: "sell",
					Item:       t.ItemName,
					TypeID:     t.TypeID,
					Quantity:   t.Quantity,
					Price:      t.ToPrice,
				})
			}
		}
	}
	
	// Sort actions
	for i := range route {
		sort.Slice(route[i].Actions, func(a, b int) bool {
			al := route[i].Actions[a]
			bl := route[i].Actions[b]
			if al.ActionType != bl.ActionType {
				return al.ActionType == "sell" // sell comes before buy (0 vs 1 in python logic)
			}
			if al.Item != bl.Item {
				return al.Item < bl.Item
			}
			return al.Price < bl.Price
		})
	}
	
	return route
}