-- FAST_DICTIONARY is a VERY efficient data structure for named objects.
-- Time complexity for data adding is O(log n).
-- Time complexity for data searching is also O(log n).
-- Space complexity is O(n) + little extra penalty compared to dictionary.

indexing

  names: fast_dictionary;
  size: unlimited;
  contents: named;

  author: "Guichard Damien";
  created: 20,January,1996;
  modified: 20,January,1996

class FAST_DICTIONARY inherit DICTIONARY
  redefine
    make, find, is_less, is_equal, is_greater
  end
creation make
feature
  make(s:STRING) is
    -- Create a fast_dictionary element.
    do
      name := s
      hash_value := s.hash_code
    end  -- make
  find (key:STRING):FAST_DICTIONARY is
    -- Find first occurrence in the tree matching 'key'.
    -- You should use 'continu' to find next occurrences.
    local key_value:INTEGER
    do
      key_value := key.hash_code
      from Result := Current
      until
        Result = Void or else
        (Result.hash_value = key_value and then Result.name.is_equal(key))
      loop
        if key_value < Result.name.hash_code then
          Result := Result.left
        else
          Result := Result.right
        end
      end
    end  -- find
feature{FAST_DICTIONARY}
  is_less (other:like Current):BOOLEAN
    -- Is 'other' less than current object?
    do
      Result := other.hash_value < hash_value
    end;  -- is_less
feature{ANY}
  is_equal (other:like Current):BOOLEAN
    -- Is 'other' equal to current object?
    do
      if other.hash_value = hash_value then
        Result := name.is_equal(other.name)
      end
    end   -- greater
feature{FAST_DICTIONARY}
  is_greater (other:like Current):BOOLEAN
    -- Is 'other' greater than current object?
    do
      Result := other.hash_value > hash_value
    end   -- greater
feature{NONE}
  hash_value:INTEGER
end