-
Notifications
You must be signed in to change notification settings - Fork 20
/
locations.go
215 lines (180 loc) · 6.42 KB
/
locations.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
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
package utils
import (
"encoding/json"
"fmt"
"regexp"
"strings"
)
// LocationID is the unique identifier for each location, e.g. an OSM ID
type LocationID string
// LocationLevel is a numeric level, e.g. 0 = country, 1 = state
type LocationLevel int
// Location represents a single Location
type Location struct {
id LocationID
level LocationLevel
name string
aliases []string
parent *Location
children []*Location
}
// NewLocation creates a new location object
func NewLocation(id LocationID, level LocationLevel, name string) *Location {
return &Location{id: id, level: level, name: name}
}
func (b *Location) ID() LocationID { return b.id }
func (b *Location) Level() LocationLevel { return b.level }
func (b *Location) Name() string { return b.name }
func (b *Location) Aliases() []string { return b.aliases }
func (b *Location) Parent() *Location { return b.parent }
func (b *Location) Children() []*Location { return b.children }
type locationVisitor func(Location *Location)
func (b *Location) visit(visitor locationVisitor) {
visitor(b)
for _, child := range b.children {
child.visit(visitor)
}
}
// for each level, we maintain some maps for faster lookups
type levelLookup struct {
byID map[LocationID]*Location
byName map[string][]*Location
}
func (l *levelLookup) setIDLookup(id LocationID, location *Location) {
l.byID[id] = location
}
func (l *levelLookup) addNameLookup(name string, location *Location) {
name = strings.ToLower(name)
l.byName[name] = append(l.byName[name], location)
}
// LocationHierarchy is a hierarical tree of locations
type LocationHierarchy struct {
root *Location
levelLookups []*levelLookup
}
// NewLocationHierarchy cretes a new location hierarchy
func NewLocationHierarchy(root *Location, numLevels int) *LocationHierarchy {
s := &LocationHierarchy{
root: root,
levelLookups: make([]*levelLookup, numLevels),
}
for l := 0; l < numLevels; l++ {
s.levelLookups[l] = &levelLookup{
byID: make(map[LocationID]*Location),
byName: make(map[string][]*Location),
}
}
root.visit(func(Location *Location) { s.addLookups(Location) })
return s
}
func (s *LocationHierarchy) addLookups(location *Location) {
lookups := s.levelLookups[int(location.level)]
lookups.setIDLookup(location.id, location)
lookups.addNameLookup(location.name, location)
// include any aliases as names too
for _, alias := range location.aliases {
lookups.addNameLookup(alias, location)
}
}
// FindByID looks for a location in the hierarchy with the given level and ID
func (s *LocationHierarchy) FindByID(id LocationID, level LocationLevel) *Location {
if int(level) < len(s.levelLookups) {
return s.levelLookups[int(level)].byID[id]
}
return nil
}
// FindByName looks for all locations in the hierarchy with the given level and name or alias
func (s *LocationHierarchy) FindByName(name string, level LocationLevel, parent *Location) []*Location {
if int(level) < len(s.levelLookups) {
matches, found := s.levelLookups[int(level)].byName[strings.ToLower(name)]
if found {
// if a parent is specified, filter the matches by it
if parent != nil {
withParent := make([]*Location, 0)
for m := range matches {
if matches[m].parent == parent {
withParent = append(withParent, matches[m])
}
}
return withParent
}
return matches
}
}
return []*Location{}
}
// FindLocations returns locations with the matching name (case-insensitive), level and parent (optional)
func FindLocations(env Environment, name string, level LocationLevel, parent *Location) ([]*Location, error) {
locations, err := env.Locations()
if err != nil {
return nil, err
}
if locations == nil {
return nil, fmt.Errorf("can't find locations in enviroment which is not location enabled")
}
return locations.FindByName(name, level, parent), nil
}
// FindLocationsFuzzy returns matching locations like FindLocations but attempts the following strategies
// to find locations:
// 1. Exact match
// 2. Match with punctuation removed
// 3. Split input into words and try to match each word
// 4. Try to match pairs of words
func FindLocationsFuzzy(env Environment, text string, level LocationLevel, parent *Location) ([]*Location, error) {
// try matching name exactly
if locations, err := FindLocations(env, text, level, parent); len(locations) > 0 || err != nil {
return locations, err
}
// try with punctuation removed
stripped := strings.TrimSpace(regexp.MustCompile(`\W+`).ReplaceAllString(text, ""))
if locations, err := FindLocations(env, stripped, level, parent); len(locations) > 0 || err != nil {
return locations, err
}
// try on each tokenized word
words := regexp.MustCompile(`\W+`).Split(text, -1)
for _, word := range words {
if locations, err := FindLocations(env, word, level, parent); len(locations) > 0 || err != nil {
return locations, err
}
}
// try with each pair of words
for w := 0; w < len(words)-1; w++ {
wordPair := strings.Join(words[w:w+2], " ")
if locations, err := FindLocations(env, wordPair, level, parent); len(locations) > 0 || err != nil {
return locations, err
}
}
return []*Location{}, nil
}
//------------------------------------------------------------------------------------------
// JSON Encoding / Decoding
//------------------------------------------------------------------------------------------
type locationEnvelope struct {
ID LocationID `json:"id"`
Name string `json:"name" validate:"required"`
Aliases []string `json:"aliases,omitempty"`
Children []*locationEnvelope `json:"children,omitempty"`
}
func locationFromEnvelope(envelope *locationEnvelope, currentLevel LocationLevel, parent *Location) *Location {
location := &Location{
id: envelope.ID,
level: LocationLevel(currentLevel),
name: envelope.Name,
aliases: envelope.Aliases,
parent: parent,
}
location.children = make([]*Location, len(envelope.Children))
for c := range envelope.Children {
location.children[c] = locationFromEnvelope(envelope.Children[c], currentLevel+1, location)
}
return location
}
// ReadLocationHierarchy reads a location hierarchy from the given JSON
func ReadLocationHierarchy(data json.RawMessage) (*LocationHierarchy, error) {
var le locationEnvelope
if err := UnmarshalAndValidate(data, &le, "location"); err != nil {
return nil, err
}
root := locationFromEnvelope(&le, LocationLevel(0), nil)
return NewLocationHierarchy(root, 4), nil
}