Class: Farce::Abstract::TreeMap Abstract

Inherits:
Map
  • Object
show all
Includes:
DuplicableMap
Defined in:
lib/farce/abstract/tree_map.rb

Overview

This class is abstract.

Superclass for all tree map implementations.

You can think of a tree map as a sorted hash (sorted by key). Under the hood, tree maps are implemented as a balanced binary search tree.

This means lookups, insertions, and deletions are O(log n) operations (vs O(1) for a hash map). This is much slower than a hash map, but much faster than ad hoc sorting of the map.

Instance Method Summary collapse

Methods included from DuplicableMap

#compact, #compact_blank, #deep_dup, #duplicable?, #except, #flatten, #invert, #merge, #reject, #reverse_merge, #select, #slice, #stringify_keys, #symbolize_keys, #to_proc, #transform_keys, #transform_values, #with_indifferent_access

Methods inherited from Map

#as_extended_json, #as_json, #assert_valid_keys, #assoc, #bson_type, #compare_by_identity?, #deconstruct_keys, #dig, #fetch_values, #has_key?, #key, #rassoc, #shareable_values?, #store, #to_a, #to_bson, #to_bson_normalized_value, #to_cbor, #to_h, #to_hash, #to_json, #to_msgpack, #to_query, #to_s, #value?, #values_at, #weak_keys?, #weak_values?

Constructor Details

#initialize(entries = nil, normalize_keys: nil, **keyword_entries) ⇒ TreeMap

Note:

Subclasses may accept additional, optional arguments (usually keyword arguments) to configure the map.

Returns a new instance of TreeMap.

Parameters:

  • entries (Hash, Array<Array(BasicObject, BasicObject)>, Map, #each, nil) (defaults to: nil) —

    Optional initial entries for the map. Needs to implement #each and yield key-value pairs. If nil, the map will be empty.

  • normalize_keys (Symbol, Proc, Hash, Farce::Abstract::Map, nil) (defaults to: nil) —

    Converts incoming keys to their canonical stored form:

    • If a Symbol is provided, it will be used as a method name to call on each key.
    • If a Proc is provided, it will be called with each key and should return the normalized key.
    • If a Hash or Map is provided, it will be used to look up the normalized key for each incoming key.


22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
 
# File 'lib/farce/abstract/tree_map.rb', line 22

def initialize(entries = nil, normalize_keys: nil, **keyword_entries)
  unless keyword_entries.empty?
    raise ArgumentError, "entries given as both positional and keyword arguments" unless entries.nil?
    entries = keyword_entries
  end
  entries = convert_entries(entries)
  @map       = new_tree_map
  @key_locks = new_key_locks
  restoring  = Internal::KeyNormalizer.restoration?(normalize_keys)
  normalizer = Internal::KeyNormalizer.build(
    normalize_keys,
    shareable: normalize_keys && Internal::KeyNormalizer.shareable_target?(self),
  )
  Internal::KeyNormalizer.install(self, normalizer, Internal::KeyNormalizer::TreeOperations) unless restoring
  entries&.each { self[_1] = _2 }
  Internal::KeyNormalizer.install(self, normalizer, Internal::KeyNormalizer::TreeOperations) if restoring
  super()
end

Instance Method Details

#[](key) ⇒ BasicObject?

This method is abstract.

Look up a key without waiting for atomic-update access.

Parameters:

  • key (BasicObject) —

    The key to look up.

Returns:

  • (BasicObject, nil) —

    The associated value, or nil if the key is absent.



49
 
# File 'lib/farce/abstract/tree_map.rb', line 49

def [](key) = unwrap_value(internal_map[prepare_key(key)])

#[]=(key, value) ⇒ BasicObject

This method is abstract.

Associate a value with a key without a timeout.

Parameters:

  • key (BasicObject) —

    The key to store.

  • value (BasicObject) —

    The value to store.

Returns:

  • (BasicObject) —

    value.



52
53
54
55
56
 
# File 'lib/farce/abstract/tree_map.rb', line 52

def []=(key, value)
  key = internal_map.prepare_key(prepare_key(key))
  with_key_lock(key) { internal_map[key] = wrap_value(value) }
  value
end

#clear ⇒ self

Remove all entries from the map.

Returns:

  • (self) 


148
149
150
151
 
# File 'lib/farce/abstract/tree_map.rb', line 148

def clear
  internal_map.clear
  self
end

#compare_keys_by_identity? ⇒ false

TreeMap keys are compared by their ordering, never by identity.

Returns:

  • (false) 


228
 
# File 'lib/farce/abstract/tree_map.rb', line 228

def compare_keys_by_identity? = false

#compare_values_by_identity? ⇒ false

TreeMap values are compared by equality, never by identity.

Returns:

  • (false) 


232
 
# File 'lib/farce/abstract/tree_map.rb', line 232

def compare_values_by_identity? = false

#delete(key) ⇒ BasicObject?

This method is abstract.

Remove a key and its associated value.

Parameters:

  • key (BasicObject) —

    The key to remove.

Returns:

  • (BasicObject, nil) —

    The removed value, or nil if the key was absent.



90
 
# File 'lib/farce/abstract/tree_map.rb', line 90

def delete(key) = unwrap_value(internal_map.delete(prepare_key(key)))

#each {|pair| ... } ⇒ self #each ⇒ Enumerator Also known as: each_pair

Iterate over the map's key-value pairs. Order is guaranteed to be from smallest to largest key according.

Overloads:

  • #each {|pair| ... } ⇒ self

    Yields:

    • (pair) —

      Called once for each entry.

    Yield Parameters:

    • pair (Array<BasicObject>) —

      A two-element [key, value] pair.

    Returns:

    • (self)
  • #each ⇒ Enumerator

    Returns An enumerator over two-element [key, value] pairs.

    Returns:

    • (Enumerator) —

      An enumerator over two-element [key, value] pairs.



162
163
164
165
166
 
# File 'lib/farce/abstract/tree_map.rb', line 162

def each
  return enum_for(__method__) unless block_given?
  internal_map.each { |key, value| yield [key, unwrap_value(value)] }
  self
end

#each_key {|key| ... } ⇒ self #each_key ⇒ Enumerator

Iterate over the keys currently stored in the map. Keys are yielded from smallest to largest.

Overloads:

  • #each_key {|key| ... } ⇒ self

    Yields:

    • (key) —

      Called once for each stored key.

    Yield Parameters:

    • key (BasicObject) —

      A stored key.

    Returns:

    • (self)
  • #each_key ⇒ Enumerator

    Returns An enumerator over the stored keys.

    Returns:

    • (Enumerator) —

      An enumerator over the stored keys.



190
191
192
193
194
 
# File 'lib/farce/abstract/tree_map.rb', line 190

def each_key
  return enum_for(__method__) unless block_given?
  each { |key, _| yield key }
  self
end

#each_value {|value| ... } ⇒ self #each_value ⇒ Enumerator

Iterate over the values currently stored in the map. Values are yielded in the order of their corresponding keys (from smallest to largest).

Overloads:

  • #each_value {|value| ... } ⇒ self

    Yields:

    • (value) —

      Called once for each stored value.

    Yield Parameters:

    • value (BasicObject) —

      A stored value.

    Returns:

    • (self)
  • #each_value ⇒ Enumerator

    Returns An enumerator over the stored values.

    Returns:

    • (Enumerator) —

      An enumerator over the stored values.



205
206
207
208
209
 
# File 'lib/farce/abstract/tree_map.rb', line 205

def each_value
  return enum_for(__method__) unless block_given?
  each { |_, value| yield value }
  self
end

#empty? ⇒ Boolean

Returns whether the map contains no entries.

Returns:

  • (Boolean) —

    Whether the map is empty.



93
 
# File 'lib/farce/abstract/tree_map.rb', line 93

def empty? = internal_map.empty?

#fetch(key) ⇒ BasicObject #fetch(key, default) ⇒ BasicObject #fetch(key) {|key| ... } ⇒ BasicObject

This method is abstract.

Fetch the value associated with a key, using the same missing-key behavior as Hash#fetch. If both a default and a block are provided, the block takes precedence and a warning is emitted.

Overloads:

  • #fetch(key) ⇒ BasicObject

    Returns The associated value.

    Parameters:

    • key (BasicObject) —

      The key to look up.

    Returns:

    • (BasicObject) —

      The associated value.

    Raises:

    • (KeyError) —

      If the key is absent.

  • #fetch(key, default) ⇒ BasicObject

    Returns The associated value or default.

    Parameters:

    • key (BasicObject) —

      The key to look up.

    • default (BasicObject) —

      The value to return if the key is absent.

    Returns:

    • (BasicObject) —

      The associated value or default.

  • #fetch(key) {|key| ... } ⇒ BasicObject

    Returns The associated value or the block result.

    Parameters:

    • key (BasicObject) —

      The key to look up.

    Yields:

    • (key) —

      Called if the key is absent.

    Yield Parameters:

    • key (BasicObject) —

      The missing key.

    Yield Returns:

    • (BasicObject) —

      The value to return.

    Returns:

    • (BasicObject) —

      The associated value or the block result.



96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
 
# File 'lib/farce/abstract/tree_map.rb', line 96

def fetch(*arguments)
  unless arguments.length.between?(1, 2)
    raise ArgumentError, "wrong number of arguments (given #{arguments.length}, expected 1..2)"
  end

  key, default = arguments
  key = prepare_key(key)
  warn "block supersedes default value argument", uplevel: 1 if block_given? && arguments.length == 2
  value = internal_map.fetch(key) do
    return yield(key) if block_given?
    return default if arguments.length == 2
    raise KeyError.new("key not found: #{key.inspect}", receiver: self, key: key)
  end
  unwrap_value(value)
end

#first_key ⇒ BasicObject?

Return the smallest key according to the map's ordering.

Returns:

  • (BasicObject, nil) —

    The first key, or nil if the map is empty.



114
 
# File 'lib/farce/abstract/tree_map.rb', line 114

def first_key = internal_map.first_key

#getkey(key) ⇒ BasicObject?

This method is abstract.

Return the stored key that matches a lookup key.

Parameters:

  • key (BasicObject) —

    The key to match.

Returns:

  • (BasicObject, nil) —

    The matching stored key, or nil if no key matches.



117
 
# File 'lib/farce/abstract/tree_map.rb', line 117

def getkey(key) = internal_map.getkey(prepare_key(key))

#key?(key) ⇒ Boolean

This method is abstract.

Test whether a key is present, including when its associated value is nil.

Parameters:

  • key (BasicObject) —

    The key to look up.

Returns:

  • (Boolean) —

    Whether the key is present.



120
 
# File 'lib/farce/abstract/tree_map.rb', line 120

def key?(key) = internal_map.key?(prepare_key(key))

#keys ⇒ Array<BasicObject>

Return the keys currently stored in the map. The result is frozen and ordered from smallest to largest key.

Returns:

  • (Array<BasicObject>) —

    The keys currently stored in the map, in order from smallest to largest.



214
 
# File 'lib/farce/abstract/tree_map.rb', line 214

def keys = each_key.to_a.freeze

#last_key ⇒ BasicObject?

Return the largest key according to the map's ordering.

Returns:

  • (BasicObject, nil) —

    The last key, or nil if the map is empty.



124
 
# File 'lib/farce/abstract/tree_map.rb', line 124

def last_key = internal_map.last_key

#length ⇒ Integer

This method is abstract.

Return the number of entries currently in the map.

Returns:

  • (Integer) —

    The number of entries.



127
 
# File 'lib/farce/abstract/tree_map.rb', line 127

def length = internal_map.length

#pop ⇒ Array(BasicObject, BasicObject)?

Remove and return the entry with the largest key according to the map's ordering.

Returns:

  • (Array(BasicObject, BasicObject), nil) —

    The last key-value pair, or nil if the map is empty.



131
132
133
134
 
# File 'lib/farce/abstract/tree_map.rb', line 131

def pop
  pair = internal_map.pop
  [pair.first, unwrap_value(pair.last)] if pair
end

#shareable_keys? ⇒ true

TreeMap keys always have to be Ractor-shareable. Mutable strings are accepted however and will be converted to an immutable string.

Returns:

  • (true) 


224
 
# File 'lib/farce/abstract/tree_map.rb', line 224

def shareable_keys? = true

#shift ⇒ Array(BasicObject, BasicObject)?

Remove and return the entry with the smallest key according to the map's ordering.

Returns:

  • (Array(BasicObject, BasicObject), nil) —

    The first key-value pair, or nil if the map is empty.



138
139
140
141
 
# File 'lib/farce/abstract/tree_map.rb', line 138

def shift
  pair = internal_map.shift
  [pair.first, unwrap_value(pair.last)] if pair
end

#size ⇒ Integer

This method is abstract.

Return the number of entries currently in the map.

Returns:

  • (Integer) —

    The number of entries.



144
 
# File 'lib/farce/abstract/tree_map.rb', line 144

def size = internal_map.size

#store_if_absent(key) ⇒ BasicObject

Return an existing value, or store the block result for an absent key. Concurrent callers for equally ordered keys share one initialization. The block runs without holding the map's structural lock. Other keys remain accessible. Assigning the same key waits for initialization. Deletion or clearing can precede a pending initialization's insertion. Unsafe maps require callers to provide their own synchronization.

Parameters:

  • key (BasicObject) —

    The key to retrieve or initialize.

Yield Returns:

  • (BasicObject) —

    The value to store.

Returns:

  • (BasicObject) —

    The existing or newly stored value.

Raises:

  • (LocalJumpError) —

    If no block is given, even when the key exists.

  • (ThreadError) —

    If initialization recursively accesses its own gate.



69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
 
# File 'lib/farce/abstract/tree_map.rb', line 69

def store_if_absent(key)
  raise LocalJumpError, "no block given" unless block_given?

  map      = internal_map
  key      = map.prepare_key(prepare_key(key))
  found    = true
  existing = map.fetch(key) { found = false }
  return unwrap_value(existing) if found

  with_key_lock(key) do
    stored     = map.fetch(key) do
      value    = yield
      wrapped  = wrap_value(value)
      map[key] = wrapped
      return unwrap_value(wrapped)
    end
    unwrap_value(stored)
  end
end

#values ⇒ Array<BasicObject>

Return the values currently stored in the map. The result is frozen and ordered according to the order of their corresponding keys (from smallest to largest).

Returns:

  • (Array<BasicObject>) —

    The values currently stored in the map.



219
 
# File 'lib/farce/abstract/tree_map.rb', line 219

def values = each_value.to_a.freeze