Class: MultiRBTree

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

Direct Known Subclasses

RBTree

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(*args) ⇒ Object 



236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
 
# File 'ext/rbtree.c', line 236

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 



175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
 
# File 'ext/rbtree.c', line 175

VALUE
rbtree_s_create(int argc, VALUE* argv, VALUE klass)
{
    long i;
    VALUE rbtree;
    
    if (argc == 1) {
        VALUE tmp;
        
        if (klass == RBTree && CLASS_OF(argv[0]) == MultiRBTree) {
            rb_raise(rb_eTypeError, "can't convert MultiRBTree to RBTree");
        }
        
        if (rb_obj_is_kind_of(argv[0], klass)) {
            rbtree = rbtree_alloc(klass);
            rbtree_update(rbtree, argv[0]);
            return rbtree;
        }
        
        tmp = rb_check_convert_type(argv[0], T_HASH, "Hash", "to_hash");
        if (!NIL_P(tmp)) {
            rbtree = rbtree_alloc(klass);
            st_foreach(RHASH_TBL(tmp), hash_to_rbtree_i, rbtree);
            return rbtree;
        }
        
        tmp = rb_check_array_type(argv[0]);
        if (!NIL_P(tmp)) {
            rbtree = rbtree_alloc(klass);
            for (i = 0; i < RARRAY_LEN(tmp); i++) {
                VALUE v = rb_check_array_type(RARRAY_PTR(tmp)[i]);
                if (NIL_P(v)) {
                    continue;
                }
                switch(RARRAY_LEN(v)) {
                case 1:
                    rbtree_aset(rbtree, RARRAY_PTR(v)[0], Qnil);
                    break;
                case 2:
                    rbtree_aset(rbtree, RARRAY_PTR(v)[0], RARRAY_PTR(v)[1]);
                    break;
                default:
                    continue;
                }
            }
            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.



1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
 
# File 'ext/rbtree.c', line 1544

VALUE
rbtree_s_load(VALUE klass, VALUE str)
{
    VALUE rbtree = rbtree_alloc(klass);
    VALUE ary = rb_marshal_load(str);
    VALUE* ptr = RARRAY_PTR(ary);
    long len = RARRAY_LEN(ary) - 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;
}

Instance Method Details

#==(other) ⇒ Object 



446
447
448
449
450
451
452
453
454
455
456
 
# File 'ext/rbtree.c', line 446

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 



341
342
343
344
345
346
347
348
349
 
# File 'ext/rbtree.c', line 341

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 



321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
 
# File 'ext/rbtree.c', line 321

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.



1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
 
# File 'ext/rbtree.c', line 1520

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);
    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 MultiRBTree#lower_bound and MultiRBTree#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/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 



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

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

#cmp_proc ⇒ Proc

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

Returns:

  • (Proc) 


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

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

#default(*args) ⇒ Object 



398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
 
# File 'ext/rbtree.c', line 398

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 



417
418
419
420
421
422
423
424
 
# File 'ext/rbtree.c', line 417

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 



429
430
431
432
433
434
435
 
# File 'ext/rbtree.c', line 429

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

#delete(key) ⇒ Object 



753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
 
# File 'ext/rbtree.c', line 753

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 



829
830
831
832
833
834
835
836
837
838
839
840
 
# File 'ext/rbtree.c', line 829

VALUE
rbtree_delete_if(VALUE self)
{
    rbtree_delete_if_arg_t arg;
    
    RETURN_ENUMERATOR(self, 0, NULL);
    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 {|key, value| ... } ⇒ Object

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

Yields:

  • (key, value) 


548
549
550
551
552
553
 
# File 'ext/rbtree.c', line 548

VALUE
rbtree_each(VALUE self)
{
    RETURN_ENUMERATOR(self, 0, NULL);
    return rbtree_for_each(self, each_i, NULL);
}

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

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

Yields:

  • (key) 


590
591
592
593
594
595
 
# File 'ext/rbtree.c', line 590

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

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

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

Yields:

  • (key, value) 


569
570
571
572
573
574
 
# File 'ext/rbtree.c', line 569

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

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

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

Yields:

  • (value) 


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

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

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


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

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

#fetch(*args) ⇒ Object 



354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
 
# File 'ext/rbtree.c', line 354

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/rbtree.c', line 1357

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

#has_key?(key) ⇒ Boolean

Returns:

  • (Boolean) 


984
985
986
987
988
 
# File 'ext/rbtree.c', line 984

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) 


1004
1005
1006
1007
1008
1009
1010
1011
1012
 
# File 'ext/rbtree.c', line 1004

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);
    return arg[0];
}

#include?(key) ⇒ Boolean

Returns:

  • (Boolean) 


984
985
986
987
988
 
# File 'ext/rbtree.c', line 984

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

#index(value) ⇒ Object 



729
730
731
732
733
734
735
736
737
 
# File 'ext/rbtree.c', line 729

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

#initialize_copy(other) ⇒ Object 



658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
 
# File 'ext/rbtree.c', line 658

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 



1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
 
# File 'ext/rbtree.c', line 1207

VALUE
rbtree_inspect(VALUE self)
{
#ifdef HAVE_RB_EXEC_RECURSIVE
    return rb_exec_recursive(rbtree_inspect_recursive, self, Qnil);
#else
    VALUE str = rbtree_begin_inspect(self);
    if (rb_inspecting_p(self))
        return rb_str_cat2(str, "...>");
    return rb_protect_inspect(inspect_rbtree, self, str);
#endif
}

#invert ⇒ Object 



928
929
930
931
932
933
934
 
# File 'ext/rbtree.c', line 928

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

#key?(key) ⇒ Boolean

Returns:

  • (Boolean) 


984
985
986
987
988
 
# File 'ext/rbtree.c', line 984

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

#keys ⇒ Object 



1024
1025
1026
1027
1028
1029
1030
 
# File 'ext/rbtree.c', line 1024

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

#last ⇒ Object

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



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

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

#length ⇒ Object 



380
381
382
383
384
 
# File 'ext/rbtree.c', line 380

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/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) 


984
985
986
987
988
 
# File 'ext/rbtree.c', line 984

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

#merge(other) ⇒ Object 



975
976
977
978
979
 
# File 'ext/rbtree.c', line 975

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

#merge!(other) ⇒ Object 



952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
 
# File 'ext/rbtree.c', line 952

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);
    else
        rbtree_for_each(other, aset_i, (void*)self);
    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) 


912
913
914
915
916
 
# File 'ext/rbtree.c', line 912

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/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/rbtree.c', line 1499

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

#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 arguments of a key 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/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 



861
862
863
864
865
 
# File 'ext/rbtree.c', line 861

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

#reject! ⇒ Object 



845
846
847
848
849
850
851
852
853
854
855
856
 
# File 'ext/rbtree.c', line 845

VALUE
rbtree_reject_bang(VALUE self)
{
    dictcount_t count;
    
    RETURN_ENUMERATOR(self, 0, NULL);
    count = dict_count(DICT(self));
    rbtree_delete_if(self);
    if (count == dict_count(DICT(self)))
        return Qnil;
    return self;
}

#replace(other) ⇒ Object 



658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
 
# File 'ext/rbtree.c', line 658

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 {|key, value| ... } ⇒ Object

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

Yields:

  • (key, value) 


625
626
627
628
629
630
 
# File 'ext/rbtree.c', line 625

VALUE
rbtree_reverse_each(VALUE self)
{
    RETURN_ENUMERATOR(self, 0, NULL);
    return rbtree_reverse_for_each(self, each_pair_i, NULL);
}

#select ⇒ Object 



704
705
706
707
708
709
710
711
712
713
 
# File 'ext/rbtree.c', line 704

VALUE
rbtree_select(VALUE self)
{
    VALUE ary;
    
    RETURN_ENUMERATOR(self, 0, NULL);
    ary = rb_ary_new();
    rbtree_for_each(self, select_i, (void*)ary);
    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) 


899
900
901
902
903
 
# File 'ext/rbtree.c', line 899

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

#size ⇒ Object 



380
381
382
383
384
 
# File 'ext/rbtree.c', line 380

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

#store(key, value) ⇒ Object 



321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
 
# File 'ext/rbtree.c', line 321

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 



1060
1061
1062
1063
1064
1065
1066
1067
 
# File 'ext/rbtree.c', line 1060

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

#to_hash ⇒ Object 



1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
 
# File 'ext/rbtree.c', line 1079

VALUE
rbtree_to_hash(VALUE self)
{
    VALUE hash;
    if (CLASS_OF(self) == MultiRBTree) {
        rb_raise(rb_eTypeError, "can't convert MultiRBTree to Hash");
    }
    
    hash = rb_hash_new();
    rbtree_for_each(self, to_hash_i, (void*)hash);
    RHASH_IFNONE(hash) = IFNONE(self);
    if (FL_TEST(self, RBTREE_PROC_DEFAULT))
        FL_SET(hash, HASH_PROC_DEFAULT);
    OBJ_INFECT(hash, self);
    return hash;
}

#to_rbtree ⇒ Object 



1099
1100
1101
1102
1103
 
# File 'ext/rbtree.c', line 1099

VALUE
rbtree_to_rbtree(VALUE self)
{
    return self;
}

#to_s ⇒ Object 



1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
 
# File 'ext/rbtree.c', line 1133

VALUE
rbtree_to_s(VALUE self)
{
#ifdef HAVE_RB_EXEC_RECURSIVE
    return rb_exec_recursive(rbtree_to_s_recursive, self, Qnil);
#else
    if (rb_inspecting_p(self))
        return rb_str_cat2(rbtree_begin_inspect(self), "...>");
    return rb_protect_inspect(to_s_rbtree, self, Qnil);
#endif
}

#update(other) ⇒ Object 



952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
 
# File 'ext/rbtree.c', line 952

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);
    else
        rbtree_for_each(other, aset_i, (void*)self);
    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/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) 


1004
1005
1006
1007
1008
1009
1010
1011
1012
 
# File 'ext/rbtree.c', line 1004

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);
    return arg[0];
}

#values ⇒ Object 



1042
1043
1044
1045
1046
1047
1048
 
# File 'ext/rbtree.c', line 1042

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

#values_at(*args) ⇒ Object 



682
683
684
685
686
687
688
689
690
691
 
# File 'ext/rbtree.c', line 682

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