The Labs \ Source Viewer \ SSCLI \ System.Collections \ BitArray

  1. // ==++==
  2. //
  3. //
  4. // Copyright (c) 2006 Microsoft Corporation. All rights reserved.
  5. //
  6. // The use and distribution terms for this software are contained in the file
  7. // named license.txt, which can be found in the root of this distribution.
  8. // By using this software in any fashion, you are agreeing to be bound by the
  9. // terms of this license.
  10. //
  11. // You must not remove this notice, or any other, from this software.
  12. //
  13. //
  14. // ==--==
  15. /*=============================================================================
  16. **
  17. ** Class: BitArray
  18. **
  19. **
  20. ** Purpose: The BitArray class manages a compact array of bit values.
  21. **
  22. **
  23. =============================================================================*/
  24. namespace System.Collections
  25. {
  26.    
  27.     using System;
  28.     using System.Security.Permissions;
  29.     // A vector of bits. Use this to store bits efficiently, without having to do bit
  30.     // shifting yourself.
  31.     [System.Runtime.InteropServices.ComVisible(true)]
  32.     [Serializable()]
  33.     public sealed class BitArray : ICollection, ICloneable
  34.     {
  35.         private BitArray()
  36.         {
  37.         }
  38.        
  39. /*=========================================================================
  40.         ** Allocates space to hold length bit values. All of the values in the bit
  41.         ** array are set to false.
  42.         **
  43.         ** Exceptions: ArgumentException if length < 0.
  44.         =========================================================================*/       
  45.         public BitArray(int length) : this(length, false)
  46.         {
  47.         }
  48.        
  49. /*=========================================================================
  50.         ** Allocates space to hold length bit values. All of the values in the bit
  51.         ** array are set to defaultValue.
  52.         **
  53.         ** Exceptions: ArgumentOutOfRangeException if length < 0.
  54.         =========================================================================*/       
  55.         public BitArray(int length, bool defaultValue)
  56.         {
  57.             if (length < 0) {
  58.                 throw new ArgumentOutOfRangeException("length", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
  59.             }
  60.            
  61.             m_array = new int[(length + 31) / 32];
  62.             m_length = length;
  63.            
  64.             int fillValue = defaultValue ? unchecked(((int)4294967295u)) : 0;
  65.             for (int i = 0; i < m_array.Length; i++) {
  66.                 m_array[i] = fillValue;
  67.             }
  68.            
  69.             _version = 0;
  70.         }
  71.        
  72. /*=========================================================================
  73.         ** Allocates space to hold the bit values in bytes. bytes[0] represents
  74.         ** bits 0 - 7, bytes[1] represents bits 8 - 15, etc. The LSB of each byte
  75.         ** represents the lowest index value; bytes[0] & 1 represents bit 0,
  76.         ** bytes[0] & 2 represents bit 1, bytes[0] & 4 represents bit 2, etc.
  77.         **
  78.         ** Exceptions: ArgumentException if bytes == null.
  79.         =========================================================================*/       
  80.         public BitArray(byte[] bytes)
  81.         {
  82.             if (bytes == null) {
  83.                 throw new ArgumentNullException("bytes");
  84.             }
  85.            
  86.             m_array = new int[(bytes.Length + 3) / 4];
  87.             m_length = bytes.Length * 8;
  88.            
  89.             int i = 0;
  90.             int j = 0;
  91.             while (bytes.Length - j >= 4) {
  92.                 m_array[i++] = (bytes[j] & 255) | ((bytes[j + 1] & 255) << 8) | ((bytes[j + 2] & 255) << 16) | ((bytes[j + 3] & 255) << 24);
  93.                 j += 4;
  94.             }
  95.            
  96.             BCLDebug.Assert(bytes.Length - j >= 0, "BitArray byteLength problem");
  97.             BCLDebug.Assert(bytes.Length - j < 4, "BitArray byteLength problem #2");
  98.            
  99.             switch (bytes.Length - j) {
  100.                 case 3:
  101.                     m_array[i] = ((bytes[j + 2] & 255) << 16);
  102.                     goto case 2;
  103.                     break;
  104.                 case 2:
  105.                     // fall through
  106.                     m_array[i] |= ((bytes[j + 1] & 255) << 8);
  107.                     goto case 1;
  108.                     break;
  109.                 case 1:
  110.                     // fall through
  111.                     m_array[i] |= (bytes[j] & 255);
  112.                     break;
  113.             }
  114.            
  115.             _version = 0;
  116.         }
  117.        
  118.         public BitArray(bool[] values)
  119.         {
  120.             if (values == null) {
  121.                 throw new ArgumentNullException("values");
  122.             }
  123.            
  124.             m_array = new int[(values.Length + 31) / 32];
  125.             m_length = values.Length;
  126.            
  127.             for (int i = 0; i < values.Length; i++) {
  128.                 if (values[i])
  129.                     m_array[i / 32] |= (1 << (i % 32));
  130.             }
  131.            
  132.             _version = 0;
  133.            
  134.         }
  135.        
  136. /*=========================================================================
  137.         ** Allocates space to hold the bit values in values. values[0] represents
  138.         ** bits 0 - 31, values[1] represents bits 32 - 63, etc. The LSB of each
  139.         ** integer represents the lowest index value; values[0] & 1 represents bit
  140.         ** 0, values[0] & 2 represents bit 1, values[0] & 4 represents bit 2, etc.
  141.         **
  142.         ** Exceptions: ArgumentException if values == null.
  143.         =========================================================================*/       
  144.         public BitArray(int[] values)
  145.         {
  146.             if (values == null) {
  147.                 throw new ArgumentNullException("values");
  148.             }
  149.            
  150.             m_array = new int[values.Length];
  151.             m_length = values.Length * 32;
  152.            
  153.             Array.Copy(values, m_array, values.Length);
  154.            
  155.             _version = 0;
  156.         }
  157.        
  158. /*=========================================================================
  159.         ** Allocates a new BitArray with the same length and bit values as bits.
  160.         **
  161.         ** Exceptions: ArgumentException if bits == null.
  162.         =========================================================================*/       
  163.         public BitArray(BitArray bits)
  164.         {
  165.             if (bits == null) {
  166.                 throw new ArgumentNullException("bits");
  167.             }
  168.            
  169.             m_array = new int[(bits.m_length + 31) / 32];
  170.             m_length = bits.m_length;
  171.            
  172.             Array.Copy(bits.m_array, m_array, (bits.m_length + 31) / 32);
  173.            
  174.             _version = bits._version;
  175.         }
  176.        
  177.         public bool this[int index]
  178.         {
  179.             get { return Get(index); }
  180.             set { Set(index, value); }
  181.         }
  182.        
  183. /*=========================================================================
  184.         ** Returns the bit value at position index.
  185.         **
  186.         ** Exceptions: ArgumentOutOfRangeException if index < 0 or
  187.         **            index >= GetLength().
  188.         =========================================================================*/       
  189.         public bool Get(int index)
  190.         {
  191.             if (index < 0 || index >= m_length) {
  192.                 throw new ArgumentOutOfRangeException("index", Environment.GetResourceString("ArgumentOutOfRange_Index"));
  193.             }
  194.            
  195.             return (m_array[index / 32] & (1 << (index % 32))) != 0;
  196.         }
  197.        
  198. /*=========================================================================
  199.         ** Sets the bit value at position index to value.
  200.         **
  201.         ** Exceptions: ArgumentOutOfRangeException if index < 0 or
  202.         **            index >= GetLength().
  203.         =========================================================================*/       
  204.         public void Set(int index, bool value)
  205.         {
  206.             if (index < 0 || index >= m_length) {
  207.                 throw new ArgumentOutOfRangeException("index", Environment.GetResourceString("ArgumentOutOfRange_Index"));
  208.             }
  209.            
  210.             if (value) {
  211.                 m_array[index / 32] |= (1 << (index % 32));
  212.             }
  213.             else {
  214.                 m_array[index / 32] &= ~(1 << (index % 32));
  215.             }
  216.            
  217.             _version++;
  218.         }
  219.        
  220. /*=========================================================================
  221.         ** Sets all the bit values to value.
  222.         =========================================================================*/       
  223.         public void SetAll(bool value)
  224.         {
  225.             int fillValue = value ? unchecked(((int)4294967295u)) : 0;
  226.             int ints = (m_length + 31) / 32;
  227.             for (int i = 0; i < ints; i++) {
  228.                 m_array[i] = fillValue;
  229.             }
  230.            
  231.             _version++;
  232.         }
  233.        
  234. /*=========================================================================
  235.         ** Returns a reference to the current instance ANDed with value.
  236.         **
  237.         ** Exceptions: ArgumentException if value == null or
  238.         **            value.Length != this.Length.
  239.         =========================================================================*/       
  240.         public BitArray And(BitArray value)
  241.         {
  242.             if (value == null)
  243.                 throw new ArgumentNullException("value");
  244.             if (m_length != value.m_length)
  245.                 throw new ArgumentException(Environment.GetResourceString("Arg_ArrayLengthsDiffer"));
  246.            
  247.             int ints = (m_length + 31) / 32;
  248.             for (int i = 0; i < ints; i++) {
  249.                 m_array[i] &= value.m_array[i];
  250.             }
  251.            
  252.             _version++;
  253.             return this;
  254.         }
  255.        
  256. /*=========================================================================
  257.         ** Returns a reference to the current instance ORed with value.
  258.         **
  259.         ** Exceptions: ArgumentException if value == null or
  260.         **            value.Length != this.Length.
  261.         =========================================================================*/       
  262.         public BitArray Or(BitArray value)
  263.         {
  264.             if (value == null)
  265.                 throw new ArgumentNullException("value");
  266.             if (m_length != value.m_length)
  267.                 throw new ArgumentException(Environment.GetResourceString("Arg_ArrayLengthsDiffer"));
  268.            
  269.             int ints = (m_length + 31) / 32;
  270.             for (int i = 0; i < ints; i++) {
  271.                 m_array[i] |= value.m_array[i];
  272.             }
  273.            
  274.             _version++;
  275.             return this;
  276.         }
  277.        
  278. /*=========================================================================
  279.         ** Returns a reference to the current instance XORed with value.
  280.         **
  281.         ** Exceptions: ArgumentException if value == null or
  282.         **            value.Length != this.Length.
  283.         =========================================================================*/       
  284.         public BitArray Xor(BitArray value)
  285.         {
  286.             if (value == null)
  287.                 throw new ArgumentNullException("value");
  288.             if (m_length != value.m_length)
  289.                 throw new ArgumentException(Environment.GetResourceString("Arg_ArrayLengthsDiffer"));
  290.            
  291.             int ints = (m_length + 31) / 32;
  292.             for (int i = 0; i < ints; i++) {
  293.                 m_array[i] ^= value.m_array[i];
  294.             }
  295.            
  296.             _version++;
  297.             return this;
  298.         }
  299.        
  300. /*=========================================================================
  301.         ** Inverts all the bit values. On/true bit values are converted to
  302.         ** off/false. Off/false bit values are turned on/true. The current instance
  303.         ** is updated and returned.
  304.         =========================================================================*/       
  305.         public BitArray Not()
  306.         {
  307.             int ints = (m_length + 31) / 32;
  308.             for (int i = 0; i < ints; i++) {
  309.                 m_array[i] = ~m_array[i];
  310.             }
  311.            
  312.             _version++;
  313.             return this;
  314.         }
  315.        
  316.        
  317.         public int Length {
  318.             get { return m_length; }
  319.             set {
  320.                 if (value < 0) {
  321.                     throw new ArgumentOutOfRangeException("value", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
  322.                 }
  323.                
  324.                 int newints = (value + 31) / 32;
  325.                 if (newints > m_array.Length || newints + _ShrinkThreshold < m_array.Length) {
  326.                     // grow or shrink (if wasting more than _ShrinkThreshold ints)
  327.                     int[] newarray = new int[newints];
  328.                     Array.Copy(m_array, newarray, newints > m_array.Length ? m_array.Length : newints);
  329.                     m_array = newarray;
  330.                 }
  331.                
  332.                 if (value > m_length) {
  333.                     // clear high bit values in the last int
  334.                     int last = ((m_length + 31) / 32) - 1;
  335.                     int bits = m_length % 32;
  336.                     if (bits > 0) {
  337.                         m_array[last] &= (1 << bits) - 1;
  338.                     }
  339.                    
  340.                     // clear remaining int values
  341.                     Array.Clear(m_array, last + 1, newints - last - 1);
  342.                 }
  343.                
  344.                 m_length = value;
  345.                 _version++;
  346.             }
  347.         }
  348.        
  349.         // ICollection implementation
  350.         public void CopyTo(Array array, int index)
  351.         {
  352.             if (array == null)
  353.                 throw new ArgumentNullException("array");
  354.            
  355.             if (index < 0)
  356.                 throw new ArgumentOutOfRangeException("index", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
  357.            
  358.             if (array.Rank != 1)
  359.                 throw new ArgumentException(Environment.GetResourceString("Arg_RankMultiDimNotSupported"));
  360.            
  361.            
  362.             if (array is int[]) {
  363.                 Array.Copy(m_array, 0, array, index, (m_length + 31) / 32);
  364.             }
  365.             else if (array is byte[]) {
  366.                 if ((array.Length - index) < (m_length + 7) / 8)
  367.                     throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen"));
  368.                
  369.                 byte[] b = (byte[])array;
  370.                 for (int i = 0; i < (m_length + 7) / 8; i++)
  371.                     b[index + i] = (byte)((m_array[i / 4] >> ((i % 4) * 8)) & 255);
  372.                 // Shift to bring the required byte to LSB, then mask
  373.             }
  374.             else if (array is bool[]) {
  375.                 if (array.Length - index < m_length)
  376.                     throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen"));
  377.                
  378.                 bool[] b = (bool[])array;
  379.                 for (int i = 0; i < m_length; i++)
  380.                     b[index + i] = ((m_array[i / 32] >> (i % 32)) & 1) != 0;
  381.             }
  382.             else
  383.                 throw new ArgumentException(Environment.GetResourceString("Arg_BitArrayTypeUnsupported"));
  384.         }
  385.        
  386.         public int Count {
  387.             get { return m_length; }
  388.         }
  389.        
  390.         public object Clone()
  391.         {
  392.             BitArray bitArray = new BitArray(m_array);
  393.             bitArray._version = _version;
  394.             bitArray.m_length = m_length;
  395.             return bitArray;
  396.         }
  397.        
  398.         public object SyncRoot {
  399.             get {
  400.                 if (_syncRoot == null) {
  401.                     System.Threading.Interlocked.CompareExchange(ref _syncRoot, new object(), null);
  402.                 }
  403.                 return _syncRoot;
  404.             }
  405.         }
  406.        
  407.         public bool IsReadOnly {
  408.             get { return false; }
  409.         }
  410.        
  411.        
  412.         public bool IsSynchronized {
  413.             get { return false; }
  414.         }
  415.        
  416.         public IEnumerator GetEnumerator()
  417.         {
  418.             return new BitArrayEnumeratorSimple(this);
  419.         }
  420.        
  421.         [Serializable()]
  422.         private class BitArrayEnumeratorSimple : IEnumerator, ICloneable
  423.         {
  424.             private BitArray bitarray;
  425.             private int index;
  426.             private int version;
  427.             private bool currentElement;
  428.            
  429.             internal BitArrayEnumeratorSimple(BitArray bitarray)
  430.             {
  431.                 this.bitarray = bitarray;
  432.                 this.index = -1;
  433.                 version = bitarray._version;
  434.             }
  435.            
  436.             public object Clone()
  437.             {
  438.                 return MemberwiseClone();
  439.             }
  440.            
  441.             public virtual bool MoveNext()
  442.             {
  443.                 if (version != bitarray._version)
  444.                     throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumFailedVersion));
  445.                 if (index < (bitarray.Count - 1)) {
  446.                     index++;
  447.                     currentElement = bitarray.Get(index);
  448.                     return true;
  449.                 }
  450.                 else
  451.                     index = bitarray.Count;
  452.                
  453.                 return false;
  454.             }
  455.            
  456.             public virtual object Current {
  457.                 get {
  458.                     if (index == -1)
  459.                         throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumNotStarted));
  460.                     if (index >= bitarray.Count)
  461.                         throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumEnded));
  462.                     return currentElement;
  463.                 }
  464.             }
  465.            
  466.             public void Reset()
  467.             {
  468.                 if (version != bitarray._version)
  469.                     throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumFailedVersion));
  470.                 index = -1;
  471.             }
  472.         }
  473.        
  474.         private int[] m_array;
  475.         private int m_length;
  476.         private int _version;
  477.         [NonSerialized()]
  478.         private object _syncRoot;
  479.        
  480.         private const int _ShrinkThreshold = 256;
  481.     }
  482.    
  483. }

Developer Fusion