Util/SmallIntArray.cs

   1 //
   2 // Logger.cs
   3 //
   4 // Copyright (C) 2005 Novell, Inc.
   5 //
   6
   7 //
   8 // Permission is hereby granted, free of charge, to any person obtaining a copy
   9 // of this software and associated documentation files (the "Software"), to deal
  10 // in the Software without restriction, including without limitation the rights
  11 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  12 // copies of the Software, and to permit persons to whom the Software is
  13 // furnished to do so, subject to the following conditions:
  14 //
  15 // The above copyright notice and this permission notice shall be included in all
  16 // copies or substantial portions of the Software.
  17 //
  18 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  19 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  20 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  21 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  22 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  23 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  24 // SOFTWARE.
  25 //
  26
  27 using System;
  28 using System.Collections;
  29
  30 namespace Beagle.Util {
  31
  32         public class SmallIntArray {
  33
  34                 private int length;
  35                 private int bits_per_int;
  36                 private int max_int;
  37                 private BetterBitArray bit_array;
  38
  39                 public SmallIntArray (int length, int max_int)
  40                 {
  41                         this.length = length;
  42                         this.max_int = max_int;
  43
  44                         this.bits_per_int = 0;
  45                         while (max_int != 0) {
  46                                 ++bits_per_int;
  47                                 max_int = max_int >> 1;
  48                         }
  49
  50                         this.bit_array = new BetterBitArray (this.length * this.bits_per_int);
  51                 }
  52
  53                 public int this [int index] {
  54                         get { return Get (index); }
  55                         set { Set (index, value); }
  56                 }
  57
  58                 public int Length {
  59                         get { return length; }
  60                 }
  61
  62                 public int Count {
  63                         get { return length; }
  64                 }
  65
  66                 public int MaxInteger {
  67                         get { return max_int; }
  68                 }
  69
  70                 public int Get (int index)
  71                 {
  72                         int value, i, j;
  73                         value = 0;
  74                         i = index * bits_per_int;
  75                         for (j = 0; j < bits_per_int; ++j) {
  76                                 if (j != 0)
  77                                         value <<= 1;
  78                                 if (bit_array.Get (i+j))
  79                                         value |= 1;
  80                         }
  81                         return value;
  82
  83                 }
  84
  85                 public void Set (int index, int value)
  86                 {
  87                         if (value < 0 || value > max_int)
  88                                 throw new ArgumentException ("invalid value");
  89                         int i, j;
  90                         i = (index + 1) * bits_per_int - 1;
  91                         for (j = 0; j < bits_per_int; ++j) {
  92                                 bit_array.Set (i-j, (value & 1) == 1);
  93                                 value = value >> 1;
  94                         }
  95                 }
  96
  97                 public void SetAll (int value)
  98                 {
  99                         if (value == 0) {
 100                                 bit_array.SetAll (false);
 101                                 return;
 102                         }
 103
 104                         // This is not particularly efficient
 105                         for (int i = 0; i < length; ++i)
 106                                 Set (i, value);
 107                 }
 108
 109                 public void Incr (BetterBitArray bit_array)
 110                 {
 111                         if (bit_array.Length != length)
 112                                 throw new Exception ("Incr BetterBitArray has wrong length!");
 113
 114                         int i = 0;
 115                         while (i < length) {
 116                                 i = bit_array.GetNextTrueIndex (i);
 117                                 if (i >= length)
 118                                         break;
 119                                 Set (i, Get (i) + 1);
 120                                 ++i;
 121                         }
 122                 }
 123
 124                 public bool ContainsNonZero ()
 125                 {
 126                         return bit_array.ContainsTrue ();
 127                 }
 128
 129                 public int GetNextNonZeroIndex (int start)
 130                 {
 131                         if (start >= length)
 132                                 return length;
 133                         if (start < 0)
 134                                 start = 0;
 135                         return bit_array.GetNextTrueIndex (start * bits_per_int) / bits_per_int;
 136                 }
 137         }
 138 }