Class: BitArray

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
ext/bitarray.c,
ext/bitarray.c

Overview

An array of bits. Usage is similar to the standard Array class, but the only allowed elements are 1 and 0. BitArrays are not resizable.

Instance Method Summary collapse

Constructor Details

#new(size) ⇒ Object #new(string) ⇒ Object #new(array) ⇒ Object

When called with a size, creates a new BitArray of the specified size, with all bits cleared. When called with a string or an array, creates a new BitArray from the argument.

If a string is given, it should consist of ones and zeroes. If there are any other characters in the string, the first invalid character and all following characters will be ignored.

b = BitArray.new("10101010")       => 10101010
b = BitArray.new("1010abcd")       => 1010
b = BitArray.new("abcd")           =>

If an array is given, the BitArray is initialized from its elements using the following rules:

  1. 0, false, or nil => 0

  2. anything else => 1

Note that the 0 is a number, not a string. “Anything else” means strings, symbols, non-zero numbers, subarrays, etc.

b = BitArray.new([0,0,0,1,1,0])            => 000110
b = BitArray.new([false, true, false])     => 010
b = BitArray.new([:a, :b, :c, [:d, :e]])   => 1111



289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
 
# File 'ext/bitarray.c', line 289

static VALUE
rb_bitarray_initialize(VALUE self, VALUE arg)
{
    if (TYPE(arg) == T_FIXNUM || TYPE(arg) == T_BIGNUM) {
        struct bit_array *ba;
        Data_Get_Struct(self, struct bit_array, ba);

        long bits = NUM2LONG(arg);
        if (bits <= 0) {
            ba->bits = 0;
            ba->array_size = 0;
            return self;
        }
        
        ba->bits = bits;
        ba->array_size = ((bits - 1) / UINT_BITS) + 1;
        ba->array = ruby_xcalloc(ba->array_size, UINT_BYTES);

        return self;

    } else if (TYPE(arg) == T_STRING) {
        return rb_bitarray_from_string(self, arg);
    } else if (TYPE(arg) == T_ARRAY) { 
        return rb_bitarray_from_array(self, arg);
    } else {
        rb_raise(rb_eArgError, "must be size, string, or array");
    }
}

Instance Method Details

#+(other_bitarray) ⇒ Object

Concatenation—Return a new BitArray built by concatenating the two BitArrays.



348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
 
# File 'ext/bitarray.c', line 348

static VALUE
rb_bitarray_concat(VALUE x, VALUE y)
{
    /* Get the bit_arrays from x and y */
    struct bit_array *x_ba, *y_ba;
    Data_Get_Struct(x, struct bit_array, x_ba);
    Data_Get_Struct(y, struct bit_array, y_ba);

    /* Create a new BitArray, and its bit_array */
    VALUE z;
    struct bit_array *z_ba;
    z = rb_bitarray_alloc(rb_bitarray_class);
    rb_bitarray_initialize(z, LONG2NUM(x_ba->bits + y_ba->bits));
    Data_Get_Struct(z, struct bit_array, z_ba);

    /* For each bit set in x and y, set the corresponding bit in z. First, copy
     * x to the beginning of z. Then, if x->bits is a multiple of UINT_BITS, we
     * can just copy y onto the end of z. Otherwise, we need to go through y
     * bit-by-bit and set the appropriate bits in z.
     */
    memcpy(z_ba->array, x_ba->array, (x_ba->array_size * UINT_BYTES));
    if ((x_ba->bits % UINT_BITS) == 0) {
        unsigned int *start = z_ba->array + x_ba->array_size;
        memcpy(start, y_ba->array, (y_ba->array_size * UINT_BYTES));
    } else {
        long y_index, z_index;
        for (y_index = 0, z_index = x_ba->bits;
                y_index < y_ba->bits;
                y_index++, z_index++)
        {
            if (get_bit(y_ba, y_index) == 1) {
                set_bit(z_ba, z_index);
            } else {
                clear_bit(z_ba, z_index);
            }
        }
    }
    return z;
}

#[](index) ⇒ Object #[](beg, len) ⇒ Object #[](range) ⇒ Object Also known as: slice

Bit Reference—Returns the bit at index, or returns a subarray starting at beg, and continuing for len bits, or returns a subarray specified by range. _Negative indices count backwards from the end of bitarray. If index is greater than the capacity of bitarray, an IndexError is raised.



626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
 
# File 'ext/bitarray.c', line 626

static VALUE
rb_bitarray_bitref(int argc, VALUE *argv, VALUE self)
{
    /* We follow a form similar to rb_ary_aref in array.c */

    /* Two arguments means we have a beginning and a  length */
    if (argc == 2) {
        long beg = NUM2LONG(argv[0]);
        long len = NUM2LONG(argv[1]);
        return rb_bitarray_subseq(self, beg, len);
    } 
    
    /* Make sure we have either 1 or 2 arguments. */
    if (argc != 1) {
        rb_scan_args(argc, argv, "11", 0, 0);
    }

    /* If we have a single argument, it can be either an index, or a range. */
    VALUE arg = argv[0];
    
    /* rb_ary_aref treats a fixnum argument specially, for a speedup in the
     * most common case. We'll do the same.
     */
    if (FIXNUM_P(arg)) {
        return rb_bitarray_get_bit(self, FIX2LONG(arg));
    }

    struct bit_array *ba;
    Data_Get_Struct(self, struct bit_array, ba);
    /* Next we see if arg is a range. rb_range_beg_len is defined in range.c
     * If arg is not a range, it returns Qfalse. If arg is a range, but it
     * refers to invalid indices, it returns Qnil. Otherwise, it sets beg and
     * end to the appropriate values.
     */
    long beg, len;
    switch (rb_range_beg_len(arg, &beg, &len, ba->bits, 0)) {
        case Qfalse:
            break;
        case Qnil:
            return Qnil;
        default:
            return rb_bitarray_subseq(self, beg, len);
    }
    
    return rb_bitarray_get_bit(self, NUM2LONG(arg));
}

#[]=(index) ⇒ Object

Bit Assignment—Sets the bit at index. value must be 0 or 1. Negative indices are allowed, and will count backwards from the end of bitarray.

If index is greater than the capacity of bitarray, an IndexError is raised. If value is something other than 0 or 1, a RuntimeError is raised.



684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
 
# File 'ext/bitarray.c', line 684

static VALUE
rb_bitarray_assign_bit(VALUE self, VALUE bit, VALUE value)
{
    struct bit_array *ba;
    Data_Get_Struct(self, struct bit_array, ba);

    long index = NUM2LONG(bit);
    int bit_value = NUM2INT(value);

    int result = assign_bit(ba, index, bit_value);
    if (result == 1) {
        return value;
    } else if (result == 0) {
        rb_raise(rb_eIndexError, "index %ld out of bit array", index);
    } else {
        rb_raise(rb_eRuntimeError, "bit value %d out of range", bit_value);
    }
}

#clear_all_bits ⇒ Object

Sets all bits to 0.



491
492
493
494
495
496
497
498
499
500
501
502
 
# File 'ext/bitarray.c', line 491

static VALUE
rb_bitarray_clear_all_bits(VALUE self)
{
    struct bit_array *ba;
    Data_Get_Struct(self, struct bit_array, ba);

    if(clear_all_bits(ba)) {
        return self;
    } else {
        rb_bug("BitArray#clear_all_bits failed. This should not occur.");
    }
}

#clear_bit(index) ⇒ Object

Sets the bit at index to 0. Negative indices count backwards from the end of bitarray. If index is greater than the capacity of bitarray, an IndexError is raised.



470
471
472
473
474
475
476
477
478
479
480
481
482
483
 
# File 'ext/bitarray.c', line 470

static VALUE
rb_bitarray_clear_bit(VALUE self, VALUE bit)
{
    struct bit_array *ba;
    Data_Get_Struct(self, struct bit_array, ba);

    long index = NUM2LONG(bit);

    if (clear_bit(ba, index)) {
        return self;
    } else {
        rb_raise(rb_eIndexError, "index %ld out of bit array", index);
    }
}

#each {|bit| ... } ⇒ Object

Calls block once for each bit in bitarray, passing that bit as a parameter.

ba = BitArray.new(10)
ba.each {|bit| print bit, " " }

produces:

0 0 0 0 0 0 0 0 0 0

Yields:

  • (bit) 


766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
 
# File 'ext/bitarray.c', line 766

static VALUE
rb_bitarray_each(VALUE self)
{
    struct bit_array *ba;
    Data_Get_Struct(self, struct bit_array, ba);

    long i;

    RETURN_ENUMERATOR(self, 0, 0);
    for (i = 0; i < ba->bits; i++) {
        int bit_value = get_bit(ba, i);
        rb_yield(INT2NUM(bit_value));
    }
    return self;
}

#clone ⇒ Object #dup ⇒ Object

Produces a copy of bitarray.



325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
 
# File 'ext/bitarray.c', line 325

static VALUE
rb_bitarray_initialize_copy(VALUE self, VALUE orig)
{
    struct bit_array *new_ba, *orig_ba;
    Data_Get_Struct(self, struct bit_array, new_ba);
    Data_Get_Struct(orig, struct bit_array, orig_ba);

    new_ba->bits = orig_ba->bits;
    new_ba->array_size = orig_ba->array_size;
    new_ba->array = ruby_xcalloc(new_ba->array_size, UINT_BYTES);

    memcpy(new_ba->array, orig_ba->array, (new_ba->array_size * UINT_BYTES));

    return self;
}

#inspect ⇒ String #to_s ⇒ String Also known as: to_s

Create a printable version of bitarray.

Overloads:

  • #inspect ⇒ String

    Returns:

    • (String)
  • #to_s ⇒ String

    Returns:

    • (String) 


710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
 
# File 'ext/bitarray.c', line 710

static VALUE
rb_bitarray_inspect(VALUE self)
{
    struct bit_array *ba;
    Data_Get_Struct(self, struct bit_array, ba);

    long cstr_size = ba->bits + 1;
    char cstr[cstr_size];
    
    long i;
    for (i = 0; i < ba->bits; i++) {
        cstr[i] = get_bit(ba, i) + '0';
    }
    cstr[ba->bits] = '\0';

    VALUE str = rb_str_new2(cstr);
    return str;
}

#set_all_bits ⇒ Object

Sets all bits to 1.



449
450
451
452
453
454
455
456
457
458
459
460
 
# File 'ext/bitarray.c', line 449

static VALUE
rb_bitarray_set_all_bits(VALUE self)
{
    struct bit_array *ba;
    Data_Get_Struct(self, struct bit_array, ba);

    if(set_all_bits(ba)) {
        return self;
    } else {
        rb_bug("BitArray#set_all_bits failed. This should not occur.");
    }
}

#set_bit(index) ⇒ Object

Sets the bit at index to 1. Negative indices count backwards from the end of bitarray. If index is greater than the capacity of bitarray, an IndexError is raised.



428
429
430
431
432
433
434
435
436
437
438
439
440
441
 
# File 'ext/bitarray.c', line 428

static VALUE
rb_bitarray_set_bit(VALUE self, VALUE bit)
{
    struct bit_array *ba;
    Data_Get_Struct(self, struct bit_array, ba);

    long index = NUM2LONG(bit);

    if (set_bit(ba, index)) {
        return self;
    } else {
        rb_raise(rb_eIndexError, "index %ld out of bit array", index);
    }
}

#size ⇒ Integer #length ⇒ Integer Also known as: length

Returns the number of bits in bitarray.

Overloads:

  • #size ⇒ Integer

    Returns:

    • (Integer)
  • #length ⇒ Integer

    Returns:

    • (Integer) 


395
396
397
398
399
400
401
402
 
# File 'ext/bitarray.c', line 395

static VALUE
rb_bitarray_size(VALUE self)
{
    struct bit_array *ba;
    Data_Get_Struct(self, struct bit_array, ba);

    return LONG2NUM(ba->bits);
}

#to_a ⇒ Array

Creates a Ruby Array from bitarray.

Returns:

  • (Array) 


735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
 
# File 'ext/bitarray.c', line 735

static VALUE
rb_bitarray_to_a(VALUE self)
{
    struct bit_array *ba;
    Data_Get_Struct(self, struct bit_array, ba);

    long array_size = ba->bits;
    VALUE c_array[array_size];
    
    int i;
    for (i = 0; i < array_size; i++) {
        c_array[i] = INT2FIX(get_bit(ba, i));
    }

    return rb_ary_new4(array_size, c_array);
}

#toggle_all_bits ⇒ Object

Toggle all bits.



533
534
535
536
537
538
539
540
541
542
543
544
 
# File 'ext/bitarray.c', line 533

static VALUE
rb_bitarray_toggle_all_bits(VALUE self)
{
    struct bit_array *ba;
    Data_Get_Struct(self, struct bit_array, ba);

    if(toggle_all_bits(ba)) {
        return self;
    } else {
        rb_bug("BitArray#clear_all_bits failed. This should not occur.");
    }
}

#toggle_bit(index) ⇒ Object

Toggles the bit at index to 0. Negative indices count backwards from the end of bitarray. If index is greater than the capacity of bitarray, an IndexError is raised.



512
513
514
515
516
517
518
519
520
521
522
523
524
525
 
# File 'ext/bitarray.c', line 512

static VALUE
rb_bitarray_toggle_bit(VALUE self, VALUE bit)
{
    struct bit_array *ba;
    Data_Get_Struct(self, struct bit_array, ba);

    long index = NUM2LONG(bit);

    if (toggle_bit(ba, index)) {
        return self;
    } else {
        rb_raise(rb_eIndexError, "index %ld out of bit array", index);
    }
}

#total_set ⇒ Integer

Return the number of set (1) bits in bitarray.

Returns:

  • (Integer) 


410
411
412
413
414
415
416
417
418
 
# File 'ext/bitarray.c', line 410

static VALUE
rb_bitarray_total_set(VALUE self)
{
    struct bit_array *ba;
    Data_Get_Struct(self, struct bit_array, ba);

    long count = total_set(ba);
    return LONG2NUM(count);
}