diff options
author | Karl Berry <karl@freefriends.org> | 2014-02-27 00:01:50 +0000 |
---|---|---|
committer | Karl Berry <karl@freefriends.org> | 2014-02-27 00:01:50 +0000 |
commit | 90ae413a94da014dbf7a6a8ab584f7c668483a5a (patch) | |
tree | 4e0528a2b2fb2004988e7fc804ea2f1354f1f5d5 /Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/lib/PriorityQueue.lua | |
parent | 800cc56380d1edfe567a6a66bef13e8950eb2b0c (diff) |
pgf 3.0.0
git-svn-id: svn://tug.org/texlive/trunk@33057 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/lib/PriorityQueue.lua')
-rw-r--r-- | Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/lib/PriorityQueue.lua | 342 |
1 files changed, 342 insertions, 0 deletions
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/lib/PriorityQueue.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/lib/PriorityQueue.lua new file mode 100644 index 00000000000..7b93c755c56 --- /dev/null +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/lib/PriorityQueue.lua @@ -0,0 +1,342 @@ +-- Copyright 2011 by Jannis Pohlmann +-- Copyright 2012 by Till Tantau +-- +-- This file may be distributed an/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + +-- @release $Header: /cvsroot/pgf/pgf/generic/pgf/graphdrawing/lua/pgf/gd/lib/PriorityQueue.lua,v 1.1 2012/11/27 17:24:26 tantau Exp $ + + + +--- +-- A PriorityQueue supports operations for quickly finding the minimum from a set of elements +-- +-- Its implementation is based on (simplified) Fibonacci heaps. +local PriorityQueue = {} +PriorityQueue.__index = PriorityQueue + + +-- Namespace +local lib = require "pgf.gd.lib" +lib.PriorityQueue = PriorityQueue + + + +-- Local declarations +local FibonacciHeap = {} +local FibonacciHeapNode = {} + + + + +--- Creates a new priority queue +-- +-- @return The newly created queue + +function PriorityQueue.new() + local queue = { + heap = FibonacciHeap.new(), + nodes = {}, + values = {}, + } + setmetatable(queue, PriorityQueue) + return queue +end + + + +--- Add an element with a certain priority to the queue +-- +-- @param value An object +-- @param priority Its priority + +function PriorityQueue:enqueue(value, priority) + local node = self.heap:insert(priority) + self.nodes[value] = node + self.values[node] = value +end + + + +--- Removes the element with the minimum priority from the queue +-- +-- @return The element with the minimum priority + +function PriorityQueue:dequeue() + local node = self.heap:extractMinimum() + + if node then + local value = self.values[node] + self.nodes[value] = nil + self.values[node] = nil + return value + else + return nil + end +end + + + +--- Lower the priority of an element of a queue +-- +-- @param value An object +-- @param priority A new priority, which must be lower than the old priority + +function PriorityQueue:updatePriority(value, priority) + local node = self.nodes[value] + assert(node, 'updating the priority of ' .. tostring(value) .. ' failed because it is not in the priority queue') + self.heap:updateValue(node, priority) +end + + + +--- Tests, whether the queue is empty +-- +-- @return True, if the queue is empty + +function PriorityQueue:isEmpty() + return #self.heap.trees == 0 +end + + + + + + +-- Internals: An implementation of fibonacci heaps. +FibonacciHeap.__index = FibonacciHeap + + +function FibonacciHeap.new() + local heap = { + trees = trees or {}, + minimum = nil, + } + setmetatable(heap, FibonacciHeap) + return heap +end + + + +function FibonacciHeap:insert(value) + local node = FibonacciHeapNode.new(value) + local heap = FibonacciHeap.new() + table.insert(heap.trees, node) + self:merge(heap) + return node +end + + + +function FibonacciHeap:merge(other) + for _, tree in ipairs(other.trees) do + table.insert(self.trees, tree) + end + self:updateMinimum() +end + + + +function FibonacciHeap:extractMinimum() + if self.minimum then + local minimum = self:removeTableElement(self.trees, self.minimum) + + for _, child in ipairs(minimum.children) do + child.root = child + table.insert(self.trees, child) + end + + local same_degrees_found = true + while same_degrees_found do + same_degrees_found = false + + local degrees = {} + + for _, root in ipairs(self.trees) do + local degree = root:getDegree() + + if degrees[degree] then + if root.value < degrees[degree].value then + self:linkRoots(root, degrees[degree]) + else + self:linkRoots(degrees[degree], root) + end + + degrees[degree] = nil + same_degrees_found = true + break + else + degrees[degree] = root + end + end + end + + self:updateMinimum() + + return minimum + end +end + + + +function FibonacciHeap:updateValue(node, value) + local old_value = node.value + local new_value = value + + if new_value <= old_value then + self:decreaseValue(node, value) + else + assert(false, 'FibonacciHeap:increaseValue is not implemented yet') + end +end + + + +function FibonacciHeap:decreaseValue(node, value) + assert(value <= node.value) + + node.value = value + + if node.value < node.parent.value then + local parent = node.parent + self:cutFromParent(node) + + if not parent:isRoot() then + if parent.marked then + self:cutFromParent(parent) + else + parent.marked = true + end + end + end + + if node.value < self.minimum.value then + self.minimum = node + end +end + + + +function FibonacciHeap:delete(node) + self:decreaseValue(node, -math.huge) + self:extractMinimum() +end + + + +function FibonacciHeap:linkRoots(root, child) + child.root = root + child.parent = root + + child = self:removeTableElement(self.trees, child) + table.insert(root.children, child) + + return root +end + + + +function FibonacciHeap:cutFromParent(node) + local parent = node.parent + + node.root = node + node.parent = node + node.marked = false + + node = self:removeTableElement(parent.children, node) + table.insert(self.trees, node) +end + + + +function FibonacciHeap:updateMinimum() + self.minimum = self.trees[1] + + for _, root in ipairs(self.trees) do + if root.value < self.minimum.value then + self.minimum = root + end + end +end + + + +function FibonacciHeap:removeTableElement(input_table, element) + for i = 1, #input_table do + if input_table[i] == element then + return table.remove(input_table, i) + end + end +end + + + + +-- Now come the nodes + +FibonacciHeapNode.__index = FibonacciHeapNode + +function FibonacciHeapNode.new(value, root, parent) + local node = { + value = value, + children = {}, + marked = false, + root = nil, + parent = nil, + } + setmetatable(node, FibonacciHeapNode) + + if root then + node.root = root + node.parent = parent + else + node.root = node + node.parent = node + end + + return node +end + +function FibonacciHeapNode:addChild(value) + local child = FibonacciHeapNode.new(value, self.root, self) + table.insert(self.children, child) +end + +function FibonacciHeapNode:getDegree() + return #self.children +end + + + +function FibonacciHeapNode:setRoot(root) + self.root = root + + if root == self then + self.parent = root + end + + if #self.children > 0 then + for _, child in ipairs(self.children) do + child.root = root + end + end +end + + + +function FibonacciHeapNode:isRoot() + return self.root == self +end + + + + + + +-- done + +return PriorityQueue
\ No newline at end of file |