[Issue 10131] New: To remove duplicates and keep order

[d-bugmail at puremagic.com]

http://d.puremagic.com/issues/show_bug.cgi?id=10131

           Summary: To remove duplicates and keep order
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: Phobos
        AssignedTo: nobody at puremagic.com
        ReportedBy: bearophile_hugs at eml.cc


--- Comment #0 from bearophile_hugs at eml.cc 2013-05-21 16:59:50 PDT ---
I suggest to add to Phobos a function with semantics similar to this one, that
sometimes I find useful:


T[] noDupes(T)(in T[] s) {
    import std.algorithm: canFind;
    T[] result;
    foreach (T c; s)
        if (!result.canFind(c))
            result ~= c;
    return result;
}

void main() {
    import std.string: squeeze;
    assert("AAAA".noDupes == "A");
    assert("AAAA".squeeze == "A");
    assert("ABAC".noDupes == "ABC");
    assert("ABAC".squeeze == "ABAC");
}


Notes:
- It's related to std.string.squeeze and std.algorithm.uniq, but they need the
items to be sorted to remove all the duplicates, while the function discussed
here doesn't change the order of the items.
- The implementation shown here is slow, O(n^2), because it's meant to just
show the semantics clearly. If the items are hashable it's possible to create a
O(n) implementation, storing the items in a hash. If the items are comparable
it's possible to write a O(n ln n) version that creates an array of sorted
pointers and then performs binary searches on it. The O(n^2) version is a
fallback if the items are not hashable nor comparable. The three versions are
meant to be three parts of the same general function.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------