# Just some general recursion stress tests:
# 1. Ackermann's Function
# 2. Fibonacci Numbers

import sys
from Ft import MAX_PYTHON_RECURSION_DEPTH
sys.setrecursionlimit(MAX_PYTHON_RECURSION_DEPTH)

from Xml.Xslt import test_harness

source_1 = """<dummy/>"""

sty_1 = """<?xml version="1.0" encoding="utf-8"?>
<!--

  Ackermann's function
  http://pweb.netcom.com/~hjsmith/Ackerman/AckeWhat.html

  1. If x = 0 then  A(x, y) = y + 1
  2. If y = 0 then  A(x, y) = A(x-1, 1)
  3. Otherwise,     A(x, y) = A(x-1, A(x, y-1))

  A(3,4) = 125
  A(3,5) = 253
  A(3,6) = 509; template called 172233 times, nested up to 511 calls deep
  A(3,7) will call the template 693964 times (good luck)

-->
<xsl:stylesheet version="1.0"
  xmlns:xsl="http://www.w3.org/1999/XSL/Transform">

  <xsl:output method="text" indent="no"/>

  <xsl:param name="x" select="3"/>
  <xsl:param name="y" select="6"/>

  <xsl:template match="/">
    <xsl:value-of select="concat('A(',$x,',',$y,') = ')"/>
    <xsl:variable name="c" select="0"/>
    <xsl:call-template name="A">
      <xsl:with-param name="x" select="$x"/>
      <xsl:with-param name="y" select="$y"/>
    </xsl:call-template>
  </xsl:template>

  <xsl:template name="A">
    <xsl:param name="x" select="0"/>
    <xsl:param name="y" select="0"/>
    <xsl:choose>
      <xsl:when test="$x = 0">
        <xsl:value-of select="$y + 1"/>
      </xsl:when>
      <xsl:when test="$y = 0">
        <xsl:call-template name="A">
          <xsl:with-param name="x" select="$x - 1"/>
          <xsl:with-param name="y" select="1"/>
        </xsl:call-template>
      </xsl:when>
      <xsl:otherwise>
        <xsl:call-template name="A">
          <xsl:with-param name="x" select="$x - 1"/>
          <xsl:with-param name="y">
            <xsl:call-template name="A">
              <xsl:with-param name="x" select="$x"/>
              <xsl:with-param name="y" select="$y - 1"/>
            </xsl:call-template>
          </xsl:with-param>
        </xsl:call-template>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:template>

</xsl:stylesheet>"""

expected_1 = """A(3,4) = 125"""

sty_2 = """<?xml version="1.0" encoding="utf-8"?>
<!--

  Fibonacci Numbers

  if n = 0, f(n) = 0
  if n = 1, f(n) = 1
  otherwise, f(n) = f(n-2) + f(n-1)

  tail-recursive version based on Scheme code by
  Ben Gum and John David Stone, at
  http://www.math.grin.edu/~gum/courses/151/readings/tail-recursion.xhtml
        
-->
<xsl:stylesheet version="1.0"
  xmlns:xsl="http://www.w3.org/1999/XSL/Transform">

  <xsl:output method="text" indent="no"/>

  <xsl:param name="n" select="100"/>

  <xsl:template match="/">
    <xsl:value-of select="concat('f(',$n,') = ')"/>
    <xsl:call-template name="fibo">
      <xsl:with-param name="n" select="$n"/>
    </xsl:call-template>
  </xsl:template>

  <xsl:template name="fibo">
    <xsl:param name="n" select="0"/>
    <xsl:call-template name="fibo-guts">
      <xsl:with-param name="current" select="0"/>
      <xsl:with-param name="next" select="1"/>
      <xsl:with-param name="remaining" select="$n"/>
    </xsl:call-template>
  </xsl:template>
    
  <xsl:template name="fibo-guts">
    <xsl:param name="current" select="0"/>
    <xsl:param name="next" select="0"/>
    <xsl:param name="remaining" select="0"/>
    <xsl:choose>
      <xsl:when test="$remaining = 0">
        <xsl:value-of select="$current"/>
      </xsl:when>
      <xsl:otherwise>
        <xsl:call-template name="fibo-guts">
          <xsl:with-param name="current" select="$next"/>
          <xsl:with-param name="next" select="$current + $next"/>
          <xsl:with-param name="remaining" select="$remaining - 1"/>
        </xsl:call-template>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:template>

</xsl:stylesheet>"""

expected_2 = "f(100) = 354224848179261997056"

def Test(tester):
    source = test_harness.FileInfo(string=source_1)
    sheet = test_harness.FileInfo(string=sty_1)
    test_harness.XsltTest(tester, source, [sheet], expected_1,
                          topLevelParams={'x': 3, 'y': 4},
                          title="Ackermann's Function")

    sheet = test_harness.FileInfo(string=sty_2)
    test_harness.XsltTest(tester, source, [sheet], expected_2,
                          title="Fibonacci Numbers")
    return