title: Simple String template replacement in Scala and Clojure
body: <p>Below are functions written in Scala and Clojure to do simple replacement of templates in Strings. The input to each function is a <code>String</code> containing templates of the form <code>{key}</code> and a map from Symbol/Keyword to replacement value.</p>
  
  <p>For example:</p>
  
  <p>Scala:</p>
  
  <pre><code>replaceTemplates("This is a {test}", Map('test -&gt; "game"))
  </code></pre>
  
  <p>Clojure:</p>
  
  <pre class="lang-clj prettyprint-override"><code>(replace-templates "This is a {test}" {:test "game"})
  </code></pre>
  
  <p>will return <code>"This is a game"</code>.</p>
  
  <p>The input map uses Symbols/Keywords so that I don't have to deal with corner cases where the templates in the Strings contain braces.</p>
  
  <p>Unfortunately, the algorithm is not very efficient.</p>
  
  <p>Here is the Scala code:</p>
  
  <pre><code>def replaceTemplates(text: String,
                       templates: Map[Symbol, String]): String = {
    val builder = new StringBuilder(text)
  
    @tailrec
    def loop(key: String,
             keyLength: Int,
             value: String): StringBuilder = {
      val index = builder.lastIndexOf(key)
      if (index &lt; 0) builder
      else {
        builder.replace(index, index + keyLength, value)
        loop(key, keyLength, value)
      }
    }
  
    templates.foreach {
      case (key, value) =&gt;
        val template = "{" + key.name + "}"
        loop(template, template.length, value)
    }
  
    builder.toString
  }
  </code></pre>
  
  <p>and here is the Clojure code:</p>
  
  <pre class="lang-clj prettyprint-override"><code>(defn replace-templates
    "Return a String with each occurrence of a substring of the form {key}
     replaced with the corresponding value from a map parameter.
     @param str the String in which to do the replacements
     @param m a map of keyword-&gt;value"
    [text m]
    (let [sb (StringBuilder. text)]
      (letfn [(replace-all [key key-length value]
                (let [index (.lastIndexOf sb key)]
                  (if (&lt; index 0)
                    sb
                    (do
                      (.replace sb index (+ index key-length) value)
                      (recur key key-length value)))))]
        (doseq [[key value] m]
          (let [template (str "{" (name key) "}")]
            (replace-all template (count template) value))))
      (.toString sb)))
  </code></pre>
  
  <p>Here is a test case (Scala code):</p>
  
  <pre><code>replaceTemplates("""
  Lorem ipsum dolor sit amet, consectetur adipiscing elit. Pellentesque
  elit nisi, egestas et tincidunt eget, {foo} mattis non erat. Aenean ut
  elit in odio vehicula facilisis. Vestibulum quis elit vel nulla
  interdum facilisis ut eu sapien. Nullam cursus fermentum
  sollicitudin. Donec non congue augue. {bar} Vestibulum et magna quis
  arcu ultricies consectetur auctor vitae urna. Fusce hendrerit
  facilisis volutpat. Ut lectus augue, mattis {baz} venenatis {foo}
  lobortis sed, varius eu massa. Ut sit amet nunc quis velit hendrerit
  bibendum in eget nibh. Cras blandit nibh in odio suscipit eget aliquet
  tortor placerat. In tempor ullamcorper mi. Quisque egestas, metus eu
  venenatis pulvinar, sem urna blandit mi, in lobortis augue sem ut
  dolor. Sed in {bar} neque sapien, vitae lacinia arcu. Phasellus mollis
  blandit commodo.
  """, Map('foo -&gt; "HELLO", 'bar -&gt; "GOODBYE", 'baz -&gt; "FORTY-TWO"))
  </code></pre>
  
  <p>and the output:</p>
  
  <pre><code>Lorem ipsum dolor sit amet, consectetur adipiscing elit. Pellentesque
  elit nisi, egestas et tincidunt eget, HELLO mattis non erat. Aenean ut
  elit in odio vehicula facilisis. Vestibulum quis elit vel nulla
  interdum facilisis ut eu sapien. Nullam cursus fermentum
  sollicitudin. Donec non congue augue. GOODBYE Vestibulum et magna quis
  arcu ultricies consectetur auctor vitae urna. Fusce hendrerit
  facilisis volutpat. Ut lectus augue, mattis FORTY-TWO venenatis HELLO
  lobortis sed, varius eu massa. Ut sit amet nunc quis velit hendrerit
  bibendum in eget nibh. Cras blandit nibh in odio suscipit eget aliquet
  tortor placerat. In tempor ullamcorper mi. Quisque egestas, metus eu
  venenatis pulvinar, sem urna blandit mi, in lobortis augue sem ut
  dolor. Sed in GOODBYE neque sapien, vitae lacinia arcu. Phasellus mollis
  blandit commodo.
  </code></pre>
  
  <p>The algorithm transverses the input map and for each pair, does a replacement in the input <code>String</code>, temporarily held in a <code>StringBuilder</code>. For each key/value pair, we search for the last occurrence of the key (enclosed in braces) and replace it with the value, until there are no more occurrences.</p>
  
  <p>Does it make any performance difference if we use <code>.lastIndexOf</code> versus <code>.indexOf</code> in the StringBuilder?</p>
  
  <p>How can the algorithm be improved? Is there a more idiomatic way to write the Scala and/or Clojure code?</p>
  
  <p><strong>UPDATE</strong>: See my <a href="https://stackoverflow.com/questions/6112534/follow-up-to-simple-string-template-replacement-in-scala-and-clojure">follow-up</a>.</p>
  
  <p><strong>UPDATE 2</strong>: Here is a better Scala implementation; O(n) in the length of the String. Note that I modified the <code>Map</code> to be <code>[String, String]</code> instead of <code>[Symbol, String]</code> on the recommendation of several people. (thanks <a href="https://stackoverflow.com/users/214010/mikera">mikera</a>, <a href="https://stackoverflow.com/users/198935/kotarak">kotarak</a>):</p>
  
  <pre><code>/**
   * Replace templates of the form {key} in the input String with values from the Map.
   *
   * @param text the String in which to do the replacements
   * @param templates a Map from Symbol (key) to value
   * @returns the String with all occurrences of the templates replaced by their values
   */
  def replaceTemplates(text: String,
                       templates: Map[String, String]): String = {
    val builder = new StringBuilder
    val textLength = text.length
  
    @tailrec
    def loop(text: String): String = {
      if (text.length == 0) builder.toString
      else if (text.startsWith("{")) {
        val brace = text.indexOf("}")
        if (brace &lt; 0) builder.append(text).toString
        else {
          val replacement = templates.get(text.substring(1, brace)).orNull
            if (replacement != null) {
              builder.append(replacement)
              loop(text.substring(brace + 1))
            } else {
              builder.append("{")
              loop(text.substring(1))
            }
        }
      } else {
        val brace = text.indexOf("{")
        if (brace &lt; 0) builder.append(text).toString
        else {
          builder.append(text.substring(0, brace))
          loop(text.substring(brace))
        }
      }
    }
  
    loop(text)
  }
  </code></pre>
  
  <p><strong>UPDATE 3</strong>: Here are a set of Clojure test cases (Scala versions are left as an exercise :-)):</p>
  
  <pre class="lang-clj prettyprint-override"><code>(use 'clojure.test)
  
  (deftest test-replace-templates
    (is (=        ; No templates
          (replace-templates "this is a test" {:foo "FOO"})
          "this is a test"))
  
    (is (=        ; One simple template
          (replace-templates "this is a {foo} test" {:foo "FOO"})
          "this is a FOO test"))
  
    (is (=        ; Two templates, second at end of input string
          (replace-templates "this is a {foo} test {bar}" {:foo "FOO" :bar "BAR"})
          "this is a FOO test BAR"))
  
    (is (=        ; Two templates
          (replace-templates "this is a {foo} test {bar} 42" {:foo "FOO" :bar "BAR"})
          "this is a FOO test BAR 42"))
  
    (is (=        ; Second brace-enclosed item is NOT a template
          (replace-templates "this is a {foo} test {baz} 42" {:foo "FOO" :bar "BAR"})
          "this is a FOO test {baz} 42"))
  
    (is (=        ; Second item is not a template (no closing brace)
          (replace-templates "this is a {foo} test {bar" {:foo "FOO" :bar "BAR"})
          "this is a FOO test {bar"))
  
    (is (=        ; First item is enclosed in a non-template brace-pair
          (replace-templates "this is {a {foo} test} {bar" {:foo "FOO" :bar "BAR"})
          "this is {a FOO test} {bar")))
  
  (run-tests)
  </code></pre>