// Filename: graphReducer.cxx
// Created by:  drose (26Apr00)
//
////////////////////////////////////////////////////////////////////
//
// PANDA 3D SOFTWARE
// Copyright (c) 2001, Disney Enterprises, Inc.  All rights reserved
//
// All use of this software is subject to the terms of the Panda 3d
// Software license.  You should have received a copy of this license
// along with this source code; you will also find a current copy of
// the license at http://www.panda3d.org/license.txt .
//
// To contact the maintainers of this program write to
// panda3d@yahoogroups.com .
//
////////////////////////////////////////////////////////////////////

#include "graphReducer.h"
#include "config_graph.h"
#include "namedNode.h"
#include "pt_Node.h"

#include "pmap.h"
#include "plist.h"

////////////////////////////////////////////////////////////////////
//     Function: GraphReducer::Constructor
//       Access: Public
//  Description:
////////////////////////////////////////////////////////////////////
GraphReducer::
GraphReducer(TypeHandle graph_type) :
  _graph_type(graph_type)
{
  _max_children = 1;
}

////////////////////////////////////////////////////////////////////
//     Function: GraphReducer::Destructor
//       Access: Public
//  Description:
////////////////////////////////////////////////////////////////////
GraphReducer::
~GraphReducer() {
}

////////////////////////////////////////////////////////////////////
//     Function: GraphReducer::set_max_children
//       Access: Public
//  Description: Sets the maximum number of children a node is allowed
//               to have and still be flattened.  Normally, this is 1;
//               we don't typically want to flatten a node that has
//               multiple children.  However, sometimes this may be
//               desirable; set this parameter to control the limit.
//               If this is set to -1, there is no limit.
//
//               If any of a node's arcs cannot be flattened,
//               generally none of them will be, although this depends
//               on how late the inability to flatten a particular arc
//               is discovered.
////////////////////////////////////////////////////////////////////
void GraphReducer::
set_max_children(int count) {
  _max_children = count;
}

////////////////////////////////////////////////////////////////////
//     Function: GraphReducer::flatten
//       Access: Public
//  Description: Simplifies the graph by removing unnecessary nodes
//               and arcs.
//
//               In general, a node (and its parent arc) is a
//               candidate for removal if the node has no siblings and
//               the node and arc have no special properties.  The
//               definition of what, precisely, is a 'special
//               property' may be extended by subclassing from this
//               type and redefining consider_arc() appropriately.
//
//               If combine_siblings is true, sibling nodes may also
//               be collapsed into a single node.  This will further
//               reduce scene graph complexity, sometimes
//               substantially, at the cost of reduced spatial
//               separation.
//
//               Returns the number of arcs removed from the graph.
////////////////////////////////////////////////////////////////////
int GraphReducer::
flatten(Node *root, bool combine_siblings) {
  int num_total_nodes = 0;
  int num_pass_nodes;

  do {
    num_pass_nodes = 0;

    const DownRelationPointers &drp =
      root->find_connection(_graph_type).get_down();

    // Get a copy of the children list, so we don't have to worry
    // about self-modifications.
    DownRelationPointers drp_copy = drp;

    // Now visit each of the children in turn.
    DownRelationPointers::const_iterator drpi;
    for (drpi = drp_copy.begin(); drpi != drp_copy.end(); ++drpi) {
      NodeRelation *arc = (*drpi);
      num_pass_nodes += r_flatten(arc->get_child(), combine_siblings);
    }

    num_total_nodes += num_pass_nodes;

    // If combine_siblings is true, we should repeat the above until
    // we don't get any more benefit from flattening, because each
    // pass could convert cousins into siblings, which may get
    // flattened next pass.  If combine_siblings is not true, the
    // first pass will be fully effective, and there's no point in
    // trying again.
  } while (combine_siblings && num_pass_nodes != 0);

  return num_total_nodes;
}

////////////////////////////////////////////////////////////////////
//     Function: GraphReducer::r_flatten
//       Access: Protected
//  Description: The recursive implementation of flatten().
////////////////////////////////////////////////////////////////////
int GraphReducer::
r_flatten(Node *root, bool combine_siblings) {
  int num_nodes = 0;

  const DownRelationPointers &drp =
    root->find_connection(_graph_type).get_down();

  // Get a copy of the children list, so we don't have to worry
  // about self-modifications.
  DownRelationPointers drp_copy = drp;

  // Now visit each of the children in turn.
  DownRelationPointers::const_iterator drpi;
  for (drpi = drp_copy.begin(); drpi != drp_copy.end(); ++drpi) {
    NodeRelation *arc = (*drpi);
    num_nodes += r_flatten(arc->get_child(), combine_siblings);
  }

  if (combine_siblings && drp.size() >= 2) {
    num_nodes += flatten_siblings(root);
  }

  if (!drp.empty() && (_max_children < 0 || (int)drp.size() <= _max_children)) {
    // If we don't have too many children, consider flattening each of
    // our child arcs.
    bool all_ok = true;
    for (drpi = drp_copy.begin(); drpi != drp_copy.end() && all_ok; ++drpi) {
      NodeRelation *arc = (*drpi);
      all_ok = consider_arc(arc);
    }

    if (all_ok) {
      // All our arcs can (potentially) be flattened; do it.

      // Get a new copy of the children list.
      drp_copy = drp;
      
      for (drpi = drp_copy.begin(); drpi != drp_copy.end(); ++drpi) {
        NodeRelation *arc = (*drpi);
        if (flatten_arc(arc)) {
          num_nodes++;
        }
      }
    }
  }

  return num_nodes;
}

class SortByTransitions {
public:
  INLINE bool
  operator () (const NodeRelation *arc1, const NodeRelation *arc2) const;
};

INLINE bool SortByTransitions::
operator () (const NodeRelation *arc1, const NodeRelation *arc2) const {
  return (arc1->compare_transitions_to(arc2) < 0);
}


////////////////////////////////////////////////////////////////////
//     Function: GraphReducer::flatten_siblings
//       Access: Protected
//  Description: Attempts to collapse together any pairs of siblings
//               of the indicated node that share the same properties.
////////////////////////////////////////////////////////////////////
int GraphReducer::
flatten_siblings(Node *root) {
  int num_nodes = 0;

  // First, collect the children into groups of arcs with common
  // properties.
  typedef pmap<NodeRelation *, plist<NodeRelation *>, SortByTransitions> Children;
  Children children;

  const DownRelationPointers &drp =
    root->find_connection(_graph_type).get_down();
  DownRelationPointers::const_iterator drpi;
  for (drpi = drp.begin(); drpi != drp.end(); ++drpi) {
    NodeRelation *arc = (*drpi);
    children[arc].push_back(arc);
  }

  // Now visit each of those groups and try to collapse them together.
  Children::iterator ci;
  for (ci = children.begin(); ci != children.end(); ++ci) {
    plist<NodeRelation *> &arcs = (*ci).second;

    plist<NodeRelation *>::iterator ai1;
    ai1 = arcs.begin();
    while (ai1 != arcs.end()) {
      plist<NodeRelation *>::iterator ai1_hold = ai1;
      NodeRelation *arc1 = (*ai1);
      ++ai1;
      plist<NodeRelation *>::iterator ai2 = ai1;
      while (ai2 != arcs.end()) {
        plist<NodeRelation *>::iterator ai2_hold = ai2;
        NodeRelation *arc2 = (*ai2);
        ++ai2;

        if (consider_siblings(root, arc1, arc2)) {
          NodeRelation *new_arc = collapse_siblings(root, arc1, arc2);
          if (new_arc != (NodeRelation *)NULL) {
            // We successfully collapsed an arc.
            arcs.erase(ai2_hold);
            arcs.erase(ai1_hold);
            arcs.push_back(new_arc);
            ai1 = arcs.begin();
            ai2 = arcs.end();
            num_nodes++;
          }
        }
      }
    }
  }

  return num_nodes;
}

////////////////////////////////////////////////////////////////////
//     Function: GraphReducer::consider_arc
//       Access: Protected, Virtual
//  Description: Decides whether or not the indicated arc is a
//               suitable candidate for removal.  Returns true if the
//               arc may be removed, false if it should be kept.  This
//               function may be extended in a user class to protect
//               special kinds of arcs from deletion.
////////////////////////////////////////////////////////////////////
bool GraphReducer::
consider_arc(NodeRelation *arc) {
  // On reflection, there's no reason to forbid the removal of arcs
  // with sub_render transitions.  It should all work out properly.
  /*
  if (arc->has_sub_render_trans()) {
    if (graph_cat.is_debug()) {
      graph_cat.debug()
        << "Not removing " << *arc
        << " because it contains a sub_render transition.\n";
    }
    return false;
  }
  */
  return true;
}

////////////////////////////////////////////////////////////////////
//     Function: GraphReducer::consider_siblings
//       Access: Protected, Virtual
//  Description: Decides whether or not the indicated sibling nodes
//               (and their associated arcs) should be collapsed into
//               a single node or not.  Returns true if the arcs may
//               be collapsed, false if they should be kept distinct.
////////////////////////////////////////////////////////////////////
bool GraphReducer::
consider_siblings(Node *, NodeRelation *arc1, NodeRelation *arc2) {
  // Don't attempt to combine any sibling arcs with different
  // transitions.
  if (arc1->compare_transitions_to(arc2) != 0) {
    return false;
  }

  // We can't collapse siblings with arcs that contain sub_render
  // transitions.  That could be bad.

  // On the other hand, maybe we can; why not?  The only one that
  // could cause grief is the DecalTransition, which we'll
  // special-case in SceneGraphReducer.
  /*
  if (arc1->has_sub_render_trans()) {
    if (graph_cat.is_debug()) {
      graph_cat.debug()
        << "Not combining " << *arc1 << " and " << *arc2
        << " because they contain a sub_render transition.\n";
    }
    return false;
  }
  */

  return true;
}

////////////////////////////////////////////////////////////////////
//     Function: GraphReducer::flatten_arc
//       Access: Protected, Virtual
//  Description: Removes the indicated arc, collapsing together the
//               two nodes and leaving them parented in the same
//               place.  The return value is true if the arc is
//               successfully collapsed, false if we chickened out.
//
//               This function may be extended in a user class to
//               handle special kinds of nodes.
////////////////////////////////////////////////////////////////////
bool GraphReducer::
flatten_arc(NodeRelation *arc) {
  PT_Node parent = arc->get_parent();
  PT_Node child = arc->get_child();

  if (graph_cat.is_debug()) {
    graph_cat.debug()
      << "Removing " << *arc << "\n";
  }

  PT_Node new_parent = collapse_nodes(parent, child, false);
  if (new_parent == (Node *)NULL) {
    if (graph_cat.is_debug()) {
      graph_cat.debug()
        << "Decided not to remove " << *arc << "\n";
    }
    return false;
  }

  choose_name(new_parent, parent, child);

  move_children(new_parent, parent);
  move_children(new_parent, child);

  // Move all of the transitions from the arc to the parent's arcs.
  int num_grandparents = parent->get_num_parents(_graph_type);
  for (int i = 0; i < num_grandparents; i++) {
    NodeRelation *grandparent_arc = parent->get_parent(_graph_type, i);

    grandparent_arc->compose_transitions_from(arc);
    if (new_parent != parent) {
      // Also switch out the parent node.
      grandparent_arc->change_child(new_parent);
    }
  }

  remove_arc(arc);
  return true;
}

////////////////////////////////////////////////////////////////////
//     Function: GraphReducer::collapse_siblings
//       Access: Protected, Virtual
//  Description: Performs the work of collapsing two sibling arcs
//               together into a single arc (and their associated
//               nodes into a single node).
//
//               Returns a pointer to a NodeRelation the reflects the
//               combined arc (which may be either of the source arcs,
//               or a new arc altogether) if the siblings are
//               successfully collapsed, or NULL if we chickened out.
////////////////////////////////////////////////////////////////////
NodeRelation *GraphReducer::
collapse_siblings(Node *parent, NodeRelation *arc1, NodeRelation *arc2) {
  PT_Node node1 = arc1->get_child();
  PT_Node node2 = arc2->get_child();

  if (graph_cat.is_debug()) {
    graph_cat.debug()
      << "Collapsing " << *node1 << " and " << *node2 << "\n";
  }

  PT_Node new_node = collapse_nodes(node1, node2, true);
  if (new_node == (Node *)NULL) {
    if (graph_cat.is_debug()) {
      graph_cat.debug()
        << "Decided not to collapse " << *node1 << " and " << *node2 << "\n";
    }
    return NULL;
  }

  choose_name(new_node, node1, node2);

  move_children(new_node, node1);
  move_children(new_node, node2);

  arc1->change_child(new_node);
  remove_arc(arc2);

  return arc1;
}

////////////////////////////////////////////////////////////////////
//     Function: GraphReducer::collapse_nodes
//       Access: Protected, Virtual
//  Description: Collapses the two nodes into a single node, if
//               possible.  The 'siblings' flag is true if the two
//               nodes are siblings nodes; otherwise, node1 is a
//               parent of node2.  The return value is the resulting
//               node, which may be either one of the source nodes, or
//               a new node altogether, or it may be NULL to indicate
//               that the collapse operation could not take place.
//
//               This function may be extended in a user class to
//               handle combining special kinds of nodes.
////////////////////////////////////////////////////////////////////
Node *GraphReducer::
collapse_nodes(Node *node1, Node *node2, bool) {
  if (!node1->safe_to_combine() || !node2->safe_to_combine()) {
    // One or both nodes cannot be safely combined with another node;
    // do nothing.
    return NULL;
  }

  return node2->combine_with(node1);
}

////////////////////////////////////////////////////////////////////
//     Function: GraphReducer::choose_name
//       Access: Protected, Virtual
//  Description: Chooses a suitable name for the collapsed node, based
//               on the names of the two sources nodes.
////////////////////////////////////////////////////////////////////
void GraphReducer::
choose_name(Node *preserve, Node *source1, Node *source2) {
  if (!preserve->is_of_type(NamedNode::get_class_type())) {
    // It's not even a namable class, so we can't name it anyway.
    // Never mind.
    return;
  }

  NamedNode *named_preserve;
  DCAST_INTO_V(named_preserve, preserve);

  string name;
  bool got_name = false;

  if (source1->is_of_type(NamedNode::get_class_type())) {
    NamedNode *named_source1;
    DCAST_INTO_V(named_source1, source1);
    name = named_source1->get_name();
    got_name = !name.empty() || named_source1->preserve_name();
  }

  if (source2->is_of_type(NamedNode::get_class_type())) {
    NamedNode *named_source2;
    DCAST_INTO_V(named_source2, source2);
    if (named_source2->preserve_name() || !got_name) {
      name = named_source2->get_name();
      got_name = !name.empty() || named_source2->preserve_name();
    }
  }

  if (got_name) {
    named_preserve->set_name(name);
  }
}

////////////////////////////////////////////////////////////////////
//     Function: GraphReducer::move_children
//       Access: Protected
//  Description: Moves all of the children arcs of the 'from' node to
//               the 'to' node.
////////////////////////////////////////////////////////////////////
void GraphReducer::
move_children(Node *to, Node *from) {
  if (to != from) {
    /*
    if (graph_cat.is_debug()) {
      graph_cat.debug()
        << "Moving children to " << *to << " from " << *from << "\n";
    }
    */

    int num_children = from->get_num_children(_graph_type);
    while (num_children > 0) {
      NodeRelation *arc = from->get_child(_graph_type, 0);
      arc->change_parent(to);
      num_children--;
      nassertv(num_children == from->get_num_children(_graph_type));
    }
  }
}

////////////////////////////////////////////////////////////////////
//     Function: GraphReducer::copy_children
//       Access: Protected
//  Description: Copies all of the children arcs of the 'from' node to
//               the 'to' node, without removing the from the 'from'
//               node.
////////////////////////////////////////////////////////////////////
void GraphReducer::
copy_children(Node *to, Node *from) {
  if (to != from) {
    int num_children = from->get_num_children(_graph_type);
    for (int i = 0; i < num_children; i++) {
      NodeRelation *arc = from->get_child(_graph_type, i);
      NodeRelation *new_arc = NodeRelation::create_typed_arc
        (_graph_type, to, arc->get_child());
      nassertv(new_arc != (NodeRelation *)NULL);
      nassertv(new_arc->is_exact_type(_graph_type));
      new_arc->copy_transitions_from(arc);
    }
  }
}
