/*
 * CDOM
 *
 * A C implementation of the Featherweight DOM API
 * The low level needs of a high level abstraction, that we hope meets up somehow
 *
 * 2009, Adam Wright (adw07@doc.ic.ac.uk)
 */

#include <stdlib.h>
#include <stdio.h>

// Constants for the two DOM nodes we model
// Elements
const unsigned short CDOM_NODE_ELEMENT = 1;
// Text Nodes
const unsigned short CDOM_NODE_TEXT = 3;

// Constants for the exceptions that DOM functions can raise
const unsigned short CDOM_GENERAL_ERR = 0;
const unsigned short CDOM_INDEX_SIZE_ERR = 1;
const unsigned short CDOM_HIERARCHY_REQUEST_ERR = 3;
const unsigned short CDOM_INVALID_CHARACTER_ERR = 5;
const unsigned short CDOM_NO_DATA_ALLOWED_ERR = 6;
const unsigned short CDOM_NOT_FOUND_ERR = 8;

struct CDOM_Node
{
    // The type of the node (CDOM_NODE_...)
    unsigned char type;
    
    // The node tagname
    char *tagName;
    
    // The parent node, or NULL if it has no parent
    struct CDOM_Node* parent;
    
    // The child text for text nodes, or NULL if it's an element
    char *childText;
    
    // The children of the node, or NULL if it's a text node
    struct CDOM_NodeList* children;
};

// Models a list (forest) of children as a singly linked list
struct CDOM_NodeList
{
    // The node at this link
    struct CDOM_Node* node;
    
    // The rest of the linked list
    struct CDOM_NodeList *rest;
};

// We include reimplementations of some standard C library functions for basic string manipulation
// So that our analysis tools have some more to get their teeth into
int CDOM_strlen(char* s);
char* CDOM_strcpy(char* s1, char* s2);
int CDOM_strcmp(char* s1, char* s2);

// We give implementations for the same DOM subset as Featherweight DOM
void CDOM_appendChild(struct CDOM_Node* parent, struct CDOM_Node* newChild);
void CDOM_removeChild(struct CDOM_Node* parent, struct CDOM_Node* oldChild);
void CDOM_appendData(struct CDOM_Node* node, char* arg);
void CDOM_deleteData(struct CDOM_Node* node, int offset, int count);
void CDOM_fault(unsigned short code, char* error);
void CDOM_destroyNode(struct CDOM_Node* node);
char* CDOM_substringData(struct CDOM_Node* node, int offset, int count);
char* CDOM_getNodeName(struct CDOM_Node* node);
struct CDOM_Node* CDOM_createNode(char *name);
struct CDOM_Node* CDOM_createTextNode(char *string);
struct CDOM_Node* CDOM_getParentNode(struct CDOM_Node* node);
struct CDOM_Node* CDOM_item(struct CDOM_NodeList* list, int index);
struct CDOM_NodeList* CDOM_getChildNodes(struct CDOM_Node* node);

int CDOM_strlen(char* s)
{
    int i = 0;
    
    // Loop over the characters until we find the NULL terminator
    while (s[i] != 0)
    {
        i++;
    }
    
    return i;
}

char *CDOM_strcpy(char* s1, char* s2)
{
    int i = 0;
    
    // Copy characters from s2 to s1 until we find the NULL terminator for S2
    while (s2[i] != 0)
    {
        s1[i] = s2[i];
        i++;
    }
    
    // Null terminate S1
    s1[i] = 0;
    
    return s1;
}

int CDOM_strcmp(char* s1, char* s2)
{
    int i = 0;

    while (s1[i] != 0 && s2[i] != 0)
    {
        if (s1[i] < s2[i])
        {
            return -1;
        }
        else if (s1[i] > s2[i])
        {
            return 1;
        }            
    }
    
    if (s1[i] == 0 && s2[i] == 0)
    {
        return 0;
    }
    else if (s1[i] == 0)
    {
        return -1;
    }
    else
    {
        return 1;
    }
}

// Creates and returns a new DOM element with the given tag name 
// Will take copies of name; All nodes must be destroyed with destroyNode
struct CDOM_Node* CDOM_createNode(char *name)
{
    struct CDOM_Node *newNode = 0;
    struct CDOM_NodeList *childList = 0;
    char* newTag = 0;
    
    // We cannot create nodes with a NULL name
    if (name == 0)
    {
        CDOM_fault(CDOM_GENERAL_ERR, "Cannot create a node without a name");
        return 0;
    }
    
    int i = 0;
    while (name[i] != 0)
    {
        if (name[i] == '#')
        {
            CDOM_fault(CDOM_INVALID_CHARACTER_ERR, "Cannot create a node with a name containing #");
            return 0;
        }
        
        i++;
    }
    
    // Allocate memory for all heap structures, and bail out if we fail
    newNode = (struct CDOM_Node*)malloc(sizeof(struct CDOM_Node));
    childList = (struct CDOM_NodeList*)malloc(sizeof(struct CDOM_NodeList));
    newTag = (char*)malloc(CDOM_strlen(name) + 1);
    
    if (newNode == 0 || childList == 0 || newTag == 0)        
    {
        if (newNode)
        {
            free(newNode);
        }
        if (childList)
        {
            free(childList);
        }
        if (newTag)
        {
            free(newTag);
        }
        
        CDOM_fault(CDOM_GENERAL_ERR, "Unable to allocate memory for new node");
        return 0;
    }
    
    // Copy the name data into it's new storage        
    CDOM_strcpy(newTag, name);
    
    // The child list of a new node starts empty
    childList->node = 0;
    childList->rest = 0;
    
    // Setup the node properties; new nodes start without a parent
    newNode->type = CDOM_NODE_ELEMENT;
    newNode->childText = NULL;
    newNode->tagName = newTag;
    newNode->parent = 0;
    newNode->children = childList;
    
    return newNode;
}

struct CDOM_Node* CDOM_createTextNode(char *string)
{
    struct CDOM_Node* newNode = 0;
    char* nodeName = 0;
    char* nodeValue = 0;
    
    // We cannot create text nodes with no value
    if (string == 0)
    {
        CDOM_fault(CDOM_GENERAL_ERR, "Cannot create a text node with a NULL value");
        return 0;
    }

    // Allocate memory for all heap structures, and bail out if we fail
    newNode = (struct CDOM_Node*)malloc(sizeof(struct CDOM_Node));
    nodeName = malloc(CDOM_strlen("#text") + 1);
    nodeValue = malloc(CDOM_strlen(string) + 1);
    
    if (newNode == 0 || nodeName == 0 || nodeValue == 0)
    {
        if (newNode)
        {
            free(newNode);
        }
        
        if (nodeName)
        {
            free(nodeName);
        }
        
        if (nodeValue)
        {
            free(nodeValue);
        }
        
        CDOM_fault(CDOM_GENERAL_ERR, "Unable to allocate memory for new node");
        return 0;
    }
    
    // Copy the fixed name for text nodes, and the value into the new storage
    CDOM_strcpy(nodeName, "#text");
    CDOM_strcpy(nodeValue, string);
    
    // Setup the node properties. Note text nodes have no children, or parent
    // This is different from an empty children list!
    newNode->type = CDOM_NODE_TEXT;
    newNode->tagName = nodeName;
    newNode->childText = nodeValue;
    
    newNode->children = 0;
    newNode->parent = 0;
    
    return newNode;
}

void CDOM_destroyNode(struct CDOM_Node* node)
{
    if (node == 0)
    {
        CDOM_fault(CDOM_GENERAL_ERR, "Cannot destroy a NULL node");
        return;
    }
    
    if (node->type == CDOM_NODE_ELEMENT)
    {
        // Free each link in the child list, but not the nodes in the links
        struct CDOM_NodeList* childList = node->children;
        
        while (childList)
        {
            struct CDOM_NodeList* toFree = childList;
            childList = childList->rest;            
            free(toFree);
        }
    }
    else if (node->type == CDOM_NODE_ELEMENT)
    {
        free(node->childText);
    }
    else
    {
        CDOM_fault(CDOM_GENERAL_ERR, "Unknown DOM node type");
    }
    
    free(node->tagName);
    free(node);
}

char* CDOM_getNodeName(struct CDOM_Node* node)
{
    if (node == 0)
    {
        CDOM_fault(CDOM_GENERAL_ERR, "Cannot get the name of a NULL node");
        return 0;
    }
    
    return node->tagName;
}

struct CDOM_Node* CDOM_getParentNode(struct CDOM_Node* node)
{
    if (node == 0)
    {
        CDOM_fault(CDOM_GENERAL_ERR, "Cannot get the parent of a NULL node");
        return 0;
    }
    
    return node->parent;
}

struct CDOM_NodeList* CDOM_getChildNodes(struct CDOM_Node* node)
{
    if (node == 0)
    {
        CDOM_fault(CDOM_GENERAL_ERR, "Cannot get the children of a NULL node");
        return 0;
    }
    
    if (node->type != CDOM_NODE_ELEMENT)
    {
        CDOM_fault(CDOM_GENERAL_ERR, "Cannot get the children of a non element node");
        return 0;
    }
    
    return node->children;
}

void CDOM_appendChild(struct CDOM_Node* parent, struct CDOM_Node* newChild)
{
    struct CDOM_NodeList* list;
    struct CDOM_NodeList* newList;
    
    if (parent == 0 || newChild == 0)
    {
        CDOM_fault(CDOM_GENERAL_ERR, "Cannot append a child if it or it's new parent is NULL");
        return;
    }
    
    // If the new child has a parent already, remove it from that parent
    if (newChild->parent)
    {
        CDOM_removeChild(newChild->parent, newChild);
    }
    newChild->parent = parent;
    
    // Create a new link in the child linked list for the parent, and hook it to the end
    newList = (struct CDOM_NodeList*)malloc(sizeof(struct CDOM_NodeList));
    newList->rest = 0;
    newList->node = newChild;
    
    list = parent->children;    
    while (list->rest != 0)
    {
        list = list->rest;
    }
    
    list->rest = newList;
}

void CDOM_removeChild(struct CDOM_Node* parent, struct CDOM_Node* oldChild)
{
    struct CDOM_NodeList* childList = parent->children;
    struct CDOM_NodeList* prevList = 0;
    
    if (parent == 0 || oldChild == 0)
    {
        CDOM_fault(CDOM_GENERAL_ERR, "Cannot remove a child if it/it's parent is NULL");
        return;
    }
    
    // Find the old child in the parents child list
    while (childList != 0 && childList->node != oldChild)
    {
        prevList = childList;
        childList = childList->rest;
    }
    
    if (childList != 0)
    {
        prevList->rest = childList->rest;
    }
    else
    {
        CDOM_fault(CDOM_NOT_FOUND_ERR, "Trying to remove a child from a parent that didn't own it");
        return;
    }
    
    free(childList);
}

struct CDOM_Node* CDOM_item(struct CDOM_NodeList* list, int index)
{
    struct CDOM_NodeList* itemList;
    
    if (list == 0)
    {
        CDOM_fault(CDOM_GENERAL_ERR, "Cannot get an item from a NULL node");
        return 0;
    }
    
    if (index < 0)
    {
        CDOM_fault(CDOM_INDEX_SIZE_ERR, "Calls to item must have a non-negative index");
        return 0;
    }
    
    // Seek down the list index's worth of steps
    itemList = list;
    for (int i = 0; i < index && itemList != 0; i++)
    {
        itemList = itemList->rest;
    }
    
    // As long as we didn't fall off the end, return the node
    if (itemList == 0)
    {
        CDOM_fault(CDOM_INDEX_SIZE_ERR, "Requested an index beyond the end of a forest");        
        return 0;
    }
    
    return itemList->node;        
}

void CDOM_appendData(struct CDOM_Node* node, char* arg)
{
    char* newData;
    
    if (node == 0)
    {
        CDOM_fault(CDOM_GENERAL_ERR, "Cannot append data to a NULL node");
        return;
    }
    
    if (node->type != CDOM_NODE_TEXT)
    {
        CDOM_fault(CDOM_NO_DATA_ALLOWED_ERR, "Cannot append data to a non-text node");
        return;
    }
    
    if (arg == 0)
    {
        CDOM_fault(CDOM_GENERAL_ERR, "Cannot append NULL data to a node");
        return;
    }
    
    // We recreate the child text entirely for appendData
    newData = (char*)malloc(CDOM_strlen(node->childText) + CDOM_strlen(arg) + 1);    
    CDOM_strcpy(newData, node->childText);
    CDOM_strcpy(newData + CDOM_strlen(node->childText), arg);
    
    free(node->childText);
    node->childText = newData;
}

void CDOM_deleteData(struct CDOM_Node* node, int offset, int count)
{
    char *newData;
    int i;
    int newLength;
    
    if (node == 0)
    {
        CDOM_fault(CDOM_GENERAL_ERR, "Cannot delete data from a NULL node");
        return;
    }
    
    if (node->type != CDOM_NODE_TEXT)
    {
        CDOM_fault(CDOM_NO_DATA_ALLOWED_ERR, "Cannot delete data from a non-text node");
        return;
    }
    
    if (offset < 0 || count < 0)
    {
        CDOM_fault(CDOM_INDEX_SIZE_ERR, "Offset or count cannot be negative");
        return;
    }
    
    if (offset > CDOM_strlen(node->childText))
    {
        CDOM_fault(CDOM_INDEX_SIZE_ERR, "Offset cannot exceed string length");
        return;
    }
    
    // If we would delete past the end of the string, only consider deletion up to the real end
    if (offset + count > CDOM_strlen(node->childText))
    {
        newLength = offset;
    }
    else
    {
        newLength = CDOM_strlen(node->childText);
    }
    
    newData = (char*)malloc(newLength + 1);
    
    // Copy up to the offset into the new string
    i = 0;
    while (i < offset)
    {
        newData[i] = node->childText[i];
        i++;
    }
    
    // Copy up to the final length from the rest of the string
    while (i < newLength)
    {
        newData[i] = (node->childText + count)[i];
        i++;
    }
    
    // Null terminate the new string
    newData[newLength] = 0;
    
    // Replace the old with the new
    free(node->childText);
    node->childText = newData;
}

char* CDOM_substringData(struct CDOM_Node* node, int offset, int count)
{
    char* result = 0;
    int i;
    int copyLength;
    
    if (node == 0)
    {
        CDOM_fault(CDOM_GENERAL_ERR, "Cannot get data from a NULL node");
        return 0;
    }
    
    if (node->type != CDOM_NODE_TEXT)
    {
        CDOM_fault(CDOM_GENERAL_ERR, "Cannot get data from a non-text node");
        return 0;
    }
    
    if (offset < 0 || count < 0)
    {
        CDOM_fault(CDOM_INDEX_SIZE_ERR, "Offset or count cannot be negative");
        return 0;
    }
    
    if (offset > CDOM_strlen(node->childText))
    {
        CDOM_fault(CDOM_INDEX_SIZE_ERR, "Offset cannot exceed string length");
        return 0;
    }
    
    // If we would copy past the end of the string, only consider data up to the real end
    if (offset + count > CDOM_strlen(node->childText))
    {
        copyLength = CDOM_strlen(node->childText) - offset;
    }
    else
    {
        copyLength = count;
    }
    
    result = (char*)malloc(copyLength + 1);
    
    i = 0;
    while (i < copyLength)
    {
        result[i] = (node->childText + offset)[i];
        i++;
    }
    result[copyLength] = 0;
    
    return result;
}

void CDOM_fault(unsigned short code, char* error)
{
    // We just bail out on exception at the moment
    fprintf(stderr, "Fatal DOM error: %s", error);
    exit(code * -1);
}

int main (int argc, const char * argv[])
{
    struct CDOM_Node* n = CDOM_createTextNode("Foo bar baz");
    char* s = CDOM_getNodeName(n);
    CDOM_appendData(n, "Blah");
    char* t = CDOM_substringData(n, 0, 50);
    printf("%s with %s\n", s, t);
    CDOM_deleteData(n, 3, 4);
    t = CDOM_substringData(n, 0, 50);
    printf("%s with %s", s, t);
    return 0;
}