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)