Polylix

Artifact Content
Login

Artifact 3a681934befb3166ab129ff79824373f7650e63b:


defmodule Polylix do
  require Bitwise
#-export([decode/1, eight_bit_chunks/1, six_bit_chunks/1, six_bit_chunk/1, split_up_six_bits/1, five_bit_chunks/1, bin_flip/1]).

#See https://developers.google.com/maps/documentation/utilities/polylinealgorithm


  #Note: Decodes into co-ordinate offsets as opposed to absolute
  def decode(encoded_polyline) do
    #Steps 11 back to 8
    six_bit_chunks = six_bit_chunks(encoded_polyline)
    #Step 8
    groups_of_chunks_list = split_up_six_bits(six_bit_chunks)
    #Step 8 back to 6
    five_bit_chunks = five_bit_chunks(groups_of_chunks_list)
    #---TODO
    #Maybe some more of the below need splitting out into different functions or nesting in a map?
    #Which option to go for, a function that maps as per five_bit_chunks, or mapping functions as per below?
    #I don't think I can map all functions in one go because ultimately need to change number of members in groups.
    #I.e. following will go from groups of five to eight.
    #---
    #Step 5
    eight_bit_chunks = Enum.map(
      five_bit_chunks,
      fn(group_of_chunks) ->
        eight_bit_chunks(group_of_chunks)
      end)
    results = Enum.map(
      eight_bit_chunks,
      fn(group_of_chunks) ->
        #TODO These should probably be separate functions, rather than one long mess inside a map
        last_bit = [hd(Enum.reverse(hd(Enum.reverse(group_of_chunks))))]
        flipped_chunks = Enum.map(
          group_of_chunks,
          fn(chunk) ->
            bin_flip_(chunk, [])
          end)
        #Step 5
        chunks = if last_bit === '1' do
          flipped_chunks
        else
          group_of_chunks
        end
        {ok, [flattened_binary], []} = :io_lib.fread('~2u', Enum.flat_map(chunks, fn(x) -> x end))
        #Step 4
        shifted_binary = Bitwise.bsr(flattened_binary,1)
        #Since bin_flip returns a string need to then change back to a number
        {ok, [shifted_binary_], []} = :io_lib.fread('~2u', bin_flip(shifted_binary - 1))
        #Step 3
        final_binary = if last_bit === '1' do
          shifted_binary_;
        else
          shifted_binary
        end
        #Step 2 back to 1
        decoded = if last_bit === '1' do
          -1 * final_binary/100000
        else
          final_binary/100000
        end
        decoded
      end)
    results
  end


#Step 8 - Split up six bit chunks, per the 0x20 bit
  def split_up_six_bits(bit_chunks_list) do
    split_up_six_bits_(bit_chunks_list, [], [])
  end
  defp split_up_six_bits_([head | tail], group_of_bit_chunks, groups_of_bit_chunks_list) when [hd(head)] == '1' do
    split_up_six_bits_(tail, [head]++group_of_bit_chunks, groups_of_bit_chunks_list)
  end
  defp split_up_six_bits_([head | tail], group_of_bit_chunks, groups_of_bit_chunks_list) when [hd(head)] == '0' do
    #Then need to start a new list, but after this 0 one!
    split_up_six_bits_(tail, [], [Enum.reverse([head]++group_of_bit_chunks)]++groups_of_bit_chunks_list)
  end
  defp split_up_six_bits_([], group_of_bit_chunks, groups_of_bit_chunks_list) when length(group_of_bit_chunks) > 0 do
    split_up_six_bits_([], [], [Enum.reverse(group_of_bit_chunks)]++groups_of_bit_chunks_list)
  end
  defp split_up_six_bits_([], [], groups_of_bit_chunks_list) do
    #TODO Might be neater to map lists:reverse over the list instead of doing above and here.
    Enum.reverse(groups_of_bit_chunks_list)
  end


##Step 5
##TODO See if better way of doing this, especially using Elixir's Enum.chunk
  def eight_bit_chunks(five_bit_chunks_list) do
    #Could call :lists.flatten, but the below flat_map keeps things Elixir
    five_bit_chunk_string = Enum.reverse(Enum.flat_map(five_bit_chunks_list, fn(x) -> x end))
    eight_bit_chunks_(five_bit_chunk_string, [])
  end
  defp eight_bit_chunks_(five_bit_chunk_string, eight_bit_chunks_list) when length(five_bit_chunk_string) > 8 do
    eight_bit_chunk = Enum.reverse(Enum.slice(five_bit_chunk_string,0,8))
    rest_of_five_bit_chunk_string = Enum.slice(five_bit_chunk_string, 8..-1)
    eight_bit_chunks_(rest_of_five_bit_chunk_string, [eight_bit_chunk]++eight_bit_chunks_list)
  end
  defp eight_bit_chunks_(five_bit_chunk_string, eight_bit_chunks_list) when length(five_bit_chunk_string) <= 8 and five_bit_chunk_string != [] do
    padded_bit_string = pad_to(8, Enum.reverse(five_bit_chunk_string))
    eight_bit_chunks_([], [padded_bit_string]++eight_bit_chunks_list)
  end
  defp eight_bit_chunks_([], eight_bit_chunks_list) do
    eight_bit_chunks_list
  end


  def six_bit_chunks(encoded_polyline) do
    six_bit_chunks_(encoded_polyline, [])
  end
  defp six_bit_chunks_([head | rest], chunks_list) do
    six_bit_chunk = six_bit_chunk(head)
    #Add to Reversed_chunks
    six_bit_chunks_(rest, [six_bit_chunk]++chunks_list)
  end
  defp six_bit_chunks_([], chunks_list) do
    Enum.reverse(chunks_list)
  end


  def six_bit_chunk(ascii_bit) do
    #Step 10
    shifted_bit = ascii_bit - 63
    #Step 9
    #From http://erlangcentral.org/wiki/index.php/Converting_Between_Binary_and_Decimal
    binary_chunk = hd(:io_lib.format("~.2B", [shifted_bit]))
    #---TODO
    #What if Binary_chunk is shorter than 6?
    #Well in that case, I guess that means we'd want to split, but for now pad to six and check for 0x20 elsewhere.
    #---
    pad_to(6, binary_chunk)
  end


  def five_bit_chunks(groups_of_chunks_list) do
    Enum.map(
      groups_of_chunks_list,
      fn(group_of_chunks) ->
        #Step 7 - Un-reverse the five bit chunks
        Enum.reverse(Enum.map(
          group_of_chunks,
          fn(chunk) ->
            #Step 8 - "Un-or" the 0x20 bit
            Enum.slice(chunk,1,5)
          end))
      end)
  end


##I can't figure out padding with io:format etc when printing binary numbers
  def pad_to(length, binary_string) when length(binary_string) < length do
    padded_binary_string = '0'++binary_string
    pad_to(length, padded_binary_string)
  end
  def pad_to(length, binary_string) when length(binary_string) == length do
    binary_string
  end


  #bnot doesn't seem to work as I thought it would so do it very inelegantly by switching each "bit" in a string.
  def bin_flip(binary_number) do
    binary_string = hd(:io_lib.format("~.2B", [binary_number]))
    bin_flip_(binary_string, [])
  end
  defp bin_flip_([head | rest], flipped_string) do
    head_bit = hd(:io_lib.format("~c",[head]))
    flipped_bit = if head_bit === '0' do
      '1'
    else
      '0'
    end
    bin_flip_(rest, flipped_bit++flipped_string)
  end
  defp bin_flip_([], flipped_string) do
    Enum.reverse(flipped_string)
  end

end

#Notes
  #Elixir:
    #Entering binary numbers 0b101010
    #Single quotes vs double quotes. Erlang: hd("101010") vs Elixir: hd('101010')
  #Erlang:
  #0x1f is 31, 0x20 is 32
  #Need to ensure functions are tail recursive
  #To convert to integer, just need to do $<char>
  #just do hd(String) will come as a number
  #Last = hd(io_lib:format("~c", [hd(lists:reverse(hd(io_lib:format("~.2B", [Binary_number]))))])),
  #{ok, Almost_flipped, _} = io_lib:fread("~2u",Almost_flipped_string),