Use multiset-like data structure for storing headers

This looks like an overkill because it is one. The space and time
complexity of the multiset structure is rather bad. At this point it
stays mostly because of sunk cost fallacy. It will provide OK
abstraction layer to build the rest of this forsaken project.

1 files changed, 168 insertions, 0 deletions

diff --git a/spec/multiset_spec.lua b/spec/multiset_spec.lua
new file mode 100644
index 0000000..7639066
--- /dev/null
+++ b/spec/multiset_spec.lua
@@ -0,0 +1,168 @@
+local multiset = require "headers.multiset"
+
+
+describe("Multisets can be created", function()
+	it("without errors", function()
+		assert.has_no.errors(function()
+			local _ = multiset.new()
+		end)
+	end)
+end)
+
+
+describe("Size of multiset", function()
+	local set
+
+	setup(function()
+		set = multiset.new()
+	end)
+
+	it("can be checked with method", function()
+		assert.is_not_nil(set:size())
+	end)
+
+	it("can be checked with operator", function()
+		assert.is_not_nil(#set)
+	end)
+
+	it("is zero after creation", function()
+		assert.are.equal(0, #set)
+	end)
+end)
+
+
+describe("Values", function()
+	randomize(false)
+	local set
+
+	setup(function()
+		set = multiset.new()
+	end)
+
+	it("are not present before insertion", function()
+		assert.is_false(set:has"will-be-removed")
+		assert.is_false(set:has"will-stay")
+		assert.is_false(set:has"never-inserted")
+	end)
+
+	it("were not tracked before insertion", function()
+		assert.is_false(set:had"will-be-removed")
+		assert.is_false(set:had"will-stay")
+		assert.is_false(set:had"never-inserted")
+	end)
+
+	it("can be inserted", function()
+		assert.has_no.errors(function()
+			set:add"will-be-removed"
+			set:add"will-stay"
+		end)
+	end)
+
+	it("are present after insertion", function()
+		assert.is_true(set:has"will-be-removed")
+		assert.is_true(set:has"will-stay")
+		assert.is_false(set:has"never-inserted")
+	end)
+
+	it("are tracked after insertion", function()
+		assert.is_true(set:had"will-be-removed")
+		assert.is_true(set:had"will-stay")
+		assert.is_false(set:had"never-inserted")
+	end)
+
+	it("are counted in size", function()
+		assert.are.equal(2, #set)
+	end)
+
+	it("can be removed", function()
+		assert.has_no.errors(function()
+			set:remove"will-be-removed"
+		end)
+	end)
+
+	it("are no longer present after removal", function()
+		assert.is_false(set:has"will-be-removed")
+		assert.is_true(set:has"will-stay")
+		assert.is_false(set:has"never-inserted")
+	end)
+
+	it("are still tracked after removal", function()
+		assert.is_true(set:had"will-be-removed")
+		assert.is_true(set:had"will-stay")
+		assert.is_false(set:had"never-inserted")
+	end)
+
+	it("are not counted after removal", function()
+		assert.are.equal(1, #set)
+	end)
+end)
+
+
+describe("Iterator", function()
+	randomize(false)
+	local set
+
+	setup(function()
+		set = multiset.new()
+		set:add"a"
+		set:add"b"
+		set:add"c"
+		set:add"d"
+	end)
+
+	it("preserves order", function()
+		local items = {}
+		for value in set:all() do
+			table.insert(items, value)
+		end
+		assert.are.same({"a", "b", "c", "d"}, items)
+	end)
+
+	it("does not include past values", function()
+		set:remove"c"
+		set:add"e"
+		local items = {}
+		for value in set:all() do
+			table.insert(items, value)
+		end
+		assert.are.same({"a", "b", "d", "e"}, items)
+	end)
+
+	it("keeps the order of re-added values", function()
+		set:add"c"
+		local items = {}
+		for value in set:all() do
+			table.insert(items, value)
+		end
+		assert.are.same({"a", "b", "c", "d", "e"}, items)
+	end)
+end)
+
+
+describe("Clones", function()
+	randomize(false)
+	local a
+	local b
+
+	setup(function()
+		a = multiset.new()
+		a:add"set-in-a"
+	end)
+
+	it("can be created", function()
+		assert.has_no.errors(function()
+			b = a:clone()
+		end)
+		assert.is_not_nil(b)
+	end)
+
+	it("do not interfere with their original", function()
+		assert.is_true(a:has"set-in-a")
+		assert.is_true(b:has"set-in-a")
+		assert.is_false(a:has"set-in-b")
+		assert.is_false(b:has"set-in-b")
+		b:add"set-in-b"
+		assert.is_false(a:has"set-in-b")
+		assert.is_true(b:has"set-in-b")
+	end)
+end)