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 = 
'1.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

#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

#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

#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