/* id_lookup.cc */

#include "id_lookup.h"
#include "root.h"
#include "element.h"

/* search_eligible iff non-dormant && visible */
bool search_eligible( const dc_label *l ) {
  if( !l->is_visible() ) return false;
  switch( l->type() ) {
  case Component_t : case Modification_t : case GA_t :
    return !( ( ( dc_component * )l )->is_dormant() );
  case Element_t :
    return !( ( ( dc_element * )l )->is_dormant() );
  default : return true;
  }
}

enum search_direction { SEARCH_UP_PATH, SEARCH_DOWN_PATH };
struct search_node {
  dc_label *id;
  const search_direction dir;
  
  /* only used when going down so up-path not re-searched */
  const dc_label *from;

  search_node( dc_label *Id, const search_direction Dir, 
	       const dc_label *From = nil ) : id(Id), dir(Dir), from(From) {}
};

void search_expand( const dc_label *id, queue<search_node *> &search_queue ) {
  switch( id->type() ) {
  case Node_t :
    dic_item it;
    /* add children to queue */
    forall_items( it, ( ( dc_node * )id )->child_list ) {
      dc_label *l = ( ( dc_node * )id )->child_list.inf( it );
      search_queue.append( new search_node( l, SEARCH_UP_PATH ) );
    }
    break;
/*case Element_t :
    if( ( ( dc_element * )id )->get_rtype() == Pointer_t ) {
    cerr << "EXPANDING POINTER ELEMENT " << id->full_type() << "\n";
    dc_pointer *p = ( dc_pointer * )( ( dc_element * )id )->get();
    if( p && p->get() ) {
    search_queue.append( new search_node( p->get(), SEARCH_UP_PATH ) );
    cerr << "ADDED " << p->get()->label() << "\n";
    }
    }
    break;
    case Pointer_t :
    if( ( ( dc_pointer * )id )->get() ) {
    search_queue.append( new search_node( ( ( dc_pointer * )id )->get(), 
    SEARCH_UP_PATH ) );
    }
    break;*/
  default :;
  }
}

dc_label *search( cstring lbl, dc_label *start = nil, 
		  const bool search_all = false ) {
  /* force search from root */
  if( lbl[0] == ID_SEPARATOR /*|| start == nil*/ ) return lookup( lbl, search_all );

  queue <search_node *> search_queue;
  int delim_n = lbl.pos( ID_SEP_STRING, 0 );

  if( delim_n < 0 ) delim_n = lbl.length();

  /* get first label to search for */
  string first_label = lbl( 0, delim_n - 1 );
  
  search_queue.append( new search_node( start, SEARCH_DOWN_PATH ) );
  while( !search_queue.empty() ) {
    search_node *S = search_queue.pop();
    if( S->id == nil ) { /* search upwards from root */
      dic_item it;
      forall_items( it, root.label_list ) {
	dc_label *id = root.label_list.inf( it );
	search_queue.append( new search_node( id, SEARCH_UP_PATH ) );
      }
    } else { 
      if( S->id->local_label() == first_label ) { // MATCHLABEL
	dc_label *check_match = lookup_relative( lbl( delim_n + 1, 
						      lbl.length() ), S->id );
	if( check_match != nil && 
	    ( search_all || search_eligible( check_match ) ) ) {
	  /* delete remaining nodes */
	  delete( S );
	  while( !search_queue.empty() ) {
	    delete( search_queue.pop() );
	  }
	  return check_match;
	}
      }
      if( S->dir == SEARCH_DOWN_PATH ) {
	/* add parent to queue */
	search_queue.append( new search_node( S->id->get_parent(),
					      SEARCH_DOWN_PATH, S->id ) );
      }
      search_expand( S->id, search_queue );
    }
    delete( S );
  }
  return nil;
}

dc_label *nt_search( cstring lbl, const dc_type T, dc_label *start =
		     nil, const bool search_all = false ) {
  int label_pos;

  /* check search from root */
  if( lbl[0] == ID_SEPARATOR ) { start = nil; label_pos = 1; }
  else label_pos = 0; 

  queue <search_node *> search_queue;
  int delim_n = lbl.pos( ID_SEP_STRING, label_pos );

  if( delim_n < 0 ) delim_n = lbl.length();

  /* get first label to search for */
  string first_label = lbl( label_pos, delim_n - 1 );
  
  search_queue.append( new search_node( start, SEARCH_DOWN_PATH ) );
  while( !search_queue.empty() ) {
    search_node *S = search_queue.pop();
    if( S->id == nil ) { /* search upwards from root */
      dic_item it;
      forall_items( it, root.label_list ) {
	dc_label *id = root.label_list.inf( it );
	search_queue.append( new search_node( id, SEARCH_UP_PATH ) );
      }
    } else { 
      if( S->id->match_label( first_label ) ) {
	dc_label *check_match = lookup_relative( lbl( delim_n + 1,
						      lbl.length() ), S->id );
	if( check_match != nil && check_match->sub_type() != T && 
	    ( search_all || search_eligible( check_match ) ) ) {
	  /* delete remaining nodes */
	  delete( S );
	  while( !search_queue.empty() ) {
	    delete( search_queue.pop() );
	  }
	  return check_match;
	}
      }
      if( S->dir == SEARCH_DOWN_PATH ) {
	/* add parent to queue */
	search_queue.append( new search_node( S->id->get_parent(),
					      SEARCH_DOWN_PATH, S->id ) );
      }
      search_expand( S->id, search_queue );
    }
    delete( S );
  }
  return nil;
}

dc_label *t_search( cstring lbl, const dc_type T, dc_label *start = 
		    nil, const bool search_all = false ) {
  int label_pos;

  /* check search from root */
  if( lbl[0] == ID_SEPARATOR ) { start = nil; label_pos = 1; }
  else label_pos = 0;

  queue <search_node *> search_queue;
  int delim_n = lbl.pos( ID_SEP_STRING, label_pos );

  if( delim_n < 0 ) delim_n = lbl.length();

  /* get first label to search for */
  string first_label = lbl( label_pos, delim_n - 1 );
  
  search_queue.append( new search_node( start, SEARCH_DOWN_PATH ) );
  while( !search_queue.empty() ) {
    search_node *S = search_queue.pop();
    if( S->id == nil ) { /* search upwards from root */
      dic_item it;
      forall_items( it, root.label_list ) {
	dc_label *id = root.label_list.inf( it );
	search_queue.append( new search_node( id, SEARCH_UP_PATH ) );
      }
    } else { 
      if( S->id->match_label( first_label ) ) {
	dc_label *check_match = lookup_relative( lbl( delim_n + 1,
						      lbl.length() ), S->id );
	if( check_match != nil && check_match->sub_type() == T && 
	    ( search_all || search_eligible( check_match ) ) ) {
	  /* delete remaining nodes */
	  delete( S );
	  while( !search_queue.empty() ) {
	    delete( search_queue.pop() );
	  }
	  return check_match;
	}
      }
      if( S->dir == SEARCH_DOWN_PATH ) {
	/* add parent to queue */
	search_queue.append( new search_node( S->id->get_parent(),
					      SEARCH_DOWN_PATH, S->id ) );
      }
      search_expand( S->id, search_queue );
    }
    delete( S );
  }
  return nil;
}

dc_label *fit_search( cstring lbl, bool crit( const dc_label * ),
		      dc_label *start = nil,
		      const bool search_all = false ) {
  int label_pos;

  /* check search from root */
  if( lbl[0] == ID_SEPARATOR ) { start = nil; label_pos = 1; }
  else label_pos = 0; 

  queue <search_node *> search_queue;

  int delim_n = lbl.pos( ID_SEP_STRING, label_pos );

  if( delim_n < 0 ) delim_n = lbl.length();

  /* get first label to search for */
  string first_label = lbl( label_pos, delim_n - 1 );
  
  search_queue.append( new search_node( start, SEARCH_DOWN_PATH ) );
  while( !search_queue.empty() ) {
    search_node *S = search_queue.pop();
    if( S->id == nil ) { /* search upwards from root */
      dic_item it;
      forall_items( it, root.label_list ) {
	dc_label *id = root.label_list.inf( it );
	search_queue.append( new search_node( id, SEARCH_UP_PATH ) );
      }
    } else { 
      if( S->id->match_label( first_label ) ) {
	dc_label *check_match = lookup_relative( lbl( delim_n + 1,
						      lbl.length() ), S->id );
	if( check_match && ( search_all || search_eligible( check_match ) ) && 
	    crit( check_match ) ) {
	  /* delete remaining nodes */
	  delete( S );
	  while( !search_queue.empty() ) {
	    delete( search_queue.pop() );
	  }
	  return check_match;
	}
      }
      if( S->dir == SEARCH_DOWN_PATH ) {
	/* add parent to queue */
	search_queue.append( new search_node( S->id->get_parent(),
					      SEARCH_DOWN_PATH, S->id ) );
      }
      search_expand( S->id, search_queue );
    }
    delete( S );
  }
  return nil;
}

dc_label *lookup_relative( cstring lbl, dc_label *start = nil,
			   const bool search_all = false ) {
  //  cerr << "LOOKUP_REL OF " << lbl << " FROM " 
  //       << ( start ? start->full_type() : string( "<nil>" ) ) << "\n";
  if( lbl.length() == 0 ) return start;

  if( start ) {
    if( start->type() == Element_t &&
	( ( dc_element * )start )->get_rtype() == Pointer_t ) {
      //cerr << "MATCHED START POINTER " << start->full_type();
      dc_pointer *p = ( dc_pointer * )( ( dc_element * )start )->get();
      dc_label *l;
      if( p && ( l = p->get() ) != nil ) {
	start = l;
	//cerr << " TO " << start->full_type() << "\n";
      }
    } else if( start->type() == Pointer_t ) {
      if( ( ( dc_pointer * )start )->get() )
	start = ( ( dc_pointer * )start )->get();
    }
  }

  int start_n = ( lbl[0] == ID_SEPARATOR );
  int delim_n = lbl.pos( ID_SEP_STRING, start_n );

  if( delim_n >= 0 ) {
    /* get root */
    string first_label = lbl( 0, delim_n - 1 );

    dc_label *id;
    if( start == nil ) {
      dic_item child_it = root.label_list.lookup( first_label );
      if( child_it == nil ) return nil;
      id = root.label_list.inf( child_it );
    } else if( start->type() == Node_t ) {
      dic_item child_it = ( ( dc_node * ) start )->
	child_list.lookup( first_label );
      if( child_it == nil ) return nil;
      id = ( ( dc_node * )start )->child_list.inf( child_it );
    } else return nil;
    
    while( 1 ) { /* run through path until no delimiter found */
      if( id->type() == Element_t &&
	  ( ( dc_element * ) id )->get_rtype() == Pointer_t ) {
	//	cerr << "MATCHED POINTER " << id->full_type();
	dc_pointer *p = ( dc_pointer * )( ( dc_element * ) id )->get();
	dc_label *l;
	if( p && ( l = p->get() ) != nil ) {
	  id = l;
	  //cerr << " TO " << id->full_type() << "\n";
	}
      } else if( id->type() == Pointer_t ) {
	if( ( ( dc_pointer * )id )->get() )
	  id = ( ( dc_pointer * )id )->get();
      }
      start_n = delim_n + 1;
      delim_n = lbl.pos( ID_SEP_STRING, start_n );
      if( delim_n < 0 ) break;
      if( id->type() == Node_t ) {
	id = ( ( dc_node * )id )->lookup_child( lbl( start_n, delim_n - 1 ), 
						search_all );
	if( id == nil ) return nil;
      } else return nil;
    }
    /* lookup last section and return */
    if( id->type() == Node_t ) {
      return ( ( dc_node * )id )->lookup_child( lbl( start_n, lbl.length() - 1 )
					      , search_all );
    } else return nil;
  } else { 
    if( start == nil ) {
      dic_item child_it = root.label_list.lookup( lbl );
      if( child_it == nil ) return nil;
      return root.label_list.inf( child_it );
    } else if( start->type() == Node_t ) {
      dic_item child_it = ( ( dc_node * )start )->child_list.lookup( lbl );
      if( child_it == nil ) return nil;
      return ( ( dc_node * )start )->child_list.inf( child_it );
    } else return nil;
  }
}

dc_label *lookup( cstring lbl, const bool search_all = false ) {
  dic_item child_it;
  int start_n = ( lbl[0] == ID_SEPARATOR );
  int delim_n = lbl.pos( ID_SEP_STRING, start_n );
  if( delim_n >= 0 ) {
    /* get root */
    string root_label = lbl( start_n, delim_n - 1 );
    child_it = root.label_list.lookup( root_label );
    if( child_it == nil ) return nil;
    dc_label *id = root.label_list.inf( child_it );
    
    while( 1 ) { /* run through path until no delimiter found */
      if( id->type() == Element_t &&
	  ( ( dc_element * ) id )->get_rtype() == Pointer_t ) {
	dc_pointer *p = ( dc_pointer * )( ( dc_element * ) id )->get();
	if( p && p->get() ) id = p->get();
      } else if( id->type() == Pointer_t ) {
	if( ( ( dc_pointer * )id )->get() ) id = ( ( dc_pointer * )id )->get();
      }
      start_n = delim_n + 1;
      delim_n = lbl.pos( ID_SEP_STRING, start_n );
      if( delim_n < 0 ) break;
      if( id->type() == Node_t ) {
	id = ( ( dc_node * )id )->lookup_child( lbl( start_n, delim_n - 1 ),
						search_all );
	if( id == nil ) return nil;
      } else return nil;
    }
    /* lookup last section and return */
    if( id->type() == Node_t ) {
      return ( ( dc_node * )id )->lookup_child( lbl( start_n, lbl.length() - 1 )
					      , search_all );
    } else return nil;
  } else {
    /* at root since no delim found */
    child_it = root.label_list.lookup( lbl( start_n, lbl.length() ) );
    if( child_it == nil )
      return nil;
    return root.label_list.inf( child_it );
  }
}

dc_label *lookup( const tag global_tag ) {
  dic_item tagL = root.tag_list.lookup( global_tag );
  if( tagL == nil ) return nil;
  return root.tag_list.inf( tagL );
}

tag lookup_tag( cstring global_label, const bool search_all = false ) {
  dc_label *id = lookup( global_label, search_all );
  return id ? ( id->get_tag() ) : tag_error;
}

bool label_exists( cstring label, const dc_node *parent = nil ) {
  if( parent == nil ) { /* look in label_list */
    return ( root.label_list.lookup( label ) != nil );
  } else { /* look in parent list */
    return ( parent->child_exists( label ) );
  }
}
