gistfile1.rb

require 'rubygems'
gem "minitest"

require 'minitest/autorun'
require 'minitest/pride'


require File.expand_path(File.join(File.dirname(__FILE__), '..', 'lib', 'trie'))

class TestTrie < MiniTest::Unit::TestCase
  def setup()
    @trie = Trie.new
  end

  def test_insert_ape
    @trie["Ape"] = "Animal"

    assert_equal true,     @trie.has_key?("Ape")
    assert_equal "Animal", @trie["Ape"]
  end

  def test_insert_multiple_with_differnt_start_nodes
    @trie["Ape"]  = "Animal"
    @trie["Tree"] = "Plant"
    
    assert_equal true,     @trie.has_key?("Ape")
    assert_equal true,     @trie.has_key?("Tree")
    assert_equal false,    @trie.has_key?("ATe")
    assert_equal "Animal", @trie["Ape"]
    assert_equal "Plant",  @trie["Tree"]
    assert_equal nil,      @trie["ATe"] 
  end
  
  def test_trie_with_default_value
    default_value = Array.new
    @trie2 = Trie.new(default_value)

    @trie2["Ape"] = "Animal"

    assert_equal "Animal",      @trie2["Ape"]
    assert_equal default_value, @trie2["Invalid"]
  end
  
  def test_delete_valid_key
    @trie["Ape"] = "Animal"

    assert_equal true,  @trie.delete("Ape")
    assert_equal false, @trie.has_key?("Ape")
    assert_equal nil,   @trie["Ape"]
    assert_equal false, @trie.keys.include?("Ape")
    assert_equal false, @trie.values.include?("Animal") 
  end
  
  def test_delete_key_shared_parent_nodes
    @trie["Apes"] = "Animal"
    @trie["Ape"]  = "Animal Also"

    assert_equal true,          @trie.delete("Apes")
    assert_equal true,          @trie.has_key?('Ape')
    assert_equal "Animal Also", @trie['Ape']
    assert_equal false,         @trie.has_key?('Apes')
  end
  
  def test_delete_key_shared_parent_nodes_different_order
    @trie["Ape"]  = "Animal 2"
    @trie["Apes"] = "Animal"
    
    assert_equal true,       @trie.delete("Apes")
    assert_equal true,       @trie.has_key?('Ape')
    assert_equal "Animal 2", @trie["Ape"]
    assert_equal false,      @trie.has_key?("Apes")
  end

  def test_delete_key_not_in_trie
    @trie["Ape"] = "Animal"

    assert_equal false,    @trie.delete("Apes")
    assert_equal true,     @trie.has_key?("Ape")
    assert_equal "Animal", @trie["Ape"]
  end

  def test_values_on_empty_trie
    assert_equal 0, @trie.values.size
  end

  def test_values_on_trie_with_keys
    @trie["Ape"]  = "Animal"
    @trie["Tree"] = "Plant"
    
    values = @trie.values
    
    assert_equal true, values.include?("Animal")
    assert_equal true, values.include?("Plant")
    assert_equal 2,    values.size
  end

  def test_keys_on_trie_with_keys
    @trie["Ape"]   = "Animal"
    @trie["Tree"]  = "Plant"
    @trie["Apple"] = "Plant"
    @trie["Trek"]  = "Other"

    keys = @trie.keys

    assert_equal 4, keys.size
    %w(Ape Tree Apple Trek).each do |key|
      assert_equal true, keys.include?(key)
    end
  end

  def test_substring_match_on_key
    @trie["Ape"]   = "Animal"
    @trie["Tree"]  = "Plant"
    @trie["Apple"] = "Plant"
    @trie["Trek"]  = "Other"

    keys = @trie.keys_like "Ap"
    %w(Ape Apple).each do |key|
      assert_equal true, keys.include?(key)
    end
  end

  def test_substring_match_on_key_failure
    @trie["Ape"]   = "Animal"
    @trie["Tree"]  = "Plant"
    @trie["Apple"] = "Plant"
    @trie["Trek"]  = "Other"

    keys = @trie.keys_like "An"
    assert_equal 0, keys.size
  end

  def test_substring_match_all_keys
    @trie["Ape"]   = "Animal"
    @trie["Tree"]  = "Plant"
    @trie["Apple"] = "Plant"
    @trie["Trek"]  = "Other"

    keys = @trie.keys_like ""
    assert_equal 4, keys.size
  end

  def test_delete_parent_key_with_child_sub_keys
    @trie["a"]     = "foo"
    @trie["apple"] = "fooish"
    
    assert_equal true,  @trie.delete("a")
    assert_equal false, @trie.has_key?("a")
    assert_equal true,  @trie.has_key?("apple")
  end
  
end