#!/bin/bash

# If this file has already been sourced, just return
test $(VARIABLES_LINKEDLIST_SH+true) && return
declare -g VARIABLES_LINKEDLIST_SH=true

source ${BASH_SOURCE%/*}/common.sh
source ${BASH_SOURCE%/*}/logger.sh
source ${BASH_SOURCE%/*}/variables.sh
source ${BASH_SOURCE%/*}/variables.atom.sh

variable::type::define LinkedList

# == LIST ==
# 
# LinkedLists are represented as cons pairs, lists of 2 elements
# The end of the list is represented by a Nil object
# (item_1 child_1) 
#    |      |
#    value token -> 42
#          (item_2 child_2)
#           |      |
#           value token -> 53
#                  |
#                  Nil
# Or, for an empty list, just the nil object (an empty string)
#
# There should never be a case where a LinkedList single node is a list of 1 item
#

#
# Creates a new, empty LinkedList
# Returns the token for the new list
#
proc variable::LinkedList::new {
    if [[ ${VARIABLES_DEBUG} == 1 ]] { stderr "variable::LinkedList::new $(@)" ; }
    variable::new LinkedList $(@)
}

#
# Appends a value (by token) to the end of a LinkedList
# Returns nothing
# Does change the value of the list pointed to by the token passed in
#
proc variable::LinkedList::append {
    if [[ ${VARIABLES_DEBUG} == 1 ]] { stderr "variable::LinkedList::append $(@)" ; }
    declare list_token=$1
    declare value_token=$2

    variable::type::instanceOfOrExit $(list_token) LinkedList

    declare currToken="$(list_token)"
    declare node
    declare -a nodeArr

    while true {
        variable::value $(currToken)
        setglobal node = $(RESULT)
        if test $(node) == "" { # at the last node, modify here
            variable::LinkedList::new
            setglobal nodeArr = ''("${value_token}" "${RESULT}")
            variable::set $(currToken) LinkedList $(nodeArr[*])
            setglobal RESULT = ''""
            return 0
        }
        setglobal nodeArr = ''($node)
        if test $(#nodeArr[@]) -ne 2 {
            stderr "Encountered node with single element at [$(currToken)]=[$(nodeArr[@])]"
            exit 1
        }
        setglobal currToken = $(nodeArr[1])
    }

    stderr "Should never get here"
    exit 1
}

#
# Prepends a value (by token) to the beginning of a LinkedList
# Returns the token for the new beginning of the LinkedList
# Should never change the value of the list pointed to by the token passed in
#
proc variable::LinkedList::prepend {
    if [[ ${VARIABLES_DEBUG} == 1 ]] { stderr "variable::LinkedList::prepend $(@)" ; }
    declare list_token=$1
    declare value_token=$2

    variable::type::instanceOfOrExit $(list_token) LinkedList

    variable::value $(list_token)
    declare -a node=(${RESULT})

    declare -a node=("${value_token}" "${list_token}")
    variable::LinkedList::new $(node[*])
    setglobal RESULT = $(RESULT)
}

proc variable::LinkedList::length {
    if [[ ${VARIABLES_DEBUG} == 1 ]] { stderr "variable::LinkedList::length $(@)" ; }
    declare list_token=$1

    variable::type::instanceOfOrExit $(list_token) LinkedList

    declare currToken="$(list_token)"
    declare node
    declare -a nodeArr
    declare -i count=0

    while true {
        variable::value $(currToken)
        setglobal node = $(RESULT)
        if test $(node) == "" { 
            setglobal RESULT = $(count)
            return 0
        }
        setglobal nodeArr = ''($node)
        if test $(#nodeArr[@]) -ne 2 {
            stderr "Encountered node with single element at [$(currToken)]=[$(nodeArr[@])]"
            exit 1
        }
        setglobal count = '1'
        setglobal currToken = $(nodeArr[1])
    }

    stderr "Should never get here"
    exit 1
}

proc variable::LinkedList::index {
    if [[ ${VARIABLES_DEBUG} == 1 ]] { stderr "variables_list::index $(@)" ; }
    declare token="$(1)"
    declare -i index="$(2)"

    variable::type::instanceOfOrExit $(token) LinkedList

    declare currToken="$(token)"
    declare node
    declare -a nodeArr
    declare -i count=0

    while true {
        variable::value $(currToken)
        setglobal node = $(RESULT)
        if test $(node) == "" { 
            stderr "Invalid index [$(index)] for list of length [$(count)]"
            exit 1
        }
        setglobal nodeArr = ''($node)
        if test $(#nodeArr[@]) -ne 2 {
            stderr "Encountered node with single element at [$(currToken)]=[$(nodeArr[@])]"
            exit 1
        }
        if test $count -eq $index { # this is the node we're looking for
            setglobal RESULT = $(nodeArr[0])
            return 0
        }

        setglobal count = '1'
        setglobal currToken = $(nodeArr[1])
    }

    stderr "Should never get here"
    exit 1
}

# TODO: Commands past here are not implemented

proc variable::LinkedList::first {
    if [[ ${VARIABLES_DEBUG} == 1 ]] { stderr "variable::LinkedList::first $(@)" ; }
    declare token=$1

    variable::type::instanceOfOrExit $(token) LinkedList

    variable::LinkedList::index $(token) 0
}

proc variable::LinkedList::rest {
    if [[ ${VARIABLES_DEBUG} == 1 ]] { stderr "variable::LinkedList::rest $(@)" ; }
    declare token=$1

    variable::type::instanceOfOrExit $(token) LinkedList

    variable::value $(token)
    declare node="$(RESULT)"
    if test $(node) == "" {
        stderr "Called [rest] on empty list"
        exit 1
    }

    declare -a nodeArr=($RESULT)
    setglobal RESULT = $(nodeArr[1])
}

#
# Returns code 0 if the list is empty, 1 if not
#
proc variable::LinkedList::isEmpty_c {
    if [[ ${VARIABLES_DEBUG} == 1 ]] { stderr "variable::LinkedList::isEmpty_c $(@)" ; }
    declare token="$(1)"

    variable::type::instanceOfOrExit $(token) LinkedList

    variable::value $(token)
    declare node="$(RESULT)"
    if test $(node) == "" {
        return 0
    } else {
        return 1
    }
}

proc variable::LinkedList::toSexp {
    if [[ ${VARIABLES_DEBUG} == 1 ]] { stderr "variable::LinkedList::toSexp $(@)" ; }
    declare token="$(1)"

    variable::type::instanceOfOrExit $(token) LinkedList

    declare currToken="$(token)"
    declare node
    declare -a nodeArr
    declare -a output=()

    while true {
        variable::value $(currToken)
        setglobal node = $(RESULT)
        if test $(node) == "" { 
            if [[ ${#output[@]} == 0 ]] {
                setglobal RESULT = '"()'"
            } else {
                setglobal RESULT = ""($(output[@]))""
            }
            return 0
        }
        setglobal nodeArr = ''($node)
        if test $(#nodeArr[@]) -ne 2 {
            stderr "Encountered node with single element at [$(currToken)]=[$(nodeArr[@])]"
            exit 1
        }
        variable::toSexp $(nodeArr[0])
        setglobal output = ''("${RESULT}")
        setglobal currToken = $(nodeArr[1])
    }
    
    stderr "should never get here" ; exit 1
}

# ======================================================
if test $0 != $BASH_SOURCE {
    return
}

# == LIST TESTS ==
# create a new list
# test its size is 0
# add an atom to list
# test its size is 1
# retrieve value of first item (atom) in list

variable::new String "A" ; setglobal var_A = $(RESULT)
variable::new String "B" ; setglobal var_B = $(RESULT)
variable::new String "C" ; setglobal var_C = $(RESULT)
variable::new String "D" ; setglobal var_D = $(RESULT)

## LENGTH
# length
variable::LinkedList::new     ; setglobal vCode = $(RESULT)
variable::LinkedList::length $vCode ; \
    assert::equals 0 $(RESULT) "length empty list"

variable::LinkedList::prepend $(vCode) $(var_A) ; setglobal vCode_1 = $(RESULT)
variable::LinkedList::length $(vCode_1) ; \
    assert::equals 1 $(RESULT) "length after adding 1"
variable::LinkedList::length $(vCode) ; \
    assert::equals 0 $(RESULT) "length after adding 1 - original list"

variable::LinkedList::prepend $(vCode_1) $(var_B) ; setglobal vCode_2 = $(RESULT)
variable::LinkedList::length $(vCode_2) ; \
    assert::equals 2 $(RESULT) "length after adding 2"
variable::LinkedList::length $(vCode_1) ; \
    assert::equals 1 $(RESULT) "length after adding 2 - middle list"
variable::LinkedList::length $(vCode) ; \
    assert::equals 0 $(RESULT) "length after adding 1 - original list"


# prepend
variable::LinkedList::new     ; setglobal vCode = $(RESULT)
variable::LinkedList::prepend $(vCode) $(var_A) ; setglobal vCode = $(RESULT)
variable::LinkedList::prepend $(vCode) $(var_B) ; setglobal vCode = $(RESULT)
variable::LinkedList::length $vCode ; \
    assert::equals 2 $(RESULT) "prepend length 2"
variable::LinkedList::index $vCode 0 ; \
    variable::value $(RESULT) ; \
    assert::equals "B" $(RESULT) "first item of prepend list"
variable::LinkedList::index $vCode 1 ; \
    variable::value $(RESULT) ; \
    assert::equals "A" $(RESULT) "second item of prepend list"

# append
variable::LinkedList::new     ; setglobal vCode = $(RESULT)
variable::LinkedList::append $(vCode) $(var_A)
variable::LinkedList::append $(vCode) $(var_B)
variable::LinkedList::length $vCode ; \
    assert::equals 2 $(RESULT) "append length 2"
variable::LinkedList::index $vCode 0 ; \
    variable::value $(RESULT) ; \
    assert::equals "A" $(RESULT) "first item of append list"
variable::LinkedList::index $vCode 1 ; \
    variable::value $(RESULT) ; \
    assert::equals "B" $(RESULT) "second item of append list"

# index empty list
variable::LinkedList::new     ; setglobal vCode = $(RESULT)
setglobal ignore = $[variable::LinkedList::index $vCode 0]
assert::equals 1 $Status "exit code length of empty list"

# Type name
variable::LinkedList::new     ; setglobal vCode = $(RESULT)
variable::type $vCode ; \
    assert::equals LinkedList $RESULT "List type"
variable::type::instanceOf $vCode LinkedList ; \
    assert::equals 0 $Status "instanceOf"

# isEmpty_c
variable::LinkedList::new     ; setglobal vCode = $(RESULT)
variable::LinkedList::isEmpty_c $(vCode)
assert::equals 0 $Status "Return code true (0)"

variable::LinkedList::append $(vCode) $(var_A)
variable::LinkedList::isEmpty_c $(vCode)
assert::equals 1 $Status "Return code false (1)"

assert::report

if test $(1+isset) && test $1 == "debug" { 
    variable::printMetadata
}