public PerfectDominatingSet(int n)
     : base(n)
 {
     Sigma = new BitSet(0, MaxSize);
     Sigma = !Sigma;
     Rho = new BitSet(0, MaxSize, new int[] { 1 });
 }

        public static Tree Expand(Tree tree, BitSet parent, int node)
        {
            Tree newTree = new Tree();

            Queue<BitSet> queue = new Queue<BitSet>();
            queue.Enqueue(tree.Root);

            while (queue.Count > 0)
            {
                BitSet set = queue.Dequeue();
                BitSet child;
                if (tree.LeftChild.TryGetValue(set, out child))
                {
                    queue.Enqueue(child);
                }
                if (tree.RightChild.TryGetValue(set, out child))
                {
                    queue.Enqueue(child);
                }
                if (parent.IsSubsetOf(set))
                {
                    set += node;
                }

                newTree.Insert(set);
            }

            newTree.Insert(parent);
            newTree.Insert(newTree.Root * node);

            return newTree;
        }

 public IndependentSet(int n)
     : base(n)
 {
     Sigma = new BitSet(0, MaxSize, new int[] { 0 });
     Rho = new BitSet(0, MaxSize);
     Rho = !Rho;
 }

 public InducedMatching(int n)
     : base(n)
 {
     Sigma = new BitSet(0, MaxSize, new int[] { 1 });
     Rho = new BitSet(0, MaxSize);
     Rho = !Rho;
 }

		static CharSet()
		{
			CharSet.lowerLetters = new BitSet();
			CharSet.upperLetters = new BitSet();
			CharSet.letters = new BitSet();
			for (int i = 0; i <= 65535; i++)
			{
				switch (char.GetUnicodeCategory((char)i))
				{
				case UnicodeCategory.UppercaseLetter:
					CharSet.upperLetters.Set(i, true);
					CharSet.letters.Set(i, true);
					break;
				case UnicodeCategory.LowercaseLetter:
					CharSet.lowerLetters.Set(i, true);
					CharSet.letters.Set(i, true);
					break;
				case UnicodeCategory.TitlecaseLetter:
				case UnicodeCategory.ModifierLetter:
				case UnicodeCategory.OtherLetter:
					CharSet.letters.Set(i, true);
					break;
				}
			}
		}

        // Uses depth-first search to check if the graph induced by the subgraph given as a parameter is connected
        // In other words, we retreive all edges from the original graph and check the subgraph for connectedness
        public static bool Connected(Datastructures.Graph graph, BitSet subgraph)
        {
            // Vertices that are visited
            Set<int> visited = new Set<int>();

            // Stack of vertices yet to visit
            Stack<int> stack = new Stack<int>();

            // Initial vertex
            int s = subgraph.First();
            stack.Push(s);

            // Continue while there are vertices on the stack
            while (stack.Count > 0)
            {
                int v = stack.Pop();

                // If we have not encountered this vertex before, then we check for all neighbors if they are part of the subgraph
                // If a neighbor is part of the subgraph it means that we have to push it on the stack to explore it at a later stage
                if (!visited.Contains(v))
                {
                    visited.Add(v);

                    foreach (int w in graph.OpenNeighborhood(v))
                        if (subgraph.Contains(w))
                            stack.Push(w);
                }
            }

            // If we visited an equal number of vertices as there are vertices in the subgraph then the subgraph is connected
            return visited.Count == subgraph.Count;
        }

		private static void ProcessStates(BitSet bset, Nfa current)
		{
			foreach (int current2 in bset)
			{
				List<Nfa> list = MakeNfa.spec.state_rules[current2];
				list.Add(current);
			}
		}

        // Basic constructor for a dNeighborhood
        public DNeighborhood(BitSet vector)
        {
            _occurrences = new Dictionary<int, int>();
            Vector = vector;

            foreach (int v in Vector)
                _occurrences[v] = 0;
        }

 public DominatingSet(int n)
     : base(n)
 {
     Sigma = new BitSet(0, MaxSize);
     Sigma = !Sigma;
     Rho = new BitSet(0, MaxSize, new int[] { 0 });
     Rho = !Rho;
 }

 public GhostObject()
 {
     Guid = new TFID();
     WaitingForParent = true;
     UpdatePriorityScalar = 0.1f;
     NetFlags = new BitSet();
     NetFlags.Set((UInt32) NetFlag.Ghostable);
 }

		public void CreateBitSet()
		{
			BitSet b = new BitSet(32);
			b[0] = true;
			b[1] = false;
			Assert.IsTrue(b[0]);
			Assert.IsTrue(!b[1]);
		}

 protected virtual void Condense(float[] floats)
 {
     if (floats.Length != _capacity)
     {
         throw new ArgumentException("bad input float array of length " + floats.Length + " for capacity: " + _capacity);
     }
     var bits = new BitSet(floats.Length);
     int on = 0;
     for (int i = 0; i < floats.Length; i++)
     {
         if (floats[i] != 0f)
         {
             bits.Set(i);
             on++;
         }
     }
     if (((float)on) / ((float)floats.Length) < ON_RATIO_CUTOFF)
     {
         // it's worth compressing
         if (0 == on)
         {
             // it's worth super-compressing
             _floats = null;
             _bits = null;
             _referencePoints = null;
             // capacity is good.
         }
         else
         {
             _bits = bits;
             _floats = new float[_bits.Cardinality()];
             _referencePoints = new int[floats.Length / REFERENCE_POINT_EVERY];
             int i = 0;
             int floatsIdx = 0;
             int refIdx = 0;
             while (i < floats.Length && (i = _bits.NextSetBit(i)) >= 0)
             {
                 _floats[floatsIdx] = floats[i];
                 while (refIdx < i / REFERENCE_POINT_EVERY)
                 {
                     _referencePoints[refIdx++] = floatsIdx;
                 }
                 floatsIdx++;
                 i++;
             }
             while (refIdx < _referencePoints.Length)
             {
                 _referencePoints[refIdx++] = floatsIdx;
             }
         }
     }
     else
     {
         // it's not worth compressing
         _floats = floats;
         _bits = null;
     }
 }

    static Dictionary<string,int> LoadNameIndex(BitAccess bits, out int age, out Guid guid) {
      Dictionary<string, int> result = new Dictionary<string, int>();
      int ver;
      int sig;
      bits.ReadInt32(out ver);    //  0..3  Version
      bits.ReadInt32(out sig);    //  4..7  Signature
      bits.ReadInt32(out age);    //  8..11 Age
      bits.ReadGuid(out guid);       // 12..27 GUID

      if (ver != 20000404) {
        throw new PdbDebugException("Unsupported PDB Stream version {0}", ver);
      }

      // Read string buffer.
      int buf;
      bits.ReadInt32(out buf);    // 28..31 Bytes of Strings

      int beg = bits.Position;
      int nxt = bits.Position + buf;

      bits.Position = nxt;

      // Read map index.
      int cnt;        // n+0..3 hash size.
      int max;        // n+4..7 maximum ni.

      bits.ReadInt32(out cnt);
      bits.ReadInt32(out max);

      BitSet present = new BitSet(bits);
      BitSet deleted = new BitSet(bits);
      if (!deleted.IsEmpty) {
        throw new PdbDebugException("Unsupported PDB deleted bitset is not empty.");
      }

      int j = 0;
      for (int i = 0; i < max; i++) {
        if (present.IsSet(i)) {
          int ns;
          int ni;
          bits.ReadInt32(out ns);
          bits.ReadInt32(out ni);

          string name;
          int saved = bits.Position;
          bits.Position = beg + ns;
          bits.ReadCString(out name);
          bits.Position = saved;

          result.Add(name, ni);
          j++;
        }
      }
      if (j != cnt) {
        throw new PdbDebugException("Count mismatch. ({0} != {1})", j, cnt);
      }
      return result;
    }

        public BinaryReal(BitSet bits, int numberOfBits, double lowerBound, double upperBound)
            : base(numberOfBits)
        {
            Bits = bits.Clone() as BitSet;
            LowerBound = lowerBound;
            UpperBound = upperBound;

            Decode();
        }

        private static UNSequence ComputeSequence(Datastructures.Graph graph, BitSet connectedComponent, CandidateStrategy candidateStrategy, int init, ref int max)
        {
            int n = graph.Size;
            List<int> sequence = new List<int>() { init };
            BitSet left = new BitSet(0, n, new int[] { init });
            BitSet right = connectedComponent - init;

            // Initially we store the empty set and the set with init as the representative, ie N(init) * right
            Set<BitSet> unLeft = new Set<BitSet>() { new BitSet(0, n), graph.OpenNeighborhood(init) * right };
            int value = int.MinValue;
            while (!right.IsEmpty)
            {
                Set<BitSet> unChosen = new Set<BitSet>();
                int chosen = Heuristics.TrivialCases(graph, left, right);

                if (chosen != -1)
                {
                    unChosen = IncrementUn(graph, left, unLeft, chosen);
                }
                // If chosen has not been set it means that no trivial case was found
                // Depending on the criteria for the next vertex we call a different algorithm
                else
                {
                    BitSet candidates = Heuristics.Candidates(graph, left, right, candidateStrategy);

                    int min = int.MaxValue;

                    foreach (int v in candidates)
                    {
                        Set<BitSet> unV = IncrementUn(graph, left, unLeft, v);
                        if (unV.Count < min)
                        {
                            chosen = v;
                            unChosen = unV;
                            min = unV.Count;
                        }
                    }
                }

                // This should never happen
                if (chosen == -1)
                    throw new Exception("No vertex is chosen for next step in the heuristic");

                // Add/remove the next vertex in the appropiate sets
                sequence.Add(chosen);
                left += chosen;
                right -= chosen;
                unLeft = unChosen;
                value = Math.Max(unChosen.Count, value);
                if (value > max)
                {
                    return new UNSequence() { Sequence = null, Value = int.MaxValue };
                }
            }

            return new UNSequence() { Sequence = sequence, Value = value };
        }

        // Counts the number of independent sets in a graph, such that:
        // - The vertices in P are legal choices for our IS, initially set to all vertices in the graph
        // - None of the vertices in X are used, initially empty
        // The performDFS boolean is used to check if we should perform a check for connectedness on this level of the recursion
        private static long Compute(Graph graph, BitSet p, BitSet x, bool performDfs)
        {
            // Base case, when P and X are both empty we cannot expand the IS
            if (p.IsEmpty && x.IsEmpty)
                return 1;

            // Base case, if a vertex w in X has no neighbor in P, then it means that this IS will never get maximal
            // since we could always include w. Thus, the IS will not be valid and we return 0.
            foreach (int w in x)
                if ((graph.OpenNeighborhood(w) * p).IsEmpty)
                    return 0;

            long count = 0;

            // If a DFS is needed we check if the graph induced by (P + X) is still connected.
            // If the graph is disconnected, in components c1,...,cn then we can simply count the IS of all these components
            // after which we simply multiply these numbers.
            if (performDfs)
            {
                if (!DepthFirstSearch.Connected(graph, p + x))
                {
                    count = 1;

                    foreach (BitSet component in DepthFirstSearch.ConnectedComponents(graph, p + x))
                        count *= Compute(graph, component * p, component * x, false);

                    return count;
                }
            }

            // Select a pivot in P to branch on
            // In this case we pick the vertex with the largest degree
            int maxDegree = -1; ;
            int pivot = -1;
            foreach (int u in p)
            {
                int deg = graph.Degree(u);
                if (deg > maxDegree)
                {
                    maxDegree = deg;
                    pivot = u;
                }
            }

            // There should always be a pivot after the selection procedure
            if (pivot == -1)
                throw new Exception("Pivot has not been selected");

            // We branch on the pivot, one branch we include the pivot in the IS.
            // This might possibly disconnect the subgraph G(P + X), thus we set the performDFS boolean to true.
            count = Compute(graph, p - graph.ClosedNeighborhood(pivot), x - graph.OpenNeighborhood(pivot), true);

            // One branch we exclude the pivot of the IS. This will not cause the graph to get possibly disconnected
            count += Compute(graph, p - pivot, x + pivot, false);

            return count;
        }

 public void BitSetEmpty()
 {
     BitSet a = new BitSet(8);
     Assert.IsTrue(a.IsEmpty);
     BitSet b = new BitSet(8);
     b[7] = true;
     Assert.IsTrue(!b.IsEmpty);
     b[7] = false;
     Assert.IsTrue(b.IsEmpty);
 }

        public void BitSetAllEnumerate()
        {
            using (FileUnitTester fut = new FileUnitTester("Core/BitSetAll.txt"))
            {
                BitSet a = new BitSet(8);
                a.SetAll(true);
                EnumerateBitsetBackwards(a, fut.TextWriter);
                fut.AssertFilesEqual();

            }
        }

 public void BitSetAll()
 {
     BitSet a = new BitSet(8);
     a.SetAll(true);
     string sExp = "11111111";
     string s = a.ToString();
     Assert.AreEqual(sExp, s);
     a.SetAll(false);
     sExp = "00000000";
     s = a.ToString();
     Assert.AreEqual(sExp, s);
 }

		public void BitSetToString()
		{
			BitSet b = new BitSet(8);
			b[0] = true;
			b[1] = false;
			b[2] = true;
			b[7] = true;
			b[31] = true;
			string sExp = "10100001";
			string s = b.ToString();
			Assert.AreEqual(sExp, s);
		}