Project

General

Profile

Feature #11315

[PATCH] Add Array#^ for parity with other set-like operations.

Added by 0x0dea (D.E. Akers) about 4 years ago. Updated about 4 years ago.

Status:
Open
Priority:
Normal
Assignee:
-
Target version:
-
[ruby-core:69762]

Description

Proposal

It is proposed that Array be given an "XOR" method which returns the symmetric difference between itself and another array.

Rationale

#& and #| need a friend to complete the set of set-like operations on Array.


Files

array_xor.patch (2.69 KB) array_xor.patch 0x0dea (D.E. Akers), 06/28/2015 02:22 PM
array_xor_vodka.patch (2.97 KB) array_xor_vodka.patch 0x0dea (D.E. Akers), 06/28/2015 05:03 PM
array_xor_recycle_seen.patch (3 KB) array_xor_recycle_seen.patch 0x0dea (D.E. Akers), 06/28/2015 05:07 PM

History

Updated by 0x0dea (D.E. Akers) about 4 years ago

The original implementation did not correctly handle the case of repeated elements occurring an even number of times in the second array. Attached is an updated version which does not present this defect, courtesy of apeiros (Stefan Rusterholz) and his 50-proof vodka.

Updated by 0x0dea (D.E. Akers) about 4 years ago

I forgot to recycle the seen hash. This last fix should finalize the patch, unless there is some very clever way to XOR two arrays without requiring two tables or a second pass through one of the arrays.

Updated by 0x0dea (D.E. Akers) about 4 years ago

  • Tracker changed from Bug to Feature

Updated by nobu (Nobuyoshi Nakada) about 4 years ago

st_update does lookup/replace/delete/insert in the callback at once.
And your patches are broken, necessary spaces are stripped.

diff --git a/array.c b/array.c
index 072e30d..737afa3 100644
--- a/array.c
+++ b/array.c
@@ -4200,6 +4200,14 @@ rb_ary_or(VALUE ary1, VALUE ary2)
     return ary3;
 }

+static int
+ary_hash_xorset(st_data_t *key, st_data_t *value, st_data_t arg, int existing)
+{
+    if (existing) return ST_DELETE;
+    *key = *value = (VALUE)arg;
+    return ST_CONTINUE;
+}
+
 /*
  *  call-seq:
  *     ary ^ other_ary     -> new_ary
@@ -4228,15 +4236,9 @@ rb_ary_xor(VALUE ary1, VALUE ary2)
     result = ary_make_hash(ary1);

     for (i = 0; i < RARRAY_LEN(ary2); ++i) {
-    elt = (st_data_t)RARRAY_AREF(ary2, i);
-    if (st_lookup(RHASH_TBL_RAW(seen), elt, 0)) continue;
-    st_update(RHASH_TBL_RAW(seen), elt, ary_hash_orset, elt);
-    if (st_lookup(RHASH_TBL_RAW(result), elt, 0)) {
-        st_delete(RHASH_TBL_RAW(result), &elt, 0);
-    }
-    else {
-        st_update(RHASH_TBL_RAW(result), elt, ary_hash_orset, elt);
-    }
+   elt = (st_data_t)RARRAY_AREF(ary2, i);
+   if (!st_update(RHASH_TBL_RAW(seen), elt, ary_hash_orset, elt))
+       st_update(RHASH_TBL_RAW(result), elt, ary_hash_xorset, elt);
     }

     ary3 = rb_hash_values(result);

Also available in: Atom PDF