{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import (\n",
    "    \"fmt\"\n",
    "    \"math/rand\"\n",
    "    \"sort\"\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "// Return leftmost offset where val can be inserted in sl while\n",
    "// maintaining sorted orter.  Assumes sl is sorted.\n",
    "func bisectLeftInt(sl []int, val int) int {\n",
    "    return sort.Search(len(sl), func(i int) bool {return sl[i] >= val})\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "// Same but for rightmost offset\n",
    "func bisectRightInt(sl []int, val int) int {\n",
    "    return sort.Search(len(sl), func(i int) bool {return sl[i] > val})\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "// Same as bisectLeftInt but where val and sl contain strings\n",
    "func bisectLeftStr(sl []string, val string) int {\n",
    "    return sort.Search(len(sl), func(i int) bool {return sl[i] >= val})\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "// Same but for rightmost offset\n",
    "func bisectRightStr(sl []string, val string) int {\n",
    "    return sort.Search(len(sl), func(i int) bool {return sl[i] > val})\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n"
     ]
    }
   ],
   "source": [
    "a := []int{1, 2, 3, 3, 3, 4, 5}\n",
    "bisectLeftInt(a, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n"
     ]
    }
   ],
   "source": [
    "bisectRightInt(a, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n"
     ]
    }
   ],
   "source": [
    "a = []int{2, 4, 6, 8, 10}\n",
    "bisectLeftInt(a, 5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n"
     ]
    }
   ],
   "source": [
    "bisectRightInt(a, 5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[61 71 6 70 39 55 13 19 33 71 1 72 15 34 62 72 77 52 23 95 29 9 86 40 28 50 31 59 25 62]\n"
     ]
    }
   ],
   "source": [
    "// Make a list of pseudo-random integers in [1, 99]\n",
    "rand.Seed(77)\n",
    "ls := make([]int, 30)\n",
    "for i := range ls {\n",
    "    ls[i] = rand.Intn(100) + 1\n",
    "}\n",
    "ls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1 6 9 13 15 19 23 25 28 29 31 33 34 39 40 50 52 55 59 61 62 62 70 71 71 72 72 77 86 95]\n"
     ]
    }
   ],
   "source": [
    "sort.Ints(ls)\n",
    "ls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n"
     ]
    }
   ],
   "source": [
    "// The number 30 is not in the sorted list\n",
    "// If it were, where would it go?\n",
    "val := 30\n",
    "insPt := bisectLeftInt(ls, val)\n",
    "insPt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1 6 9 13 15 19 23 25 28 29 30 31 33 34 39 40 50 52 55 59 61 62 62 70 71 71 72 72 77 86 95]\n"
     ]
    }
   ],
   "source": [
    "// Insert it\n",
    "ls = append(ls, 0)\n",
    "copy(ls[insPt+1:], ls[insPt:])\n",
    "ls[insPt] = val\n",
    "ls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "21\n"
     ]
    }
   ],
   "source": [
    "// 62 appears multiple times\n",
    "st := bisectLeftInt(ls, 62)\n",
    "en := bisectRightInt(ls, 62)\n",
    "st"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "23\n"
     ]
    }
   ],
   "source": [
    "en"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[62 62]\n"
     ]
    }
   ],
   "source": [
    "ls[st:en]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n"
     ]
    }
   ],
   "source": [
    "// Of course, there also exists a total ordering over strings\n",
    "// (lexicographical ordering), so we can do all the same things\n",
    "// with strings\n",
    "strls := []string{\"a\", \"awkward\", \"awl\", \"awls\", \"axe\", \"axes\", \"bee\"}\n",
    "st = bisectLeftStr(strls, \"awl\")\n",
    "en = bisectRightStr(strls, \"awl\")\n",
    "st"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    }
   ],
   "source": [
    "en"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "// Say we want to get the range of elements that have some prefix,\n",
    "// e.g. 'aw' and say that 'z' is the lexicographically greatest\n",
    "// character in the alphabet.\n",
    "st, en = bisectLeftStr(strls, \"aw\"), bisectLeftStr(strls, \"ax\")\n",
    "st"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n"
     ]
    }
   ],
   "source": [
    "en"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[awkward awl awls]\n"
     ]
    }
   ],
   "source": [
    "strls[st:en]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[$ a$ aaba$ aba$ abaaba$ ba$ baaba$]\n"
     ]
    }
   ],
   "source": [
    "// If we can do this for any sorted list of strings, we can do it for\n",
    "// a sorted list of suffixes\n",
    "t := \"abaaba$\"\n",
    "suffixes := []string{t, t[1:], t[2:], t[3:], t[4:], t[5:], t[6:]}\n",
    "sort.Strings(suffixes)\n",
    "suffixes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    }
   ],
   "source": [
    "// Search for suffixes starting with aba\n",
    "st = bisectLeftStr(suffixes, \"aba\")\n",
    "en = bisectLeftStr(suffixes, \"abb\")\n",
    "st"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n"
     ]
    }
   ],
   "source": [
    "en"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Go (lgo)",
   "language": "go",
   "name": "lgo"
  },
  "language_info": {
   "file_extension": "",
   "mimetype": "",
   "name": "go",
   "version": ""
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}