forked from stellar/go
-
Notifications
You must be signed in to change notification settings - Fork 0
/
path.go
151 lines (123 loc) · 3.11 KB
/
path.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
package simplepath
import (
"bytes"
"fmt"
"github.com/cowry-network/go/services/horizon/internal/db2/core"
"github.com/cowry-network/go/xdr"
)
// pathNode represents a path as a linked list pointing from source to destination
type pathNode struct {
Asset xdr.Asset
Tail *pathNode
Q *core.Q
CachedCost *xdr.Int64
Depth uint
}
func (p *pathNode) String() string {
if p == nil {
return ""
}
var out bytes.Buffer
fmt.Fprintf(&out, "%v", p.Asset)
cur := p.Tail
for cur != nil {
fmt.Fprintf(&out, " -> %v", cur.Asset)
cur = cur.Tail
}
return out.String()
}
// Destination returns the destination of the pathNode
func (p *pathNode) Destination() xdr.Asset {
cur := p
for cur.Tail != nil {
cur = cur.Tail
}
return cur.Asset
}
// IsOnPath returns true if a given asset is in the path.
func (p *pathNode) IsOnPath(asset xdr.Asset) bool {
cur := p
for cur.Tail != nil {
if asset.Equals(cur.Asset) {
return true
}
cur = cur.Tail
}
if asset.Equals(cur.Asset) {
return true
}
return false
}
// Source returns the source asset in the pathNode
func (p *pathNode) Source() xdr.Asset {
// the destination for path is the head of the linked list
return p.Asset
}
// Path returns the path of the list excluding the source and destination assets
func (p *pathNode) Path() []xdr.Asset {
path := p.Flatten()
if len(path) < 2 {
return nil
}
// return the flattened slice without the first and last elements
// which are the source and the destination assets
return path[1 : len(path)-1]
}
// Cost computes the units of the source asset needed to send the amount in the destination asset
// This is an expensive operation so callers should reuse the result where appropriate
func (p *pathNode) Cost(amount xdr.Int64) (xdr.Int64, error) {
if p.Tail == nil {
return amount, nil
}
if p.CachedCost != nil {
return *p.CachedCost, nil
}
// The first element of the current path is the current source asset.
// The last element (with `Tail` = nil) of the current path is the destination
// asset. To make the calculations correct we start by selling destination
// asset to the second from the end asset and continue until we reach the current
// source asset.
cur := p
stack := make([]*pathNode, 0, p.Depth)
for cur.Tail != nil {
stack = append(stack, cur)
cur = cur.Tail
}
var err error
result := amount
for i := len(stack) - 1; i >= 0; i-- {
cur = stack[i]
if cur.CachedCost != nil {
result = *cur.CachedCost
continue
}
ob := cur.OrderBook()
result, err = ob.CostToConsumeLiquidity(result)
if err != nil {
return result, err
}
}
// Cache the result
cur.CachedCost = &result
return result, nil
}
func (p *pathNode) OrderBook() *orderBook {
if p.Tail == nil {
return nil
}
return &orderBook{
Selling: p.Tail.Asset, // offer is selling this asset
Buying: p.Asset, // offer is buying this asset
Q: p.Q,
}
}
// Flatten walks the list and returns a slice of assets
func (p *pathNode) Flatten() []xdr.Asset {
result := []xdr.Asset{}
cur := p
for cur != nil {
result = append(result, cur.Asset)
cur = cur.Tail
}
return result
}