1 // Copyright 2020 Google Inc. All rights reserved. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 package s2 16 17 import "container/heap" 18 19 // A queryQueueEntry stores CellIDs and distance from a target. It is used by the 20 // different S2 Query types to efficiently build their internal priority queue 21 // in the optimized algorithm implementations. 22 type queryQueueEntry struct { 23 // A lower bound on the distance from the target to ID. This is the key 24 // of the priority queue. 25 distance distance 26 27 // The cell being queued. 28 id CellID 29 30 // If the CellID belongs to a ShapeIndex, this field stores the 31 // corresponding ShapeIndexCell. Otherwise ID is a proper ancestor of 32 // one or more ShapeIndexCells and this field stores is nil. 33 indexCell *ShapeIndexCell 34 } 35 36 // queryQueue is used by the optimized algorithm to maintain a priority queue of 37 // unprocessed CellIDs, sorted in increasing order of distance from the target. 38 type queryQueue struct { 39 queue queryPQ 40 } 41 42 // newQueryQueue returns a new initialized queryQueue. 43 func newQueryQueue() *queryQueue { 44 q := &queryQueue{ 45 queue: make(queryPQ, 0), 46 } 47 heap.Init(&q.queue) 48 return q 49 } 50 51 // push adds the given entry to the top of this queue. 52 func (q *queryQueue) push(e *queryQueueEntry) { 53 heap.Push(&q.queue, e) 54 } 55 56 // pop returns the top element of this queue. 57 func (q *queryQueue) pop() *queryQueueEntry { 58 return heap.Pop(&q.queue).(*queryQueueEntry) 59 } 60 61 func (q *queryQueue) size() int { 62 return q.queue.Len() 63 } 64 65 func (q *queryQueue) reset() { 66 q.queue = q.queue[:0] 67 } 68 69 // queryPQ is a priority queue that implements the heap interface. 70 type queryPQ []*queryQueueEntry 71 72 func (q queryPQ) Len() int { return len(q) } 73 func (q queryPQ) Less(i, j int) bool { 74 return q[i].distance.less(q[j].distance) 75 } 76 77 // Swap swaps the two entries. 78 func (q queryPQ) Swap(i, j int) { 79 q[i], q[j] = q[j], q[i] 80 } 81 82 // Push adds the given entry to the queue. 83 func (q *queryPQ) Push(x any) { 84 item := x.(*queryQueueEntry) 85 *q = append(*q, item) 86 } 87 88 // Pop returns the top element of the queue. 89 func (q *queryPQ) Pop() any { 90 item := (*q)[len(*q)-1] 91 *q = (*q)[:len(*q)-1] 92 return item 93 } 94