object.lua
· 1009 B · Lua
Raw
Playground
--
-- classic
--
-- Copyright (c) 2014, rxi
--
-- This module is free software; you can redistribute it and/or modify it under
-- the terms of the MIT license. See LICENSE for details.
--
local Object = {}
Object.__index = Object
function Object:new()
end
function Object:extend()
local cls = {}
for k, v in pairs(self) do
if k:find("__") == 1 then
cls[k] = v
end
end
cls.__index = cls
cls.super = self
setmetatable(cls, self)
return cls
end
function Object:implement(...)
for _, cls in pairs({...}) do
for k, v in pairs(cls) do
if self[k] == nil and type(v) == "function" then
self[k] = v
end
end
end
end
function Object:is(T)
local mt = getmetatable(self)
while mt do
if mt == T then
return true
end
mt = getmetatable(mt)
end
return false
end
function Object:__tostring()
return "Object"
end
function Object:__call(...)
local obj = setmetatable({}, self)
obj:new(...)
return obj
end
return Object
| 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 |
| 69 |
prefix-stack.lua
· 2.5 KiB · Lua
Raw
Playground
local Object = require "object"
--[[
Prefix Tree Stack preserves the insertion order
of the items being added. This can create duplicate
branches when a normal prefix tree wouldn't have it
Insertion Operations:
insert apple
insert application
insert banana
insert banned
insert apply
insert bandana
insert apples
Normal Prefix Tree:
appl
+-- e -> apple
| +-- s -> apples
+-- ication -> application
+-- y -> apply
ban
+-- ana -> banana
+-- ned -> banned
+-- dana -> bandana
Ordered Prefix Tree:
appl
+-- e -> apple
+-- ication -> application
ban
+-- ana -> banana
+-- ned -> banned
apply -> apply
bandan -> bandan
apples -> apples
]]
local PrefixTreeStack = Object:extend()
function PrefixTreeStack:new()
self.stack = {n = 0}
end
function PrefixTreeStack:push(string)
local stack = self.stack
for char in string:gmatch(".") do
if stack.n == 0 then
local newStack = {prefix = char, n = 0;}
stack.n = stack.n + 1
table.insert(stack, newStack)
stack = newStack
elseif stack[stack.n].prefix == char then
stack = stack[stack.n]
else
local newStack = {prefix = char, n = 0;}
stack.n = stack.n + 1
table.insert(stack, newStack)
stack = newStack
end
end
end
--[[
Each node should have a + before its prefix
Each node should have a | leading to its sibling
]]
function PrefixTreeStack:__tostring()
local string = {}
local function walkTree(stack, depth)
local children = {}
for i = 1, stack.n do
local path = stack[i]
table.insert(children, "+ " .. path.prefix)
local subchildren = walkTree(path, depth + 2)
for _, subchild in ipairs(subchildren) do
if i ~= stack.n then
table.insert(children, "| " .. subchild)
else
table.insert(children, " " .. subchild)
end
end
end
return children
end
string = walkTree(self.stack, 0)
return table.concat(string, "\n")
end
local pprint = require "pprint"
local pts = PrefixTreeStack()
pts:push "apple"
pts:push "apples"
pts:push "banana"
pts:push "bandana"
pts:push "banned"
pts:push "banner"
pts:push "application"
pts:push "applies"
pts:push "apply"
print(pts)
| 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) |