Red-Black Trees: String Keys

One frequently used tree variant is string_map, which may be used to maps strings to any sort of value desired, although in any single tree all values must be of the same type.

The typical pattern of usage is to create an empty tree, enter key-value pairs into it, and then retrieve the values by key. Here is a simple script doing that with pairs where both key and value are strings.

Notice that when we create the empty map, we declare what type of value we intend to store in it. This is not always necessary, but it is a good habit; It helps both the compiler and the human reader.

Notice Also that since string_map::get returns either NULL or else THE value we use the the function to drop the unwanted THE from its return value:

    #!/usr/bin/mythryl

    m = (string_map::empty: string_map::Map( String ));

    m = string_map::set (m, "Key1", "Value1");
    m = string_map::set (m, "Key2", "Value2");
    m = string_map::set (m, "Key3", "Value3");

    printf "%s -> %s\n"  "Key1"  (the (string_map::get (m, "Key1")) );
    printf "%s -> %s\n"  "Key2"  (the (string_map::get (m, "Key2")) );
    printf "%s -> %s\n"  "Key3"  (the (string_map::get (m, "Key3")) );

When run this yields just what you expect:

    linux$ ./my-script
    Key1 -> Value1
    Key2 -> Value2
    Key3 -> Value3

Just to demonstrate the parametric polymorphism of the string_map tree in its values, here is the above example rewritten to use Int values:

    #!/usr/bin/mythryl

    m = (string_map::empty: string_map::Map( Int ));

    m = string_map::set (m, "Key1", 111);
    m = string_map::set (m, "Key2", 222);
    m = string_map::set (m, "Key3", 333);

    printf "%s -> %d\n"  "Key1"  (the (string_map::get (m, "Key1")) );
    printf "%s -> %d\n"  "Key2"  (the (string_map::get (m, "Key2")) );
    printf "%s -> %d\n"  "Key3"  (the (string_map::get (m, "Key3")) );

Execution of the script is again unsurprising:

    linux$ ./my-script
    Key1 -> 111
    Key2 -> 222
    Key3 -> 333

Here is the same script rewritten yet again, this time to use float values:

    #!/usr/bin/mythryl

    m = (string_map::empty: string_map::Map( Float ));

    m = string_map::set (m, "Key1", 0.111);
    m = string_map::set (m, "Key2", 0.222);
    m = string_map::set (m, "Key3", 0.333);

    printf "%s -> %f\n"  "Key1"  (the (string_map::get (m, "Key1")) );
    printf "%s -> %f\n"  "Key2"  (the (string_map::get (m, "Key2")) );
    printf "%s -> %f\n"  "Key3"  (the (string_map::get (m, "Key3")) );

Execution of this script version will not surprise you either:

    linux$ ./my-script
    Key1 -> 0.111000
    Key2 -> 0.222000
    Key3 -> 0.333000