add heap

5 files changed, 214 insertions, 1 deletions

diff --git a/tests/modules/heap/test.lua b/tests/modules/heap/test.lua
new file mode 100644
index 000000000..098116f28
--- /dev/null
+++ b/tests/modules/heap/test.lua
@@ -0,0 +1,37 @@
+import("core.base.heap")
+
+function test_cdataheap(t)
+    local h = heap.cdataheap{
+        size = 100,
+        ctype = [[
+            struct {
+                int priority;
+                int order;
+            }
+        ]],
+        cmp = function(a, b)
+            if a.priority == b.priority then
+                return a.order > b.order
+            end
+            return a.priority < b.priority
+        end}
+    h:push{priority = 20, order = 1}
+    h:push{priority = 10, order = 2}
+    h:push{priority = 10, order = 3}
+    h:push{priority = 20, order = 4}
+    t:are_equal(h:pop().order, 3)
+    t:are_equal(h:pop().order, 2)
+    t:are_equal(h:pop().order, 4)
+    t:are_equal(h:pop().order, 1)
+end
+
+function test_valueheap(t)
+    local h = heap.valueheap{cmp = function(a, b)
+          return a.priority < b.priority
+       end}
+    h:push{priority = 20, etc = 'bar'}
+    h:push{priority = 10, etc = 'foo'}
+    t:are_equal(h:pop().priority, 10)
+    t:are_equal(h:pop().priority, 20)
+end
+
diff --git a/xmake/core/base/dlist.lua b/xmake/core/base/dlist.lua
index 050e4d7d3..12d194ff6 100644
--- a/xmake/core/base/dlist.lua
+++ b/xmake/core/base/dlist.lua
@@ -19,7 +19,7 @@
 --
 
 -- load modules
-local object = require("ui/object")
+local object = require("base/object")
 
 -- define module
 local dlist = dlist or object { _init = {"_length"} } {0}
diff --git a/xmake/core/base/heap.lua b/xmake/core/base/heap.lua
new file mode 100644
index 000000000..b4448f62d
--- /dev/null
+++ b/xmake/core/base/heap.lua
@@ -0,0 +1,153 @@
+--!A cross-platform build utility based on Lua
+--
+-- priority queue implemented as a binary heap.
+-- written by Cosmin Apreutesei. Public Domain.
+--
+-- @see https://github.com/luapower/heap
+--
+-- modified by  ruki
+-- @file        heap.lua
+--
+
+-- define module: heap
+local heap  = heap or {}
+
+local ffi --init on demand so that the module can be used without luajit
+local assert, floor = assert, math.floor
+
+-- heap algorithm working over abstract API that counts from one.
+function heap.makeheap(add, remove, swap, length, cmp)
+
+    local function moveup(child)
+        local parent = floor(child / 2)
+        while child > 1 and cmp(child, parent) do
+            swap(child, parent)
+            child = parent
+            parent = floor(child / 2)
+        end
+        return child
+    end
+
+    local function movedown(parent)
+        local last = length()
+        local child = parent * 2
+        while child <= last do
+            if child + 1 <= last and cmp(child + 1, child) then
+                child = child + 1 -- sibling is smaller
+            end
+            if not cmp(child, parent) then break end
+            swap(parent, child)
+            parent = child
+            child = parent * 2
+        end
+        return parent
+    end
+
+    local function push(...)
+        add(...)
+        return moveup(length())
+    end
+
+    local function pop(i)
+        swap(i, length())
+        remove()
+        movedown(i)
+    end
+
+    local function rebalance(i)
+        if moveup(i) == i then
+            movedown(i)
+        end
+    end
+    return push, pop, rebalance
+end
+
+-- cdata heap working over a cdata array
+function heap.cdataheap(h)
+    ffi = ffi or require("ffi")
+    assert(h and h.size, "size expected")
+    assert(h.size >= 2, "size too small")
+    assert(h.ctype, "ctype expected")
+    local ctype = ffi.typeof(h.ctype)
+    h.data = h.data or ffi.new(ffi.typeof("$[?]", ctype), h.size)
+    local t, n, maxn = h.data, h.length or 0, h.size - 1
+    local function add(v) n = n + 1; t[n] = v end
+    local function rem() n = n - 1 end
+    local function swap(i, j) t[0] = t[i]; t[i] = t[j]; t[j] = t[0] end
+    local function length() return n end
+    local cmp = h.cmp and
+        function(i, j) return h.cmp(t[i], t[j]) end or
+        function(i, j) return t[i] < t[j] end
+    local push, pop, rebalance = heap.makeheap(add, rem, swap, length, cmp)
+
+    local function get(i, box)
+        assert(i >= 1 and i <= n, "invalid index")
+        if box then
+            box[0] = t[i]
+        else
+            return ffi.new(ctype, t[i])
+        end
+    end
+    function h:push(v)
+        assert(n < maxn, "buffer overflow")
+        push(v)
+    end
+    function h:pop(i, box)
+        assert(n > 0, "buffer underflow")
+        local v = get(i or 1, box)
+        pop(i or 1)
+        return v
+    end
+    function h:peek(i, box)
+        return get(i or 1, box)
+    end
+    function h:replace(i, v)
+        assert(i >= 1 and i <= n, "invalid index")
+        t[i] = v
+        rebalance(i)
+    end
+    h.length = length
+    return h
+end
+
+-- value heap working over a Lua table
+function heap.valueheap(h)
+    h = h or {}
+    local t, n = h, #h
+    local function add(v) n = n + 1; t[n] = v end
+    local function rem() t[n] = nil; n = n - 1 end
+    local function swap(i, j) t[i], t[j] = t[j], t[i] end
+    local function length() return n end
+    local cmp = h.cmp and
+        function(i, j) return h.cmp(t[i], t[j]) end or
+        function(i, j) return t[i] < t[j] end
+    local push, pop, rebalance = heap.makeheap(add, rem, swap, length, cmp)
+
+    local function get(i)
+        assert(i >= 1 and i <= n, "invalid index")
+        return t[i]
+    end
+    function h:push(v)
+        assert(v ~= nil, "invalid value")
+        push(v)
+    end
+    function h:pop(i)
+        assert(n > 0, "buffer underflow")
+        local v = get(i or 1)
+        pop(i or 1)
+        return v
+    end
+    function h:peek(i)
+        return get(i or 1)
+    end
+    function h:replace(i, v)
+        assert(i >= 1 and i <= n, "invalid index")
+        t[i] = v
+        rebalance(i)
+    end
+    h.length = length
+    return h
+end
+
+-- return module: heap
+return heap
diff --git a/xmake/core/base/scheduler.lua b/xmake/core/base/scheduler.lua
index a2745c6e6..95e727258 100644
--- a/xmake/core/base/scheduler.lua
+++ b/xmake/core/base/scheduler.lua
@@ -147,6 +147,7 @@ end
 -- sleep some times (ms)
 function scheduler:sleep(ms)
 
+    print(require("sys"))
     print("sleep", ms)
 
     self:_co_wait()
diff --git a/xmake/core/sandbox/modules/import/core/base/heap.lua b/xmake/core/sandbox/modules/import/core/base/heap.lua
new file mode 100644
index 000000000..5fc4bb2ce
--- /dev/null
+++ b/xmake/core/sandbox/modules/import/core/base/heap.lua
@@ -0,0 +1,22 @@
+--!A cross-platform build utility based on Lua
+--
+-- Licensed under the Apache License, Version 2.0 (the "License");
+-- you may not use this file except in compliance with the License.
+-- You may obtain a copy of the License at
+--
+--     http://www.apache.org/licenses/LICENSE-2.0
+--
+-- Unless required by applicable law or agreed to in writing, software
+-- distributed under the License is distributed on an "AS IS" BASIS,
+-- WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+-- See the License for the specific language governing permissions and
+-- limitations under the License.
+-- 
+-- Copyright (C) 2015 - 2019, TBOOX Open Source Group.
+--
+-- @author      ruki
+-- @file        heap.lua
+--
+
+-- return module
+return require("base/heap")