#include <xml/addsnode.h>
#include <xml/pathnode.h>
#include <xml/attrnode.h>
#include <string.h>

#define ___ {
#define ____ }

#define X(X) /* g_printerr X */ /* debugging */
#define return_val_if_fail(X,Y) g_return_val_if_fail ((X),(Y)) /* assert */

/*
   HINT: this file implements a walk-tree that stops at the first
   node that matches - that's different over xmlglist.c
 */


inline static xml_GNode*
node_new (const gchar* name, GString* text, gsize off1, gsize off2)
{
    xml_GNode* node = xml_g_node_new_data (name);
    node->text = text;
    node->off = off1;
    node->end = off2;
    return node;
}


xml_GNode*
xml_tree_new (const gchar* name, GString* text)
{
    xml_GNode* node = xml_g_node_new_data (name);
    node->text = text;
    if (! node->text) node->text = g_string_new (0);
    node->off = 0;
    node->end = node->text->len;
    return node;
}
    

/* ______________________________________________________________ */

/**
   this function does search the correct position and adds a markup 
   node there - the return value is the new node so that you can
   add attributes and such - however as only one offset node is 
   given this call is fine for adding passthrough nodes.
  
   The reason for the existance of this function: it is considerably
   faster to look for the single insert position and add a new node
   in there. In all other respects in just calls => xml_node_add_new
   with off2 set to our off1.
 */
xml_GNode*
xml_tree_add1 (xml_GNode* tree, const gchar* name, gsize off)
{
    xml_GNode* node = xml_tree_find_node (tree, off);
    if (! node) return node;
    return xml_node_add_new (node, name, off, off);
}


xml_GNode*
xml_tree_add3 (xml_GNode* tree, const gchar* name, gchar* txt, gchar* end)
{
    if (! tree || ! tree->text) return tree;
    ___ gchar* ptr = tree->text->str;
    return_val_if_fail (ptr+tree->off <= txt && txt <= ptr+tree->end, tree);
    return_val_if_fail (ptr+tree->off <= end && end <= ptr+tree->end, tree);
    if (txt == end) return xml_tree_add1 (tree, name, txt-ptr);
    return xml_tree_add2 (tree, name, txt-ptr, end-ptr);
    ____;
}


/**
   a convenience function that will choose between => xml_tree_add2
   and => xml_tree_add1 depending on off1 == off2 or not. It will also
   reverse args if off2 < off1 and it will set off2 to off1 when
   given as a negative value. No need to differentiate that in apps.
 */
xml_GNode*
xml_tree_add (xml_GNode* tree, const gchar* name, gsize off1, gsize off2)
{
    if (off2 < 0)
	return xml_tree_add1 (tree, name, off1);
    if (off2 == off1)
	return xml_tree_add1 (tree, name, off1);
    if (off2 < off1)
	return xml_tree_add2 (tree, name, off2, off1);
    else
	return xml_tree_add2 (tree, name, off1, off2);
}


/**
   this function does search the correct position and adds a markup 
   node there - the return value is again the new node so that you
   can add attributes and such.
 */
xml_GNode*
xml_tree_add2 (xml_GNode* tree, const gchar* name, gsize off1, gsize off2)
{
    xml_GNode* node = xml_tree_find_node2 (tree, off1, off2);
    if (! node) return node;
    return xml_node_add_new (node, name, off1, off2);
}


/**
   this function adds a new node to the tree - you will probably want
   to call => xml_tree_find_node2 or => xml_tree_find_node before to find the 
   correct node to add to or just use => xml_tree_add or => xml_tree_adds
   which does it too.
 */
xml_GNode*
xml_node_add_new (xml_GNode* tree, const gchar* name, gsize off1, gsize off2)
{
    g_return_val_if_fail (off1 <= off2, 0);

    if (! tree->children) 
    
{
	tree->children = node_new (name, tree->text, off1, off2);
	tree->children->parent = tree;
	return tree->children;
    }


    /* the current node has some children - the off1/off2 may lie
     * between some of these nodes. If however one of the offs is
     * inside a child then we have an invalid-nesting problem.
     */
    ___ xml_GNode *node1;
    
    node1 = tree->children;
    if (off2 <= node1->off) /* prepend */
    
{
	X(("prepend node1.off=%i\n", node1->off));
	return xml_g_node_stick_before_ (
	    node1, node_new (name, tree->text, off1, off2));
    }


    while (off1 >= node1->end)
    
{
	if (! node1->next) /* append */
	
{
	    X(("append node1.end=%i\n", node1->end));
	    return xml_g_node_stick_after_ (
		node1, node_new (name, tree->text, off1, off2));
	}

	
	node1 = node1->next;
    }

    g_assert (node1 && off1 < node1->end);

    if (off1 > node1->off) /* reject */
    
{  /* .. it's inside node1 */
	return 0;
    }

    g_assert (node1 && off1 <= node1->off); /* off1 is before node1 */
    /* hmmmm (node1->prev && off1 >= node1->prev->end); - might fail */

    if (off2 <= node1->off)
    
{ /* insert in between two nodes - no children for the new node */
	X(("insert-no-children before node1.off=%i\n", node1->off));
	return xml_g_node_stick_before_ (
	    node1, node_new (name, tree->text, off1, off2));
    }
 /* this will also hit if off1 == off2 */

    if (! node1->next)
    
{ /* insert instead of last node */
	X(("insert-instead-of-last node1.end=%i\n", node1->end));
	return xml_g_node_group1 (node1,
				  node_new (name, tree->text, off1, off2));
    }


    ___ xml_GNode* node2 = node1;

    while (off2 > node2->off)
    
{
	if (off2 < node2->end) /* reject */
	
{ /* it's inside node2 */
	    return 0;
	}


	if (! node2->next) goto doit; /* between node1 and end */
	node2 = node2->next;
    }


    g_assert (node2 && off2 <= node2->off);
    g_assert (node2 != node1 && node2->prev);
    node2 = node2->prev; /* go back one */

 doit:
    /* off2 is after node2 */
    g_assert (node2 && off2 >= node2->end &&
	      (! node2->next || off2 <= node2->next->off));

    X(("insert node1.end=%i node2.off=%i\n", node1->end, node2->off));
    /* the nodes between node1 and node2 (perhaps the same) are the
     * new children of the current node - and the list is not empty.
     */
    return xml_g_node_group2_ (node1, node2, 
			       node_new (name, tree->text, off1, off2));
    ____;____;
}


/* ____________________________________________________________________ */
/**
   this function does search the correct position and adds a markup 
   node there - the return value is again the new node so that you
   can add attributes and such. However, this routine will try to 
   put the new markups in the most outer positions possible.
 */
xml_GNode*
xml_tree_adds (xml_GNode* tree, const gchar* name, gsize off1, gsize off2)
{
    xml_GNode* node = xml_tree_find_node2 (tree, off1, off2);
    if (! node) return node;

    while (node->off == off1 && node->end == off2)
    
{
	if (! node->parent) 
	    break;
	node = node->parent;
	if (node == tree) 
	    break;
    }


    return xml_node_adds_new (node, name, off1, off2);
}


/**
   just like => xml_node_add_new but zero-width markups are included
   in the new markup. The new code points are marked with *!* herein.
  
   Theoretically one could ask for inclusion-to-left and inclusion-to-right
   extra options but so far there was no need for it - and so this code
   is separated from the => xml_node_add_new routine being the fast one.
  
   Therefore the other routine should be used regularly and this one only
   be called from => xml_tree_adds which will also shortens the parent path
   to be able to enclose the most of subnodes possible. Got it?
 */
xml_GNode*
xml_node_adds_new (xml_GNode* tree, const gchar* name, gsize off1, gsize off2)
{
    g_return_val_if_fail (off1 <= off2, 0);

    if (! tree->children) 
    
{
	tree->children = node_new (name, tree->text, off1, off2);
	tree->children->parent = tree;
	return tree->children;
    }


    /* the current node has some children - the off1/off2 may lie
     * between some of these nodes. If however one of the offs is
     * inside a child then we have an invalid-nesting problem.
     */
    ___ xml_GNode *node1;
    
    node1 = tree->children;
    if (off2 <= node1->off) /* prepend */
    
{
	X(("prepend node1.off=%i\n", node1->off));
	return xml_g_node_stick_before_ (
	    node1, node_new (name, tree->text, off1, off2));
    }


    while (off1 >= node1->end)
    
{
	if (off1 == node1->off) /*!*/
	    break;

	if (! node1->next) /* append */
	
{
	    X(("append node1.end=%i\n", node1->end));
	    return xml_g_node_stick_after_ (
		node1, node_new (name, tree->text, off1, off2));
	}

	
	node1 = node1->next;
    }

    g_assert (node1 && off1 < node1->end);

    if (off1 > node1->off) /* reject */
    
{  /* .. it's inside node1 */
	return 0;
    }

    g_assert (node1 && off1 <= node1->off); /* off1 is before node1 */
    /* hmmmm (node1->prev && off1 >= node1->prev->end); - might fail */

    if (off2 <= node1->off && off2 != node1->end) /*!*/
    
{ /* insert in between two nodes - no children for the new node */
	X(("insert-no-children before node1.off=%i\n", node1->off));
	return xml_g_node_stick_before_ (
	    node1, node_new (name, tree->text, off1, off2));
    }


    if (! node1->next)
    
{ /* insert instead of last node */
	X(("insert-instead-of-last node1.end=%i\n", node1->end));
	return xml_g_node_group1_ (
	    node1, node_new (name, tree->text, off1, off2));
    }


    ___ xml_GNode* node2 = node1;

    while (off2 >= node2->off) /*!*/
    
{
	if (off2 == node2->off && off2 < node2->end) /*!*/
	    break;

	if (off2 < node2->end) /* reject */
	
{ /* it's inside node2 */
	    return 0;
	}


	if (! node2->next) goto doit; /* between node1 and end */
	node2 = node2->next;
    }


    g_assert (node2 && off2 <= node2->off);
    g_assert (node2 != node1 && node2->prev);
    node2 = node2->prev; /* go back one */

 doit:
    /* off2 is after node2 */
    g_assert (node2 && off2 >= node2->end &&
	      (! node2->next || off2 <= node2->next->off));
    
    X(("insert node1.end=%i node2.off=%i\n", node1->end, node2->off));
    /* the nodes between node1 and node2 (perhaps the same) are the
     * new children of the current node - and the list is not empty.
     */
    return xml_g_node_group2_ (node1, node2, 
			       node_new (name, tree->text, off1, off2));
    ____;____;
}


/* ----------------------------------------------------------------- */

/**
   a convenience function originally stemming from the pcre world.
   Instead of handing over a pair of off/len and a marker string
   as arguments, there is a field of integers and a field of strings.
   The integer field is walked up in pairs, i.e. int[0] is off and
   int[1] is end, which is the off/len pair corresponding to the
   string-pointer in the second field, ie. ptr[0]. Likewise the
   int[2]/int[3] matches ptr[1]. The string-field must be a null-
   terminated list - for each corresponding three we call our
   xml_tree_add function above. Compare that with pcre_exec's ovector.
 */
gboolean
xml_tree_add9 (xml_GNode* tree, const int ovector[], const gchar* names[])
{
    g_return_val_if_fail (tree, FALSE);
    g_return_val_if_fail (ovector, FALSE);
    g_return_val_if_fail (names, FALSE);
    g_return_val_if_fail (*names, FALSE);

    for (; *names ; names++, ovector += 2)
    
{
	const gchar* name = *names;
        switch (*name)
        
{
        case 0: continue;
	case ' ':
	    if (ovector[0] == ovector[1])
		continue;
	    /* fallthrough */
        case '=': name++;
            if (tree->text) 
            
{
		gchar* next = 0;
		for (;( next = strchr (name, '=')); name = next+1)
		
{
		    if (name == next) continue;
		    xml_node_attribute_insert (
			tree, g_strndup (name, next-name), 
			g_strndup (tree->text->str + ovector[0], 
				   ovector[1] - ovector[0]));
		    
		}

		if (*name)
		
{
		    xml_node_attribute_insert (
			tree, g_strdup (name), 
			g_strndup (tree->text->str + ovector[0], 
				   ovector[1] - ovector[0]));
		}

            }

            continue;
        case '!': name++;
	    if (! *name) continue;
            if (! xml_tree_add (tree, name, ovector[0], ovector[1]))
                return FALSE;
            continue;
        case '?': name++;
            if (ovector[0] == ovector[1])
		continue;
	    /* fallthrough */
        default:
	    if (! *name) continue;
            xml_tree_add (tree, name, ovector[0], ovector[1]);
            continue;
        }

    }

    return TRUE;
}


/**
   same like => xml_tree_add9 but call => xml_tree_adds instead and
   thereby preferring to create outermost nodes instead of innermost.
  
   As an extension, both 9ers understand a syntax where the first char
   of a name is given as a space - in which case the text is not
   enclosed in markups but cut out and placed as an attribute of the
   node. Additionally, if the element name has a '?' as the first char 
   then it is only added when the span is not null (best for "extra info")
   and if it is '!' then the function returns FALSE when that element name
   could not be added to the tree.
 */
gboolean
xml_tree_adds9 (xml_GNode* tree, const int ovector[], const gchar* names[])
{
    g_return_val_if_fail (tree, FALSE);
    g_return_val_if_fail (ovector, FALSE);
    g_return_val_if_fail (names, FALSE);
    g_return_val_if_fail (*names, FALSE);

    for (; *names ; names++, ovector += 2)
    
{
	const gchar* name = *names;
        switch (*name)
        
{
        case 0: continue;
	case ' ':
	    if (ovector[0] == ovector[1])
		continue;
	    /* fallthrough */
        case '=': name++;
            if (tree->text) 
            
{
		gchar* next = 0;
		for (;( next = strchr (name, '=')); name = next+1)
		
{
		    if (name == next) continue;
		    xml_node_attribute_insert (
			tree, g_strndup (name, name-next), 
			g_strndup (tree->text->str + ovector[0], 
				   ovector[1] - ovector[0]));
		    
		}

		if (*name)
		
{
		    xml_node_attribute_insert (
			tree, g_strdup (name), 
			g_strndup (tree->text->str + ovector[0], 
				   ovector[1] - ovector[0]));
		}

            }

            continue;
        case '!': name++;
	    if (! *name) continue;
            if (! xml_tree_adds (tree, name, ovector[0], ovector[1]))
                return FALSE;
            continue;
        case '?': name++;
            if (ovector[0] == ovector[1])
		continue;
	    /* fallthrough */
        default:
	    if (! *name) continue;
            xml_tree_adds (tree, name, ovector[0], ovector[1]);
            continue;
        }

    }

    return TRUE;
}


/* ----------------------------------------------------------------- */

/* we chose the var names of aboves routine for you to compare */
xml_GNode*
xml_node_group_outer (xml_GNode* node1, xml_GNode* node2, xml_GNode* node)
{
    g_return_val_if_fail (node1 && node2 && node, 0);

    if (! node->text) 
{ 
	node->text = node1->text; 
	node->off = node1->off; 
	node->end = node2->end;
    }
 

    return xml_g_node_group2_ (node1, node2, node);
}


/* make a new node - in between the given nodes */
xml_GNode*
xml_node_group_inner (xml_GNode* node1, xml_GNode* node2, xml_GNode* node)
{
    g_return_val_if_fail (node1 && node2 && node, 0);
    if (node1 == node2) goto subnode; /* reordered as it's quite improbable */

    if (! node->text) 
{ 
	node->text = node1->text; 
	node->off = node1->end; 
	node->end = node2->off;
    }
 

    /* node->parent = node1->parent; */
    if (node1->next == node2)
	return xml_g_node_stick_after_ (node1, node);
    if (node1->next == node2->prev)
	return xml_g_node_group1_ (node1->next, node);
    else
	return xml_g_node_group2_ (node1->next, node2->prev, node);
    
 subnode:
    if (! node->text)
    
{
	node->text = node1->text;
	node->off = node1->off;
	node->end = node1->end;
    }


    node->children = node1->children; node1->children = node; 
    node->parent = node1;  node1 = node->children;
    for (; node1 ; node1 = node1->next) node1->parent = node;
    return node;
}



/* ________________________________________________________________ */

/*
   the returned node is the group-leader "node" being unlink'ed from 
   the tree - you have to destroy it explicitly if that was meant.
  
   Note that we did not specificially provide xml_g_unlink(node) 
   since that would not ensure that the group-children will still be
   referenced somewhere. Instead you can try to simulate some of it with
   xml_node_group_cut(node) - and if the parent was null then it will be a no-op.
   Perhaps just _destroy the node.children right thereafter.
 */
xml_GNode*
xml_node_group_cut (xml_GNode* node)
{
    if (! node) return node;
    if (! node->parent) return node; 
    /* return_val_if_fail (node, node) */
    /* return_val_if_fail (node->parent, node) */

    if (! node->children)
    
{
#      ifdef OPTIMIZESIZE 
	xml_g_node_unlink (node);
	return node;
#      else
	if (node->prev)
	    node->prev->next = node->next;
	else
	    node->parent->children = node->next;
	if (node->next)
	    node->next->prev = node->prev;
	goto returns;
#      endif
    }


    ___ xml_GNode* last = node->children;
    while (1)
    
{   /* re-parent all nodes */
	last->parent = node->parent;
	if (! last->next) break;
	last = last->next;
    }
;
    /* assert (last) */

    if (! node->prev)
    
{
	node->parent->children = node->children;
    }
else
{
	node->prev->next = node->children;
	node->children->prev = node->prev;
    }


    if((last->next = node->next))
	last->next->prev = last;
    ____;
 returns:
    node->next = node->prev = node->children = node->parent = 0;
    return node;
}


xml_GNode*
xml_node_group_inner_alias (xml_GNode* node, const gchar* name)
{
    if (! node || ! name) return node;
    ___ xml_GNode* new1 = xml_g_node_new_data (name);
    new1->text = node->text; new1->off = node->off; new1->end = node->end;
    /* inner_alias means to become the only child of the current parent */
    new1->parent = node;
    new1->children = node->children; 
    node->children = 0; node->children = new1;
    /* reparent children that got adopted from the parent node */
    for (node = new1->children; node ; node = node->next)
	node->parent = new1;
    return new1;
    ____;
}


xml_GNode*
xml_node_group_outer_alias (xml_GNode* node, const gchar* name)
{
    if (! node || ! name) return node;
    ___ xml_GNode* new1 = xml_g_node_new_data (name);
    new1->text = node->text; new1->off = node->off; new1->end = node->end;
    /* outer_alias means be in the place of and become the parent of it */
    new1->next = node->next; new1->prev = node->prev;    
    node->next = node->prev = 0;

    new1->parent = node->parent; node->parent = new1; new1->children = node;
    if (new1->next)
	new1->next->prev = new1;
    if (new1->prev)
	new1->prev->next = new1;
    else if (new1->parent)
	new1->parent->children = new1;
    return new1;
    ____;
}


/* 
   Local variables:
   c-file-style: "stroustrup"
   End:
 */