1import { assert, describe, it } from "@effect/vitest"
2import { Effect, Fiber, Option, Order, TxPriorityQueue } from "effect"
3
4describe("TxPriorityQueue", () => {
5 describe("constructors", () => {
6 it.effect("empty creates an empty queue", () =>
7 Effect.tx(Effect.gen(function*() {
8 const pq = yield* TxPriorityQueue.empty<number>(Order.Number)
9 const s = yield* TxPriorityQueue.size(pq)
10 assert.strictEqual(s, 0)
11 assert.isTrue(yield* TxPriorityQueue.isEmpty(pq))
12 })))
13
14 it.effect("fromIterable creates a sorted queue", () =>
15 Effect.tx(Effect.gen(function*() {
16 const pq = yield* TxPriorityQueue.fromIterable(Order.Number, [3, 1, 2])
17 const all = yield* TxPriorityQueue.toArray(pq)
18 assert.deepStrictEqual(all, [1, 2, 3])
19 })))
20
21 it.effect("fromIterable supports the curried call", () =>
22 Effect.tx(Effect.gen(function*() {
23 const pq = yield* TxPriorityQueue.fromIterable(Order.Number)([3, 1, 2])
24 const all = yield* TxPriorityQueue.toArray(pq)
25 assert.deepStrictEqual(all, [1, 2, 3])
26 })))
27
28 it.effect("make creates from variadic args", () =>
29 Effect.tx(Effect.gen(function*() {
30 const pq = yield* TxPriorityQueue.make(Order.Number)(5, 3, 1, 4, 2)
31 const all = yield* TxPriorityQueue.toArray(pq)
32 assert.deepStrictEqual(all, [1, 2, 3, 4, 5])
33 })))
34 })
35
36 describe("getters", () => {
37 it.effect("size returns number of elements", () =>
38 Effect.tx(Effect.gen(function*() {
39 const pq = yield* TxPriorityQueue.fromIterable(Order.Number, [1, 2, 3])
40 assert.strictEqual(yield* TxPriorityQueue.size(pq), 3)
41 })))
42
43 it.effect("isEmpty/isNonEmpty", () =>
44 Effect.tx(Effect.gen(function*() {
45 const pq = yield* TxPriorityQueue.empty<number>(Order.Number)
46 assert.isTrue(yield* TxPriorityQueue.isEmpty(pq))
47 assert.isFalse(yield* TxPriorityQueue.isNonEmpty(pq))
48 yield* TxPriorityQueue.offer(pq, 1)
49 assert.isFalse(yield* TxPriorityQueue.isEmpty(pq))
50 assert.isTrue(yield* TxPriorityQueue.isNonEmpty(pq))
51 })))
52
53 it.effect("peek returns smallest without removing", () =>
54 Effect.tx(Effect.gen(function*() {
55 const pq = yield* TxPriorityQueue.fromIterable(Order.Number, [3, 1, 2])
56 const top = yield* TxPriorityQueue.peek(pq)
57 assert.strictEqual(top, 1)
58 assert.strictEqual(yield* TxPriorityQueue.size(pq), 3)
59 })))
60
61 it.effect("peekOption returns None when empty", () =>
62 Effect.tx(Effect.gen(function*() {
63 const pq = yield* TxPriorityQueue.empty<number>(Order.Number)
64 const result = yield* TxPriorityQueue.peekOption(pq)
65 assert.isTrue(Option.isNone(result))
66 })))
67
68 it.effect("peekOption returns Some when non-empty", () =>
69 Effect.tx(Effect.gen(function*() {
70 const pq = yield* TxPriorityQueue.fromIterable(Order.Number, [3, 1])
71 const result = yield* TxPriorityQueue.peekOption(pq)
72 assert.isTrue(Option.isSome(result))
73 if (Option.isSome(result)) {
74 assert.strictEqual(result.value, 1)
75 }
76 })))
77 })
78
79 describe("mutations", () => {
80 it.effect("offer + take returns elements in priority order", () =>
81 Effect.tx(Effect.gen(function*() {
82 const pq = yield* TxPriorityQueue.empty<number>(Order.Number)
83 yield* TxPriorityQueue.offer(pq, 3)
84 yield* TxPriorityQueue.offer(pq, 1)
85 yield* TxPriorityQueue.offer(pq, 2)
86 assert.strictEqual(yield* TxPriorityQueue.take(pq), 1)
87 assert.strictEqual(yield* TxPriorityQueue.take(pq), 2)
88 assert.strictEqual(yield* TxPriorityQueue.take(pq), 3)
89 })))
90
91 it.effect("duplicate priorities are all returned", () =>
92 Effect.tx(Effect.gen(function*() {
93 const pq = yield* TxPriorityQueue.fromIterable(Order.Number, [2, 1, 2, 1, 3])
94 const all = yield* TxPriorityQueue.takeAll(pq)
95 assert.deepStrictEqual(all, [1, 1, 2, 2, 3])
96 })))
97
98 it.effect("take on empty retries until offer", () =>
99 Effect.tx(Effect.gen(function*() {
100 const pq = yield* TxPriorityQueue.empty<number>(Order.Number)
101 const fiber = yield* Effect.forkChild(TxPriorityQueue.take(pq))
102 yield* TxPriorityQueue.offer(pq, 42)
103 const value = yield* Fiber.join(fiber)
104 assert.strictEqual(value, 42)
105 })))
106
107 it.effect("takeOption returns None when empty", () =>
108 Effect.tx(Effect.gen(function*() {
109 const pq = yield* TxPriorityQueue.empty<number>(Order.Number)
110 const result = yield* TxPriorityQueue.takeOption(pq)
111 assert.isTrue(Option.isNone(result))
112 })))
113
114 it.effect("takeUpTo returns min(n, size) elements in order", () =>
115 Effect.tx(Effect.gen(function*() {
116 const pq = yield* TxPriorityQueue.fromIterable(Order.Number, [5, 3, 1, 4, 2])
117 const top3 = yield* TxPriorityQueue.takeUpTo(pq, 3)
118 assert.deepStrictEqual(top3, [1, 2, 3])
119 assert.strictEqual(yield* TxPriorityQueue.size(pq), 2)
120 })))
121
122 it.effect("takeUpTo with n > size returns all", () =>
123 Effect.tx(Effect.gen(function*() {
124 const pq = yield* TxPriorityQueue.fromIterable(Order.Number, [2, 1])
125 const all = yield* TxPriorityQueue.takeUpTo(pq, 10)
126 assert.deepStrictEqual(all, [1, 2])
127 assert.strictEqual(yield* TxPriorityQueue.size(pq), 0)
128 })))
129
130 it.effect("offerAll inserts multiple elements", () =>
131 Effect.tx(Effect.gen(function*() {
132 const pq = yield* TxPriorityQueue.empty<number>(Order.Number)
133 yield* TxPriorityQueue.offerAll(pq, [3, 1, 2])
134 const all = yield* TxPriorityQueue.toArray(pq)
135 assert.deepStrictEqual(all, [1, 2, 3])
136 })))
137
138 it.effect("offerAll does not compare every queued element for one new value", () =>
139 Effect.tx(Effect.gen(function*() {
140 let comparisons = 0
141 const order: Order.Order<number> = (a, b) => {
142 comparisons++
143 return Order.Number(a, b)
144 }
145 const pq = yield* TxPriorityQueue.fromIterable(order, Array.from({ length: 128 }, (_, i) => i * 2))
146 comparisons = 0
147 yield* TxPriorityQueue.offerAll(pq, [127])
148 assert.isBelow(comparisons, 32)
149 assert.deepStrictEqual(yield* TxPriorityQueue.toArray(pq), [
150 ...Array.from({ length: 64 }, (_, i) => i * 2),
151 127,
152 ...Array.from({ length: 64 }, (_, i) => (i + 64) * 2)
153 ])
154 })))
155
156 it.effect("offerAll avoids repeated full-range searches for an interleaved batch", () =>
157 Effect.tx(Effect.gen(function*() {
158 let comparisons = 0
159 const order: Order.Order<number> = (a, b) => {
160 comparisons++
161 return Order.Number(a, b)
162 }
163 const queued = Array.from({ length: 256 }, (_, i) => i * 2)
164 const incoming = Array.from({ length: 256 }, (_, i) => i * 2 + 1)
165 const pq = yield* TxPriorityQueue.fromIterable(order, queued)
166 comparisons = 0
167 yield* TxPriorityQueue.offerAll(pq, incoming)
168 assert.isBelow(comparisons, 900)
169 assert.deepStrictEqual(yield* TxPriorityQueue.toArray(pq), Array.from({ length: 512 }, (_, i) => i))
170 })))
171 })
172
173 describe("filtering", () => {
174 it.effect("removeIf removes matching elements", () =>
175 Effect.tx(Effect.gen(function*() {
176 const pq = yield* TxPriorityQueue.fromIterable(Order.Number, [1, 2, 3, 4, 5])
177 yield* TxPriorityQueue.removeIf(pq, (n) => n % 2 === 0)
178 const all = yield* TxPriorityQueue.takeAll(pq)
179 assert.deepStrictEqual(all, [1, 3, 5])
180 })))
181
182 it.effect("retainIf keeps only matching elements", () =>
183 Effect.tx(Effect.gen(function*() {
184 const pq = yield* TxPriorityQueue.fromIterable(Order.Number, [1, 2, 3, 4, 5])
185 yield* TxPriorityQueue.retainIf(pq, (n) => n % 2 === 0)
186 const all = yield* TxPriorityQueue.takeAll(pq)
187 assert.deepStrictEqual(all, [2, 4])
188 })))
189 })
190
191 describe("guards", () => {
192 it.effect("isTxPriorityQueue", () =>
193 Effect.tx(Effect.gen(function*() {
194 const pq = yield* TxPriorityQueue.empty<number>(Order.Number)
195 assert.isTrue(TxPriorityQueue.isTxPriorityQueue(pq))
196 assert.isFalse(TxPriorityQueue.isTxPriorityQueue(null))
197 assert.isFalse(TxPriorityQueue.isTxPriorityQueue({ some: "object" }))
198 assert.isFalse(TxPriorityQueue.isTxPriorityQueue([1, 2, 3]))
199 })))
200 })
201
202 describe("concurrency", () => {
203 it.effect("concurrent offer and take", () =>
204 Effect.tx(Effect.gen(function*() {
205 const pq = yield* TxPriorityQueue.empty<number>(Order.Number)
206 const fiber = yield* Effect.forkChild(
207 Effect.all([
208 TxPriorityQueue.take(pq),
209 TxPriorityQueue.take(pq),
210 TxPriorityQueue.take(pq)
211 ])
212 )
213 yield* TxPriorityQueue.offerAll(pq, [3, 1, 2])
214 const results = yield* Fiber.join(fiber)
215 assert.deepStrictEqual(results, [1, 2, 3])
216 })))
217 })
218
219 describe("custom ordering", () => {
220 it.effect("reverse order (max-first)", () =>
221 Effect.tx(Effect.gen(function*() {
222 const reverseNumber: Order.Order<number> = (a, b) => (a < b ? 1 : a > b ? -1 : 0)
223 const pq = yield* TxPriorityQueue.fromIterable(reverseNumber, [1, 3, 2])
224 const first = yield* TxPriorityQueue.take(pq)
225 assert.strictEqual(first, 3)
226 })))
227 })
228})