Saturday, October 25, 2008

Rotating a string

Code snippet to rotate a string:


static void Main(string[] args)
{
string subject = "abcdefg";

// test harness, check it handles multiples of size and negatives and zero
for (int amount = -subject.Length * 3; amount < subject.Length * 3; amount++)
{
string result = RotateStringTest(subject, amount);

char[] inplace = subject.ToCharArray();

RotateString(inplace, amount);

if (amount % subject.Length == 0)
Debug.Assert(result.CompareTo(subject) == 0);
Debug.Assert(result.CompareTo(new String(inplace)) == 0);
}
}

/// <summary>
/// Rotates a string
/// </summary>
/// <param name="subject">string to rotate</param>
/// <param name="amount">&lt; 0 left, 0 none, &gt; 0 right</param>
/// <returns></returns>
private static void RotateString(char[] subject, int amount)
{
int length = subject.Length;

// negate rotations can be re-expressed as positive amounts
if (amount < 0)
amount = length - (-amount % length);

// 0 rotation mean return unchanged
if (amount % length == 0)
return;

int dest = amount;
char prev = subject[0];

do
{
dest %= length;

Swap(ref subject[dest], ref prev);

dest += amount;
} while (dest != amount);
}

/// <summary>
/// swaps two chars wihout using temp variable
/// </summary>
private static void Swap(ref char a, ref char b)
{
a ^= b;
b ^= a;
a ^= b;
}

/// <summary>
/// Rotates a string test (slow)
/// </summary>
/// <param name="subject">string to rotate</param>
/// <param name="amount">&lt; 0 left, 0 none, &gt; 0 right</param>
/// <returns></returns>
private static string RotateStringTest(string subject, int amount)
{
char[] result = subject.ToCharArray();
int length = subject.Length;

// negate rotations can be re-expressed as positive amounts
if (amount < 0)
amount = length - (-amount % length);

// 0 rotation mean return unchanged
if (amount % length != 0)
{
for (int pos = 0; pos < length; pos++)
{
int dest = (pos + amount) % length;

result[dest] = subject[pos];
}
}

return new String(result);
}


ps this post was really just to test this javascript code hightlighter.. It seems to work very well for both Xaml and C# - cool!

No comments: