TAG table search

[adrix89]

I have some tables with some data and this tables have some tags.
What I need is some trickery to search multiple tags for the specific tables with data.

For example if have

table 1 with tags A B
table 2 with tags B C
table 3 with tags A B C

"searching" for B gets me all, searching A B gives me 1 and 2, and searching B C gives me 2 and 3 and so on.
I need them to be pretty fast with expected 1,000-10,000 tables

[Azhukar]

I have some tables with some data and this tables have some tags.
What I need is some trickery to search multiple tags for the specific tables with data.

For example if have

table 1 with tags A B
table 2 with tags B C
table 3 with tags A B C

"searching" for B gets me all, searching A B gives me 1 and 2, and searching B C gives me 2 and 3 and so on.
I need them to be pretty fast with expected 1,000-10,000 tables

Create a table that will hold a table for each tag with all the tables having said tag at index equal to the table. Table.

Code: Select all

local table1 = {name = "table1",tags = {"A","B"}}
local table2 = {name = "table2",tags = {"B","C"}}
local table3 = {name = "table3",tags = {"A","B","C"}}

local tagtables = {
	A = {
		[table1] = table1,
		[table3] = table3,
	},
	B = {
		[table1] = table1,
		[table2] = table2,
		[table3] = table3,
	},
	C = {
		[table2] = table2,
		[table3] = table3,
	},
}

local function search(...)
	local tags = {...}
	local result = {}
	for i,sometable in pairs(tagtables[tags[1]]) do
		local include = true
		for k=2,#tags do
			if (not tagtables[tags[k]][sometable]) then
				include = false
				break
			end
		end
		if (include) then
			result[#result+1] = sometable
		end
	end
	return result
end

local result = search("A","B")
for i=1,#result do
	print(result[i].name)
end

[adrix89]

Awesome! Thanks!

[spir]

I have some tables with some data and this tables have some tags.
What I need is some trickery to search multiple tags for the specific tables with data.

Aldrix, your problem is one of sets and set intersections, just as at school. Azhukar's solution is to build a collection of associations from tags to *sets* of tables matching each of these tags, right? When searching which tables match a pair of tags (X Y), you are asking for the intersection of their sets. Clear?

Thus, your solution is --nearly as shown by Azhukar-- to use sets. Nicely, in Lua it is trivial: a set is just a table mapping each element to 'true'. So that putting an element 'e' is just "set[e]=true", and checking whether it is in a set is just "if set[e] then ...".
And:
* The set of tags matched by a table (its 'tags' field) should also be a set! As in:

Code: Select all

table1 = {name = "table1", tags = {A=true,B=true}}

* the set of tag_sets is an associative table, that is also a set, of associations...

A function building a tag set, and the function building all of them, can thus just be:

Code: Select all

make_tag_set = function (tag, tables)
   for _,i in ipairs( tables) do
      if table.tags[tag] then set[t] = true end
   end
end

make_tag_sets = functon (tags, tables)
   local tag_sets = {}
   local tag_set
   for _,tag in ipairs(tags) do
      tag_set = make_tag_set(tag, tables)
      tag_sets[tag] = tag_set
   end
   return tag_sets
end

(All code quickly written and untested... but you get the idea.)

(@Azhukar: I don't understand why your tag_tables hold each table both as keys and values, [table1] = table1, instead of just [table1] = true.)

You can add a function to see a set('s elements):

Code: Select all

local set_for_tags = function (tag_sets, tag1, tag2)
   local set = {}
   local set1, set2 = tag_sets[tag1], tag_sets[tag2]
   for t,_ in pairs(set1) do
      if set2[t] then set[t] = true end
   end
   return set
end

Then, as said, you are asking for set intersections. (You may implement it in general, it is trivial.) In your case, this looks like:

Code: Select all

local set_for_tags = function (tag_sets, tag1, tag2)
   local set = {}
   local set1, set2 = tag_sets[tag1], tag_sets[tag2]
   for t,_ in pairs(set1) do
      if set2[t] then set[t] = true end
   end
   return set
end

(You can generalise to n tags.)

Denis

[Azhukar]

I don't understand why your tag_tables hold each table both as keys and values, [table1] = table1, instead of just [table1] = true.

No reason really, it was hastily written as an example, either works.