class AVL_DICTIONARY_NODE [V_, K_ -> COMPARABLE]

Features exported to AVL_DICTIONARY

Auxiliary class to implement AVL_DICTIONARY.

Direct parents

conformant parents

ANY_AVL_DICTIONARY_NODE, AVL_TREE_NODE

Summary

creation features

exported features

Creation:

Rotations:

Details

value: V_
set_value (v: V_)

ensure

  • value = v

fast_at (k: K_): AVL_DICTIONARY_NODE[V_K_]

Is element e in the tree?

occurrences (v: V_): INTEGER
fast_occurrences (v: V_): INTEGER
key_at (v: V_): K_
fast_key_at (v: V_): K_
make (v: V_, k: K_)

ensure

  • value = v
  • key = k

out_in_tagged_out_memory

ensure

  • not_cleared: tagged_out_memory.count >= old tagged_out_memory.count
  • append_only: (old tagged_out_memory.twin).is_equal(tagged_out_memory.substring(1, old tagged_out_memory.count))

left: AVL_DICTIONARY_NODE [V_, K_ -> COMPARABLE]
right: AVL_DICTIONARY_NODE [V_, K_ -> COMPARABLE]
item: E_
balance: INTEGER

Balance factor; either balanced (the tree is balanced), imbalanced_left (the left branch is the longer) or imbalanced_right (the right branch is the longer)

count: INTEGER
height: INTEGER
map_in (map: COLLECTION[AVL_DICTIONARY_NODE [V_, K_ -> COMPARABLE]])

require

  • map /= Void

ensure

  • map.count = old map.count + count

has (e: E_): BOOLEAN

Is element e in the tree?

fast_has (e: E_): BOOLEAN

Is element e in the tree?

ensure

  • Result implies count > 0

at (e: E_): AVL_DICTIONARY_NODE [V_, K_ -> COMPARABLE]

Is element e in the tree?

set_item (i: E_)

require

  • left /= Void implies left.item = i or else left.item < i
  • right /= Void implies right.item > i

ensure

  • item = i

set_left (l: AVL_DICTIONARY_NODE [V_, K_ -> COMPARABLE])

require

  • l /= Void implies l.item = item or else l.item < item

ensure

  • left = l

set_right (r: AVL_DICTIONARY_NODE [V_, K_ -> COMPARABLE])

require

  • r /= Void implies r.item > item

ensure

  • right = r

set_balance (b: INTEGER)

ensure

  • balance = b

rotate_right: AVL_DICTIONARY_NODE [V_, K_ -> COMPARABLE]

Proceeds to some reorganisation and returns the upper node.

ensure

  • Result /= Void

rotate_left: AVL_DICTIONARY_NODE [V_, K_ -> COMPARABLE]

Proceeds to some reorganisation and returns the upper node.

ensure

  • Result /= Void