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

Return a new BitArray or the specified size.



180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
 
# File 'ext/bitarray.c', line 180

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

    long bits = NUM2LONG(size);
    if (bits <= 0) {
        ba->bits = 0;
        ba->array_size = 0;
        return self;
    }
    long array_size = ((bits - 1) / UINT_BITS) + 1;

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

    return self;
}

Instance Method Details

#+(other_bitarray) ⇒ Object

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



231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
 
# File 'ext/bitarray.c', line 231

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.



509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
 
# File 'ext/bitarray.c', line 509

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.



567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
 
# File 'ext/bitarray.c', line 567

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.



374
375
376
377
378
379
380
381
382
383
384
385
 
# File 'ext/bitarray.c', line 374

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.



353
354
355
356
357
358
359
360
361
362
363
364
365
366
 
# File 'ext/bitarray.c', line 353

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) 


626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
 
# File 'ext/bitarray.c', line 626

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.



208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
 
# File 'ext/bitarray.c', line 208

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) 


593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
 
# File 'ext/bitarray.c', line 593

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.



332
333
334
335
336
337
338
339
340
341
342
343
 
# File 'ext/bitarray.c', line 332

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.



311
312
313
314
315
316
317
318
319
320
321
322
323
324
 
# File 'ext/bitarray.c', line 311

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) 


278
279
280
281
282
283
284
285
 
# File 'ext/bitarray.c', line 278

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

    return LONG2NUM(ba->bits);
}

#toggle_all_bits ⇒ Object

Toggle all bits.



416
417
418
419
420
421
422
423
424
425
426
427
 
# File 'ext/bitarray.c', line 416

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.



395
396
397
398
399
400
401
402
403
404
405
406
407
408
 
# File 'ext/bitarray.c', line 395

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) 


293
294
295
296
297
298
299
300
301
 
# File 'ext/bitarray.c', line 293

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);
}