Class: HAMT

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/hamt.rb,
lib/hamt/version.rb

Overview

A persistent (immutable) Hash Array Mapped Trie.

set and delete return a new HAMT that shares structure with the old one; nothing is ever mutated and every node is frozen. Keys are compared the way Ruby's Hash compares them: by #hash, then #eql?.

a = HAMT[x: 1]
b = a.set(:y, 2)
a[:y]  # => nil   (a is untouched)
b[:y]  # => 2

Constant Summary collapse

BITS =

5 bits per level => 32-way branches

5
MASK = 
(1 << BITS) - 1
VERSION = 
"0.1.0"

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(root = nil, count = 0) ⇒ HAMT

Returns a new instance of HAMT.



224
225
226
227
228
 
# File 'lib/hamt.rb', line 224

def initialize(root = nil, count = 0)
  @root = root
  @count = count
  freeze
end

Instance Attribute Details

#count ⇒ Object Also known as: size, length

Returns the value of attribute count.



230
231
232
 
# File 'lib/hamt.rb', line 230

def count
  @count
end

#root ⇒ Object

Returns the value of attribute root.



230
231
232
 
# File 'lib/hamt.rb', line 230

def root
  @root
end

Class Method Details

.[](enum = []) ⇒ Object 



220
221
222
 
# File 'lib/hamt.rb', line 220

def self.[](enum = [])
  enum.reduce(new) { |h, (k, v)| h.set(k, v) }
end

.popcount(int) ⇒ Object 



29
30
31
32
33
34
35
36
 
# File 'lib/hamt.rb', line 29

def self.popcount(int)
  n = 0
  while int != 0
    int &= int - 1
    n += 1
  end
  n
end

Instance Method Details

#==(other) ⇒ Object 



300
301
302
303
 
# File 'lib/hamt.rb', line 300

def ==(other)
  other.is_a?(HAMT) && other.count == @count &&
    all? { |k, v| other.get(k, NOT_FOUND) == v }
end

#[](key) ⇒ Object 



239
240
241
 
# File 'lib/hamt.rb', line 239

def [](key)
  @root ? @root.get(key, key.hash, 0, nil) : nil
end

#delete(key) ⇒ Object 



273
274
275
276
277
 
# File 'lib/hamt.rb', line 273

def delete(key)
  return self unless @root
  root = @root.delete(key, key.hash, 0)
  root.equal?(@root) ? self : HAMT.new(root, @count - 1)
end

#each(&block) ⇒ Object 



279
280
281
282
283
 
# File 'lib/hamt.rb', line 279

def each(&block)
  return enum_for(:each) { @count } unless block_given?
  @root&.each(&block)
  self
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


233
 
# File 'lib/hamt.rb', line 233

def empty? = @count.zero?

#fetch(key, default = NOT_FOUND) ⇒ Object

Raises:

  • (KeyError) 


250
251
252
253
254
255
256
 
# File 'lib/hamt.rb', line 250

def fetch(key, default = NOT_FOUND)
  value = @root ? @root.get(key, key.hash, 0, NOT_FOUND) : NOT_FOUND
  return value unless NOT_FOUND.equal?(value)
  return yield(key) if block_given?
  return default unless NOT_FOUND.equal?(default)
  raise KeyError, "key not found: #{key.inspect}"
end

#get(key, default = nil) ⇒ Object 



235
236
237
 
# File 'lib/hamt.rb', line 235

def get(key, default = nil)
  @root ? @root.get(key, key.hash, 0, default) : default
end

#inspect ⇒ Object Also known as: to_s 



305
 
# File 'lib/hamt.rb', line 305

def inspect = "HAMT[#{map { |k, v| "#{k.inspect}=>#{v.inspect}" }.join(', ')}]"

#key?(key) ⇒ Boolean Also known as: has_key?, include?

Returns:

  • (Boolean) 


243
244
245
246
 
# File 'lib/hamt.rb', line 243

def key?(key)
  return false unless @root
  !@root.get(key, key.hash, 0, NOT_FOUND).equal?(NOT_FOUND)
end

#keys ⇒ Object 



296
 
# File 'lib/hamt.rb', line 296

def keys = map { |k, _| k }

#merge(*others) ⇒ Object 



285
286
287
288
289
290
291
292
293
294
295
 
# File 'lib/hamt.rb', line 285

def merge(*others)
  others.reduce(self) do |acc, other|
    other.reduce(acc) do |h, (k, v)|
      if block_given? && !(old = h.get(k, NOT_FOUND)).equal?(NOT_FOUND)
        h.set(k, yield(k, old, v))
      else
        h.set(k, v)
      end
    end
  end
end

#set(key, value) ⇒ Object Also known as: store, put 



258
259
260
261
262
263
264
265
266
267
268
269
 
# File 'lib/hamt.rb', line 258

def set(key, value)
  hash = key.hash
  return HAMT.new(Node.new(1 << (hash & MASK), [key, value].freeze), 1) if @root.nil?

  result = HAMT.allocate
  result.count = @count
  root = @root.put(key, hash, 0, value, result)
  return self if root.equal?(@root)
  result.root = root
  result.freeze
  result
end

#to_h ⇒ Object 



298
 
# File 'lib/hamt.rb', line 298

def to_h = each_with_object({}) { |(k, v), h| h[k] = v }

#values ⇒ Object 



297
 
# File 'lib/hamt.rb', line 297

def values = map { |_, v| v }