Notes - Lua programming (2nd Edition) Ch11~13

11 data structure

array

Use an integer to index the table

a = {}
-- The size is defined indirectly when initializing the array
for i = 1, 1000 do
  a[i] = 0
end
-- Generally, 1 is used as the starting index of the array
-- It's OK not to, but some Lua Library and length operators are invalidated
print(#a)

-- Support list initialization
squares = {1, 4, 9, 16, 25}

Matrix and multidimensional array

Use the table of table to explicitly create each row:

function createMatrix(m, n)
  local matrix = {}
  for i = 1, m do
    matrix[i] = {}
    for j = 1, n do
      matrix[i][j] = 0
    end
  end
  return matrix
end

m0 = createMatrix(4, 4)

for i = 1, #m0 do
  for j = 1, #m0[i] do
    if i == j then
      m0[i][j] = 1
    else
      m0[i][j] = 0
    end
  end
end

for i = 1, #m0 do
  for j = 1, #m0[i] do
    io.write(string.format("%3d", m0[i][j]))
  end
  print()
end

Represented by one-dimensional table:

function createMatrix(m, n)
  local matrix = {}
  for i = 1, m do
    for j = 1, n do
      matrix[(i - 1) * n + j] = 0
    end
  end
  return matrix
end

m = 4
n = 4
m0 = createMatrix(4, 4)

for i = 1, m do
  for j = 1, n do
    if i == j then
      m0[(i - 1) * n + j] = 1
    else
      m0[(i - 1) * n + j] = 0
    end
  end
end

for i = 1, m do
  for j = 1, n do
    io.write(string.format("%3d", m0[(i - 1) * n + j]))
  end
  print()
end

The table in Lua itself is sparse, so no additional skills are needed to deal with sparse arrays. During traversal, pairs is generally used to traverse non nil elements, but because the key s in table are unordered, using pairs does not guarantee sequential access

Linked list

-- Create list
list = nil
for i = 1, 5 do
  list = {next = list, value = i}
end
-- ergodic
p = list
while p do
  print(p, p.value)
  p = p.next
end

Queue and bidirectional queue

List = {}
function List.new()
  return {first = 0, last = -1}
end

function List.pushFirst(list, value)
  local first = list.first - 1
  list.first = first
  list[first] = value
end

function List.pushLast(list, value)
  local last = list.last + 1
  list.last = last
  list[last] = value
end

function List.popFirst(list)
  local first = list.first
  if first > list.last then
    error("list is empty")
  end
  local value = list[first]
  list[first] = nil
  list.first = first + 1
  return value
end

function List.popLast(list)
  local last = list.last
  if first > list.last then
    error("list is empty")
  end
  local value = list[last]
  list[last] = nil
  list.last = last - 1
  return value
end

function List.display(list)
  for i = list.first, list.last do
    print(i, list[i])
  end
end

list = List.new()
for i = 1, 3 do
  List.pushLast(list, i)
end
List.display(list)
for i = 1, 3 do
  print(List.popFirst(list))
end
List.display(list)

If you only need to use queues, just call pushLast and popFirst

Set and unordered group (bag)

Implement set in Lua:

reserved = {
  ["while"] = true,
  ["if"] = true,
  ["for"] = true,
  ["end"] = true,
}

function stringReserved(x)
  if reserved[x] then
    return true
  else
    return false
  end
end

print(stringReserved("end")) -->true
print(stringReserved("blabla")) -->false

If you want to implement multiset, set value as a counter. If the counter is 0, delete the element

String buffer

local buffers = {}
for line in io.lines() do
  if line == "" then
    break
  end
  buffers[#buffers + 1] = line .. "\n"
end
local s = table.concat(buffers) -- use concat
print(s)

concat also has a second optional parameter, the delimiter

local buffers = {}
for line in io.lines() do
  if line == "" then
    break
  end
  buffers[#buffers + 1] = line
end
buffers[#buffers + 1] = ""
local s = table.concat(buffers, "\n")
print(s)

The underlying implementation of concat is similar to a Hanoi tower shaped stack. See P102 for details

chart

It is implemented with a table composed of nodes. There are two fields: the name of the node and the node set adjacent to the node

12 data files and persistence

data file

If it is a file similar to CSV format, it can be changed to the following form:

-- C:\Users\Administrator\Desktop\LuaTests\data.txt
-- be careful Entry{}It means to use one table Call a function for an argument Entry
Entry{
  "Alice",
  "18",
  "1997"}

Entry{
  "Bob",
  "20",
  "2000"}

There are several simple statistics:

local count = 0
function Entry()
  count = count + 1
end
dofile("C:\\Users\\Administrator\\Desktop\\LuaTests\\data.txt")
print("numbers: " .. count)

You can also use the format of "self describing data":

-- C:\Users\Administrator\Desktop\LuaTests\data.txt
Entry{
  name = "Alice",
  score = "78",
  year = "1997"}

Entry{
  name = "Bob",
  score = "99",
  year = "2000"}

Collect everyone's name:

local authors = {}
function Entry(dataTable)
  authors[#authors + 1] = dataTable.name
end
dofile("C:\\Users\\Administrator\\Desktop\\LuaTests\\data.txt")
for key, val in pairs(authors) do
  print(val)
end

Serialization

Serialization: convert data into byte stream or character stream for storage or transmission.

-- Serialize numbers or strings
function serialize(o)
  if type(o) == "number" then
    io.write(o)
  elseif type(o) == "string" then
    io.write(string.format("%q", o))
  end
end
    
io.output("C:\\Users\\Administrator\\Desktop\\LuaTests\\output.txt")
serialize(18)
serialize("\\d[]''")

Serialization result:

-- C:\Users\Administrator\Desktop\LuaTests\output.txt
18"\\d[]''"

P108: serialization of Long String Tags

Save acyclic table

-- Serialization with indentation
fourBlank = "    "

function printBlank(serializeLevel)
  for i = 1, serializeLevel do
    io.write(fourBlank)
  end
end

function serialize(o, serializeLevel)
  if type(o) == "number" then
    io.write(o)
  elseif type(o) == "string" then
    io.write(string.format("%q", o))
  elseif type(o) == "table" then
    io.write("{\n")
    for key, val in pairs(o) do
      printBlank(serializeLevel)
      io.write(key, " = ")
      serialize(val, serializeLevel + 1)
      io.write(",\n")
    end
    printBlank(serializeLevel - 1)
    io.write("}")
  else
    error("cannot serialize a " .. type(o))
  end
end

buffer = {}
function Entry(dataTable)
  buffer[#buffer + 1] = dataTable
end

dofile("C:\\Users\\Administrator\\Desktop\\LuaTests\\data.txt")
io.output("C:\\Users\\Administrator\\Desktop\\LuaTests\\output.txt")
serialize(buffer, 1)

Input:

-- "C:\\Users\\Administrator\\Desktop\\LuaTests\\data.txt"
Entry{
  name = "Alice",
  score = "78",
  year = "1997"}

Entry{
  name = "Bob",
  score = "99",
  year = "2000",
  book = {"abc", "def"}}

Output:

-- "C:\\Users\\Administrator\\Desktop\\LuaTests\\output.txt"
{
    1 = {
        year = "1997",
        name = "Alice",
        score = "78",
    },
    2 = {
        book = {
            1 = "abc",
            2 = "def",
        },
        year = "2000",
        name = "Bob",
        score = "99",
    },
}

Considering that the key of table may have an illegal Lua identifier, the

io.write(" ", k, " = ")

Change to

io.write("["); serialize(k); io.write("] = ")

The robustness of the function can be enhanced, and the output becomes:

-- "C:\\Users\\Administrator\\Desktop\\LuaTests\\output.txt"
{
    [1] = {
        ["year"] = "1997",
        ["name"] = "Alice",
        ["score"] = "78",
    },
    [2] = {
        ["book"] = {
            [1] = "abc",
            [2] = "def",
        },
        ["year"] = "2000",
        ["name"] = "Bob",
        ["score"] = "99",
    },
}

table with ring

Additional tables are required to record the tables that appear.

If table has ever appeared, use the previous name; If not, serialize and save the new name.

See P111 for details

13 metatable and metamethod

You can modify the behavior of a value through a meta table

t = {}
t1 = {}
print(getmetatable(t)) -->nil
-- setmetatable Used to modify any table Meta table of
-- Lua Can only be set in table Meta table of
-- Meta table of other types of values must pass C Code complete
setmetatable(t, t1)
assert(getmetatable(t) == t1)
print(getmetatable(t)) -->table: 0x006b1b60

-- All strings have meta tables set by the standard string library, and other types have no meta tables by default
print(getmetatable("y")) -->table: 0x006b53e8
print(getmetatable(10)) -->nil

Meta method of arithmetic class

Write a simple Set class:

Set = {}

-- Constructor
function Set.new(list)
  local set = {}
  for _, v in ipairs(list) do
    set[v] = true
  end
  return set
end

-- Union
function Set.union(a, b)
  local res = Set.new{}
  for k in pairs(a) do
    res[k] = true
  end
  for k in pairs(b) do
    res[k] = true
  end
  return res
end

-- intersection
function Set.intersection(a, b)
  local res = Set.new{}
  for k in pairs(a) do
    res[k] = b[k]
  end
  return res
end

-- Set To string
function Set.toString(set)
  local list = {}
  for e in pairs(set) do
    list[#list + 1] = e
  end
  return "{" .. table.concat(list, ", ") .. "}"
end

-- Print
function Set.print(s)
  print(Set.toString(s))
end

a = Set.new({1, 2, 3})
b = Set.new({2, 3, 4})
Set.print(Set.intersection(a, b)) -->{2, 3}

Add a meta table to it:

-- Set
Set = {}
local mtSet = {}

function Set.new(list)
  local set = {}
  setmetatable(set, mtSet) --> Each new Set All have the same meta table
  for _, v in ipairs(list) do
    set[v] = true
  end
  return set
end

function Set.union(a, b)
  local res = Set.new{}
  for k in pairs(a) do
    res[k] = true
  end
  for k in pairs(b) do
    res[k] = true
  end
  return res
end

function Set.intersection(a, b)
  local res = Set.new{}
  for k in pairs(a) do
    res[k] = b[k]
  end
  return res
end

function Set.toString(set)
  local list = {}
  for e in pairs(set) do
    list[#list + 1] = e
  end
  return "{" .. table.concat(list, ", ") .. "}"
end

function Set.print(s)
  print(Set.toString(s))
end

-- Add two meta methods to the meta table
mtSet.__add = Set.union
mtSet.__mul = Set.intersection
-- end of Set

a = Set.new({1, 2, 3})
b = Set.new({2, 3, 4})
Set.print(a * b) -->{2, 3}

The meta methods of the arithmetic class in the meta table also include:

__add
__mul
__sub
__div
__ unm: opposite number
__mod
__pow
__ concat: join operator

Lua's steps to find the meta table (taking the multiplication operator as an example): first check whether the first value has a meta table and whether there is a meta table in the meta table__ mul field, if any, is used as the meta method, which is irrelevant to the second value; If not, check the second value; If neither value is found, an error is raised.

If you want to get clearer error information, you can check the type of operands before the actual operation of the meta method:

function Set.intersection(a, b)
  if getmetatable(a) ~= mtSet or getmetatable(b) ~= mtSet then
    -- The second parameter 2 here indicates the number of layers in which the error occurs
    -- Measured in ZeroBrane Studio The number of lines that will affect the display of errors
    error("attempt to 'mul' a set with a non-set value", 2)
  end
  local res = Set.new{}
  for k in pairs(a) do
    res[k] = b[k]
  end
  return res
end

Meta methods of relational classes

Meta methods of relation classes include:

__ eq: equal to
__ lt: less than
__ le: less than or equal to

Not equal to, greater than, and greater than or equal to can be obtained by the above meta method

Note that meta methods of relational classes cannot be applied to mixed types, nor can you attempt to compare two objects with different meta methods

Equal comparison will never cause an error. If the types are different or the meta methods are different, it will directly return false

-- Set
Set = {}
local mtSet = {}

function Set.new(list)
  local set = {}
  setmetatable(set, mtSet)
  for _, v in ipairs(list) do
    set[v] = true
  end
  return set
end

function Set.union(a, b)
  local res = Set.new{}
  for k in pairs(a) do
    res[k] = true
  end
  for k in pairs(b) do
    res[k] = true
  end
  return res
end

function Set.intersection(a, b)
  if getmetatable(a) ~= mtSet or getmetatable(b) ~= mtSet then
    error("attempt to 'mul' a set with a non-set value", 2)
  end
  local res = Set.new{}
  for k in pairs(a) do
    res[k] = b[k]
  end
  return res
end

function Set.toString(set)
  local list = {}
  for e in pairs(set) do
    list[#list + 1] = e
  end
  return "{" .. table.concat(list, ", ") .. "}"
end

function Set.print(s)
  print(Set.toString(s))
end

mtSet.__add = Set.union
mtSet.__mul = Set.intersection
mtSet.__le = function(a, b)
  for k in pairs(a) do
    if not b[k] then
      return false
    end
  end
  return true
end
mtSet.__lt = function(a, b)
  return a <= b and not (b <= a)
end
mtSet.__eq = function(a, b)
  return a <= b and b <= a
end
-- end of Set

a = Set.new({1, 2, 3})
b = Set.new({1, 2, 3, 4})
print(a < b) -->true
print(a > b) -->false
print(a <= b) -->true
print(a >= b) -->false
print(a == b) -->false
print(a ~= b) -->true

Meta method defined by Library

The function print always calls tostring to format its output, and tostring checks whether the value has a__ Meta method of tostring

mtSet.__tostring = Set.toString
b = Set.new({1, 2, 3, 4})
print(b) -->{1, 2, 3, 4}

Set field__ metatable can protect the meta table from being modified

mtSet.__metatable = "not your business"
b = Set.new({1, 2, 3, 4})
myMt = {}
setmetatable(b, myMt)
-->D:\Program Files\ZeroBraneStudio\bin\lua.exe: C:\Users\Administrator\Desktop\LuaTests\test0.lua:71: cannot change a protected metatable

Meta method of table access

__index

If you access a field that does not exist in the table, the interpreter looks for a field named__ index meta method. If there is no meta method, nil is returned. Otherwise, the result returned by the meta method is returned:

Window = {}
Window.mt = {}

Window.prototype = {
  x = 0,
  y = 0,
  width = 800,
  height = 600
}

function Window.new(o)
  setmetatable(o, Window.mt)
  return o
end

Window.mt.__index = function(table, key)
  return Window.prototype[key]
end

window = Window.new{x = 10, y = 20}
print(window.width) -->800
window1 = Window.new{x = 10, y = 20, width = 256}
print(window1.width) -->256

Will__ It is a common practice to use index for inheritance. Therefore, Lua supports the following wording:

Window.mt.__index = Window.prototype

Use table as__ The index metamethod can quickly implement single inheritance, but the function will be more flexible

window = Window.new{x = 10, y = 20}
-- use rawget yes table Original access, that is, simple access without considering the meta table
print(rawget(window, "x"))
print(rawget(window, "width"))

__newindex

It is used for updating table. It is used when assigning values to indexes that do not exist

-- A wrong example
Window.mt.__newindex = function(table, key)
  table[key] = 1 -- Infinite recursion occurs here__newindex Meta method causes stack explosion
end

Correct setting__ The newindex meta method needs to cooperate with rawset(table, key, val):

Window.mt.__newindex = function(table, key)
  rawset(table, key, 1)
end
-- Whether given to non-existent index What is the setting value
-- The results are all assigned to 1
window.notExistIndex = 999
print(window.notExistIndex)

Combined use__ index and__ The newindex meta method can realize the powerful functions in Lua: read-only table, table with default value and inheritance

table with default value

Window = {}
Window.mt = {}

function Window.new(o)
  return o
end

local key = {} -- Prevent name conflicts with a new one table As the only key
local mt = {
  __index = function(t)
    return t[key]
  end
}
function setDefault(t, d)
  t[key] = d
  setmetatable(t, mt)
end

window = Window.new{x = 10, y = 10}
setDefault(window, 0)
print(window.newIndex) -->0

Track access to table

Window = {}
Window.mt = {}

function Window.new(o)
  return o
end

window = Window.new{x = 10, y = 10}

local _window = window
window = {}

local mt = {
  __index = function(t, k)
    print("access to element " .. tostring(k))
    return _window[k]
  end,
  
  __newindex = function(t, k, v)
    print("update of element " .. tostring(k) ..
      " to " .. tostring(v))
    _window[k] = v
  end
}
setmetatable(window, mt)

print(window.x)
window.x = 20
window.newIndex = 100