Class: Rangeable::BoundaryIndex

Inherits:
Object
  • Object
show all
Defined in:
lib/rangeable/boundary_index.rb

Overview

Lazy boundary-event index per RFC §5.2 / §6.3.

Built from a snapshot of the per-element interval map plus the insertion-order map ‘ord`. Carries:

* `events`   — sorted Array of TransitionEvent under §4.5 ordering.
* `segments` — sorted, disjoint Array of (seg_lo, seg_hi, frozen active)
               triples covering every coordinate at which the active
               set is non-empty. Active sets are frozen and sorted by
               `ord(e)` ascending.
* `version`  — snapshot of Rangeable.version at build time. The owner
               Rangeable invalidates the index by setting it to nil
               on any mutation; reads compare versions to decide
               whether to rebuild (T3 mutex pattern, §11).

‘nil` close coordinates encode +∞ for hi == Integer::MAX boundaries (§4.7 C4). Comparison against `nil` always treats it as greater than any finite Integer; we centralise that logic in `coord_lt?` / `coord_le?`.

Defined Under Namespace

Classes: Segment, TransitionEvent

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(events, segments, version) ⇒ BoundaryIndex

Returns a new instance of BoundaryIndex.



56
57
58
59
60
61
 
# File 'lib/rangeable/boundary_index.rb', line 56

def initialize(events, segments, version)
  @events   = events.freeze
  @segments = segments.freeze
  @version  = version
  freeze
end

Instance Attribute Details

#events ⇒ Object (readonly)

Returns the value of attribute events.



54
55
56
 
# File 'lib/rangeable/boundary_index.rb', line 54

def events
  @events
end

#segments ⇒ Object (readonly)

Returns the value of attribute segments.



54
55
56
 
# File 'lib/rangeable/boundary_index.rb', line 54

def segments
  @segments
end

#version ⇒ Object (readonly)

Returns the value of attribute version.



54
55
56
 
# File 'lib/rangeable/boundary_index.rb', line 54

def version
  @version
end

Class Method Details

.build(intervals, ord, snapshot_version, int_max_sentinel: nil) ⇒ Object

Build a fresh index from the per-element interval map and the insertion-order map ‘ord`. `int_max_sentinel` (default nil) lets the caller opt into “treat hi == sentinel as +∞” semantics for cross- language fixture parity; if it is nil we never coerce close coords to nil (Ruby’s unbounded Integer makes that unnecessary).



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

def self.build(intervals, ord, snapshot_version, int_max_sentinel: nil)
  events = []
  intervals.each do |element, set|
    element_ord = ord[element]
    set.each do |interval|
      events << TransitionEvent.new(interval.lo, :open, element, element_ord)
      close_coord =
        if !int_max_sentinel.nil? && interval.hi == int_max_sentinel
          nil
        else
          interval.hi + 1
        end
      events << TransitionEvent.new(close_coord, :close, element, element_ord)
    end
  end

  events.sort! do |a, b|
    cmp = compare_coord(a.coordinate, b.coordinate)
    next cmp unless cmp.zero?

    # Same coord: opens before closes.
    cmp = (a.kind == :open ? 0 : 1) <=> (b.kind == :open ? 0 : 1)
    next cmp unless cmp.zero?

    # Same coord + same kind: open ascending by ord, close descending.
    if a.kind == :open
      a.ord <=> b.ord
    else
      b.ord <=> a.ord
    end
  end

  segments = materialise_segments(events)
  new(events, segments, snapshot_version)
end

.compare_coord(a, b) ⇒ Object

Total order over coordinates: nil (== ∞) is greater than any finite. Returns -1 / 0 / 1.



174
175
176
177
178
179
180
 
# File 'lib/rangeable/boundary_index.rb', line 174

def self.compare_coord(a, b)
  return 0 if a.nil? && b.nil?
  return 1 if a.nil?
  return -1 if b.nil?

  a <=> b
end

.materialise_segments(events) ⇒ Object

Sweep events linearly, materialising a Segment for every maximal run of integers over which the active set is constant. Per RFC §6.3 we do not emit a segment whose active set is empty (no phantom ‘(-inf, first_open - 1)` segment).



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

def self.materialise_segments(events)
  segments = []
  active_by_ord = {} # ord => element (treated as a sorted set keyed by ord)
  prev_coord = nil
  i = 0
  while i < events.size
    # Group events at the same coord; we apply all of them before
    # snapshotting the active set so that segment boundaries land on
    # transitions, not in the middle of a same-coord burst.
    ev = events[i]
    coord = ev.coordinate

    if !prev_coord.nil? && !active_by_ord.empty?
      segments << Segment.new(prev_coord, coord - 1, snapshot_active(active_by_ord))
    end

    # Apply every event at this coord.
    while i < events.size && events[i].coordinate == coord
      ev_i = events[i]
      if ev_i.open?
        active_by_ord[ev_i.ord] = ev_i.element
      else
        active_by_ord.delete(ev_i.ord)
      end
      i += 1
    end

    prev_coord = coord
  end
  segments
end

.snapshot_active(active_by_ord) ⇒ Object

Snapshot the active set as a frozen Array sorted by ord ascending. The Hash insertion order is not guaranteed to match ord ascending (we add/remove arbitrarily), so we sort explicitly.



168
169
170
 
# File 'lib/rangeable/boundary_index.rb', line 168

def self.snapshot_active(active_by_ord)
  active_by_ord.keys.sort.map { |o| active_by_ord[o] }.freeze
end

Instance Method Details

#events_in_range(lo, upper_coord) ⇒ Object

Returns the events whose coordinate falls in ‘[lo, succ(hi)]` per RFC §6.4. `lo` is a finite Integer; `upper_coord` may be `nil` to mean “include all events through +∞”.



77
78
79
80
81
82
83
84
85
86
 
# File 'lib/rangeable/boundary_index.rb', line 77

def events_in_range(lo, upper_coord)
  i_start = @events.bsearch_index { |ev| coord_ge?(ev.coordinate, lo) } || @events.size
  result = []
  i = i_start
  while i < @events.size && coord_le?(@events[i].coordinate, upper_coord)
    result << @events[i]
    i += 1
  end
  result
end

#segment_at(coord) ⇒ Object

Find the segment containing ‘coord`, or nil if none. O(log |segments|). `coord` must be a finite Integer.



65
66
67
68
69
70
71
72
 
# File 'lib/rangeable/boundary_index.rb', line 65

def segment_at(coord)
  idx = @segments.bsearch_index { |seg| seg.hi >= coord }
  return nil unless idx

  seg = @segments[idx]
  return nil unless seg.lo <= coord
  seg
end