Module: RelativePositioning

Extended by:
ActiveSupport::Concern
Included in:
Analytics::CycleAnalytics::Stage, DesignManagement::Design, Issue
Defined in:
app/models/concerns/relative_positioning.rb

Overview

This module makes it possible to handle items as a list, where the order of items can be easily altered Requirements:

The model must have the following named columns:

- id: integer
- relative_position: integer

The model must support a concept of siblings via a child->parent relationship, to enable rebalancing and `GROUP BY` in queries.

  • example: project -> issues, project is the parent relation (issues table has a parent_id column)

Two class methods must be defined when including this concern:

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

Constant Summary collapse

STEPS = 
10
IDEAL_DISTANCE = 
2**(STEPS - 1) + 1
MIN_POSITION = 
Gitlab::Database::MIN_INT_VALUE
START_POSITION = 
0
MAX_POSITION = 
Gitlab::Database::MAX_INT_VALUE
MAX_GAP = 
IDEAL_DISTANCE * 2
MIN_GAP = 
2
NoSpaceLeft = 
Class.new(StandardError)

Instance Method Summary collapse

Instance Method Details

#max_relative_position(&block) ⇒ Object 


205
206
207
 
# File 'app/models/concerns/relative_positioning.rb', line 205

def max_relative_position(&block)
  calculate_relative_position('MAX', &block)
end

#min_relative_position(&block) ⇒ Object 


201
202
203
 
# File 'app/models/concerns/relative_positioning.rb', line 201

def min_relative_position(&block)
  calculate_relative_position('MIN', &block)
end

#move_after(before = self) ⇒ Object 


263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
 
# File 'app/models/concerns/relative_positioning.rb', line 263

def move_after(before = self)
  pos_before = before.relative_position
  pos_after = before.next_relative_position(ignoring: self)

  if pos_before == MAX_POSITION || gap_too_small?(pos_after, pos_before)
    gap = before.send(:find_next_gap_after) # rubocop:disable GitlabSecurity/PublicSend

    if gap.nil?
      before.move_sequence_before(true)
      pos_before = before.reset.relative_position
    else
      before.move_sequence_after(next_gap: gap)
      pos_after += optimum_delta_for_gap(gap)
    end
  end

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

#move_before(after = self) ⇒ Object 


282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
 
# File 'app/models/concerns/relative_positioning.rb', line 282

def move_before(after = self)
  pos_after = after.relative_position
  pos_before = after.prev_relative_position(ignoring: self)

  if pos_after == MIN_POSITION || gap_too_small?(pos_before, pos_after)
    gap = after.send(:find_next_gap_before) # rubocop:disable GitlabSecurity/PublicSend

    if gap.nil?
      after.move_sequence_after(true)
      pos_after = after.reset.relative_position
    else
      after.move_sequence_before(next_gap: gap)
      pos_before -= optimum_delta_for_gap(gap)
    end
  end

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

#move_between(before, after) ⇒ Object 


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
 
# File 'app/models/concerns/relative_positioning.rb', line 235

def move_between(before, after)
  return move_after(before) unless after
  return move_before(after) unless before

  before, after = after, before if after.relative_position < before.relative_position

  pos_left = before.relative_position
  pos_right = after.relative_position

  if pos_right - pos_left < MIN_GAP
    # Not enough room! Make space by shifting all previous elements to the left
    # if there is enough space, else to the right
    gap = after.send(:find_next_gap_before) # rubocop:disable GitlabSecurity/PublicSend

    if gap.present?
      after.move_sequence_before(next_gap: gap)
      pos_left -= optimum_delta_for_gap(gap)
    else
      before.move_sequence_after
      pos_right = after.reset.relative_position
    end
  end

  new_position = self.class.position_between(pos_left, pos_right)

  self.relative_position = new_position
end

#move_sequence_after(include_self = false, next_gap: find_next_gap_after) ⇒ Object

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Moves the sequence after the current item to the middle of the next gap For example, we have:

8 . 10 [11] 12 13 14 15 . . . . . 21
            -----------

This moves the sequence [12 13 14 15] to [15 16 17 18], so we have:

8 . 10 [11] . . . 15 16 17 18 . . 21
                  -----------

Creating a gap to the right of the current item. We can understand this as dividing the 5 spaces between 15 and 21 into two smaller gaps of 3 and 2.

If `include_self` is true, the current item will also be moved, creating a gap to the left of the current item:

8 . 10 . . . [14] 15 16 17 18 . . 21
             ----------------

As an optimization, the gap can be precalculated and passed to this method.

Raises:


387
388
389
390
391
392
393
 
# File 'app/models/concerns/relative_positioning.rb', line 387

def move_sequence_after(include_self = false, next_gap: find_next_gap_after)
  raise NoSpaceLeft unless next_gap.present?

  delta = optimum_delta_for_gap(next_gap)

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

#move_sequence_before(include_self = false, next_gap: find_next_gap_before) ⇒ Object

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Moves the sequence before the current item to the middle of the next gap For example, we have

5 . . . . . 11 12 13 14 [15] 16 . 17
            -----------

This moves the sequence [11 12 13 14] to [8 9 10 11], so we have:

5 . . 8 9 10 11 . . . [15] 16 . 17
      ---------

Creating a gap to the left of the current item. We can understand this as dividing the 5 spaces between 5 and 11 into two smaller gaps of 2 and 3.

If `include_self` is true, the current item will also be moved, creating a gap to the right of the current item:

5 . . 8 9 10 11 [14] . . . 16 . 17
      --------------

As an optimization, the gap can be precalculated and passed to this method.

Raises:


355
356
357
358
359
360
361
 
# File 'app/models/concerns/relative_positioning.rb', line 355

def move_sequence_before(include_self = false, next_gap: find_next_gap_before)
  raise NoSpaceLeft unless next_gap.present?

  delta = optimum_delta_for_gap(next_gap)

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

#move_to_end ⇒ Object 


301
302
303
304
305
306
307
308
309
310
311
312
313
314
 
# File 'app/models/concerns/relative_positioning.rb', line 301

def move_to_end
  max_pos = max_relative_position

  if max_pos.nil?
    self.relative_position = START_POSITION
  elsif gap_too_small?(max_pos, MAX_POSITION + 1)
    max = relative_siblings.order(Gitlab::Database.nulls_last_order('relative_position', 'DESC')).first
    max.move_sequence_before(true)
    max.reset
    self.relative_position = self.class.position_between(max.relative_position, MAX_POSITION + 1)
  else
    self.relative_position = self.class.position_between(max_pos, MAX_POSITION + 1)
  end
end

#move_to_start ⇒ Object 


316
317
318
319
320
321
322
323
324
325
326
327
328
329
 
# File 'app/models/concerns/relative_positioning.rb', line 316

def move_to_start
  min_pos = min_relative_position

  if min_pos.nil?
    self.relative_position = START_POSITION
  elsif gap_too_small?(min_pos, MIN_POSITION - 1)
    min = relative_siblings.order(Gitlab::Database.nulls_last_order('relative_position', 'ASC')).first
    min.move_sequence_after(true)
    min.reset
    self.relative_position = self.class.position_between(MIN_POSITION - 1, min.relative_position)
  else
    self.relative_position = self.class.position_between(MIN_POSITION - 1, min_pos)
  end
end

#next_relative_position(ignoring: nil) ⇒ Object 


222
223
224
225
226
227
228
229
230
231
232
233
 
# File 'app/models/concerns/relative_positioning.rb', line 222

def next_relative_position(ignoring: nil)
  next_pos = nil

  if self.relative_position
    next_pos = min_relative_position do |relation|
      relation = relation.id_not_in(ignoring.id) if ignoring.present?
      relation.where('relative_position > ?', self.relative_position)
    end
  end

  next_pos
end

#prev_relative_position(ignoring: nil) ⇒ Object 


209
210
211
212
213
214
215
216
217
218
219
220
 
# File 'app/models/concerns/relative_positioning.rb', line 209

def prev_relative_position(ignoring: nil)
  prev_pos = nil

  if self.relative_position
    prev_pos = max_relative_position do |relation|
      relation = relation.id_not_in(ignoring.id) if ignoring.present?
      relation.where('relative_position < ?', self.relative_position)
    end
  end

  prev_pos
end