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 ConstructPos(BitSet firstpos, BitSet lastpos, BitSet[] followpos)
 {
     base.LeftChild.ConstructPos(firstpos, lastpos, followpos);
     for (int i = lastpos.NextSet(-1); i != -1; i = lastpos.NextSet(i))
     {
         followpos[i].Or(firstpos);
     }
 }

 public override void ConstructPos(BitSet firstpos, BitSet lastpos, BitSet[] followpos)
 {
     base.LeftChild.ConstructPos(firstpos, lastpos, followpos);
     BitSet set = new BitSet(firstpos.Count);
     BitSet set2 = new BitSet(lastpos.Count);
     base.RightChild.ConstructPos(set, set2, followpos);
     firstpos.Or(set);
     lastpos.Or(set2);
 }

        internal void Or(BitSet set) {
            if (this == set) {
                return;
            }

            int setLength = set._length;
            EnsureLength(setLength);
            for (int i = setLength; i-- > 0 ;) {
                _bits[i] |= set._bits[i];
            }
        }

 public void And(BitSet other)
 {
     if (this != other)
     {
         int length = this.bits.Length;
         int num2 = other.bits.Length;
         int index = (length > num2) ? num2 : length;
         int num4 = index;
         while (num4-- > 0)
         {
             this.bits[num4] &= other.bits[num4];
         }
         while (index < length)
         {
             this.bits[index] = 0;
             index++;
         }
     }
 }

        internal void And(BitSet set) {
            /*
             * Need to synchronize  both this and set->
             * This might lead to deadlock if one thread grabs them in one order
             * while another thread grabs them the other order.
             * Use a trick from Doug Lea's book on concurrency,
             * somewhat complicated because BitSet overrides hashCode().
             */
            if (this == set) {
                return;
            }

            int bitsLength = _length;
            int setLength = set._length;
            int n = (bitsLength > setLength) ? setLength : bitsLength;
            for (int i = n ; i-- > 0 ;) {
                _bits[i] &= set._bits[i];
            }
            for (; n < bitsLength ; n++) {
                _bits[n] = 0;
            }
        }

 public override void ConstructPos(BitSet firstpos, BitSet lastpos, BitSet[] followpos) {
     throw new InvalidOperationException();
 }

 private static void ConstructChildPos(SyntaxTreeNode child, BitSet firstpos, BitSet lastpos, BitSet[] followpos) {
     BitSet firstPosTemp = new BitSet(firstpos.Count);
     BitSet lastPosTemp = new BitSet(lastpos.Count);
     child.ConstructPos(firstPosTemp, lastPosTemp, followpos);
     firstpos.Or(firstPosTemp);
     lastpos.Or(lastPosTemp);
 }

        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]);
            }
        }

            public SequenceConstructPosContext(SequenceNode node, BitSet firstpos, BitSet lastpos) {
                this_ = node;
                this.firstpos = firstpos;
                this.lastpos = lastpos;

                lastposLeft = null;
                firstposRight = null;
            }

 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
     }
 }

 //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 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;
             }
         }
     }
 }

        /// <summary>
        /// Algorithm 3.5 Construction of a DFA from a regular expression
        /// </summary>
        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[]));
        }

 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 ? "+" : "");
         }
     }
 }

 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, "");
 }

 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 ArrayList ExpectedElements(ValidationState context, bool isRequiredOnly) {
     ArrayList names = null;
     BitSet expectedPos;
     if (context.RunningPositions != null) {
         List<RangePositionInfo> 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, XmlSchemaSet schemaSet) {
     ArrayList particles = new ArrayList();
     BitSet expectedPos;
     if (context.RunningPositions != null) {
         List<RangePositionInfo> 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;
                 }
                 AddParticleToExpected(p, schemaSet, particles);
             }
         }
     }
     return particles;
 }

 private bool IsSequenceFromAll(XmlSchemaSequence derivedSequence, XmlSchemaAll baseAll) {
     if (!IsValidOccurrenceRangeRestriction(derivedSequence, baseAll) || derivedSequence.Items.Count > baseAll.Items.Count) {
         return false;
     }
     BitSet map = new BitSet(baseAll.Items.Count);
     for (int j = 0; j < derivedSequence.Items.Count; ++j) {
         int i = GetMappingParticle((XmlSchemaParticle)derivedSequence.Items[j], baseAll.Items);
         if (i >= 0) {
             if (map[i]) {
                 return false;
             }
             else {
                 map.Set(i);
             }
         }
         else {
             return false;
         }
     }
     for (int i = 0; i < baseAll.Items.Count; i++) {
         if (!map[i] && !IsParticleEmptiable((XmlSchemaParticle)baseAll.Items[i])) {
             return false;
         }
     }
     return true;
 }