# Instructions
# ------------------------------------------------------------------------------

# This library adds the type STVar, which internally is an array structure with
# sufficient information to serialize and deserialize itself.

# An STVar is any of the following:
# STDict
# STFloat
# STInt
# STQueue
# STString
# STVector

# Each type has a type constructor of the same name.

# For example, we can create a dict and populate it with values.

# var dict = STDict()
# STDictSet(dict, "one", STInt(1))
# STDictSet(dict, "two", STInt(2))
# STDictSet(dict, "three", STInt(3))
# STDictSet(dict, "one_as_string", STString("one"))

# A dict can contain other dicts as well.

# var dict2 = STDict()
# STDictSet(dict2, "five", STInt(5))
# STDictSet(dict, "recurse", dict2)

# Then store the data in memory for later.

# SaveMemory("memory_key", STSerialize(dict))

# And get it back in another session!

# if (HasMemory("memory_key"))
#     var dict = Deserialize(LoadMemory("memory_key"))
# end

# See unit tests for more usage.


# Globals
# ------------------------------------------------------------------------------

# These should all be 1 byte long
var gstTypeString = "s"
var gstTypeInt = "i"
var gstTypeFloat = "f"
var gstTypeDict = "d"
var gstTypeQueue = "q"
var gstTypeVector = "v"

# Serializable type internal array positions
var gstTypePos  = 0
var gstValuePos = 1

var gstQueueSizePos = 2
var gstVectorSizePos = 2

var gstPrettyPrintIndent = "    "


# Program
# ------------------------------------------------------------------------------

ClearText()
STRunTests()


# STVar Constructors
# ------------------------------------------------------------------------------

# Create an STString
#
# @param string to lift into STVar
#
# @return New STVar
var STString(string val)
    return [gstTypeString, val]
end

# Create an STInt
#
# @param int to lift into STVar
#
# @return New STVar
var STInt(number val)
    return [gstTypeInt, Int(val)]
end

# Create an STFloat
#
# @param float to lift into STVar
#
# @return New STVar
var STFloat(number val)
    return [gstTypeFloat, val]
end

# Create an empty STQueue
#
# @return New STVar
var STQueue()
    return [gstTypeQueue, [], 0]
end

# Create an empty STDict
#
# @return New STVar
var STDict()
    return [gstTypeDict, []]
end

# Create an empty STVector
#
# @return New STVar
var STVector()
    return [gstTypeVector, [], 0]
end

# Dict functions
# ------------------------------------------------------------------------------

# Add a value to an STDict
#
# @param STDict Dict to modify
# @param string Key for value
# @param STVar Value to add to STDict
void STDictSet(array st, string key, var stVal)
    STAssertType(st, gstTypeDict)
    STAssertIsST(stVal)

    array internal = STGet(st)
    internal[key] = stVal
end

# Extract all keys in STDict
#
# @param STDict Dictionary with keys
#
# @return array All keys in STDict.
array STDictKeys(array st)
    STAssertType(st, gstTypeDict)

    array internal = STGet(st)
    return GetIndexes(internal)
end

# Check if STDict has a key.
#
# @param STDict to examine.
# @param string Key to verify existence.
#
# @return bool True if key in STDict.
bool STDictHasKey(array st, string key)
    STAssertType(st, gstTypeDict)

    array internal = STGet(st)
    return HasIndex(internal, key)
end

# Get value by key from STDict
#
# @param STDict to examine.
# @param string Key with value.
#
# @return STVar referenced by key from st.
#
# @warning Runtime failure if key does not exist.
var STDictGetByKey(array st, string key)
    STAssertType(st, gstTypeDict)

    array internal = STGet(st)
    return internal[key]
end

# Remove a value from an STDict
#
# @param STDict to modify
# @param string Key to remove
void STDictRemoveByKey(array st, string key)
    STAssertType(st, gstTypeDict)

    array internal = STGet(st)
    Remove(internal, key)
end


# Queue functions
# ------------------------------------------------------------------------------

# Pushes value onto end of STQueue
#
# @param array STQueue created by STQueue
# @param An STVar
void STQueuePush(array st, var stVal)
    STAssertType(st, gstTypeQueue)
    STAssertIsST(stVal)

    # increment size
    var currentSize = st[gstQueueSizePos]
    var newSize = currentSize + 1
    st[gstQueueSizePos] = newSize

    # Add value
    var internalQueue = st[gstValuePos]
    internalQueue[currentSize] = stVal
end

# Removes value from queue
#
# @param array STQueue created by STQueue
#
# @return Popped value
var STQueuePop(array st)
    STAssertType(st, gstTypeQueue)
    if (STQueueSize(st) <= 0)
        STFail("STQueuePop on empty queue.")
    end

    # decrement size
    var currentSize = st[gstQueueSizePos]
    var newSize = currentSize - 1
    st[gstQueueSizePos] = newSize

    # return value
    var internalQueue = st[gstValuePos]
    return internalQueue[newSize]
end

# Get size of STQueue
#
# @param STQueue
#
# @return number Size of argument
number STQueueSize(array st)
    return st[gstQueueSizePos]
end


# Vector functions
# ------------------------------------------------------------------------------

# Get element from vector
#
# @param STVector
# @param number Position to insert new element starting a 0.
#
# @return Element from vector at indicated position.
void STVectorAt(array st, number pos)
    array internal = STGet(st)
    return internal[pos]
end

# Insert element into vector
#
# @param STVector
# @param number Position to insert new element starting a 0.
# @param STVal Value to append
void STVectorInsert(array st, number insertPos, var stVal)
    number originalSize = st[gstVectorSizePos]

    # increment size
    st[gstVectorSizePos] = st[gstVectorSizePos] + 1

    array internal = STGet(st)

    # Move insertPos and above one slot higher
    number i = originalSize
    loop
        var j = i - 1
        if (j < insertPos)
            break
        end

        internal[i] = internal[j]
        i -= 1
    end

    # insert element at position
    internal[insertPos] = stVal
end

# Remove element from vector
#
# @param STVector
# @param number Position to insert new element starting a 0.
#
# @return Removed element from vector.
void STVectorRemoveAt(array st, number removePos)
    # decrment size
    st[gstVectorSizePos] = st[gstVectorSizePos] - 1

    number newSize = st[gstVectorSizePos]

    array internal = STGet(st)

    var removedVal = internal[removePos]

    # Rotate elements down
    number i = removePos
    loop
        var j = i + 1
        if (j > newSize)
            break
        end

        internal[i] = internal[j]
        i += 1
    end

    Remove(internal, newSize)
end

# Add element to end of vector
#
# @param STVector
# @param STVal Value to append
void STVectorAppend(array st, var stVal)
    number newPos = st[gstVectorSizePos]
    st[gstVectorSizePos] = st[gstVectorSizePos] + 1

    array internal = STGet(st)
    internal[newPos] = stVal
end

# Get size of STVector
#
# @param STVector
#
# @return number Size of argument
number STVectorSize(array st)
    return st[gstVectorSizePos]
end


# Serialization
# ------------------------------------------------------------------------------

# Serialize an STVar
#
# @param STVar to serialize
#
# @return string representation of STVar
string STSerialize(var st)
    string ret = ""
    var stType = STType(st)

    if (stType == gstTypeString)
        string str = STGet(st)
        ret += stType + "{" + Count(str) + ":" + str + "}"
    else if (stType == gstTypeInt)
        ret += stType + "{" + STGet(st) + "}"
    else if (stType == gstTypeFloat)
        ret += stType + "{" + STGet(st) + "}"
    else if (stType == gstTypeDict)
        array keys = STDictKeys(st)
        ret += stType + "{"
        loop key in keys
            ret += STSerialize(STString(key))
            ret += STSerialize(STDictGetByKey(st, key))
        end
        ret += "}"
    else if (stType == gstTypeQueue)
        var size = STQueueSize(st)
        ret += stType + "{"

        var innerArray = STGet(st)
        if (size > 0)
            loop i from 0 to size - 1
                ret += STSerialize(innerArray[i])
            end
        end

        ret += "}"
    else if (stType == gstTypeVector)
        var size = STVectorSize(st)
        ret += stType + "{"

        var innerArray = STGet(st)
        if (size > 0)
            loop i from 0 to size - 1
                ret += STSerialize(innerArray[i])
            end
        end

        ret += "}"
    else
        STFail("STSerialize unhandled type: " + stType)
    end

    return ret
end

# Deserialize STVar serialized string representation
#
# @param string Data to deserialize.
#
# @return STVar from str.
#
# @warning Calls STFail on parse failure.
var STDeserialize(string str)
    var ret = STDeserializeFrom(str, 0)
    return ret[0]
end


# Internal deserialize STVar serialized string representation
#
# @param string Data to deserialize.
#
# @return array 0: Extracted STVar
#               1: End read position
#
# @warning Calls STFail on parse failure.
var STDeserializeFrom(string str, number startPos)
    string typeStr = str[startPos]

    if (str[startPos + 1] != "{")
        STFail("Unexpected opener: " + STStringExtractRest(str, startPos + 1))
    end

    if (typeStr == gstTypeString)
        number strLenPos = startPos + 2
        number colonPos = STStringFindChar(str, ":", strLenPos)
        if (colonPos == -1)
            STFail("Colon unparsed in: " + STStringExtractRest(str, strLenPos))
        end
        number strLen = STStringExtract(str, strLenPos, colonPos)

        number stringStartPos = colonPos + 1
        number stringEndPos = stringStartPos + strLen

        if (str[stringEndPos] != "}")
            STFail("Unexpected closing bracket: " + STStringExtractRest(str, stringEndPos))
        end

        return [STString(STStringExtract(str, stringStartPos, stringEndPos)), stringEndPos + 1]
    else if (typeStr == gstTypeInt)
        number intPos = startPos + 2
        number endPos = STStringFindChar(str, "}", intPos)
        if (endPos == -1)
            STFail("Closing bracket unparsed in: " + STStringExtractRest(str, intPos))
        end

        number val = STStringExtract(str, intPos, endPos)
        return [STInt(Int(val)), endPos + 1]
    else if (typeStr == gstTypeFloat)
        number floatPos = startPos + 2
        number endPos = STStringFindChar(str, "}", floatPos)
        if (endPos == -1)
            STFail("Closing bracket unparsed in: " + STStringExtractRest(str, floatPos))
        end

        number val = STStringExtract(str, floatPos, endPos)
        return [STFloat(val), endPos + 1]
    else if (typeStr == gstTypeDict)
        number readPos = startPos + 2
        var dict = STDict()
        loop
            if (str[readPos] == "}")
                break
            end
            var keyData = STDeserializeFrom(str, readPos)
            readPos = keyData[1]

            var valueData = STDeserializeFrom(str, readPos)
            readPos = valueData[1]

            STDictSet(dict, STGet(keyData[0]), valueData[0])
        end
        return [dict, readPos + 1]
    else if (typeStr == gstTypeQueue)
        number readPos = startPos + 2
        var queue = STQueue()

        loop
            if (str[readPos] == "}")
                break
            end

            var inner = STDeserializeFrom(str, readPos)
            STQueuePush(queue, inner[0])
            readPos = inner[1]
        end

        return [queue, readPos + 1]
    else if (typeStr == gstTypeVector)
        number readPos = startPos + 2
        var vector = STVector()

        loop
            if (str[readPos] == "}")
                break
            end

            var inner = STDeserializeFrom(str, readPos)
            STVectorAppend(vector, inner[0])
            readPos = inner[1]
        end

        return [vector, readPos + 1]
    else
        STFail("Unexpected type char: " + typeStr)
    end
end


# Library functions
# ------------------------------------------------------------------------------

# Terminate program due to error
#
# @param string Reason to display to the user
void STFail(string reason)
    Print("STFail: " + reason)
    var fail = []
    return fail[reason]
end

# Convert type char to type string
#
# @param char The type as a char used by type system and serialization.
#
# @return string Full type name
string STTypeAsString(string stType)
    if (stType == gstTypeString)
        return "STString"
    else if (stType == gstTypeInt)
        return "STInt"
    else if (stType == gstTypeFloat)
        return "STFloat"
    else if (stType == gstTypeDict)
        return "STDict"
    else if (stType == gstTypeQueue)
        return "STQueue"
    else if (stType == gstTypeVector)
        return "STVector"
    else
        return "Unknown ST type " + stType
    end
end

# Compare two STVars
#
# @param STVar to compare
# @param STVar to compare
#
# @return True if both arguments have same values
bool STEqual(var a, var b)
    STAssertIsST(a)
    STAssertIsST(b)

    var aType = STType(a)
    var bType = STType(b)

    if (aType != bType)
        return False
    end

    if (aType == gstTypeString)
        return STGet(a) == STGet(b)
    else if (aType == gstTypeInt)
        return STGet(a) == STGet(b)
    else if (aType == gstTypeFloat)
        return STGet(a) == STGet(b)
    else if (aType == gstTypeDict)
        var aKeys = STDictKeys(a)
        var bKeys = STDictKeys(b)
        if (Count(aKeys) != Count(bKeys))
            return False
        end

        # iterate through all keys comparing equality
        loop key in aKeys
            if (STDictHasKey(b, key) == False)
                return False
            end
            if (STEqual(STDictGetByKey(a, key), STDictGetByKey(b, key)) == False)
                return False
            end
        end

        return True
    else if (aType == gstTypeQueue)
        if (STQueueSize(a) != STQueueSize(b))
            return False
        end

        var aInternal = STGet(a)
        var bInternal = STGet(b)

        loop i from 0 to STQueueSize(a)
            if (STEqual(aInternal[i], bInternal[i]) == False)
                return False
            end
            return True
        end
    else if (aType == gstTypeVector)
        if (STVectorSize(a) != STVectorSize(b))
            return False
        end

        var aInternal = STGet(a)
        var bInternal = STGet(b)

        loop i from 0 to STVectorSize(a)
            if (STEqual(aInternal[i], bInternal[i]) == False)
                return False
            end
            return True
        end
    else
        STFail("STEqual unhandled type: " + STTypeAsString(aType))
    end

    return False
end

# Get type char from STVar
#
# @param STVar
#
# @return char Type as char
string STType(var st)
    return st[gstTypePos]
end

# Fail if STVar is not expected type
#
# @param STVar to check
# @param char STVar expected type
void STAssertType(var st, var expectedType)
    string actualType = STType(st)
    if (actualType != expectedType)
        string failStr = "Unexpected type '" + STTypeAsString(actualType)
        failStr += "' when '" + STTypeAsString(expectedType)
        failStr += "' was expected."
        STFail(failStr)
    end
end

# Assert that argument is STVar
#
# @param any
#
# @warning Asserts if argument is not of type STVar.
void STAssertIsST(var st)
    var stType = STType(st)

    if (stType == gstTypeString)
    else if (stType == gstTypeInt)
    else if (stType == gstTypeFloat)
    else if (stType == gstTypeDict)
    else if (stType == gstTypeQueue)
    else if (stType == gstTypeVector)
    else
        STFail("Not a STVar")
    end
end

# Unwrap STVar
#
# @param STVar to unwrap
#
# @return Unwrapped internal value.  Only makes sense for basic types.
var STGet(var st)
    return st[gstValuePos]
end

# Output STVar as text
#
# @param STVar to print
void STPrettyPrint(var st)
    STPrettyPrintIndented(st, 0)
end

# Output STVar as text
#
# @param STVar to print
# @param number Indentation level
void STPrettyPrintIndented(var st, number indentLevel)
    string indent = ""

    if (indentLevel > 0)
        loop x from 0 to (indentLevel - 1)
            indent += gstPrettyPrintIndent
        end
    end

    var stType = STType(st)

    if (stType == gstTypeString)
        Print(indent + "STString(" + STGet(st) + ")")
    else if (stType == gstTypeInt)
        Print(indent + "STInt(" + STGet(st) + ")")
    else if (stType == gstTypeFloat)
        Print(indent + "STFloat(" + STGet(st) + ")")
    else if (stType == gstTypeDict)
        Print(indent + "STDict {")
        var indent2 = indent + gstPrettyPrintIndent
        loop key in STDictKeys(st)
            Print(indent2 + key + ":")
            STPrettyPrintIndented(STDictGetByKey(st, key), indentLevel + 2)
        end
        Print(indent + "}")
    else if (stType == gstTypeQueue)
        Print(indent + "STQueue {")
        var size = STQueueSize(st)
        var count = 0
        loop value in STGet(st)
            if (count >= size)
                break
            end
            STPrettyPrintIndented(value, indentLevel + 1)
        end
        Print(indent + "}")
    else if (stType == gstTypeVector)
        Print(indent + "STVector {")
        var size = STVectorSize(st)
        var count = 0
        loop value in STGet(st)
            if (count >= size)
                break
            end
            STPrettyPrintIndented(value, indentLevel + 1)
        end
        Print(indent + "}")
    else
        STFail("Unknown ST type " + stType)
    end
end

# Library Internal Helpers
# ------------------------------------------------------------------------------

# Convenience substr function
#
# @param string Source extraction data
# @param int Position to start extraction.
# @param int Position to stop extraction.  Not included in response.
#
# @return string extracted from str.
string STStringExtract(string str, number startPos, number endPos)
    if (startPos >= endPos)
        return ""
    end

    string ret = ""
    loop i from startPos to (endPos - 1)
        ret += str[i]
    end
    return ret
end

# Convenience substr function
#
# @param string Source extraction data
# @param int Position to start extraction.
#
# @return string extracted from str.
var STStringExtractRest(string str, number startPos)
    return STStringExtract(str, startPos, Count(str))
end

# Find character position
#
# @param string Search string
# @param char Char to find in str.
# @param number Position to start search.
#
# @return number -1 if ch doesn't exist, otherwise position of ch.
number STStringFindChar(string str, string ch, number startPos)
    number size = Count(str)
    number remaining = size - startPos

    if (remaining > 0)
        loop i from startPos to (size - 1)
            if (str[i] == ch)
                return i
            end
        end
    end
    return -1
end

# Library Testing
# ------------------------------------------------------------------------------

void STQueueTestMakeQueue()
    var queue = STQueue()
    STQueuePush(queue, STInt(1))
    STQueuePush(queue, STInt(2))
    STQueuePush(queue, STInt(3))
    STQueuePush(queue, STInt(4))
    STQueuePush(queue, STInt(5))
    STQueuePush(queue, STInt(6))
    STQueuePush(queue, STInt(0))
    STQueuePush(queue, STString("zero"))

    var innerQueue = STQueue()
    STQueuePush(innerQueue, STInt(0))
    STQueuePush(innerQueue, STInt(1))
    STQueuePush(innerQueue, STInt(2))

    STQueuePush(queue, innerQueue)

    return queue
end

void STQueueTest()
    var queue = STQueueTestMakeQueue()
    var queue2 = STQueueTestMakeQueue()
    if (STEqual(queue, queue2) == False)
        STFail("Queue equality failure.")
    end

    STQueuePop(queue2)
    if (STEqual(queue, queue2) == True)
        STFail("Queue equality failure(2).")
    end

    STTestSerialization(queue)
end

void STDictTest()
    var dict = STDict()
    STDictSet(dict, "one", STInt(1))
    STDictSet(dict, "two", STInt(2))
    STDictSet(dict, "three", STInt(3))

    if (STEqual(STDictGetByKey(dict, "two"), STInt(2) ) == False )
        STFail("Dict lookup failed expected value")
    end

    var dict2 = STDict()
    STDictSet(dict2, "three", STInt(3))
    STDictSet(dict2, "two", STInt(2))
    STDictSet(dict2, "one", STInt(1))

    if (STEqual(dict, dict2) == False)
        STFail("Dict equality failure.")
    end

    STDictSet(dict2, "zero", STInt(0))

    if (STEqual(dict, dict2) == True)
        STFail("Dict equality failure(2).")
    end

    STTestSerialization(dict)
end

void STVectorTest()
    var vector = STVector()
    STVectorAppend(vector, STInt(1))
    STVectorAppend(vector, STInt(2))
    STVectorAppend(vector, STInt(3))

    if (STEqual(STVectorAt(vector, 1), STInt(2)) == False)
        STFail("vector lookup failed expected value")
    end

    var vector2 = STVector()
    STVectorInsert(vector2, 0, STInt(3))
    STVectorInsert(vector2, 0, STInt(2))
    STVectorInsert(vector2, 0, STInt(1))

    if (STEqual(vector, vector2) == False)
        STFail("Vector equality failure.")
    end

    STVectorInsert(vector2, 0, STInt(0))

    if (STEqual(vector, vector2) == True)
        STFail("Vector equality failure(2).")
    end

    STVectorRemoveAt(vector2, 0)

    if (STEqual(vector, vector2) == False)
        STFail("Vector equality failure(3).")
    end

    STTestSerialization(vector)
end

void STTestSerialization(var stVar)
    STPrettyPrint(stVar)
    var serialized = STSerialize(stVar)
    Print(serialized)
    var stStrDeserialized = STDeserialize(serialized)
    if (STEqual(stVar, stStrDeserialized) == False)
        STFail("Failed deserialization")
    end
end

void STRunTests()
    STTestSerialization(STString("Test string"))
    STTestSerialization(STInt(51))
    STTestSerialization(STFloat(3.14))

    STQueueTest()
    STDictTest()
    STVectorTest()

    Print("STRunTests successful")
end