code_ruby/lib/maasha/bitmap.rb

   1 # Copyright (C) 2012 Martin A. Hansen.
   2
   3 # This program is free software; you can redistribute it and/or
   4 # modify it under the terms of the GNU General Public License
   5 # as published by the Free Software Foundation; either version 2
   6 # of the License, or (at your option) any later version.
   7
   8 # This program is distributed in the hope that it will be useful,
   9 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  10 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11 # GNU General Public License for more details.
  12
  13 # You should have received a copy of the GNU General Public License
  14 # along with this program; if not, write to the Free Software
  15 # Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  16
  17 # http://www.gnu.org/copyleft/gpl.html
  18
  19 # >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
  20
  21 # This software is part of the Biopieces framework (www.biopieces.org).
  22
  23 # >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
  24
  25 require 'inline'
  26
  27 # Error class for all exceptions to do with Base36.
  28 class BitMapError < StandardError; end
  29
  30 BitsInChar = 8
  31
  32 class BitMap
  33   attr_accessor :byte_array
  34
  35   def initialize(rows, cols, byte_array = nil)
  36     @rows            = rows
  37     @cols            = cols
  38     @size            = rows * cols
  39
  40     if byte_array.nil?
  41       @byte_array_size = (rows * cols.to_f / BitsInChar).ceil
  42       @byte_array      = "\0" * @byte_array_size
  43     else
  44       @byte_array_size = (rows * cols.to_f / BitsInChar).ceil
  45       @byte_array      = byte_array
  46     end
  47   end
  48
  49   def slice(rows, cols)
  50     rows = rows.first.to_a if rows.first.respond_to? :to_a
  51     cols = cols.first.to_a if cols.first.respond_to? :to_a
  52
  53     new_byte_array_size = (rows.size * cols.size.to_f / BitsInChar).ceil
  54     new_byte_array      = "\0" * new_byte_array_size
  55
  56     slice_c(new_byte_array, rows, cols)
  57
  58     BitMap.new(rows.size, cols.size, new_byte_array)
  59   end
  60
  61   def flip!
  62     @rows, @cols = @cols, @rows
  63   end
  64
  65   # Method to convert a bit array to a string.
  66   def to_s
  67     string = ""
  68
  69     (0 ... @size).each do |pos|
  70       if self.bit_set? pos
  71         string << "1"
  72       else
  73         string << "0"
  74       end
  75     end
  76
  77     string.gsub(/.{#{@cols}}/, "\\0#{$/}")
  78   end
  79
  80   inline do |builder|
  81     builder.add_static "rows",            'rb_intern("@rows")',            "ID"
  82     builder.add_static "cols",            'rb_intern("@cols")',            "ID"
  83     builder.add_static "size",            'rb_intern("@size")',            "ID"
  84     builder.add_static "byte_array_size", 'rb_intern("@byte_array_size")', "ID"
  85     builder.add_static "byte_array",      'rb_intern("@byte_array")',      "ID"
  86
  87     builder.prefix %s{
  88       unsigned char bit_count[256] = {
  89         0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
  90         1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  91         1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  92         2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  93         1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  94         2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  95         2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  96         3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  97         1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  98         2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  99         2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 100         3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
 101         2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 102         3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
 103         3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
 104         4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
 105       };
 106     }
 107
 108     builder.prefix %{
 109       #define COUNT_BITS(c) (bit_count[c])
 110     }
 111
 112     builder.prefix %{
 113       #define BYTE_POS(pos) (pos / CHAR_BIT)
 114     }
 115
 116     builder.prefix %{
 117       #define BIT_POS(pos) (1 << (CHAR_BIT - 1 - (pos % CHAR_BIT)))
 118     }
 119
 120     builder.c %{
 121       void fill_c()
 122       {
 123         VALUE          _size       = rb_ivar_get(self, byte_array_size);
 124         VALUE          _byte_array = rb_ivar_get(self, byte_array);
 125         int            size        = NUM2INT(_size);
 126         unsigned char* byte_array  = StringValuePtr(_byte_array);
 127         int            i           = 0;
 128
 129         for (i = 0; i < size; i++) byte_array[i] = ~0;
 130       }
 131     }
 132
 133     builder.c %{
 134       void empty_c()
 135       {
 136         VALUE          _size       = rb_ivar_get(self, byte_array_size);
 137         VALUE          _byte_array = rb_ivar_get(self, byte_array);
 138         int            size        = NUM2INT(_size);
 139         unsigned char* byte_array  = StringValuePtr(_byte_array);
 140         int            i           = 0;
 141
 142         for (i = 0; i < size; i++) byte_array[i] = 0;
 143       }
 144     }
 145
 146     builder.c %{
 147       void bit_set_c(int row, int col)
 148       {
 149         VALUE          _rows       = rb_ivar_get(self, rows);
 150         VALUE          _cols       = rb_ivar_get(self, cols);
 151         VALUE          _byte_array = rb_ivar_get(self, byte_array);
 152         int            rows        = NUM2INT(_rows);
 153         int            cols        = NUM2INT(_cols);
 154         unsigned char* byte_array  = StringValuePtr(_byte_array);
 155         int            pos         = 0;
 156
 157         if (row >= rows)
 158           rb_raise(rb_eval_string("BitMapError"), "row out of range: %d >= %d\\n", row, rows);
 159
 160         if (col >= cols)
 161           rb_raise(rb_eval_string("BitMapError"), "col out of range: %d >= %d\\n", col, cols);
 162
 163         pos = row * cols + col;
 164
 165         byte_array[BYTE_POS(pos)] |= BIT_POS(pos);
 166       }
 167     }
 168
 169     builder.c %{
 170       VALUE bit_test_c(int pos)
 171       {
 172         VALUE          _byte_array = rb_ivar_get(self, byte_array);
 173         unsigned char* byte_array  = StringValuePtr(_byte_array);
 174
 175         return ((byte_array[BYTE_POS(pos)] & BIT_POS(pos)) != 0);
 176       }
 177     }
 178
 179     builder.c %{
 180       void slice_c(char* new_array, VALUE _new_rows, VALUE _new_cols)
 181       {
 182         VALUE          _old_array  = rb_ivar_get(self, byte_array);
 183         VALUE          _old_rows   = rb_ivar_get(self, rows);
 184         VALUE          _old_cols   = rb_ivar_get(self, cols);
 185         unsigned char* old_array   = StringValuePtr(_old_array);
 186         int            old_rows    = NUM2INT(_old_rows);
 187         int            old_cols    = NUM2INT(_old_cols);
 188
 189         VALUE          *rows_array = RARRAY_PTR(_new_rows);
 190         VALUE          *cols_array = RARRAY_PTR(_new_cols);
 191         int            row_count   = (int) RARRAY_LEN(_new_rows);
 192         int            col_count   = (int) RARRAY_LEN(_new_cols);
 193         int            r           = 0;
 194         int            c           = 0;
 195         int            old_pos     = 0;
 196         int            new_pos     = 0;
 197
 198         for (r = 0; r < row_count; r++)
 199         {
 200           for (c = 0; c < col_count; c++)
 201           {
 202             old_pos = NUM2INT(rows_array[r]) * old_cols + NUM2INT(cols_array[c]);
 203             new_pos = r * col_count + c;
 204
 205             new_array[BYTE_POS(new_pos)] |= BIT_POS(new_pos) & (old_array[BYTE_POS(old_pos)] & BIT_POS(old_pos));
 206           }
 207         }
 208       }
 209     }
 210
 211     builder.c %{
 212       VALUE sum_c()
 213       {
 214         VALUE          _size       = rb_ivar_get(self, byte_array_size);
 215         VALUE          _byte_array = rb_ivar_get(self, byte_array);
 216         int            size        = NUM2INT(_size);
 217         unsigned char* byte_array  = StringValuePtr(_byte_array);
 218         int            i           = 0;
 219         int            sum         = 0;
 220
 221         for (i = 0; i < size; i++)
 222           sum += COUNT_BITS(byte_array[i]);
 223
 224         return INT2NUM(sum);
 225       }
 226     }
 227
 228     builder.c %{
 229       VALUE sum_rows_c()
 230       {
 231         VALUE          _rows       = rb_ivar_get(self, rows);
 232         VALUE          _cols       = rb_ivar_get(self, cols);
 233         VALUE          _byte_array = rb_ivar_get(self, byte_array);
 234         int            rows        = NUM2INT(_rows);
 235         int            cols        = NUM2INT(_cols);
 236         unsigned char* byte_array  = StringValuePtr(_byte_array);
 237         int            row         = 0;
 238         int            col         = 0;
 239         int            sums[rows];
 240         VALUE          rb_sums     = rb_ary_new();
 241
 242         int pos = 0;
 243
 244         for (row = 0; row < rows; row++) sums[row] = 0;
 245
 246         for (row = 0; row < rows; row++)
 247         {
 248           for (col = 0; col < cols; col++)
 249           {
 250             pos = row * cols + col;
 251             sums[row] += ((byte_array[BYTE_POS(pos)] & BIT_POS(pos)) != 0);
 252           }
 253         }
 254
 255         for (row = 0; row < rows; row++) rb_ary_push(rb_sums, INT2FIX(sums[row]));
 256
 257         return rb_sums;
 258       }
 259     }
 260   end
 261
 262   alias :sum :sum_c
 263   alias :sum_rows :sum_rows_c
 264   alias :bit_set :bit_set_c
 265   alias :bit_set? :bit_test_c
 266   alias :fill! :fill_c
 267   alias :empty! :empty_c
 268   alias :zero! :empty_c
 269 end