Find Mersenne primes in C#

[example]

Mersenne primes are prime numbers of the from 2n – 1 for some integer n. For example, 22 – 1 = 4 – 1 = 3 and 3 is prime, so 3 is a Mersenne prime.

This example uses a relatively straightforward approach to find Mersenne primes. When you click the Go button, the following code executes.

private void btnGo_Click(object sender, EventArgs e)
{
    lstPrimes.Items.Clear();
    Cursor = Cursors.WaitCursor;
    Refresh();

    try
    {
        checked
        {
            long power = 1;
            for (int n = 1; n < 63; n++)
            {
                // Get the next power of 2.
                power *= 2;

                // See if power - 1 is prime.
                if (IsPrime(power - 1))
                {
                    lstPrimes.Items.Add(
                        n.ToString() + ": " + (power - 1).ToString());
                    Refresh();
                }
            }
        }
    }
    catch
    {
    }

    Cursor = Cursors.Default;
}

This code loops through values of n ranging from 1 to 63 and calls the IsMersennePrime method described shortly to see if 2n – 1 is prime. The code only checks values up to n = 63 because 264 – 1 is too big to fit in a long integer.

The following code shows the IsPrimes method.

// Return true if the number is prime.
private bool IsMersennePrime(long number)
{
    // Handle 2 separately.
    if (number == 2) return true;

    // See if the number is divisible by odd values up to Sqrt(number).
    long sqrt = (long)Math.Sqrt(number);
    for (long i = 3; i < sqrt; i += 2)
        if (number % i == 0) return false;

    // If we get here, the number is prime.
    return true;
}

This method determines whether a number is prime, but it is optimized slightly for Mersenne primes. If n ≥ 1, then the value 2n must be even so the value 2n - 1 must be odd. For that reason, the code doesn't check to see if the number is divisible by 2. Instead it loops through odd numbers between 3 and the square root of the number. If the number is divisible by any of those values, then the number is not prime.

If the number is not divisible by any of the n considered by the loop, then the number is prime.

The program quickly finds the Mersenne primes up to 231 - 1. For larger values of n, the value 2n - 1 is large enough that the search slows down and finding 261 - 1 takes longer.

To find larger Mersenne primes, you can use the BigInteger structure in the System.Numerics namespace, but the numbers become so large that your search will slow considerably. You'll probably need to switch to a new method is you want to find new Mersenne primes larger than the current largest known value of 277,232,917 - 1.


Download Example   Follow me on Twitter   RSS feed   Donate




Posted in algorithms, mathematics | Tagged , , , , , , , , , | Leave a comment

Display a progress bar with text in WPF and C#

[progress bar]

As is so often the case in WPF, the solution is simple after you spend a few hours figuring out what controls to use. This example uses a normal Grid control that holds a StackPanel. The following code shows the controls inside the StackPanel.

<Button Name="goButton" Width="75" Height="30"
    Content="Go" Click="goButton_Click"/>

<Border Name="progBorder"
    Margin="0,10,0,0" Width="300" Height="25"
    BorderBrush="Black" BorderThickness="1">
    <Grid Margin="0">
        <Label Name="progBgLabel" Width="0" 
            HorizontalAlignment="Left"
            Background="LightGreen" />
        <Label Name="progLabel"
            HorizontalAlignment="Center"
            VerticalAlignment="Center"
            Content="0%" />
    </Grid>
</Border>

The button is there to let you start the progress simulation.

After the button comes a Border. This displays the black border around the progress bar and acts as a container for the remaining controls. This is the control that you should use to change the size or position of the progress bar. For example, this program makes the progress bar 300 pixels wide, 25 pixels tall, and centered inside the StackPanel. You can modify the Border control to change those values.

The progress bar must hold two Label controls, one to display the colored background and one to display text. Because a Border control can have only one child, the XAML code places a Grid inside the Border and then places the two Label controls inside the Grid.

Initially the controls are set to show no green background and the string “0%.”

The program uses the following code behind to prepare to update the progress.

// The timer.
private DispatcherTimer Timer = null;

// Progress parameters.
private const double ProgressMinimum = 0;
private const double ProgressMaximum = 100;
private const double ProgressStep = 4;
private double ProgressValue = ProgressMinimum;

WPF doesn’t have a Timer control, so the code declares a DispatcherTimer to use instead.

The code then defines some values to use while updating the progress. The ProgressValue variable shows the current progress.

When the window loads, the following code executes.

// Create the timer.
private void Window_Loaded(object sender, RoutedEventArgs e)
{
    Timer = new DispatcherTimer();
    Timer.Tick += new EventHandler(Timer_Tick);
    Timer.Interval = new TimeSpan(0, 0, 0, 0, 100);
}

This code creates the DispatcherTimer, assigns its Tick event handler, and sets its interval to 100 milliseconds.

When you click the Go button, the following code executes.

// Start a timer.
private void goButton_Click(object sender, RoutedEventArgs e)
{
ProgressValue = ProgressMinimum;
Timer.Start();
}

This code sets ProgressValue to the minimum and enables the timer. The following event handler executes when the timer fires.

// Simulate a task's progress.
private void Timer_Tick(object sender, EventArgs e)
{
    ProgressValue += ProgressStep;
    if (ProgressValue > ProgressMaximum)
    {
        ProgressValue = ProgressMinimum;
        Timer.Stop();
    }

    // Show the progress.
    double fraction = (ProgressValue - ProgressMinimum) /
        (ProgressMaximum - ProgressMinimum);
    progBgLabel.Width = progBorder.Width * fraction;

    progLabel.Content = ProgressValue.ToString() + "%";
}

This code adds ProgressStep to ProgressValue. Then if ProgressValue is greater than ProgressMaximum, the code resets ProgessValue to ProgressMinimum and stops the timer.

After it updates ProgressValue, the code calculates the fraction of the Border control’s width that should filled with background. It multiplies that fraction by the Border control’s width and sets the background label’s width to the result.

The code finishes by setting the progLabel control’s contents to the ProgressValue. Note that this string is displayed with no digits after the decimal as long as ProgressValue has an integer value, as it does in this example.

There are several modifications that you could make to this example. For instance, you could left justify the text label. You could also fill the background label with a color gradient or tiled picture.

If you need to do something like this often, then you might want to make a custom control to fill the background and display the numeric value more easily.


Download Example   Follow me on Twitter   RSS feed   Donate




Posted in controls, user interface, wpf, XAML | Tagged , , , , , , , , , , , , , | 1 Comment

Convert between ragged arrays and two-dimensional arrays


[example]

Ragged arrays are arrays that hold other arrays, as opposed to two-dimensional arrays. They are called “ragged arrays” because they work like two-dimensional arrays (or higher-dimensional arrays) where each row in the array can hold a different number of elements.

Converting between ragged arrays and two-dimensional arrays isn’t too hard, it just requires some bookkeeping. You can also use generic parameters to make a method to convert between ragged arrays and two-dimensional arrays holding any type of objects.

The following extension method converts from a two-dimensional array to a ragged array.

// Convert T[,] to T[][].
public static T[][] ToRagged<T>(this T[,] values)
{
    // Get the number of rows and columns.
    int num_rows = values.GetUpperBound(0) + 1;
    int num_cols = values.GetUpperBound(1) + 1;

    // Make the ragged array.
    T[][] result = new T[num_rows][];

    // Copy values into the ragged array.
    for (int r = 0; r < num_rows; r++)
    {
        result[r] = new T[num_cols];
        for (int c = 0; c < num_cols; c++)
            result[r][c] = values[r, c];
    }

    return result;
}

The method first gets the two-dimensional array’s dimensions. It then creates a one-dimensional array to hold the ragged array’s rows.

The code then loops through the two-dimensional array’s rows. For each row, the method creates a one-dimensional array to hold the row’s values and then copies the values into the row.

The following extension method converts a ragged array into a two-dimensional array.

// Convert T[][] to T[,].
public static T[,] To2DArray<T>(this T[][] values)
{
    // Get the number of rows.
    int num_rows = values.GetUpperBound(0) + 1;

    // Get the maximum number of columns in any row.
    int num_cols = 0;
    for (int r = 0; r < num_rows; r++)
        if (num_cols < values[r].Length)
            num_cols = values[r].Length;

    // Make the two-dimensional array.
    T[,] result = new T[num_rows, num_cols];

    // Copy values into the ragged array.
    for (int r = 0; r < num_rows; r++)
    {
        for (int c = 0; c < values[r].Length; c++)
            result[r, c] = values[r][c];
    }

    return result;
}

This method gets the number of rows in the ragged array. It then loops through its rows to see how long its longest row is.

The code then allocates a two-dimensional array with the correct number of rows and columns. It then loops through the ragged array’s values adding them to the two-dimensional array.

Note that any entries in the two-dimensional array that do not correspond to entries in the ragged array are left uninitialized. For example, suppose the longest row in the ragged array has 25 entries but the first row has only 10 entries. In that case, the last 15 entries in the first row of the result array will hold only 10 values and the last 15 values will be uninitialized and will holdd the default value for their data type.


Download Example   Follow me on Twitter   RSS feed   Donate




Posted in algorithms, arrays, extension methods, generic | Tagged , , , , , , , , , , , | Leave a comment

Perform image hashing in C#


[image hashing]

Image hashing or (perceptual image hashing) attempts to reduce an image to a concise code that represents the image so you can compare it to other images to see if they are the same. This example uses a difference hash algorithm that takes the following steps.

  1. Reduce the image size – The image is shrunk to 9×9 pixels so all images have a standard size.
  2. Reduce the color – The 9×9 image is converted to grayscale.
  3. Calculate the hash – The program scans the image’s first 8 rows. For each row, it compares adjacent pairs of pixels. If the right pixel is brighter than the left pixel in a pair, the algorithm adds 1 to the hash code. If the right pixel is darker, the algorithm adds 0 to the hash code. The program then repeats the process for the left 8 columns.

Because there are nine pixels in each row and column, there are eight adjacent pairs of pixels so the hash includes eight zeros or ones for each row and column. The algorithm considers eight rows and eight columns, so the hash code includes a total of 8 * 8 + 8 * 8 = 128 zeros and ones.

Click the Load Image buttons to select two image files to compare. When you click Compare, the program executes the following code to compare the images.

// Compare the images.
private void btnCompare_Click(object sender, EventArgs e)
{
    string hash_code1 = ProcessImage(picImage1.Image as Bitmap,
        picShrunk1, picMonochrome1, txtHashCode1);
    string hash_code2 = ProcessImage(picImage2.Image as Bitmap,
        picShrunk2, picMonochrome2, txtHashCode2);

    // Display the difference and score.
    string difference = "";
    int score = 0;
    for (int i = 0; i < hash_code1.Length; i++)
    {
        if (hash_code1[i] == hash_code2[i])
        {
            difference += " ";
        }
        else
        {
            difference += "X";
            score++;
        }
    }
    txtDifference.Text = difference;
    txtScore.Text = score.ToString();
    float percent = (hash_code1.Length - score) / (float)hash_code1.Length;
    txtPercent.Text = percent.ToString("P");
}

This code calls the ProcessImage method to do most of the interesting work on the two images. It then compares the two images’ hash codes character-by-character. It then displays the difference string.

The code also counts the differences and displays the count as a score indicating how similar to the two images are. A low score indicates few differences so the images are more similar.

The code finishes by displaying the percentage of characters in the hash code that are the same. A value close to 100% indicates that the images are very similar.

The following code shows the ProcessImage method.

private string ProcessImage(Bitmap original_bm,
    PictureBox pic_shrunk, PictureBox pic_monochrome,
    TextBox txt_hashcode)
{
    // Shrink the original image and display the result.
    Bitmap shrunk_bm = ScaleTo(original_bm, 9, 9,
        InterpolationMode.High);
    pic_shrunk.Image = ScaleTo(shrunk_bm, 90, 90,
        InterpolationMode.NearestNeighbor);

    // Convert to grayscale and display the result.
    Bitmap grayscale_bm = ToMonochrome(shrunk_bm);
    pic_monochrome.Image = ScaleTo(grayscale_bm, 90, 90,
        InterpolationMode.NearestNeighbor);

    // Calculate the hash code.
    string hash_code = GetHashCode(grayscale_bm);
    txt_hashcode.Text = hash_code;

    return hash_code;
}

This method calls the ScaleTo method to shrink the image to 9×9 pixels. The first piece of blue code enlarges the image and displays it in the pic_shrunk PictureBox so you can see the shrunk image.

Next, the code calls the ToMonochrome method to convert the small image to monochrome. The second piece of blue code enlarges the monochrome image and displays it in the pic_monochrome PictureBox so you can see it.

Finally, the code calls the GetHashCode method to perform the last step in the image hashing.

The following code shows the ScaleTo helper method.

// Scale an image.
private Bitmap ScaleTo(Bitmap bm, int wid, int hgt,
    InterpolationMode interpolation_mode)
{
    Bitmap new_bm = new Bitmap(wid, hgt);
    using (Graphics gr = Graphics.FromImage(new_bm))
    {
        RectangleF source_rect = new RectangleF(-0.5f, -0.5f, bm.Width, bm.Height);
        Rectangle dest_rect = new Rectangle(0, 0, wid, hgt);
        gr.InterpolationMode = interpolation_mode;
        gr.DrawImage(bm, dest_rect, source_rect, GraphicsUnit.Pixel);
    }
    return new_bm;
}

This method creates a bitmap with the desired size and an associated Graphics object. It then draws the original image on the bitmap and returns it.

Note that this method does not try to preserve the image’s aspect ratio. For example, if the original image is tall and thin but the desired size is square, as it is for this image hashing algorithm, then the image is stretched to fit.

The following code shows the ToMonochrome helper method.

// Convert an image to monochrome.
private Bitmap ToMonochrome(Image image)
{
    // Make the ColorMatrix.
    ColorMatrix cm = new ColorMatrix(new float[][]
    {
        new float[] {0.299f, 0.299f, 0.299f, 0, 0},
        new float[] {0.587f, 0.587f, 0.587f, 0, 0},
        new float[] {0.114f, 0.114f, 0.114f, 0, 0},
        new float[] { 0, 0, 0, 1, 0},
        new float[] { 0, 0, 0, 0, 1}
    });
    ImageAttributes attributes = new ImageAttributes();
    attributes.SetColorMatrix(cm);

    // Draw the image onto the new bitmap while
    // applying the new ColorMatrix.
    Point[] points =
    {
        new Point(0, 0),
        new Point(image.Width, 0),
        new Point(0, image.Height),
    };
    Rectangle rect = new Rectangle(0, 0, image.Width, image.Height);

    // Make the result bitmap.
    Bitmap bm = new Bitmap(image.Width, image.Height);
    using (Graphics gr = Graphics.FromImage(bm))
    {
        gr.DrawImage(image, points, rect,
            GraphicsUnit.Pixel, attributes);
    }

    // Return the result.
    return bm;
}

This method creates a ColorMatrix that converts an image to grayscale. The numbers multiply each pixel’s red, green, and blue color components by the indicated values to create a monochrome result. The code then creates a new bitmap and copies the image into it, using the ColorMatrix to adjust the new image’s colors.

The following code shows the final piece of the program, the GetHashCode method that performs the actual image hashing.

// Return the hashcode for this 9x9 image.
private string GetHashCode(Bitmap bm)
{
    string row_hash = "";
    for (int r = 0; r < 8; r++)
        for (int c = 0; c < 8; c++)
            if (bm.GetPixel(c + 1, r).R >= bm.GetPixel(c, r).R)
                row_hash += "1";
            else
                row_hash += "0";

    string col_hash = "";
    for (int c = 0; c < 8; c++)
        for (int r = 0; r < 8; r++)
            if (bm.GetPixel(c, r + 1).R >= bm.GetPixel(c, r).R)
                col_hash += "1";
            else
                col_hash += "0";

    return row_hash + "," + col_hash;
}

This method loops through the first eight rows, comparing adjacent pixels to add 0s and 1s to the hash string. It then repeats the same steps for the image’s first eight columns to create a column hash code. Finally, the method concatenates the two codes separated by a comma and returns the result. (The comma is just to make it easier to tell where the row codes end and the column codes begin.)

You could save space by storing an image’s hash codes in two 64-bit integers. I didn’t do that because it would make comparing the codes harder and would make them more difficult to visualize.

This image hashing method is good at identifying two images that are roughly the same but that may have different sizes or that have been modified by image compression algorithms.

I’ve seen at least one other implementation that rotated images by various angles to try to determine if two images are the same but rotated.

Unfortunately, I don’t of a reasonable way to determine whether one image is part of another or if two images share some parts. For example, if you crop an image, this method probably won’t be able to tell that the original and cropped version are similar.


Download Example   Follow me on Twitter   RSS feed   Donate




Posted in algorithms, graphics, image processing | Tagged , , , , , , , | Leave a comment

Use the automatic code converters at developerFusion to convert C# code into Visual Basic, Ruby, and Python

[code converters]

The developerFusion web site provides code converters that let you translate between C#, Visual Basic, Ruby, and Python.

One of the most important uses for reflection is analyzing code to figure out what it does. Once you know what the code does, you can emit new code to do the same thing in a different programming language. That’s what these code converters do. (Although right now they seem to be having trouble.)

The site has a tools page with links to free web-based tools that convert between C#, Visual Basic, Ruby, and Python. The tools are:

The results are pretty good, although the languages do not provide exactly the same features so the results aren’t necessarily perfectly equivalent. For example, Visual Basic’s Select Case statement is more flexible than C#’s switch statement, so the tools cannot always perform a round trip conversion from Visual Basic to C# and back. For specific examples, it converts Case 0 To 9 into a series of 10 C# case statements and it cannot handle statements such as Case Is < 0, Is >= 30. (It should probably convert these kinds of Select Case statements into sequences of if-then-else statements instead if trying to use a switch statement.)

Overall, however, the results are reasonably good, can give you a big head start if you need to translate a lot of code, and are free.


Follow me on Twitter   RSS feed   Donate




Posted in programs, reflection, syntax | Tagged , , , , , , , , , , , , , , , | 1 Comment

Copy ListView data into an array in C#

[ListView]

This example uses the following ListView extension method to copy ListView data into a two-dimensional array of strings.

// Return the ListBox's contents in a string[,].
public static string[,] GetListViewData(this ListView lvw)
{
    // Get the number of rows and columns.
    int num_rows = lvw.Items.Count;
    int num_cols = 0;
    for (int i = 0; i < num_rows; i++)
    {
        if (num_cols < lvw.Items[i].SubItems.Count)
            num_cols = lvw.Items[i].SubItems.Count;
    }

    // Make the array.
    string[,] results = new string[num_rows, num_cols];

    // Populate the array.
    // Note that SubItems includes the items, too.
    for (int r = 0; r < num_rows; r++)
    {
        for (int c = 0; c < num_cols; c++)
            results[r, c] = lvw.Items[r].SubItems[c].Text;
    }

    // Return the result.
    return results;
}

The method sets num_rows equal to the number of items in the ListView control’s Items collection. It then loops through that collection to see which item has the most sub-items.

Note that an item’s SubItems collection includes the item, too. For example, suppose the ListView control named lvw has a first item that includes the values Apple, Banana, and Cherry. Then lvw.Items[0].Text is Apple and lvw.Items[0].SubItems contains all three values Apple, Banana, and Cherry.

When it loops through the SubItems collection, the program keeps track of the SubItems collection that has the most items. that gives the number of columns we need in the array.

Having found the number of rows and columns it needs, the program allocates the results array. It then loops through the items again, this time copying the ListView data into the array. When it is done, the method returns the result.

Using the extension method is easy. The following code shows how the main program uses the method when you click the Get Data button.

// Get the ListView's contents.
private void btnGetData_Click(object sender, EventArgs e)
{
    // Get the contents.
    string[,] listview_data = lvwBooks.GetListViewData();

    // Display the contents.
    StringBuilder sb = new StringBuilder();
    int num_rows = listview_data.GetUpperBound(0) + 1;
    int num_cols = listview_data.GetUpperBound(1) + 1;
    for (int r = 0; r < num_rows; r++)
    {
        for (int c = 0; c < num_cols; c++)
        {
            sb.Append(listview_data[r, c] + "|");
        }
        sb.AppendLine();
    }
    txtResult.Text = sb.ToString();
}

This event handler uses the extension method to get the ListView control’s values. It then loops through them adding the values to a StringBuilder. When it is finished, the program displays the resulting string in a text box.


Download Example   Follow me on Twitter   RSS feed   Donate




Posted in arrays, controls, strings | Tagged , , , , , , , , , , | Leave a comment

Draw the spiral of Theodorus in C#

[spiral of Theodorus]

The spiral of Theodorus (which is also called the square root spiral, Einstein spiral, and Pythagorean spiral) was first devised by the Greek mathematician Theodorus of Cyrene during the 5th century BC. The spiral consists of a sequence of right triangles where the ith triangle has side lengths 1, √i, and √(i+1). Each triangle’s edge of length √(i+1) is shared with the next triangle as shown in the following picture from Wikipedia.


[spiral of Theodorus]

When you fill in the number of triangles that you want to draw and click Draw, the following code executes.

private void btnDraw_Click(object sender, EventArgs e)
{
    // Get the spiral of Theodorus's points.
    int num_triangles = int.Parse(txtNumTriangles.Text);
    List<PointF> edge_points = FindTheodorusPoints(num_triangles);

    // Draw the spiral of Theodorus.
    picSpiral.Image = DrawTheodorusSpiral(
        edge_points, picSpiral.ClientSize,
        chkOutline.Checked, chkFill.Checked);
}

This code gets the number of triangles that you entered. It then calls the FindTheodorusPoints method described shortly to get the points on the outside of the spiral of Theodorus. It finishes by calling the DrawSpiral method (also described shortly) to draw the spiral.

The following sections describe the FindTheodorusPoints and DrawSpiral methods and their helper routines.

FindTheodorusPoints

The following code shows the FindTheodorusPoints method.

// Find points on the spiral of Theodorus.
private List<PointF> FindTheodorusPoints(int num_triangles)
{
    // Find the edge points.
    List<PointF> edge_points = new List<PointF>();

    // Add the first point.
    float theta = 0;
    float radius = 1;
    for (int i = 1; i <= num_triangles; i++)
    {
        radius = (float)Math.Sqrt(i);
        edge_points.Add(new PointF(
            radius * (float)Math.Cos(theta),
            radius * (float)Math.Sin(theta)));
        theta -= (float)Math.Atan2(1, radius);
    }

    return edge_points;
}

This method first creates an edge_points list to hold the triangles’ outer vertices.

The variable theta keeps track of the angle that the points make with respect to the spiral’s center. Variable radius keeps track of the length of the triangles’ side lengths.

The code sets theta = 0 and radius = 1, and then enters a loop to find the leading edge point for each triangle. Inside the loop, the code uses theta and radius to find the triangle’s point and adds it to the list.

Each triangle’s inner angle (the one by the spiral’s center) is the arc tangent of the opposite side (which always has length 1) and the adjacent side. The adjacent side for the ith triangle has length radius = √i, so the program subtracts Atan2(1, radius) from theta to prepare for the next point on the spiral. (The code subtracts this value instead of adding it so the angles increase counterclockwise for the triangles.)

After it finishes finding the edge points, the method returns them.

DrawTheodorusSpiral

The following code shows the DrawTheodorusSpiral method, which draws the spiral.

// Draw the spiral of Theodorus.
private Bitmap DrawTheodorusSpiral(List<PointF> edge_points,
    Size size, bool outline_triangles, bool fill_triangles)
{
    // Make the bitmap and associated Graphics object.
    int wid = size.Width;
    int hgt = size.Height;
    Bitmap bm = new Bitmap(wid, hgt);
    using (Graphics gr = Graphics.FromImage(bm))
    {
        gr.SmoothingMode = SmoothingMode.AntiAlias;
        gr.Clear(Color.White);

        // Make brushes.
        Color[] colors = RainbowColors(255);
        Brush[] brushes = ColorsToBrushes(colors);

        // Scale and center.
        float xmin, xmax, ymin, ymax;
        GetBounds(edge_points, out xmin, out xmax,
            out ymin, out ymax);
        RectangleF drawing_rect = new RectangleF(
            xmin, ymin, xmax - xmin, ymax - ymin);
        RectangleF target_rect = new RectangleF(
            5, 5, wid - 10, hgt - 10);
        MapDrawing(gr, drawing_rect, target_rect, false);

        // Draw.
        using (Pen pen = new Pen(Color.Black, 0))
        {
            int num_brushes = brushes.Length;
            for (int i = edge_points.Count - 1; i > 0; i--)
            {
                PointF[] points =
                {
                    new PointF(0, 0),
                    new PointF(
                        edge_points[i].X,
                        edge_points[i].Y),
                    new PointF(
                        edge_points[i - 1].X,
                        edge_points[i - 1].Y),
                };
                if (fill_triangles)
                    gr.FillPolygon(brushes[i % num_brushes],
                        points);
                if (outline_triangles)
                    gr.DrawPolygon(pen, points);
            }
        }
    }

    return bm;
}

This method draws the spiral of Theodorus on a bitmap of a specified size and returns the bitmap.

It starts by creating a bitmap of the correct size, making an associated Graphics object, and clearing it.

The method then calls the RainbowColors method to make some colors. It then uses the ColorsToBrushes method to convert those colors into an array of brushes. Both of those methods are described shortly.

The code then calls the GetBounds method (also described shortly) to get bounds for the spiral’s edge points. It uses the bounds to make a rectangle representing the drawing area. It then passes the drawing rectangle and a rectangle that represents the bitmap’s surface (minus a margin) to the MapDrawing method.

The MapDrawing method applies translation and scaling transformations to the Graphics object to make drawing commands it inside the target area. For more information on this method, see the post Scale a drawing to fit a target area in C#.

Now the method draws the spiral of Theodorus. It creates a black pen with thickness 0. (Pens with thickness 0 are not scaled even if the Graphics object includes a scaling transformation.)

[spiral of Theodorus]

The method then enters a loop that runs from the last triangle point to the first. The loops runs last-to-first instead of first-to-last because later triangles may overlap earlier ones. The picture on the right shows the spiral of Theodorus with 30 triangles. You can see that the outer ones overlap the inner ones. Drawing the triangles last-to-first lets you see pieces of all of the triangles.

After it fills a triangle, the method outlines it.

As it draws each triangle, the code checks the outline_triangles and fill_triangles values to see whether it should outline or fill the triangles. (Draw the spiral without filling it if you want to see the overlapping outlines of the triangles.)

RainbowColors

The following code shows the RainbowColors method.

// Return an array of rainbow colors.
private Color[] RainbowColors(byte alpha)
{
    return new Color[]
    {
        Color.FromArgb(alpha, 255, 0, 0),
        Color.FromArgb(alpha, 255, 255, 0),
        Color.FromArgb(alpha, 255, 128, 0),
        Color.FromArgb(alpha, 0, 255, 0),
        Color.FromArgb(alpha, 0, 255, 255),
        Color.FromArgb(alpha, 0, 0, 255),
        Color.FromArgb(alpha, 255, 0, 255),
    };
}

This method simply builds an array holding a predefined set of colors. The method takes an alpha parameter in case you want to make the colors semi-transparent. (I originally thought that would be useful in this example, but it just made the result more cluttered.)

ColorsToBrushes

The following code shows the ColorsToBrushes helper method.

// Convert colors to brushes.
private Brush[] ColorsToBrushes(Color[] colors)
{
    int num_colors = colors.Length;
    Brush[] brushes = new Brush[num_colors];
    for (int i = 0; i < num_colors; i++)
        brushes[i] = new SolidBrush(colors[i]);
    return brushes;
}

This method simply loops through an array of colors and makes a SolidBrush for each.

GetBounds

The following code shows the GetBounds method.

// Get the points' bounds.
private void GetBounds(List<PointF> points,
    out float xmin, out float xmax,
    out float ymin, out float ymax)
{
    // Find the bounds.
    xmin = points[0].X;
    xmax = xmin;
    ymin = points[0].Y;
    ymax = ymin;
    foreach (PointF point in points)
    {
        if (xmin > point.X) xmin = point.X;
        if (xmax < point.X) xmax = point.X;
        if (ymin > point.Y) ymin = point.Y;
        if (ymax < point.Y) ymax = point.Y;
    }
}

This method simply loops through an array of PointF and finds their minimum and maximum X and Y values. (You could use LINQ to do something similar, but it wouldn’t be any easier to read and it would be slightly slower.)

Summary

Download the example to see additional details and to experiment with the program. For example, you might try using semi-transparent colors, with or without the triangle outlines. If you fill around 10,000 or more triangles without outlining them, you can also see an interesting wave effect flowing through the spiral’s rings.

For more information on the spiral of Theodorus, see the Wikipedia article Spiral of Theodorus.


Download Example   Follow me on Twitter   RSS feed   Donate




Posted in algorithms, drawing, graphics, mathematics | Tagged , , , , , , , , , , , , , | Leave a comment

Add LINQ to autocomplete in C#

[autocomplete]

This example adds LINQ to the example Improve autocomplete suggestion in C#. It adds LINQ in two places: when it loads the list of words and when the program searches for the best matches that begin with a particular letter.

The following code shows how the older version of the program loads its word list.

// Non-LINQ method.
foreach (string line in lines)
{
    if (line.Length > 1)
    {
        // Get the first letter.
        int index = (int)line.ToUpper()[0] - (int)'A';
        Words[index].Add(line);
    }
}

This code loops through the words in the lines array. For each word it gets the word’s first letter and uses it to decide which list in the Words array of lists should hold that word.

The following code shows the LINQ version.

// LINQ method.
var word_groups =
    from string line in lines
    group line by line.ToUpper()[0] into g
    select new { Letter = g.Key, Words = g };
foreach (var g in word_groups)
{
    int index = (int)g.Letter - (int)'A';
    Words[index] = g.Words.ToList();
}

This code defines a query that selects the words in the lines array and groups them by their first letters. For each group, the program uses the group’s first letter to calculate the index where the group’s words should be stored in the Words list and then stores the group there converting it into a List.

LINQ is often not as fast as other methods. Its strength lies in the fact that it’s easy to write and often produces code that is easier to read than code that you write to perform similar actions. In this case, however, I don’t think the LINQ is easier to write or understand. The LINQ group command has a confusing syntax and the result is rather confusing. For this simple example that selects all of the items, LINQ doesn’t add much and actually makes the code longer, so I wouldn’t use it here.

The other use of LINQ in this example, however, is more helpful. The following code shows how the previous version of the program finds the best matches for a word.

// Find the best matches for the typed word.
private void FindBestMatches(string word, int num_matches,
    out string[] words, out int[] values)
{
    // Get the word list for the word's first letter.
    int index = (int)word.ToUpper()[0] - (int)'A';

    // Find words that start with the same letter.
    List<string> match_words = new List<string>();
    List<int> match_values = new List<int>();
    foreach (string test_word in Words[index])
    {
        // Consider the next word up to
        // the length of the typed word.
        int max_length = Math.Min(test_word.Length, word.Length);
        string short_word = test_word.Substring(0, max_length);

        // Build the edit graph.
        Node[,] nodes = MakeEditGraph(word, short_word);

        // List the distance.
        int x = nodes.GetUpperBound(0);
        int y = nodes.GetUpperBound(1);
        match_words.Add(test_word);
        match_values.Add(nodes[x, y].distance);
    }

    // Sort the matches by distance, smallest distance first.
    string[] match_words_array = match_words.ToArray();
    int[] match_values_array = match_values.ToArray();
    Array.Sort(match_values_array, match_words_array);

    // Return the desired number of matches.
    int max = Math.Min(num_matches, match_values_array.Length);
    words = new string[max];
    Array.Copy(match_words_array, words, max);
    values = new int[max];
    Array.Copy(match_values_array, values, max);
}

The code loops through the list of words that have the same initial letter as the target word. For each test word in the list, the code creates an edit graph representing the transformation from the word to the test word and saves the word and its edit distance. After the loop finishes, the program sorts the words and their edit distances and returns at most the desired number of matches.

A few hints that LINQ might be useful here include the fact that the code searches over lists (words with matching first letters), sorts some arrays (the words and their edit distances), and returns at most a certain number of items (the words and their edit distances again).

This code performs a somewhat involved calculation to find the edit distance for a word. While you may be able to work that calculation into LINQ code, LINQ statements are a lot easier to understand if you extract that calculation into a separate method. The new example does that with the following GetEditDistance method.

// Return the edit distance from target_word to test_word.
private int GetEditDistance(string target_word, string test_word)
{
    // Make test_word the same length as target_word.
    int max_length = Math.Min(test_word.Length, target_word.Length);
    test_word = test_word.Substring(0, max_length);

    // Build the edit graph.
    Node[,] nodes = MakeEditGraph(target_word, test_word);

    // Return the distance.
    int x = nodes.GetUpperBound(0);
    int y = nodes.GetUpperBound(1);
    return nodes[x, y].distance;
}

This method performs the same steps used by the previous examples to calculate a test word’s edit distance. It then returns that distance.

The following code shows how the new example uses this GetEditDistance method and LINQ to find the best matches for a word.

// Find the best matches for the typed word.
private string[] FindBestMatches(string target_word,
    int num_matches)
{
    // Get the word list for the word's first letter.
    int index = (int)target_word.ToUpper()[0] - (int)'A';

    // Use LINQ to select the test words' edit distance.
    var word_distance_query =
        from string test_word in Words[index]
        orderby GetEditDistance(target_word, test_word)
        select GetEditDistance(target_word, test_word) +
            " " + test_word;

    // Return up to the desired number of matches.
    return word_distance_query.Take(num_matches).ToArray();
}

This code builds a LINQ query that searches the Words list that contains the words beginning with the target word’s first letter. It orders the results by the edit distances between those words and the target word. Finally, it selects the edit distances and the corresponding words.

Having built the query, the code invokes it’s Take method to take at most the desired number of matches. It calls the result’s ToArray method to convert the result into an array and returns it.

This example has one other minor change. The previous version kept the test words and their edit distances in two separate arrays so it could sort the arrays by edit distance. It then needed to combine the values to create strings showing the words and their edit distances. The TextChanged event handler that calls FindBestMatches must then assemble the edit distances and words as shown in the following code.

// Find good guesses for this word.
private void txtWord_TextChanged(object sender, EventArgs e)
{
    lstGuesses.Items.Clear();
    string word = txtWord.Text;
    if (word.Length == 0) return;

    // Find the best matches.
    string[] words;
    int[] values;
    FindBestMatches(word, 10, out words, out values);

    // Display the best matches.
    for (int i = 0; i < words.Length; i++)
    {
        lstGuesses.Items.Add(values[i].ToString() +
            '\t' + words[i]);
    }
}

The new example’s LINQ code sorts the results, builds the result strings, and returns at most a desired number of items all in one step. This not only simplifies the FindBestMatches method, but it also simplifies the text box’s TextChanged event handler that calls it as shown in the following code.

// Find good guesses for this word.
private void txtWord_TextChanged(object sender, EventArgs e)
{
    lstGuesses.DataSource = null;
    string word = txtWord.Text;
    if (word.Length == 0) return;

    // Find the best matches.
    lstGuesses.DataSource = FindBestMatches(word, 100);
}

This use of LINQ is worth the effort. It makes the FindBestMatches method easier to understand and makes the TextChanged event handler that calls it simpler, too. It probably reduces performance, but this application is fast enough that the user won’t notice.


Download Example   Follow me on Twitter   RSS feed   Donate




Posted in algorithms, LINQ, strings | Tagged , , , , , , , , , , , , , , | Leave a comment

Improve autocomplete suggestion in C#

[autocomplete]

This example improves on the example Suggest autocomplete words in C#. The previous example loads all of its words into a big array. Then, to find the words that start with a particular letter, the program uses a binary search to find the letter in the word list. The program then loops through the words in the list until it finds a word that doesn’t begin with the same letter.

When this new example starts, it loads the words that start with different letters into different lists. Then when it needs to process the words that start with a given letter, it simply loops through the appropriate list.

The following code shows how the program loads its lists of words.

// The dictionary.
private List<string>[] Words;

// Load the dictionary.
private void Form1_Load(object sender, EventArgs e)
{
    // Get the words from the dictionary file.
    string[] lines = File.ReadAllLines("Words.txt");

    // Group the words by first letter.
    Words = new List<string>[26];
    for (int i = 0; i < 26; i++)
        Words[i] = new List<string>();
    foreach (string line in lines)
    {
        if (line.Length > 1)
        {
            // Get the first letter.
            int index = (int)line.ToUpper()[0] - (int)'A';
            Words[index].Add(line);
        }
    }

    txtWord.Text = "absi";
}

The program uses the File class’s ReadAllLines method to read the words into an array. It then loops through the array.

For each word in the array (not counting single letters such as “A” and “R”), the code uses the word’s first letter to determine which list should hold the word and then adds the word to that list.

The other change to the program occurs in the FindBestMatches method. In the previous version of that method uses binary search to find the first word in the list starting with a given letter and then uses a somewhat confusing loop to examine the words that follow until it finds a word that starts with a new letter or it runs out of words.

The following code shows the new version of the loop.

// Get the word list for the word's first letter.
int index = (int)word.ToUpper()[0] - (int)'A';

// Find words that start with the same letter.
List<string> match_words = new List<string>();
List<int> match_values = new List<int>();
foreach (string test_word in Words[index])
{
    ...
}

This code subtracts the ASCII value of the letter A from the word’s first letter to get the index of the list that holds words starting with the same letter. It creates output lists for words that match and their edit distance values much as before. It then uses a simple foreach loop to examine the words that have the same first letter as the target word. The omitted code indicated by the ellipsis is the same as in the previous version.

This version is slightly faster (you can’t really tell the difference when you’re running it) but the loop in the FindBestMatches method is easier to understand.

In my next post, I’ll convert some of the searches performed by the program into LINQ. If you have time, you might want to give them a try yourself before you read that post.


Download Example   Follow me on Twitter   RSS feed   Donate




Posted in algorithms, strings | Tagged , , , , , , , , , , , , , , | 1 Comment

Suggest autocomplete words in C#

[autocomplete]

This example shows one way that a program can suggest words for the user.

When I type something on my phone, it displays a list of possible words for autocomplete below the editing area. For example, if I type “gping” it suggests “going” as a possible word that I might be trying to type.

Edit Distance

I don’t know what algorithm the phone uses to suggest words, but this example shows one possible approach. This program uses an “edit distance” algorithm to decide how similar the word you have typed so far is from those in a dictionary. It then suggests the words that are most similar to what you have typed.

To completely understand the program, you need to understand the edit distance algorithm. I wrote an article about this algorithm and you can find it in the DevX article Turn a Parsnip into a Turnip with Edit Distance Algorithms.

You can read the article on DevX so I won’t repeat it here, but the general idea is to build an edit graph that shows the best way to convert one word into another word by inserting and removing letters. The last node in the graph gives the “distance” from the start word to the end word.

When you type into this example’s upper text box, the following event handler executes to display the best matches.

// Find good guesses for this word.
private void txtWord_TextChanged(object sender, EventArgs e)
{
    lstGuesses.Items.Clear();
    string word = txtWord.Text;
    if (word.Length == 0) return;

    // Find the best matches.
    string[] words;
    int[] values;
    FindBestMatches(word, 10, out words, out values);

    // Display the best matches.
    for (int i = 0; i < words.Length; i++)
    {
        lstGuesses.Items.Add(values[i].ToString() +
            '\t' + words[i]);
    }
}

This code clears the program’s ListBox of matches. It then gets the text that you typed and, if that text is blank, returns.

If the text is not blank, the code calls the FindBestMatches method to get arrays containing the best matches and their edit distance values. The results are sorted in increasing order of edit distance value.

The event handler finishes by displaying the edit distance values and the words in the program’s ListBox so you can see them.

All of the hard work is done in the following FindBestMatches method.

// Find the best matches for the typed word.
private void FindBestMatches(string word, int num_matches,
    out string[] words, out int[] values)
{
    // Find words that start with the same letter.
    string start_char = word.Substring(0, 1).ToUpper();
    int start_index = Array.BinarySearch(Words, start_char);
    List<string> match_words = new List<string>();
    List<int> match_values = new List<int>();
    for (int i = start_index + 1; i < Words.Length; i++)
    {
        // Get the next word and make sure it starts
        // with the same letter.
        string test_word = Words[i];
        if (test_word.Substring(0, 1).ToUpper() != start_char)
            break;

        // Consider the next word up to the length
        // of the typed word.
        int max_length = Math.Min(test_word.Length, word.Length);
        string short_word = test_word.Substring(0, max_length);

        // Build the edit graph.
        Node[,] nodes = MakeEditGraph(word, short_word);

        // List the distance.
        int x = nodes.GetUpperBound(0);
        int y = nodes.GetUpperBound(1);
        match_words.Add(test_word);
        match_values.Add(nodes[x, y].distance);
    }

    // Sort the matches by distance, smallest distance first.
    string[] match_words_array = match_words.ToArray();
    int[] match_values_array = match_values.ToArray();
    Array.Sort(match_values_array, match_words_array);

    // Return the desired number of matches.
    int max = Math.Min(num_matches, match_values_array.Length);
    words = new string[max];
    Array.Copy(match_words_array, words, max);
    values = new int[max];
    Array.Copy(match_values_array, values, max);
}

The Words array contains a list of 14,596 words in sorted order. The list includes each letter of the alphabet. For example, the section of words starting with the letter “a” begins with the value “A” to make finding those words easier.

The FindBestMatches method gets the first character in the target word and converts it to upper case. It then uses the Array.BinarySearch method to locate that letter in the word list. (Note that BinarySearch only works if the array is sorted, which it is.) For example, if you have entered “bea,” then the method searches for the word “B.”

Next, the code loops through the array examining words that start with this letter. If you typed “bea,” then it loops over words that start with “b.”

For each word that starts with the given letter, the program truncates the word to the length that you have typed so far. If you typed “bea,” and the program is considering the word “barter,” it truncates that test word to “bar.”

Next, the program builds an edit graph that transforms what you typed into the test word (for example, “bea” into “bar”). It adds the entire test word (barter) and its edit distance to the match_words and match_values lists.

After it has processed all of the words that start with the given letter, the method must return those that have the smallest edit distance values. To do that, it converts the match_words and match_values lists into arrays and uses Array.Sort to sort them. It uses match_words as the array to sort and uses match_values as an array of keys to use while sorting. The Array.Sort method sorts match_values in increasing order and arranges match_words so its values correspond to the numbers in match_values.

Finally, the FindBestMatches method uses Array.Copy to copy the desired number of matches and their edit distances into the words and values output arrays for return to the calling code.

TextBox AutoComplete

The TextBox control also provides some autocomplete features, which the example demonstrates in its bottom text box. When the program starts, the following Form_Load event handler loads the Words array and prepares the bottom text box for autocomplete.

// The dictionary.
private string[] Words;

// Load the dictionary.
private void Form1_Load(object sender, EventArgs e)
{
    Words = File.ReadAllLines("Words.txt");
    txtWord.Text = "absi";

    // Make an autocomplete TextBox.
    AutoCompleteStringCollection word_source =
        new AutoCompleteStringCollection();
    word_source.AddRange(Words);
    txtAuto.AutoCompleteSource = AutoCompleteSource.CustomSource;
    txtAuto.AutoCompleteCustomSource = word_source;
    txtAuto.AutoCompleteMode = AutoCompleteMode.Suggest;
}

The event handler uses the File class’s ReadAllLines method to load the file Words.txt into the Words array. It then enters the test word fragment “absi” in the form’s upper text box.

Next, the code creates an AutoCompleteStringCollection object to hold the text box’s auto completion words. This object behaves mostly like a string collection. (My guess is that internally it uses a trie, also known as a radix tree or prefix tree, to make searching for words easier. For more information on tries, see the Wikipedia article trie.)

The code uses the collection’s AddRange method to add the words in the Words array to it. It then sets the text box’s AutoCompletionSource property to CustomSource, its AutoCompletionCustomSource to the string collection, and its AutoCompleteMode property to Suggest.

After that, the text box works automatically. When you type the beginning of a word, the control displays dropdown list of words that begin with what you have typed. You can use then click on a word or the up and down arrows and press Enter to select a word to place in the text box.

Notes

As an exercise, you might try using LINQ to implement at least part of the FindBestMatches method. It might not work well for selecting words that start with the correct letter (it would loop through every entry in the word list), but it might make pulling out the best matches easier.

This method is not what my phone does but it does produce some reasonable suggestions. There are several ways that it might be improved. For example, this method considers all character exchanges equally likely. If you type “whst” the code considers the possibilities “whit” and “what” equally likely. If you look on the phone’s keypad, however, you’ll see that the s and a keys are right next to each other, so I probably tried to type “what” and just hit the wrong key. You could modify the edit distance algorithm to give preference to swapping letters that were close to each other on the keypad. (I may do that at some point.)

You could also probably improve the algorithm by considering the grammar and meaning of the sentence being typed. For example, if you type “Are you going ton,” then the final word is more likely to be “tonight” than “tonnage.” This is a much bigger topic, so I won’t pursue it.

This example also doesn’t include contractions in its word list. If you type “whats,” then you probably mean “what’s” and adding that to the word list (with some special rules for adding apostrophes) would give you a better result.

Finally, this method assumes that you typed the first letter of the word correctly but that may not always give the best solution. If you type “gello,” then “hello” is probably a better match than “gallop.” (I may work on this issue a bit later, too.)

As you can see, there are several ways you can improve this program, but it does give reasonable suggestions in many cases.


Download Example   Follow me on Twitter   RSS feed   Donate




Posted in algorithms, strings | Tagged , , , , , , , , , , , , , , | 5 Comments