Click here to Skip to main content
15,878,852 members
Articles / Programming Languages / C#

Generic DFA State Machine for .NET

Rate me:
Please Sign up or sign in to vote.
4.75/5 (42 votes)
21 May 2003BSD6 min read 224.1K   3.6K   75  
Seemless NFA to DFA transfers with GraphViz graphing integration
using System;
using System.Collections;

namespace leppie.FA
{
	/// <summary>
	/// Summary description for Combination.
	/// </summary>
   public class Combination
   {
      ArrayList numbers;

      public Combination(ArrayList elements)
      {
         this.numbers = elements;
      }

      public ArrayList Get(int size, bool allowrepeat, bool allownulls, bool ordered)
      {
         if (size > numbers.Count && !allowrepeat && !allownulls) 
            throw new InvalidOperationException("Size cannot be greater than input count when repeating is not allowed");
         if (!ordered && (allownulls || allowrepeat))
            throw new InvalidOperationException("That combination is not allowed.");
#if DEBUG	
         DateTime now = DateTime.Now;
#endif		
			int estsize = Convert.ToInt32(Math.Pow(numbers.Count, size));
         ArrayList finalout = new ArrayList(estsize);
         ArrayList orderarr = new ArrayList(estsize);

         int k = 1;
         if (!allownulls) k = size;
			
         for (; k < size + 1; k++)
         {
            int many = Convert.ToInt32(Math.Pow(numbers.Count, k)); // many = maxvalue
            ArrayList output = new ArrayList(many);
            ArrayNumber arnum = new ArrayNumber(0, numbers.Count); 
			
            for (int i = 0; i < many; i++)
            {
               //many = Convert.ToInt32(Math.Pow(numbers.Count, 1));
               bool repeattest = false;
               bool ordertest = false;

               int[] arr = arnum.ToArray(k);
               int testint = Total(arr);

               if (!ordered)ordertest = TestOrdered(arr, orderarr); // problem adding number

               ArrayList onemore = new ArrayList(k);

               for (int j = 0; j < arr.Length; j++)
               {
                  if (!allowrepeat)
                  {
                     for (int m = 0; m < j; m++)
                     {
                        if (arr[j] == arr[m]) 
                           repeattest = true;
                     }
                  }
                  onemore.Add(numbers[arr[j]]);
               }

               arnum++;

               if (!allowrepeat && repeattest) continue;
               if (!ordered && ordertest) continue;
               orderarr.Add(testint);
               output.Add(onemore);
            }	

            finalout.AddRange(output);
				
         }
#if DEBUG
         TimeSpan ts = DateTime.Now - now;
         Console.WriteLine("Time: {0}ms \tN:{1} R:{2} #:{6} \tRepeat:{3} \tNulls:{4} \tOrder:{5}",
            ts.TotalMilliseconds.ToString("F0"), numbers.Count, size, allowrepeat, allownulls, ordered, finalout.Count);
#endif
         return finalout;
      }

      private bool TestOrdered(int[] totest, ArrayList totallist)
      {
         int testint = Total(totest);
         return totallist.Contains(testint);
      }

      private int Total(int[] intarr)
      {
         int output = 0;
         foreach (int i in intarr)
         {
            output += i;
         }
         return output;
      }

      internal struct ArrayNumber
      {
         int num;
         int basenum;

         public ArrayNumber(int num, int basenum)
         {
            this.num = num;
            this.basenum = basenum;
         }

         public static ArrayNumber operator ++(ArrayNumber arrnum) 
         {
            arrnum.num++;
            return arrnum;
         }

         public int[] ToArray(int size)
         {
            int[] output = new int[size];
            int numcopy = num;

            int maxvalue = Convert.ToInt32(Math.Pow(basenum, size));

            if (maxvalue > num)
            { //ok
               for (int i = 0; i < size; i++)
               {
                  int test = Convert.ToInt32(Math.Pow(basenum, size - 1 - i));
                  output[i] = numcopy/test;
                  numcopy -= (numcopy/test * test);
               }
            }
            else throw new OverflowException("Number is too big to implement " +
                    "in array of size: " + size + " MaxValue: " + maxvalue );

            return output;
         }
      }
   }
}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The BSD License


Written By
Software Developer
South Africa South Africa
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions