-- DICTIONARY is an 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).

indexing

  names: dictionary;
  size: unlimited;
  contents: named;

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

class DICTIONARY inherit SORTED_TREE
  rename nodes as articles
  export {NONE} leaves
  end
creation make
feature{ANY}
  name:STRING
  make(s:STRING) is
    -- Create a dictionary element.
    do
      name := s
    end  -- make
  find (key:STRING):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.name.is_equal(key)
      loop
        if key_value < Result.name.hash_code then
          Result := Result.left
        else
          Result := Result.right
        end
      end
    end  -- find
  continu:DICTIONARY is
    -- Find next element in the tree that has same name.
    -- Usually this is used on element returned by find.
    do
      if right /= Void then Result := right.find(name) end
    end  -- continu
feature{DICTIONARY}
  is_less (other:like Current):BOOLEAN
    -- Is 'other' less than current object?
    do
      Result := other.name.hash_code < name.hash_code
    end;  -- is_less
feature{ANY}
  is_equal (other:like Current):BOOLEAN
    -- Is 'other' equal to current object?
    do
      Result := name.is_equal(other.name)
    end   -- greater
feature{DICTIONARY}
  is_greater (other:like Current):BOOLEAN
    -- Is 'other' greater than current object?
    do
      Result := other.name.hash_code > name.hash_code
    end   -- greater
end  -- class 'DICTIONARY'