Class: MultiRBTree

Inherits:
Data
  • Object
show all
Includes:
Enumerable
Defined in:
ext/archipelago_rbtree.c

Direct Known Subclasses

RBTree

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(*args) ⇒ Object 



245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
 
# File 'ext/archipelago_rbtree.c', line 245

VALUE
rbtree_initialize(int argc, VALUE* argv, VALUE self)
{
    rbtree_modify(self);

    if (rb_block_given_p()) {
        if (argc > 0)
            rbtree_argc_error();
        IFNONE(self) = rb_block_proc();
        FL_SET(self, RBTREE_PROC_DEFAULT);
    } else {
        if (argc > 1)
            rbtree_argc_error();
        else if (argc == 1)
            IFNONE(self) = argv[0];
    }
    return self;
}

Class Method Details

.[](*args) ⇒ Object 



215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
 
# File 'ext/archipelago_rbtree.c', line 215

VALUE
rbtree_s_create(int argc, VALUE* argv, VALUE klass)
{
    int i;
    VALUE rbtree;

    if (argc == 1) {
        if (rb_obj_is_kind_of(argv[0], klass)) {
            rbtree = rbtree_alloc(klass);
            rbtree_update(rbtree, argv[0]);
            return rbtree;
        } else if (TYPE(argv[0]) == T_HASH) {
            rbtree = rbtree_alloc(klass);
            st_foreach(RHASH(argv[0])->tbl, hash_to_rbtree_i, rbtree);
            return rbtree;
        }
    }
    
    if (argc % 2 != 0)
        rb_raise(rb_eArgError, "odd number of arguments for RBTree");

    rbtree = rbtree_alloc(klass);
    for (i = 0; i < argc; i += 2)
        rbtree_aset(rbtree, argv[i], argv[i + 1]);
    return rbtree;
}

._load(str) ⇒ Object

Called by Marshal.load.



1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
 
# File 'ext/archipelago_rbtree.c', line 1558

VALUE
rbtree_s_load(VALUE klass, VALUE str)
{
    VALUE rbtree = rbtree_alloc(klass);
    VALUE ary = rb_marshal_load(str);
    VALUE* ptr = RARRAY(ary)->ptr;
    long len = RARRAY(ary)->len - 1;
    long i;
    
    for (i = 0; i < len; i += 2)
        rbtree_aset(rbtree, ptr[i], ptr[i + 1]);
    IFNONE(rbtree) = ptr[len];
    
    rb_ary_clear(ary);
    rb_gc_force_recycle(ary);
    return rbtree;
}

.new(*args) ⇒ Object 



195
196
197
198
199
200
201
 
# File 'ext/archipelago_rbtree.c', line 195

VALUE
rbtree_s_new(int argc, VALUE* argv, VALUE klass)
{
    VALUE rbtree = rbtree_alloc(klass);
    rb_obj_call_init(rbtree, argc, argv);
    return rbtree;
}

Instance Method Details

#==(other) ⇒ Object 



455
456
457
458
459
460
461
462
463
464
465
 
# File 'ext/archipelago_rbtree.c', line 455

VALUE
rbtree_equal(VALUE self, VALUE other)
{
    int ret;
    if (self == other)
        return Qtrue;
    if (!rb_obj_is_kind_of(other, MultiRBTree))
        return Qfalse;
    ret = dict_equal(DICT(self), DICT(other), value_eq);
    return ret ? Qtrue : Qfalse;
}

#[](key) ⇒ Object 



350
351
352
353
354
355
356
357
358
 
# File 'ext/archipelago_rbtree.c', line 350

VALUE
rbtree_aref(VALUE self, VALUE key)
{
    dnode_t* node = dict_lookup(DICT(self), TO_KEY(key));
    if (node == NULL)
        return rb_funcall(self, id_default, 1, key);
    else
        return GET_VAL(node);
}

#[]=(key, value) ⇒ Object 



330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
 
# File 'ext/archipelago_rbtree.c', line 330

VALUE
rbtree_aset(VALUE self, VALUE key, VALUE value)
{
    rbtree_modify(self);

    if (dict_isfull(DICT(self))) {
        dnode_t* node = dict_lookup(DICT(self), TO_KEY(key));
        if (node == NULL)
            rb_raise(rb_eIndexError, "rbtree full");
        else
            dnode_put(node, TO_VAL(value));
        return value;
    }
    rbtree_insert(self, key, value);
    return value;
}

#_dump(limit) ⇒ Object

Called by Marshal.dump.



1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
 
# File 'ext/archipelago_rbtree.c', line 1534

VALUE
rbtree_dump(VALUE self, VALUE limit)
{
    VALUE ary;
    VALUE ret;
    
    if (FL_TEST(self, RBTREE_PROC_DEFAULT))
        rb_raise(rb_eTypeError, "cannot dump rbtree with default proc");
    if ((VALUE)CONTEXT(self) != Qnil)
        rb_raise(rb_eTypeError, "cannot dump rbtree with compare proc");
    
    ary = rb_ary_new2(dict_count(DICT(self)) * 2 + 1);
    rbtree_for_each(self, to_flatten_ary_i, (void*)ary, NULL);
    rb_ary_push(ary, IFNONE(self));

    ret = rb_marshal_dump(ary, limit);
    rb_ary_clear(ary);
    rb_gc_force_recycle(ary);
    return ret;
}

#bound(key1, key2 = key1) ⇒ Array #bound(key1, key2 = key1) {|key, value| ... } ⇒ Object

Returns an array containing key-value pairs between the result of RBTree#lower_bound and RBTree#upper_bound. If a block is given it calls the block once for each pair.

Overloads:

  • #bound(key1, key2 = key1) ⇒ Array

    Returns:

    • (Array)
  • #bound(key1, key2 = key1) {|key, value| ... } ⇒ Object

    Yields:

    • (key, value) 


1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
 
# File 'ext/archipelago_rbtree.c', line 1299

VALUE
rbtree_bound(int argc, VALUE* argv, VALUE self)
{
    dict_t* dict = DICT(self);
    dnode_t* lower_node;
    dnode_t* upper_node;
    VALUE ret;
    
    if (argc == 0 || argc > 2)
        rbtree_argc_error();
    
    lower_node = dict_lower_bound(dict, TO_KEY(argv[0]));
    upper_node = dict_upper_bound(dict, TO_KEY(argv[argc - 1]));
    ret = rb_block_given_p() ? self : rb_ary_new();
    
    if (lower_node == NULL || upper_node == NULL ||
        COMPARE(self)(dnode_getkey(lower_node),
                      dnode_getkey(upper_node),
                      CONTEXT(self)) > 0) {
        return ret;
    } else {
        rbtree_bound_arg_t arg;
        arg.self = self;
        arg.lower_node = lower_node;
        arg.upper_node = upper_node;
        arg.ret = ret;

        return rb_ensure(rbtree_bound_body, (VALUE)&arg,
                         rbtree_each_ensure, self);
    }
}

#clear ⇒ Object 



777
778
779
780
781
782
783
 
# File 'ext/archipelago_rbtree.c', line 777

VALUE
rbtree_clear(VALUE self)
{
    rbtree_modify(self);
    dict_free_nodes(DICT(self));
    return self;
}

#clone ⇒ Object 



708
709
710
711
712
713
714
 
# File 'ext/archipelago_rbtree.c', line 708

VALUE
rbtree_clone(VALUE self)
{
    VALUE clone = rbtree_alloc(CLASS_OF(self));
    rbtree_initialize_copy(clone, self);
    return clone;
}

#cmp_proc ⇒ Proc

Returns the comparison block that is given by RBTree#readjust.

Returns:

  • (Proc) 


1437
1438
1439
1440
1441
 
# File 'ext/archipelago_rbtree.c', line 1437

VALUE
rbtree_cmp_proc(VALUE self)
{
    return (VALUE)(CONTEXT(self));
}

#default(*args) ⇒ Object 



407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
 
# File 'ext/archipelago_rbtree.c', line 407

VALUE
rbtree_default(int argc, VALUE* argv, VALUE self)
{
    VALUE key = Qnil;
    if (argc == 1)
        key = argv[0];
    else if (argc > 1)
        rbtree_argc_error();

    if (FL_TEST(self, RBTREE_PROC_DEFAULT)) {
        if (argc == 0) return Qnil;
        return rb_funcall(IFNONE(self), id_call, 2, self, key);
    }
    return IFNONE(self);
}

#default=(ifnone) ⇒ Object 



426
427
428
429
430
431
432
433
 
# File 'ext/archipelago_rbtree.c', line 426

VALUE
rbtree_set_default(VALUE self, VALUE ifnone)
{
    rbtree_modify(self);
    IFNONE(self) = ifnone;
    FL_UNSET(self, RBTREE_PROC_DEFAULT);
    return ifnone;
}

#default_proc ⇒ Object 



438
439
440
441
442
443
444
 
# File 'ext/archipelago_rbtree.c', line 438

VALUE
rbtree_default_proc(VALUE self)
{
    if (FL_TEST(self, RBTREE_PROC_DEFAULT))
        return IFNONE(self);
    return Qnil;
}

#delete(key) ⇒ Object 



788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
 
# File 'ext/archipelago_rbtree.c', line 788

VALUE
rbtree_delete(VALUE self, VALUE key)
{
    dict_t* dict = DICT(self);
    dnode_t* node;
    VALUE value;

    rbtree_modify(self);
    node = dict_lookup(dict, TO_KEY(key));
    if (node == NULL)
        return rb_block_given_p() ? rb_yield(key) : Qnil;
    value = GET_VAL(node);
    dict_delete_free(dict, node);
    return value;
}

#delete_if ⇒ Object 



864
865
866
867
868
869
870
871
872
873
874
 
# File 'ext/archipelago_rbtree.c', line 864

VALUE
rbtree_delete_if(VALUE self)
{
    rbtree_delete_if_arg_t arg;

    rbtree_modify(self);
    arg.self = self;
    arg.list = NULL;
    return rb_ensure(rbtree_delete_if_body, (VALUE)&arg,
                     rbtree_delete_if_ensure, (VALUE)&arg);
}

#each(start = nil) {|key, value| ... } ⇒ Object

Calls block once for each key in order, passing the key and value as a two-element array parameters. Starts at start if given.

Yields:

  • (key, value) 


566
567
568
569
570
571
572
573
574
575
576
 
# File 'ext/archipelago_rbtree.c', line 566

VALUE
rbtree_each(int argc, VALUE *argv, VALUE self)
{
  if (argc > 1)
    rbtree_argc_error();

  if (argc == 0)
    return rbtree_for_each(self, each_i, NULL, NULL);
  else if (argc == 1)
    return rbtree_for_each(self, each_i, NULL, argv[0]);
}

#each_key {|key| ... } ⇒ Object

Calls block once for each key in order, passing the key as parameters.

Yields:

  • (key) 


612
613
614
615
616
 
# File 'ext/archipelago_rbtree.c', line 612

VALUE
rbtree_each_key(VALUE self)
{
  return rbtree_for_each(self, each_key_i, NULL, NULL);
}

#each_pair {|key, value| ... } ⇒ Object

Calls block once for each key in order, passing the key and value as parameters.

Yields:

  • (key, value) 


592
593
594
595
596
 
# File 'ext/archipelago_rbtree.c', line 592

VALUE
rbtree_each_pair(VALUE self)
{
  return rbtree_for_each(self, each_pair_i, NULL, NULL);
}

#each_value {|value| ... } ⇒ Object

Calls block once for each key in order, passing the value as parameters.

Yields:

  • (value) 


632
633
634
635
636
 
# File 'ext/archipelago_rbtree.c', line 632

VALUE
rbtree_each_value(VALUE self)
{
  return rbtree_for_each(self, each_value_i, NULL, NULL);
}

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


398
399
400
401
402
 
# File 'ext/archipelago_rbtree.c', line 398

VALUE
rbtree_empty_p(VALUE self)
{
    return dict_isempty(DICT(self)) ? Qtrue : Qfalse;
}

#fetch(*args) ⇒ Object 



363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
 
# File 'ext/archipelago_rbtree.c', line 363

VALUE
rbtree_fetch(int argc, VALUE* argv, VALUE self)
{
    dnode_t* node;
    int block_given;

    if (argc == 0 || argc > 2)
        rbtree_argc_error();
    block_given = rb_block_given_p();
    if (block_given && argc == 2)
	rb_warn("block supersedes default value argument");

    node = dict_lookup(DICT(self), TO_KEY(argv[0]));
    if (node != NULL)
        return GET_VAL(node);

    if (block_given)
        return rb_yield(argv[0]);
    if (argc == 1)
        rb_raise(rb_eIndexError, "key not found");
    return argv[1];
}

#first ⇒ Array, Object

Returns the first(that is, the smallest) key-value pair.

Returns:

  • (Array, Object) 


1357
1358
1359
1360
1361
 
# File 'ext/archipelago_rbtree.c', line 1357

VALUE
rbtree_first(VALUE self)
{
    return rbtree_first_last(self, 0);
}

#has_key?(key) ⇒ Boolean

Returns:

  • (Boolean) 


1015
1016
1017
1018
1019
 
# File 'ext/archipelago_rbtree.c', line 1015

VALUE
rbtree_has_key(VALUE self, VALUE key)
{
    return dict_lookup(DICT(self), TO_KEY(key)) == NULL ? Qfalse : Qtrue;
}

#has_value?(value) ⇒ Boolean

Returns:

  • (Boolean) 


1035
1036
1037
1038
1039
1040
1041
1042
1043
 
# File 'ext/archipelago_rbtree.c', line 1035

VALUE
rbtree_has_value(VALUE self, VALUE value)
{
    VALUE arg[2];
    arg[0] = Qfalse;
    arg[1] = value;
    rbtree_for_each(self, has_value_i, (void*)&arg, NULL);
    return arg[0];
}

#include?(key) ⇒ Boolean

Returns:

  • (Boolean) 


1015
1016
1017
1018
1019
 
# File 'ext/archipelago_rbtree.c', line 1015

VALUE
rbtree_has_key(VALUE self, VALUE key)
{
    return dict_lookup(DICT(self), TO_KEY(key)) == NULL ? Qfalse : Qtrue;
}

#index(value) ⇒ Object 



764
765
766
767
768
769
770
771
772
 
# File 'ext/archipelago_rbtree.c', line 764

VALUE
rbtree_index(VALUE self, VALUE value)
{
    VALUE arg[2];
    arg[0] = Qnil;
    arg[1] = value;
    rbtree_for_each(self, index_i, (void*)&arg, NULL);
    return arg[0];
}

#initialize_copy(other) ⇒ Object 



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

VALUE
rbtree_initialize_copy(VALUE self, VALUE other)
{
    if (self == other)
        return self;
    if (!rb_obj_is_kind_of(other, CLASS_OF(self))) {
        rb_raise(rb_eTypeError, "wrong argument type %s (expected %s)",
                 rb_class2name(CLASS_OF(other)),
                 rb_class2name(CLASS_OF(self)));
    }
    
    copy_dict(other, self, COMPARE(other), CONTEXT(other));
    
    IFNONE(self) = IFNONE(other);
    if (FL_TEST(other, RBTREE_PROC_DEFAULT))
        FL_SET(self, RBTREE_PROC_DEFAULT);
    else
        FL_UNSET(self, RBTREE_PROC_DEFAULT);
    return self;
}

#inspect ⇒ Object 



1211
1212
1213
1214
1215
1216
1217
1218
 
# File 'ext/archipelago_rbtree.c', line 1211

VALUE
rbtree_inspect(VALUE self)
{
    VALUE str = rbtree_begin_inspect(self);
    if (rb_inspecting_p(self))
        return rb_str_cat2(str, "...>");
    return rb_protect_inspect(inspect_rbtree, self, str);
}

#invert ⇒ Object 



959
960
961
962
963
964
965
 
# File 'ext/archipelago_rbtree.c', line 959

VALUE
rbtree_invert(VALUE self)
{
    VALUE rbtree = rbtree_alloc(CLASS_OF(self));
    rbtree_for_each(self, invert_i, (void*)rbtree, NULL);
    return rbtree;
}

#key?(key) ⇒ Boolean

Returns:

  • (Boolean) 


1015
1016
1017
1018
1019
 
# File 'ext/archipelago_rbtree.c', line 1015

VALUE
rbtree_has_key(VALUE self, VALUE key)
{
    return dict_lookup(DICT(self), TO_KEY(key)) == NULL ? Qfalse : Qtrue;
}

#keys ⇒ Object 



1055
1056
1057
1058
1059
1060
1061
 
# File 'ext/archipelago_rbtree.c', line 1055

VALUE
rbtree_keys(VALUE self)
{
    VALUE ary = rb_ary_new();
    rbtree_for_each(self, keys_i, (void*)ary, NULL);
    return ary;
}

#last ⇒ Object

Returns the last(that is, the biggest) key-value pair.



1369
1370
1371
1372
1373
 
# File 'ext/archipelago_rbtree.c', line 1369

VALUE
rbtree_last(VALUE self)
{
    return rbtree_first_last(self, 1);
}

#length ⇒ Object 



389
390
391
392
393
 
# File 'ext/archipelago_rbtree.c', line 389

VALUE
rbtree_size(VALUE self)
{
    return ULONG2NUM(dict_count(DICT(self)));
}

#lower_bound(key) ⇒ Array

Retruns key-value pair corresponding to the lowest key that is equal to or greater than the given key(inside of lower boundary). If there is no such key, returns nil.

Returns:

  • (Array) 


1228
1229
1230
1231
1232
1233
1234
1235
 
# File 'ext/archipelago_rbtree.c', line 1228

VALUE
rbtree_lower_bound(VALUE self, VALUE key)
{
    dnode_t* node = dict_lower_bound(DICT(self), TO_KEY(key));
    if (node == NULL)
        return Qnil;
    return ASSOC(node);
}

#member?(key) ⇒ Boolean

Returns:

  • (Boolean) 


1015
1016
1017
1018
1019
 
# File 'ext/archipelago_rbtree.c', line 1015

VALUE
rbtree_has_key(VALUE self, VALUE key)
{
    return dict_lookup(DICT(self), TO_KEY(key)) == NULL ? Qfalse : Qtrue;
}

#merge(other) ⇒ Object 



1006
1007
1008
1009
1010
 
# File 'ext/archipelago_rbtree.c', line 1006

VALUE
rbtree_merge(VALUE self, VALUE other)
{
    return rbtree_update(rb_obj_dup(self), other);
}

#merge!(other) ⇒ Object 



983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
 
# File 'ext/archipelago_rbtree.c', line 983

VALUE
rbtree_update(VALUE self, VALUE other)
{
    rbtree_modify(self);

    if (self == other)
        return self;
    if (!rb_obj_is_kind_of(other, CLASS_OF(self))) {
        rb_raise(rb_eTypeError, "wrong argument type %s (expected %s)",
                 rb_class2name(CLASS_OF(other)),
                 rb_class2name(CLASS_OF(self)));
    }
    
    if (rb_block_given_p())
      rbtree_for_each(other, update_block_i, (void*)self, NULL);
    else
      rbtree_for_each(other, aset_i, (void*)self, NULL);
    return self;
}

#pop ⇒ Array, Object

Removes the last(that is, the biggest) key-value pair and returns it as a two-item array.

Returns:

  • (Array, Object) 


943
944
945
946
947
 
# File 'ext/archipelago_rbtree.c', line 943

VALUE
rbtree_pop(VALUE self)
{
    return rbtree_shift_pop(self, 1);
}

#pretty_print(pp) ⇒ Object

Called by pretty printing function pp.



1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
 
# File 'ext/archipelago_rbtree.c', line 1485

VALUE
rbtree_pretty_print(VALUE self, VALUE pp)
{
    pp_arg_t pp_arg;
    pp_arg.rbtree = self;
    pp_arg.pp = pp;

    return rb_iterate(pp_object_group, (VALUE)&pp_arg,
                      pp_block, (VALUE)&pp_arg);
}

#pretty_print_cycle(pp) ⇒ Object

Called by pretty printing function pp.



1499
1500
1501
1502
1503
 
# File 'ext/archipelago_rbtree.c', line 1499

VALUE
rbtree_pretty_print_cycle(VALUE self, VALUE pp)
{
    return rb_funcall(pp, id_pp, 1, rbtree_inspect(self));
}

#readjust ⇒ Object #readjust(nil) ⇒ Object #readjust(proc) ⇒ Object #readjust {|key1, key2| ... } ⇒ Object

Sets a proc to compare keys and readjusts elements using the given block or a Proc object given as the argument. The block takes two key arguments and returns negative, 0, or positive depending on the first argument is less than, equal to, or greater than the second one. If no block is given it just readjusts elements using current comparison block. If nil is given as the argument it sets default comparison block.

Overloads:

  • #readjust {|key1, key2| ... } ⇒ Object

    Yields:

    • (key1, key2) 


1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
 
# File 'ext/archipelago_rbtree.c', line 1390

VALUE
rbtree_readjust(int argc, VALUE* argv, VALUE self)
{
    dict_comp_t cmp = NULL;
    void* context = NULL;
    
    rbtree_modify(self);

    if (argc == 0) {
        if (rb_block_given_p()) {
            cmp = rbtree_user_cmp;
            context = (void*)rb_block_proc();
        } else {
            cmp = COMPARE(self);
            context = CONTEXT(self);
        }
    } else if (argc == 1 && !rb_block_given_p()) {
        if (argv[0] == Qnil) {
            cmp = rbtree_cmp;
            context = (void*)Qnil;
        } else {
            if (CLASS_OF(argv[0]) != rb_cProc)
                rb_raise(rb_eTypeError,
                         "wrong argument type %s (expected Proc)",
                         rb_class2name(CLASS_OF(argv[0])));
            cmp = rbtree_user_cmp;
            context = (void*)argv[0];
        }
    } else {
        rbtree_argc_error();
    }

    if (dict_isempty(DICT(self))) {
        COMPARE(self) = cmp;
        CONTEXT(self) = context;
        return self;
    }
    copy_dict(self, self, cmp, context);
    return self;
}

#reject ⇒ Object 



892
893
894
895
896
 
# File 'ext/archipelago_rbtree.c', line 892

VALUE
rbtree_reject(VALUE self)
{
    return rbtree_reject_bang(rb_obj_dup(self));
}

#reject! ⇒ Object 



879
880
881
882
883
884
885
886
887
 
# File 'ext/archipelago_rbtree.c', line 879

VALUE
rbtree_reject_bang(VALUE self)
{
    const dictcount_t count = dict_count(DICT(self));
    rbtree_delete_if(self);
    if (count == dict_count(DICT(self)))
        return Qnil;
    return self;
}

#replace(other) ⇒ Object 



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

VALUE
rbtree_initialize_copy(VALUE self, VALUE other)
{
    if (self == other)
        return self;
    if (!rb_obj_is_kind_of(other, CLASS_OF(self))) {
        rb_raise(rb_eTypeError, "wrong argument type %s (expected %s)",
                 rb_class2name(CLASS_OF(other)),
                 rb_class2name(CLASS_OF(self)));
    }
    
    copy_dict(other, self, COMPARE(other), CONTEXT(other));
    
    IFNONE(self) = IFNONE(other);
    if (FL_TEST(other, RBTREE_PROC_DEFAULT))
        FL_SET(self, RBTREE_PROC_DEFAULT);
    else
        FL_UNSET(self, RBTREE_PROC_DEFAULT);
    return self;
}

#reverse_each(start = nil) {|key, value| ... } ⇒ Object

Calls block once for each key in reverse order, passing the key and value as parameters. Starts at start if given.

Yields:

  • (key, value) 


645
646
647
648
649
650
651
652
653
654
655
 
# File 'ext/archipelago_rbtree.c', line 645

VALUE
rbtree_reverse_each(int argc, VALUE *argv, VALUE self)
{
  if (argc > 1)
    rbtree_argc_error();

  if (argc == 0)
    return rbtree_reverse_for_each(self, each_i, NULL, NULL);
  else if (argc == 1)
    return rbtree_reverse_for_each(self, each_i, NULL, argv[0]);
}

#select ⇒ Object 



742
743
744
745
746
747
748
 
# File 'ext/archipelago_rbtree.c', line 742

VALUE
rbtree_select(VALUE self)
{
    VALUE ary = rb_ary_new();
    rbtree_for_each(self, select_i, (void*)ary, NULL);
    return ary;
}

#shift ⇒ Array, Object

Removes the first(that is, the smallest) key-value pair and returns it as a two-item array.

Returns:

  • (Array, Object) 


930
931
932
933
934
 
# File 'ext/archipelago_rbtree.c', line 930

VALUE
rbtree_shift(VALUE self)
{
    return rbtree_shift_pop(self, 0);
}

#size ⇒ Object 



389
390
391
392
393
 
# File 'ext/archipelago_rbtree.c', line 389

VALUE
rbtree_size(VALUE self)
{
    return ULONG2NUM(dict_count(DICT(self)));
}

#store(key, value) ⇒ Object 



330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
 
# File 'ext/archipelago_rbtree.c', line 330

VALUE
rbtree_aset(VALUE self, VALUE key, VALUE value)
{
    rbtree_modify(self);

    if (dict_isfull(DICT(self))) {
        dnode_t* node = dict_lookup(DICT(self), TO_KEY(key));
        if (node == NULL)
            rb_raise(rb_eIndexError, "rbtree full");
        else
            dnode_put(node, TO_VAL(value));
        return value;
    }
    rbtree_insert(self, key, value);
    return value;
}

#to_a ⇒ Object 



1091
1092
1093
1094
1095
1096
1097
1098
 
# File 'ext/archipelago_rbtree.c', line 1091

VALUE
rbtree_to_a(VALUE self)
{
    VALUE ary = rb_ary_new();
    rbtree_for_each(self, to_a_i, (void*)ary, NULL);
    OBJ_INFECT(ary, self);
    return ary;
}

#to_hash ⇒ Object 



1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
 
# File 'ext/archipelago_rbtree.c', line 1110

VALUE
rbtree_to_hash(VALUE self)
{
    VALUE hash = rb_hash_new();
    rbtree_for_each(self, to_hash_i, (void*)hash, NULL);
    RHASH(hash)->ifnone = IFNONE(self);
    if (FL_TEST(self, RBTREE_PROC_DEFAULT))
        FL_SET(hash, HASH_PROC_DEFAULT);
    OBJ_INFECT(hash, self);
    return hash;
}

#to_rbtree ⇒ Object 



1125
1126
1127
1128
1129
 
# File 'ext/archipelago_rbtree.c', line 1125

VALUE
rbtree_to_rbtree(VALUE self)
{
    return self;
}

#to_s ⇒ Object 



1150
1151
1152
1153
1154
1155
1156
 
# File 'ext/archipelago_rbtree.c', line 1150

VALUE
rbtree_to_s(VALUE self)
{
    if (rb_inspecting_p(self))
        return rb_str_cat2(rbtree_begin_inspect(self), "...>");
    return rb_protect_inspect(to_s_rbtree, self, Qnil);
}

#update(other) ⇒ Object 



983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
 
# File 'ext/archipelago_rbtree.c', line 983

VALUE
rbtree_update(VALUE self, VALUE other)
{
    rbtree_modify(self);

    if (self == other)
        return self;
    if (!rb_obj_is_kind_of(other, CLASS_OF(self))) {
        rb_raise(rb_eTypeError, "wrong argument type %s (expected %s)",
                 rb_class2name(CLASS_OF(other)),
                 rb_class2name(CLASS_OF(self)));
    }
    
    if (rb_block_given_p())
      rbtree_for_each(other, update_block_i, (void*)self, NULL);
    else
      rbtree_for_each(other, aset_i, (void*)self, NULL);
    return self;
}

#upper_bound(key) ⇒ Array

Retruns key-value pair corresponding to the greatest key that is equal to or lower than the given key(inside of upper boundary). If there is no such key, returns nil.

Returns:

  • (Array) 


1245
1246
1247
1248
1249
1250
1251
1252
 
# File 'ext/archipelago_rbtree.c', line 1245

VALUE
rbtree_upper_bound(VALUE self, VALUE key)
{
    dnode_t* node = dict_upper_bound(DICT(self), TO_KEY(key));
    if (node == NULL)
        return Qnil;
    return ASSOC(node);
}

#value?(value) ⇒ Boolean

Returns:

  • (Boolean) 


1035
1036
1037
1038
1039
1040
1041
1042
1043
 
# File 'ext/archipelago_rbtree.c', line 1035

VALUE
rbtree_has_value(VALUE self, VALUE value)
{
    VALUE arg[2];
    arg[0] = Qfalse;
    arg[1] = value;
    rbtree_for_each(self, has_value_i, (void*)&arg, NULL);
    return arg[0];
}

#values ⇒ Object 



1073
1074
1075
1076
1077
1078
1079
 
# File 'ext/archipelago_rbtree.c', line 1073

VALUE
rbtree_values(VALUE self)
{
    VALUE ret = rb_ary_new();
    rbtree_for_each(self, values_i, (void*)ret, NULL);
    return ret;
}

#values_at(*args) ⇒ Object 



720
721
722
723
724
725
726
727
728
729
 
# File 'ext/archipelago_rbtree.c', line 720

VALUE
rbtree_values_at(int argc, VALUE* argv, VALUE self)
{
    int i;
    VALUE ary = rb_ary_new();
    
    for (i = 0; i < argc; i++)
        rb_ary_push(ary, rbtree_aref(self, argv[i]));
    return ary;
}