Revision of prefix-stack.lua

capitalex revised this gist 7 hours ago. Go to revision

2 files changed, 174 insertions

object.lua(file created)

		@@ -0,0 +1,68 @@
1	+	--
2	+	-- classic
3	+	--
4	+	-- Copyright (c) 2014, rxi
5	+	--
6	+	-- This module is free software; you can redistribute it and/or modify it under
7	+	-- the terms of the MIT license. See LICENSE for details.
8	+	--
9	+
10	+
11	+	local Object = {}
12	+	Object.__index = Object
13	+
14	+
15	+	function Object:new()
16	+	end
17	+
18	+
19	+	function Object:extend()
20	+	local cls = {}
21	+	for k, v in pairs(self) do
22	+	if k:find("__") == 1 then
23	+	cls[k] = v
24	+	end
25	+	end
26	+	cls.__index = cls
27	+	cls.super = self
28	+	setmetatable(cls, self)
29	+	return cls
30	+	end
31	+
32	+
33	+	function Object:implement(...)
34	+	for _, cls in pairs({...}) do
35	+	for k, v in pairs(cls) do
36	+	if self[k] == nil and type(v) == "function" then
37	+	self[k] = v
38	+	end
39	+	end
40	+	end
41	+	end
42	+
43	+
44	+	function Object:is(T)
45	+	local mt = getmetatable(self)
46	+	while mt do
47	+	if mt == T then
48	+	return true
49	+	end
50	+	mt = getmetatable(mt)
51	+	end
52	+	return false
53	+	end
54	+
55	+
56	+	function Object:__tostring()
57	+	return "Object"
58	+	end
59	+
60	+
61	+	function Object:__call(...)
62	+	local obj = setmetatable({}, self)
63	+	obj:new(...)
64	+	return obj
65	+	end
66	+
67	+
68	+	return Object

prefix-stack.lua(file created)

		@@ -0,0 +1,106 @@
1	+	local Object = require "object"
2	+
3	+
4	+	--[[
5	+	Prefix Tree Stack preserves the insertion order
6	+	of the items being added. This can create duplicate
7	+	branches when a normal prefix tree wouldn't have it
8	+
9	+	Insertion Operations:
10	+	insert apple
11	+	insert application
12	+	insert banana
13	+	insert banned
14	+	insert apply
15	+	insert bandana
16	+	insert apples
17	+
18	+	Normal Prefix Tree:
19	+	appl
20	+	+-- e -> apple
21	+	\| +-- s -> apples
22	+	+-- ication -> application
23	+	+-- y -> apply
24	+	ban
25	+	+-- ana -> banana
26	+	+-- ned -> banned
27	+	+-- dana -> bandana
28	+
29	+	Ordered Prefix Tree:
30	+	appl
31	+	+-- e -> apple
32	+	+-- ication -> application
33	+	ban
34	+	+-- ana -> banana
35	+	+-- ned -> banned
36	+	apply -> apply
37	+	bandan -> bandan
38	+	apples -> apples
39	+
40	+	]]
41	+	local PrefixTreeStack = Object:extend()
42	+
43	+	function PrefixTreeStack:new()
44	+	self.stack = {n = 0}
45	+	end
46	+
47	+	function PrefixTreeStack:push(string)
48	+	local stack = self.stack
49	+	for char in string:gmatch(".") do
50	+	if stack.n == 0 then
51	+	local newStack = {prefix = char, n = 0;}
52	+	stack.n = stack.n + 1
53	+	table.insert(stack, newStack)
54	+	stack = newStack
55	+	elseif stack[stack.n].prefix == char then
56	+	stack = stack[stack.n]
57	+	else
58	+	local newStack = {prefix = char, n = 0;}
59	+	stack.n = stack.n + 1
60	+	table.insert(stack, newStack)
61	+	stack = newStack
62	+	end
63	+	end
64	+	end
65	+
66	+
67	+	--[[
68	+	Each node should have a + before its prefix
69	+	Each node should have a \| leading to its sibling
70	+	]]
71	+	function PrefixTreeStack:__tostring()
72	+	local string = {}
73	+	local function walkTree(stack, depth)
74	+	local children = {}
75	+	for i = 1, stack.n do
76	+	local path = stack[i]
77	+	table.insert(children, "+ " .. path.prefix)
78	+	local subchildren = walkTree(path, depth + 2)
79	+	for _, subchild in ipairs(subchildren) do
80	+	if i ~= stack.n then
81	+	table.insert(children, "\| " .. subchild)
82	+	else
83	+	table.insert(children, " " .. subchild)
84	+	end
85	+	end
86	+	end
87	+	return children
88	+	end
89	+	string = walkTree(self.stack, 0)
90	+	return table.concat(string, "\n")
91	+	end
92	+
93	+	local pprint = require "pprint"
94	+
95	+	local pts = PrefixTreeStack()
96	+	pts:push "apple"
97	+	pts:push "apples"
98	+	pts:push "banana"
99	+	pts:push "bandana"
100	+	pts:push "banned"
101	+	pts:push "banner"
102	+	pts:push "application"
103	+	pts:push "applies"
104	+	pts:push "apply"
105	+
106	+	print(pts)

Newer Older