TdList =
{
    new = function(self)
        local list = 
        {
            first = 0,
            last = -1,
            data = {}
        }

        setmetatable(list, self)
        self.__index = self

        return list
    end,

    head = function(self)
        return self.data[self.first]
    end,

    tail = function(self)
        return self.data[self.last]
    end,

    isEmpty = function(self)
        return self.first > self.last
    end,

    size = function(self)
        return self.last - self.first
    end,

    pushLeft = function(self, val)
        local first = self.first - 1
        self.first = first
        self.data[first] = val
    end,

    pushRight = function(self, val)
        local last = self.last + 1
        self.last = last
        self.data[last] = val
    end,

    popLeft = function(self)
        local first = self.first
        if self:isEmpty() then 
            return
        end

        local value = self.data[first]
        self.data[first] = nil
        self.first = first + 1

        return value
    end,

    popRight = function(self)
        local last = self.last
        if self:isEmpty() then 
            return 
        end

        local value = self.data[last]
        self.data[last] = nil
        self.last = last - 1

        return value
    end,

    forEach = function(self, f)
        for i = self.first, self.last do
            f(self.data[i])
        end
    end
}