class MultiRBTree
A sorted associative collection that can contain duplicate keys.
Public Class Methods
VALUE rbtree_s_create(int argc, VALUE* argv, VALUE klass) { long i; VALUE rbtree; if (argc == 1) { VALUE temp; if (rb_obj_is_kind_of(argv[0], klass)) { rbtree = rbtree_alloc(klass); rbtree_update(rbtree, argv[0]); return rbtree; } if (RTEST(rb_class_inherited_p(klass, RBTree)) && (rb_obj_is_kind_of(argv[0], MultiRBTree) && !rb_obj_is_kind_of(argv[0], RBTree))) { rb_raise(rb_eTypeError, "wrong argument type MultiRBTree (expected RBTree)"); } temp = rb_check_convert_type(argv[0], T_HASH, "Hash", "to_hash"); if (!NIL_P(temp)) { rbtree = rbtree_alloc(klass); rb_hash_foreach(temp, hash_to_rbtree_i, rbtree); return rbtree; } temp = rb_check_array_type(argv[0]); if (!NIL_P(temp)) { rbtree = rbtree_alloc(klass); for (i = 0; i < RARRAY_LEN(temp); i++) { VALUE v = rb_check_array_type(RARRAY_AREF(temp, i)); if (NIL_P(v)) { rb_warn("wrong element type %s at %ld (expected Array)", rb_obj_classname(RARRAY_AREF(temp, i)), i); continue; } switch(RARRAY_LEN(v)) { case 1: rbtree_aset(rbtree, RARRAY_AREF(v, 0), Qnil); break; case 2: rbtree_aset(rbtree, RARRAY_AREF(v, 0), RARRAY_AREF(v, 1)); break; default: rb_warn("invalid number of elements (%ld for 1..2)", RARRAY_LEN(v)); } } return rbtree; } } if (argc % 2 != 0) rb_raise(rb_eArgError, "odd number of arguments for %s", rb_class2name(klass)); rbtree = rbtree_alloc(klass); for (i = 0; i < argc; i += 2) rbtree_aset(rbtree, argv[i], argv[i + 1]); return rbtree; }
VALUE rbtree_initialize(int argc, VALUE* argv, VALUE self) { rbtree_modify(self); if (rb_block_given_p()) { VALUE proc; rbtree_check_argument_count(argc, 0, 0); proc = rb_block_proc(); rbtree_check_proc_arity(proc, 2); IFNONE(self) = proc; FL_SET(self, RBTREE_PROC_DEFAULT); } else { rbtree_check_argument_count(argc, 0, 1); if (argc == 1) { IFNONE(self) = argv[0]; } } return self; }
Public Instance Methods
VALUE rbtree_equal(VALUE self, VALUE other) { if (self == other) return Qtrue; if (!rb_obj_is_kind_of(other, MultiRBTree)) return Qfalse; if (dict_count(DICT(self)) != dict_count(DICT(other)) || DICT(self)->dict_compare != DICT(other)->dict_compare || CMP_PROC(self) != CMP_PROC(other)) { return Qfalse; } #if defined(HAVE_RB_EXEC_RECURSIVE_PAIRED) return rb_exec_recursive_paired(rbtree_recursive_equal, self, other, other); #elif defined(HAVE_RB_EXEC_RECURSIVE) return rb_exec_recursive(rbtree_recursive_equal, self, other); #else return rbtree_recursive_equal(self, other, 0); #endif }
VALUE rbtree_aref(VALUE self, VALUE key) { dnode_t* node = dict_lookup(DICT(self), TO_KEY(key)); if (node == NULL) return rb_funcall2(self, id_default, 1, &key); else return GET_VAL(node); }
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; }
Calls block once for each key between the result of rbtree.lower_bound(key1) and rbtree.upper_bound(key2) in order, passing the key-value pair as parameters. If the lower bound exceeds the upper bound, block is not called.
Returns an enumerator if no block is given.
mrbtree = MultiRBTree["az", 10, "ba", 20, "ba", 30, "bz", 40] mrbtree.bound("ba").to_a # => [["ba", 20], ["ba", 30]] mrbtree.bound("b", "c").to_a # => [["ba", 20], ["ba", 30], ["bz", 40]] # the lower bound ("ba") exceeds the upper bound ("az") mrbtree.bound("b").to_a # => []
VALUE rbtree_bound(int argc, VALUE* argv, VALUE self) { dict_t* dict = DICT(self); dnode_t* lower_node; dnode_t* upper_node; VALUE result; rbtree_check_argument_count(argc, 1, 2); RETURN_SIZED_ENUMERATOR(self, argc, argv, rbtree_bound_size); lower_node = dict_lower_bound(dict, TO_KEY(argv[0])); upper_node = dict_upper_bound(dict, TO_KEY(argv[argc - 1])); result = rb_block_given_p() ? self : rb_ary_new(); if (lower_node == NULL || upper_node == NULL || DICT(self)->dict_compare(dnode_getkey(lower_node), dnode_getkey(upper_node), DICT(self)->dict_context) > 0) { return result; } else { rbtree_bound_arg_t arg; arg.self = self; arg.lower_node = lower_node; arg.upper_node = upper_node; arg.result = result; return rb_ensure(rbtree_bound_body, (VALUE)&arg, rbtree_each_ensure, self); } }
VALUE rbtree_clear(VALUE self) { rbtree_modify(self); dict_free_nodes(DICT(self)); return self; }
Returns the comparison block that is set by MultiRBTree#readjust
. If the default comparison block is set, returns nil.
VALUE rbtree_cmp_proc(VALUE self) { return CMP_PROC(self); }
VALUE rbtree_default(int argc, VALUE* argv, VALUE self) { rbtree_check_argument_count(argc, 0, 1); if (FL_TEST(self, RBTREE_PROC_DEFAULT)) { if (argc == 0) { return Qnil; } return rb_funcall(IFNONE(self), id_call, 2, self, argv[0]); } return IFNONE(self); }
VALUE rbtree_set_default(VALUE self, VALUE ifnone) { rbtree_modify(self); IFNONE(self) = ifnone; FL_UNSET(self, RBTREE_PROC_DEFAULT); return ifnone; }
VALUE rbtree_default_proc(VALUE self) { if (FL_TEST(self, RBTREE_PROC_DEFAULT)) return IFNONE(self); return Qnil; }
VALUE rbtree_set_default_proc(VALUE self, VALUE proc) { VALUE temp; rbtree_modify(self); if (NIL_P(proc)) { IFNONE(self) = Qnil; FL_UNSET(self, RBTREE_PROC_DEFAULT); return Qnil; } temp = rb_check_convert_type(proc, T_DATA, "Proc", "to_proc"); if (NIL_P(temp)) { rb_raise(rb_eTypeError, "wrong default_proc type %s (expected Proc)", rb_obj_classname(proc)); } rbtree_check_proc_arity(temp, 2); IFNONE(self) = temp; FL_SET(self, RBTREE_PROC_DEFAULT); return proc; }
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; }
VALUE rbtree_delete_if(VALUE self) { return rbtree_remove_if(self, 1); }
Calls block once for each key in order, passing the key-value pair as parameters.
Returns an enumerator if no block is given.
VALUE rbtree_each_pair(VALUE self) { RETURN_SIZED_ENUMERATOR(self, 0, NULL, rbtree_size); return rbtree_for_each(self, each_pair_i, NULL); }
Calls block once for each key in order, passing the key as a parameter.
Returns an enumerator if no block is given.
VALUE rbtree_each_key(VALUE self) { RETURN_SIZED_ENUMERATOR(self, 0, NULL, rbtree_size); return rbtree_for_each(self, each_key_i, NULL); }
Calls block once for each key in order, passing the key-value pair as parameters.
Returns an enumerator if no block is given.
VALUE rbtree_each_pair(VALUE self) { RETURN_SIZED_ENUMERATOR(self, 0, NULL, rbtree_size); return rbtree_for_each(self, each_pair_i, NULL); }
Calls block once for each key in order, passing the value as a parameter.
Returns an enumerator if no block is given.
VALUE rbtree_each_value(VALUE self) { RETURN_SIZED_ENUMERATOR(self, 0, NULL, rbtree_size); return rbtree_for_each(self, each_value_i, NULL); }
VALUE rbtree_empty_p(VALUE self) { return dict_isempty(DICT(self)) ? Qtrue : Qfalse; }
VALUE rbtree_fetch(int argc, VALUE* argv, VALUE self) { dnode_t* node; rbtree_check_argument_count(argc, 1, 2); if (argc == 2 && rb_block_given_p()) { rb_warn("block supersedes default value argument"); } node = dict_lookup(DICT(self), TO_KEY(argv[0])); if (node != NULL) { return GET_VAL(node); } if (rb_block_given_p()) { return rb_yield(argv[0]); } if (argc == 1) { rb_raise(rb_eIndexError, "key not found"); } return argv[1]; }
Returns the first (that is, the smallest) key-value pair.
VALUE rbtree_first(VALUE self) { return rbtree_first_last(self, 1); }
VALUE rbtree_flatten(int argc, VALUE* argv, VALUE self) { VALUE ary; rbtree_check_argument_count(argc, 0, 1); ary = rb_ary_new2(dict_count(DICT(self)) * 2); rbtree_for_each(self, to_flat_ary_i, (void*)ary); if (argc == 1) { const int level = NUM2INT(argv[0]) - 1; if (level > 0) { argv[0] = INT2FIX(level); rb_funcall2(ary, id_flatten_bang, argc, argv); } } return ary; }
VALUE rbtree_has_key(VALUE self, VALUE key) { return dict_lookup(DICT(self), TO_KEY(key)) == NULL ? Qfalse : Qtrue; }
VALUE rbtree_has_value(VALUE self, VALUE value) { VALUE args[2]; args[0] = Qfalse; args[1] = value; rbtree_for_each(self, has_value_i, &args); return args[0]; }
VALUE rbtree_has_key(VALUE self, VALUE key) { return dict_lookup(DICT(self), TO_KEY(key)) == NULL ? Qfalse : Qtrue; }
VALUE rbtree_index(VALUE self, VALUE value) { VALUE klass = rb_obj_is_kind_of(self, RBTree) ? RBTree : MultiRBTree; const char* classname = rb_class2name(klass); rb_warn("%s#index is deprecated; use %s#key", classname, classname); return rbtree_key(self, value); }
VALUE rbtree_initialize_copy(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_obj_classname(other), rb_obj_classname(self)); } copy_dict(other, self, DICT(other)->dict_compare, CMP_PROC(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; }
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 }
VALUE rbtree_invert(VALUE self) { VALUE rbtree = rbtree_alloc(CLASS_OF(self)); rbtree_for_each(self, invert_i, (void*)rbtree); return rbtree; }
VALUE rbtree_keep_if(VALUE self) { return rbtree_remove_if(self, 0); }
VALUE rbtree_key(VALUE self, VALUE value) { VALUE args[2]; args[0] = Qnil; args[1] = value; rbtree_for_each(self, key_i, &args); return args[0]; }
VALUE rbtree_has_key(VALUE self, VALUE key) { return dict_lookup(DICT(self), TO_KEY(key)) == NULL ? Qfalse : Qtrue; }
VALUE rbtree_keys(VALUE self) { VALUE ary = rb_ary_new2(dict_count(DICT(self))); rbtree_for_each(self, keys_i, (void*)ary); return ary; }
Returns the last (that is, the greatest) key-value pair.
VALUE rbtree_last(VALUE self) { return rbtree_first_last(self, 0); }
VALUE rbtree_size(VALUE self) { return ULONG2NUM(dict_count(DICT(self))); }
Retruns the key-value pair corresponding to the lowest key that is equal to or greater than the given key (inside the lower boundary). If there is no such key, returns nil.
rbtree = RBTree["az", 10, "ba", 20] rbtree.lower_bound("ba") # => ["ba", 20] # "ba" is the lowest key that is greater than "b" rbtree.lower_bound("b") # => ["ba", 20] # no key that is equal to or greater than "c" rbtree.lower_bound("c") # => nil
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); }
VALUE rbtree_has_key(VALUE self, VALUE key) { return dict_lookup(DICT(self), TO_KEY(key)) == NULL ? Qfalse : Qtrue; }
VALUE rbtree_merge(VALUE self, VALUE other) { return rbtree_update(rb_obj_dup(self), other); }
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_obj_classname(other), rb_obj_classname(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; }
Removes the last (that is, the greatest) key-value pair and returns it.
VALUE rbtree_pop(VALUE self) { return rbtree_shift_pop(self, 1); }
Sets a proc to compare keys and readjusts elements using the given block or a Proc object given as an argument. The block takes two keys and returns a negative integer, 0, or a positive integer as the first argument is less than, equal to, or greater than the second one. If no block is given, just readjusts elements using the current comparison block. If nil is given as an argument the default comparison block that uses the <=> method is set.
rbtree = RBTree["a", 10, "b", 20] rbtree.readjust {|a, b| b <=> a } rbtree.first # => ["b", 20] rbtree.readjust(nil) rbtree.first # => ["a", 10]
VALUE rbtree_readjust(int argc, VALUE* argv, VALUE self) { dict_comp_t cmp_func = NULL; VALUE cmp_proc = Qnil; rbtree_modify(self); if (rb_block_given_p()) { rbtree_check_argument_count(argc, 0, 0); cmp_func = rbtree_user_cmp; cmp_proc = rb_block_proc(); rbtree_check_proc_arity(cmp_proc, 2); } else { rbtree_check_argument_count(argc, 0, 1); if (argc == 0) { cmp_func = DICT(self)->dict_compare; cmp_proc = CMP_PROC(self); } else { if (NIL_P(argv[0])) { cmp_func = rbtree_cmp; cmp_proc = Qnil; } else { VALUE proc = rb_check_convert_type(argv[0], T_DATA, "Proc", "to_proc"); if (NIL_P(proc)) { rb_raise(rb_eTypeError, "wrong cmp_proc type %s (expected Proc)", rb_obj_classname(argv[0])); } cmp_func = rbtree_user_cmp; cmp_proc = proc; rbtree_check_proc_arity(cmp_proc, 2); } } } if (dict_isempty(DICT(self))) { DICT(self)->dict_compare = cmp_func; CMP_PROC(self) = cmp_proc; return self; } copy_dict(self, self, cmp_func, cmp_proc); return self; }
VALUE rbtree_reject(VALUE self) { return rbtree_select_if(self, 0); }
VALUE rbtree_reject_bang(VALUE self) { dictcount_t count; RETURN_SIZED_ENUMERATOR(self, 0, NULL, rbtree_size); count = dict_count(DICT(self)); rbtree_delete_if(self); if (count == dict_count(DICT(self))) return Qnil; return self; }
VALUE rbtree_initialize_copy(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_obj_classname(other), rb_obj_classname(self)); } copy_dict(other, self, DICT(other)->dict_compare, CMP_PROC(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; }
Calls block once for each key in reverse order, passing the key-value pair as parameters.
Returns an enumerator if no block is given.
VALUE rbtree_reverse_each(VALUE self) { RETURN_SIZED_ENUMERATOR(self, 0, NULL, rbtree_size); return rbtree_reverse_for_each(self, each_pair_i, NULL); }
VALUE rbtree_select(VALUE self) { return rbtree_select_if(self, 1); }
VALUE rbtree_select_bang(VALUE self) { dictcount_t count; RETURN_SIZED_ENUMERATOR(self, 0, NULL, rbtree_size); count = dict_count(DICT(self)); rbtree_keep_if(self); if (count == dict_count(DICT(self))) return Qnil; return self; }
Removes the first (that is, the smallest) key-value pair and returns it.
VALUE rbtree_shift(VALUE self) { return rbtree_shift_pop(self, 0); }
VALUE rbtree_size(VALUE self) { return ULONG2NUM(dict_count(DICT(self))); }
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; }
VALUE rbtree_to_a(VALUE self) { VALUE ary = rb_ary_new2(dict_count(DICT(self))); rbtree_for_each(self, to_a_i, (void*)ary); OBJ_INFECT(ary, self); return ary; }
VALUE rbtree_to_hash(VALUE self) { VALUE hash; if (!rb_obj_is_kind_of(self, RBTree)) rb_raise(rb_eTypeError, "can't convert MultiRBTree to Hash"); hash = rb_hash_new(); rbtree_for_each(self, to_hash_i, (void*)hash); RHASH_SET_IFNONE(hash, IFNONE(self)); if (FL_TEST(self, RBTREE_PROC_DEFAULT)) FL_SET(hash, HASH_PROC_DEFAULT); OBJ_INFECT(hash, self); return hash; }
VALUE rbtree_to_hash(VALUE self) { VALUE hash; if (!rb_obj_is_kind_of(self, RBTree)) rb_raise(rb_eTypeError, "can't convert MultiRBTree to Hash"); hash = rb_hash_new(); rbtree_for_each(self, to_hash_i, (void*)hash); RHASH_SET_IFNONE(hash, IFNONE(self)); if (FL_TEST(self, RBTREE_PROC_DEFAULT)) FL_SET(hash, HASH_PROC_DEFAULT); OBJ_INFECT(hash, self); return hash; }
VALUE rbtree_to_rbtree(VALUE self) { return self; }
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_obj_classname(other), rb_obj_classname(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; }
Retruns the key-value pair corresponding to the greatest key that is equal to or lower than the given key (inside the upper boundary). If there is no such key, returns nil.
rbtree = RBTree["az", 10, "ba", 20] rbtree.upper_bound("ba") # => ["ba", 20] # "az" is the greatest key that is lower than "b" rbtree.upper_bound("b") # => ["az", 10] # no key that is equal to or lower than "a" rbtree.upper_bound("a") # => nil
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 rbtree_has_value(VALUE self, VALUE value) { VALUE args[2]; args[0] = Qfalse; args[1] = value; rbtree_for_each(self, has_value_i, &args); return args[0]; }
VALUE rbtree_values(VALUE self) { VALUE ary = rb_ary_new2(dict_count(DICT(self))); rbtree_for_each(self, values_i, (void*)ary); return ary; }
VALUE rbtree_values_at(int argc, VALUE* argv, VALUE self) { long i; VALUE ary = rb_ary_new2(argc); for (i = 0; i < argc; i++) rb_ary_push(ary, rbtree_aref(self, argv[i])); return ary; }