class RnDB::Thicket

Public Class Methods

new(range=nil) click to toggle source

A sorted array of disjoint ranges, optionally initialised with a default range.

# File lib/rndb/thicket.rb, line 8
def initialize(range=nil)
  @ids = []
  @ids << Slice.new(range.min, range.max) unless range.nil?
end

Public Instance Methods

&(other) click to toggle source

Intersect two Thickets, useful when performing queries.

# File lib/rndb/thicket.rb, line 24
def &(other)
  retval = self.class.new
  slices.each do |slice|
    other.slices.each do |other_slice|
      next unless (intersection = slice & other_slice)
      retval << intersection
    end
  end
  retval
end
*(other) click to toggle source

Subdivide a Thicket with a probability range, also used for migrations.

# File lib/rndb/thicket.rb, line 44
def *(other)
  slices.each_with_object(self.class.new) do |slice, thicket|
    min = slice.min + (slice.count * other.min).round
    max = slice.min + (slice.count * other.max).round - 1
    thicket << (min..max) unless max < min
  end
end
<<(range) click to toggle source

Append a range, throwing an error if it overlaps with an existing range, and keeping the resulting array sorted so we can iterate over values.

# File lib/rndb/thicket.rb, line 15
def <<(range)
  slice = Slice.new(range.min, range.max)
  raise "slices in thicket must be disjoint" unless @ids.all? { |id| (id & slice).nil? }
  @ids << Slice.new(range.min, range.max)
  @ids.sort!
  self
end
[](index) click to toggle source

Return the ID corresponding to the supplied index.

# File lib/rndb/thicket.rb, line 58
def [](index)
  index += count while index.negative?
  @ids.each do |slice|
    return index + slice.min if index < slice.count
    index -= slice.count
  end
  nil
end
count() click to toggle source

Sum the counts of the Slices in the Thicket.

# File lib/rndb/thicket.rb, line 53
def count
  @ids.map(&:count).sum
end
each(&block) click to toggle source

Iterate over each slice in the Thicket in turn.

# File lib/rndb/thicket.rb, line 88
def each(&block)
  @ids.each { |slice| slice.each(&block) }
end
include?(id) click to toggle source

Test whether the specified ID exists in this Thicket.

# File lib/rndb/thicket.rb, line 78
def include?(id)
  @ids.any? { |slice| slice.include?(id) }
end
index(id) click to toggle source

Return the index corresponding to the supplied ID.

# File lib/rndb/thicket.rb, line 68
def index(id)
  start = 0
  @ids.each do |slice|
    return start + id - slice.min if slice.include?(id)
    start += slice.count
  end
  nil
end
last() click to toggle source

Implemented to be consistent with first, which we get by magic.

# File lib/rndb/thicket.rb, line 83
def last
  self[-1] unless count.zero?
end
Also aliased as: max
max()
Alias for: last
sample(limit=1, prng=Random) click to toggle source

Return a Thicket that contains a sampling of IDs.

# File lib/rndb/thicket.rb, line 93
def sample(limit=1, prng=Random)
  ids = Set.new
  limit = [limit, count].min
  ids << self[prng.rand(count)] while ids.count < limit
  ids.sort.each_with_object(self.class.new) do |id, thicket|
    thicket << Slice.new(id, id)
  end
end
to_s() click to toggle source

We display the internal slices.

# File lib/rndb/thicket.rb, line 103
def to_s
  slices.to_s
end
|(other) click to toggle source

Merge two Thickets, which we need during migrations.

# File lib/rndb/thicket.rb, line 36
def |(other)
  retval = self.class.new
  slices.each { |slice| retval << slice }
  other.slices.each { |slice| retval << slice }
  retval
end

Protected Instance Methods

slices() click to toggle source
# File lib/rndb/thicket.rb, line 112
def slices
  @ids
end