/*
 * $Id$
 *
 * ***** BEGIN GPL LICENSE BLOCK *****
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
 *
 * The Original Code is Copyright (C) 2004 Blender Foundation.
 * All rights reserved.
 *
 * Contributor(s): none yet.
 *
 * ***** END GPL LICENSE BLOCK *****
 */

/** \file blender/blenkernel/intern/depsgraph.c
 *  \ingroup bke
 */

 
#include <stdio.h>
#include <string.h>
#include <math.h>

#include "MEM_guardedalloc.h"

#include "BLI_winstuff.h"
#include "BLI_utildefines.h"
#include "BLI_ghash.h"

#include "DNA_anim_types.h"
#include "DNA_camera_types.h"
#include "DNA_group_types.h"
#include "DNA_lattice_types.h"
#include "DNA_key_types.h"
#include "DNA_material_types.h"
#include "DNA_mesh_types.h"
#include "DNA_node_types.h"
#include "DNA_scene_types.h"
#include "DNA_screen_types.h"
#include "DNA_windowmanager_types.h"

#include "BKE_animsys.h"
#include "BKE_action.h"
#include "BKE_effect.h"
#include "BKE_fcurve.h"
#include "BKE_global.h"
#include "BKE_group.h"
#include "BKE_key.h"
#include "BKE_library.h"
#include "BKE_main.h"
#include "BKE_node.h"
#include "BKE_mball.h"
#include "BKE_modifier.h"
#include "BKE_object.h"
#include "BKE_particle.h"
#include "BKE_pointcache.h"
#include "BKE_scene.h"
#include "BKE_screen.h"
#include "BKE_utildefines.h"

#include "depsgraph_private.h"
 
/* Queue and stack operations for dag traversal 
 *
 * the queue store a list of freenodes to avoid successives alloc/dealloc
 */

DagNodeQueue * queue_create (int slots) 
{
	DagNodeQueue * queue;
	DagNodeQueueElem * elem;
	int i;
	
	queue = MEM_mallocN(sizeof(DagNodeQueue),"DAG queue");
	queue->freenodes = MEM_mallocN(sizeof(DagNodeQueue),"DAG queue");
	queue->count = 0;
	queue->maxlevel = 0;
	queue->first = queue->last = NULL;
	elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem3");
	elem->node = NULL;
	elem->next = NULL;
	queue->freenodes->first = queue->freenodes->last = elem;
	
	for (i = 1; i <slots;i++) {
		elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem4");
		elem->node = NULL;
		elem->next = NULL;
		queue->freenodes->last->next = elem;
		queue->freenodes->last = elem;
	}
	queue->freenodes->count = slots;
	return queue;
}

void queue_raz(DagNodeQueue *queue)
{
	DagNodeQueueElem * elem;
	
	elem = queue->first;
	if (queue->freenodes->last)
		queue->freenodes->last->next = elem;
	else
		queue->freenodes->first = queue->freenodes->last = elem;
	
	elem->node = NULL;
	queue->freenodes->count++;
	while (elem->next) {
		elem = elem->next;
		elem->node = NULL;
		queue->freenodes->count++;
	}
	queue->freenodes->last = elem;
	queue->count = 0;
}

void queue_delete(DagNodeQueue *queue)
{
	DagNodeQueueElem * elem;
	DagNodeQueueElem * temp;
	
	elem = queue->first;
	while (elem) {
		temp = elem;
		elem = elem->next;
		MEM_freeN(temp);
	}
	
	elem = queue->freenodes->first;
	while (elem) {
		temp = elem;
		elem = elem->next;
		MEM_freeN(temp);
	}
	
	MEM_freeN(queue->freenodes);			
	MEM_freeN(queue);			
}

/* insert in queue, remove in front */
void push_queue(DagNodeQueue *queue, DagNode *node)
{
	DagNodeQueueElem * elem;
	int i;

	if (node == NULL) {
		fprintf(stderr,"pushing null node \n");
		return;
	}
	/*fprintf(stderr,"BFS push : %s %d\n",((ID *) node->ob)->name, queue->count);*/

	elem = queue->freenodes->first;
	if (elem != NULL) {
		queue->freenodes->first = elem->next;
		if ( queue->freenodes->last == elem) {
			queue->freenodes->last = NULL;
			queue->freenodes->first = NULL;
		}
		queue->freenodes->count--;
	} else { /* alllocating more */		
		elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem1");
		elem->node = NULL;
		elem->next = NULL;
		queue->freenodes->first = queue->freenodes->last = elem;

		for (i = 1; i <DAGQUEUEALLOC;i++) {
			elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem2");
			elem->node = NULL;
			elem->next = NULL;
			queue->freenodes->last->next = elem;
			queue->freenodes->last = elem;
		}
		queue->freenodes->count = DAGQUEUEALLOC;
			
		elem = queue->freenodes->first;	
		queue->freenodes->first = elem->next;	
	}
	elem->next = NULL;
	elem->node = node;
	if (queue->last != NULL)
		queue->last->next = elem;
	queue->last = elem;
	if (queue->first == NULL) {
		queue->first = elem;
	}
	queue->count++;
}


/* insert in front, remove in front */
void push_stack(DagNodeQueue *queue, DagNode *node)
{
	DagNodeQueueElem * elem;
	int i;

	elem = queue->freenodes->first;	
	if (elem != NULL) {
		queue->freenodes->first = elem->next;
		if ( queue->freenodes->last == elem) {
			queue->freenodes->last = NULL;
			queue->freenodes->first = NULL;
		}
		queue->freenodes->count--;
	} else { /* alllocating more */
		elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem1");
		elem->node = NULL;
		elem->next = NULL;
		queue->freenodes->first = queue->freenodes->last = elem;

		for (i = 1; i <DAGQUEUEALLOC;i++) {
			elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem2");
			elem->node = NULL;
			elem->next = NULL;
			queue->freenodes->last->next = elem;
			queue->freenodes->last = elem;
		}
		queue->freenodes->count = DAGQUEUEALLOC;
			
		elem = queue->freenodes->first;	
		queue->freenodes->first = elem->next;	
	}
	elem->next = queue->first;
	elem->node = node;
	queue->first = elem;
	if (queue->last == NULL)
		queue->last = elem;
	queue->count++;
}


DagNode * pop_queue(DagNodeQueue *queue)
{
	DagNodeQueueElem * elem;
	DagNode *node;

	elem = queue->first;
	if (elem) {
		queue->first = elem->next;
		if (queue->last == elem) {
			queue->last=NULL;
			queue->first=NULL;
		}
		queue->count--;
		if (queue->freenodes->last)
			queue->freenodes->last->next=elem;
		queue->freenodes->last=elem;
		if (queue->freenodes->first == NULL)
			queue->freenodes->first=elem;
		node = elem->node;
		elem->node = NULL;
		elem->next = NULL;
		queue->freenodes->count++;
		return node;
	} else {
		fprintf(stderr,"return null \n");
		return NULL;
	}
}

void	*pop_ob_queue(struct DagNodeQueue *queue) {
	return(pop_queue(queue)->ob);
}

DagNode * get_top_node_queue(DagNodeQueue *queue) 
{
	return queue->first->node;
}

int		queue_count(struct DagNodeQueue *queue){
	return queue->count;
}


DagForest *dag_init(void)
{
	DagForest *forest;
	/* use callocN to init all zero */
	forest = MEM_callocN(sizeof(DagForest),"DAG root");
	return forest;
}

/* isdata = object data... */
// XXX this needs to be extended to be more flexible (so that not only objects are evaluated via depsgraph)...
static void dag_add_driver_relation(AnimData *adt, DagForest *dag, DagNode *node, int isdata)
{
	FCurve *fcu;
	DagNode *node1;
	
	for (fcu= adt->drivers.first; fcu; fcu= fcu->next) {
		ChannelDriver *driver= fcu->driver;
		DriverVar *dvar;
		
		/* loop over variables to get the target relationships */
		for (dvar= driver->variables.first; dvar; dvar= dvar->next) {
			/* only used targets */
			DRIVER_TARGETS_USED_LOOPER(dvar) 
			{
				if (dtar->id) {
					// FIXME: other data types need to be added here so that they can work!
					if (GS(dtar->id->name)==ID_OB) {
						Object *ob= (Object *)dtar->id;
						
						/* normal channel-drives-channel */
						node1 = dag_get_node(dag, dtar->id);
						
						/* check if bone... */
						if ((ob->type==OB_ARMATURE) && 
							( ((dtar->rna_path) && strstr(dtar->rna_path, "pose.bones[")) || 
							  ((dtar->flag & DTAR_FLAG_STRUCT_REF) && (dtar->pchan_name[0])) )) 
						{
							dag_add_relation(dag, node1, node, isdata?DAG_RL_DATA_DATA:DAG_RL_DATA_OB, "Driver");
						}
						/* check if ob data */
						else if (dtar->rna_path && strstr(dtar->rna_path, "data."))
							dag_add_relation(dag, node1, node, isdata?DAG_RL_DATA_DATA:DAG_RL_DATA_OB, "Driver");
						/* normal */
						else
							dag_add_relation(dag, node1, node, isdata?DAG_RL_OB_DATA:DAG_RL_OB_OB, "Driver");
					}
				}
			}
			DRIVER_TARGETS_LOOPER_END
		}
	}
}

static void dag_add_collision_field_relation(DagForest *dag, Scene *scene, Object *ob, DagNode *node)
{
	Base *base;
	DagNode *node2;

	// would be nice to have a list of colliders here
	// so for now walk all objects in scene check 'same layer rule'
	for(base = scene->base.first; base; base= base->next) {
		if((base->lay & ob->lay) && base->object->pd) {
			Object *ob1= base->object;
			if((ob1->pd->deflect || ob1->pd->forcefield) && (ob1 != ob))  {
				node2 = dag_get_node(dag, ob1);					
				dag_add_relation(dag, node2, node, DAG_RL_DATA_DATA|DAG_RL_OB_DATA, "Field Collision");
			}
		}
	}
}

static void build_dag_object(DagForest *dag, DagNode *scenenode, Scene *scene, Object *ob, int mask)
{
	bConstraint *con;
	DagNode * node;
	DagNode * node2;
	DagNode * node3;
	Key *key;
	ParticleSystem *psys;
	int addtoroot= 1;
	
	node = dag_get_node(dag, ob);
	
	if ((ob->data) && (mask&DAG_RL_DATA)) {
		node2 = dag_get_node(dag,ob->data);
		dag_add_relation(dag,node,node2,DAG_RL_DATA, "Object-Data Relation");
		node2->first_ancestor = ob;
		node2->ancestor_count += 1;
	}
	
	if (ob->type == OB_ARMATURE) {
		if (ob->pose){
			bPoseChannel *pchan;
			bConstraint *con;
			
			for (pchan = ob->pose->chanbase.first; pchan; pchan=pchan->next) {
				for (con = pchan->constraints.first; con; con=con->next) {
					bConstraintTypeInfo *cti= constraint_get_typeinfo(con);
					ListBase targets = {NULL, NULL};
					bConstraintTarget *ct;
					
					if (cti && cti->get_constraint_targets) {
						cti->get_constraint_targets(con, &targets);
						
						for (ct= targets.first; ct; ct= ct->next) {
							if (ct->tar && ct->tar != ob) {
								// fprintf(stderr,"armature %s target :%s \n", ob->id.name, target->id.name);
								node3 = dag_get_node(dag, ct->tar);
								
								if (ct->subtarget[0])
									dag_add_relation(dag,node3,node, DAG_RL_OB_DATA|DAG_RL_DATA_DATA, cti->name);
								else if(ELEM3(con->type, CONSTRAINT_TYPE_FOLLOWPATH, CONSTRAINT_TYPE_CLAMPTO, CONSTRAINT_TYPE_SPLINEIK)) 	
									dag_add_relation(dag,node3,node, DAG_RL_DATA_DATA|DAG_RL_OB_DATA, cti->name);
								else
									dag_add_relation(dag,node3,node, DAG_RL_OB_DATA, cti->name);
							}
						}
						
						if (cti->flush_constraint_targets)
							cti->flush_constraint_targets(con, &targets, 1);
					}
					
				}
			}
		}
	}
	
	/* driver dependencies, nla modifiers */
#if 0 // XXX old animation system
	if(ob->nlastrips.first) {
		bActionStrip *strip;
		bActionChannel *chan;
		for(strip= ob->nlastrips.first; strip; strip= strip->next) {
			if(strip->modifiers.first) {
				bActionModifier *amod;
				for(amod= strip->modifiers.first; amod; amod= amod->next) {
					if(amod->ob) {
						node2 = dag_get_node(dag, amod->ob);
						dag_add_relation(dag, node2, node, DAG_RL_DATA_DATA|DAG_RL_OB_DATA, "NLA Strip Modifier");
					}
				}
			}
		}
	}
#endif // XXX old animation system
	if (ob->adt)
		dag_add_driver_relation(ob->adt, dag, node, (ob->type == OB_ARMATURE)); // XXX isdata arg here doesn't give an accurate picture of situation
		
	key= ob_get_key(ob);
	if (key && key->adt)
		dag_add_driver_relation(key->adt, dag, node, 1);

	if (ob->modifiers.first) {
		ModifierData *md;
		
		for(md=ob->modifiers.first; md; md=md->next) {
			ModifierTypeInfo *mti = modifierType_getInfo(md->type);
			
			if (mti->updateDepgraph) mti->updateDepgraph(md, dag, scene, ob, node);
		}
	}
	if (ob->parent) {
		node2 = dag_get_node(dag,ob->parent);
		
		switch(ob->partype) {
			case PARSKEL:
				dag_add_relation(dag,node2,node,DAG_RL_DATA_DATA|DAG_RL_OB_OB, "Parent");
				break;
			case PARVERT1: case PARVERT3: case PARBONE:
				dag_add_relation(dag,node2,node,DAG_RL_DATA_OB|DAG_RL_OB_OB, "Vertex Parent");
				break;
			default:
				if(ob->parent->type==OB_LATTICE) 
					dag_add_relation(dag,node2,node,DAG_RL_DATA_DATA|DAG_RL_OB_OB, "Lattice Parent");
				else if(ob->parent->type==OB_CURVE) {
					Curve *cu= ob->parent->data;
					if(cu->flag & CU_PATH) 
						dag_add_relation(dag,node2,node,DAG_RL_DATA_OB|DAG_RL_OB_OB, "Curve Parent");
					else
						dag_add_relation(dag,node2,node,DAG_RL_OB_OB, "Curve Parent");
				}
				else
					dag_add_relation(dag,node2,node,DAG_RL_OB_OB, "Parent");
		}
		/* exception case: parent is duplivert */
		if(ob->type==OB_MBALL && (ob->parent->transflag & OB_DUPLIVERTS)) {
			dag_add_relation(dag, node2, node, DAG_RL_DATA_DATA|DAG_RL_OB_OB, "Duplivert");
		}
		
		addtoroot = 0;
	}
	if (ob->proxy) {
		node2 = dag_get_node(dag, ob->proxy);
		dag_add_relation(dag, node, node2, DAG_RL_DATA_DATA|DAG_RL_OB_OB, "Proxy");
		/* inverted relation, so addtoroot shouldn't be set to zero */
	}
	
	if (ob->transflag & OB_DUPLI) {
		if((ob->transflag & OB_DUPLIGROUP) && ob->dup_group) {
			GroupObject *go;
			for(go= ob->dup_group->gobject.first; go; go= go->next) {
				if(go->ob) {
					node2 = dag_get_node(dag, go->ob);
					/* node2 changes node1, this keeps animations updated in groups?? not logical? */
					dag_add_relation(dag, node2, node, DAG_RL_OB_OB, "Dupligroup");
				}
			}
		}
	}
    
	/* softbody collision  */
	if ((ob->type==OB_MESH) || (ob->type==OB_CURVE) || (ob->type==OB_LATTICE)) {
		if(modifiers_isSoftbodyEnabled(ob) || modifiers_isClothEnabled(ob) || ob->particlesystem.first)
			dag_add_collision_field_relation(dag, scene, ob, node); /* TODO: use effectorweight->group */
	}
	
	/* object data drivers */
	if (ob->data) {
		AnimData *adt= BKE_animdata_from_id((ID *)ob->data);
		if (adt)
			dag_add_driver_relation(adt, dag, node, 1);
	}
	
	/* object type/data relationships */
	switch (ob->type) {
		case OB_CAMERA:
		{
			Camera *cam = (Camera *)ob->data;
			
			if (cam->dof_ob) {
				node2 = dag_get_node(dag, cam->dof_ob);
				dag_add_relation(dag,node2,node,DAG_RL_OB_OB, "Camera DoF");
			}
		}
			break;
		case OB_MBALL: 
		{
			Object *mom= find_basis_mball(scene, ob);
			
			if(mom!=ob) {
				node2 = dag_get_node(dag, mom);
				dag_add_relation(dag,node,node2,DAG_RL_DATA_DATA|DAG_RL_OB_DATA, "Metaball");  // mom depends on children!
			}
		}
			break;
		case OB_CURVE:
		{
			Curve *cu= ob->data;
			
			if(cu->bevobj) {
				node2 = dag_get_node(dag, cu->bevobj);
				dag_add_relation(dag,node2,node,DAG_RL_DATA_DATA|DAG_RL_OB_DATA, "Curve Bevel");
			}
			if(cu->taperobj) {
				node2 = dag_get_node(dag, cu->taperobj);
				dag_add_relation(dag,node2,node,DAG_RL_DATA_DATA|DAG_RL_OB_DATA, "Curve Taper");
			}
		}
			break;
		case OB_FONT: 
		{
			Curve *cu= ob->data;
			
			if(cu->textoncurve) {
				node2 = dag_get_node(dag, cu->textoncurve);
				dag_add_relation(dag,node2,node,DAG_RL_DATA_DATA|DAG_RL_OB_DATA, "Texture On Curve");
			}
		}
			break;
	}
	
	/* particles */
	psys= ob->particlesystem.first;
	if(psys) {
		GroupObject *go;

		for(; psys; psys=psys->next) {
			BoidRule *rule = NULL;
			BoidState *state = NULL;
			ParticleSettings *part= psys->part;
			ListBase *effectors = NULL;
			EffectorCache *eff;

			dag_add_relation(dag, node, node, DAG_RL_OB_DATA, "Particle-Object Relation");

			if(!psys_check_enabled(ob, psys))
				continue;

			if(ELEM(part->phystype,PART_PHYS_KEYED,PART_PHYS_BOIDS)) {
				ParticleTarget *pt = psys->targets.first;

				for(; pt; pt=pt->next) {
					if(pt->ob && BLI_findlink(&pt->ob->particlesystem, pt->psys-1)) {
						node2 = dag_get_node(dag, pt->ob);
						dag_add_relation(dag, node2, node, DAG_RL_DATA_DATA|DAG_RL_OB_DATA, "Particle Targets");
					}
			   }
			}

			if(part->ren_as == PART_DRAW_OB && part->dup_ob) {
				node2 = dag_get_node(dag, part->dup_ob);
				dag_add_relation(dag, node, node2, DAG_RL_OB_OB, "Particle Object Visualisation");
				if(part->dup_ob->type == OB_MBALL)
					dag_add_relation(dag, node, node2, DAG_RL_DATA_DATA, "Particle Object Visualisation");
			}

			if(part->ren_as == PART_DRAW_GR && part->dup_group) {
				for(go=part->dup_group->gobject.first; go; go=go->next) {
					node2 = dag_get_node(dag, go->ob);
					dag_add_relation(dag, node, node2, DAG_RL_OB_OB, "Particle Group Visualisation");
				}
			}

			effectors = pdInitEffectors(scene, ob, psys, part->effector_weights);

			if(effectors) for(eff = effectors->first; eff; eff=eff->next) {
				if(eff->psys) {
					node2 = dag_get_node(dag, eff->ob);
					dag_add_relation(dag, node2, node, DAG_RL_DATA_DATA|DAG_RL_OB_DATA, "Particle Field");
				}
			}

			pdEndEffectors(&effectors);

			if(part->boids) {
				for(state = part->boids->states.first; state; state=state->next) {
					for(rule = state->rules.first; rule; rule=rule->next) {
						Object *ruleob = NULL;
						if(rule->type==eBoidRuleType_Avoid)
							ruleob = ((BoidRuleGoalAvoid*)rule)->ob;
						else if(rule->type==eBoidRuleType_FollowLeader)
							ruleob = ((BoidRuleFollowLeader*)rule)->ob;

						if(ruleob) {
							node2 = dag_get_node(dag, ruleob);
							dag_add_relation(dag, node2, node, DAG_RL_OB_DATA, "Boid Rule");
						}
					}
				}
			}
		}
	}
	
	/* object constraints */
	for (con = ob->constraints.first; con; con=con->next) {
		bConstraintTypeInfo *cti= constraint_get_typeinfo(con);
		ListBase targets = {NULL, NULL};
		bConstraintTarget *ct;
		
		if (cti && cti->get_constraint_targets) {
			cti->get_constraint_targets(con, &targets);
			
			for (ct= targets.first; ct; ct= ct->next) {
				Object *obt;
				
				if (ct->tar)
					obt= ct->tar;
				else
					continue;
				
				node2 = dag_get_node(dag, obt);
				if (ELEM(con->type, CONSTRAINT_TYPE_FOLLOWPATH, CONSTRAINT_TYPE_CLAMPTO))
					dag_add_relation(dag, node2, node, DAG_RL_DATA_OB|DAG_RL_OB_OB, cti->name);
				else {
					if (ELEM3(obt->type, OB_ARMATURE, OB_MESH, OB_LATTICE) && (ct->subtarget[0]))
						dag_add_relation(dag, node2, node, DAG_RL_DATA_OB|DAG_RL_OB_OB, cti->name);
					else
						dag_add_relation(dag, node2, node, DAG_RL_OB_OB, cti->name);
				}
				addtoroot = 0;
			}
			
			if (cti->flush_constraint_targets)
				cti->flush_constraint_targets(con, &targets, 1);
		}
	}

	if (addtoroot == 1 )
		dag_add_relation(dag,scenenode,node,DAG_RL_SCENE, "Scene Relation");
}

struct DagForest *build_dag(Main *bmain, Scene *sce, short mask) 
{
	Base *base;
	Object *ob;
	Group *group;
	GroupObject *go;
	DagNode *node;
	DagNode *scenenode;
	DagForest *dag;
	DagAdjList *itA;

	dag = sce->theDag;
	sce->dagisvalid=1;
	if ( dag)
		free_forest( dag ); 
	else {
		dag = dag_init();
		sce->theDag = dag;
	}
	
	/* add base node for scene. scene is always the first node in DAG */
	scenenode = dag_add_node(dag, sce);	
	
	/* add current scene objects */
	for(base = sce->base.first; base; base= base->next) {
		ob= base->object;
		
		build_dag_object(dag, scenenode, sce, ob, mask);
		if(ob->proxy)
			build_dag_object(dag, scenenode, sce, ob->proxy, mask);
		
		/* handled in next loop */
		if(ob->dup_group) 
			ob->dup_group->id.flag |= LIB_DOIT;
	}
	
	/* add groups used in current scene objects */
	for(group= bmain->group.first; group; group= group->id.next) {
		if(group->id.flag & LIB_DOIT) {
			for(go= group->gobject.first; go; go= go->next) {
				build_dag_object(dag, scenenode, sce, go->ob, mask);
			}
			group->id.flag &= ~LIB_DOIT;
		}
	}
	
	/* Now all relations were built, but we need to solve 1 exceptional case;
	   When objects have multiple "parents" (for example parent + constraint working on same object)
	   the relation type has to be synced. One of the parents can change, and should give same event to child */
	
	/* nodes were callocced, so we can use node->color for temporal storage */
	for(node = sce->theDag->DagNode.first; node; node= node->next) {
		if(node->type==ID_OB) {
			for(itA = node->child; itA; itA= itA->next) {
				if(itA->node->type==ID_OB) {
					itA->node->color |= itA->type;
				}
			}
		}
	}
	/* now set relations equal, so that when only one parent changes, the correct recalcs are found */
	for(node = sce->theDag->DagNode.first; node; node= node->next) {
		if(node->type==ID_OB) {
			for(itA = node->child; itA; itA= itA->next) {
				if(itA->node->type==ID_OB) {
					itA->type |= itA->node->color;
				}
			}
		}
	}
	
	// cycle detection and solving
	// solve_cycles(dag);	
	
	return dag;
}


void free_forest(DagForest *Dag) 
{  /* remove all nodes and deps */
	DagNode *tempN;
	DagAdjList *tempA;	
	DagAdjList *itA;
	DagNode *itN = Dag->DagNode.first;
	
	while (itN) {
		itA = itN->child;	
		while (itA) {
			tempA = itA;
			itA = itA->next;
			MEM_freeN(tempA);			
		}
		
		itA = itN->parent;	
		while (itA) {
			tempA = itA;
			itA = itA->next;
			MEM_freeN(tempA);			
		}
		
		tempN = itN;
		itN = itN->next;
		MEM_freeN(tempN);
	}

	BLI_ghash_free(Dag->nodeHash, NULL, NULL);
	Dag->nodeHash= NULL;
	Dag->DagNode.first = NULL;
	Dag->DagNode.last = NULL;
	Dag->numNodes = 0;

}

DagNode * dag_find_node (DagForest *forest,void * fob)
{
	if(forest->nodeHash)
		return BLI_ghash_lookup(forest->nodeHash, fob);

	return NULL;
}

static int ugly_hack_sorry= 1;	// prevent type check

/* no checking of existence, use dag_find_node first or dag_get_node */
DagNode * dag_add_node (DagForest *forest, void * fob)
{
	DagNode *node;
		
	node = MEM_callocN(sizeof(DagNode),"DAG node");
	if (node) {
		node->ob = fob;
		node->color = DAG_WHITE;

		if(ugly_hack_sorry) node->type = GS(((ID *) fob)->name);	// sorry, done for pose sorting
		if (forest->numNodes) {
			((DagNode *) forest->DagNode.last)->next = node;
			forest->DagNode.last = node;
			forest->numNodes++;
		} else {
			forest->DagNode.last = node;
			forest->DagNode.first = node;
			forest->numNodes = 1;
		}

		if(!forest->nodeHash)
			forest->nodeHash= BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "dag_add_node gh");
		BLI_ghash_insert(forest->nodeHash, fob, node);
	}

	return node;
}

DagNode * dag_get_node (DagForest *forest,void * fob)
{
	DagNode *node;
	
	node = dag_find_node (forest, fob);	
	if (!node) 
		node = dag_add_node(forest, fob);
	return node;
}



DagNode * dag_get_sub_node (DagForest *forest,void * fob)
{
	DagNode *node;
	DagAdjList *mainchild, *prev=NULL;
	
	mainchild = ((DagNode *) forest->DagNode.first)->child;
	/* remove from first node (scene) adj list if present */
	while (mainchild) {
		if (mainchild->node == fob) {
			if (prev) {
				prev->next = mainchild->next;
				MEM_freeN(mainchild);
				break;
			} else {
				((DagNode *) forest->DagNode.first)->child = mainchild->next;
				MEM_freeN(mainchild);
				break;
			}
		}
		prev = mainchild;
		mainchild = mainchild->next;
	}
	node = dag_find_node (forest, fob);	
	if (!node) 
		node = dag_add_node(forest, fob);
	return node;
}

static void dag_add_parent_relation(DagForest *UNUSED(forest), DagNode *fob1, DagNode *fob2, short rel, const char *name) 
{
	DagAdjList *itA = fob2->parent;
	
	while (itA) { /* search if relation exist already */
		if (itA->node == fob1) {
			itA->type |= rel;
			itA->count += 1;
			return;
		}
		itA = itA->next;
	}
	/* create new relation and insert at head. MALLOC alert! */
	itA = MEM_mallocN(sizeof(DagAdjList),"DAG adj list");
	itA->node = fob1;
	itA->type = rel;
	itA->count = 1;
	itA->next = fob2->parent;
	itA->name = name;
	fob2->parent = itA;
}

void dag_add_relation(DagForest *forest, DagNode *fob1, DagNode *fob2, short rel, const char *name) 
{
	DagAdjList *itA = fob1->child;
	
	/* parent relation is for cycle checking */
	dag_add_parent_relation(forest, fob1, fob2, rel, name);

	while (itA) { /* search if relation exist already */
		if (itA->node == fob2) {
			itA->type |= rel;
			itA->count += 1;
			return;
		}
		itA = itA->next;
	}
	/* create new relation and insert at head. MALLOC alert! */
	itA = MEM_mallocN(sizeof(DagAdjList),"DAG adj list");
	itA->node = fob2;
	itA->type = rel;
	itA->count = 1;
	itA->next = fob1->child;
	itA->name = name;
	fob1->child = itA;
}

static const char *dag_node_name(DagNode *node)
{
	if(node->ob == NULL)
		return "null";
	else if(ugly_hack_sorry)
		return ((ID*)(node->ob))->name+2;
	else
		return ((bPoseChannel*)(node->ob))->name;
}

#if 0
static void dag_node_print_dependencies(DagNode *node)
{
	DagAdjList *itA;

	printf("%s depends on:\n", dag_node_name(node));

	for(itA= node->parent; itA; itA= itA->next)
		printf("  %s through %s\n", dag_node_name(itA->node), itA->name);
	printf("\n");
}
#endif

static int dag_node_print_dependency_recurs(DagNode *node, DagNode *endnode)
{
	DagAdjList *itA;

	if(node->color == DAG_BLACK)
		return 0;

	node->color= DAG_BLACK;

	if(node == endnode)
		return 1;

	for(itA= node->parent; itA; itA= itA->next) {
		if(dag_node_print_dependency_recurs(itA->node, endnode)) {
			printf("  %s depends on %s through %s.\n", dag_node_name(node), dag_node_name(itA->node), itA->name);
			return 1;
		}
	}

	return 0;
}

static void dag_node_print_dependency_cycle(DagForest *dag, DagNode *startnode, DagNode *endnode, const char *name)
{
	DagNode *node;

	for(node = dag->DagNode.first; node; node= node->next)
		node->color= DAG_WHITE;

	printf("  %s depends on %s through %s.\n", dag_node_name(endnode), dag_node_name(startnode), name);
	dag_node_print_dependency_recurs(startnode, endnode);
	printf("\n");
}

static int dag_node_recurs_level(DagNode *node, int level)
{
	DagAdjList *itA;
	int newlevel;

	node->color= DAG_BLACK;	/* done */
	newlevel= ++level;
	
	for(itA= node->parent; itA; itA= itA->next) {
		if(itA->node->color==DAG_WHITE) {
			itA->node->ancestor_count= dag_node_recurs_level(itA->node, level);
			newlevel= MAX2(newlevel, level+itA->node->ancestor_count);
		}
		else
			newlevel= MAX2(newlevel, level+itA->node->ancestor_count);
	}
	
	return newlevel;
}

static void dag_check_cycle(DagForest *dag)
{
	DagNode *node;
	DagAdjList *itA;

	/* tag nodes unchecked */
	for(node = dag->DagNode.first; node; node= node->next)
		node->color= DAG_WHITE;
	
	for(node = dag->DagNode.first; node; node= node->next) {
		if(node->color==DAG_WHITE) {
			node->ancestor_count= dag_node_recurs_level(node, 0);
		}
	}
	
	/* check relations, and print errors */
	for(node = dag->DagNode.first; node; node= node->next) {
		for(itA= node->parent; itA; itA= itA->next) {
			if(itA->node->ancestor_count > node->ancestor_count) {
				if(node->ob && itA->node->ob) {
					printf("Dependency cycle detected:\n");
					dag_node_print_dependency_cycle(dag, itA->node, node, itA->name);
				}
			}
		}
	}

	/* parent relations are only needed for cycle checking, so free now */
	for(node = dag->DagNode.first; node; node= node->next) {
		while (node->parent) {
			itA = node->parent->next;
			MEM_freeN(node->parent);			
			node->parent = itA;
		}
	}
}

/*
 * MainDAG is the DAG of all objects in current scene
 * used only for drawing there is one also in each scene
 */
static DagForest * MainDag = NULL;

DagForest *getMainDag(void)
{
	return MainDag;
}


void setMainDag(DagForest *dag)
{
	MainDag = dag;
}


/*
 * note for BFS/DFS
 * in theory we should sweep the whole array
 * but in our case the first node is the scene
 * and is linked to every other object
 *
 * for general case we will need to add outer loop
 */

/*
 * ToDo : change pos kludge
 */

/* adjust levels for drawing in oops space */
void graph_bfs(void)
{
	DagNode *node;
	DagNodeQueue *nqueue;
	int pos[50];
	int i;
	DagAdjList *itA;
	int minheight;
	
	/* fprintf(stderr,"starting BFS \n ------------\n"); */	
	nqueue = queue_create(DAGQUEUEALLOC);
	for ( i=0; i<50; i++)
		pos[i] = 0;
	
	/* Init
	 * dagnode.first is alway the root (scene) 
	 */
	node = MainDag->DagNode.first;
	while(node) {
		node->color = DAG_WHITE;
		node->BFS_dist = 9999;
		node->k = 0;
		node = node->next;
	}
	
	node = MainDag->DagNode.first;
	if (node->color == DAG_WHITE) {
		node->color = DAG_GRAY;
		node->BFS_dist = 1;
		push_queue(nqueue,node);  
		while(nqueue->count) {
			node = pop_queue(nqueue);
			
			minheight = pos[node->BFS_dist];
			itA = node->child;
			while(itA != NULL) {
				if(itA->node->color == DAG_WHITE) {
					itA->node->color = DAG_GRAY;
					itA->node->BFS_dist = node->BFS_dist + 1;
					itA->node->k = (float) minheight;
					push_queue(nqueue,itA->node);
				}
				
				 else {
					fprintf(stderr,"bfs not dag tree edge color :%i \n",itA->node->color);
				}
				 
				
				itA = itA->next;
			}
			if (pos[node->BFS_dist] > node->k ) {
				pos[node->BFS_dist] += 1;				
				node->k = (float) pos[node->BFS_dist];
			} else {
				pos[node->BFS_dist] = (int) node->k +1;
			}
			set_node_xy(node, node->BFS_dist*DEPSX*2, pos[node->BFS_dist]*DEPSY*2);
			node->color = DAG_BLACK;
			/*
			 fprintf(stderr,"BFS node : %20s %i %5.0f %5.0f\n",((ID *) node->ob)->name,node->BFS_dist, node->x, node->y);	
			 */
		}
	}
	queue_delete(nqueue);
}

int pre_and_post_BFS(DagForest *dag, short mask, graph_action_func pre_func, graph_action_func post_func, void **data) {
	DagNode *node;
	
	node = dag->DagNode.first;
	return pre_and_post_source_BFS(dag, mask,  node,  pre_func,  post_func, data);
}


int pre_and_post_source_BFS(DagForest *dag, short mask, DagNode *source, graph_action_func pre_func, graph_action_func post_func, void **data)
{
	DagNode *node;
	DagNodeQueue *nqueue;
	DagAdjList *itA;
	int	retval = 0;
	/* fprintf(stderr,"starting BFS \n ------------\n"); */	
	
	/* Init
		* dagnode.first is alway the root (scene) 
		*/
	node = dag->DagNode.first;
	nqueue = queue_create(DAGQUEUEALLOC);
	while(node) {
		node->color = DAG_WHITE;
		node->BFS_dist = 9999;
		node = node->next;
	}
	
	node = source;
	if (node->color == DAG_WHITE) {
		node->color = DAG_GRAY;
		node->BFS_dist = 1;
		pre_func(node->ob,data);
		
		while(nqueue->count) {
			node = pop_queue(nqueue);
			
			itA = node->child;
			while(itA != NULL) {
				if((itA->node->color == DAG_WHITE) && (itA->type & mask)) {
					itA->node->color = DAG_GRAY;
					itA->node->BFS_dist = node->BFS_dist + 1;
					push_queue(nqueue,itA->node);
					pre_func(node->ob,data);
				}
				
				else { // back or cross edge
					retval = 1;
				}
				itA = itA->next;
			}
			post_func(node->ob,data);
			node->color = DAG_BLACK;
			/*
			 fprintf(stderr,"BFS node : %20s %i %5.0f %5.0f\n",((ID *) node->ob)->name,node->BFS_dist, node->x, node->y);	
			 */
		}
	}
	queue_delete(nqueue);
	return retval;
}

/* non recursive version of DFS, return queue -- outer loop present to catch odd cases (first level cycles)*/
DagNodeQueue * graph_dfs(void)
{
	DagNode *node;
	DagNodeQueue *nqueue;
	DagNodeQueue *retqueue;
	int pos[50];
	int i;
	DagAdjList *itA;
	int time;
	int skip = 0;
	int minheight;
	int maxpos=0;
	int	is_cycle = 0;
	/*
	 *fprintf(stderr,"starting DFS \n ------------\n");
	 */	
	nqueue = queue_create(DAGQUEUEALLOC);
	retqueue = queue_create(MainDag->numNodes);
	for ( i=0; i<50; i++)
		pos[i] = 0;
	
	/* Init
	 * dagnode.first is alway the root (scene) 
	 */
	node = MainDag->DagNode.first;
	while(node) {
		node->color = DAG_WHITE;
		node->DFS_dist = 9999;
		node->DFS_dvtm = node->DFS_fntm = 9999;
		node->k = 0;
		node =  node->next;
	}
	
	time = 1;
	
	node = MainDag->DagNode.first;

	do {
	if (node->color == DAG_WHITE) {
		node->color = DAG_GRAY;
		node->DFS_dist = 1;
		node->DFS_dvtm = time;
		time++;
		push_stack(nqueue,node);  
			
		while(nqueue->count) {
			//graph_print_queue(nqueue);

			 skip = 0;
			node = get_top_node_queue(nqueue);
			
			minheight = pos[node->DFS_dist];

			itA = node->child;
			while(itA != NULL) {
				if(itA->node->color == DAG_WHITE) {
					itA->node->DFS_dvtm = time;
					itA->node->color = DAG_GRAY;

					time++;
					itA->node->DFS_dist = node->DFS_dist + 1;
					itA->node->k = (float) minheight;
					push_stack(nqueue,itA->node);
					skip = 1;
					break;
				} else { 
					if (itA->node->color == DAG_GRAY) { // back edge
						fprintf(stderr,"dfs back edge :%15s %15s \n",((ID *) node->ob)->name, ((ID *) itA->node->ob)->name);
						is_cycle = 1;
					} else if (itA->node->color == DAG_BLACK) {
						;
						/* already processed node but we may want later to change distance either to shorter to longer.
						 * DFS_dist is the first encounter  
						*/
						/*if (node->DFS_dist >= itA->node->DFS_dist)
							itA->node->DFS_dist = node->DFS_dist + 1;
						 	
							fprintf(stderr,"dfs forward or cross edge :%15s %i-%i %15s %i-%i \n",
								((ID *) node->ob)->name,
								node->DFS_dvtm, 
								node->DFS_fntm, 
								((ID *) itA->node->ob)->name, 
								itA->node->DFS_dvtm,
								itA->node->DFS_fntm);
					*/
					} else 
						fprintf(stderr,"dfs unknown edge \n");
				}
				itA = itA->next;
			}			

			if (!skip) {
				node = pop_queue(nqueue);
				node->color = DAG_BLACK;

				node->DFS_fntm = time;
				time++;
				if (node->DFS_dist > maxpos)
					maxpos = node->DFS_dist;
				if (pos[node->DFS_dist] > node->k ) {
					pos[node->DFS_dist] += 1;				
					node->k = (float) pos[node->DFS_dist];
				} else {
					pos[node->DFS_dist] = (int) node->k +1;
				}
				set_node_xy(node, node->DFS_dist*DEPSX*2, pos[node->DFS_dist]*DEPSY*2);
				
				/*
				 fprintf(stderr,"DFS node : %20s %i %i %i %i\n",((ID *) node->ob)->name,node->BFS_dist, node->DFS_dist, node->DFS_dvtm, node->DFS_fntm ); 	
				*/
				 push_stack(retqueue,node);
				
			}
		}
	}
		node = node->next;
	} while (node);
//	  fprintf(stderr,"i size : %i \n", maxpos);
	  
	queue_delete(nqueue);
	  return(retqueue);
}

/* unused */
int pre_and_post_DFS(DagForest *dag, short mask, graph_action_func pre_func, graph_action_func post_func, void **data) {
	DagNode *node;

	node = dag->DagNode.first;
	return pre_and_post_source_DFS(dag, mask,  node,  pre_func,  post_func, data);
}

int pre_and_post_source_DFS(DagForest *dag, short mask, DagNode *source, graph_action_func pre_func, graph_action_func post_func, void **data)
{
	DagNode *node;
	DagNodeQueue *nqueue;
	DagAdjList *itA;
	int time;
	int skip = 0;
	int retval = 0;
	/*
	 *fprintf(stderr,"starting DFS \n ------------\n");
	 */	
	nqueue = queue_create(DAGQUEUEALLOC);
	
	/* Init
		* dagnode.first is alway the root (scene) 
		*/
	node = dag->DagNode.first;
	while(node) {
		node->color = DAG_WHITE;
		node->DFS_dist = 9999;
		node->DFS_dvtm = node->DFS_fntm = 9999;
		node->k = 0;
		node =  node->next;
	}
	
	time = 1;
	
	node = source;
	do {
		if (node->color == DAG_WHITE) {
			node->color = DAG_GRAY;
			node->DFS_dist = 1;
			node->DFS_dvtm = time;
			time++;
			push_stack(nqueue,node);  
			pre_func(node->ob,data);

			while(nqueue->count) {
				skip = 0;
				node = get_top_node_queue(nqueue);
								
				itA = node->child;
				while(itA != NULL) {
					if((itA->node->color == DAG_WHITE) && (itA->type & mask) ) {
						itA->node->DFS_dvtm = time;
						itA->node->color = DAG_GRAY;
						
						time++;
						itA->node->DFS_dist = node->DFS_dist + 1;
						push_stack(nqueue,itA->node);
						pre_func(node->ob,data);

						skip = 1;
						break;
					} else {
						if (itA->node->color == DAG_GRAY) {// back edge
							retval = 1;
						}
//						else if (itA->node->color == DAG_BLACK) { // cross or forward
//							;
					}
					itA = itA->next;
				}			
				
				if (!skip) {
					node = pop_queue(nqueue);
					node->color = DAG_BLACK;
					
					node->DFS_fntm = time;
					time++;
					post_func(node->ob,data);
				}
			}
		}
		node = node->next;
	} while (node);
	queue_delete(nqueue);
	return(retval);
}


// used to get the obs owning a datablock
struct DagNodeQueue *get_obparents(struct DagForest	*dag, void *ob) 
{
	DagNode * node, *node1;
	DagNodeQueue *nqueue;
	DagAdjList *itA;

	node = dag_find_node(dag,ob);
	if(node==NULL) {
		return NULL;
	}
	else if (node->ancestor_count == 1) { // simple case
		nqueue = queue_create(1);
		push_queue(nqueue,node);
	} else {	// need to go over the whole dag for adj list
		nqueue = queue_create(node->ancestor_count);
		
		node1 = dag->DagNode.first;
		do {
			if (node1->DFS_fntm > node->DFS_fntm) { // a parent is finished after child. must check adj list
				itA = node->child;
				while(itA != NULL) {
					if ((itA->node == node) && (itA->type == DAG_RL_DATA)) {
						push_queue(nqueue,node);
					}
					itA = itA->next;
				}
			}
			node1 = node1->next;
		} while (node1);
	}
	return nqueue;
}

struct DagNodeQueue *get_first_ancestors(struct DagForest	*dag, void *ob)
{
	DagNode * node, *node1;
	DagNodeQueue *nqueue;
	DagAdjList *itA;
	
	node = dag_find_node(dag,ob);
	
	// need to go over the whole dag for adj list
	nqueue = queue_create(node->ancestor_count);
	
	node1 = dag->DagNode.first;
	do {
		if (node1->DFS_fntm > node->DFS_fntm) { 
			itA = node->child;
			while(itA != NULL) {
				if (itA->node == node) {
					push_queue(nqueue,node);
				}
				itA = itA->next;
			}
		}
		node1 = node1->next;
	} while (node1);
	
	return nqueue;	
}

// standard DFS list
struct DagNodeQueue *get_all_childs(struct DagForest	*dag, void *ob)
{
	DagNode *node;
	DagNodeQueue *nqueue;
	DagNodeQueue *retqueue;
	DagAdjList *itA;
	int time;
	int skip = 0;

	nqueue = queue_create(DAGQUEUEALLOC);
	retqueue = queue_create(dag->numNodes); // was MainDag... why? (ton)
	
	node = dag->DagNode.first;
	while(node) {
		node->color = DAG_WHITE;
		node =  node->next;
	}
	
	time = 1;
	
	node = dag_find_node(dag, ob);   // could be done in loop above (ton)
	if(node) { // can be null for newly added objects
		
		node->color = DAG_GRAY;
		time++;
		push_stack(nqueue,node);  
		
		while(nqueue->count) {
			
			skip = 0;
			node = get_top_node_queue(nqueue);
					
			itA = node->child;
			while(itA != NULL) {
				if(itA->node->color == DAG_WHITE) {
					itA->node->DFS_dvtm = time;
					itA->node->color = DAG_GRAY;
					
					time++;
					push_stack(nqueue,itA->node);
					skip = 1;
					break;
				} 
				itA = itA->next;
			}			
			
			if (!skip) {
				node = pop_queue(nqueue);
				node->color = DAG_BLACK;
				
				time++;
				push_stack(retqueue,node);			
			}
		}
	}
	queue_delete(nqueue);
	return(retqueue);
}

/* unused */
short	are_obs_related(struct DagForest	*dag, void *ob1, void *ob2) {
	DagNode * node;
	DagAdjList *itA;
	
	node = dag_find_node(dag, ob1);
	
	itA = node->child;
	while(itA != NULL) {
		if(itA->node->ob == ob2) {
			return itA->node->type;
		} 
		itA = itA->next;
	}
	return DAG_NO_RELATION;
}

int	is_acyclic( DagForest	*dag) {
	return dag->is_acyclic;
}

void set_node_xy(DagNode *node, float x, float y)
{
	 node->x = x;
	node->y = y;
}


/* debug test functions */

void graph_print_queue(DagNodeQueue *nqueue)
{	
	DagNodeQueueElem *queueElem;
	
	queueElem = nqueue->first;
	while(queueElem) {
		fprintf(stderr,"** %s %i %i-%i ",((ID *) queueElem->node->ob)->name,queueElem->node->color,queueElem->node->DFS_dvtm,queueElem->node->DFS_fntm);
		queueElem = queueElem->next;		
	}
	fprintf(stderr,"\n");
}

void graph_print_queue_dist(DagNodeQueue *nqueue)
{	
	DagNodeQueueElem *queueElem;
	int count;
	
	queueElem = nqueue->first;
	count = 0;
	while(queueElem) {
		fprintf(stderr,"** %25s %2.2i-%2.2i ",((ID *) queueElem->node->ob)->name,queueElem->node->DFS_dvtm,queueElem->node->DFS_fntm);
		while (count < queueElem->node->DFS_dvtm-1) { fputc(' ',stderr); count++;}
		fputc('|',stderr); 
		while (count < queueElem->node->DFS_fntm-2) { fputc('-',stderr); count++;}
		fputc('|',stderr);
		fputc('\n',stderr);
		count = 0;
		queueElem = queueElem->next;		
	}
	fprintf(stderr,"\n");
}

void graph_print_adj_list(void)
{
	DagNode *node;
	DagAdjList *itA;
	
	node = (getMainDag())->DagNode.first;
	while(node) {
		fprintf(stderr,"node : %s col: %i",((ID *) node->ob)->name, node->color);		
		itA = node->child;
		while (itA) {
			fprintf(stderr,"-- %s ",((ID *) itA->node->ob)->name);
			
			itA = itA->next;
		}
		fprintf(stderr,"\n");
		node = node->next;
	}
}

/* ************************ API *********************** */

/* mechanism to allow editors to be informed of depsgraph updates,
   to do their own updates based on changes... */
static void (*EditorsUpdateCb)(Main *bmain, ID *id)= NULL;

void DAG_editors_update_cb(void (*func)(Main *bmain, ID *id))
{
	EditorsUpdateCb= func;
}

static void dag_editors_update(Main *bmain, ID *id)
{
	if(EditorsUpdateCb)
		EditorsUpdateCb(bmain, id);
}

/* groups with objects in this scene need to be put in the right order as well */
static void scene_sort_groups(Main *bmain, Scene *sce)
{
	Base *base;
	Group *group;
	GroupObject *go;
	Object *ob;
	
	/* test; are group objects all in this scene? */
	for(ob= bmain->object.first; ob; ob= ob->id.next) {
		ob->id.flag &= ~LIB_DOIT;
		ob->id.newid= NULL;	/* newid abuse for GroupObject */
	}
	for(base = sce->base.first; base; base= base->next)
		base->object->id.flag |= LIB_DOIT;
	
	for(group= bmain->group.first; group; group= group->id.next) {
		for(go= group->gobject.first; go; go= go->next) {
			if((go->ob->id.flag & LIB_DOIT)==0)
				break;
		}
		/* this group is entirely in this scene */
		if(go==NULL) {
			ListBase listb= {NULL, NULL};
			
			for(go= group->gobject.first; go; go= go->next)
				go->ob->id.newid= (ID *)go;
			
			/* in order of sorted bases we reinsert group objects */
			for(base = sce->base.first; base; base= base->next) {
				
				if(base->object->id.newid) {
					go= (GroupObject *)base->object->id.newid;
					base->object->id.newid= NULL;
					BLI_remlink( &group->gobject, go);
					BLI_addtail( &listb, go);
				}
			}
			/* copy the newly sorted listbase */
			group->gobject= listb;
		}
	}
}

/* sort the base list on dependency order */
void DAG_scene_sort(Main *bmain, Scene *sce)
{
	DagNode *node;
	DagNodeQueue *nqueue;
	DagAdjList *itA;
	int time;
	int skip = 0;
	ListBase tempbase;
	Base *base;
	
	tempbase.first= tempbase.last= NULL;
	
	build_dag(bmain, sce, DAG_RL_ALL_BUT_DATA);
	
	dag_check_cycle(sce->theDag);

	nqueue = queue_create(DAGQUEUEALLOC);
	
	for(node = sce->theDag->DagNode.first; node; node= node->next) {
		node->color = DAG_WHITE;
	}
	
	time = 1;
	
	node = sce->theDag->DagNode.first;
	
	node->color = DAG_GRAY;
	time++;
	push_stack(nqueue,node);  
	
	while(nqueue->count) {
		
		skip = 0;
		node = get_top_node_queue(nqueue);
		
		itA = node->child;
		while(itA != NULL) {
			if(itA->node->color == DAG_WHITE) {
				itA->node->DFS_dvtm = time;
				itA->node->color = DAG_GRAY;
				
				time++;
				push_stack(nqueue,itA->node);
				skip = 1;
				break;
			} 
			itA = itA->next;
		}			
		
		if (!skip) {
			if (node) {
				node = pop_queue(nqueue);
				if (node->ob == sce)	// we are done
					break ;
				node->color = DAG_BLACK;
				
				time++;
				base = sce->base.first;
				while (base && base->object != node->ob)
					base = base->next;
				if(base) {
					BLI_remlink(&sce->base,base);
					BLI_addhead(&tempbase,base);
				}
			}	
		}
	}
	
	// temporal correction for circular dependancies
	base = sce->base.first;
	while (base) {
		BLI_remlink(&sce->base,base);
		BLI_addhead(&tempbase,base);
		//if(G.f & G_DEBUG) 
			printf("cyclic %s\n", base->object->id.name);
		base = sce->base.first;
	}
	
	sce->base = tempbase;
	queue_delete(nqueue);
	
	/* all groups with objects in this scene gets resorted too */
	scene_sort_groups(bmain, sce);
	
	if(G.f & G_DEBUG) {
		printf("\nordered\n");
		for(base = sce->base.first; base; base= base->next) {
			printf(" %s\n", base->object->id.name);
		}
	}
	/* temporal...? */
	sce->recalc |= SCE_PRV_CHANGED;	/* test for 3d preview */
}

/* node was checked to have lasttime != curtime and is if type ID_OB */
static void flush_update_node(DagNode *node, unsigned int layer, int curtime)
{
	DagAdjList *itA;
	Object *ob, *obc;
	int oldflag, changed=0;
	unsigned int all_layer;
	
	node->lasttime= curtime;
	
	ob= node->ob;
	if(ob && (ob->recalc & OB_RECALC_ALL)) {
		all_layer= node->scelay;

		/* got an object node that changes, now check relations */
		for(itA = node->child; itA; itA= itA->next) {
			all_layer |= itA->lay;
			/* the relationship is visible */
			if((itA->lay & layer)) { // XXX || (itA->node->ob == obedit)
				if(itA->node->type==ID_OB) {
					obc= itA->node->ob;
					oldflag= obc->recalc;
					
					/* got a ob->obc relation, now check if flag needs flush */
					if(ob->recalc & OB_RECALC_OB) {
						if(itA->type & DAG_RL_OB_OB) {
							//printf("ob %s changes ob %s\n", ob->id.name, obc->id.name);
							obc->recalc |= OB_RECALC_OB;
						}
						if(itA->type & DAG_RL_OB_DATA) {
							//printf("ob %s changes obdata %s\n", ob->id.name, obc->id.name);
							obc->recalc |= OB_RECALC_DATA;
						}
					}
					if(ob->recalc & OB_RECALC_DATA) {
						if(itA->type & DAG_RL_DATA_OB) {
							//printf("obdata %s changes ob %s\n", ob->id.name, obc->id.name);
							obc->recalc |= OB_RECALC_OB;
						}
						if(itA->type & DAG_RL_DATA_DATA) {
							//printf("obdata %s changes obdata %s\n", ob->id.name, obc->id.name);
							obc->recalc |= OB_RECALC_DATA;
						}
					}
					if(oldflag!=obc->recalc) changed= 1;
				}
			}
		}
		/* even nicer, we can clear recalc flags...  */
		if((all_layer & layer)==0) { // XXX && (ob != obedit)) {
			/* but existing displaylists or derivedmesh should be freed */
			if(ob->recalc & OB_RECALC_DATA)
				object_free_display(ob);
			
			ob->recalc &= ~OB_RECALC_ALL;
		}
	}
	
	/* check case where child changes and parent forcing obdata to change */
	/* should be done regardless if this ob has recalc set */
	/* could merge this in with loop above...? (ton) */
	for(itA = node->child; itA; itA= itA->next) {
		/* the relationship is visible */
		if((itA->lay & layer)) {		// XXX  || (itA->node->ob == obedit)
			if(itA->node->type==ID_OB) {
				obc= itA->node->ob;
				/* child moves */
				if((obc->recalc & OB_RECALC_ALL)==OB_RECALC_OB) {
					/* parent has deforming info */
					if(itA->type & (DAG_RL_OB_DATA|DAG_RL_DATA_DATA)) {
						// printf("parent %s changes ob %s\n", ob->id.name, obc->id.name);
						obc->recalc |= OB_RECALC_DATA;
					}
				}
			}
		}
	}
	
	/* we only go deeper if node not checked or something changed  */
	for(itA = node->child; itA; itA= itA->next) {
		if(changed || itA->node->lasttime!=curtime) 
			flush_update_node(itA->node, layer, curtime);
	}
	
}

/* node was checked to have lasttime != curtime , and is of type ID_OB */
static unsigned int flush_layer_node(Scene *sce, DagNode *node, int curtime)
{
	DagAdjList *itA;
	
	node->lasttime= curtime;
	node->lay= node->scelay;
	
	for(itA = node->child; itA; itA= itA->next) {
		if(itA->node->type==ID_OB) {
			if(itA->node->lasttime!=curtime) {
				itA->lay= flush_layer_node(sce, itA->node, curtime);  // lay is only set once for each relation
			}
			else itA->lay= itA->node->lay;
			
			node->lay |= itA->lay;
		}
	}

	return node->lay;
}

/* node was checked to have lasttime != curtime , and is of type ID_OB */
static void flush_pointcache_reset(Scene *scene, DagNode *node, int curtime, int reset)
{
	DagAdjList *itA;
	Object *ob;
	
	node->lasttime= curtime;
	
	for(itA = node->child; itA; itA= itA->next) {
		if(itA->node->type==ID_OB) {
			if(itA->node->lasttime!=curtime) {
				ob= (Object*)(itA->node->ob);

				if(reset || (ob->recalc & OB_RECALC_ALL)) {
					if(BKE_ptcache_object_reset(scene, ob, PTCACHE_RESET_DEPSGRAPH))
						ob->recalc |= OB_RECALC_DATA;

					flush_pointcache_reset(scene, itA->node, curtime, 1);
				}
				else
					flush_pointcache_reset(scene, itA->node, curtime, 0);
			}
		}
	}
}

/* flush layer flags to dependencies */
static void dag_scene_flush_layers(Scene *sce, int lay)
{
	DagNode *node, *firstnode;
	DagAdjList *itA;
	Base *base;
	int lasttime;

	firstnode= sce->theDag->DagNode.first;  // always scene node

	for(itA = firstnode->child; itA; itA= itA->next)
		itA->lay= 0;

	sce->theDag->time++;	// so we know which nodes were accessed
	lasttime= sce->theDag->time;

	/* update layer flags in nodes */
	for(base= sce->base.first; base; base= base->next) {
		node= dag_get_node(sce->theDag, base->object);
		node->scelay= base->object->lay;
	}

	/* ensure cameras are set as if they are on a visible layer, because
	   they ared still used for rendering or setting the camera view */
	if(sce->camera) {
		node= dag_get_node(sce->theDag, sce->camera);
		node->scelay |= lay;
	}

#ifdef DURIAN_CAMERA_SWITCH
	{
		TimeMarker *m;

		for(m= sce->markers.first; m; m= m->next) {
			if(m->camera) {
				node= dag_get_node(sce->theDag, m->camera);
				node->scelay |= lay;
			}
		}
	}
#endif

	/* flush layer nodes to dependencies */
	for(itA = firstnode->child; itA; itA= itA->next)
		if(itA->node->lasttime!=lasttime && itA->node->type==ID_OB) 
			flush_layer_node(sce, itA->node, lasttime);
}

static void dag_tag_renderlayers(Scene *sce, unsigned int lay)
{
	if(sce->nodetree) {
		bNode *node;
		Base *base;
		unsigned int lay_changed= 0;
		
		for(base= sce->base.first; base; base= base->next)
			if(base->lay & lay)
				if(base->object->recalc)
					lay_changed |= base->lay;
			
		for(node= sce->nodetree->nodes.first; node; node= node->next) {
			if(node->id==(ID *)sce) {
				SceneRenderLayer *srl= BLI_findlink(&sce->r.layers, node->custom1);
				if(srl && (srl->lay & lay_changed))
					NodeTagChanged(sce->nodetree, node);
			}
		}
	}
}

/* flushes all recalc flags in objects down the dependency tree */
void DAG_scene_flush_update(Main *bmain, Scene *sce, unsigned int lay, const short time)
{
	DagNode *firstnode;
	DagAdjList *itA;
	Object *ob;
	int lasttime;
	
	if(sce->theDag==NULL) {
		printf("DAG zero... not allowed to happen!\n");
		DAG_scene_sort(bmain, sce);
	}
	
	firstnode= sce->theDag->DagNode.first;  // always scene node

	/* first we flush the layer flags */
	dag_scene_flush_layers(sce, lay);

	/* then we use the relationships + layer info to flush update events */
	sce->theDag->time++;	// so we know which nodes were accessed
	lasttime= sce->theDag->time;
	for(itA = firstnode->child; itA; itA= itA->next)
		if(itA->node->lasttime!=lasttime && itA->node->type==ID_OB)
			flush_update_node(itA->node, lay, lasttime);

	/* if update is not due to time change, do pointcache clears */
	if(!time) {
		sce->theDag->time++;	// so we know which nodes were accessed
		lasttime= sce->theDag->time;
		for(itA = firstnode->child; itA; itA= itA->next) {
			if(itA->node->lasttime!=lasttime && itA->node->type==ID_OB)  {
				ob= (Object*)(itA->node->ob);

				if(ob->recalc & OB_RECALC_ALL) {
					if(BKE_ptcache_object_reset(sce, ob, PTCACHE_RESET_DEPSGRAPH))
						ob->recalc |= OB_RECALC_DATA;

					flush_pointcache_reset(sce, itA->node, lasttime, 1);
				}
				else
					flush_pointcache_reset(sce, itA->node, lasttime, 0);
			}
		}
	}
	
	dag_tag_renderlayers(sce, lay);
}

static int object_modifiers_use_time(Object *ob)
{
	ModifierData *md;
	
	/* check if a modifier in modifier stack needs time input */
	for (md=ob->modifiers.first; md; md=md->next)
		if (modifier_dependsOnTime(md))
			return 1;
	
	/* check whether any modifiers are animated */
	if (ob->adt) {
		AnimData *adt = ob->adt;
		
		/* action - check for F-Curves with paths containing 'modifiers[' */
		if (adt->action) {
			FCurve *fcu;
			
			for (fcu = adt->action->curves.first; fcu; fcu = fcu->next) {
				if (fcu->rna_path && strstr(fcu->rna_path, "modifiers["))
					return 1;
			}
		}
		
		// XXX: also, should check NLA strips, though for now assume that nobody uses
		// that and we can omit that for performance reasons...
	}
	
	return 0;
}

static short animdata_use_time(AnimData *adt)
{
	NlaTrack *nlt;
	
	if(adt==NULL) return 0;
	
	/* check action - only if assigned, and it has anim curves */
	if (adt->action && adt->action->curves.first)
		return 1;
	
	/* check NLA tracks + strips */
	for (nlt= adt->nla_tracks.first; nlt; nlt= nlt->next) {
		if (nlt->strips.first)
			return 1;
	}
	
	return 0;
}

static void dag_object_time_update_flags(Object *ob)
{
	if(ob->constraints.first) {
		bConstraint *con;
		for (con = ob->constraints.first; con; con=con->next) {
			bConstraintTypeInfo *cti= constraint_get_typeinfo(con);
			ListBase targets = {NULL, NULL};
			bConstraintTarget *ct;
			
			if (cti && cti->get_constraint_targets) {
				cti->get_constraint_targets(con, &targets);
				
				for (ct= targets.first; ct; ct= ct->next) {
					if (ct->tar) {
						ob->recalc |= OB_RECALC_OB;
						break;
					}
				}
				
				if (cti->flush_constraint_targets)
					cti->flush_constraint_targets(con, &targets, 1);
			}
		}
	}
	
	if(ob->parent) {
		/* motion path or bone child */
		if(ob->parent->type==OB_CURVE || ob->parent->type==OB_ARMATURE) ob->recalc |= OB_RECALC_OB;
	}
	
#if 0 // XXX old animation system
	if(ob->nlastrips.first) {
		if(ob->dup_group) {
			bActionStrip *strip;
			/* this case is for groups with nla, whilst nla target has no action or nla */
			for(strip= ob->nlastrips.first; strip; strip= strip->next) {
				if(strip->object)
					strip->object->recalc |= OB_RECALC_ALL;
			}
		}
	}
#endif // XXX old animation system
	
	if(animdata_use_time(ob->adt)) {
		ob->recalc |= OB_RECALC_OB;
		ob->adt->recalc |= ADT_RECALC_ANIM;
	}
	
	if((ob->adt) && (ob->type==OB_ARMATURE)) ob->recalc |= OB_RECALC_DATA;
	
	if(object_modifiers_use_time(ob)) ob->recalc |= OB_RECALC_DATA;
	if((ob->pose) && (ob->pose->flag & POSE_CONSTRAINTS_TIMEDEPEND)) ob->recalc |= OB_RECALC_DATA;
	
	{
		AnimData *adt= BKE_animdata_from_id((ID *)ob->data);
		Mesh *me;
		Curve *cu;
		Lattice *lt;
		
		switch(ob->type) {
			case OB_MESH:
				me= ob->data;
				if(me->key) {
					if(!(ob->shapeflag & OB_SHAPE_LOCK)) {
						ob->recalc |= OB_RECALC_DATA;
					}
				}
				if(ob->particlesystem.first)
					ob->recalc |= OB_RECALC_DATA;
				break;
			case OB_CURVE:
			case OB_SURF:
				cu= ob->data;
				if(cu->key) {
					if(!(ob->shapeflag & OB_SHAPE_LOCK)) {
						ob->recalc |= OB_RECALC_DATA;
					}
				}
				break;
			case OB_FONT:
				cu= ob->data;
				if(cu->nurb.first==NULL && cu->str && cu->vfont)
					ob->recalc |= OB_RECALC_DATA;
				break;
			case OB_LATTICE:
				lt= ob->data;
				if(lt->key) {
					if(!(ob->shapeflag & OB_SHAPE_LOCK)) {
						ob->recalc |= OB_RECALC_DATA;
					}
				}
					break;
			case OB_MBALL:
				if(ob->transflag & OB_DUPLI) ob->recalc |= OB_RECALC_DATA;
				break;
		}
		
		if(animdata_use_time(adt)) {
			ob->recalc |= OB_RECALC_DATA;
			adt->recalc |= ADT_RECALC_ANIM;
		}

		if(ob->particlesystem.first) {
			ParticleSystem *psys= ob->particlesystem.first;

			for(; psys; psys=psys->next) {
				if(psys_check_enabled(ob, psys)) {
					ob->recalc |= OB_RECALC_DATA;
					break;
				}
			}
		}
	}		
}
/* flag all objects that need recalc, for changes in time for example */
/* do_time: make this optional because undo resets objects to their animated locations without this */
void DAG_scene_update_flags(Main *bmain, Scene *scene, unsigned int lay, const short do_time)
{
	Base *base;
	Object *ob;
	Group *group;
	GroupObject *go;
	Scene *sce_iter;

	/* set ob flags where animated systems are */
	for(SETLOOPER(scene, sce_iter, base)) {
		ob= base->object;

		if(do_time) {
			/* now if DagNode were part of base, the node->lay could be checked... */
			/* we do all now, since the scene_flush checks layers and clears recalc flags even */
			dag_object_time_update_flags(ob);
		}

		/* handled in next loop */
		if(ob->dup_group)
			ob->dup_group->id.flag |= LIB_DOIT;
	}

	if(do_time) {
		/* we do groups each once */
		for(group= bmain->group.first; group; group= group->id.next) {
			if(group->id.flag & LIB_DOIT) {
				for(go= group->gobject.first; go; go= go->next) {
					dag_object_time_update_flags(go->ob);
				}
			}
		}
	}

	for(sce_iter= scene; sce_iter; sce_iter= sce_iter->set)
		DAG_scene_flush_update(bmain, sce_iter, lay, 1);
	
	if(do_time) {
		/* test: set time flag, to disable baked systems to update */
		for(SETLOOPER(scene, sce_iter, base)) {
			ob= base->object;
			if(ob->recalc)
				ob->recalc |= OB_RECALC_TIME;
		}

		/* hrmf... an exception to look at once, for invisible camera object we do it over */
		if(scene->camera)
			dag_object_time_update_flags(scene->camera);
	}

	/* and store the info in groupobject */
	for(group= bmain->group.first; group; group= group->id.next) {
		if(group->id.flag & LIB_DOIT) {
			for(go= group->gobject.first; go; go= go->next) {
				go->recalc= go->ob->recalc;
				// printf("ob %s recalc %d\n", go->ob->id.name, go->recalc);
			}
			group->id.flag &= ~LIB_DOIT;
		}
	}
	
}

static void dag_current_scene_layers(Main *bmain, Scene **sce, unsigned int *lay)
{
	wmWindowManager *wm;
	wmWindow *win;

	/* only one scene supported currently, making more scenes work
	   correctly requires changes beyond just the dependency graph */

	*sce= NULL;
	*lay= 0;

	if((wm= bmain->wm.first)) {
		/* if we have a windowmanager, look into windows */
		for(win=wm->windows.first; win; win=win->next) {
			if(win->screen) {
				if(!*sce) *sce= win->screen->scene;
				*lay |= BKE_screen_visible_layers(win->screen, win->screen->scene);
			}
		}
	}
	else {
		/* if not, use the first sce */
		*sce= bmain->scene.first;
		if(*sce) *lay= (*sce)->lay;

		/* XXX for background mode, we should get the scene
		   from somewhere, for the -S option, but it's in
		   the context, how to get it here? */
	}
}

void DAG_ids_flush_update(Main *bmain, int time)
{
	Scene *sce;
	unsigned int lay;

	dag_current_scene_layers(bmain, &sce, &lay);

	if(sce)
		DAG_scene_flush_update(bmain, sce, lay, time);
}

void DAG_on_visible_update(Main *bmain, const short do_time)
{
	Scene *scene;
	Base *base;
	Object *ob;
	Group *group;
	GroupObject *go;
	DagNode *node;
	unsigned int lay, oblay;

	dag_current_scene_layers(bmain, &scene, &lay);

	if(scene && scene->theDag) {
		Scene *sce_iter;
		/* derivedmeshes and displists are not saved to file so need to be
		   remade, tag them so they get remade in the scene update loop,
		   note armature poses or object matrices are preserved and do not
		   require updates, so we skip those */
		dag_scene_flush_layers(scene, lay);

		for(SETLOOPER(scene, sce_iter, base)) {
			ob= base->object;
			node= (sce_iter->theDag)? dag_get_node(sce_iter->theDag, ob): NULL;
			oblay= (node)? node->lay: ob->lay;

			if((oblay & lay) & ~scene->lay_updated) {
				if(ELEM6(ob->type, OB_MESH, OB_CURVE, OB_SURF, OB_FONT, OB_MBALL, OB_LATTICE))
					ob->recalc |= OB_RECALC_DATA;
				if(ob->dup_group) 
					ob->dup_group->id.flag |= LIB_DOIT;
			}
		}

		for(group= bmain->group.first; group; group= group->id.next) {
			if(group->id.flag & LIB_DOIT) {
				for(go= group->gobject.first; go; go= go->next) {
					if(ELEM6(go->ob->type, OB_MESH, OB_CURVE, OB_SURF, OB_FONT, OB_MBALL, OB_LATTICE))
						go->ob->recalc |= OB_RECALC_DATA;
					if(go->ob->proxy_from)
						go->ob->recalc |= OB_RECALC_OB;
				}
				
				group->id.flag &= ~LIB_DOIT;
			}
		}

		/* now tag update flags, to ensure deformers get calculated on redraw */
		DAG_scene_update_flags(bmain, scene, lay, do_time);
		scene->lay_updated |= lay;
	}
}

static void dag_id_flush_update__isDependentTexture(void *userData, Object *UNUSED(ob), ID **idpoin)
{
	struct { ID *id; int is_dependent; } *data = userData;
	
	if(*idpoin && GS((*idpoin)->name)==ID_TE) {
		if (data->id == (*idpoin))
			data->is_dependent = 1;
	}
}

static void dag_id_flush_update(Scene *sce, ID *id)
{
	Main *bmain= G.main;
	Object *obt, *ob= NULL;
	short idtype;

	/* here we flush a few things before actual scene wide flush, mostly
	   due to only objects and not other datablocks being in the depsgraph */

	/* set flags & pointcache for object */
	if(GS(id->name) == ID_OB) {
		ob= (Object*)id;
		BKE_ptcache_object_reset(sce, ob, PTCACHE_RESET_DEPSGRAPH);

		if(ob->recalc & OB_RECALC_DATA) {
			/* all users of this ob->data should be checked */
			id= ob->data;

			/* no point in trying in this cases */
			if(id && id->us <= 1) {
				dag_editors_update(bmain, id);
				id= NULL;
			}
		}
	}

	/* set flags & pointcache for object data */
	if(id) {
		idtype= GS(id->name);

		if(ELEM7(idtype, ID_ME, ID_CU, ID_MB, ID_LA, ID_LT, ID_CA, ID_AR)) {
			for(obt=bmain->object.first; obt; obt= obt->id.next) {
				if(!(ob && obt == ob) && obt->data == id) {
					obt->recalc |= OB_RECALC_DATA;
					BKE_ptcache_object_reset(sce, obt, PTCACHE_RESET_DEPSGRAPH);
				}
			}
		}
		
		/* set flags based on textures - can influence depgraph via modifiers */
		if(idtype == ID_TE) {
			for(obt=bmain->object.first; obt; obt= obt->id.next) {
				struct { ID *id; int is_dependent; } data;
				data.id= id;
				data.is_dependent= 0;

				modifiers_foreachIDLink(obt, dag_id_flush_update__isDependentTexture, &data);
				if (data.is_dependent)
					obt->recalc |= OB_RECALC_DATA;

				/* particle settings can use the texture as well */
				if(obt->particlesystem.first) {
					ParticleSystem *psys = obt->particlesystem.first;
					MTex **mtexp, *mtex;
					int a;
					for(; psys; psys=psys->next) {
						mtexp = psys->part->mtex;
						for(a=0; a<MAX_MTEX; a++, mtexp++) {
							mtex = *mtexp;
							if(mtex && mtex->tex == (Tex*)id) {
								obt->recalc |= OB_RECALC_DATA;
								
								if(mtex->mapto & PAMAP_INIT)
									psys->recalc |= PSYS_RECALC_RESET;
								if(mtex->mapto & PAMAP_CHILD)
									psys->recalc |= PSYS_RECALC_CHILD;

								BKE_ptcache_object_reset(sce, obt, PTCACHE_RESET_DEPSGRAPH);
							}
						}
					}
				}
			}
		}
		
		/* set flags based on ShapeKey */
		if(idtype == ID_KE) {
			for(obt=bmain->object.first; obt; obt= obt->id.next) {
				Key *key= ob_get_key(obt);
				if(!(ob && obt == ob) && ((ID *)key == id)) {
					obt->flag |= (OB_RECALC_OB|OB_RECALC_DATA);
					BKE_ptcache_object_reset(sce, obt, PTCACHE_RESET_DEPSGRAPH);
				}
			}
		}
		
		/* set flags based on particle settings */
		if(idtype == ID_PA) {
			ParticleSystem *psys;
			for(obt=bmain->object.first; obt; obt= obt->id.next)
				for(psys=obt->particlesystem.first; psys; psys=psys->next)
					if(&psys->part->id == id)
						BKE_ptcache_object_reset(sce, obt, PTCACHE_RESET_DEPSGRAPH);
		}

		/* update editors */
		dag_editors_update(bmain, id);
	}
}

void DAG_ids_flush_tagged(Main *bmain)
{
	ListBase *lbarray[MAX_LIBARRAY];
	Scene *sce;
	unsigned int lay;
	int a, have_tag = 0;

	dag_current_scene_layers(bmain, &sce, &lay);

	if(!sce || !sce->theDag)
		return;

	/* loop over all ID types */
	a  = set_listbasepointers(bmain, lbarray);

	while(a--) {
		ListBase *lb = lbarray[a];
		ID *id = lb->first;

		/* we tag based on first ID type character to avoid 
		   looping over all ID's in case there are no tags */
		if(id && bmain->id_tag_update[id->name[0]]) {
			for(; id; id=id->next) {
				if(id->flag & LIB_ID_RECALC) {
					dag_id_flush_update(sce, id);
					id->flag &= ~LIB_ID_RECALC;
				}
			}

			have_tag = 1;
		}
	}

	if(have_tag) {
		/* clear tags */
		memset(bmain->id_tag_update, 0, sizeof(bmain->id_tag_update));

		/* flush changes to other objects */
		DAG_scene_flush_update(bmain, sce, lay, 0);
	}
}

void DAG_id_tag_update(ID *id, short flag)
{
	Main *bmain= G.main;

	if(id==NULL) return;
	
	/* tag ID for update */
	id->flag |= LIB_ID_RECALC;
	bmain->id_tag_update[id->name[0]] = 1;

	/* flag is for objects and particle systems */
	if(flag) {
		Object *ob;
		ParticleSystem *psys;
		short idtype = GS(id->name);

		if(idtype == ID_OB) {
			/* only quick tag */
			ob = (Object*)id;
			ob->recalc |= (flag & OB_RECALC_ALL);
		}
		else if(idtype == ID_PA) {
			/* this is weak still, should be done delayed as well */
			for(ob=bmain->object.first; ob; ob=ob->id.next) {
				for(psys=ob->particlesystem.first; psys; psys=psys->next) {
					if(&psys->part->id == id) {
						ob->recalc |= (flag & OB_RECALC_ALL);
						psys->recalc |= (flag & PSYS_RECALC);
					}
				}
			}
		}
		else {
			/* disable because this is called on various ID types automatically.
			 * where printing warning is not useful. for now just ignore */
			/* BLI_assert(!"invalid flag for this 'idtype'"); */
		}
	}
}

#if 0 // UNUSED
/* recursively descends tree, each node only checked once */
/* node is checked to be of type object */
static int parent_check_node(DagNode *node, int curtime)
{
	DagAdjList *itA;
	
	node->lasttime= curtime;
	
	if(node->color==DAG_GRAY)
		return DAG_GRAY;
	
	for(itA = node->child; itA; itA= itA->next) {
		if(itA->node->type==ID_OB) {
			
			if(itA->node->color==DAG_GRAY)
				return DAG_GRAY;

			/* descend if not done */
			if(itA->node->lasttime!=curtime) {
				itA->node->color= parent_check_node(itA->node, curtime);
			
				if(itA->node->color==DAG_GRAY)
					return DAG_GRAY;
			}
		}
	}
	
	return DAG_WHITE;
}
#endif

/* ******************* DAG FOR ARMATURE POSE ***************** */

/* we assume its an armature with pose */
void DAG_pose_sort(Object *ob)
{
	bPose *pose= ob->pose;
	bPoseChannel *pchan;
	bConstraint *con;
	DagNode *node;
	DagNode *node2, *node3;
	DagNode *rootnode;
	DagForest *dag;
	DagNodeQueue *nqueue;
	DagAdjList *itA;
	ListBase tempbase;
	int skip = 0;
	
	dag = dag_init();
	ugly_hack_sorry= 0;	// no ID structs

	rootnode = dag_add_node(dag, NULL);	// node->ob becomes NULL
	
	/* we add the hierarchy and the constraints */
	for(pchan = pose->chanbase.first; pchan; pchan= pchan->next) {
		int addtoroot = 1;
		
		node = dag_get_node(dag, pchan);
		
		if(pchan->parent) {
			node2 = dag_get_node(dag, pchan->parent);
			dag_add_relation(dag, node2, node, 0, "Parent Relation");
			addtoroot = 0;
		}
		for (con = pchan->constraints.first; con; con=con->next) {
			bConstraintTypeInfo *cti= constraint_get_typeinfo(con);
			ListBase targets = {NULL, NULL};
			bConstraintTarget *ct;
			
			if (cti && cti->get_constraint_targets) {
				cti->get_constraint_targets(con, &targets);
				
				for (ct= targets.first; ct; ct= ct->next) {
					if (ct->tar==ob && ct->subtarget[0]) {
						bPoseChannel *target= get_pose_channel(ob->pose, ct->subtarget);
						if (target) {
							node2= dag_get_node(dag, target);
							dag_add_relation(dag, node2, node, 0, "Pose Constraint");
							
							if (con->type==CONSTRAINT_TYPE_KINEMATIC) {
								bKinematicConstraint *data = (bKinematicConstraint *)con->data;
								bPoseChannel *parchan;
								int segcount= 0;
								
								/* exclude tip from chain? */
								if(!(data->flag & CONSTRAINT_IK_TIP))
									parchan= pchan->parent;
								else
									parchan= pchan;
								
								/* Walk to the chain's root */
								while (parchan) {
									node3= dag_get_node(dag, parchan);
									dag_add_relation(dag, node2, node3, 0, "IK Constraint");
									
									segcount++;
									if (segcount==data->rootbone || segcount>255) break; // 255 is weak
									parchan= parchan->parent;
								}
							}
						}
					}
				}
				
				if (cti->flush_constraint_targets)
					cti->flush_constraint_targets(con, &targets, 1);
			}
		}
		if (addtoroot == 1 ) {
			dag_add_relation(dag, rootnode, node, 0, "Root Bone Relation");
		}
	}

	dag_check_cycle(dag);
	
	/* now we try to sort... */
	tempbase.first= tempbase.last= NULL;

	nqueue = queue_create(DAGQUEUEALLOC);
	
	/* tag nodes unchecked */
	for(node = dag->DagNode.first; node; node= node->next) 
		node->color = DAG_WHITE;
	
	node = dag->DagNode.first;
	
	node->color = DAG_GRAY;
	push_stack(nqueue, node);  
	
	while(nqueue->count) {
		
		skip = 0;
		node = get_top_node_queue(nqueue);
		
		itA = node->child;
		while(itA != NULL) {
			if(itA->node->color == DAG_WHITE) {
				itA->node->color = DAG_GRAY;
				push_stack(nqueue,itA->node);
				skip = 1;
				break;
			} 
			itA = itA->next;
		}			
		
		if (!skip) {
			if (node) {
				node = pop_queue(nqueue);
				if (node->ob == NULL)	// we are done
					break ;
				node->color = DAG_BLACK;
				
				/* put node in new list */
				BLI_remlink(&pose->chanbase, node->ob);
				BLI_addhead(&tempbase, node->ob);
			}	
		}
	}
	
	// temporal correction for circular dependancies
	while(pose->chanbase.first) {
		pchan= pose->chanbase.first;
		BLI_remlink(&pose->chanbase, pchan);
		BLI_addhead(&tempbase, pchan);

		printf("cyclic %s\n", pchan->name);
	}
	
	pose->chanbase = tempbase;
	queue_delete(nqueue);
	
//	printf("\nordered\n");
//	for(pchan = pose->chanbase.first; pchan; pchan= pchan->next) {
//		printf(" %s\n", pchan->name);
//	}
	
	free_forest( dag );
	MEM_freeN( dag );
	
	ugly_hack_sorry= 1;
}