ContentValidator.cs source code in C# .NET

Source code for the .NET framework in C#

                        

Code:

/ Net / Net / 3.5.50727.3053 / DEVDIV / depot / DevDiv / releases / whidbey / netfxsp / ndp / fx / src / Xml / System / Xml / schema / ContentValidator.cs / 1 / ContentValidator.cs

                            //------------------------------------------------------------------------------ 
// 
//     Copyright (c) Microsoft Corporation.  All rights reserved.
// 
// [....] 
//-----------------------------------------------------------------------------
using System; 
using System.Collections; 
using System.Collections.Generic;
using System.Globalization; 
using System.Text;
using System.Diagnostics;

namespace System.Xml.Schema { 

    #region ExceptionSymbolsPositions 
 
    /// 
    /// UPA violations will throw this exception 
    /// 
    class UpaException : Exception {
        object particle1;
        object particle2; 
        public UpaException(object particle1, object particle2) {
            this.particle1 = particle1; 
            this.particle2 = particle2; 
        }
        public object Particle1 { get { return particle1; } } 
        public object Particle2 { get { return particle2; } }
    }

    ///  
    /// SymbolsDictionary is a map between names that ContextValidator recognizes and symbols - int symbol[XmlQualifiedName name].
    /// There are two types of name - full names and wildcards (namespace is specified, local name is anythig). 
    /// Wildcard excludes all full names that would match by the namespace part. 
    /// SymbolsDictionry alwas recognizes all the symbols - the last one is a true wildcard -
    ///      both name and namespace can be anything that none of the other symbols matched. 
    /// 
    class SymbolsDictionary {
        int last = 0;
        Hashtable names; 
        Hashtable wildcards = null;
        ArrayList particles; 
        object particleLast = null; 
        bool isUpaEnforced = true;
 
        public SymbolsDictionary() {
            names = new Hashtable();
            particles = new ArrayList();
        } 

        public int Count { 
            // last one is a "*:*" any wildcard 
            get { return last + 1; }
        } 

        public int CountOfNames {
            get { return names.Count; }
        } 

        ///  
        /// True is particle can be deterministically attributed from the symbol and conversion to DFA is possible. 
        /// 
        public bool IsUpaEnforced { 
            get { return isUpaEnforced; }
            set { isUpaEnforced = value; }
        }
 
        /// 
        /// Add name  and return it's number 
        ///  
        public int AddName(XmlQualifiedName name, object particle) {
            object lookup = names[name]; 
            if (lookup != null) {
                int symbol = (int)lookup;
                if (particles[symbol] != particle) {
                    isUpaEnforced = false; 
                }
                return symbol; 
            } 
            else {
                names.Add(name, last); 
                particles.Add(particle);
                Debug.Assert(particles.Count == last + 1);
                return last ++;
            } 
        }
 
        public void AddNamespaceList(NamespaceList list, object particle, bool allowLocal) { 
            switch (list.Type) {
            case NamespaceList.ListType.Any: 
                particleLast = particle;
                break;
            case NamespaceList.ListType.Other:
                // Create a symbol for the excluded namespace, but don't set a particle for it. 
                AddWildcard(list.Excluded, null);
                if (!allowLocal) { 
                    AddWildcard(string.Empty, null); //##local is not allowed 
                }
                break; 
            case NamespaceList.ListType.Set:
                foreach(string wildcard in list.Enumerate) {
                    AddWildcard(wildcard, particle);
                } 
                break;
            } 
        } 

        private void AddWildcard(string wildcard, object particle) { 
            if (wildcards == null) {
                wildcards = new Hashtable();
            }
            object lookup = wildcards[wildcard]; 
            if (lookup == null) {
                wildcards.Add(wildcard, last); 
                particles.Add(particle); 
                Debug.Assert(particles.Count == last + 1);
                last ++; 
            }
            else if (particle != null) {
                particles[(int)lookup] = particle;
            } 
        }
 
        public ICollection GetNamespaceListSymbols(NamespaceList list) { 
            ArrayList match = new ArrayList();
            foreach(XmlQualifiedName name in names.Keys) { 
                if (name != XmlQualifiedName.Empty && list.Allows(name)) {
                    match.Add(names[name]);
                }
            } 
            if (wildcards != null) {
                foreach(string wildcard in wildcards.Keys) { 
                    if (list.Allows(wildcard)) { 
                        match.Add(wildcards[wildcard]);
                    } 
                }
            }
            if (list.Type == NamespaceList.ListType.Any || list.Type == NamespaceList.ListType.Other) {
                match.Add(last); // add wildcard 
            }
            return match; 
        } 

        ///  
        /// Find the symbol for the given name. If neither names nor wilcards match it last (*.*) symbol will be returned
        /// 
        public int this[XmlQualifiedName name] {
            get { 
                object lookup = names[name];
                if (lookup != null) { 
                    return (int)lookup; 
                }
                if (wildcards != null) { 
                    lookup = wildcards[name.Namespace];
                    if (lookup != null) {
                        return (int)lookup;
                    } 
                }
                return last; // true wildcard 
            } 
        }
 
        /// 
        /// Check if a name exists in the symbol dictionary
        /// 
        public bool Exists(XmlQualifiedName name) { 

            object lookup = names[name]; 
            if (lookup != null) { 
                return true;
            } 
            return false;
        }

        ///  
        /// Return content processing mode for the symbol
        ///  
        public object GetParticle(int symbol) { 
            return symbol == last ? particleLast : particles[symbol];
        } 

        /// 
        /// Output symbol's name
        ///  
        public string NameOf(int symbol) {
            foreach (DictionaryEntry de in names) { 
                if ((int)de.Value == symbol) { 
                    return ((XmlQualifiedName)de.Key).ToString();
                } 
            }
            if (wildcards != null) {
                foreach (DictionaryEntry de in wildcards) {
                    if ((int)de.Value == symbol) { 
                        return (string)de.Key + ":*";
                    } 
                } 
            }
            return "##other:*"; 
        }
    }

    struct Position { 
        public int symbol;
        public object particle; 
        public Position(int symbol, object particle) { 
            this.symbol = symbol;
            this.particle = particle; 
        }
    }

    class Positions { 
        ArrayList positions = new ArrayList();
 
        public int Add(int symbol, object particle) { 
            return positions.Add(new Position(symbol, particle));
        } 

        public Position this[int pos] {
            get { return (Position)positions[pos]; }
        } 

        public int Count { 
            get { return positions.Count; } 
        }
    } 
    #endregion

    #region SystaxTree
    ///  
    /// Base class for the systax tree nodes
    ///  
    abstract class SyntaxTreeNode { 
        /// 
        /// Expand NamesapceListNode and RangeNode nodes. All other nodes 
        /// 
        public abstract void ExpandTree(InteriorNode parent, SymbolsDictionary symbols, Positions positions);

        ///  
        /// Clone the syntaxTree. We need to pass symbolsByPosition because leaf nodes have to add themselves to it.
        ///  
        public abstract SyntaxTreeNode Clone(Positions positions); 

        ///  
        /// From a regular expression to a DFA
        /// Compilers by Aho, Sethi, Ullman.
        /// ISBN 0-201-10088-6, p135
        /// Construct firstpos, lastpos and calculate followpos 
        /// 
        public abstract void ConstructPos(BitSet firstpos, BitSet lastpos, BitSet[] followpos); 
 
        /// 
        /// Returns nullable property that is being used by ConstructPos 
        /// 
        public abstract bool IsNullable { get; }

        ///  
        /// Returns true if node is a range node
        ///  
        public virtual bool IsRangeNode { 
            get {
                return false; 
            }
        }

        ///  
        /// Print syntax tree
        ///  
#if DEBUG 
        public abstract void Dump(StringBuilder bb, SymbolsDictionary symbols, Positions positions);
#endif 
    }

    /// 
    /// Terminal of the syntax tree 
    /// 
    class LeafNode : SyntaxTreeNode { 
        int pos; 

        public LeafNode(int pos) { 
            this.pos = pos;
        }

        public int Pos { 
            get { return pos;}
            set { pos = value; } 
        } 

        public override void ExpandTree(InteriorNode parent, SymbolsDictionary symbols, Positions positions) { 
            // do nothing
        }

        public override SyntaxTreeNode Clone(Positions positions) { 
            return new LeafNode(positions.Add(positions[pos].symbol, positions[pos].particle));
        } 
 
        public override void ConstructPos(BitSet firstpos, BitSet lastpos, BitSet[] followpos) {
            firstpos.Set(pos); 
            lastpos.Set(pos);
        }

        public override bool IsNullable { 
            get { return false; }
        } 
 
#if DEBUG
        public override void Dump(StringBuilder bb, SymbolsDictionary symbols, Positions positions) { 
            bb.Append("\"" + symbols.NameOf(positions[pos].symbol) + "\"");
        }
#endif
    } 

    ///  
    /// Temporary node to represent NamespaceList. Will be expended as a choice of symbols 
    /// 
    class NamespaceListNode : SyntaxTreeNode { 
        protected NamespaceList namespaceList;
        protected object particle;

        public NamespaceListNode(NamespaceList namespaceList, object particle) { 
            this.namespaceList = namespaceList;
            this.particle = particle; 
        } 

        public override SyntaxTreeNode Clone(Positions positions) { 
            // NamespaceListNode nodes have to be removed prior to that
            throw new InvalidOperationException();
        }
 
        public virtual ICollection GetResolvedSymbols(SymbolsDictionary symbols)  {
            return symbols.GetNamespaceListSymbols(namespaceList); 
        } 

        public override void ExpandTree(InteriorNode parent, SymbolsDictionary symbols, Positions positions) { 
            SyntaxTreeNode replacementNode = null;
            foreach(int symbol in GetResolvedSymbols(symbols)) {
                if (symbols.GetParticle(symbol) != particle) {
                    symbols.IsUpaEnforced = false; 
                }
                LeafNode node = new LeafNode(positions.Add(symbol, particle)); 
                if (replacementNode == null) { 
                    replacementNode = node;
                } 
                else {
                    InteriorNode choice = new ChoiceNode();
                    choice.LeftChild = replacementNode;
                    choice.RightChild = node; 
                    replacementNode = choice;
                } 
            } 
            if (parent.LeftChild == this) {
                parent.LeftChild = replacementNode; 
            }
            else {
                parent.RightChild = replacementNode;
            } 
        }
 
        public override void ConstructPos(BitSet firstpos, BitSet lastpos, BitSet[] followpos) { 
            // NamespaceListNode nodes have to be removed prior to that
            throw new InvalidOperationException(); 
        }

        public override bool IsNullable {
            // NamespaceListNode nodes have to be removed prior to that 
            get { throw new InvalidOperationException(); }
        } 
 
#if DEBUG
        public override void Dump(StringBuilder bb, SymbolsDictionary symbols, Positions positions) { 
            bb.Append("[" + namespaceList.ToString() + "]");
        }
#endif
    } 

    ///  
    /// Base class for all internal node. Note that only sequence and choice have right child 
    /// 
    abstract class InteriorNode : SyntaxTreeNode { 
        SyntaxTreeNode leftChild;
        SyntaxTreeNode rightChild;

        public SyntaxTreeNode LeftChild { 
            get { return leftChild;}
            set { leftChild = value;} 
        } 

        public SyntaxTreeNode RightChild { 
            get { return rightChild;}
            set { rightChild = value;}
        }
 
        public override SyntaxTreeNode Clone(Positions positions) {
            InteriorNode other = (InteriorNode)this.MemberwiseClone(); 
            other.LeftChild = leftChild.Clone(positions); 
            if (rightChild != null) {
                other.RightChild = rightChild.Clone(positions); 
            }
            return other;
        }
 
        public override void ExpandTree(InteriorNode parent, SymbolsDictionary symbols, Positions positions) {
            leftChild.ExpandTree(this, symbols, positions); 
            if (rightChild != null) { 
                rightChild.ExpandTree(this, symbols, positions);
            } 
        }
    }

    sealed class SequenceNode : InteriorNode { 
        public override void ConstructPos(BitSet firstpos, BitSet lastpos, BitSet[] followpos) {
            BitSet lastposLeft = new BitSet(lastpos.Count); 
            LeftChild.ConstructPos(firstpos, lastposLeft, followpos); 

            BitSet firstposRight = new BitSet(firstpos.Count); 
            RightChild.ConstructPos(firstposRight, lastpos, followpos);

            if (LeftChild.IsNullable && !RightChild.IsRangeNode) {
                firstpos.Or(firstposRight); 
            }
            if (RightChild.IsNullable) { 
                lastpos.Or(lastposLeft); 
            }
            for (int pos = lastposLeft.NextSet(-1); pos != -1; pos = lastposLeft.NextSet(pos)) { 
                followpos[pos].Or(firstposRight);
            }
            if (RightChild.IsRangeNode) { //firstpos is leftchild.firstpos as the or with firstposRight has not been done as it is a rangenode
                ((LeafRangeNode)RightChild).NextIteration = firstpos.Clone(); 
            }
        } 
 
        public override bool IsNullable {
            get { return (LeftChild.IsNullable && (RightChild.IsNullable || RightChild.IsRangeNode)) || (RightChild.IsRangeNode && ((LeafRangeNode)RightChild).Min == 0 ); } 
        }

#if DEBUG
        internal static void WritePos(BitSet firstpos, BitSet lastpos, BitSet[] followpos) { 
            Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, "FirstPos:  ");
            WriteBitSet(firstpos); 
 
            Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, "LastPos:  ");
            WriteBitSet(lastpos); 

            Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, "Followpos:  ");
            for(int i =0; i < followpos.Length; i++) {
                WriteBitSet(followpos[i]); 
            }
        } 
        internal static void WriteBitSet(BitSet curpos) { 
            int[] list = new int[curpos.Count];
            for (int pos = curpos.NextSet(-1); pos != -1; pos = curpos.NextSet(pos)) { 
                list[pos] = 1;
            }
            for(int i = 0; i < list.Length; i++) {
                Debug.WriteIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, list[i] + " "); 
            }
            Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, ""); 
        } 

 
        public override void Dump(StringBuilder bb, SymbolsDictionary symbols, Positions positions) {
            bb.Append("(");
            LeftChild.Dump(bb, symbols, positions);
            bb.Append(", "); 
            RightChild.Dump(bb, symbols, positions);
            bb.Append(")"); 
        } 
#endif
    } 

    sealed class ChoiceNode : InteriorNode {
        public override void ConstructPos(BitSet firstpos, BitSet lastpos, BitSet[] followpos) {
            LeftChild.ConstructPos(firstpos, lastpos, followpos); 

            BitSet firstposRight = new BitSet(firstpos.Count); 
            BitSet lastposRight = new BitSet(lastpos.Count); 
            RightChild.ConstructPos(firstposRight, lastposRight, followpos);
 
            firstpos.Or(firstposRight);
            lastpos.Or(lastposRight);
        }
 
        public override bool IsNullable {
            get { return LeftChild.IsNullable || RightChild.IsNullable; } 
        } 

#if DEBUG 
        public override void Dump(StringBuilder bb, SymbolsDictionary symbols, Positions positions) {
            bb.Append("(");
            LeftChild.Dump(bb, symbols, positions);
            bb.Append(" | "); 
            RightChild.Dump(bb, symbols, positions);
            bb.Append(")"); 
        } 
#endif
    } 

    sealed class PlusNode : InteriorNode {
        public override void ConstructPos(BitSet firstpos, BitSet lastpos, BitSet[] followpos) {
            LeftChild.ConstructPos(firstpos, lastpos, followpos); 
            for (int pos = lastpos.NextSet(-1); pos != -1; pos = lastpos.NextSet(pos)) {
                followpos[pos].Or(firstpos); 
            } 
        }
 
        public override bool IsNullable {
            get { return LeftChild.IsNullable; }
        }
 
#if DEBUG
        public override void Dump(StringBuilder bb, SymbolsDictionary symbols, Positions positions) { 
            LeftChild.Dump(bb, symbols, positions); 
            bb.Append("+");
        } 
#endif
    }

    sealed class QmarkNode : InteriorNode { 
        public override void ConstructPos(BitSet firstpos, BitSet lastpos, BitSet[] followpos) {
            LeftChild.ConstructPos(firstpos, lastpos, followpos); 
        } 

        public override bool IsNullable { 
            get { return true; }
        }

#if DEBUG 
        public override void Dump(StringBuilder bb, SymbolsDictionary symbols, Positions positions) {
            LeftChild.Dump(bb, symbols, positions); 
            bb.Append("?"); 
        }
#endif 
    }

    sealed class StarNode : InteriorNode {
        public override void ConstructPos(BitSet firstpos, BitSet lastpos, BitSet[] followpos) { 
            LeftChild.ConstructPos(firstpos, lastpos, followpos);
            for (int pos = lastpos.NextSet(-1); pos != -1; pos = lastpos.NextSet(pos)) { 
                followpos[pos].Or(firstpos); 
            }
        } 

        public override bool IsNullable {
            get { return true; }
        } 

#if DEBUG 
        public override void Dump(StringBuilder bb, SymbolsDictionary symbols, Positions positions) { 
            LeftChild.Dump(bb, symbols, positions);
            bb.Append("*"); 
        }
#endif
    }
 
#if EXPANDRANGE
    ///  
    /// Temporary node to occurance range. Will be expended to a sequence of terminals 
    /// 
    sealed class RangeNode : InteriorNode { 
        int min;
        int max;

        public RangeNode(int min, int max) { 
            this.min = min;
            this.max = max; 
        } 

        public int Max { 
            get { return max;}
        }

        public int Min { 
            get { return min;}
        } 
 
        public override SyntaxTreeNode Clone(Positions positions) {
            // range nodes have to be removed prior to that 
            throw new InvalidOperationException();
        }

        ///  
        /// Expand tree will replace a{min, max} using following algorithm. Bare in mind that this sequence will have at least two leaves
        /// if min == 0 (max cannot be unbounded) 
        ///         a?, ...  a? 
        ///         \__     __/
        ///             max 
        /// else
        ///     if max == unbounded
        ///         a,  ...   a, a*
        ///         \__     __/ 
        ///             min
        ///     else 
        ///         a,  ...   a, a?,   ...     a? 
        ///         \__     __/  \__          __/
        ///             min          max - min 
        /// 
        public override void ExpandTree(InteriorNode parent, SymbolsDictionary symbols, Positions positions) {
            LeftChild.ExpandTree(this, symbols, positions);
            SyntaxTreeNode replacementNode = null; 
            if (min == 0) {
                Debug.Assert(max != int.MaxValue); 
                replacementNode = NewQmark(LeftChild); 
                for (int i = 0; i < max - 1; i ++) {
                    replacementNode = NewSequence(replacementNode, NewQmark(LeftChild.Clone(positions))); 
                }
            }
            else {
                replacementNode = LeftChild; 
                for (int i = 0; i < min - 1; i ++) {
                    replacementNode = NewSequence(replacementNode, LeftChild.Clone(positions)); 
                } 
                if (max == int.MaxValue) {
                    replacementNode = NewSequence(replacementNode, NewStar(LeftChild.Clone(positions))); 
                }
                else {
                    for (int i = 0; i < max - min; i ++) {
                        replacementNode = NewSequence(replacementNode, NewQmark(LeftChild.Clone(positions))); 
                    }
                } 
            } 
            if (parent.LeftChild == this) {
                parent.LeftChild = replacementNode; 
            }
            else {
                parent.RightChild = replacementNode;
            } 
        }
 
        private SyntaxTreeNode NewSequence(SyntaxTreeNode leftChild, SyntaxTreeNode rightChild) { 
            InteriorNode sequence = new SequenceNode();
            sequence.LeftChild = leftChild; 
            sequence.RightChild = rightChild;
            return sequence;
        }
 
        private SyntaxTreeNode NewStar(SyntaxTreeNode leftChild) {
            InteriorNode star = new StarNode(); 
            star.LeftChild = leftChild; 
            return star;
        } 

        private SyntaxTreeNode NewQmark(SyntaxTreeNode leftChild) {
            InteriorNode qmark = new QmarkNode();
            qmark.LeftChild = leftChild; 
            return qmark;
        } 
 
        public override void ConstructPos(BitSet firstpos, BitSet lastpos, BitSet[] followpos) {
            throw new InvalidOperationException(); 
        }

        public override bool IsNullable {
            get { throw new InvalidOperationException(); } 
        }
 
        public override void Dump(StringBuilder bb, SymbolsDictionary symbols, Positions positions) { 
            LeftChild.Dump(bb, symbols, positions);
            bb.Append("{" + Convert.ToString(min, NumberFormatInfo.InvariantInfo) + ", " + Convert.ToString(max, NumberFormatInfo.InvariantInfo) + "}"); 
        }

    }
#endif 

 
    ///  
    /// Using range node as one of the terminals
    ///  
    sealed class LeafRangeNode : LeafNode {
        decimal min;
        decimal max;
        BitSet nextIteration; 

        public LeafRangeNode(decimal min, decimal max) : this(-1, min, max) {} 
 
        public LeafRangeNode(int pos, decimal min, decimal max) : base(pos) {
            this.min = min; 
            this.max = max;
        }

        public decimal Max { 
            get { return max;}
        } 
 
        public decimal Min {
            get { return min;} 
        }

        public BitSet NextIteration {
            get { 
                return nextIteration;
            } 
            set { 
                nextIteration = value;
            } 
        }

        public override SyntaxTreeNode Clone(Positions positions) {
            return new LeafRangeNode(this.Pos, this.min, this.max); 
        }
 
        public override bool IsRangeNode { 
            get {
                return true; 
            }
        }
    }
 
    #endregion
 
    #region ContentValidator 
    /// 
    /// Basic ContentValidator 
    /// 
    class ContentValidator {
        XmlSchemaContentType contentType;
        bool isOpen;  //For XDR Content Models or ANY 
        bool isEmptiable;
 
        public static readonly ContentValidator Empty = new ContentValidator(XmlSchemaContentType.Empty); 
        public static readonly ContentValidator TextOnly = new ContentValidator(XmlSchemaContentType.TextOnly, false, false);
        public static readonly ContentValidator Mixed = new ContentValidator(XmlSchemaContentType.Mixed); 
        public static readonly ContentValidator Any = new ContentValidator(XmlSchemaContentType.Mixed, true, true);

        public ContentValidator(XmlSchemaContentType contentType) {
            this.contentType = contentType; 
            this.isEmptiable = true;
        } 
 
        protected ContentValidator(XmlSchemaContentType contentType, bool isOpen, bool isEmptiable) {
            this.contentType = contentType; 
            this.isOpen = isOpen;
            this.isEmptiable = isEmptiable;
        }
 
        public XmlSchemaContentType ContentType {
            get { return contentType; } 
        } 

        public bool PreserveWhitespace { 
            get { return contentType == XmlSchemaContentType.TextOnly || contentType == XmlSchemaContentType.Mixed; }
        }

        public virtual bool IsEmptiable { 
            get { return isEmptiable; }
        } 
 
        public bool IsOpen {
            get { 
                if (contentType == XmlSchemaContentType.TextOnly || contentType == XmlSchemaContentType.Empty)
                    return false;
                else
                    return isOpen; 
            }
            set { isOpen = value; } 
        } 

        public virtual void InitValidation(ValidationState context) { 
            // do nothin'
        }

        public virtual object ValidateElement(XmlQualifiedName name, ValidationState context, out int errorCode) { 
            if (contentType == XmlSchemaContentType.TextOnly || contentType == XmlSchemaContentType.Empty) { //Cannot have elements in TextOnly or Empty content
                context.NeedValidateChildren = false; 
            } 
            errorCode = -1;
            return null; 
        }

        public virtual bool CompleteValidation(ValidationState context) {
            return true; 
        }
 
        public virtual ArrayList ExpectedElements(ValidationState context, bool isRequiredOnly) { 
            return null;
        } 

        public virtual ArrayList ExpectedParticles(ValidationState context, bool isRequiredOnly) {
            return null;
        } 
    }
 
    sealed class ParticleContentValidator : ContentValidator { 
        SymbolsDictionary symbols;
        Positions positions; 
        Stack stack;                        // parsing context
        SyntaxTreeNode contentNode;         // content model points to syntax tree
        bool isPartial;                     // whether the closure applies to partial or the whole node that is on top of the stack
        int minMaxNodesCount; 
        bool enableUpaCheck;
 
        public ParticleContentValidator(XmlSchemaContentType contentType) : this(contentType, true) { 
        }
 
        public ParticleContentValidator(XmlSchemaContentType contentType, bool enableUpaCheck) : base(contentType) {
            this.enableUpaCheck = enableUpaCheck;
        }
 
        public override void InitValidation(ValidationState context) {
            // ParticleContentValidator cannot be used during validation 
            throw new InvalidOperationException(); 
        }
 
        public override object ValidateElement(XmlQualifiedName name, ValidationState context, out int errorCode) {
            // ParticleContentValidator cannot be used during validation
            throw new InvalidOperationException();
        } 

        public override bool CompleteValidation(ValidationState context) { 
            // ParticleContentValidator cannot be used during validation 
            throw new InvalidOperationException();
        } 

        public void Start() {
            symbols = new SymbolsDictionary();
            positions = new Positions(); 
            stack = new Stack();
        } 
 
        public void OpenGroup() {
            stack.Push(null); 
        }

        public void CloseGroup() {
            SyntaxTreeNode node = (SyntaxTreeNode)stack.Pop(); 
            if (node == null) {
                return; 
            } 
            if (stack.Count == 0) {
                contentNode = node; 
                isPartial = false;
            }
            else {
                // some collapsing to do... 
                InteriorNode inNode = (InteriorNode)stack.Pop();
                if (inNode != null) { 
                    inNode.RightChild = node; 
                    node = inNode;
                    isPartial = true; 
                }
                else {
                    isPartial = false;
                } 
                stack.Push(node);
            } 
        } 

        public bool Exists(XmlQualifiedName name) { 
            if (symbols.Exists(name)) {
                return true;
            }
            return false; 
        }
 
        public void AddName(XmlQualifiedName name, object particle) { 
            AddLeafNode(new LeafNode(positions.Add(symbols.AddName(name, particle), particle)));
        } 

        public void AddNamespaceList(NamespaceList namespaceList, object particle) {
            symbols.AddNamespaceList(namespaceList, particle, false);
            AddLeafNode(new NamespaceListNode(namespaceList, particle)); 
        }
 
        private void AddLeafNode(SyntaxTreeNode node) { 
            if (stack.Count > 0) {
                InteriorNode inNode = (InteriorNode)stack.Pop(); 
                if (inNode != null) {
                    inNode.RightChild = node;
                    node = inNode;
                } 
            }
            stack.Push( node ); 
            isPartial = true; 
        }
 
        public void AddChoice() {
            SyntaxTreeNode node = (SyntaxTreeNode)stack.Pop();
            InteriorNode choice = new ChoiceNode();
            choice.LeftChild = node; 
            stack.Push(choice);
        } 
 
        public void AddSequence() {
            SyntaxTreeNode node = (SyntaxTreeNode)stack.Pop(); 
            InteriorNode sequence = new SequenceNode();
            sequence.LeftChild = node;
            stack.Push(sequence);
        } 

        public void AddStar() { 
            Closure(new StarNode()); 
        }
 
        public void AddPlus() {
            Closure(new PlusNode());
        }
 
        public void AddQMark() {
            Closure(new QmarkNode()); 
        } 

        public void AddLeafRange(decimal min, decimal max) { 
            LeafRangeNode rNode = new LeafRangeNode(min, max);
            int pos = positions.Add(-2, rNode);
            rNode.Pos = pos;
 
            InteriorNode sequence = new SequenceNode();
            sequence.RightChild = rNode; 
            Closure(sequence); 
            minMaxNodesCount++;
        } 

#if EXPANDRANGE
        public void AddRange(int min, int max) {
            Closure(new RangeNode(min, max)); 
        }
#endif 
        private void Closure(InteriorNode node) { 
            if (stack.Count > 0) {
                SyntaxTreeNode topNode = (SyntaxTreeNode)stack.Pop(); 
                InteriorNode inNode = topNode as InteriorNode;
                if (isPartial && inNode != null) {
                    // need to reach in and wrap right hand side of element.
                    // and n remains the same. 
                    node.LeftChild = inNode.RightChild;
                    inNode.RightChild = node; 
                } 
                else {
                    // wrap terminal or any node 
                    node.LeftChild = topNode;
                    topNode = node;
                }
                stack.Push(topNode); 
            }
            else if (contentNode != null) { //If there is content to wrap 
                // wrap whole content 
                node.LeftChild = contentNode;
                contentNode = node; 
            }
        }

        public ContentValidator Finish() { 
            return Finish(true);
        } 
 
        public ContentValidator Finish(bool useDFA) {
            Debug.Assert(ContentType == XmlSchemaContentType.ElementOnly || ContentType == XmlSchemaContentType.Mixed); 
            if (contentNode == null) {
                if (ContentType == XmlSchemaContentType.Mixed) {
                    string ctype = IsOpen ? "Any" : "TextOnly";
                    Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled,  "\t\t\tContentType:  " + ctype); 
                    return IsOpen ? ContentValidator.Any : ContentValidator.TextOnly;
                } 
                else { 
                    Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled,  "\t\t\tContent:   EMPTY");
                    Debug.Assert(!IsOpen); 
                    return ContentValidator.Empty;
                }
            }
 
            #if DEBUG
            StringBuilder bb = new StringBuilder(); 
            contentNode.Dump(bb, symbols, positions); 
            Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled,  "\t\t\tContent :   " + bb.ToString());
            #endif 

            // Add end marker
            InteriorNode contentRoot = new SequenceNode();
            contentRoot.LeftChild = contentNode; 
            LeafNode endMarker = new LeafNode(positions.Add(symbols.AddName(XmlQualifiedName.Empty, null), null));
            contentRoot.RightChild = endMarker; 
 
            // Eliminate NamespaceListNode(s) and RangeNode(s)
            contentNode.ExpandTree(contentRoot, symbols, positions); 

            #if DEBUG
            bb = new StringBuilder();
            contentRoot.LeftChild.Dump(bb, symbols, positions); 
            Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled,  "\t\t\tExpended:   " + bb.ToString());
            #endif 
 
            // calculate followpos
            int symbolsCount = symbols.Count; 
            int positionsCount = positions.Count;
            BitSet firstpos = new BitSet(positionsCount);
            BitSet lastpos = new BitSet(positionsCount);
            BitSet[] followpos = new BitSet[positionsCount]; 
            for (int i = 0; i < positionsCount; i++) {
                followpos[i] = new BitSet(positionsCount); 
            } 
            contentRoot.ConstructPos(firstpos, lastpos, followpos);
#if DEBUG 
            Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, "firstpos, lastpos, followpos");
            SequenceNode.WritePos(firstpos, lastpos, followpos);
#endif
            if (minMaxNodesCount > 0) { //If the tree has any terminal range nodes 
                BitSet positionsWithRangeTerminals;
                BitSet[] minMaxFollowPos = CalculateTotalFollowposForRangeNodes(firstpos, followpos, out positionsWithRangeTerminals); 
 
                if (enableUpaCheck) {
                    CheckCMUPAWithLeafRangeNodes(GetApplicableMinMaxFollowPos(firstpos, positionsWithRangeTerminals, minMaxFollowPos)); 
                    for (int i = 0; i < positionsCount; i++) {
                        CheckCMUPAWithLeafRangeNodes(GetApplicableMinMaxFollowPos(followpos[i], positionsWithRangeTerminals, minMaxFollowPos));
                    }
                } 
                return new RangeContentValidator(firstpos, followpos, symbols, positions, endMarker.Pos, this.ContentType, contentRoot.LeftChild.IsNullable, positionsWithRangeTerminals, minMaxNodesCount);
            } 
            else { 
                int[][] transitionTable = null;
                // if each symbol has unique particle we are golden 
                if (!symbols.IsUpaEnforced) {
                    if (enableUpaCheck) {
                        // multiple positions that match the same symbol have different particles, but they never follow the same position
                        CheckUniqueParticleAttribution(firstpos, followpos); 
                    }
                } 
                else if (useDFA) { 
                    // Can return null if the number of states reaches higher than 8192 / positionsCount
                    transitionTable = BuildTransitionTable(firstpos, followpos, endMarker.Pos); 
                }
                #if DEBUG
                bb = new StringBuilder();
                Dump(bb, followpos, transitionTable); 
                Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, bb.ToString());
                #endif 
                if (transitionTable != null) { 
                    return new DfaContentValidator(transitionTable, symbols,this.ContentType, this.IsOpen, contentRoot.LeftChild.IsNullable);
                } else { 
                    return new NfaContentValidator(firstpos, followpos, symbols, positions, endMarker.Pos, this.ContentType, this.IsOpen, contentRoot.LeftChild.IsNullable);
                }
            }
        } 

        private BitSet[] CalculateTotalFollowposForRangeNodes(BitSet firstpos, BitSet[] followpos, out BitSet posWithRangeTerminals) { 
            int positionsCount = positions.Count; //terminals 
            posWithRangeTerminals = new BitSet(positionsCount);
 
            //Compute followpos for each range node
            //For any range node that is surrounded by an outer range node, its follow positions will include those of the outer range node
            BitSet[] minmaxFollowPos = new BitSet[minMaxNodesCount];
            int localMinMaxNodesCount = 0; 

            for (int i = positionsCount - 1;  i >= 0; i--) { 
                Position p = positions[i]; 
                if (p.symbol == -2) { //P is a LeafRangeNode
                    LeafRangeNode lrNode = p.particle as LeafRangeNode; 
                    Debug.Assert(lrNode != null);
                    BitSet tempFollowPos = new BitSet(positionsCount);
                    tempFollowPos.Clear();
                    tempFollowPos.Or(followpos[i]); //Add the followpos of the range node 
                    if (lrNode.Min != lrNode.Max) { //If they are the same, then followpos cannot include the firstpos
                        tempFollowPos.Or(lrNode.NextIteration); //Add the nextIteration of the range node (this is the firstpos of its parent's leftChild) 
                    } 

                    //For each position in the bitset, if it is a outer range node (pos > i), then add its followpos as well to the current node's followpos 
                    for (int pos = tempFollowPos.NextSet(-1); pos != -1; pos = tempFollowPos.NextSet(pos)) {
                        if (pos > i) {
                            Position p1 = positions[pos];
                            if (p1.symbol == -2) { 
                                LeafRangeNode lrNode1 = p1.particle as LeafRangeNode;
                                Debug.Assert(lrNode1 != null); 
                                tempFollowPos.Or(minmaxFollowPos[lrNode1.Pos]); 
                            }
                        } 
                    }
                    //set the followpos built to the index in the BitSet[]
                    minmaxFollowPos[localMinMaxNodesCount] = tempFollowPos;
                    lrNode.Pos = localMinMaxNodesCount++; 
                    posWithRangeTerminals.Set(i);
                } 
            } 
            return minmaxFollowPos;
        } 

        private void CheckCMUPAWithLeafRangeNodes(BitSet curpos) {
            object[] symbolMatches = new object[symbols.Count];
            for (int pos = curpos.NextSet(-1); pos != -1; pos = curpos.NextSet(pos)) { 
                Position currentPosition = positions[pos];
                int symbol = currentPosition.symbol; 
                if (symbol >= 0) { //its not a range position 
                    if (symbolMatches[symbol] != null) {
                        throw new UpaException(symbolMatches[symbol], currentPosition.particle); 
                    }
                    else {
                        symbolMatches[symbol] = currentPosition.particle;
                    } 
                }
            } 
        } 

        //For each position, this method calculates the additional follows of any range nodes that need to be added to its followpos 
        //((ab?)2-4)c, Followpos of a is b as well as that of node R(2-4) = c
        private BitSet GetApplicableMinMaxFollowPos(BitSet curpos, BitSet posWithRangeTerminals, BitSet[] minmaxFollowPos) {
            if (curpos.Intersects(posWithRangeTerminals)) {
                BitSet newSet = new BitSet(positions.Count); //Doing work again 
                newSet.Or(curpos);
                newSet.And(posWithRangeTerminals); 
                curpos = curpos.Clone(); 
                for (int pos = newSet.NextSet(-1); pos != -1; pos = newSet.NextSet(pos)) {
                    LeafRangeNode lrNode = positions[pos].particle as LeafRangeNode; 
                    curpos.Or(minmaxFollowPos[lrNode.Pos]);
                }
            }
            return curpos; 
        }
 
        private void CheckUniqueParticleAttribution(BitSet firstpos, BitSet[] followpos) { 
            CheckUniqueParticleAttribution(firstpos);
            for (int i = 0; i < positions.Count; i++) { 
                CheckUniqueParticleAttribution(followpos[i]);
            }
        }
 
        private void CheckUniqueParticleAttribution(BitSet curpos) {
            // particles will be attributed uniquely if the same symbol never poins to two different ones 
            object[] particles = new object[symbols.Count]; 
            for (int pos = curpos.NextSet(-1); pos != -1; pos = curpos.NextSet(pos)) {
                // if position can follow 
                int symbol = positions[pos].symbol;
                if (particles[symbol] == null) {
                    // set particle for the symbol
                    particles[symbol] = positions[pos].particle; 
                }
                else if (particles[symbol] != positions[pos].particle) { 
                    throw new UpaException(particles[symbol], positions[pos].particle); 
                }
                // two different position point to the same symbol and particle - that's OK 
            }
        }

        ///  
        /// Algorithm 3.5 Construction of a DFA from a regular expression
        ///  
        private int[][] BuildTransitionTable(BitSet firstpos, BitSet[] followpos, int endMarkerPos) { 
            const int TimeConstant = 8192; //(MaxStates * MaxPositions should be a constant)
            int positionsCount = positions.Count; 
            int MaxStatesCount = TimeConstant / positionsCount;
            int symbolsCount = symbols.Count;

            // transition table (Dtran in the book) 
            ArrayList transitionTable = new ArrayList();
 
            // state lookup table (Dstate in the book) 
            Hashtable stateTable = new Hashtable();
 
            // Add empty set that would signal an error
            stateTable.Add(new BitSet(positionsCount), -1);

            // lists unmarked states 
            Queue unmarked = new Queue();
 
            // initially, the only unmarked state in Dstates is firstpo(root) 
            int state = 0;
            unmarked.Enqueue(firstpos); 
            stateTable.Add(firstpos, 0);
            transitionTable.Add(new int[symbolsCount + 1]);

            // while there is an umnarked state T in Dstates do begin 
            while (unmarked.Count > 0) {
                BitSet statePosSet = (BitSet)unmarked.Dequeue(); // all positions that constitute DFA state 
                Debug.Assert(state == (int)stateTable[statePosSet]); // just make sure that statePosSet is for correct state 
                int[] transition = (int[])transitionTable[state];
                if (statePosSet[endMarkerPos]) { 
                    transition[symbolsCount] = 1;   // accepting
                }

                // for each input symbol a do begin 
                for (int symbol = 0; symbol < symbolsCount; symbol ++) {
                    // let U be the set of positions that are in followpos(p) 
                    //       for some position p in T 
                    //       such that the symbol at position p is a
                    BitSet newset = new BitSet(positionsCount); 
                    for (int pos = statePosSet.NextSet(-1); pos != -1; pos = statePosSet.NextSet(pos)) {
                        if (symbol == positions[pos].symbol) {
                            newset.Or(followpos[pos]);
                        } 
                    }
 
                    // if U is not empty and is not in Dstates then 
                    //      add U as an unmarked state to Dstates
                    object lookup = stateTable[newset]; 
                    if (lookup != null) {
                        transition[symbol] = (int)lookup;
                    }
                    else { 
                        // construct new state
                        int newState = stateTable.Count - 1; 
                        if (newState >= MaxStatesCount) { 
                            return null;
                        } 
                        unmarked.Enqueue(newset);
                        stateTable.Add(newset, newState);
                        transitionTable.Add(new int[symbolsCount + 1]);
                        transition[symbol] = newState; 
                    }
                } 
                state++; 
            }
            // now convert transition table to array 
            return (int[][])transitionTable.ToArray(typeof(int[]));
        }

#if DEBUG 
        private void Dump(StringBuilder bb, BitSet[] followpos, int[][] transitionTable) {
            // Temporary printout 
            bb.AppendLine("Positions"); 
            for (int i = 0; i < positions.Count; i ++) {
                bb.AppendLine(i + " " + positions[i].symbol.ToString(NumberFormatInfo.InvariantInfo) + " " + symbols.NameOf(positions[i].symbol)); 
            }
            bb.AppendLine("Followpos");
            for (int i = 0; i < positions.Count; i++) {
                for (int j = 0; j < positions.Count; j++) { 
                    bb.Append(followpos[i][j] ? "X" : "O");
                } 
               bb.AppendLine(); 
            }
            if (transitionTable != null) { 
                // Temporary printout
                bb.AppendLine("Transitions");
                for (int i = 0; i < transitionTable.Length; i++) {
                    for (int j = 0; j < symbols.Count; j++) { 
                        if (transitionTable[i][j] == -1) {
                            bb.Append("  x  "); 
                        } 
                        else {
                            bb.AppendFormat(" {0:000} ", transitionTable[i][j]); 
                        }
                    }
                    bb.AppendLine(transitionTable[i][symbols.Count] == 1 ? "+" : "");
                } 
            }
        } 
#endif 
    }
 
    /// 
    /// Deterministic Finite Automata
    /// Compilers by Aho, Sethi, Ullman.
    /// ISBN 0-201-10088-6, pp. 115, 116, 140 
    /// 
    sealed class DfaContentValidator : ContentValidator { 
        int[][] transitionTable; 
        SymbolsDictionary symbols;
 
        /// 
        /// Algorithm 3.5 Construction of a DFA from a regular expression
        /// 
        internal DfaContentValidator( 
            int[][] transitionTable, SymbolsDictionary symbols,
            XmlSchemaContentType contentType, bool isOpen, bool isEmptiable)  : base(contentType, isOpen, isEmptiable) { 
            this.transitionTable = transitionTable; 
            this.symbols = symbols;
        } 

        public override void InitValidation(ValidationState context) {
            context.CurrentState.State = 0;
            context.HasMatched = transitionTable[0][symbols.Count] > 0; 
        }
 
        ///  
        /// Algorithm 3.1 Simulating a DFA
        ///  
        public override object ValidateElement(XmlQualifiedName name, ValidationState context, out int errorCode) {
            int symbol = symbols[name];
            int state = transitionTable[context.CurrentState.State][symbol];
            errorCode = 0; 
            if (state != -1) {
                context.CurrentState.State = state; 
                context.HasMatched = transitionTable[context.CurrentState.State][symbols.Count] > 0; 
                return symbols.GetParticle(symbol); // OK
            } 
            if (IsOpen && context.HasMatched) {
                // XDR allows any well-formed contents after matched.
                return null;
            } 
            context.NeedValidateChildren = false;
            errorCode = -1; 
            return null; // will never be here 
        }
 
        public override bool CompleteValidation(ValidationState context) {
            if (!context.HasMatched) {
                return false;
            } 
            return true;
        } 
 
        public override ArrayList ExpectedElements(ValidationState context, bool isRequiredOnly) {
            ArrayList names = null; 
            int[] transition = transitionTable[context.CurrentState.State];
            if (transition != null) {
                for (int i = 0; i < transition.Length - 1; i ++) {
                    if (transition[i] != -1) { 
                        if (names == null) {
                            names = new ArrayList(); 
                        } 
                        XmlSchemaParticle p = (XmlSchemaParticle)symbols.GetParticle(i);
                        if (p == null) { 
                            string s = symbols.NameOf(i);
                            if (s.Length != 0) {
                                names.Add(s);
                            } 
                        }
                        else { 
                            string s = p.NameString; 
                            if (!names.Contains(s)) {
                                names.Add(s); 
                            }
                        }
                    }
                } 
            }
            return names; 
        } 

        public override ArrayList ExpectedParticles(ValidationState context, bool isRequiredOnly) { 
            ArrayList particles = new ArrayList();
            int[] transition = transitionTable[context.CurrentState.State];
            if (transition != null) {
                for (int i = 0; i < transition.Length - 1; i ++) { 
                    if (transition[i] != -1) {
                        XmlSchemaParticle p = (XmlSchemaParticle)symbols.GetParticle(i); 
                        if (p == null) { 
                            continue;
                        } 
                        if (!particles.Contains(p)) {
                            particles.Add(p);
                        }
                    } 
                }
            } 
            return particles; 
        }
    } 

    /// 
    /// Nondeterministic Finite Automata
    /// Compilers by Aho, Sethi, Ullman. 
    /// ISBN 0-201-10088-6, pp. 126,140
    ///  
    sealed class NfaContentValidator : ContentValidator { 
        BitSet firstpos;
        BitSet[] followpos; 
        SymbolsDictionary symbols;
        Positions positions;
        int endMarkerPos;
 
        internal NfaContentValidator(
            BitSet firstpos, BitSet[] followpos, SymbolsDictionary symbols, Positions positions, int endMarkerPos, 
            XmlSchemaContentType contentType, bool isOpen, bool isEmptiable)  : base(contentType, isOpen, isEmptiable) { 
            this.firstpos = firstpos;
            this.followpos = followpos; 
            this.symbols = symbols;
            this.positions = positions;
            this.endMarkerPos = endMarkerPos;
        } 

        public override void InitValidation(ValidationState context) { 
            context.CurPos[0] = firstpos.Clone(); 
            context.CurPos[1] = new BitSet(firstpos.Count);
            context.CurrentState.CurPosIndex = 0; 
        }

        /// 
        /// Algorithm 3.4 Simulation of an NFA 
        /// 
        public override object ValidateElement(XmlQualifiedName name, ValidationState context, out int errorCode) { 
            BitSet curpos = context.CurPos[context.CurrentState.CurPosIndex]; 
            int next = (context.CurrentState.CurPosIndex + 1) % 2;
            BitSet nextpos = context.CurPos[next]; 
            nextpos.Clear();
            int symbol = symbols[name];
            object particle = null;
            errorCode = 0; 
            for (int pos = curpos.NextSet(-1); pos != -1; pos = curpos.NextSet(pos)) {
                // if position can follow 
                if (symbol == positions[pos].symbol) { 
                    nextpos.Or(followpos[pos]);
                    particle = positions[pos].particle; //Between element and wildcard, element will be in earlier pos than wildcard since we add the element nodes to the list of positions first 
                    break;                              // and then ExpandTree for the namespace nodes which adds the wildcards to the positions list
                }
            }
            if (!nextpos.IsEmpty) { 
                context.CurrentState.CurPosIndex = next;
                return particle; 
            } 
            if (IsOpen && curpos[endMarkerPos]) {
                // XDR allows any well-formed contents after matched. 
                return null;
            }
            context.NeedValidateChildren = false;
            errorCode = -1; 
            return null; // will never be here
 
        } 

#if FINDUPA_PARTICLE 
        private bool FindUPAParticle(ref object originalParticle, object newParticle) {
            if (originalParticle == null) {
                originalParticle = newParticle;
                if (originalParticle is XmlSchemaElement) { //if the first particle is element, then break, otherwise try to find an element 
                    return true;
                } 
            } 
            else if (newParticle is XmlSchemaElement) {
                if (originalParticle is XmlSchemaAny) { //Weak wildcards, element takes precendence over any 
                    originalParticle = newParticle;
                    return true;
                }
            } 
            return false;
        } 
#endif 

        public override bool CompleteValidation(ValidationState context) { 
            if (!context.CurPos[context.CurrentState.CurPosIndex][endMarkerPos]) {
                return false;
            }
            return true; 
        }
 
        public override ArrayList ExpectedElements(ValidationState context, bool isRequiredOnly) { 
            ArrayList names = null;
            BitSet curpos = context.CurPos[context.CurrentState.CurPosIndex]; 
            for (int pos = curpos.NextSet(-1); pos != -1; pos = curpos.NextSet(pos)) {
                if (names == null) {
                    names = new ArrayList();
                } 
                XmlSchemaParticle p = (XmlSchemaParticle)positions[pos].particle;
                if (p == null) { 
                    string s = symbols.NameOf(positions[pos].symbol); 
                    if (s.Length != 0) {
                        names.Add(s); 
                    }
                }
                else {
                    string s = p.NameString; 
                    if (!names.Contains(s)) {
                        names.Add(s); 
                    } 
                }
            } 
            return names;
        }

        public override ArrayList ExpectedParticles(ValidationState context, bool isRequiredOnly) { 
            ArrayList particles = new ArrayList();
            BitSet curpos = context.CurPos[context.CurrentState.CurPosIndex]; 
            for (int pos = curpos.NextSet(-1); pos != -1; pos = curpos.NextSet(pos)) { 
                XmlSchemaParticle p = (XmlSchemaParticle)positions[pos].particle;
                if (p == null) { 
                    continue;
                }
                else {
                    if (!particles.Contains(p)) { 
                        particles.Add(p);
                    } 
                } 
            }
            return particles; 
        }
    }

    internal struct RangePositionInfo { 
        public BitSet curpos;
        public decimal[] rangeCounters; 
    } 

    sealed class RangeContentValidator : ContentValidator { 
        BitSet firstpos;
        BitSet[] followpos;
        BitSet positionsWithRangeTerminals;
        SymbolsDictionary symbols; 
        Positions positions;
        int minMaxNodesCount; 
        int endMarkerPos; 

        internal RangeContentValidator( 
            BitSet firstpos, BitSet[] followpos, SymbolsDictionary symbols, Positions positions, int endMarkerPos, XmlSchemaContentType contentType, bool isEmptiable, BitSet positionsWithRangeTerminals, int minmaxNodesCount)  : base(contentType, false, isEmptiable) {
            this.firstpos = firstpos;
            this.followpos = followpos;
            this.symbols = symbols; 
            this.positions = positions;
            this.positionsWithRangeTerminals = positionsWithRangeTerminals; 
            this.minMaxNodesCount = minmaxNodesCount; 
            this.endMarkerPos = endMarkerPos;
        } 

        public override void InitValidation(ValidationState context) {
            int positionsCount = positions.Count;
            List runningPositions = context.RunningPositions; 
            if (runningPositions != null) {
                Debug.Assert(minMaxNodesCount != 0); 
                runningPositions.Clear(); 
            }
            else { 
                runningPositions = new List();
                context.RunningPositions = runningPositions;
            }
            RangePositionInfo rposInfo = new RangePositionInfo(); 
            rposInfo.curpos = firstpos.Clone();
 
            rposInfo.rangeCounters = new decimal[minMaxNodesCount]; 
            runningPositions.Add(rposInfo);
            context.CurrentState.NumberOfRunningPos = 1; 
            context.HasMatched = rposInfo.curpos.Get(endMarkerPos);
        }

        public override object ValidateElement(XmlQualifiedName name, ValidationState context, out int errorCode) { 
            errorCode = 0;
            int symbol = symbols[name]; 
            bool hasSeenFinalPosition = false; 
            List runningPositions = context.RunningPositions;
            int matchCount = context.CurrentState.NumberOfRunningPos; 
            int k = 0;
            RangePositionInfo rposInfo;

            int pos = -1; 
            int firstMatchedIndex = -1;
            bool matched = false; 
 
#if RANGE_DEBUG
            WriteRunningPositions("Current running positions to match", runningPositions, name, matchCount); 
#endif

            while (k < matchCount) { //we are looking for the first match in the list of bitsets
                rposInfo = runningPositions[k]; 
                BitSet curpos = rposInfo.curpos;
                for (int matchpos = curpos.NextSet(-1); matchpos != -1; matchpos = curpos.NextSet(matchpos)) { //In all sets, have to scan all positions because of Disabled UPA possibility 
                    if (symbol == positions[matchpos].symbol) { 
                        pos = matchpos;
                        if (firstMatchedIndex == -1) { // get the first match for this symbol 
                            firstMatchedIndex = k;
                        }
                        matched = true;
                        break; 
                    }
                } 
                if (matched && positions[pos].particle is XmlSchemaElement) { //We found a match in the list, break at that bitset 
                    break;
                } 
                else {
                    k++;
                }
            } 

            if (k == matchCount && pos != -1) { // we did find a match but that was any and hence continued ahead for element 
                k = firstMatchedIndex; 
            }
            if (k < matchCount) { //There is a match 
                if (k != 0) { //If the first bitset itself matched, then no need to remove anything
#if RANGE_DEBUG
                    WriteRunningPositions("Removing unmatched entries till the first match", runningPositions, XmlQualifiedName.Empty, k);
#endif 
                    runningPositions.RemoveRange(0, k); //Delete entries from 0 to k-1
                } 
                matchCount = matchCount - k; 
                k = 0; // Since we re-sized the array
                while (k < matchCount) { 
                    rposInfo = runningPositions[k];
                    matched = rposInfo.curpos.Get(pos); //Look for the bitset that matches the same position as pos
                    if (matched) { //If match found, get the follow positions of the current matched position
#if RANGE_DEBUG 
                        Debug.WriteIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, "Matched position: " + pos + " "); SequenceNode.WriteBitSet(rposInfo.curpos);
                        Debug.WriteIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, "Follow pos of Matched position: "); SequenceNode.WriteBitSet(followpos[pos]); 
#endif 
                        rposInfo.curpos = followpos[pos]; //Note that we are copying the same counters of the current position to that of the follow position
                        runningPositions[k] = rposInfo; 
                        k++;
                    }
                    else { //Clear the current pos and get another position from the list to start matching
                        matchCount--; 
                        if (matchCount > 0) {
                            RangePositionInfo lastrpos = runningPositions[matchCount]; 
                            runningPositions[matchCount] = runningPositions[k]; 
                            runningPositions[k] = lastrpos;
                        } 
                    }
                }
            }
            else { //There is no match 
                matchCount = 0;
            } 
 
            if (matchCount > 0) {
                Debug.Assert(minMaxNodesCount > 0); 
                if (matchCount >= 10000) {
                    context.TooComplex = true;
                    matchCount /= 2;
                } 
#if RANGE_DEBUG
                WriteRunningPositions("Matched positions to expand ", runningPositions, name, matchCount); 
#endif 

                for (k = matchCount - 1; k >= 0; k--) { 
                    int j = k;
                    BitSet currentRunningPosition = runningPositions[k].curpos;
                    hasSeenFinalPosition = hasSeenFinalPosition || currentRunningPosition.Get(endMarkerPos); //Accepting position reached if the current position BitSet contains the endPosition
                    while (matchCount < 10000 && currentRunningPosition.Intersects(positionsWithRangeTerminals)) { 
                        //Now might add 2 more positions to followpos
                        //1. nextIteration of the rangeNode, which is firstpos of its parent's leftChild 
                        //2. Followpos of the range node 

                        BitSet countingPosition = currentRunningPosition.Clone(); 
                        countingPosition.And(positionsWithRangeTerminals);
                        int cPos = countingPosition.NextSet(-1); //Get the first position where leaf range node appears
                        LeafRangeNode lrNode = positions[cPos].particle as LeafRangeNode; //For a position with leaf range node, the particle is the node itself
                        Debug.Assert(lrNode != null); 

                        rposInfo = runningPositions[j]; 
                        if (matchCount + 2 >= runningPositions.Count) { 
                            runningPositions.Add(new RangePositionInfo());
                            runningPositions.Add(new RangePositionInfo()); 
                        }
                        RangePositionInfo newRPosInfo = runningPositions[matchCount];
                        if (newRPosInfo.rangeCounters == null) {
                            newRPosInfo.rangeCounters = new decimal[minMaxNodesCount]; 
                        }
                        Array.Copy(rposInfo.rangeCounters, 0, newRPosInfo.rangeCounters, 0, rposInfo.rangeCounters.Length); 
                        decimal count = ++newRPosInfo.rangeCounters[lrNode.Pos]; 

                        if (count == lrNode.Max) { 
                            newRPosInfo.curpos = followpos[cPos]; //since max has been reached, Get followposition of range node
                            newRPosInfo.rangeCounters[lrNode.Pos] = 0; //reset counter
                            runningPositions[matchCount] = newRPosInfo;
                            j = matchCount++; 
                        }
                        else if (count < lrNode.Min) { 
                            newRPosInfo.curpos = lrNode.NextIteration; 
                            runningPositions[matchCount] = newRPosInfo;
                            matchCount++; 
                            break;
                        }
                        else { // min <= count < max
                            newRPosInfo.curpos = lrNode.NextIteration; //set currentpos to firstpos of node which has the range 
                            runningPositions[matchCount] = newRPosInfo;
                            j = matchCount + 1; 
                            newRPosInfo = runningPositions[j]; 
                            if (newRPosInfo.rangeCounters == null) {
                                newRPosInfo.rangeCounters = new decimal[minMaxNodesCount]; 
                            }
                            Array.Copy(rposInfo.rangeCounters, 0, newRPosInfo.rangeCounters, 0, rposInfo.rangeCounters.Length);
                            newRPosInfo.curpos = followpos[cPos];
                            newRPosInfo.rangeCounters[lrNode.Pos] = 0; 
                            runningPositions[j] = newRPosInfo;
                            matchCount += 2; 
                        } 
                        currentRunningPosition = runningPositions[j].curpos;
                        hasSeenFinalPosition = hasSeenFinalPosition || currentRunningPosition.Get(endMarkerPos); 
                    }
                }
                context.HasMatched = hasSeenFinalPosition;
                context.CurrentState.NumberOfRunningPos = matchCount; 
                return positions[pos].particle;
            } //matchcount > 0 
            errorCode = -1; 
            context.NeedValidateChildren = false;
            return null; 
        }

#if RANGE_DEBUG
        private void WriteRunningPositions(string text, List runningPositions, XmlQualifiedName name, int length) { 
            int counter = 0;
            Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, ""); 
            Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, ""); 
            Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, text + name.Name);
            while (counter < length) { 
                BitSet curpos = runningPositions[counter].curpos;
                SequenceNode.WriteBitSet(curpos);
                for(int rcnt = 0; rcnt < runningPositions[counter].rangeCounters.Length; rcnt++) {
                    Debug.WriteIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, "RangeCounter[" + rcnt + "]" + runningPositions[counter].rangeCounters[rcnt] + " "); 
                }
                Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, ""); 
                Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, ""); 
                counter++;
            } 
        }
#endif
        public override bool CompleteValidation(ValidationState context) {
            return context.HasMatched; 
        }
 
        public override ArrayList ExpectedElements(ValidationState context, bool isRequiredOnly) { 
            ArrayList names = null;
            BitSet expectedPos; 
            if (context.RunningPositions != null) {
                List runningPositions = context.RunningPositions;
                expectedPos = new BitSet(positions.Count);
                for (int i = context.CurrentState.NumberOfRunningPos - 1; i >=0; i--) { 
                    Debug.Assert(runningPositions[i].curpos != null);
                    expectedPos.Or(runningPositions[i].curpos); 
                } 
                for (int pos = expectedPos.NextSet(-1); pos != -1; pos = expectedPos.NextSet(pos)) {
                    if (names == null) { 
                        names = new ArrayList();
                    }
                    int symbol = positions[pos].symbol;
                    if (symbol >= 0) { //non range nodes 
                        XmlSchemaParticle p = positions[pos].particle as XmlSchemaParticle;
                        if (p == null) { 
                            string s = symbols.NameOf(positions[pos].symbol); 
                            if (s.Length != 0) {
                                names.Add(s); 
                            }
                        }
                        else {
                            string s = p.NameString; 
                            if (!names.Contains(s)) {
                                names.Add(s); 
                            } 
                        }
                    } 
                }
            }
            return names;
        } 

        public override ArrayList ExpectedParticles(ValidationState context, bool isRequiredOnly) { 
            ArrayList particles = new ArrayList(); 
            BitSet expectedPos;
            if (context.RunningPositions != null) { 
                List runningPositions = context.RunningPositions;
                expectedPos = new BitSet(positions.Count);
                for (int i = context.CurrentState.NumberOfRunningPos - 1; i >=0; i--) {
                    Debug.Assert(runningPositions[i].curpos != null); 
                    expectedPos.Or(runningPositions[i].curpos);
                } 
                for (int pos = expectedPos.NextSet(-1); pos != -1; pos = expectedPos.NextSet(pos)) { 
                    int symbol = positions[pos].symbol;
                    if (symbol >= 0) { //non range nodes 
                        XmlSchemaParticle p = positions[pos].particle as XmlSchemaParticle;
                        if (p == null) {
                           continue;
                        } 
                        else if (!particles.Contains(p)) {
                           particles.Add(p); 
                        } 
                    }
                } 
            }
            return particles;
        }
    } 

    sealed class AllElementsContentValidator : ContentValidator { 
        Hashtable elements;     // unique terminal names to positions in Bitset mapping 
        object[] particles;
        BitSet isRequired;      // required flags 
        int countRequired = 0;

        public AllElementsContentValidator(XmlSchemaContentType contentType, int size, bool isEmptiable) : base(contentType, false, isEmptiable) {
            elements = new Hashtable(size); 
            particles = new object[size];
            isRequired = new BitSet(size); 
        } 

        public bool AddElement(XmlQualifiedName name, object particle, bool isEmptiable) { 
            if (elements[name] != null) {
                return false;
            }
            int i = elements.Count; 
            elements.Add(name, i);
            particles[i] = particle; 
            if (!isEmptiable) { 
                isRequired.Set(i);
                countRequired ++; 
            }
            return true;
        }
 
        public override bool IsEmptiable {
            get { return base.IsEmptiable || countRequired == 0; } 
        } 

        public override void InitValidation(ValidationState context) { 
            Debug.Assert(elements.Count > 0);
            context.AllElementsSet = new BitSet(elements.Count); //
            context.CurrentState.AllElementsRequired = -1; // no elements at all
        } 

        public override object ValidateElement(XmlQualifiedName name, ValidationState context, out int errorCode) { 
            object lookup = elements[name]; 
            errorCode = 0;
            if (lookup == null) { 
                context.NeedValidateChildren = false;
                return null;
            }
            int index = (int)lookup; 
            if (context.AllElementsSet[index]) {
                errorCode = -2; 
                return null; 
            }
            if (context.CurrentState.AllElementsRequired == -1) { 
                context.CurrentState.AllElementsRequired = 0;
            }
            context.AllElementsSet.Set(index);
            if (isRequired[index]) { 
                context.CurrentState.AllElementsRequired++;
            } 
            return particles[index]; 
        }
 
        public override bool CompleteValidation(ValidationState context) {
            if (context.CurrentState.AllElementsRequired == countRequired || IsEmptiable && context.CurrentState.AllElementsRequired == -1) {
                return true;
            } 
            return false;
        } 
 
        public override ArrayList ExpectedElements(ValidationState context, bool isRequiredOnly) {
            ArrayList names = null; 
            foreach (DictionaryEntry entry in elements) {
                if (!context.AllElementsSet[(int)entry.Value] && (!isRequiredOnly || isRequired[(int)entry.Value])) {
                    if (names == null) {
                        names = new ArrayList(); 
                    }
                    names.Add(entry.Key); 
                } 
            }
            return names; 
        }

        public override ArrayList ExpectedParticles(ValidationState context, bool isRequiredOnly) {
            ArrayList expectedParticles = new ArrayList(); 
            foreach (DictionaryEntry entry in elements) {
                if (!context.AllElementsSet[(int)entry.Value] && (!isRequiredOnly || isRequired[(int)entry.Value])) { 
                    expectedParticles.Add(this.particles[(int)entry.Value]); 
                }
            } 
            return expectedParticles;
        }
    }
    #endregion 
}

// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
//------------------------------------------------------------------------------ 
// 
//     Copyright (c) Microsoft Corporation.  All rights reserved.
// 
// [....] 
//-----------------------------------------------------------------------------
using System; 
using System.Collections; 
using System.Collections.Generic;
using System.Globalization; 
using System.Text;
using System.Diagnostics;

namespace System.Xml.Schema { 

    #region ExceptionSymbolsPositions 
 
    /// 
    /// UPA violations will throw this exception 
    /// 
    class UpaException : Exception {
        object particle1;
        object particle2; 
        public UpaException(object particle1, object particle2) {
            this.particle1 = particle1; 
            this.particle2 = particle2; 
        }
        public object Particle1 { get { return particle1; } } 
        public object Particle2 { get { return particle2; } }
    }

    ///  
    /// SymbolsDictionary is a map between names that ContextValidator recognizes and symbols - int symbol[XmlQualifiedName name].
    /// There are two types of name - full names and wildcards (namespace is specified, local name is anythig). 
    /// Wildcard excludes all full names that would match by the namespace part. 
    /// SymbolsDictionry alwas recognizes all the symbols - the last one is a true wildcard -
    ///      both name and namespace can be anything that none of the other symbols matched. 
    /// 
    class SymbolsDictionary {
        int last = 0;
        Hashtable names; 
        Hashtable wildcards = null;
        ArrayList particles; 
        object particleLast = null; 
        bool isUpaEnforced = true;
 
        public SymbolsDictionary() {
            names = new Hashtable();
            particles = new ArrayList();
        } 

        public int Count { 
            // last one is a "*:*" any wildcard 
            get { return last + 1; }
        } 

        public int CountOfNames {
            get { return names.Count; }
        } 

        ///  
        /// True is particle can be deterministically attributed from the symbol and conversion to DFA is possible. 
        /// 
        public bool IsUpaEnforced { 
            get { return isUpaEnforced; }
            set { isUpaEnforced = value; }
        }
 
        /// 
        /// Add name  and return it's number 
        ///  
        public int AddName(XmlQualifiedName name, object particle) {
            object lookup = names[name]; 
            if (lookup != null) {
                int symbol = (int)lookup;
                if (particles[symbol] != particle) {
                    isUpaEnforced = false; 
                }
                return symbol; 
            } 
            else {
                names.Add(name, last); 
                particles.Add(particle);
                Debug.Assert(particles.Count == last + 1);
                return last ++;
            } 
        }
 
        public void AddNamespaceList(NamespaceList list, object particle, bool allowLocal) { 
            switch (list.Type) {
            case NamespaceList.ListType.Any: 
                particleLast = particle;
                break;
            case NamespaceList.ListType.Other:
                // Create a symbol for the excluded namespace, but don't set a particle for it. 
                AddWildcard(list.Excluded, null);
                if (!allowLocal) { 
                    AddWildcard(string.Empty, null); //##local is not allowed 
                }
                break; 
            case NamespaceList.ListType.Set:
                foreach(string wildcard in list.Enumerate) {
                    AddWildcard(wildcard, particle);
                } 
                break;
            } 
        } 

        private void AddWildcard(string wildcard, object particle) { 
            if (wildcards == null) {
                wildcards = new Hashtable();
            }
            object lookup = wildcards[wildcard]; 
            if (lookup == null) {
                wildcards.Add(wildcard, last); 
                particles.Add(particle); 
                Debug.Assert(particles.Count == last + 1);
                last ++; 
            }
            else if (particle != null) {
                particles[(int)lookup] = particle;
            } 
        }
 
        public ICollection GetNamespaceListSymbols(NamespaceList list) { 
            ArrayList match = new ArrayList();
            foreach(XmlQualifiedName name in names.Keys) { 
                if (name != XmlQualifiedName.Empty && list.Allows(name)) {
                    match.Add(names[name]);
                }
            } 
            if (wildcards != null) {
                foreach(string wildcard in wildcards.Keys) { 
                    if (list.Allows(wildcard)) { 
                        match.Add(wildcards[wildcard]);
                    } 
                }
            }
            if (list.Type == NamespaceList.ListType.Any || list.Type == NamespaceList.ListType.Other) {
                match.Add(last); // add wildcard 
            }
            return match; 
        } 

        ///  
        /// Find the symbol for the given name. If neither names nor wilcards match it last (*.*) symbol will be returned
        /// 
        public int this[XmlQualifiedName name] {
            get { 
                object lookup = names[name];
                if (lookup != null) { 
                    return (int)lookup; 
                }
                if (wildcards != null) { 
                    lookup = wildcards[name.Namespace];
                    if (lookup != null) {
                        return (int)lookup;
                    } 
                }
                return last; // true wildcard 
            } 
        }
 
        /// 
        /// Check if a name exists in the symbol dictionary
        /// 
        public bool Exists(XmlQualifiedName name) { 

            object lookup = names[name]; 
            if (lookup != null) { 
                return true;
            } 
            return false;
        }

        ///  
        /// Return content processing mode for the symbol
        ///  
        public object GetParticle(int symbol) { 
            return symbol == last ? particleLast : particles[symbol];
        } 

        /// 
        /// Output symbol's name
        ///  
        public string NameOf(int symbol) {
            foreach (DictionaryEntry de in names) { 
                if ((int)de.Value == symbol) { 
                    return ((XmlQualifiedName)de.Key).ToString();
                } 
            }
            if (wildcards != null) {
                foreach (DictionaryEntry de in wildcards) {
                    if ((int)de.Value == symbol) { 
                        return (string)de.Key + ":*";
                    } 
                } 
            }
            return "##other:*"; 
        }
    }

    struct Position { 
        public int symbol;
        public object particle; 
        public Position(int symbol, object particle) { 
            this.symbol = symbol;
            this.particle = particle; 
        }
    }

    class Positions { 
        ArrayList positions = new ArrayList();
 
        public int Add(int symbol, object particle) { 
            return positions.Add(new Position(symbol, particle));
        } 

        public Position this[int pos] {
            get { return (Position)positions[pos]; }
        } 

        public int Count { 
            get { return positions.Count; } 
        }
    } 
    #endregion

    #region SystaxTree
    ///  
    /// Base class for the systax tree nodes
    ///  
    abstract class SyntaxTreeNode { 
        /// 
        /// Expand NamesapceListNode and RangeNode nodes. All other nodes 
        /// 
        public abstract void ExpandTree(InteriorNode parent, SymbolsDictionary symbols, Positions positions);

        ///  
        /// Clone the syntaxTree. We need to pass symbolsByPosition because leaf nodes have to add themselves to it.
        ///  
        public abstract SyntaxTreeNode Clone(Positions positions); 

        ///  
        /// From a regular expression to a DFA
        /// Compilers by Aho, Sethi, Ullman.
        /// ISBN 0-201-10088-6, p135
        /// Construct firstpos, lastpos and calculate followpos 
        /// 
        public abstract void ConstructPos(BitSet firstpos, BitSet lastpos, BitSet[] followpos); 
 
        /// 
        /// Returns nullable property that is being used by ConstructPos 
        /// 
        public abstract bool IsNullable { get; }

        ///  
        /// Returns true if node is a range node
        ///  
        public virtual bool IsRangeNode { 
            get {
                return false; 
            }
        }

        ///  
        /// Print syntax tree
        ///  
#if DEBUG 
        public abstract void Dump(StringBuilder bb, SymbolsDictionary symbols, Positions positions);
#endif 
    }

    /// 
    /// Terminal of the syntax tree 
    /// 
    class LeafNode : SyntaxTreeNode { 
        int pos; 

        public LeafNode(int pos) { 
            this.pos = pos;
        }

        public int Pos { 
            get { return pos;}
            set { pos = value; } 
        } 

        public override void ExpandTree(InteriorNode parent, SymbolsDictionary symbols, Positions positions) { 
            // do nothing
        }

        public override SyntaxTreeNode Clone(Positions positions) { 
            return new LeafNode(positions.Add(positions[pos].symbol, positions[pos].particle));
        } 
 
        public override void ConstructPos(BitSet firstpos, BitSet lastpos, BitSet[] followpos) {
            firstpos.Set(pos); 
            lastpos.Set(pos);
        }

        public override bool IsNullable { 
            get { return false; }
        } 
 
#if DEBUG
        public override void Dump(StringBuilder bb, SymbolsDictionary symbols, Positions positions) { 
            bb.Append("\"" + symbols.NameOf(positions[pos].symbol) + "\"");
        }
#endif
    } 

    ///  
    /// Temporary node to represent NamespaceList. Will be expended as a choice of symbols 
    /// 
    class NamespaceListNode : SyntaxTreeNode { 
        protected NamespaceList namespaceList;
        protected object particle;

        public NamespaceListNode(NamespaceList namespaceList, object particle) { 
            this.namespaceList = namespaceList;
            this.particle = particle; 
        } 

        public override SyntaxTreeNode Clone(Positions positions) { 
            // NamespaceListNode nodes have to be removed prior to that
            throw new InvalidOperationException();
        }
 
        public virtual ICollection GetResolvedSymbols(SymbolsDictionary symbols)  {
            return symbols.GetNamespaceListSymbols(namespaceList); 
        } 

        public override void ExpandTree(InteriorNode parent, SymbolsDictionary symbols, Positions positions) { 
            SyntaxTreeNode replacementNode = null;
            foreach(int symbol in GetResolvedSymbols(symbols)) {
                if (symbols.GetParticle(symbol) != particle) {
                    symbols.IsUpaEnforced = false; 
                }
                LeafNode node = new LeafNode(positions.Add(symbol, particle)); 
                if (replacementNode == null) { 
                    replacementNode = node;
                } 
                else {
                    InteriorNode choice = new ChoiceNode();
                    choice.LeftChild = replacementNode;
                    choice.RightChild = node; 
                    replacementNode = choice;
                } 
            } 
            if (parent.LeftChild == this) {
                parent.LeftChild = replacementNode; 
            }
            else {
                parent.RightChild = replacementNode;
            } 
        }
 
        public override void ConstructPos(BitSet firstpos, BitSet lastpos, BitSet[] followpos) { 
            // NamespaceListNode nodes have to be removed prior to that
            throw new InvalidOperationException(); 
        }

        public override bool IsNullable {
            // NamespaceListNode nodes have to be removed prior to that 
            get { throw new InvalidOperationException(); }
        } 
 
#if DEBUG
        public override void Dump(StringBuilder bb, SymbolsDictionary symbols, Positions positions) { 
            bb.Append("[" + namespaceList.ToString() + "]");
        }
#endif
    } 

    ///  
    /// Base class for all internal node. Note that only sequence and choice have right child 
    /// 
    abstract class InteriorNode : SyntaxTreeNode { 
        SyntaxTreeNode leftChild;
        SyntaxTreeNode rightChild;

        public SyntaxTreeNode LeftChild { 
            get { return leftChild;}
            set { leftChild = value;} 
        } 

        public SyntaxTreeNode RightChild { 
            get { return rightChild;}
            set { rightChild = value;}
        }
 
        public override SyntaxTreeNode Clone(Positions positions) {
            InteriorNode other = (InteriorNode)this.MemberwiseClone(); 
            other.LeftChild = leftChild.Clone(positions); 
            if (rightChild != null) {
                other.RightChild = rightChild.Clone(positions); 
            }
            return other;
        }
 
        public override void ExpandTree(InteriorNode parent, SymbolsDictionary symbols, Positions positions) {
            leftChild.ExpandTree(this, symbols, positions); 
            if (rightChild != null) { 
                rightChild.ExpandTree(this, symbols, positions);
            } 
        }
    }

    sealed class SequenceNode : InteriorNode { 
        public override void ConstructPos(BitSet firstpos, BitSet lastpos, BitSet[] followpos) {
            BitSet lastposLeft = new BitSet(lastpos.Count); 
            LeftChild.ConstructPos(firstpos, lastposLeft, followpos); 

            BitSet firstposRight = new BitSet(firstpos.Count); 
            RightChild.ConstructPos(firstposRight, lastpos, followpos);

            if (LeftChild.IsNullable && !RightChild.IsRangeNode) {
                firstpos.Or(firstposRight); 
            }
            if (RightChild.IsNullable) { 
                lastpos.Or(lastposLeft); 
            }
            for (int pos = lastposLeft.NextSet(-1); pos != -1; pos = lastposLeft.NextSet(pos)) { 
                followpos[pos].Or(firstposRight);
            }
            if (RightChild.IsRangeNode) { //firstpos is leftchild.firstpos as the or with firstposRight has not been done as it is a rangenode
                ((LeafRangeNode)RightChild).NextIteration = firstpos.Clone(); 
            }
        } 
 
        public override bool IsNullable {
            get { return (LeftChild.IsNullable && (RightChild.IsNullable || RightChild.IsRangeNode)) || (RightChild.IsRangeNode && ((LeafRangeNode)RightChild).Min == 0 ); } 
        }

#if DEBUG
        internal static void WritePos(BitSet firstpos, BitSet lastpos, BitSet[] followpos) { 
            Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, "FirstPos:  ");
            WriteBitSet(firstpos); 
 
            Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, "LastPos:  ");
            WriteBitSet(lastpos); 

            Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, "Followpos:  ");
            for(int i =0; i < followpos.Length; i++) {
                WriteBitSet(followpos[i]); 
            }
        } 
        internal static void WriteBitSet(BitSet curpos) { 
            int[] list = new int[curpos.Count];
            for (int pos = curpos.NextSet(-1); pos != -1; pos = curpos.NextSet(pos)) { 
                list[pos] = 1;
            }
            for(int i = 0; i < list.Length; i++) {
                Debug.WriteIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, list[i] + " "); 
            }
            Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, ""); 
        } 

 
        public override void Dump(StringBuilder bb, SymbolsDictionary symbols, Positions positions) {
            bb.Append("(");
            LeftChild.Dump(bb, symbols, positions);
            bb.Append(", "); 
            RightChild.Dump(bb, symbols, positions);
            bb.Append(")"); 
        } 
#endif
    } 

    sealed class ChoiceNode : InteriorNode {
        public override void ConstructPos(BitSet firstpos, BitSet lastpos, BitSet[] followpos) {
            LeftChild.ConstructPos(firstpos, lastpos, followpos); 

            BitSet firstposRight = new BitSet(firstpos.Count); 
            BitSet lastposRight = new BitSet(lastpos.Count); 
            RightChild.ConstructPos(firstposRight, lastposRight, followpos);
 
            firstpos.Or(firstposRight);
            lastpos.Or(lastposRight);
        }
 
        public override bool IsNullable {
            get { return LeftChild.IsNullable || RightChild.IsNullable; } 
        } 

#if DEBUG 
        public override void Dump(StringBuilder bb, SymbolsDictionary symbols, Positions positions) {
            bb.Append("(");
            LeftChild.Dump(bb, symbols, positions);
            bb.Append(" | "); 
            RightChild.Dump(bb, symbols, positions);
            bb.Append(")"); 
        } 
#endif
    } 

    sealed class PlusNode : InteriorNode {
        public override void ConstructPos(BitSet firstpos, BitSet lastpos, BitSet[] followpos) {
            LeftChild.ConstructPos(firstpos, lastpos, followpos); 
            for (int pos = lastpos.NextSet(-1); pos != -1; pos = lastpos.NextSet(pos)) {
                followpos[pos].Or(firstpos); 
            } 
        }
 
        public override bool IsNullable {
            get { return LeftChild.IsNullable; }
        }
 
#if DEBUG
        public override void Dump(StringBuilder bb, SymbolsDictionary symbols, Positions positions) { 
            LeftChild.Dump(bb, symbols, positions); 
            bb.Append("+");
        } 
#endif
    }

    sealed class QmarkNode : InteriorNode { 
        public override void ConstructPos(BitSet firstpos, BitSet lastpos, BitSet[] followpos) {
            LeftChild.ConstructPos(firstpos, lastpos, followpos); 
        } 

        public override bool IsNullable { 
            get { return true; }
        }

#if DEBUG 
        public override void Dump(StringBuilder bb, SymbolsDictionary symbols, Positions positions) {
            LeftChild.Dump(bb, symbols, positions); 
            bb.Append("?"); 
        }
#endif 
    }

    sealed class StarNode : InteriorNode {
        public override void ConstructPos(BitSet firstpos, BitSet lastpos, BitSet[] followpos) { 
            LeftChild.ConstructPos(firstpos, lastpos, followpos);
            for (int pos = lastpos.NextSet(-1); pos != -1; pos = lastpos.NextSet(pos)) { 
                followpos[pos].Or(firstpos); 
            }
        } 

        public override bool IsNullable {
            get { return true; }
        } 

#if DEBUG 
        public override void Dump(StringBuilder bb, SymbolsDictionary symbols, Positions positions) { 
            LeftChild.Dump(bb, symbols, positions);
            bb.Append("*"); 
        }
#endif
    }
 
#if EXPANDRANGE
    ///  
    /// Temporary node to occurance range. Will be expended to a sequence of terminals 
    /// 
    sealed class RangeNode : InteriorNode { 
        int min;
        int max;

        public RangeNode(int min, int max) { 
            this.min = min;
            this.max = max; 
        } 

        public int Max { 
            get { return max;}
        }

        public int Min { 
            get { return min;}
        } 
 
        public override SyntaxTreeNode Clone(Positions positions) {
            // range nodes have to be removed prior to that 
            throw new InvalidOperationException();
        }

        ///  
        /// Expand tree will replace a{min, max} using following algorithm. Bare in mind that this sequence will have at least two leaves
        /// if min == 0 (max cannot be unbounded) 
        ///         a?, ...  a? 
        ///         \__     __/
        ///             max 
        /// else
        ///     if max == unbounded
        ///         a,  ...   a, a*
        ///         \__     __/ 
        ///             min
        ///     else 
        ///         a,  ...   a, a?,   ...     a? 
        ///         \__     __/  \__          __/
        ///             min          max - min 
        /// 
        public override void ExpandTree(InteriorNode parent, SymbolsDictionary symbols, Positions positions) {
            LeftChild.ExpandTree(this, symbols, positions);
            SyntaxTreeNode replacementNode = null; 
            if (min == 0) {
                Debug.Assert(max != int.MaxValue); 
                replacementNode = NewQmark(LeftChild); 
                for (int i = 0; i < max - 1; i ++) {
                    replacementNode = NewSequence(replacementNode, NewQmark(LeftChild.Clone(positions))); 
                }
            }
            else {
                replacementNode = LeftChild; 
                for (int i = 0; i < min - 1; i ++) {
                    replacementNode = NewSequence(replacementNode, LeftChild.Clone(positions)); 
                } 
                if (max == int.MaxValue) {
                    replacementNode = NewSequence(replacementNode, NewStar(LeftChild.Clone(positions))); 
                }
                else {
                    for (int i = 0; i < max - min; i ++) {
                        replacementNode = NewSequence(replacementNode, NewQmark(LeftChild.Clone(positions))); 
                    }
                } 
            } 
            if (parent.LeftChild == this) {
                parent.LeftChild = replacementNode; 
            }
            else {
                parent.RightChild = replacementNode;
            } 
        }
 
        private SyntaxTreeNode NewSequence(SyntaxTreeNode leftChild, SyntaxTreeNode rightChild) { 
            InteriorNode sequence = new SequenceNode();
            sequence.LeftChild = leftChild; 
            sequence.RightChild = rightChild;
            return sequence;
        }
 
        private SyntaxTreeNode NewStar(SyntaxTreeNode leftChild) {
            InteriorNode star = new StarNode(); 
            star.LeftChild = leftChild; 
            return star;
        } 

        private SyntaxTreeNode NewQmark(SyntaxTreeNode leftChild) {
            InteriorNode qmark = new QmarkNode();
            qmark.LeftChild = leftChild; 
            return qmark;
        } 
 
        public override void ConstructPos(BitSet firstpos, BitSet lastpos, BitSet[] followpos) {
            throw new InvalidOperationException(); 
        }

        public override bool IsNullable {
            get { throw new InvalidOperationException(); } 
        }
 
        public override void Dump(StringBuilder bb, SymbolsDictionary symbols, Positions positions) { 
            LeftChild.Dump(bb, symbols, positions);
            bb.Append("{" + Convert.ToString(min, NumberFormatInfo.InvariantInfo) + ", " + Convert.ToString(max, NumberFormatInfo.InvariantInfo) + "}"); 
        }

    }
#endif 

 
    ///  
    /// Using range node as one of the terminals
    ///  
    sealed class LeafRangeNode : LeafNode {
        decimal min;
        decimal max;
        BitSet nextIteration; 

        public LeafRangeNode(decimal min, decimal max) : this(-1, min, max) {} 
 
        public LeafRangeNode(int pos, decimal min, decimal max) : base(pos) {
            this.min = min; 
            this.max = max;
        }

        public decimal Max { 
            get { return max;}
        } 
 
        public decimal Min {
            get { return min;} 
        }

        public BitSet NextIteration {
            get { 
                return nextIteration;
            } 
            set { 
                nextIteration = value;
            } 
        }

        public override SyntaxTreeNode Clone(Positions positions) {
            return new LeafRangeNode(this.Pos, this.min, this.max); 
        }
 
        public override bool IsRangeNode { 
            get {
                return true; 
            }
        }
    }
 
    #endregion
 
    #region ContentValidator 
    /// 
    /// Basic ContentValidator 
    /// 
    class ContentValidator {
        XmlSchemaContentType contentType;
        bool isOpen;  //For XDR Content Models or ANY 
        bool isEmptiable;
 
        public static readonly ContentValidator Empty = new ContentValidator(XmlSchemaContentType.Empty); 
        public static readonly ContentValidator TextOnly = new ContentValidator(XmlSchemaContentType.TextOnly, false, false);
        public static readonly ContentValidator Mixed = new ContentValidator(XmlSchemaContentType.Mixed); 
        public static readonly ContentValidator Any = new ContentValidator(XmlSchemaContentType.Mixed, true, true);

        public ContentValidator(XmlSchemaContentType contentType) {
            this.contentType = contentType; 
            this.isEmptiable = true;
        } 
 
        protected ContentValidator(XmlSchemaContentType contentType, bool isOpen, bool isEmptiable) {
            this.contentType = contentType; 
            this.isOpen = isOpen;
            this.isEmptiable = isEmptiable;
        }
 
        public XmlSchemaContentType ContentType {
            get { return contentType; } 
        } 

        public bool PreserveWhitespace { 
            get { return contentType == XmlSchemaContentType.TextOnly || contentType == XmlSchemaContentType.Mixed; }
        }

        public virtual bool IsEmptiable { 
            get { return isEmptiable; }
        } 
 
        public bool IsOpen {
            get { 
                if (contentType == XmlSchemaContentType.TextOnly || contentType == XmlSchemaContentType.Empty)
                    return false;
                else
                    return isOpen; 
            }
            set { isOpen = value; } 
        } 

        public virtual void InitValidation(ValidationState context) { 
            // do nothin'
        }

        public virtual object ValidateElement(XmlQualifiedName name, ValidationState context, out int errorCode) { 
            if (contentType == XmlSchemaContentType.TextOnly || contentType == XmlSchemaContentType.Empty) { //Cannot have elements in TextOnly or Empty content
                context.NeedValidateChildren = false; 
            } 
            errorCode = -1;
            return null; 
        }

        public virtual bool CompleteValidation(ValidationState context) {
            return true; 
        }
 
        public virtual ArrayList ExpectedElements(ValidationState context, bool isRequiredOnly) { 
            return null;
        } 

        public virtual ArrayList ExpectedParticles(ValidationState context, bool isRequiredOnly) {
            return null;
        } 
    }
 
    sealed class ParticleContentValidator : ContentValidator { 
        SymbolsDictionary symbols;
        Positions positions; 
        Stack stack;                        // parsing context
        SyntaxTreeNode contentNode;         // content model points to syntax tree
        bool isPartial;                     // whether the closure applies to partial or the whole node that is on top of the stack
        int minMaxNodesCount; 
        bool enableUpaCheck;
 
        public ParticleContentValidator(XmlSchemaContentType contentType) : this(contentType, true) { 
        }
 
        public ParticleContentValidator(XmlSchemaContentType contentType, bool enableUpaCheck) : base(contentType) {
            this.enableUpaCheck = enableUpaCheck;
        }
 
        public override void InitValidation(ValidationState context) {
            // ParticleContentValidator cannot be used during validation 
            throw new InvalidOperationException(); 
        }
 
        public override object ValidateElement(XmlQualifiedName name, ValidationState context, out int errorCode) {
            // ParticleContentValidator cannot be used during validation
            throw new InvalidOperationException();
        } 

        public override bool CompleteValidation(ValidationState context) { 
            // ParticleContentValidator cannot be used during validation 
            throw new InvalidOperationException();
        } 

        public void Start() {
            symbols = new SymbolsDictionary();
            positions = new Positions(); 
            stack = new Stack();
        } 
 
        public void OpenGroup() {
            stack.Push(null); 
        }

        public void CloseGroup() {
            SyntaxTreeNode node = (SyntaxTreeNode)stack.Pop(); 
            if (node == null) {
                return; 
            } 
            if (stack.Count == 0) {
                contentNode = node; 
                isPartial = false;
            }
            else {
                // some collapsing to do... 
                InteriorNode inNode = (InteriorNode)stack.Pop();
                if (inNode != null) { 
                    inNode.RightChild = node; 
                    node = inNode;
                    isPartial = true; 
                }
                else {
                    isPartial = false;
                } 
                stack.Push(node);
            } 
        } 

        public bool Exists(XmlQualifiedName name) { 
            if (symbols.Exists(name)) {
                return true;
            }
            return false; 
        }
 
        public void AddName(XmlQualifiedName name, object particle) { 
            AddLeafNode(new LeafNode(positions.Add(symbols.AddName(name, particle), particle)));
        } 

        public void AddNamespaceList(NamespaceList namespaceList, object particle) {
            symbols.AddNamespaceList(namespaceList, particle, false);
            AddLeafNode(new NamespaceListNode(namespaceList, particle)); 
        }
 
        private void AddLeafNode(SyntaxTreeNode node) { 
            if (stack.Count > 0) {
                InteriorNode inNode = (InteriorNode)stack.Pop(); 
                if (inNode != null) {
                    inNode.RightChild = node;
                    node = inNode;
                } 
            }
            stack.Push( node ); 
            isPartial = true; 
        }
 
        public void AddChoice() {
            SyntaxTreeNode node = (SyntaxTreeNode)stack.Pop();
            InteriorNode choice = new ChoiceNode();
            choice.LeftChild = node; 
            stack.Push(choice);
        } 
 
        public void AddSequence() {
            SyntaxTreeNode node = (SyntaxTreeNode)stack.Pop(); 
            InteriorNode sequence = new SequenceNode();
            sequence.LeftChild = node;
            stack.Push(sequence);
        } 

        public void AddStar() { 
            Closure(new StarNode()); 
        }
 
        public void AddPlus() {
            Closure(new PlusNode());
        }
 
        public void AddQMark() {
            Closure(new QmarkNode()); 
        } 

        public void AddLeafRange(decimal min, decimal max) { 
            LeafRangeNode rNode = new LeafRangeNode(min, max);
            int pos = positions.Add(-2, rNode);
            rNode.Pos = pos;
 
            InteriorNode sequence = new SequenceNode();
            sequence.RightChild = rNode; 
            Closure(sequence); 
            minMaxNodesCount++;
        } 

#if EXPANDRANGE
        public void AddRange(int min, int max) {
            Closure(new RangeNode(min, max)); 
        }
#endif 
        private void Closure(InteriorNode node) { 
            if (stack.Count > 0) {
                SyntaxTreeNode topNode = (SyntaxTreeNode)stack.Pop(); 
                InteriorNode inNode = topNode as InteriorNode;
                if (isPartial && inNode != null) {
                    // need to reach in and wrap right hand side of element.
                    // and n remains the same. 
                    node.LeftChild = inNode.RightChild;
                    inNode.RightChild = node; 
                } 
                else {
                    // wrap terminal or any node 
                    node.LeftChild = topNode;
                    topNode = node;
                }
                stack.Push(topNode); 
            }
            else if (contentNode != null) { //If there is content to wrap 
                // wrap whole content 
                node.LeftChild = contentNode;
                contentNode = node; 
            }
        }

        public ContentValidator Finish() { 
            return Finish(true);
        } 
 
        public ContentValidator Finish(bool useDFA) {
            Debug.Assert(ContentType == XmlSchemaContentType.ElementOnly || ContentType == XmlSchemaContentType.Mixed); 
            if (contentNode == null) {
                if (ContentType == XmlSchemaContentType.Mixed) {
                    string ctype = IsOpen ? "Any" : "TextOnly";
                    Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled,  "\t\t\tContentType:  " + ctype); 
                    return IsOpen ? ContentValidator.Any : ContentValidator.TextOnly;
                } 
                else { 
                    Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled,  "\t\t\tContent:   EMPTY");
                    Debug.Assert(!IsOpen); 
                    return ContentValidator.Empty;
                }
            }
 
            #if DEBUG
            StringBuilder bb = new StringBuilder(); 
            contentNode.Dump(bb, symbols, positions); 
            Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled,  "\t\t\tContent :   " + bb.ToString());
            #endif 

            // Add end marker
            InteriorNode contentRoot = new SequenceNode();
            contentRoot.LeftChild = contentNode; 
            LeafNode endMarker = new LeafNode(positions.Add(symbols.AddName(XmlQualifiedName.Empty, null), null));
            contentRoot.RightChild = endMarker; 
 
            // Eliminate NamespaceListNode(s) and RangeNode(s)
            contentNode.ExpandTree(contentRoot, symbols, positions); 

            #if DEBUG
            bb = new StringBuilder();
            contentRoot.LeftChild.Dump(bb, symbols, positions); 
            Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled,  "\t\t\tExpended:   " + bb.ToString());
            #endif 
 
            // calculate followpos
            int symbolsCount = symbols.Count; 
            int positionsCount = positions.Count;
            BitSet firstpos = new BitSet(positionsCount);
            BitSet lastpos = new BitSet(positionsCount);
            BitSet[] followpos = new BitSet[positionsCount]; 
            for (int i = 0; i < positionsCount; i++) {
                followpos[i] = new BitSet(positionsCount); 
            } 
            contentRoot.ConstructPos(firstpos, lastpos, followpos);
#if DEBUG 
            Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, "firstpos, lastpos, followpos");
            SequenceNode.WritePos(firstpos, lastpos, followpos);
#endif
            if (minMaxNodesCount > 0) { //If the tree has any terminal range nodes 
                BitSet positionsWithRangeTerminals;
                BitSet[] minMaxFollowPos = CalculateTotalFollowposForRangeNodes(firstpos, followpos, out positionsWithRangeTerminals); 
 
                if (enableUpaCheck) {
                    CheckCMUPAWithLeafRangeNodes(GetApplicableMinMaxFollowPos(firstpos, positionsWithRangeTerminals, minMaxFollowPos)); 
                    for (int i = 0; i < positionsCount; i++) {
                        CheckCMUPAWithLeafRangeNodes(GetApplicableMinMaxFollowPos(followpos[i], positionsWithRangeTerminals, minMaxFollowPos));
                    }
                } 
                return new RangeContentValidator(firstpos, followpos, symbols, positions, endMarker.Pos, this.ContentType, contentRoot.LeftChild.IsNullable, positionsWithRangeTerminals, minMaxNodesCount);
            } 
            else { 
                int[][] transitionTable = null;
                // if each symbol has unique particle we are golden 
                if (!symbols.IsUpaEnforced) {
                    if (enableUpaCheck) {
                        // multiple positions that match the same symbol have different particles, but they never follow the same position
                        CheckUniqueParticleAttribution(firstpos, followpos); 
                    }
                } 
                else if (useDFA) { 
                    // Can return null if the number of states reaches higher than 8192 / positionsCount
                    transitionTable = BuildTransitionTable(firstpos, followpos, endMarker.Pos); 
                }
                #if DEBUG
                bb = new StringBuilder();
                Dump(bb, followpos, transitionTable); 
                Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, bb.ToString());
                #endif 
                if (transitionTable != null) { 
                    return new DfaContentValidator(transitionTable, symbols,this.ContentType, this.IsOpen, contentRoot.LeftChild.IsNullable);
                } else { 
                    return new NfaContentValidator(firstpos, followpos, symbols, positions, endMarker.Pos, this.ContentType, this.IsOpen, contentRoot.LeftChild.IsNullable);
                }
            }
        } 

        private BitSet[] CalculateTotalFollowposForRangeNodes(BitSet firstpos, BitSet[] followpos, out BitSet posWithRangeTerminals) { 
            int positionsCount = positions.Count; //terminals 
            posWithRangeTerminals = new BitSet(positionsCount);
 
            //Compute followpos for each range node
            //For any range node that is surrounded by an outer range node, its follow positions will include those of the outer range node
            BitSet[] minmaxFollowPos = new BitSet[minMaxNodesCount];
            int localMinMaxNodesCount = 0; 

            for (int i = positionsCount - 1;  i >= 0; i--) { 
                Position p = positions[i]; 
                if (p.symbol == -2) { //P is a LeafRangeNode
                    LeafRangeNode lrNode = p.particle as LeafRangeNode; 
                    Debug.Assert(lrNode != null);
                    BitSet tempFollowPos = new BitSet(positionsCount);
                    tempFollowPos.Clear();
                    tempFollowPos.Or(followpos[i]); //Add the followpos of the range node 
                    if (lrNode.Min != lrNode.Max) { //If they are the same, then followpos cannot include the firstpos
                        tempFollowPos.Or(lrNode.NextIteration); //Add the nextIteration of the range node (this is the firstpos of its parent's leftChild) 
                    } 

                    //For each position in the bitset, if it is a outer range node (pos > i), then add its followpos as well to the current node's followpos 
                    for (int pos = tempFollowPos.NextSet(-1); pos != -1; pos = tempFollowPos.NextSet(pos)) {
                        if (pos > i) {
                            Position p1 = positions[pos];
                            if (p1.symbol == -2) { 
                                LeafRangeNode lrNode1 = p1.particle as LeafRangeNode;
                                Debug.Assert(lrNode1 != null); 
                                tempFollowPos.Or(minmaxFollowPos[lrNode1.Pos]); 
                            }
                        } 
                    }
                    //set the followpos built to the index in the BitSet[]
                    minmaxFollowPos[localMinMaxNodesCount] = tempFollowPos;
                    lrNode.Pos = localMinMaxNodesCount++; 
                    posWithRangeTerminals.Set(i);
                } 
            } 
            return minmaxFollowPos;
        } 

        private void CheckCMUPAWithLeafRangeNodes(BitSet curpos) {
            object[] symbolMatches = new object[symbols.Count];
            for (int pos = curpos.NextSet(-1); pos != -1; pos = curpos.NextSet(pos)) { 
                Position currentPosition = positions[pos];
                int symbol = currentPosition.symbol; 
                if (symbol >= 0) { //its not a range position 
                    if (symbolMatches[symbol] != null) {
                        throw new UpaException(symbolMatches[symbol], currentPosition.particle); 
                    }
                    else {
                        symbolMatches[symbol] = currentPosition.particle;
                    } 
                }
            } 
        } 

        //For each position, this method calculates the additional follows of any range nodes that need to be added to its followpos 
        //((ab?)2-4)c, Followpos of a is b as well as that of node R(2-4) = c
        private BitSet GetApplicableMinMaxFollowPos(BitSet curpos, BitSet posWithRangeTerminals, BitSet[] minmaxFollowPos) {
            if (curpos.Intersects(posWithRangeTerminals)) {
                BitSet newSet = new BitSet(positions.Count); //Doing work again 
                newSet.Or(curpos);
                newSet.And(posWithRangeTerminals); 
                curpos = curpos.Clone(); 
                for (int pos = newSet.NextSet(-1); pos != -1; pos = newSet.NextSet(pos)) {
                    LeafRangeNode lrNode = positions[pos].particle as LeafRangeNode; 
                    curpos.Or(minmaxFollowPos[lrNode.Pos]);
                }
            }
            return curpos; 
        }
 
        private void CheckUniqueParticleAttribution(BitSet firstpos, BitSet[] followpos) { 
            CheckUniqueParticleAttribution(firstpos);
            for (int i = 0; i < positions.Count; i++) { 
                CheckUniqueParticleAttribution(followpos[i]);
            }
        }
 
        private void CheckUniqueParticleAttribution(BitSet curpos) {
            // particles will be attributed uniquely if the same symbol never poins to two different ones 
            object[] particles = new object[symbols.Count]; 
            for (int pos = curpos.NextSet(-1); pos != -1; pos = curpos.NextSet(pos)) {
                // if position can follow 
                int symbol = positions[pos].symbol;
                if (particles[symbol] == null) {
                    // set particle for the symbol
                    particles[symbol] = positions[pos].particle; 
                }
                else if (particles[symbol] != positions[pos].particle) { 
                    throw new UpaException(particles[symbol], positions[pos].particle); 
                }
                // two different position point to the same symbol and particle - that's OK 
            }
        }

        ///  
        /// Algorithm 3.5 Construction of a DFA from a regular expression
        ///  
        private int[][] BuildTransitionTable(BitSet firstpos, BitSet[] followpos, int endMarkerPos) { 
            const int TimeConstant = 8192; //(MaxStates * MaxPositions should be a constant)
            int positionsCount = positions.Count; 
            int MaxStatesCount = TimeConstant / positionsCount;
            int symbolsCount = symbols.Count;

            // transition table (Dtran in the book) 
            ArrayList transitionTable = new ArrayList();
 
            // state lookup table (Dstate in the book) 
            Hashtable stateTable = new Hashtable();
 
            // Add empty set that would signal an error
            stateTable.Add(new BitSet(positionsCount), -1);

            // lists unmarked states 
            Queue unmarked = new Queue();
 
            // initially, the only unmarked state in Dstates is firstpo(root) 
            int state = 0;
            unmarked.Enqueue(firstpos); 
            stateTable.Add(firstpos, 0);
            transitionTable.Add(new int[symbolsCount + 1]);

            // while there is an umnarked state T in Dstates do begin 
            while (unmarked.Count > 0) {
                BitSet statePosSet = (BitSet)unmarked.Dequeue(); // all positions that constitute DFA state 
                Debug.Assert(state == (int)stateTable[statePosSet]); // just make sure that statePosSet is for correct state 
                int[] transition = (int[])transitionTable[state];
                if (statePosSet[endMarkerPos]) { 
                    transition[symbolsCount] = 1;   // accepting
                }

                // for each input symbol a do begin 
                for (int symbol = 0; symbol < symbolsCount; symbol ++) {
                    // let U be the set of positions that are in followpos(p) 
                    //       for some position p in T 
                    //       such that the symbol at position p is a
                    BitSet newset = new BitSet(positionsCount); 
                    for (int pos = statePosSet.NextSet(-1); pos != -1; pos = statePosSet.NextSet(pos)) {
                        if (symbol == positions[pos].symbol) {
                            newset.Or(followpos[pos]);
                        } 
                    }
 
                    // if U is not empty and is not in Dstates then 
                    //      add U as an unmarked state to Dstates
                    object lookup = stateTable[newset]; 
                    if (lookup != null) {
                        transition[symbol] = (int)lookup;
                    }
                    else { 
                        // construct new state
                        int newState = stateTable.Count - 1; 
                        if (newState >= MaxStatesCount) { 
                            return null;
                        } 
                        unmarked.Enqueue(newset);
                        stateTable.Add(newset, newState);
                        transitionTable.Add(new int[symbolsCount + 1]);
                        transition[symbol] = newState; 
                    }
                } 
                state++; 
            }
            // now convert transition table to array 
            return (int[][])transitionTable.ToArray(typeof(int[]));
        }

#if DEBUG 
        private void Dump(StringBuilder bb, BitSet[] followpos, int[][] transitionTable) {
            // Temporary printout 
            bb.AppendLine("Positions"); 
            for (int i = 0; i < positions.Count; i ++) {
                bb.AppendLine(i + " " + positions[i].symbol.ToString(NumberFormatInfo.InvariantInfo) + " " + symbols.NameOf(positions[i].symbol)); 
            }
            bb.AppendLine("Followpos");
            for (int i = 0; i < positions.Count; i++) {
                for (int j = 0; j < positions.Count; j++) { 
                    bb.Append(followpos[i][j] ? "X" : "O");
                } 
               bb.AppendLine(); 
            }
            if (transitionTable != null) { 
                // Temporary printout
                bb.AppendLine("Transitions");
                for (int i = 0; i < transitionTable.Length; i++) {
                    for (int j = 0; j < symbols.Count; j++) { 
                        if (transitionTable[i][j] == -1) {
                            bb.Append("  x  "); 
                        } 
                        else {
                            bb.AppendFormat(" {0:000} ", transitionTable[i][j]); 
                        }
                    }
                    bb.AppendLine(transitionTable[i][symbols.Count] == 1 ? "+" : "");
                } 
            }
        } 
#endif 
    }
 
    /// 
    /// Deterministic Finite Automata
    /// Compilers by Aho, Sethi, Ullman.
    /// ISBN 0-201-10088-6, pp. 115, 116, 140 
    /// 
    sealed class DfaContentValidator : ContentValidator { 
        int[][] transitionTable; 
        SymbolsDictionary symbols;
 
        /// 
        /// Algorithm 3.5 Construction of a DFA from a regular expression
        /// 
        internal DfaContentValidator( 
            int[][] transitionTable, SymbolsDictionary symbols,
            XmlSchemaContentType contentType, bool isOpen, bool isEmptiable)  : base(contentType, isOpen, isEmptiable) { 
            this.transitionTable = transitionTable; 
            this.symbols = symbols;
        } 

        public override void InitValidation(ValidationState context) {
            context.CurrentState.State = 0;
            context.HasMatched = transitionTable[0][symbols.Count] > 0; 
        }
 
        ///  
        /// Algorithm 3.1 Simulating a DFA
        ///  
        public override object ValidateElement(XmlQualifiedName name, ValidationState context, out int errorCode) {
            int symbol = symbols[name];
            int state = transitionTable[context.CurrentState.State][symbol];
            errorCode = 0; 
            if (state != -1) {
                context.CurrentState.State = state; 
                context.HasMatched = transitionTable[context.CurrentState.State][symbols.Count] > 0; 
                return symbols.GetParticle(symbol); // OK
            } 
            if (IsOpen && context.HasMatched) {
                // XDR allows any well-formed contents after matched.
                return null;
            } 
            context.NeedValidateChildren = false;
            errorCode = -1; 
            return null; // will never be here 
        }
 
        public override bool CompleteValidation(ValidationState context) {
            if (!context.HasMatched) {
                return false;
            } 
            return true;
        } 
 
        public override ArrayList ExpectedElements(ValidationState context, bool isRequiredOnly) {
            ArrayList names = null; 
            int[] transition = transitionTable[context.CurrentState.State];
            if (transition != null) {
                for (int i = 0; i < transition.Length - 1; i ++) {
                    if (transition[i] != -1) { 
                        if (names == null) {
                            names = new ArrayList(); 
                        } 
                        XmlSchemaParticle p = (XmlSchemaParticle)symbols.GetParticle(i);
                        if (p == null) { 
                            string s = symbols.NameOf(i);
                            if (s.Length != 0) {
                                names.Add(s);
                            } 
                        }
                        else { 
                            string s = p.NameString; 
                            if (!names.Contains(s)) {
                                names.Add(s); 
                            }
                        }
                    }
                } 
            }
            return names; 
        } 

        public override ArrayList ExpectedParticles(ValidationState context, bool isRequiredOnly) { 
            ArrayList particles = new ArrayList();
            int[] transition = transitionTable[context.CurrentState.State];
            if (transition != null) {
                for (int i = 0; i < transition.Length - 1; i ++) { 
                    if (transition[i] != -1) {
                        XmlSchemaParticle p = (XmlSchemaParticle)symbols.GetParticle(i); 
                        if (p == null) { 
                            continue;
                        } 
                        if (!particles.Contains(p)) {
                            particles.Add(p);
                        }
                    } 
                }
            } 
            return particles; 
        }
    } 

    /// 
    /// Nondeterministic Finite Automata
    /// Compilers by Aho, Sethi, Ullman. 
    /// ISBN 0-201-10088-6, pp. 126,140
    ///  
    sealed class NfaContentValidator : ContentValidator { 
        BitSet firstpos;
        BitSet[] followpos; 
        SymbolsDictionary symbols;
        Positions positions;
        int endMarkerPos;
 
        internal NfaContentValidator(
            BitSet firstpos, BitSet[] followpos, SymbolsDictionary symbols, Positions positions, int endMarkerPos, 
            XmlSchemaContentType contentType, bool isOpen, bool isEmptiable)  : base(contentType, isOpen, isEmptiable) { 
            this.firstpos = firstpos;
            this.followpos = followpos; 
            this.symbols = symbols;
            this.positions = positions;
            this.endMarkerPos = endMarkerPos;
        } 

        public override void InitValidation(ValidationState context) { 
            context.CurPos[0] = firstpos.Clone(); 
            context.CurPos[1] = new BitSet(firstpos.Count);
            context.CurrentState.CurPosIndex = 0; 
        }

        /// 
        /// Algorithm 3.4 Simulation of an NFA 
        /// 
        public override object ValidateElement(XmlQualifiedName name, ValidationState context, out int errorCode) { 
            BitSet curpos = context.CurPos[context.CurrentState.CurPosIndex]; 
            int next = (context.CurrentState.CurPosIndex + 1) % 2;
            BitSet nextpos = context.CurPos[next]; 
            nextpos.Clear();
            int symbol = symbols[name];
            object particle = null;
            errorCode = 0; 
            for (int pos = curpos.NextSet(-1); pos != -1; pos = curpos.NextSet(pos)) {
                // if position can follow 
                if (symbol == positions[pos].symbol) { 
                    nextpos.Or(followpos[pos]);
                    particle = positions[pos].particle; //Between element and wildcard, element will be in earlier pos than wildcard since we add the element nodes to the list of positions first 
                    break;                              // and then ExpandTree for the namespace nodes which adds the wildcards to the positions list
                }
            }
            if (!nextpos.IsEmpty) { 
                context.CurrentState.CurPosIndex = next;
                return particle; 
            } 
            if (IsOpen && curpos[endMarkerPos]) {
                // XDR allows any well-formed contents after matched. 
                return null;
            }
            context.NeedValidateChildren = false;
            errorCode = -1; 
            return null; // will never be here
 
        } 

#if FINDUPA_PARTICLE 
        private bool FindUPAParticle(ref object originalParticle, object newParticle) {
            if (originalParticle == null) {
                originalParticle = newParticle;
                if (originalParticle is XmlSchemaElement) { //if the first particle is element, then break, otherwise try to find an element 
                    return true;
                } 
            } 
            else if (newParticle is XmlSchemaElement) {
                if (originalParticle is XmlSchemaAny) { //Weak wildcards, element takes precendence over any 
                    originalParticle = newParticle;
                    return true;
                }
            } 
            return false;
        } 
#endif 

        public override bool CompleteValidation(ValidationState context) { 
            if (!context.CurPos[context.CurrentState.CurPosIndex][endMarkerPos]) {
                return false;
            }
            return true; 
        }
 
        public override ArrayList ExpectedElements(ValidationState context, bool isRequiredOnly) { 
            ArrayList names = null;
            BitSet curpos = context.CurPos[context.CurrentState.CurPosIndex]; 
            for (int pos = curpos.NextSet(-1); pos != -1; pos = curpos.NextSet(pos)) {
                if (names == null) {
                    names = new ArrayList();
                } 
                XmlSchemaParticle p = (XmlSchemaParticle)positions[pos].particle;
                if (p == null) { 
                    string s = symbols.NameOf(positions[pos].symbol); 
                    if (s.Length != 0) {
                        names.Add(s); 
                    }
                }
                else {
                    string s = p.NameString; 
                    if (!names.Contains(s)) {
                        names.Add(s); 
                    } 
                }
            } 
            return names;
        }

        public override ArrayList ExpectedParticles(ValidationState context, bool isRequiredOnly) { 
            ArrayList particles = new ArrayList();
            BitSet curpos = context.CurPos[context.CurrentState.CurPosIndex]; 
            for (int pos = curpos.NextSet(-1); pos != -1; pos = curpos.NextSet(pos)) { 
                XmlSchemaParticle p = (XmlSchemaParticle)positions[pos].particle;
                if (p == null) { 
                    continue;
                }
                else {
                    if (!particles.Contains(p)) { 
                        particles.Add(p);
                    } 
                } 
            }
            return particles; 
        }
    }

    internal struct RangePositionInfo { 
        public BitSet curpos;
        public decimal[] rangeCounters; 
    } 

    sealed class RangeContentValidator : ContentValidator { 
        BitSet firstpos;
        BitSet[] followpos;
        BitSet positionsWithRangeTerminals;
        SymbolsDictionary symbols; 
        Positions positions;
        int minMaxNodesCount; 
        int endMarkerPos; 

        internal RangeContentValidator( 
            BitSet firstpos, BitSet[] followpos, SymbolsDictionary symbols, Positions positions, int endMarkerPos, XmlSchemaContentType contentType, bool isEmptiable, BitSet positionsWithRangeTerminals, int minmaxNodesCount)  : base(contentType, false, isEmptiable) {
            this.firstpos = firstpos;
            this.followpos = followpos;
            this.symbols = symbols; 
            this.positions = positions;
            this.positionsWithRangeTerminals = positionsWithRangeTerminals; 
            this.minMaxNodesCount = minmaxNodesCount; 
            this.endMarkerPos = endMarkerPos;
        } 

        public override void InitValidation(ValidationState context) {
            int positionsCount = positions.Count;
            List runningPositions = context.RunningPositions; 
            if (runningPositions != null) {
                Debug.Assert(minMaxNodesCount != 0); 
                runningPositions.Clear(); 
            }
            else { 
                runningPositions = new List();
                context.RunningPositions = runningPositions;
            }
            RangePositionInfo rposInfo = new RangePositionInfo(); 
            rposInfo.curpos = firstpos.Clone();
 
            rposInfo.rangeCounters = new decimal[minMaxNodesCount]; 
            runningPositions.Add(rposInfo);
            context.CurrentState.NumberOfRunningPos = 1; 
            context.HasMatched = rposInfo.curpos.Get(endMarkerPos);
        }

        public override object ValidateElement(XmlQualifiedName name, ValidationState context, out int errorCode) { 
            errorCode = 0;
            int symbol = symbols[name]; 
            bool hasSeenFinalPosition = false; 
            List runningPositions = context.RunningPositions;
            int matchCount = context.CurrentState.NumberOfRunningPos; 
            int k = 0;
            RangePositionInfo rposInfo;

            int pos = -1; 
            int firstMatchedIndex = -1;
            bool matched = false; 
 
#if RANGE_DEBUG
            WriteRunningPositions("Current running positions to match", runningPositions, name, matchCount); 
#endif

            while (k < matchCount) { //we are looking for the first match in the list of bitsets
                rposInfo = runningPositions[k]; 
                BitSet curpos = rposInfo.curpos;
                for (int matchpos = curpos.NextSet(-1); matchpos != -1; matchpos = curpos.NextSet(matchpos)) { //In all sets, have to scan all positions because of Disabled UPA possibility 
                    if (symbol == positions[matchpos].symbol) { 
                        pos = matchpos;
                        if (firstMatchedIndex == -1) { // get the first match for this symbol 
                            firstMatchedIndex = k;
                        }
                        matched = true;
                        break; 
                    }
                } 
                if (matched && positions[pos].particle is XmlSchemaElement) { //We found a match in the list, break at that bitset 
                    break;
                } 
                else {
                    k++;
                }
            } 

            if (k == matchCount && pos != -1) { // we did find a match but that was any and hence continued ahead for element 
                k = firstMatchedIndex; 
            }
            if (k < matchCount) { //There is a match 
                if (k != 0) { //If the first bitset itself matched, then no need to remove anything
#if RANGE_DEBUG
                    WriteRunningPositions("Removing unmatched entries till the first match", runningPositions, XmlQualifiedName.Empty, k);
#endif 
                    runningPositions.RemoveRange(0, k); //Delete entries from 0 to k-1
                } 
                matchCount = matchCount - k; 
                k = 0; // Since we re-sized the array
                while (k < matchCount) { 
                    rposInfo = runningPositions[k];
                    matched = rposInfo.curpos.Get(pos); //Look for the bitset that matches the same position as pos
                    if (matched) { //If match found, get the follow positions of the current matched position
#if RANGE_DEBUG 
                        Debug.WriteIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, "Matched position: " + pos + " "); SequenceNode.WriteBitSet(rposInfo.curpos);
                        Debug.WriteIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, "Follow pos of Matched position: "); SequenceNode.WriteBitSet(followpos[pos]); 
#endif 
                        rposInfo.curpos = followpos[pos]; //Note that we are copying the same counters of the current position to that of the follow position
                        runningPositions[k] = rposInfo; 
                        k++;
                    }
                    else { //Clear the current pos and get another position from the list to start matching
                        matchCount--; 
                        if (matchCount > 0) {
                            RangePositionInfo lastrpos = runningPositions[matchCount]; 
                            runningPositions[matchCount] = runningPositions[k]; 
                            runningPositions[k] = lastrpos;
                        } 
                    }
                }
            }
            else { //There is no match 
                matchCount = 0;
            } 
 
            if (matchCount > 0) {
                Debug.Assert(minMaxNodesCount > 0); 
                if (matchCount >= 10000) {
                    context.TooComplex = true;
                    matchCount /= 2;
                } 
#if RANGE_DEBUG
                WriteRunningPositions("Matched positions to expand ", runningPositions, name, matchCount); 
#endif 

                for (k = matchCount - 1; k >= 0; k--) { 
                    int j = k;
                    BitSet currentRunningPosition = runningPositions[k].curpos;
                    hasSeenFinalPosition = hasSeenFinalPosition || currentRunningPosition.Get(endMarkerPos); //Accepting position reached if the current position BitSet contains the endPosition
                    while (matchCount < 10000 && currentRunningPosition.Intersects(positionsWithRangeTerminals)) { 
                        //Now might add 2 more positions to followpos
                        //1. nextIteration of the rangeNode, which is firstpos of its parent's leftChild 
                        //2. Followpos of the range node 

                        BitSet countingPosition = currentRunningPosition.Clone(); 
                        countingPosition.And(positionsWithRangeTerminals);
                        int cPos = countingPosition.NextSet(-1); //Get the first position where leaf range node appears
                        LeafRangeNode lrNode = positions[cPos].particle as LeafRangeNode; //For a position with leaf range node, the particle is the node itself
                        Debug.Assert(lrNode != null); 

                        rposInfo = runningPositions[j]; 
                        if (matchCount + 2 >= runningPositions.Count) { 
                            runningPositions.Add(new RangePositionInfo());
                            runningPositions.Add(new RangePositionInfo()); 
                        }
                        RangePositionInfo newRPosInfo = runningPositions[matchCount];
                        if (newRPosInfo.rangeCounters == null) {
                            newRPosInfo.rangeCounters = new decimal[minMaxNodesCount]; 
                        }
                        Array.Copy(rposInfo.rangeCounters, 0, newRPosInfo.rangeCounters, 0, rposInfo.rangeCounters.Length); 
                        decimal count = ++newRPosInfo.rangeCounters[lrNode.Pos]; 

                        if (count == lrNode.Max) { 
                            newRPosInfo.curpos = followpos[cPos]; //since max has been reached, Get followposition of range node
                            newRPosInfo.rangeCounters[lrNode.Pos] = 0; //reset counter
                            runningPositions[matchCount] = newRPosInfo;
                            j = matchCount++; 
                        }
                        else if (count < lrNode.Min) { 
                            newRPosInfo.curpos = lrNode.NextIteration; 
                            runningPositions[matchCount] = newRPosInfo;
                            matchCount++; 
                            break;
                        }
                        else { // min <= count < max
                            newRPosInfo.curpos = lrNode.NextIteration; //set currentpos to firstpos of node which has the range 
                            runningPositions[matchCount] = newRPosInfo;
                            j = matchCount + 1; 
                            newRPosInfo = runningPositions[j]; 
                            if (newRPosInfo.rangeCounters == null) {
                                newRPosInfo.rangeCounters = new decimal[minMaxNodesCount]; 
                            }
                            Array.Copy(rposInfo.rangeCounters, 0, newRPosInfo.rangeCounters, 0, rposInfo.rangeCounters.Length);
                            newRPosInfo.curpos = followpos[cPos];
                            newRPosInfo.rangeCounters[lrNode.Pos] = 0; 
                            runningPositions[j] = newRPosInfo;
                            matchCount += 2; 
                        } 
                        currentRunningPosition = runningPositions[j].curpos;
                        hasSeenFinalPosition = hasSeenFinalPosition || currentRunningPosition.Get(endMarkerPos); 
                    }
                }
                context.HasMatched = hasSeenFinalPosition;
                context.CurrentState.NumberOfRunningPos = matchCount; 
                return positions[pos].particle;
            } //matchcount > 0 
            errorCode = -1; 
            context.NeedValidateChildren = false;
            return null; 
        }

#if RANGE_DEBUG
        private void WriteRunningPositions(string text, List runningPositions, XmlQualifiedName name, int length) { 
            int counter = 0;
            Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, ""); 
            Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, ""); 
            Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, text + name.Name);
            while (counter < length) { 
                BitSet curpos = runningPositions[counter].curpos;
                SequenceNode.WriteBitSet(curpos);
                for(int rcnt = 0; rcnt < runningPositions[counter].rangeCounters.Length; rcnt++) {
                    Debug.WriteIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, "RangeCounter[" + rcnt + "]" + runningPositions[counter].rangeCounters[rcnt] + " "); 
                }
                Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, ""); 
                Debug.WriteLineIf(DiagnosticsSwitches.XmlSchemaContentModel.Enabled, ""); 
                counter++;
            } 
        }
#endif
        public override bool CompleteValidation(ValidationState context) {
            return context.HasMatched; 
        }
 
        public override ArrayList ExpectedElements(ValidationState context, bool isRequiredOnly) { 
            ArrayList names = null;
            BitSet expectedPos; 
            if (context.RunningPositions != null) {
                List runningPositions = context.RunningPositions;
                expectedPos = new BitSet(positions.Count);
                for (int i = context.CurrentState.NumberOfRunningPos - 1; i >=0; i--) { 
                    Debug.Assert(runningPositions[i].curpos != null);
                    expectedPos.Or(runningPositions[i].curpos); 
                } 
                for (int pos = expectedPos.NextSet(-1); pos != -1; pos = expectedPos.NextSet(pos)) {
                    if (names == null) { 
                        names = new ArrayList();
                    }
                    int symbol = positions[pos].symbol;
                    if (symbol >= 0) { //non range nodes 
                        XmlSchemaParticle p = positions[pos].particle as XmlSchemaParticle;
                        if (p == null) { 
                            string s = symbols.NameOf(positions[pos].symbol); 
                            if (s.Length != 0) {
                                names.Add(s); 
                            }
                        }
                        else {
                            string s = p.NameString; 
                            if (!names.Contains(s)) {
                                names.Add(s); 
                            } 
                        }
                    } 
                }
            }
            return names;
        } 

        public override ArrayList ExpectedParticles(ValidationState context, bool isRequiredOnly) { 
            ArrayList particles = new ArrayList(); 
            BitSet expectedPos;
            if (context.RunningPositions != null) { 
                List runningPositions = context.RunningPositions;
                expectedPos = new BitSet(positions.Count);
                for (int i = context.CurrentState.NumberOfRunningPos - 1; i >=0; i--) {
                    Debug.Assert(runningPositions[i].curpos != null); 
                    expectedPos.Or(runningPositions[i].curpos);
                } 
                for (int pos = expectedPos.NextSet(-1); pos != -1; pos = expectedPos.NextSet(pos)) { 
                    int symbol = positions[pos].symbol;
                    if (symbol >= 0) { //non range nodes 
                        XmlSchemaParticle p = positions[pos].particle as XmlSchemaParticle;
                        if (p == null) {
                           continue;
                        } 
                        else if (!particles.Contains(p)) {
                           particles.Add(p); 
                        } 
                    }
                } 
            }
            return particles;
        }
    } 

    sealed class AllElementsContentValidator : ContentValidator { 
        Hashtable elements;     // unique terminal names to positions in Bitset mapping 
        object[] particles;
        BitSet isRequired;      // required flags 
        int countRequired = 0;

        public AllElementsContentValidator(XmlSchemaContentType contentType, int size, bool isEmptiable) : base(contentType, false, isEmptiable) {
            elements = new Hashtable(size); 
            particles = new object[size];
            isRequired = new BitSet(size); 
        } 

        public bool AddElement(XmlQualifiedName name, object particle, bool isEmptiable) { 
            if (elements[name] != null) {
                return false;
            }
            int i = elements.Count; 
            elements.Add(name, i);
            particles[i] = particle; 
            if (!isEmptiable) { 
                isRequired.Set(i);
                countRequired ++; 
            }
            return true;
        }
 
        public override bool IsEmptiable {
            get { return base.IsEmptiable || countRequired == 0; } 
        } 

        public override void InitValidation(ValidationState context) { 
            Debug.Assert(elements.Count > 0);
            context.AllElementsSet = new BitSet(elements.Count); //
            context.CurrentState.AllElementsRequired = -1; // no elements at all
        } 

        public override object ValidateElement(XmlQualifiedName name, ValidationState context, out int errorCode) { 
            object lookup = elements[name]; 
            errorCode = 0;
            if (lookup == null) { 
                context.NeedValidateChildren = false;
                return null;
            }
            int index = (int)lookup; 
            if (context.AllElementsSet[index]) {
                errorCode = -2; 
                return null; 
            }
            if (context.CurrentState.AllElementsRequired == -1) { 
                context.CurrentState.AllElementsRequired = 0;
            }
            context.AllElementsSet.Set(index);
            if (isRequired[index]) { 
                context.CurrentState.AllElementsRequired++;
            } 
            return particles[index]; 
        }
 
        public override bool CompleteValidation(ValidationState context) {
            if (context.CurrentState.AllElementsRequired == countRequired || IsEmptiable && context.CurrentState.AllElementsRequired == -1) {
                return true;
            } 
            return false;
        } 
 
        public override ArrayList ExpectedElements(ValidationState context, bool isRequiredOnly) {
            ArrayList names = null; 
            foreach (DictionaryEntry entry in elements) {
                if (!context.AllElementsSet[(int)entry.Value] && (!isRequiredOnly || isRequired[(int)entry.Value])) {
                    if (names == null) {
                        names = new ArrayList(); 
                    }
                    names.Add(entry.Key); 
                } 
            }
            return names; 
        }

        public override ArrayList ExpectedParticles(ValidationState context, bool isRequiredOnly) {
            ArrayList expectedParticles = new ArrayList(); 
            foreach (DictionaryEntry entry in elements) {
                if (!context.AllElementsSet[(int)entry.Value] && (!isRequiredOnly || isRequired[(int)entry.Value])) { 
                    expectedParticles.Add(this.particles[(int)entry.Value]); 
                }
            } 
            return expectedParticles;
        }
    }
    #endregion 
}

// File provided for Reference Use Only by Microsoft Corporation (c) 2007.

                        

Link Menu

Network programming in C#, Network Programming in VB.NET, Network Programming in .NET
This book is available now!
Buy at Amazon US or
Buy at Amazon UK