Read about our upcoming Code of Conduct on this issue

relative_positioning.rb 7.87 KB
Newer Older
1
2
# frozen_string_literal: true

Adam Hegyi's avatar
Adam Hegyi committed
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# This module makes it possible to handle items as a list, where the order of items can be easily altered
# Requirements:
#
# - Only works for ActiveRecord models
# - relative_position integer field must present on the model
# - This module uses GROUP BY: the model should have a parent relation, example: project -> issues, project is the parent relation (issues table has a parent_id column)
#
# Setup like this in the body of your class:
#
#     include RelativePositioning
#
#     # base query used for the position calculation
#     def self.relative_positioning_query_base(issue)
#       where(deleted: false)
#     end
#
#     # column that should be used in GROUP BY
#     def self.relative_positioning_parent_column
#       :project_id
#     end
#
24
25
26
module RelativePositioning
  extend ActiveSupport::Concern

27
  MIN_POSITION = 0
28
  START_POSITION = Gitlab::Database::MAX_INT_VALUE / 2
29
  MAX_POSITION = Gitlab::Database::MAX_INT_VALUE
30
  IDEAL_DISTANCE = 500
31

32
  class_methods do
33
    def move_nulls_to_end(objects)
34
35
      objects = objects.reject(&:relative_position)

36
37
38
39
      return if objects.empty?

      max_relative_position = objects.first.max_relative_position

40
41
      self.transaction do
        objects.each do |object|
42
          relative_position = position_between(max_relative_position || START_POSITION, MAX_POSITION)
43
44
          object.relative_position = relative_position
          max_relative_position = relative_position
45
          object.save(touch: false)
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
        end
      end
    end

    # This method takes two integer values (positions) and
    # calculates the position between them. The range is huge as
    # the maximum integer value is 2147483647. We are incrementing position by IDEAL_DISTANCE * 2 every time
    # when we have enough space. If distance is less then IDEAL_DISTANCE we are calculating an average number
    def position_between(pos_before, pos_after)
      pos_before ||= MIN_POSITION
      pos_after ||= MAX_POSITION

      pos_before, pos_after = [pos_before, pos_after].sort

      halfway = (pos_after + pos_before) / 2
      distance_to_halfway = pos_after - halfway

      if distance_to_halfway < IDEAL_DISTANCE
        halfway
      else
        if pos_before == MIN_POSITION
          pos_after - IDEAL_DISTANCE
        elsif pos_after == MAX_POSITION
          pos_before + IDEAL_DISTANCE
        else
          halfway
        end
      end
    end
  end

77
78
  def min_relative_position(&block)
    calculate_relative_position('MIN', &block)
Felipe Artur's avatar
Felipe Artur committed
79
80
  end

81
82
  def max_relative_position(&block)
    calculate_relative_position('MAX', &block)
83
84
  end

85
86
87
88
  def prev_relative_position
    prev_pos = nil

    if self.relative_position
89
90
91
      prev_pos = max_relative_position do |relation|
        relation.where('relative_position < ?', self.relative_position)
      end
92
93
    end

94
    prev_pos
95
96
97
98
99
100
  end

  def next_relative_position
    next_pos = nil

    if self.relative_position
101
102
103
      next_pos = min_relative_position do |relation|
        relation.where('relative_position > ?', self.relative_position)
      end
104
105
    end

106
    next_pos
107
108
  end

109
  def move_between(before, after)
110
111
    return move_after(before) unless after
    return move_before(after) unless before
112

113
114
    # If there is no place to insert an item we need to create one by moving the item
    # before this and all preceding items until there is a gap
115
    before, after = after, before if after.relative_position < before.relative_position
116
    if (after.relative_position - before.relative_position) < 2
117
118
      after.move_sequence_before
      before.reset
119
120
    end

121
    self.relative_position = self.class.position_between(before.relative_position, after.relative_position)
122
123
124
  end

  def move_after(before = self)
125
    pos_before = before.relative_position
126
    pos_after = before.next_relative_position
127

128
    if pos_after && (pos_after - pos_before) < 2
129
      before.move_sequence_after
130
      pos_after = before.next_relative_position
131
132
    end

133
    self.relative_position = self.class.position_between(pos_before, pos_after)
134
135
  end

136
137
138
139
  def move_before(after = self)
    pos_after = after.relative_position
    pos_before = after.prev_relative_position

140
    if pos_before && (pos_after - pos_before) < 2
141
      after.move_sequence_before
142
      pos_before = after.prev_relative_position
143
144
    end

145
    self.relative_position = self.class.position_between(pos_before, pos_after)
146
147
  end

148
  def move_to_end
149
    self.relative_position = self.class.position_between(max_relative_position || START_POSITION, MAX_POSITION)
150
151
  end

152
  def move_to_start
153
    self.relative_position = self.class.position_between(min_relative_position || START_POSITION, MIN_POSITION)
154
155
  end

156
157
158
159
160
161
162
163
  # Moves the sequence before the current item to the middle of the next gap
  # For example, we have 5 11 12 13 14 15 and the current item is 15
  # This moves the sequence 11 12 13 14 to 8 9 10 11
  def move_sequence_before
    next_gap = find_next_gap_before
    delta = optimum_delta_for_gap(next_gap)

    move_sequence(next_gap[:start], relative_position, -delta)
164
165
  end

166
167
168
169
170
171
172
173
  # Moves the sequence after the current item to the middle of the next gap
  # For example, we have 11 12 13 14 15 21 and the current item is 11
  # This moves the sequence 12 13 14 15 to 15 16 17 18
  def move_sequence_after
    next_gap = find_next_gap_after
    delta = optimum_delta_for_gap(next_gap)

    move_sequence(relative_position, next_gap[:start], delta)
174
175
  end

176
177
178
179
180
181
182
183
184
185
186
187
188
  private

  # Supposing that we have a sequence of items: 1 5 11 12 13 and the current item is 13
  # This would return: `{ start: 11, end: 5 }`
  def find_next_gap_before
    items_with_next_pos = scoped_items
                            .select('relative_position AS pos, LEAD(relative_position) OVER (ORDER BY relative_position DESC) AS next_pos')
                            .where('relative_position <= ?', relative_position)
                            .order(relative_position: :desc)

    find_next_gap(items_with_next_pos).tap do |gap|
      gap[:end] ||= MIN_POSITION
    end
189
  end
190

191
192
193
194
195
196
197
198
199
200
201
  # Supposing that we have a sequence of items: 13 14 15 20 24 and the current item is 13
  # This would return: `{ start: 15, end: 20 }`
  def find_next_gap_after
    items_with_next_pos = scoped_items
                            .select('relative_position AS pos, LEAD(relative_position) OVER (ORDER BY relative_position ASC) AS next_pos')
                            .where('relative_position >= ?', relative_position)
                            .order(:relative_position)

    find_next_gap(items_with_next_pos).tap do |gap|
      gap[:end] ||= MAX_POSITION
    end
202
  end
203

204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
  def find_next_gap(items_with_next_pos)
    gap = self.class.from(items_with_next_pos, :items_with_next_pos)
                    .where('ABS(pos - next_pos) > 1 OR next_pos IS NULL')
                    .limit(1)
                    .pluck(:pos, :next_pos)
                    .first

    { start: gap[0], end: gap[1] }
  end

  def optimum_delta_for_gap(gap)
    delta = ((gap[:start] - gap[:end]) / 2.0).abs.ceil

    [delta, IDEAL_DISTANCE].min
  end

  def move_sequence(start_pos, end_pos, delta)
    scoped_items
      .where.not(id: self.id)
      .where('relative_position BETWEEN ? AND ?', start_pos, end_pos)
      .update_all("relative_position = relative_position + #{delta}")
  end
226
227
228
229

  def calculate_relative_position(calculation)
    # When calculating across projects, this is much more efficient than
    # MAX(relative_position) without the GROUP BY, due to index usage:
230
    # https://gitlab.com/gitlab-org/gitlab-foss/issues/54276#note_119340977
231
    relation = scoped_items
232
                 .order(Gitlab::Database.nulls_last_order('position', 'DESC'))
Adam Hegyi's avatar
Adam Hegyi committed
233
                 .group(self.class.relative_positioning_parent_column)
234
235
236
237
238
                 .limit(1)

    relation = yield relation if block_given?

    relation
Adam Hegyi's avatar
Adam Hegyi committed
239
      .pluck(self.class.relative_positioning_parent_column, Arel.sql("#{calculation}(relative_position) AS position"))
240
      .first&.last
241
  end
242
243
244
245

  def scoped_items
    self.class.relative_positioning_query_base(self)
  end
246
end