# The beginning of a personal implementation of linked lists
# in Elixir. Realistically, this is a stupid thing to do as
# the native language implementation is certainly superior
# in EVERY way
# But as a way to explore the language, probably good.
# Author: gtowell
# Created: August 2022

defmodule Nde do
  @moduledoc """
  A module mostly to define a node struct for my linked list
  as to provide a printer for the node structure.  The node
  is dead simple, just a payload and a forward pointer
  """
  defstruct payload: nil, next: nil

  # This is effectively the same as the toString function in Java.
  defimpl String.Chars do
    def to_string(item) do
      "#{item.payload}"
    end
  end

end

defmodule LiLi do
  @moduledoc """
  A structure for LinkedLists. Perhaps this structure could
  also have a length variable, but everything else seems
  useless under immutability.  Indeed this whole module
  is of dubious utility except as a gathering point for
  all of the linked list functions
  Note that the structure is pretty useless, just a nde and the number of nodes in the linked list
  """
  defstruct thehead: nil, thelength: 0

  @doc """
  Create an empty linked list.   Needed? As things are written
  yes it is convenient.
  Could alter the add_first and append functions to
  make this wholly unnecessary
  """
  def create() do
    %LiLi{thehead: nil, thelength: 0}
  end

  @doc """
  The head element of this linked list.
  This will only match to this linked list struct
  Could possibly have a second thing that says "not
  applicable" to prevent a program from dieing.
  Note "lili = %LiLi{}" can be read as "match only to
  an instance of LiLi and then bind that matched thing
  to the variable lili
  """
  def head(lili = %LiLi{}) do
    lili.thehead
  end

  @doc """
  The linked list without the head.
  Here the parameter "%LiLi{thehead: the_head, thelength: len}
  is interpreted as match only to an instance of LiLi and then
  bind the_head to the value of the match item thehead and
  bind len to the matched item thelength value
  Matching is crazy!
  """
  def rest(%LiLi{thehead: the_head, thelength: len}) do
    %LiLi{thehead: the_head.next, thelength: (len-1)}
  end

  @doc """
  Add one item to the front of the linked list
  Note that this returns a new linked list
  but that all of the elments in the original linked list
  are used.
  """
  def add_front(nw, lili) do
    %LiLi{thehead: %Nde{payload: nw, next: lili.thehead}, thelength: lili.thelength+1}
  end

  @doc """
  Add one item to the tail of this linked list
  This implementation is poor for the following
  reasons:
  1. It is quite inefficient in that
  it creates new Ndes for everything in the linked
  list being appended to. It should be possible to
  just use the original linked list.
  2. If you use the Tail-Rec version (i_append) then the first
  list is reversed. The non-tail-rec version does not reverse the first list

  the argument "second_lili=%LiLi{}" says, roughly, match to only
  things of type LiLi
    """
  def append(first_lili=%LiLi{}, second_lili=%LiLi{}) do
    # this version appends two lists together
    ii_append(first_lili.thehead, second_lili)
  end

  def append(lili=%LiLi{}, nw) do
    # this version appends a random piece of data to the end of a list
    # It does so by making a list of the random piece of data
    tl = %LiLi{thehead: %Nde{payload: nw, next: nil}, thelength: 1}
    ii_append(lili.thehead, tl)
  end


  #private function do actually do the work of appending
  # this version is tail recursive which is fast but
  # has the problem of reversing the first list
  defp i_append(nil, nnde, cnt) do
    %LiLi{thehead: nnde, thelength: cnt}
  end
  defp i_append(onde, nnde, cnt) do
    i_append(onde.next, %Nde{payload: onde.payload, next: nnde}, cnt+1)
  end


  # private function do actually do the work of appending
  # this version is NOT tail recursive which is slower but
  # has the advantage of maintaining order
  defp ii_append(nil, lst2) do
    %LiLi{thehead: lst2.thehead, thelength: lst2.thelength}
  end
  defp ii_append(onde, lst2) do
    aa = ii_append(onde.next, lst2)
    %LiLi{thehead: %Nde{payload: onde.payload, next: aa.thehead}, thelength: aa.thelength+1}
  end

  # This is effectively the same as the toString function in Java.
  defimpl String.Chars do
    def to_string(item) do
      i_printer(item.thehead, "Length: #{item.thelength} [[")
    end

    def i_printer(nil, acc) do
      "#{acc} ]]"
    end

   def i_printer(anode, acc) do
     i_printer(anode.next, "#{acc} #{if String.length(acc)>14 do "-->" else "" end} #{anode}")
   end
   end

  def main do
    aa=create()
    aa = add_front("1", aa)
    IO.puts(aa)
    bb = add_front("2", aa)
    IO.puts(bb)
    cc = add_front("a", bb)
    IO.puts(cc)
    IO.puts cc.thelength
    dd = add_front("b", cc)
    IO.puts(dd)
    IO.puts(dd.thelength)
    ee = append(dd, "skiff" )
    IO.puts(ee)
    ff = append(dd, cc)
    IO.puts(ff)
    IO.puts "head #{head(ff)}"
  end
end

LiLi.main