{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "5786b096",
   "metadata": {},
   "source": [
    "## Elias Fano encoding"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "521222af",
   "metadata": {},
   "outputs": [],
   "source": [
    "# sample implementation of Elias-Fano code\n",
    "# Use\n",
    "#  ef_build(a,u,verbose)\n",
    "# to compute the Elias-Fano representation \n",
    "# of the integers in a (must be increasing and non-negative). \n",
    "# u is an upper bound to the max of a, if not given we set u=max(a)+1  \n",
    "# \n",
    "# For testing purposes:\n",
    "#   create_set(n,u)\n",
    "# create a set containing n randomly selected \n",
    "# increasing integers in [0,u)\n",
    "\n",
    "\n",
    "# return the bitarrays (represented as strings)\n",
    "# L and H associated to the integers in a[]\n",
    "def ef_build(a,u = -1, verbose=False):\n",
    "  assert len(a)>0\n",
    "  if u<0:\n",
    "    u = 1 + max(a)\n",
    "  else: \n",
    "    assert u > max(a), \"Invalid u parameter\"   \n",
    "  n = len(a)\n",
    "  log_u = bits(u)\n",
    "  ell = int(math.ceil(math.log(u/n,2)))\n",
    "  # number of necessary buckets \n",
    "  buckets = math.ceil(u/(2**ell))\n",
    "  print(f\"n={n}, u={u}, log(u)={log_u}, ell={ell}, #buckets={buckets}\")\n",
    "  # for debug purposes print binary representation of input\n",
    "  if verbose:\n",
    "    print(\"Binary representation:\\n  \",list2bin(a,log_u))\n",
    "  # compute L bitvector with ell less significant bits\n",
    "  # of each entry\n",
    "  Llist = [ dec2bin(i%(2**ell),ell) for i in a]\n",
    "  if verbose:\n",
    "    print(\"Less significant bits:\\n  \",Llist) \n",
    "  # compute L\n",
    "  L = \"\".join(Llist)\n",
    "  assert(len(L)==n*ell)\n",
    "  # compute bucket id for each value\n",
    "  Hvalues = [i >> ell for i in a] # i//(2**ell)\n",
    "  if verbose:\n",
    "    print(\"Bucket ids:\\n  \", Hvalues)\n",
    "  # build H using array count() method\n",
    "  H = \"\"\n",
    "  for i in range(buckets):\n",
    "    H += Hvalues.count(i)*\"1\" + \"0\"\n",
    "  assert(len(H) == n+buckets)\n",
    "  return L, H, ell\n",
    "\n",
    "# access the i-th element of the original array\n",
    "# the index i is 1-based\n",
    "def access(L,H,ell,i):\n",
    "  assert i>0, \"Invalid index\"\n",
    "  lowbits = L[(i-1)*ell:i*ell]\n",
    "  bucket = select(H,1,i) - i\n",
    "  return bucket * 2**ell + bin2dec(lowbits)\n",
    "\n",
    "\n",
    "# return the pair (i,v) where v is the i-th (1-based)\n",
    "# element of the set and v is the smallest value\n",
    "# in the set which is >= x\n",
    "# return (-1,-1) is the set contains no value >= x\n",
    "def nextGEQ(L,H,ell,x,verbose=True):\n",
    "  assert x>=0\n",
    "  bx = x >> ell         # bucket that would contain x \n",
    "  if bx>0: \n",
    "    j =select(H,0,bx)+1 # first bit of bucket bx>0\n",
    "  else:\n",
    "    j = 1               # bucket 0 starts at position 1 \n",
    "  if(j<=0):             # j is invalid, ie x>= u\n",
    "    return (-1,-1)      # there is no value => x   \n",
    "  if verbose:  \n",
    "    print(f\"The first bit of bucket {bx} is in pos {j}\") \n",
    "    if H[j-1]=='0':\n",
    "        print(f\"since H({j}) (1-based) is 0, the bucket is empty\")\n",
    "  # scan the elements of bucket bx, if any\n",
    "  while H[j-1]=='1':\n",
    "    i = j - bx       # there are i-1 1's in H[1..j]\n",
    "    v = (bx<< ell) + bin2dec(L[(i-1)*ell:i*ell])\n",
    "    if v>=x:         # found element >= x \n",
    "      return (i ,v)  # return its position and its value \n",
    "    j += 1           # linear scan ot the 1's; binary search is also possilbe \n",
    "  # now we have reached the end of bucket bx\n",
    "  assert(H[j-1]=='0')\n",
    "  i = j - bx            # there are i-1 1's in H[1..j] \n",
    "  next1 = select(H,1,i) # position of the i-th 1  \n",
    "  if next1 == -1:       # there is no i-th element\n",
    "    return (-1, -1)     # x is larger than all set elements \n",
    "  # the desired value is the one in position i+1        \n",
    "  return i, access(L,H,ell,i) \n",
    "\n",
    "# test nextGEQ() function on a random set  \n",
    "def test_set(n,u):\n",
    "  y = create_set(n,u)\n",
    "  print(y)\n",
    "  L,H,ell = ef_build(y,False)\n",
    "  for j in range(0,y[0]+1):\n",
    "    ij,vj = nextGEQ(L,H,ell,j,False)\n",
    "    assert ij== 1\n",
    "    assert vj == y[0]       \n",
    "  for i in range(n-1):\n",
    "    for j in range(y[i]+1,y[i+1]+1):\n",
    "      ij,vj = nextGEQ(L,H,ell,j,False)\n",
    "      assert ij== i+2, f\"j={j} a\"\n",
    "      assert vj == y[i+1], f\"j={j} b\"\n",
    "  for j in range(y[-1]+1,y[-1]+10):\n",
    "    ij,vj = nextGEQ(L,H,ell,j,False)\n",
    "    assert ij== -1\n",
    "    assert vj == -1     \n",
    "  print(\"Done!\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dee01db1",
   "metadata": {},
   "source": [
    "**Auxiliary functions**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "49ff7874",
   "metadata": {},
   "outputs": [],
   "source": [
    "import math, random \n",
    "\n",
    "# select function for a binary string\n",
    "# return the index 1-based of the ith occurrence of d\n",
    "def select(s,d,i):\n",
    "  assert i>0, \"Invalid index\"\n",
    "  assert d==0 or d==1, \"Invalid bit\"\n",
    "  if d==0: c='0'\n",
    "  else: c='1'\n",
    "  # check there are at least i c's\n",
    "  tot = s.count(c)\n",
    "  if i>tot:\n",
    "    return -1\n",
    "  found = 0  \n",
    "  for j in range(len(s)):\n",
    "    if s[j]==c:\n",
    "      found += 1\n",
    "      if found==i:\n",
    "        return j+1 # +1 because we are 1-based \n",
    "  assert False,\"Something is wrong\"\n",
    "  \n",
    "\n",
    "# create a sorted sequence of n values in [0,u)\n",
    "def create_set(n,u):\n",
    "  a = random.sample(range(u),n)\n",
    "  a.sort()\n",
    "  return a\n",
    "  \n",
    "\n",
    "# convert n to binary using at least d bits  \n",
    "def dec2bin(n,d=8):\n",
    "  assert n>=0\n",
    "  return f\"{n:0{d}b}\"\n",
    "\n",
    "# convert a list of integers to binary using at least d bits\n",
    "def list2bin(lis,d=8):\n",
    "  return [dec2bin(i,d) for i in lis]\n",
    "\n",
    "# convert from binary \n",
    "def bin2dec(s):\n",
    "    return int(s, 2)\n",
    "\n",
    "# number of bits required to encode k different values\n",
    "def bits(k):\n",
    "    assert k > 0\n",
    "    if k == 1:\n",
    "        return 0\n",
    "    bits = 1\n",
    "    values = 2  # 1 bit -> 2 values\n",
    "    while values < k:\n",
    "        bits += 1\n",
    "        values *= 2\n",
    "    return bits"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "43ef4042",
   "metadata": {},
   "source": [
    "**Sample queries**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "eda7ea1b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "n=10, u=60, log(u)=6, ell=3, #buckets=8\n",
      "Binary representation:\n",
      "   ['000010', '000110', '001001', '001101', '001111', '010100', '011001', '101000', '101010', '110010']\n",
      "Less significant bits:\n",
      "   ['010', '110', '001', '101', '111', '100', '001', '000', '010', '010']\n",
      "Bucket ids:\n",
      "   [0, 0, 1, 1, 1, 2, 3, 5, 5, 6]\n",
      "010110001101111100001000010010 110111010100110100 3 48\n"
     ]
    }
   ],
   "source": [
    "a = [2, 6, 9, 13, 15, 20, 25, 40, 42, 50]\n",
    "L,H,ell = ef_build(a,60,True)\n",
    "print(L,H,ell,len(L)+len(H))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "3ec18feb",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "20"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# access the 6-th element (1-based)\n",
    "access(L,H,ell,6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "f7a900dc",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The first bit of bucket 4 is in pos 12\n",
      "Since H(12) (1-based) is 0, the bucket is empty\n",
      "The desired element is in position: 8, value: 40\n"
     ]
    }
   ],
   "source": [
    "# get element GEQ 33\n",
    "i,v = nextGEQ(L,H,ell,33,True)\n",
    "print(f\"The desired element is in position: {i}, value: {v}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "712c20d1",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The first bit of bucket 1 is in pos 4\n",
      "The desired element is in position: 4, value: 13\n"
     ]
    }
   ],
   "source": [
    "# get element GEQ 12\n",
    "i,v =  nextGEQ(L,H,ell,12,True)\n",
    "print(f\"The desired element is in position: {i}, value: {v}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2e92ac70",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}