using System;
using System.Text.RegularExpressions;
using System.Diagnostics;

public class Test
{
    static Regex    reg  = new Regex(@"\{[^\{\}]*\}", RegexOptions.Compiled);
    static Random   rand = new Random((int)DateTime.Now.Ticks);
    static String[] parts;
    
    public static void Main()
    {
        String text = "Oh! {{I'm|You're} here!|How are you{ doing{|, {buddy|pal|guy}}|}?}";
        
        Console.WriteLine("Input Text:         " + text);
        Console.WriteLine("Testing SpinRE:     " + SpinRE(text));
        Console.WriteLine("Testing SpinRE:     " + SpinRE(text));
        Console.WriteLine("Testing SpinRE:     " + SpinRE(text));
        Console.WriteLine("Testing SpinRE:     " + SpinRE(text));
        Console.WriteLine("Testing SpinRE:     " + SpinRE(text));
        Console.WriteLine("Testing SpinRE:     " + SpinRE(text));
        Console.WriteLine("Testing SpinRE:     " + SpinRE(text));
        Console.WriteLine("Testing SpinRE:     " + SpinRE(text));
        Console.WriteLine("Testing SpinRE:     " + SpinRE(text));
        Console.WriteLine("Testing SpinRE:     " + SpinRE(text));
        Console.WriteLine("Testing SpinNoRE:   " + SpinNoRE(text));
        Console.WriteLine("Testing SpinNoRE:   " + SpinNoRE(text));
        Console.WriteLine("Testing SpinNoRE:   " + SpinNoRE(text));
        Console.WriteLine("Testing SpinNoRE:   " + SpinNoRE(text));
        Console.WriteLine("Testing SpinNoRE:   " + SpinNoRE(text));
        Console.WriteLine("Testing SpinNoRE:   " + SpinNoRE(text));
        Console.WriteLine("Testing SpinNoRE:   " + SpinNoRE(text));
        Console.WriteLine("Testing SpinNoRE:   " + SpinNoRE(text));
        Console.WriteLine("Testing SpinNoRE:   " + SpinNoRE(text));
        Console.WriteLine("Testing SpinNoRE:   " + SpinNoRE(text));
        Console.WriteLine("Testing SpinSergey: " + SpinSergey(text));
        Console.WriteLine("Testing SpinSergey: " + SpinSergey(text));
        Console.WriteLine("Testing SpinSergey: " + SpinSergey(text));
        Console.WriteLine("Testing SpinSergey: " + SpinSergey(text));
        Console.WriteLine("Testing SpinSergey: " + SpinSergey(text));
        Console.WriteLine("Testing SpinSergey: " + SpinSergey(text));
        Console.WriteLine("Testing SpinSergey: " + SpinSergey(text));
        Console.WriteLine("Testing SpinSergey: " + SpinSergey(text));
        Console.WriteLine("Testing SpinSergey: " + SpinSergey(text));
        Console.WriteLine("Testing SpinSergey: " + SpinSergey(text));
        
        Stopwatch s1 = new Stopwatch();
        Stopwatch s2 = new Stopwatch();
        Stopwatch s3 = new Stopwatch();
        
        for (int i = 0; i < 100000; i++)
        {
            s1.Start(); SpinRE(text);     s1.Stop();
            s2.Start(); SpinNoRE(text);   s2.Stop();
            s3.Start(); SpinSergey(text); s3.Stop();
        }
        
        Console.WriteLine("\nTime elapsed over 100,000 runs of each in alternation:\n");
        Console.WriteLine("SpinRE:           " + String.Format("{0:00}.{1:000}", s1.Elapsed.Seconds, s1.Elapsed.Milliseconds) + "s");
        Console.WriteLine("SpinNoRE:         " + String.Format("{0:00}.{1:000}", s2.Elapsed.Seconds, s2.Elapsed.Milliseconds) + "s");
        Console.WriteLine("SpinSergey:       " + String.Format("{0:00}.{1:000}", s3.Elapsed.Seconds, s3.Elapsed.Milliseconds) + "s");
    }
    
    public static String SpinRE(String text)
    {
        while (true)
        {
            Match m = reg.Match(text);
            if (!m.Success) break;
            parts = m.Value.Substring(1, m.Value.Length-2).Split('|');
            text = text.Substring(0, m.Index) + parts[rand.Next(parts.Length)] + text.Substring(m.Index + m.Length);
        }
        return text;
    }
    
    public static String SpinNoRE(String text)
    {
        int i;  // stores index of current open brace.
        int j;  // stores index of current close brace.
        int e;  // stores index of earliest untouched open brace.
        
        // helpers.
        char[] curls = new char[] {'{', '}'};

        // hack to prevent ArgumentOutOfRangeExceptions without having to check.
        text += '~';
        
        // index of "earliest untouched open brace" is unknown at start.
        e = -1;
        
        do
        {
            i =  e;
            e = -1;
            
            // loop as long as an open brace is found.
            while ((i = text.IndexOf('{', i+1)) != -1)
            {
                j = i;
                
                // loop as long as a brace is found and it is not a close brace.
                while ((j = text.IndexOfAny(curls, j+1)) != -1 && text[j] != '}')
                {
                    // means nested spintax was found; make j (the inner open
                    // brace) the "new" i and continue search for close brace.
                    
                    // nested spintax found; we're going to skip the current
                    // open brace in favor of this new one; but remember the
                    // index of the current open brace if it's the first such
                    // to be skipped; make j the "new" i; continue the search.
                    if (e == -1) e = i;
                    i = j;
                }
                
                // if close brace found, process spintax.
                if (j != -1)
                {
                    parts = text.Substring(i+1, (j-1)-(i+1-1)).Split('|');
                    text = text.Remove(i, j-(i-1)).Insert(i, parts[rand.Next(parts.Length)]);
                }
            }
        }
        // loop as long as an earlier untouched open brace exists (decrement e
        // before looping: the next loop begins its search at "i+1" == "e+1").
        while (e-- != -1);
        
        // undo aforementioned hack and return.
        return text.Remove(text.Length-1);
    }
    
    // @SergeyS's code:

    static int[] partIndices = new int[100];
	static int[] depth = new int[100];
	static char[] symbolsOfTextProcessed = new char[100000];

	public static String SpinSergey(String text)
	{
		int cur = SpinEvenMoreFasterInner(text, 0, text.Length, 0);
		return new String(symbolsOfTextProcessed, 0, cur);
	}

	public static int SpinEvenMoreFasterInner(String text, int start, int end, int symbolIndex)
	{
		int last = start;
		for (int i = start; i < end; i++)
		{
			if (text[i] == '{')
			{
				int k = 1;
				int j = i + 1;
				int index = 0;
				partIndices[0] = i;
				depth[0] = 1;
				for (; j < end && k > 0; j++)
				{
					if (text[j] == '{')
						k++;
					else if (text[j] == '}')
						k--;
					else if (text[j] == '|')
					{
						if (k == 1)
						{
							partIndices[++index] = j;
							depth[index] = 1;
						}
						else
							depth[index] = k;
					}
				}
				if (k == 0)
				{
					partIndices[++index] = j - 1;
					int part = rand.Next(index);
					text.CopyTo(last, symbolsOfTextProcessed, symbolIndex, i - last);
					symbolIndex += i - last;
					if (depth[part] == 1)
					{
						text.CopyTo(partIndices[part] + 1, symbolsOfTextProcessed, symbolIndex, partIndices[part + 1] - partIndices[part] - 1);
						symbolIndex += partIndices[part + 1] - partIndices[part] - 1;
					}
					else
					{
						symbolIndex = SpinEvenMoreFasterInner(text, partIndices[part] + 1, partIndices[part + 1], symbolIndex);
					}
					i = j - 1;
					last = j;
				}
			}
		}
		text.CopyTo(last, symbolsOfTextProcessed, symbolIndex, end - last);
		return symbolIndex + end - last;
	}
}