Changeset 2373

Timestamp:

01/23/11 15:44:03 (14 years ago)

Author:

andrei

Message:

findSplit, findSplitBefore, findSplitAfter

Files:

• trunk/phobos/std/algorithm.d (modified) (2 diffs)

trunk/phobos/std/algorithm.d

@@ -2982 +2982 @@
-assert(findSkip("abcdef", "cd") && s == "ef");
-s = "abcdef";
-assert(!findSkip("abcdef", "cxd") && s == "abcdef");
-assert(findSkip("abcdef", "def") && s.empty);
-----
- */
-bool findSkip(alias pred = "a == b", R1, R2)(ref R1 haystack, R2 needle)
-if (isForwardRange!R1 && isForwardRange!R2
-        && is(typeof(binaryFun!pred(haystack.front, needle.front))))
-{
-Parts
+Split
-    if (parts[1].empty) return false;
-    // found
-    haystack = parts[2];
-    return true;
-}
-
-unittest
-{
-    string s = "abcdef";
-    assert(findSkip(s, "cd") && s == "ef");
-    s = "abcdef";
-    assert(!findSkip(s, "cxd") && s == "abcdef");
-    s = "abcdef";
-    assert(findSkip(s, "def") && s.empty);
-}
-
-/**
-
-
-
-
-
+
+
+
+
+
+
+
+
- 
+$(D findSplitBefore) returns a tuple $(D result) containing two
+ranges. $(D result[0]) is the portion of $(D haystack) before $(D
+needle), and $(D result[1]) is the balance of $(D haystack) starting
+with the match. If $(D needle) was not found, $(D result[0])
+comprehends $(D haystack) entirely and $(D result[1]) is empty.
+
+$(D findSplitAfter) returns a tuple $(D result) containing two ranges.
+$(D result[0]) is the portion of $(D haystack) up to and including the
+match, and $(D result[1]) is the balance of $(D haystack) starting
+after the match. If $(D needle) was not found, $(D result[0]) is empty
+and $(D result[1]) is $(D haystack).
+
+In all cases, the concatenation of the returned ranges spans the
+entire $(D haystack).
+
-If $(D haystack) is a random-access range, all three components of the
-tuple have the same type as $(D haystack). Otherwise, $(D haystack)
-must be a forward range and the type of $(D result[0]) and $(D
-result[1]) is the same as $(XREF range,takeExactly).
-
-Example:
-----
-auto a = [ 1, 2, 3, 4, 5, 6, 7, 8 ];
-Parts
+Split
-assert(r[0] == a);
-assert(r[1].empty);
-assert(r[2].empty);
-Parts(a, [3
+Split(a, [ 3, 4 
-assert(r[0] == a[0 .. 2]);
-
-
+
+
+
+
+
+
+
+
-----
- */
-Parts
+Split
-if (isForwardRange!R1 && isForwardRange!R2)
-{
-    static if (isSomeString!R1 && isSomeString!R2
-            || isRandomAccessRange!R1 && hasLength!R2)
-    {
-        auto balance = find!pred(haystack, needle);
-        immutable pos1 = haystack.length - balance.length;
-length ? pos1 + needle.length : pos1
+empty ? pos1 : pos1 + needle.length
-        return tuple(haystack[0 .. pos1],
-                haystack[pos1 .. pos2],
-                haystack[pos2 .. haystack.length]);
-    }
-    else
-    {
-        auto original = haystack.save;
-        auto h = haystack.save;
-        auto n = needle.save;
-        size_t pos1, pos2;
@@ -3060 +3084 @@
-            }
-            else
-            {
-                haystack.popFront();
-                n = needle.save;
-                h = haystack.save;
-                pos2 = ++pos1;
-            }
-        }
-        return tuple(takeExactly(original, pos1),
-
+ - pos1
-                h);
-    }
-}
-
+/// Ditto
+auto findSplitBefore(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle)
+if (isForwardRange!R1 && isForwardRange!R2)
+{
+    static if (isSomeString!R1 && isSomeString!R2
+            || isRandomAccessRange!R1 && hasLength!R2)
+    {
+        auto balance = find!pred(haystack, needle);
+        immutable pos = haystack.length - balance.length;
+        return tuple(haystack[0 .. pos], haystack[pos .. haystack.length]);
+    }
+    else
+    {
+        auto original = haystack.save;
+        auto h = haystack.save;
+        auto n = needle.save;
+        size_t pos;
+        while (!n.empty && !h.empty)
+        {
+            if (binaryFun!pred(h.front, n.front))
+            {
+                h.popFront();
+                n.popFront();
+            }
+            else
+            {
+                haystack.popFront();
+                n = needle.save;
+                h = haystack.save;
+                ++pos;
+            }
+        }
+        return tuple(takeExactly(original, pos), haystack);
+    }
+}
+
+/// Ditto
+auto findSplitAfter(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle)
+if (isForwardRange!R1 && isForwardRange!R2)
+{
+    static if (isSomeString!R1 && isSomeString!R2
+            || isRandomAccessRange!R1 && hasLength!R2)
+    {
+        auto balance = find!pred(haystack, needle);
+        immutable pos = balance.empty ? 0 : haystack.length - balance.length + needle.length;
+        return tuple(haystack[0 .. pos], haystack[pos .. haystack.length]);
+    }
+    else
+    {
+        auto original = haystack.save;
+        auto h = haystack.save;
+        auto n = needle.save;
+        size_t pos1, pos2;
+        while (!n.empty)
+        {
+            if (h.empty)
+            {
+                // Failed search
+                return tuple(takeExactly(original, 0), original);
+            }
+            if (binaryFun!pred(h.front, n.front))
+            {
+                h.popFront();
+                n.popFront();
+                ++pos2;
+            }
+            else
+            {
+                haystack.popFront();
+                n = needle.save;
+                h = haystack.save;
+                pos2 = ++pos1;
+            }
+        }
+        return tuple(takeExactly(original, pos2), h);
+    }
+}
+
-unittest
-{
-    auto a = [ 1, 2, 3, 4, 5, 6, 7, 8 ];
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-    assert(equal(r[0], a));
-    assert(r[1].empty);
-    assert(r[2].empty);
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-}
-
-/**
-If $(D haystack) supports slicing, returns the smallest number $(D n)
-such that $(D haystack[n .. $].startsWith!pred(needle)). Oherwise,
-returns the smallest $(D n) such that after $(D n) calls to $(D
-haystack.popFront), $(D haystack.startsWith!pred(needle)). If no such
-number could be found, return $(D -1).
- */
-sizediff_t countUntil(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle)