链表Map

# Entry

local Entry = {}
Entry.__cname = "util.Map.Entry"
Entry.__index = Entry

function Entry.new(map, k, v)
    local obj = {}
    setmetatable(obj, Entry)
    obj:ctor(map, k, v)
    return obj
end

function Entry:ctor(map, k, v)
    self.map = map
    self.key = k
    self.value = v
    self.prev = nil
    self.next = nil
end

function Entry:GetKey()
    return self.key
end

function Entry:GetValue()
    return self.value
end

# 链表部分

local EntryLinkedList = {}
EntryLinkedList.__cname = "util.Map.EntryLinkedList"
EntryLinkedList.__index = EntryLinkedList

function EntryLinkedList.new()
    local obj = {}
    setmetatable(obj, EntryLinkedList)
    obj:ctor()
    return obj
end

function EntryLinkedList:ctor()
    self:_Reset()
end

function EntryLinkedList:_Reset()
    self.head = nil
    self.tail = nil
    self.count = 0
end

function EntryLinkedList:Clear()
    self:_Reset()
end

function EntryLinkedList:GetCount()
    return self.count
end

function EntryLinkedList:_SetTail(entry)
    -- oldTail <=> node建立链接
    entry.prev = self.tail
    self.tail.next = entry
    -- 设为新tail
    self.tail = entry
end

function EntryLinkedList:AddLast(entry)
    if 0 == self.count then
        self.count = 1
        self.head = entry
        self.tail = self.head
    else
        self.count = self.count + 1
        self:_SetTail(entry)
    end
end

function EntryLinkedList:_DetachHead()
    local newHead = self.head.next
    newHead.prev = nil --断开旧head
    self.head.next = nil--旧head清除next
    self.head = newHead --设置新head
end

function EntryLinkedList:RemoveFirst()
    if 1 == self.count then
        self:_Reset()
    else
        self:_DetachHead()
        self.count = self.count - 1
    end
end

function EntryLinkedList:_DetachTail()
    local newTail = self.tail.prev
    newTail.next = nil --断开旧tail
    self.tail.prev = nil --旧tail清除prev
    self.tail = newTail --设置新tail
end

function EntryLinkedList:RemoveLast()
    if 1 == self.count then
        self:_Reset()
    else
        self:_DetachTail()
        self.count = self.count - 1
    end
end

function EntryLinkedList:_DetachNode(node)
    node.prev.next = node.next
    node.next.prev = node.prev
    node.prev = nil
    node.next = nil
end

function EntryLinkedList:Remove(entry)
    if self.head == entry then
        self:RemoveFirst()
    elseif self.tail == entry then
        self:RemoveLast()
    else
        self:_DetachNode(entry)
        self.count = self.count - 1
    end
end

function EntryLinkedList:GetIterator(exceptModCount, map)
    self.iteratorCur = self.head
    if nil == self.iterator then
        self.iterator = function(itrObj, node)
            if nil ~= exceptModCount and nil ~= map then
                assert(exceptModCount == map.modCount, "Map: modify map in Iterator")
            end
            local ret = self.iteratorCur
            if nil ~= ret then
                self.iteratorCur = self.iteratorCur.next
                return ret
            end
            return nil
        end
    end
    return self.iterator
end

# Map

local Map = {}
Map.__cname = "util.Map"
local MapMt1 = {
    __index = Map
}
Map.__index = Map
Map.__newindex = function(tb, k, v)
    tb:Set(k, v)
end

local ClearTypeEnum = {
    Reset = nil,
    FillNil = 1,
}
Map.ClearTypeEnum = ClearTypeEnum

function Map.new()
    local obj = {}
    setmetatable(obj, MapMt1)
    obj:ctor()
    setmetatable(obj, Map)
    return obj
end

function Map:ctor()
    self.kvTb = {}
    self.modCount = 0
    self.entrys = EntryLinkedList.new()
end

function Map:Clear(clearType)
    if self.entrys:GetCount() < 1 then return end

    if clearType == ClearTypeEnum.Reset then
        self.kvTb = {}
    elseif clearType == ClearTypeEnum.FillNil then
        for entry in self.entrys:GetIterator() do
            self.kvTb[entry.key] = nil
        end
    end
    self.modCount = 0
    self.entrys:Clear()
end

function Map:GetCount()
    return self.entrys:GetCount()
end

function Map:Add(k, v)
    local entry = self.kvTb[k]
    assert(nil == entry)

    self.modCount = self.modCount + 1
    entry = Entry.new(self, k, v)
    self.entrys:AddLast(entry)
    self.kvTb[k] = entry
end

function Map:Remove(k)
    local entry = self.kvTb[k]
    self.kvTb[k] = nil
    if nil ~= entry then
        self.entrys:Remove(entry)
        return true, entry:GetValue()
    end
    return false, nil
end

function Map:Set(k, v)
    local entry = self.kvTb[k]
    if nil == entry then
        self:Add(k, v)
    else
        entry.value = v
    end
end

function Map:Get(k)
    local entry = self.kvTb[k]
    if nil ~= entry then
        return entry.value
    end
    return nil
end

function Map:ContainsKey(k)
    return nil ~= self.kvTb[k]
end

function Map:__tostring()
    if self:GetCount() <= 0 then return "" end

    local strTb = {}
    local count = 0
    for entry in self.entrys:GetIterator() do
        if count > 0 then
            table.insert(strTb, ",")
        end
        table.insert(strTb, tostring(entry.key))
        table.insert(strTb, "->")
        table.insert(strTb, tostring(entry.value))
        count = count + 1
    end
    return table.concat(strTb)
end

function Map:GetEntrysIterator()
    return self.entrys:GetIterator(self.modCount, self)
end

return Map