summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/Ranking.lua
blob: 6ed63b0249d1f901c3d1dd795ce420982a5d2737 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
-- 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$



--- The Ranking class is used by the Sugiyama algorithm to compute an
-- ordering on the nodes of a layer

local Ranking = {}
Ranking.__index = Ranking

-- Namespace
local layered = require "pgf.gd.layered"
layered.Ranking = Ranking


local lib = require "pgf.gd.lib"


-- TODO Jannis: document!


function Ranking.new()
  local ranking = {
    rank_to_nodes = {},
    node_to_rank = {},
    position_in_rank = {},
  }
  setmetatable(ranking, Ranking)
  return ranking
end



function Ranking:copy()
  local copied_ranking = Ranking.new()

  -- copy rank to nodes mapping
  for rank, nodes in pairs(self.rank_to_nodes) do
    copied_ranking.rank_to_nodes[rank] = lib.copy(self.rank_to_nodes[rank])
  end

  -- copy node to rank mapping
  copied_ranking.node_to_rank = lib.copy(self.node_to_rank)

  -- copy node to position in rank mapping
  copied_ranking.position_in_rank = lib.copy(self.position_in_rank)

  return copied_ranking
end



function Ranking:reset()
  self.rank_to_nodes = {}
  self.node_to_rank = {}
  self.position_in_rank = {}
end



function Ranking:getRanks()
  local ranks = {}
  for rank, nodes in pairs(self.rank_to_nodes) do
    table.insert(ranks, rank)
  end
  table.sort(ranks)
  return ranks
end



function Ranking:getRankSize(rank)
  if self.rank_to_nodes[rank] then
    return #self.rank_to_nodes[rank]
  else
    return 0
  end
end



function Ranking:getNodeInfo(node)
  return self:getRank(node), self:getRankPosition(node)
end



function Ranking:getNodes(rank)
  return self.rank_to_nodes[rank] or {}
end



function Ranking:getRank(node)
  return self.node_to_rank[node]
end



function Ranking:setRank(node, new_rank)
  local rank, pos = self:getNodeInfo(node)

  if rank == new_rank then
    return
  end

  if rank then
    for n = pos+1, #self.rank_to_nodes[rank] do
      local other_node = self.rank_to_nodes[rank][n]
      self.position_in_rank[other_node] = self.position_in_rank[other_node]-1
    end

    table.remove(self.rank_to_nodes[rank], pos)
    self.node_to_rank[node] = nil
    self.position_in_rank[node] = nil

    if #self.rank_to_nodes[rank] == 0 then
      self.rank_to_nodes[rank] = nil
    end
  end

  if new_rank then
    self.rank_to_nodes[new_rank] = self.rank_to_nodes[new_rank] or {}
    table.insert(self.rank_to_nodes[new_rank], node)
    self.node_to_rank[node] = new_rank
    self.position_in_rank[node] = #self.rank_to_nodes[new_rank]
  end
end



function Ranking:getRankPosition(node)
  return self.position_in_rank[node]
end



function Ranking:setRankPosition(node, new_pos)
  local rank, pos = self:getNodeInfo(node)

  assert((rank and pos) or ((not rank) and (not pos)))

  if pos == new_pos then
    return
  end

  if rank and pos then
    for n = pos+1, #self.rank_to_nodes[rank] do
      local other_node = self.rank_to_nodes[rank][n]
      self.position_in_rank[other_node] = self.position_in_rank[other_node]-1
    end

    table.remove(self.rank_to_nodes[rank], pos)
    self.node_to_rank[node] = nil
    self.position_in_rank[node] = nil
  end

  if new_pos then
    self.rank_to_nodes[rank] = self.rank_to_nodes[rank] or {}

    for n = new_pos+1, #self.rank_to_nodes[rank] do
      local other_node = self.rank_to_nodes[rank][new_pos]
      self.position_in_rank[other_node] = self.position_in_rank[other_node]+1
    end

    table.insert(self.rank_to_nodes[rank], node)
    self.node_to_rank[node] = rank
    self.position_in_rank[node] = new_pos
  end
end



function Ranking:normalizeRanks()

  -- get the current ranks
  local ranks = self:getRanks()

  local min_rank = ranks[1]
  local max_rank = ranks[#ranks]

  -- clear ranks
  self.rank_to_nodes = {}

  -- iterate over all nodes and rerank them manually
  for node in pairs(self.position_in_rank) do
    local rank, pos = self:getNodeInfo(node)
    local new_rank = rank - (min_rank - 1)

    self.rank_to_nodes[new_rank] = self.rank_to_nodes[new_rank] or {}
    self.rank_to_nodes[new_rank][pos] = node

    self.node_to_rank[node] = new_rank
  end
end



function Ranking:switchPositions(left_node, right_node)
  local left_rank = self.node_to_rank[left_node]
  local right_rank = self.node_to_rank[right_node]

  assert(left_rank == right_rank, 'only positions of nodes in the same rank can be switched')

  local left_pos = self.position_in_rank[left_node]
  local right_pos = self.position_in_rank[right_node]

  self.rank_to_nodes[left_rank][left_pos] = right_node
  self.rank_to_nodes[left_rank][right_pos] = left_node

  self.position_in_rank[left_node] = right_pos
  self.position_in_rank[right_node] = left_pos
end



function Ranking:reorderRank(rank, get_index_func, is_fixed_func)
  self:reorderTable(self.rank_to_nodes[rank], get_index_func, is_fixed_func)

  for n = 1, #self.rank_to_nodes[rank] do
    self.position_in_rank[self.rank_to_nodes[rank][n]] = n
  end
end



function Ranking:reorderTable(input, get_index_func, is_fixed_func)
  -- collect all allowed indices
  local allowed_indices = {}
  for n = 1, #input do
    if not is_fixed_func(n, input[n]) then
      table.insert(allowed_indices, n)
    end
  end

  -- collect all desired indices; for each of these desired indices,
  -- remember by which element it was requested
  local desired_to_real_indices = {}
  local sort_indices = {}
  for n = 1, #input do
    if not is_fixed_func(n, input[n]) then
      local index = get_index_func(n, input[n])
      if not desired_to_real_indices[index] then
        desired_to_real_indices[index] = {}
        table.insert(sort_indices, index)
      end
      table.insert(desired_to_real_indices[index], n)
    end
  end

  -- sort the desired indices
  table.sort(sort_indices)

  -- compute the final indices by counting the final indices generated
  -- prior to the current one and by mapping this number to the allowed
  -- index with the same number
  local final_indices = {}
  local n = 1
  for _,index in ipairs(sort_indices) do
    local real_indices = desired_to_real_indices[index]
    for _,real_index in ipairs(real_indices) do
      final_indices[real_index] = allowed_indices[n]
      n = n + 1
    end
  end

  -- flat-copy the input table so that we can still access the elements
  -- using their real index while overwriting the input table in-place
  local input_copy = lib.copy(input)

  -- move flexible elements to their final indices
  for old_index, new_index in pairs(final_indices) do
    input[new_index] = input_copy[old_index]
  end
end



-- Done

return Ranking