AppPkg/Applications/Python/Python-2.7.10: Initial Checkin part 4/5.

[mirror_edk2.git] / AppPkg / Applications / Python / Python-2.7.10 / Lib / bisect.py

diff --git a/AppPkg/Applications/Python/Python-2.7.10/Lib/bisect.py b/AppPkg/Applications/Python/Python-2.7.10/Lib/bisect.py
new file mode 100644 (file)
index 0000000..d1016d9
--- /dev/null
+++ b/AppPkg/Applications/Python/Python-2.7.10/Lib/bisect.py
@@ -0,0 +1,92 @@
+"""Bisection algorithms."""\r
+\r
+def insort_right(a, x, lo=0, hi=None):\r
+    """Insert item x in list a, and keep it sorted assuming a is sorted.\r
+\r
+    If x is already in a, insert it to the right of the rightmost x.\r
+\r
+    Optional args lo (default 0) and hi (default len(a)) bound the\r
+    slice of a to be searched.\r
+    """\r
+\r
+    if lo < 0:\r
+        raise ValueError('lo must be non-negative')\r
+    if hi is None:\r
+        hi = len(a)\r
+    while lo < hi:\r
+        mid = (lo+hi)//2\r
+        if x < a[mid]: hi = mid\r
+        else: lo = mid+1\r
+    a.insert(lo, x)\r
+\r
+insort = insort_right   # backward compatibility\r
+\r
+def bisect_right(a, x, lo=0, hi=None):\r
+    """Return the index where to insert item x in list a, assuming a is sorted.\r
+\r
+    The return value i is such that all e in a[:i] have e <= x, and all e in\r
+    a[i:] have e > x.  So if x already appears in the list, a.insert(x) will\r
+    insert just after the rightmost x already there.\r
+\r
+    Optional args lo (default 0) and hi (default len(a)) bound the\r
+    slice of a to be searched.\r
+    """\r
+\r
+    if lo < 0:\r
+        raise ValueError('lo must be non-negative')\r
+    if hi is None:\r
+        hi = len(a)\r
+    while lo < hi:\r
+        mid = (lo+hi)//2\r
+        if x < a[mid]: hi = mid\r
+        else: lo = mid+1\r
+    return lo\r
+\r
+bisect = bisect_right   # backward compatibility\r
+\r
+def insort_left(a, x, lo=0, hi=None):\r
+    """Insert item x in list a, and keep it sorted assuming a is sorted.\r
+\r
+    If x is already in a, insert it to the left of the leftmost x.\r
+\r
+    Optional args lo (default 0) and hi (default len(a)) bound the\r
+    slice of a to be searched.\r
+    """\r
+\r
+    if lo < 0:\r
+        raise ValueError('lo must be non-negative')\r
+    if hi is None:\r
+        hi = len(a)\r
+    while lo < hi:\r
+        mid = (lo+hi)//2\r
+        if a[mid] < x: lo = mid+1\r
+        else: hi = mid\r
+    a.insert(lo, x)\r
+\r
+\r
+def bisect_left(a, x, lo=0, hi=None):\r
+    """Return the index where to insert item x in list a, assuming a is sorted.\r
+\r
+    The return value i is such that all e in a[:i] have e < x, and all e in\r
+    a[i:] have e >= x.  So if x already appears in the list, a.insert(x) will\r
+    insert just before the leftmost x already there.\r
+\r
+    Optional args lo (default 0) and hi (default len(a)) bound the\r
+    slice of a to be searched.\r
+    """\r
+\r
+    if lo < 0:\r
+        raise ValueError('lo must be non-negative')\r
+    if hi is None:\r
+        hi = len(a)\r
+    while lo < hi:\r
+        mid = (lo+hi)//2\r
+        if a[mid] < x: lo = mid+1\r
+        else: hi = mid\r
+    return lo\r
+\r
+# Overwrite above definitions with a fast C implementation\r
+try:\r
+    from _bisect import *\r
+except ImportError:\r
+    pass\r