   Custom pretty printers can be implemented using
   functions, exported from this module.
 
+  Elixir implementation of the Wadler document algebra as described in 
+  "Strictly Pretty" (2000) by Christian Lindig
+  http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.2200
+   
+  The original Haskell implementation of the algorithm relies on lazy 
+  evaluation to unfold document groups on two alternatives:
+  _flat_ (breaks as spaces) and _broken_ (breakes as newlines).
+  Implementing the same logic on a strict language such as Elixir leads
+  to an exponential growth of the possible documents, unless document
+  groups are encoded explictly as _flat_ or _broken_. Those groups are
+  then reduced to a simple document, where the layout is already decided.
+
   ## Examples
 
     iex> Wadler.text "foo"                      
-    Wadler.TEXT[string: "foo"]
-    
-    iex> Wadler.group(Wadler.concat(Wadler.text("1"), Wadler.concat(Wadler.line, Wadler.text("2"))))
-    Wadler.UNION[
-      left: Wadler.CONCAT[
-        left: Wadler.TEXT[string: "1"], 
-        right: Wadler.CONCAT[left: Wadler.TEXT[string: " "], right: Wadler.TEXT[string: "2"]] 
-      ], 
-      right: Wadler.CONCAT[
-        left: Wadler.TEXT[string: "1"], 
-        right: Wadler.CONCAT[left: LINE, right: Wadler.TEXT[string: "2"]]
-      ]
-    ]
-
-  """
-
-  # Records to work with variant document representation
-  # Those are generalized by `docentity` type.
-  # Note that function that returns atom NIL is called `null`
-  @type docentity :: TEXT.t | CONCAT.t | UNION.t | NEST.t | GLUE.t | NIL | LINE
-  defrecord TEXT, string: ""
-  defrecord CONCAT, left: nil, right: nil
-  defrecord UNION, left: nil, right: nil
-  defrecord NEST, indent: 1, rest: nil
-  defrecord GLUE, string: "" 
-
-  # Records that represent finalized entities in a document
-  # Those are generalized by `docfactor` type.
-  @type docfactor :: Text.t | Line.t | Nil
-  defrecord Text, string: "", rest: nil
-  defrecord Line, indent: 0,  rest: nil
-
-  # Functional interface to `docentity` records
-  @doc """
-  Returns NIL which is a document entity used to represent
+    Wadler.DocText[str: "foo"]
+    
+    iex> doc = Wadler.group(Wadler.concat(Wadler.text("1"), Wadler.concat(Wadler.break, Wadler.text("2"))))
+    Wadler.DocGroup[
+      doc: Wadler.DocCons[
+        left: Wadler.DocText[str: "1"], 
+        right: Wadler.DocCons[
+          left: Wadler.DocBreak[str: " "], 
+          right: Wadler.DocText[str: "2"]
+        ]
+      ]
+    ]
+
+    iex> sdoc = Wadler.format w, 0, [{0, Wadler.Flat, doc}]
+    Wadler.SText[
+      str: "1", 
+      sdoc: Wadler.SText[
+        str: " ", 
+        sdoc: Wadler.SText[
+          str: "2",
+          sdoc: SNil
+        ]
+      ]
+    ]
+
+
+  """
+
+  # some shortcut functions
+  defp newline, do: "\n"
+  defp strlen(s), do: String.length(s)
+
+  defp repeat(_, 0), do: ""
+  defp repeat(s, i), do: String.duplicate s, i
+
+  # Records representing a __complex__ document
+  @type doc :: DocNil | DocCons.t | DocText.t | DocNest.t | DocBreak.t | DocGroup.t
+  defrecord DocCons, left: DocNil, right: DocNil
+  defrecord DocText, str: ""
+  defrecord DocNest, indent: 1, doc: DocNil
+  defrecord DocBreak, str: " "
+  defrecord DocGroup, doc: DocNil
+
+  # Functional interface to `doc` records
+  @doc """
+  Returns DocNil which is a document entity used to represent
   nothingness. Takes no arguments.
 
   ## Examples
 
-    iex> Wadler.null
-    NIL
-
-  """
-  @spec null() :: NIL
-  def null, do: NIL
+    iex> Wadler.empty
+    DocNil
+
+  """
+  @spec empty() :: DocNil
+  def empty, do: DocNil
 
   @doc """
   Concatenates two document entities. Takes two arguments:
-  left docentity and right docentity. Returns CONCAT 
-  docentity.
+  left doc and right doc. Returns a DocCons doc
 
   ## Examples
     
     iex(1)> Wadler.concat Wadler.text("Tasteless"), Wadler.text("Artosis")
-    Wadler.CONCAT[left: Wadler.TEXT[string: "Tasteless"], right: Wadler.TEXT[string: "Artosis"]]  
+    Wadler.DocCons[left: Wadler.DocText[str: "Tasteless"], right: Wadler.DocText[str: "Artosis"]]  
 
     iex(2)> IO.puts Wadler.pretty(80, v(1))
     TastelessArtosis
     :ok
 
   """
-  @spec concat(docentity, docentity) :: CONCAT.t
-  def concat(x, y), do: CONCAT[left: x, right: y]
+  @spec concat(doc, doc) :: DocCons.t
+  def concat(x, y), do: DocCons[left: x, right: y]
+  
 
   @doc """
   Nests document entity x positions deep. Nesting will be

    B
    :ok
  """
  @spec group(docentity) :: UNION.t
  def group(x),  do: UNION[left: flatten(x), right: x]

  @doc """
  Does the same thing as `group` but collapses
  line breaks into NILs. Can be handy for
  pretty printing terms, representations of
  which have natural separators (such as lists).

  ## Examples

    iex(1)> Wadler.group1(Wadler.concat(Wadler.group1(
    ...(1)>                                           Wadler.concat(Wadler.text("Hello,"),
    ...(1)>                                                         Wadler.concat(Wadler.line,
    ...(1)>                                                                       Wadler.text("A"))
    ...(1)>                                           )),
    ...(1)>                              Wadler.concat(Wadler.line,
    ...(1)>                                            Wadler.text("B"))
    ...(1)> )) # Output is prettified for readability
    UNION[
      left:CONCAT[
        left:CONCAT[
          left:TEXT[string: "Hello,"]
          right:CONCAT[
            left:NIL
            right:TEXT[string: "A"]]]
        right:CONCAT[
          left:NIL
          right:TEXT[string: "B"]]]
      right:CONCAT[
        left:UNION[
          left:CONCAT[
            left:TEXT[string: "Hello,"]
            right:CONCAT[
              left:NIL
              right:TEXT[string: "A"]]]
          right:CONCAT[
            left:TEXT[string: "Hello,"]
            right:CONCAT[
              left:LINE
              right:TEXT[string: "A"]]]]
        right:CONCAT[
          left:LINE
          right:TEXT[string: "B"]]]]
      
  """
  @spec group1(docentity) :: UNION.t
  def group1(x), do: UNION[left: shrink(x),  right: x]

  # Helpers
  @doc """
  Inserts single space between two document entities.

  ## Examples
  
    iex(1)> Wadler.space Wadler.text("Hughes"), Wadler.text("Wadler")
    Wadler.CONCAT[
      left: Wadler.TEXT[string: "Hughes"], 
      right: Wadler.CONCAT[left: Wadler.TEXT[string: " "], right: Wadler.TEXT[string: "Wadler"]]
    ] 

  """
  @spec space(docentity, docentity) :: CONCAT.t
  def space(x, y), do: concat(x, concat(text(" "), y))
  
  @doc """
  Inserts single line between two document entities.

  ## Examples

    iex(1)> Wadler.line Wadler.text("Hughes"), Wadler.text("Wadler")
    Wadler.CONCAT[
      left: Wadler.TEXT[string: "Hughes"], 
      right: Wadler.CONCAT[left: LINE, right: Wadler.TEXT[string: "Wadler"]]
    ]

  """
  @spec line(docentity, docentity) :: CONCAT.t
  def line(x, y), do: concat(x, concat(line, y))

  @doc """
  Produces document entity where separator
  is a union of space and line.

  ## Examples
    iex(1)> Wadler.sn Wadler.text("Hughes"), Wadler.text("Wadler")        
    Wadler.CONCAT[
      left: Wadler.TEXT[string: "Hughes"], 
      right: Wadler.CONCAT[
        left: Wadler.UNION[
          left: Wadler.TEXT[string: " "], 
          right: LINE], 
        right: Wadler.TEXT[string: "Wadler"]
      ]
    ]

  
  """
  @spec sn(docentity, docentity) :: CONCAT.t
  def sn(x, y), do: concat(x, concat(UNION[left: text(" "), right: line], y))

  @doc """
  Fold a list of document entities into a document entity
  using a function that is passed as the first argument.

  ## Example

    iex(1)> [Wadler.text("A"), Wadler.text("B")] 
    [Wadler.TEXT[string: "A"],Wadler.TEXT[string: "B"]]
    
    iex(2)> Wadler.folddoc(fn(x,y) -> Wadler.concat(x, Wadler.concat(Wadler.text("!"), y)) end, v(1))
    Wadler.CONCAT[
      left: Wadler.TEXT[string: "A"], 
      right: Wadler.CONCAT[
        left: Wadler.TEXT[string: "!"], 
        right: Wadler.TEXT[string: "B"]
      ]
    ]
    
  """
  @spec folddoc( ((docentity, [docentity]) -> docentity), [docentity]) :: docentity
  def folddoc(_, []), do: null
  def folddoc(_, [doc]), do: doc
  def folddoc(f, [d|ds]), do: f.(d, folddoc(f, ds))

  @doc """
  Fold a list of document entities with space/2 function.
  """
  @spec spread(docentity) :: docentity
  def spread(doc), do: folddoc(fn(x, d) -> space(x,d) end, doc)
  @spec stack(docentity) :: docentity

  @doc """
  Fold a list of document entities with line/2 function.
  """
  def stack(doc),  do: folddoc(fn(x, d) -> line(x,d) end, doc)

  @doc """
  Collapse a list of documents into a reasonably formatted document.
  """
  @spec fill([docentity]) :: docentity
  def fill([]), do: NIL
  def fill([doc]), do: doc
  def fill([x|[y|docs]]) do
    UNION[left:  space(flatten(x), fill( [flatten(y)|docs] )),
          right: line(x, fill( [y|docs] ))]
  end
  
  @doc """
  Takes three arguments: left bracket, document
  and right bracket.
  Puts the document between the brackets and nests
  it using `group`.
  """
  @spec bracket(binary, docentity, binary) :: docentity
  def bracket(bracketl, doc, bracketr) do
    group(
      concat(
             text(bracketl), 
             concat(
                    nest(2, concat(line, doc)),
                    concat(line, text(bracketr))
             )
      )
    )
  end  
  
  @doc"""
  The pretty printing functoion.
  Takes maximum width and document to print as
  its arguments and returns the string
  representation of the best layout for the
  document to fit in the given width.
  """
  @spec pretty(non_neg_integer, docentity) :: binary
  def pretty(width, document), do: layout best(width, 0, document)

  @doc"""
  Exported for the purpose of tests. You shouldn't
  use this function.
  """
  @spec factor(non_neg_integer, docentity) :: docfactor
  def factor(width, document), do: best width, 0, document
  
  ## Private functions

  # Flatten variant representation.
  # Non-terminals
  defp flatten(UNION[left: x, right: _]),  do: flatten x
  defp flatten(CONCAT[left: x, right: y]), do: CONCAT[left: flatten(x), right: flatten(y)]
  defp flatten(NEST[indent: i, rest: x]),  do: NEST[indent: i, rest: flatten(x)]
  # Terminals
  defp flatten(LINE),                      do: TEXT[string: " "]
  defp flatten(GLUE[]),                    do: NIL
  defp flatten(NIL),                       do: NIL
  defp flatten(x = TEXT[]),                do: x

  # Shrink is flatten version that replaces lines with NIL.
  # Non-terminals
  defp shrink(UNION[left: x, right: _]),   do: shrink x
  defp shrink(CONCAT[left: x, right: y]),  do: CONCAT[left: shrink(x), right: shrink(y)]
  defp shrink(NEST[indent: i, rest: x]),   do: NEST[indent: i, rest: shrink(x)]
  # Terminals
  defp shrink(LINE),                       do: NIL
  defp shrink(GLUE[]),                     do: NIL
  # Other terminals are same as with flatten
  defp shrink(x),                          do: flatten(x)

  # Laying out finalized document
  defp layout(Nil), do: ""
  defp layout(Text[string: s, rest: x]), do: s <> layout(x)
  defp layout(Line[indent: i, rest: x]), do: "\n" <> copy(" ", i) <> layout(x)

  defp copy(_, 0), do: ""
  defp copy(binary, i), do: String.duplicate binary, i


  # Choosing best layout
  defp best(width, start_pos, document), do: dobest width, start_pos, [{0,document}]

  # Best layout of \varempty is Nil
  defp dobest(_, _, []), do: Nil
  # Ignore NIL
  defp dobest(w, k, [{_,NIL}|z]), do: dobest w,k,z
  # Expand CONCAT into two candidates
  defp dobest(w, k, [{i,CONCAT[left: x, right: y]}|z]) do 
    dobest w,k,[{i,x}|[{i,y}|z]]
  end
  # Get indentation information from NEST and move on
  defp dobest(w, k, [{i,NEST[indent: j, rest: x]}|z]) do 
    dobest w,k,[{i+j,x}|z]
  end
  # Factor out TEXT or GLUE and move caret accordingly
  defp dobest(w, k, [{_,TEXT[string: s]}|z]) do 
    Text[string: s, rest: dobest w, k+String.length(s), z]
  end
  defp dobest(w, k, [{_,GLUE[string: s]}|z]) do
    Text[string: s, rest: dobest w, k+String.length(s), z]
  end
  # Factor out LINE and make the indentation be initial caret position on the new line
  defp dobest(w, _, [{i,LINE}|z]) do
    Line[indent: i, rest: dobest w, i, z]
  end
  # Choose better alternative from UNION
  defp dobest(w, k, [{i,UNION[left: x, right: y]}|z]) do
    better w, k, dobest(w,k,[{i,x}|z]), dobest(w,k,[{i,y}|z])
  end

  defp better(w, k, x, y), do: if fits?(w-k, x), do: x, else: y

  defp fits?(delta, _) when delta<0,  do: false
  defp fits?(_____, Nil),             do: true
  defp fits?(_____, Line[]),          do: true 
  defp fits?(delta, Text[string: s,
                           rest: x]), do: fits? delta - String.length(s), x

end


  ## Examples

    iex(1)> Wadler.nest(5, Wadler.concat(Wadler.break, Wadler.text("6")))
    Wadler.DocNest[indent: 5, doc: Wadler.DocCons[left: Wadler.DocBreak, right: Wadler.DocText[str: "6"]]]

    iex(2)> IO.puts Wadler.pretty(80, v(1))
    
