public static Pair<HashSet<char>, Automaton<BDD>> parseDFAFromString(string str, CharSetSolver solver)
        {
            var lines = Regex.Split(str, "\r\n|\r|\n");
            HashSet<char> al = new HashSet<char>();

            var line = lines[0];
            var tokens = line.Split(new char[] { ' ' });
            for (int i = 1; i < tokens.Length; i++)
                al.Add(tokens[i].ToCharArray()[0]);

            var finalStates = new List<int>();
            line = lines[2];
            tokens = line.Split(new char[] { ' ' });
            for (int i = 2; i < tokens.Length; i++)
                finalStates.Add(Convert.ToInt32(tokens[i]));

            var moves = new List<Move<BDD>>();
            for (int i = 3; i < lines.Length; i++)
            {
                tokens = lines[i].Split(new char[] { ',' });
                if (tokens.Length > 1)
                    moves.Add(new Move<BDD>(Convert.ToInt32(tokens[0]), Convert.ToInt32(tokens[1]), solver.MkCharConstraint(false, tokens[2].ToCharArray()[0])));
            }

            return new Pair<HashSet<char>, Automaton<BDD>>(al, Automaton<BDD>.Create(0, finalStates, moves));
        }

        public void ChooseUnifromlyTest()
        {
            CharSetSolver solver = new CharSetSolver(BitWidth.BV16);

            BDD set1 = solver.MkRangeConstraint('\0', '\x01', true);
            BDD set2 = solver.MkRangeConstraint( '\u0FFF', '\u0FFF');
            string set2str = solver.PrettyPrint(set2);
            BDD set3 = solver.MkRangeConstraint( '\u00FF', '\u00FF');
            BDD set4 = solver.MkRangeConstraint( '\u000F', '\u000F');

            BDD set = solver.MkOr(new BDD[]{set2, set3, set4, set1});

            string setstr = solver.PrettyPrint(set);

            set.ToDot(@"foo.dot");

            var map = new Dictionary<char, int>();
            map['\0'] = 0;
            map['\x01'] = 0;
            map['\u0FFF'] = 0;
            map['\u00FF'] = 0;
            map['\u000F'] = 0;

            for (int i = 0; i < 50000; i++)
            {
                var c = solver.ChooseUniformly(set);
                map[c] += 1;
            }
            foreach (var kv in map)
                Assert.IsTrue(kv.Value > 9700);
        }

        public void TestGroups()
        {
            CharSetSolver css = new CharSetSolver(BitWidth.BV7);
            var regex = @"\W*(?<key>\w{1,3})\s*(?<value>\d{2,3})\D*";
            bool b;
            var captures = css.ConvertCaptures(regex, out b);
            Assert.IsTrue(captures.Length == 5);
            for (int i = 0; i < captures.Length; i++ )
            {
                var aut = captures[i].Item2;
                var name = captures[i].Item1;
                if (name == "")
                    name = "skip" + i;
                //css.ShowGraph(aut, name);
            }
            string s = "foobar";
            s.StartsWith("foo");
            s.EndsWith("bar");
            s.Equals("foobar");

            for (int i = 0; i < captures.Length; i++)
            {

            }
        }

        public void intEq2()
        {
            var solver = new CharSetSolver(BitWidth.BV64);

            List<char> alph = new List<char> { 'a', 'b', 'c' };
            HashSet<char> al = new HashSet<char>(alph);

            PDLPred phi = new PDLIntEq(new PDLAllPos(), 2);

            StringBuilder sb = new StringBuilder();


            phi.ToMSO(new FreshGen()).ToString(sb);

            System.Console.WriteLine(sb);

            var dfa = phi.GetDFA(al, solver);

            var test = solver.Convert(@"^(a|b|c){2}$");

            Assert.IsTrue(dfa.IsEquivalentWith(test, solver));

            ////string file = "../../../TestPDL/DotFiles/IntEq2";

            //solver.SaveAsDot(dfa, "aut", file);

        }

        public void TextP48()
        {
            var solver = new CharSetSolver(CharacterEncoding.Unicode);
            var alph = new List<char> { 'a', 'b' };
            var al = new HashSet<char>(alph);

            var moves = new List<Move<CharSet>>();

            var a = solver.MkCharConstraint(false, 'a');
            var b = solver.MkCharConstraint(false, 'b');

            moves.Add(new Move<CharSet>(0, 1, a));
            moves.Add(new Move<CharSet>(0, 4, b));
            moves.Add(new Move<CharSet>(1, 4, a));
            moves.Add(new Move<CharSet>(1, 2, b));
            moves.Add(new Move<CharSet>(2, 3, a));
            moves.Add(new Move<CharSet>(2, 3, b));
            moves.Add(new Move<CharSet>(3, 2, a));
            moves.Add(new Move<CharSet>(3, 2, b));
            moves.Add(new Move<CharSet>(4, 4, a));
            moves.Add(new Move<CharSet>(4, 4, b));

            var dfa = Automaton<CharSet>.Create(0, new int[] { 2 }, moves).Determinize(solver).Minimize(solver);
            var sb = new StringBuilder();

            DFAUtilities.printDFA(dfa, al, sb);
            System.Console.WriteLine(sb);
            
        }

        public void MSOFirstLastSucc()
        {
            var solver = new CharSetSolver(BitWidth.BV64);  //new solver using ASCII encoding

            List<char> alph = new List<char> { 'a', 'b' };
            HashSet<char> al = new HashSet<char>(alph);

            //ex x. first(x)
            MSOFormula first = new MSOFirst("x");
            MSOFormula last = new MSOLast("y");
            MSOFormula succ = new MSOSucc("x", "y");
            MSOFormula and = new MSOAnd(new MSOAnd(first, last), succ);
            MSOFormula formula = new MSOExistsFO("x", new MSOExistsFO("y", and));

            Assert.IsTrue(formula.CheckUseOfVars());

            var dfa = formula.getDFA(al, solver);

            var test = solver.Convert(@"^(a|b){2}$");

            Assert.IsTrue(dfa.IsEquivalentWith(test, solver));

            string file = "../../../MSOZ3Test/DotFiles/ab";

            solver.SaveAsDot(dfa, "aut", file);   //extension .dot  is added automatically when missing
        }

        public void Feedback2()
        {
            CharSetSolver solver = new CharSetSolver(BitWidth.BV64);
            var al = new HashSet<char>(new char[] { 'a', 'b' });

            var dfa1 = new PDLModSetEq(new PDLIndicesOf("a"), 2, 1).GetDFA(al, solver);


            var a = solver.MkCharConstraint(false, 'a');
            var b = solver.MkCharConstraint(false, 'b');
            var movescorrect = new List<Move<BDD>>();

            movescorrect.Add(new Move<BDD>(0, 0, b));
            movescorrect.Add(new Move<BDD>(0, 1, a));
            movescorrect.Add(new Move<BDD>(1, 0, a));
            movescorrect.Add(new Move<BDD>(1, 0, b));

            var dfa2 = Automaton<BDD>.Create(0, new int[] { 1 }, movescorrect);

            var v4 = DFAGrading.GetGrade(dfa1, dfa2, al, solver, timeout, 10, FeedbackLevel.Hint);
            Console.WriteLine("Grade: {0}", v4.First);
            foreach (var v in v4.Second)
                Console.WriteLine("Feedback: {0}", v);


        }

 public DFAFeedback(FeedbackLevel level, HashSet<char> alphabet, double utility, CharSetSolver solver)
 {
     this.alphabet = alphabet;
     this.level = level;
     this.solver = solver;
     this.utility = Math.Round(Math.Max(1-utility,0)*100);
 }

        public void MyTest()
        {
            PDLEnumerator pdlEnumerator = new PDLEnumerator();
            var solver = new CharSetSolver(BitWidth.BV64);
            List<char> alph = new List<char> { 'a', 'b' };
            HashSet<char> al = new HashSet<char>(alph);

            var a = solver.MkCharConstraint(false, 'a');
            var b = solver.MkCharConstraint(false, 'b');
            var moves = new List<Move<BDD>>();

            moves.Add(new Move<BDD>(0, 1, a));
            moves.Add(new Move<BDD>(0, 3, b));
            moves.Add(new Move<BDD>(1,2, b));
            moves.Add(new Move<BDD>(2, 1, a));
            moves.Add(new Move<BDD>(1, 1, a));
            moves.Add(new Move<BDD>(2, 2, b));

            moves.Add(new Move<BDD>(3, 4, a));
            moves.Add(new Move<BDD>(4, 3, b));
            moves.Add(new Move<BDD>(3, 3, b));
            moves.Add(new Move<BDD>(4, 4, a));

            var dfa1 = Automaton<BDD>.Create(0, new int[] { 0,1,3 }, moves).Determinize(solver).Minimize(solver);
            foreach (var v in pdlEnumerator.SynthesizePDL(al, dfa1, solver, new StringBuilder(), 5000))
            {
                Console.WriteLine(PDLUtil.ToEnglishString(v));
                break;
            }
        }

        public static Automaton<BDD> ReadFromString(CharSetSolver solver, string automaton)
        {
            var lines = automaton.Split(new char[] { '\n','\r' }, StringSplitOptions.RemoveEmptyEntries);
            int initialState = int.Parse(lines[0]);
            var moves = new Dictionary<Pair<int, int>, BDD>();
            var allmoves = new List<Move<BDD>>();
            int[] finals = Array.ConvertAll(lines[1].TrimEnd(' ').Split(' '), s => int.Parse(s));
            for (int i = 2; i < lines.Length; i++)
            {
                int[] elems = Array.ConvertAll(lines[i].TrimEnd(' ').Split(' '), s => int.Parse(s));
                var key = new Pair<int, int>(elems[0], elems[3]);
                if (elems[1] == -1)
                    allmoves.Add(Move<BDD>.Epsilon(elems[0], elems[3]));
                else
                {
                    var pred = solver.MkCharSetFromRange((char)elems[1], (char)elems[2]);
                    if (moves.ContainsKey(key))
                        moves[key] = solver.MkOr(moves[key], pred);
                    else
                        moves[key] = pred;
                }
            }
            foreach (var kv in moves)
                allmoves.Add(Move<BDD>.Create(kv.Key.First, kv.Key.Second, kv.Value));

            var aut = Automaton<BDD>.Create(solver, initialState, finals, allmoves);
            return aut;
        }

        /// <summary>
        /// Each transition has the form int[]{fromState, intervalStart, intervalEnd, toState}.
        /// If intervalStart = intervalEnd = -1 then this is an epsilon move.
        /// </summary>
        public static Automaton<BDD> ReadFromRanges(CharSetSolver solver, int initialState, int[] finalStates, IEnumerable<int[]> transitions)
        {
            var moves = new Dictionary<Pair<int, int>, BDD>();
            var allmoves = new List<Move<BDD>>();
            int[] finals = finalStates;
            foreach (var elems in transitions)
            {
                var key = new Pair<int, int>(elems[0], elems[3]);
                if (elems[1] == -1)
                    allmoves.Add(Move<BDD>.Epsilon(elems[0], elems[3]));
                else
                {
                    var pred = solver.MkCharSetFromRange((char)elems[1], (char)elems[2]);
                    if (moves.ContainsKey(key))
                        moves[key] = solver.MkOr(moves[key], pred);
                    else
                        moves[key] = pred;
                }
            }
            foreach (var kv in moves)
                allmoves.Add(Move<BDD>.Create(kv.Key.First, kv.Key.Second, kv.Value));

            var aut = Automaton<BDD>.Create(solver, initialState, finals, allmoves);
            return aut;
        }

        /// <summary>
        /// Computes the ratio of two dfas
        /// </summary>        
        /// <returns>size of dfa2/ size of dfa1</returns>
        internal static double GetDFARatio(Automaton<BDD> dfa1, Automaton<BDD> dfa2, HashSet<char> al, CharSetSolver solver, bool isSolDense)
        {
            var n = dfa1.StateCount;

            double multiplier = 3;
            int k = Math.Min(13, (int)(n * multiplier));

            int finalDivider = k;

            double[] paths1 = GetPathsUpToN(dfa1, al, solver, k);
            double[] paths2 = GetPathsUpToN(dfa2, al, solver, k);

            double sum = 0;
            for (int i = 0; i <= k; i++)
            {
                //TODO check grading still works
                double divider = Math.Min(paths1[i], Math.Pow(al.Count, i) - paths1[i]);
                if (divider != 0)
                    sum += (paths2[i] / divider);
                else
                {
                    sum += paths2[i];
                    if (paths2[i] == 0)
                        finalDivider--;
                }
            }

            return sum / (finalDivider + 1);
        }

        public void DileepTest1()
        {
            PDLEnumerator pdlEnumerator = new PDLEnumerator();
            var solver = new CharSetSolver(BitWidth.BV64);
            List<char> alph = new List<char> { 'a', 'b' };
            HashSet<char> al = new HashSet<char>(alph);

            PDLPred phi = new PDLModSetEq(new PDLIndicesOf("a"), 2, 1);
            phi = new PDLAnd(new PDLStartsWith("a"), phi);
            var dfa1 = phi.GetDFA(al, solver);

            var a = solver.MkCharConstraint(false, 'a');
            var b = solver.MkCharConstraint(false, 'b');
            var moves = new List<Move<BDD>>();

            moves.Add(new Move<BDD>(0, 0, a));
            moves.Add(new Move<BDD>(0, 5, a));
            moves.Add(new Move<BDD>(5, 0, a));
            moves.Add(new Move<BDD>(5, 5, b));

            var dfa2 = Automaton<BDD>.Create(0, new int[] { 5 }, moves);
            var feedbackGrade = DFAGrading.GetGrade(dfa1, dfa2, al, solver, timeout, 10, FeedbackLevel.Solution, true, false, false);
            var feedString = "<ul>";
            foreach (var feed in feedbackGrade.Second)
                feedString += string.Format("<li>{0}</li>", feed);
            feedString += "</ul>";

            Console.Write( string.Format("<div>Grade: {0} <br /> Feedback: {1}</div>", feedbackGrade.First, feedString));
        }

 public RegexToSMTConverter(BitWidth encoding, string charSortAlias)
 {
     css = new CharSetSolver(encoding);
     automConverter = css.RegexConverter;
     maxChar = (encoding == BitWidth.BV16 ? '\uFFFF' :
         (encoding == BitWidth.BV8 ? '\u00FF' : '\u007F'));
     CHAR = charSortAlias;
 }

 public HelperPredicates(CharSetSolver solver, bool OptimzeForAsciiInput)
 {
     this.solver = solver;
     helper_predicates = new List<string>();
     predicate_cache = new Dictionary<BDD, string>();
     ascii = solver.MkRangeConstraint('\0', '\x7F');
     this.OptimzeForASCIIinput = OptimzeForAsciiInput;
 }

 public MoveSequence(string regex)
 {
     solver = new CharSetSolver(BitWidth.BV7);
     moveAutomaton = solver.Convert("^(" + regex + ")$").Determinize(solver).Minimize(solver);
     currentState = 0;
     //solver.ShowGraph(moveAutomaton, "D");
     //ComputeDeadStates();
 }

 public CSharpGenerator(Automaton<BDD> automaton, CharSetSolver solver, string classname, string namespacename, bool OptimzeForAsciiInput = true)
 {
     this.solver = solver;
     this.automaton = automaton;
     this.namespacename = namespacename;
     this.classname = classname;
     ASCII = solver.MkCharSetFromRange('\0', '\x7F');
     helper_predicates = new HelperPredicates(solver, OptimzeForAsciiInput);
 }

        public static Pair<HashSet<char>, Automaton<BDD>> parseNFAFromXML(XElement Automaton1, CharSetSolver solver)
        {
            HashSet<char> al = new HashSet<char>();

            var moves = new List<Move<BDD>>();
            var finalStates = new List<int>();
            int start = 0;

            XElement Automaton = XElement.Parse(RemoveAllNamespaces(Automaton1.ToString()));
            XElement xmlAlphabet = Automaton.Element("alphabet");
            foreach (XElement child in xmlAlphabet.Elements())
            {
                char element = Convert.ToChar(child.Value);
                if (element != 'ε' && element != '?')
                    al.Add(element);
            }


            XElement trans = Automaton.Element("transitionSet");

            foreach (XElement child in trans.Elements())
            {
                if (child.Name == "transition")
                {
                    char element = Convert.ToChar(child.Element("read").Value);
                    if (element != 'ε' && element != '?')
                        moves.Add(new Move<BDD>(Convert.ToInt32(child.Element("from").Value), Convert.ToInt32(child.Element("to").Value),
                            solver.MkCharConstraint(false, element)));
                    else
                        moves.Add(Move<BDD>.Epsilon(Convert.ToInt32(child.Element("from").Value), Convert.ToInt32(child.Element("to").Value)));

                    
                }
            }

            XElement acc = Automaton.Element("acceptingSet");
            foreach (XElement child in acc.Elements())
            {
                if (child.Name == "state")
                {
                    finalStates.Add((int)child.Attribute("sid"));
                }
            }

            XElement states = Automaton.Element("initState");
            foreach (XElement child in states.Elements())
            {
                if (child.Name == "state")
                {
                    start = (int)child.Attribute("sid");
                }
            }

            return new Pair<HashSet<char>, Automaton<BDD>>(al, Automaton<BDD>.Create(start, finalStates, moves));

        }

 /// <summary>
 /// Returns the minimum PDL edit distance ratio between all the PDL A1 and A2 inferred for dfa1 and dfa2
 /// in less than timeout. For every  min_ij(d(A1i,A2j)/|A1i)
 /// </summary>
 /// <param name="dfa1"></param>
 /// <param name="dfa2"></param>
 /// <param name="al"></param>
 /// <param name="solver"></param>
 /// <param name="timeout"></param>
 /// <returns></returns>
 public static double GetMinimalFormulaEditDistanceRatio(Automaton<BDD> dfa1, Automaton<BDD> dfa2, HashSet<char> al, CharSetSolver solver, long timeout, PDLEnumerator pdlEnumerator)
 {
     var v = GetMinimalFormulaEditDistanceTransformation(dfa1, dfa2, al, solver, timeout, pdlEnumerator);
     if(v!=null){
         var transformation = v.First;
         var scaling = 1.0;
         return transformation.totalCost / (transformation.minSizeForTreeA * scaling);
     }
     return 10;
 }

        public XElement ComputeFeedbackXML(XElement dfaCorrectDesc, XElement dfaAttemptDesc, XElement maxGrade, XElement feedbackLevel, XElement enabledFeedbacks)
        {
            #region Check if item is in cache
            StringBuilder key = new StringBuilder();
            key.Append("feed");
            key.Append(dfaCorrectDesc.ToString());
            key.Append(dfaAttemptDesc.ToString());
            key.Append(feedbackLevel.ToString());
            key.Append(enabledFeedbacks.ToString());
            string keystr = key.ToString();

            var cachedValue = HttpContext.Current.Cache.Get(key.ToString());
            if (cachedValue != null)
            {
                HttpContext.Current.Cache.Remove(keystr);
                HttpContext.Current.Cache.Add(keystr, cachedValue, null, System.Web.Caching.Cache.NoAbsoluteExpiration, TimeSpan.FromDays(30), System.Web.Caching.CacheItemPriority.Normal, null);
                return (XElement)cachedValue;
            } 
            #endregion
            
            CharSetSolver solver = new CharSetSolver(BitWidth.BV64);

            //Read input 
            var dfaCorrectPair = DFAUtilities.parseDFAFromXML(dfaCorrectDesc, solver);
            var dfaAttemptPair = DFAUtilities.parseDFAFromXML(dfaAttemptDesc, solver);

            var level = (FeedbackLevel) Enum.Parse(typeof(FeedbackLevel), feedbackLevel.Value, true);
            var enabList = (enabledFeedbacks.Value).Split(',').ToList<String>();
            //bool dfaedit = enabList.Contains("dfaedit"), moseledit = enabList.Contains("moseledit"), density = enabList.Contains("density");
            bool dfaedit =true, moseledit = true, density = true;

            var maxG = int.Parse(maxGrade.Value);

            //Compute feedback
            var feedbackGrade = DFAGrading.GetGrade(dfaCorrectPair.Second, dfaAttemptPair.Second, dfaCorrectPair.First, solver, 1500, maxG, level, dfaedit, density, moseledit);

            //Pretty print feedback
            var feedString = "<ul>";
            foreach (var feed in feedbackGrade.Second)
            {
                feedString += string.Format("<li>{0}</li>", feed);
                break;
            }
            feedString += "</ul>";

            //var output = string.Format("<result><grade>{0}</grade><feedString>{1}</feedString></result>", feedbackGrade.First, feedString);
            var outXML = new XElement("result",  
                                    new XElement("grade", feedbackGrade.First),
                                    new XElement("feedString", XElement.Parse(feedString)));
            //XElement outXML = XElement.Parse(output);
            //Add this element to chace and return it
            HttpContext.Current.Cache.Add(key.ToString(), outXML, null, System.Web.Caching.Cache.NoAbsoluteExpiration, TimeSpan.FromDays(30), System.Web.Caching.CacheItemPriority.Normal, null);

            return outXML;
        }