Class: RnDB::Thicket

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/rndb/thicket.rb

Instance Method Summary collapse

Constructor Details

#initialize(range = nil) ⇒ Thicket

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



8
9
10
11
 
# File 'lib/rndb/thicket.rb', line 8

def initialize(range=nil)
  @ids = []
  @ids << Slice.new(range.min, range.max) unless range.nil?
end

Instance Method Details

#&(other) ⇒ Object

Intersect two Thickets, useful when performing queries.



24
25
26
27
28
29
30
31
32
33
 
# 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) ⇒ Object

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



44
45
46
47
48
49
50
 
# 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) ⇒ Object

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.



15
16
17
18
19
20
21
 
# 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) ⇒ Object

Return the ID corresponding to the supplied index.



58
59
60
61
62
63
64
65
 
# 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 ⇒ Object

Sum the counts of the Slices in the Thicket.



53
54
55
 
# File 'lib/rndb/thicket.rb', line 53

def count
  @ids.map(&:count).sum
end

#each(&block) ⇒ Object

Iterate over each slice in the Thicket in turn.



88
89
90
 
# File 'lib/rndb/thicket.rb', line 88

def each(&block)
  @ids.each { |slice| slice.each(&block) }
end

#include?(id) ⇒ Boolean

Test whether the specified ID exists in this Thicket.

Returns:

  • (Boolean) 


78
79
80
 
# File 'lib/rndb/thicket.rb', line 78

def include?(id)
  @ids.any? { |slice| slice.include?(id) }
end

#index(id) ⇒ Object

Return the index corresponding to the supplied ID.



68
69
70
71
72
73
74
75
 
# 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 ⇒ Object Also known as: max

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



83
84
85
 
# File 'lib/rndb/thicket.rb', line 83

def last
  self[-1] unless count.zero?
end

#sample(limit = 1, prng = Random) ⇒ Object

Return a Thicket that contains a sampling of IDs.



93
94
95
96
97
98
99
100
 
# 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 ⇒ Object

We display the internal slices.



103
104
105
 
# File 'lib/rndb/thicket.rb', line 103

def to_s
  slices.to_s
end

#|(other) ⇒ Object

Merge two Thickets, which we need during migrations.



36
37
38
39
40
41
 
# 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