Software /
code /
prosody
Annotate
spec/util_indexedbheap_spec.lua @ 13238:26327eac56dc
util.datamanager: Always reset index after list shift
Shifting the index does not work reliably yet, better to rebuild it from
scratch. Since there is minimal parsing involved in that, it should be
more efficient anyway.
author | Kim Alvefur <zash@zash.se> |
---|---|
date | Sat, 22 Jul 2023 14:02:01 +0200 |
parent | 11116:d334f2bebe55 |
rev | line source |
---|---|
11115
7d4c292f178e
util.indexedbheap: Fix heap datastructure corruption in :reschedule(smaller_value)
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
1 local ibh = require"util.indexedbheap"; |
7d4c292f178e
util.indexedbheap: Fix heap datastructure corruption in :reschedule(smaller_value)
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
2 |
7d4c292f178e
util.indexedbheap: Fix heap datastructure corruption in :reschedule(smaller_value)
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
3 local function verify_heap_property(priorities) |
7d4c292f178e
util.indexedbheap: Fix heap datastructure corruption in :reschedule(smaller_value)
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
4 for k in ipairs(priorities) do |
7d4c292f178e
util.indexedbheap: Fix heap datastructure corruption in :reschedule(smaller_value)
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
5 local parent = priorities[k]; |
7d4c292f178e
util.indexedbheap: Fix heap datastructure corruption in :reschedule(smaller_value)
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
6 local childA = priorities[2*k]; |
7d4c292f178e
util.indexedbheap: Fix heap datastructure corruption in :reschedule(smaller_value)
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
7 local childB = priorities[2*k+1]; |
7d4c292f178e
util.indexedbheap: Fix heap datastructure corruption in :reschedule(smaller_value)
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
8 -- print("-", parent, childA, childB) |
7d4c292f178e
util.indexedbheap: Fix heap datastructure corruption in :reschedule(smaller_value)
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
9 assert(childA == nil or childA > parent, "heap property violated"); |
7d4c292f178e
util.indexedbheap: Fix heap datastructure corruption in :reschedule(smaller_value)
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
10 assert(childB == nil or childB > parent, "heap property violated"); |
7d4c292f178e
util.indexedbheap: Fix heap datastructure corruption in :reschedule(smaller_value)
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
11 end |
7d4c292f178e
util.indexedbheap: Fix heap datastructure corruption in :reschedule(smaller_value)
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
12 end |
7d4c292f178e
util.indexedbheap: Fix heap datastructure corruption in :reschedule(smaller_value)
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
13 |
7d4c292f178e
util.indexedbheap: Fix heap datastructure corruption in :reschedule(smaller_value)
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
14 local h |
7d4c292f178e
util.indexedbheap: Fix heap datastructure corruption in :reschedule(smaller_value)
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
15 setup(function () |
7d4c292f178e
util.indexedbheap: Fix heap datastructure corruption in :reschedule(smaller_value)
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
16 h = ibh.create(); |
7d4c292f178e
util.indexedbheap: Fix heap datastructure corruption in :reschedule(smaller_value)
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
17 end) |
7d4c292f178e
util.indexedbheap: Fix heap datastructure corruption in :reschedule(smaller_value)
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
18 describe("util.indexedbheap", function () |
7d4c292f178e
util.indexedbheap: Fix heap datastructure corruption in :reschedule(smaller_value)
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
19 it("item can be moved from end to top", function () |
7d4c292f178e
util.indexedbheap: Fix heap datastructure corruption in :reschedule(smaller_value)
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
20 verify_heap_property(h); |
7d4c292f178e
util.indexedbheap: Fix heap datastructure corruption in :reschedule(smaller_value)
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
21 h:insert("a", 1); |
7d4c292f178e
util.indexedbheap: Fix heap datastructure corruption in :reschedule(smaller_value)
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
22 verify_heap_property(h); |
7d4c292f178e
util.indexedbheap: Fix heap datastructure corruption in :reschedule(smaller_value)
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
23 h:insert("b", 2); |
7d4c292f178e
util.indexedbheap: Fix heap datastructure corruption in :reschedule(smaller_value)
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
24 verify_heap_property(h); |
7d4c292f178e
util.indexedbheap: Fix heap datastructure corruption in :reschedule(smaller_value)
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
25 h:insert("c", 3); |
7d4c292f178e
util.indexedbheap: Fix heap datastructure corruption in :reschedule(smaller_value)
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
26 verify_heap_property(h); |
7d4c292f178e
util.indexedbheap: Fix heap datastructure corruption in :reschedule(smaller_value)
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
27 local id = h:insert("*", 10); |
7d4c292f178e
util.indexedbheap: Fix heap datastructure corruption in :reschedule(smaller_value)
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
28 verify_heap_property(h); |
7d4c292f178e
util.indexedbheap: Fix heap datastructure corruption in :reschedule(smaller_value)
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
29 h:reprioritize(id, 0); |
7d4c292f178e
util.indexedbheap: Fix heap datastructure corruption in :reschedule(smaller_value)
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
30 verify_heap_property(h); |
7d4c292f178e
util.indexedbheap: Fix heap datastructure corruption in :reschedule(smaller_value)
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
31 assert.same({ 0, "*", id }, { h:pop() }); |
7d4c292f178e
util.indexedbheap: Fix heap datastructure corruption in :reschedule(smaller_value)
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
32 end) |
7d4c292f178e
util.indexedbheap: Fix heap datastructure corruption in :reschedule(smaller_value)
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
33 end); |