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.

6 files changed, 354 insertions, 57 deletions

diff --git a/headers.lua b/headers.lua
index 972b360..8726615 100755
--- a/headers.lua
+++ b/headers.lua
@@ -5,13 +5,13 @@ Prints list of headers from a standard or available standards
 	<selection>  (optional string)  Standard to display headers for
 ]]
 local dir = require "pl.dir"
-local parse = require "headers.parser"
+local parser = require "headers.parser".new()
 local definitions = dir.getfiles(args.d, "*.lua")
 for _, filename in pairs(definitions) do
 	local handle = io.open(filename)
 	local data = handle:read("a")
 	handle:close()
-	if parse(data, args.selection) then
+	if parser:parse(data, args.selection) then
 		return  -- interface is yet to be properly defined, this allows only for first-result queries
 	end
 end
diff --git a/headers/definition.lua b/headers/definition.lua
index 82ce3b5..33c5143 100644
--- a/headers/definition.lua
+++ b/headers/definition.lua
@@ -1,6 +1,8 @@
---- Builds a definition parser that binds to a *private* object that implements +3,+41/private:/ callbacks.
-local
-function build (private)
+local definition = {}
+
+
+--- Builds a definition parser environment that binds to a *private* object that implements +3,+41/private:/ callbacks.
+function definition.new (private)
 	local public = {}
 
 	--- scheme "headers/1"
@@ -10,20 +12,28 @@ function build (private)
 		end
 	end
 
-	--- aliases "Formal Name" {"FN"}
-	--- aliases "New Formal Name" {"FN42"}
-	function public.aliases (tag)
-		tag = private:get_or_add_tag(tag)
-		return function (others)
-			for _, other in pairs(others) do
-				private:add_alias(tag, other)
+	--- aliases "Formal Name" {"FN", "ANSI FN"}
+	--- aliases "Another Formal Name" "FN42" "FN++" "Slightly Informal but Known Long Name"
+	function public.aliases (name)
+		local tag = private:get_or_add_tag(name)
+
+		local function step (names)
+			if type(names) == "table" then
+				for _, name in pairs(names) do
+					private:add_alias(tag, name)
+				end
+			else
+				private:add_alias(tag, names)
 			end
+			return step
 		end
+
+		return step
 	end
 
 	--- headers "FN" {"a.fn", "b.fn"}
-	function public.headers (tag)
-		tag = private:get_or_add_tag(tag)
+	function public.headers (name)
+		local tag = private:get_or_add_tag(name)
 		return function (entries)
 			for _, entry in pairs(entries) do
 				private:add_entry(tag, entry)
@@ -32,18 +42,17 @@ function build (private)
 	end
 
 	--- headers "FN42" {include "FN"}
-	function public.include (tag)
-		tag = private:get_tag(tag) or error("tag not found: " .. tag, 2)
-		return private:create_include(tag)
+	function public.include (name)
+		return private:new_include(name)
 	end
 
 	--- headers "FN42" {remove "a.fn"}
 	function public.remove (header)
-		return private:create_remove(header)
+		return private:new_remove(header)
 	end
 
 	return public
 end
 
 
-return build
+return definition
diff --git a/headers/multiset.lua b/headers/multiset.lua
new file mode 100644
index 0000000..7fb1a49
--- /dev/null
+++ b/headers/multiset.lua
@@ -0,0 +1,102 @@
+--- A counting multiset with negative values:
+---
+---     local a = multiset.new()
+---     a:add"value"     --> a:has"value" == true
+---     a:add"value"     --> a:has"value" == true
+---     a:remove"value"  --> a:has"value" == true
+---     a:remove"value"  --> a:has"value" == false
+---     a:remove"value"  --> a:has"value" == false
+---     a:add"value"     --> a:has"value" == false
+local tablex = require "pl.tablex"
+local multiset = {}
+
+
+local function raw ()
+	return {
+		counts={},
+		order={},
+		reverse={},
+	}
+end
+
+
+--- Increase reference count for *value*.
+function multiset:add (value)
+	if not self:had(value) then
+		local index = #self.order + 1
+		self.order[index] = value
+		self.reverse[value] = index
+	end
+	self.counts[value] = (self.counts[value] or 0) + 1
+end
+
+
+--- Reduce reference count for *value*. May go into negative values.
+function multiset:remove (value)
+	self.counts[value] = (self.counts[value] or 0) - 1
+end
+
+
+--- Whether *value* is currently included in the set.
+function multiset:has (value)
+	return self:had(value) and self.counts[value] > 0
+end
+
+
+--- Whether *value* is or was included in the set.
+function multiset:had (value)
+	return self.counts[value] ~= nil
+end
+
+
+function multiset:size ()
+	local count = 0
+	for value in self:all() do
+		count = count + 1
+	end
+	return count
+end
+
+
+--- Guarantees insertion-order iteration over values currently included in the set.
+function multiset:next (previous)
+	local value
+	if previous == nil then
+		value = self.order[1]
+	else
+		value = self.order[self.reverse[previous] + 1]
+	end
+	if value == nil then
+		return nil
+	end
+	if self.counts[value] > 0 then
+		return value
+	end
+	return self:next(value)
+end
+
+
+--- for value in set:all() do ... end
+function multiset:all ()
+	return self.next, self, nil
+end
+
+
+local mt = {
+	__index=multiset,
+	__len=multiset.size,
+}
+
+
+local
+function new ()
+	return setmetatable(raw(), mt)
+end
+
+
+function multiset:clone ()
+	return tablex.deepcopy(self)
+end
+
+
+return setmetatable({new=new}, {__index=multiset})
diff --git a/headers/parser.lua b/headers/parser.lua
index e6895e6..95312ab 100644
--- a/headers/parser.lua
+++ b/headers/parser.lua
@@ -1,34 +1,26 @@
-local build_definition = require "headers.definition"
+local definition = require "headers.definition"
+local multiset = require "headers.multiset"
 
 
 local tag do
 	local methods = {}
+	local mt = {
+		__tostring=function (self) return self.name end,
+		__index=methods,
+	}
+
 	function methods:add (header)
-		table.insert(self.headers_, header)
+		self.headers:add(header)
 		return header
 	end
-	local function headers (self)
-		local result = {}
-		for _, value in pairs(self.headers_) do
-			if type(value) == "function" then
-				value(result)
-			else
-				table.insert(result, value)
-			end
-		end
-		return result
+
+	function methods:remove (header)
+		self.headers:remove(header)
+		return header
 	end
-	local mt = {
-		__tostring=function (self) return self.name end,
-		__index=function (self, key)
-			if key == "headers" then
-				return headers(self)
-			end
-			return methods[key]
-		end,
-	}
+
 	function tag (name)
-		return setmetatable({name=name, headers_={}}, mt)
+		return setmetatable({name=name, headers=multiset.new()}, mt)
 	end
 end
 
@@ -38,13 +30,14 @@ local alias do
 		__tostring = function (self) return string.format("%s\t(%s)", self.name, tostring(self.tag)) end,
 		__index = function (self, key) return self.tag[key] end,
 	}
+
 	function alias (name, tag)
 		return setmetatable({name=name, tag=tag}, mt)
 	end
 end
 
 
-local private = {}
+local private = {}  -- FIXME: Shared state at module level when a constructor function is provided
 private.tags = {}
 private.tag_lookup = {}
 
@@ -72,26 +65,26 @@ end
 
 
 function private:add_entry (tag, entry)
+	if type(entry) == "function" then
+		return entry(tag)
+	end
 	return tag:add(entry)
 end
 
 
-function private:create_include (source)
+function private:new_include (name)
 	return function (target)
-		for _, header in pairs(source.headers) do
-			table.insert(target, header)
+		local source = self:get_tag(name) or error("tag not found: " .. name)
+		for header in source.headers:all() do
+			target:add(header)
 		end
 	end
 end
 
 
-function private:create_remove (header)
+function private:new_remove (header)
 	return function (target)
-		for key, value in pairs(target) do
-			if value == header then
-				table.remove(target, key)
-			end
-		end
+		target:remove(header)
 	end
 end
 
@@ -102,16 +95,17 @@ function private:reset ()
 end
 
 
-return function (input, selection)
+local
+function parse (self, input, selection)
 	private:reset()  -- interface yet to be defined, this is a naive workaround to avoid retriggering prints
-	local db = load(input, nil, nil, build_definition(private))
+	local db = load(input, nil, nil, definition.new(private))
 	db()
 	if selection then
 		local found = private:get_tag(selection)
 		if not found then
 			return false
 		end
-		for _, header in pairs(found.headers) do
+		for header in found.headers:all() do
 			print(header)
 		end
 	else
@@ -121,3 +115,12 @@ return function (input, selection)
 	end
 	return true
 end
+
+
+local
+function new ()
+	return {parse=parse}
+end
+
+
+return {new=new}
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)
diff --git a/spec/parser_spec.lua b/spec/parser_spec.lua
index 78ee8b8..53f86a1 100644
--- a/spec/parser_spec.lua
+++ b/spec/parser_spec.lua
@@ -1,16 +1,31 @@
-local parse = require "headers.parser"
+local parser = require "headers.parser"
 
 
 describe("Scheme", function()
+	local headers
+
+	setup(function()
+		headers = parser.new()
+	end)
+
 	it("version one is supported", function()
 		assert.has_no.errors(function()
-			parse [[scheme "headers/1"]]
+			headers:parse [[scheme "headers/1"]]
 		end)
 	end)
 
 	it("is not required", function()
 		assert.has_no.errors(function()
-			parse ""
+			headers:parse ""
 		end)
 	end)
 end)
+
+
+describe("Standards (tags)", function()  -- TODO: Streamline the naming convention standards/tags/aliases?
+	local headers
+
+	setup(function()
+		headers = parser.new()
+	end)
+end)