1. 1
2. 2
3. 3
4. 4
5. 5
6. 6
7. 7
8. 8
9. 9
10. 10
11. 11
12. 12
13. 13
14. 14
15. 15
16. 16
17. 17
18. 18
19. 19
20. 20
21. 21
22. 22
23. 23
24. 24
25. 25
26. 26
27. 27
28. 28
29. 29
30. 30
31. 31
32. 32
33. 33
34. 34
35. 35
36. 36
37. 37
38. 38
39. 39
40. 40
41. 41
42. 42
43. 43
44. 44
45. 45
46. 46
47. 47
48. 48
49. 49
50. 50
51. 51
52. 52
53. 53
54. 54
55. 55
56. 56
57. 57
58. 58
59. 59
60. 60
61. 61
62. 62
63. 63
64. 64
65. 65
66. 66
67. 67
68. 68
69. 69
70. 70
71. 71
72. 72
73. 73
74. 74
75. 75
76. 76
77. 77
78. 78
79. 79
80. 80
81. 81
82. 82
83. 83
84. 84
85. 85
86. 86
87. 87
88. 88
89. 89
90. 90
91. 91
92. 92
93. 93
94. 94
95. 95
96. 96
97. 97
98. 98
99. 99
100. 100
101. 101

package roaring

import "container/heap"

/////////////
// The priorityQueue is used to keep Bitmaps sorted.
////////////

type item struct {
	value *Bitmap
	index int
}

type priorityQueue []*item

func (pq priorityQueue) Len() int { return len(pq) }

func (pq priorityQueue) Less(i, j int) bool {
	return pq[i].value.GetSizeInBytes() < pq[j].value.GetSizeInBytes()
}

func (pq priorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = i
	pq[j].index = j
}

func (pq *priorityQueue) Push(x interface{}) {
	n := len(*pq)
	item := x.(*item)
	item.index = n
	*pq = append(*pq, item)
}

func (pq *priorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	item.index = -1 // for safety
	*pq = old[0 : n-1]
	return item
}

func (pq *priorityQueue) update(item *item, value *Bitmap) {
	item.value = value
	heap.Fix(pq, item.index)
}

/////////////
// The containerPriorityQueue is used to keep the containers of various Bitmaps sorted.
////////////

type containeritem struct {
	value    *Bitmap
	keyindex int
	index    int
}

type containerPriorityQueue []*containeritem

func (pq containerPriorityQueue) Len() int { return len(pq) }

func (pq containerPriorityQueue) Less(i, j int) bool {
	k1 := pq[i].value.highlowcontainer.getKeyAtIndex(pq[i].keyindex)
	k2 := pq[j].value.highlowcontainer.getKeyAtIndex(pq[j].keyindex)
	if k1 != k2 {
		return k1 < k2
	}
	c1 := pq[i].value.highlowcontainer.getContainerAtIndex(pq[i].keyindex)
	c2 := pq[j].value.highlowcontainer.getContainerAtIndex(pq[j].keyindex)

	return c1.getCardinality() > c2.getCardinality()
}

func (pq containerPriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = i
	pq[j].index = j
}

func (pq *containerPriorityQueue) Push(x interface{}) {
	n := len(*pq)
	item := x.(*containeritem)
	item.index = n
	*pq = append(*pq, item)
}

func (pq *containerPriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	item.index = -1 // for safety
	*pq = old[0 : n-1]
	return item
}

//func (pq *containerPriorityQueue) update(item *containeritem, value *Bitmap, keyindex int) {
//	item.value = value
//	item.keyindex = keyindex
//	heap.Fix(pq, item.index)
//}