Class: Rangeable

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/rangeable.rb,
lib/rangeable/slot.rb,
lib/rangeable/version.rb,
lib/rangeable/interval.rb,
lib/rangeable/disjoint_set.rb,
lib/rangeable/boundary_index.rb

Overview

Defined as a class because the main ‘Rangeable` symbol in `rangeable.rb` is a class. We declare it the same way here so that requiring this file alone (e.g. from the gemspec) does not lock the symbol into being a module.

Defined Under Namespace

Modules: Refinements Classes: BoundaryIndex, DisjointSet, Interval, InvalidIntervalError, Slot

Constant Summary collapse

TransitionEvent =

‘Rangeable::TransitionEvent` is the public alias for the Struct defined inside the index. Re-exposed here so callers don’t need to reach through ‘BoundaryIndex` to reference its type.

::Rangeable::BoundaryIndex::TransitionEvent
EMPTY_ACTIVE =

Frozen empty Array we hand back from ‘[]` when the coordinate is outside every segment. Avoids re-allocating an empty Array per query.

[].freeze
VERSION = 
'2.0.0'

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Rangeable

Build a fresh empty container. RFC §3.1.



32
33
34
35
36
37
38
 
# File 'lib/rangeable.rb', line 32

def initialize
  @intervals       = {}     # element => DisjointSet
  @insertion_order = []     # Array<element> in first-insert order
  @ord             = {}     # element => Integer (1-based)
  @version         = 0
  @event_index     = nil    # BoundaryIndex or nil (lazy)
end

Instance Attribute Details

#version ⇒ Object (readonly)

Returns the value of attribute version.



29
30
31
 
# File 'lib/rangeable.rb', line 29

def version
  @version
end

Class Method Details

.empty ⇒ Object

Sugar: ‘Rangeable.empty` matches the RFC §3.1 alias.



41
42
43
 
# File 'lib/rangeable.rb', line 41

def self.empty
  new
end

.range_of(element, from:) ⇒ Object

Sugar form: ‘Rangeable.range_of(element, from: r)`. RFC §3.4.



178
179
180
 
# File 'lib/rangeable.rb', line 178

def self.range_of(element, from:)
  from.get_range(element)
end

Instance Method Details

#[](i) ⇒ Object Also known as: active_at_index

Active-element list at ‘i`. RFC §3.3. O(log |segments| + r) once the index is built.

Hot path: we inline the segment bsearch here (instead of going through a private helper or method dispatch into BoundaryIndex#segment_at) so ‘r` stays allocation-free apart from the unavoidable `Slot` envelope. The cached active array on the segment is already frozen, so `Slot.new` does not duplicate it (see `Slot#initialize`).



82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
 
# File 'lib/rangeable.rb', line 82

def [](i)
  ensure_event_index_fresh
  segs = @event_index.segments
  idx = segs.bsearch_index { |seg| seg.hi >= i }
  if idx
    seg = segs[idx]
    if seg.lo <= i
      Slot.new(seg.active)
    else
      Slot.new(EMPTY_ACTIVE)
    end
  else
    Slot.new(EMPTY_ACTIVE)
  end
end

#active_at(index:) ⇒ Object

Same as ‘[]` but spelled out to match RFC §3.3.



100
101
102
 
# File 'lib/rangeable.rb', line 100

def active_at(index:)
  self[index]
end

#clear ⇒ Object Also known as: remove_all

Reset the container to its empty state. RFC §6.8. Idempotent on an already-empty container (no version bump).



241
242
243
244
245
246
247
248
249
250
 
# File 'lib/rangeable.rb', line 241

def clear
  return self if @insertion_order.empty?  # §4.10 (N3) idempotence.

  @intervals       = {}
  @insertion_order = []
  @ord             = {}
  @version += 1
  @event_index = nil
  self
end

#copy ⇒ Object Also known as: dup, clone

Deep copy of the entire container per RFC §3.5.1. Mutation on the copy MUST NOT affect this instance and vice versa.



166
167
168
169
170
171
172
173
 
# File 'lib/rangeable.rb', line 166

def copy
  dup_instance = self.class.new
  @insertion_order.each do |element|
    dup_instance.send(:replant, element, @intervals[element], @ord[element])
  end
  dup_instance.send(:set_version_after_copy, @version)
  dup_instance
end

#count ⇒ Object Also known as: size, length

Number of distinct equivalence-class elements ever inserted. RFC §3.5.1.



142
143
144
 
# File 'lib/rangeable.rb', line 142

def count
  @insertion_order.length
end

#difference(other) ⇒ Object Also known as: -, subtract

Per-element ‘R_self(e) ∖ R_other(e)`. Empty results eagerly pruned. Insertion-order: preserve self’s order over surviving keys. RFC §6.12.

Raises:

  • (ArgumentError) 


347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
 
# File 'lib/rangeable.rb', line 347

def difference(other)
  raise ArgumentError, "expected Rangeable, got #{other.class}" unless other.is_a?(Rangeable)

  out = self.class.new

  @insertion_order.each do |element|
    list_self = @intervals[element].entries
    other_set = other.send(:intervals_internal)[element]
    remaining =
      if other_set.nil? || other_set.empty?
        list_self.dup
      else
        DisjointSet.subtract_disjoint_lists(list_self, other_set.entries)
      end
    next if remaining.empty?  # eager prune.

    out.send(:install_element, element, DisjointSet.from_entries(remaining))
  end

  out
end

#difference!(other) ⇒ Object Also known as: subtract! 



430
431
432
 
# File 'lib/rangeable.rb', line 430

def difference!(other)
  swap_with(difference(other))
end

#each(&block) ⇒ Object

Iterate ‘(element, ranges)` pairs in insertion-order ascending. RFC §3.5.1.



154
155
156
157
158
159
160
161
 
# File 'lib/rangeable.rb', line 154

def each(&block)
  return enum_for(:each) unless block_given?

  @insertion_order.each do |element|
    yield element, @intervals[element].to_pairs
  end
  self
end

#empty? ⇒ Boolean

‘count == 0`. RFC §3.5.1.

Returns:

  • (Boolean) 


149
150
151
 
# File 'lib/rangeable.rb', line 149

def empty?
  @insertion_order.empty?
end

#get_range(element) ⇒ Object Also known as: range_of, get_range_of

Merged ranges for ‘element` as `[[lo, hi], …]`. RFC §3.4. Returns an empty Array when the element has never been inserted.



106
107
108
109
110
111
 
# File 'lib/rangeable.rb', line 106

def get_range(element)
  set = @intervals[element]
  return [] unless set

  set.to_pairs
end

#insert(element, start:, end:) ⇒ Object

Insert ‘element` covering `[start, end_]` (closed interval). Idempotent by RFC §3.2: re-inserting a sub-range that is already fully contained leaves the container unchanged and does NOT bump version.

The RFC reference uses the keyword ‘end:`, but Ruby treats `end` inside method headers as a soft-keyword that is fine in keyword-arg position. We accept it that way to match the RFC API exactly.

Raises:



52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
 
# File 'lib/rangeable.rb', line 52

def insert(element, start:, end:)
  end_ = binding.local_variable_get(:end)
  raise InvalidIntervalError, "start (#{start}) > end (#{end_})" if start > end_

  e = freeze_for_insert(element)

  set = @intervals[e]
  if set.nil?
    set = DisjointSet.new
    @intervals[e] = set
    @insertion_order << e
    @ord[e] = @insertion_order.length
  end

  result = set.insert(start, end_)
  if result == DisjointSet::MUTATED
    @version += 1
    @event_index = nil
  end
  self
end

#intersect(other) ⇒ Object Also known as: &, intersection

Per-element ‘R_self(e) ∩ R_other(e)` for keys in both. Empty results are eagerly pruned (§4.10). Insertion-order: preserve self’s order over surviving keys. RFC §6.11.

Raises:

  • (ArgumentError) 


323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
 
# File 'lib/rangeable.rb', line 323

def intersect(other)
  raise ArgumentError, "expected Rangeable, got #{other.class}" unless other.is_a?(Rangeable)

  out = self.class.new

  @insertion_order.each do |element|
    other_set = other.send(:intervals_internal)[element]
    next unless other_set  # not in other ⇒ drop.

    list_self  = @intervals[element].entries
    list_other = other_set.entries
    intersected = DisjointSet.intersect_disjoint_lists(list_self, list_other)
    next if intersected.empty?  # eager prune.

    out.send(:install_element, element, DisjointSet.from_entries(intersected))
  end

  out
end

#intersect!(other) ⇒ Object Also known as: intersection! 



425
426
427
 
# File 'lib/rangeable.rb', line 425

def intersect!(other)
  swap_with(intersect(other))
end

#remove(element, start:, end:) ⇒ Object

Remove the closed interval ‘[start_, end_]` from `R(element)`. RFC §6.6. Splits an entry if the cut lies strictly inside it. Idempotent (no-op, no version bump) when `element` is absent or no entry overlaps the cut window. Eagerly prunes `element` if its `R(e)` becomes empty (§4.10 N1).

Raises:



200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
 
# File 'lib/rangeable.rb', line 200

def remove(element, start:, end:)
  end_ = binding.local_variable_get(:end)
  raise InvalidIntervalError, "start (#{start}) > end (#{end_})" if start > end_

  set = @intervals[element]
  return self if set.nil?  # §4.10 (N3): no R(e) ⇒ no-op, no bump.

  result = set.remove_subrange(start, end_)
  return self if result == DisjointSet::IDEMPOTENT

  # Eager pruning (§4.10 N1) when R(e) is now ∅.
  excise_element(element) if set.empty?

  @version += 1
  @event_index = nil
  self
end

#remove_element(element) ⇒ Object Also known as: delete

Fully remove ‘element` from the container. RFC §6.7. Idempotent on a never-inserted element. Eagerly excises and densely renumbers `ord`.



220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
 
# File 'lib/rangeable.rb', line 220

def remove_element(element)
  # Hash#delete returns the deleted value or nil. nil ⇒ key absent ⇒
  # no-op per §4.10 (N3); MUST NOT bump version.
  return self unless @intervals.delete(element)

  idx = @insertion_order.index(element)
  @insertion_order.delete_at(idx)
  @ord.delete(element)
  # Renumber ord densely for elements that moved up by one position.
  (idx...@insertion_order.length).each do |k|
    @ord[@insertion_order[k]] = k + 1
  end

  @version += 1
  @event_index = nil
  self
end

#remove_ranges(start:, end:) ⇒ Object

Subtract ‘[start_, end_]` from every element’s ‘R(e)`. RFC §6.9. Atomic: at most one version bump for the entire op. Eagerly prunes any element whose `R(e)` becomes empty. No-op (no bump) if no element overlaps the cut window.

Raises:



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
 
# File 'lib/rangeable.rb', line 257

def remove_ranges(start:, end:)
  end_ = binding.local_variable_get(:end)
  raise InvalidIntervalError, "start (#{start}) > end (#{end_})" if start > end_

  any_change = false
  # Iterate a snapshot of @insertion_order: we may delete from @intervals
  # mid-loop. We do NOT mutate @insertion_order in this loop — the §6.9
  # pseudocode defers the rebuild to step 4 to avoid O(E²) delete_at cost.
  @insertion_order.each do |element|
    set = @intervals[element]
    result = set.remove_subrange(start, end_)
    next if result == DisjointSet::IDEMPOTENT

    any_change = true
    @intervals.delete(element) if set.empty?
  end

  return self unless any_change  # §4.10 (N3) no-op.

  # Step 4: single-pass rebuild of insertion_order and dense ord.
  @insertion_order = @insertion_order.select { |e| @intervals.key?(e) }
  @ord = {}
  @insertion_order.each_with_index { |e, k| @ord[e] = k + 1 }

  @version += 1
  @event_index = nil
  self
end

#symmetric_difference(other) ⇒ Object Also known as: ^

Per-element ‘R_self(e) △ R_other(e) = (self∖other) ∪ (other∖self)`. Empty results eagerly pruned. Insertion-order: preserve self’s order for ‘e ∈ keys(self)`; tail-append `e ∈ keys(other) ∖ keys(self)` in other’s order. RFC §6.13.

‘merge_disjoint_lists` (NOT sorted concat) is required because the two one-sided residuals can be integer-adjacent (RFC §10.B Test #34 worked example: `R_self=, R_other=` ⇒ a=, b=, adjacent at 5+1==6, must collapse to [(0,10)]).

Raises:

  • (ArgumentError) 


380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
 
# File 'lib/rangeable.rb', line 380

def symmetric_difference(other)
  raise ArgumentError, "expected Rangeable, got #{other.class}" unless other.is_a?(Rangeable)

  out = self.class.new

  # Step 1: self-primary keys.
  @insertion_order.each do |element|
    list_self  = @intervals[element].entries
    other_set  = other.send(:intervals_internal)[element]
    list_other = other_set ? other_set.entries : EMPTY_ACTIVE
    a = DisjointSet.subtract_disjoint_lists(list_self,  list_other)
    b = DisjointSet.subtract_disjoint_lists(list_other, list_self)
    sym = DisjointSet.merge_disjoint_lists(a, b)
    next if sym.empty?  # eager prune.

    out.send(:install_element, element, DisjointSet.from_entries(sym))
  end

  # Step 2: other-only keys.
  other.send(:insertion_order_internal).each do |element|
    next if @intervals.key?(element)

    other_entries = other.send(:intervals_internal)[element].entries
    next if other_entries.empty?  # defensive; (I1.4) makes this unreachable.

    out.send(:install_element, element, DisjointSet.from_entries(other_entries.dup))
  end

  out
end

#symmetric_difference!(other) ⇒ Object 



435
436
437
 
# File 'lib/rangeable.rb', line 435

def symmetric_difference!(other)
  swap_with(symmetric_difference(other))
end

#transitions(over:) ⇒ Object

Transitions (open / close events) within an inclusive coordinate range. Accepts a Ruby ‘Range` (inclusive or exclusive). RFC §3.5.

Raises:



117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
 
# File 'lib/rangeable.rb', line 117

def transitions(over:)
  raise InvalidIntervalError, "transitions range must be a Range" unless over.is_a?(Range)

  lo = over.begin
  hi = over.end
  raise InvalidIntervalError, "open-ended begin not supported" if lo.nil?

  # Normalise exclusive end (`a...b` ⇒ inclusive end `b - 1`).
  hi = hi - 1 if !hi.nil? && over.exclude_end?

  # Open-ended top (`a..nil`) means +∞ ⇒ include all events.
  if hi.nil?
    raise InvalidIntervalError, "lo (#{lo}) > hi (nil)" if lo.nil?
  else
    raise InvalidIntervalError, "lo (#{lo}) > hi (#{hi})" if lo > hi
  end

  ensure_event_index_fresh
  upper = hi.nil? ? nil : hi + 1
  @event_index.events_in_range(lo, upper).map do |ev|
    TransitionEvent.new(ev.coordinate, ev.kind, ev.element, ev.ord)
  end
end

#union(other) ⇒ Object Also known as: |

Per-element ‘R_self(e) ∪ R_other(e)`. Returns a fresh `Rangeable` with `version == 0`. Insertion-order rule: preserve `self`’s, tail-append keys ∈ ‘other` ∖ `self` in `other`’s insertion-order order. RFC §6.10.

Raises:

  • (ArgumentError) 


293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
 
# File 'lib/rangeable.rb', line 293

def union(other)
  raise ArgumentError, "expected Rangeable, got #{other.class}" unless other.is_a?(Rangeable)

  out = self.class.new

  # Step 1: walk self's insertion_order; merge with other if shared key.
  @insertion_order.each do |element|
    list_self  = @intervals[element].entries
    other_set  = other.send(:intervals_internal)[element]
    list_other = other_set ? other_set.entries : EMPTY_ACTIVE
    merged = DisjointSet.merge_disjoint_lists(list_self, list_other)
    # length(merged) > 0 is guaranteed because list_self is non-empty (I1.4).
    out.send(:install_element, element, DisjointSet.from_entries(merged))
  end

  # Step 2: tail-append keys ∈ other ∖ self in other's insertion order.
  other.send(:insertion_order_internal).each do |element|
    next if @intervals.key?(element)

    other_entries = other.send(:intervals_internal)[element].entries
    out.send(:install_element, element, DisjointSet.from_entries(other_entries.dup))
  end

  out
end

#union!(other) ⇒ Object

Mutating set ops (Ruby ‘!` convention). All four ALWAYS return self for chain-friendliness. Each bumps `version` exactly once iff the result differs structurally from `self` (per §6.10–§6.13 idempotence dual). Implementation strategy: build the new container via the non-mutating form (copy-then-swap), then compare to self. If structurally identical, discard and skip the bump.



421
422
423
 
# File 'lib/rangeable.rb', line 421

def union!(other)
  swap_with(union(other))
end