-
Notifications
You must be signed in to change notification settings - Fork 92
/
priority_queue.go
112 lines (93 loc) · 2.51 KB
/
priority_queue.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
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package merge
import (
"container/heap"
)
import (
"github.com/arana-db/arana/pkg/proto"
)
type PriorityQueue struct {
results []*MergeRows
orderByItems []OrderByItem
}
type OrderByItem struct {
Column string
Desc bool
}
func NewPriorityQueue(rows []*MergeRows, orderByItems []OrderByItem) PriorityQueue {
pq := PriorityQueue{
results: rows,
orderByItems: orderByItems,
}
heap.Init(&pq)
return pq
}
func (pq *PriorityQueue) Len() int {
return len(pq.results)
}
func (pq *PriorityQueue) Less(i, j int) bool {
for _, item := range pq.orderByItems {
rowi := pq.results[i].GetCurrentRow().(proto.KeyedRow)
rowj := pq.results[j].GetCurrentRow().(proto.KeyedRow)
val1, _ := rowi.Get(item.Column)
val2, _ := rowj.Get(item.Column)
var c int
switch {
case val1 == nil && val2 == nil:
case val1 == nil && val2 != nil:
// NULL is less than anything
c = -1
case val1 != nil && val2 == nil:
// NULL is less than anything
c = 1
case val1 != nil && val2 != nil:
c = proto.CompareValue(val1, val2)
}
if c == 0 {
continue
}
if item.Desc {
c *= -1
}
return c < 0
}
return false
}
func (pq *PriorityQueue) Swap(i, j int) {
pq.results[i], pq.results[j] = pq.results[j], pq.results[i]
}
func (pq *PriorityQueue) Push(x interface{}) {
item := x.(*MergeRows)
pq.results = append(pq.results, item)
pq.update()
}
func (pq *PriorityQueue) Pop() interface{} {
old := *pq
n := len(old.results)
item := old.results[n-1]
pq.results = old.results[0 : n-1]
pq.update()
return item
}
func (pq *PriorityQueue) Peek() interface{} {
return pq.results[0]
}
// update modifies the priority and value of an Item in the queue.
func (pq *PriorityQueue) update() {
heap.Fix(pq, len(pq.results)-1)
}