#include "menu-tree.h"
#include "install-menu.h"
#include "hints.h"
#include <ctype.h>
#include <list>
#include <set>

bool operator< (const StrVec &left, const StrVec &right){
  cStrVec::iterator i,j;

  for(i=left.begin(), j=right.begin();
      (i!=left.end()) && (j!=right.end());
      i++, j++){
    if((*i)<(*j))
      return true;
    else if((*i)>(*j))
      return false;
  }
  if(j==right.end())
    return false;
  else
    return true;
}


void menuentry::add_entry(StrVec s,
			  map <String, String, less<String> > &v){
  submenu_container::iterator f,firstsec_i;
  StrVec subs;
  StrVec firstsec;
  cStrVec::iterator i;
  bool use_forced=false;
  
  //there are two ways to store the menuentries in the `tree'
  // - `flat', all menuentries in the toplevel submenus map.
  //   This is used when working with `hints'. In this case, we
  //   will later sort out the tree.
  // - as a true tree.
  //However, even in the `flat', hint-processing case, if there already
  //exists a submenu with exactly the right s[0], then we do desent,
  //if it has a v[FORCED_VAR] set.

  firstsec.push_back(s[0]);
  firstsec_i=submenus.find(firstsec);

  if(firstsec_i!=submenus.end())
    if((*firstsec_i).second->forced)
      use_forced=true;

  if(((!config->hint_optimize)||use_forced)&&
     (s.size()>1)){
    
    for(i=s.begin()+1;i!=s.end(); i++)
      if((*i).size())
	subs.push_back((*i));
    
    if(firstsec_i==submenus.end()){
      submenus[firstsec]=new menuentry;
      submenus[firstsec]->section=subs;
      (submenus[firstsec]->vars)[TITLE_VAR]=firstsec[0];
    }
    submenus[firstsec]->add_entry(subs,v);
  }else {
    f=submenus.find(s);
    if(f==submenus.end()){
      menuentry *m;
      m=new menuentry;
      submenus[s]=m;
      m->section=s;
      m->vars=v;
    }
  }
}

void menuentry::add_menuentry_ptr(StrVec s,
				  menuentry *m){
  submenu_container::iterator f;
  StrVec subs,firstsec;
  cStrVec::iterator i;

  if(s.size()>1){
    for(i=s.begin()+1;i!=s.end(); i++)
      if((*i).size())
	subs.push_back((*i));
    
    firstsec.push_back(s[0]);
    f=submenus.find(firstsec);
    if(f==submenus.end()){
      submenus[firstsec]=new menuentry;
      submenus[firstsec]->section=subs;
      submenus[firstsec]->forced=m->forced;
      (submenus[firstsec]->vars)[TITLE_VAR]=firstsec[0];
    }
    submenus[firstsec]->add_menuentry_ptr(subs,m);
  }else {
    f=submenus.find(s);
    if(f==submenus.end())
      submenus[s]=m;
  }
}

void menuentry::output(){
  String treew=config->treewalk();
  //  map <String, menuentry *, less<String> >::iterator i;
  submenu_container::iterator j;
  multimap <String, menuentry *, less<String> > sorted;
  multimap <String, menuentry *, less<String> >::iterator i;

  
  //sort the submenus in sorted:
  for(j=submenus.begin(); j!=submenus.end(); j++){
    String s;
    if(config->sort)
      s=config->sort->soutput((*j).second->vars);
    else
      s=(*j).second->vars[TITLE_VAR];
    sorted.insert(pair<String,menuentry *>(s,(*j).second));
  };

  for(string::size_type j=0;j<treew.length(); j++){
    bool children_too=false;
    switch(treew[j]){
    case 'c':
      for(i=sorted.begin(); i!=sorted.end(); i++)
	if((*i).second->submenus.size())
	  (*i).second->output();
      break;
    case '(':
      if(submenus.size())
	if(config->startmenu&& testuniqueness(vars))
	  config->startmenu->output(vars);
      break;
    case ')':
      if(submenus.size())
	if(config->endmenu && testuniqueness(vars))
	  config->endmenu->output(vars);
      break;
    case 'M':
      children_too=true;
    case 'm':;
      for(i=sorted.begin(); i!=sorted.end(); i++)
        if(((*i).second->vars[COMMAND_VAR].length())&&
	   testuniqueness((*i).second->vars))
          supported->subst((*i).second->vars);
        else{
	  if((config->submenutitle)&&
	     ((*i).second->submenus.size())&&
	     testuniqueness((*i).second->vars))
	    config->submenutitle->output((*i).second->vars);
          if(children_too)
            (*i).second->output();
        }
    }
  }
}

void menuentry::store_hints(){
  /* put the $hint variables contents in the hint of
     the submenu[] map. For submenu entries (without a command),
     put the $hint variable in all menuentries that lie below
     that one.
  */
  submenu_container::iterator i,j;
  cStrVec::iterator k;
  unsigned int l;

  // Make sure menuhints are empty:
  for(i=submenus.begin(); i!=submenus.end(); i++){
    (*i).second->menuhints.erase((*i).second->menuhints.begin(),
				 (*i).second->menuhints.end());
  }

  for(i=submenus.begin(); i!=submenus.end(); i++){
    const String &hs=(*i).second->vars[HINTS_VAR];

    if(hs.size() != 0){
      StrVec h;
      
      break_commas(hs,h);
      j=i;
      do{
	for(k=h.begin(); k!=h.end(); k++)
	  (*j).second->menuhints.push_back(*k);
	j++;
	for(l=0; (l!=(*i).first.size());  l++)
	  if((*i).first[l]!=(*j).first[l])
	    break;
      } while (l==(*i).first.size());
    }
  }  
}


void menuentry::process_hints(const StrVec &pref){
  vector <StrVec> hint_list, hint_out;
  vector <const StrVec>::iterator k,m;
  cStrVec::iterator l;
  submenu_container::iterator i;
  submenu_container oldsubmenus;
  hints h;

  // first, process hints of children.
  for(i=submenus.begin(); i!=submenus.end(); i++){
    if(((*i).second->vars[COMMAND_VAR]).size()==0){
      StrVec v(pref);
      cStrVec::iterator j;
      for(j=(*i).first.begin(); j!=(*i).first.end(); j++)
	v.push_back((*j));
      (*i).second->process_hints(v);
    }
  }
  store_hints();

  for(i=submenus.begin(); i!=submenus.end(); i++){
    //if(((*i).second->vars[COMMAND_VAR]).size()!=0){
      StrVec v;
      
      for(l=(*i).first.begin(); l!=(*i).first.end(); l++)
	v.push_back(*l);
      //if(((*i).second->vars[COMMAND_VAR]).size()!=0)
      if(v.size()>1){
	v.pop_back();
	if(config->hint_debug)
	  cout<<"Adding to hint_list: "<<(*i).first
	      <<", hints="<<(*i).second->menuhints<<endl;
	for(l=(*i).second->menuhints.begin(); 
	    l!=(*i).second->menuhints.end(); 
	    l++)
	  v.push_back(*l);
	hint_list.push_back(v);
      } else{
	StrVec empty; // to make sure hint_list[i] and submenus[i] match
	hint_list.push_back(empty);
      }
      //}
  }
  h.set_nentry(      config->hint_nentry);
  h.set_topnentry(config->hint_topnentry);
  h.set_mixedpenalty(config->hint_mixedpenalty);
  h.set_minhintfreq(config->hint_minhintfreq);
  h.set_max_local_penalty(config->hint_mlpenalty);
  h.set_max_ntry(config->hint_max_ntry);
  h.set_max_iter_hint(config->hint_max_iter_hint);
  h.set_debug(      config->hint_debug);

  h.calc_tree(hint_list,hint_out);

  oldsubmenus=submenus;
  submenus.erase(submenus.begin(), submenus.end());

  for(k=hint_list.begin(), m=hint_out.begin(), i=oldsubmenus.begin(); 
      k!=hint_list.end(); 
      k++, m++, i++){
    StrVec v;

    v=(*m);
    v.push_back((*i).first[(*i).first.size()-1]); // restore title

    add_menuentry_ptr(v,(*i).second);
  }
}

void menuentry::postprocess(int n_parent, int level, String prev){
  // Postprocess will set or correct some variables in the
  // menuentry tree (vars), that were not known at the time of
  // creation of the menuentry classes (due to hints, or other reasons)
  //
  // n_parent: number of elements in menu of parent
  // level: how deep this entry is nested in menu tree.

  submenu_container::iterator i;
  int index;

  vars[PRIVATE_LEVEL_VAR]=itoString(level);
  if(!level)
    vars[SECTION_VAR]=prev;
  for(i=submenus.begin(), index=0; 
      i!=submenus.end(); 
      i++, index++){
    String title;
    cStrVec::iterator j;

    title=prev;
    for(j=(*i).first.begin(); j!=(*i).first.end(); j++)
      title += String("/") + (*j);

    (*i).second->vars[SECTION_VAR]=title;

    (*i).second->vars[PRIVATE_ENTRYINDEX_VAR]=itoString(index);
    
    if((*i).second->submenus.size())
      (*i).second->postprocess(submenus.size(), level+1, title);
    else {
      (*i).second->vars[PRIVATE_ENTRYCOUNT_VAR]=itoString(submenus.size());
      (*i).second->vars[PRIVATE_LEVEL_VAR]=itoString(level+1);
    }
  }

  generate_hotkeys();
  vars[PRIVATE_ENTRYCOUNT_VAR]=itoString(n_parent);
}

char menuentry::hotkeyconv(char h){
  if (config->hotkeycase)
    return h;
  else
    return tolower(h);
}
void menuentry::generate_hotkeys(){
  string::size_type i,j;
  list<int>::iterator k, old_k;
  submenu_container::iterator subi;
  map <String, String, less<String> >::iterator l;
  StrVec keys;
  list<int> todo;
  set<char, less<char> > used_chars;
  String s;
  String str0;
  char c;

  str0="0";
  str0[0]='\0';
  if(config->hkexclude)
    s=config->hkexclude->soutput(vars);
  for(i=0;i!=s.length();i++)
    used_chars.insert(hotkeyconv(s[i]));

  for(subi=submenus.begin(), i=0; subi!=submenus.end(); subi++, i++){
    todo.push_back(i);
    l=(*subi).second->vars.find(HOTKEY_VAR);
    if(l!=(*subi).second->vars.end())
      keys.push_back((*l).second);
    else
      keys.push_back(str0);
    keys[i]+=sort_hotkey((*subi).second->vars[TITLE_VAR]);
  }
  j=0;
  while(todo.size()){
    for(k=todo.begin();k!=todo.end();){
      i=*k; 
      old_k=k++; //k++ here, to be able to todo.erase(old_k) safely.
      if(j>=keys[i].length()){
	keys[i]=str0;
	todo.erase(old_k);  //no hotkey found -- give up on this entry.
	continue;
      }
      c=keys[i][j];
      if(c){
	if(used_chars.find(hotkeyconv(c))==used_chars.end()){
	  todo.erase(old_k); //found a hotkey for this entry.
	  keys[i]=String("")+c;
	  used_chars.insert(hotkeyconv(c));
	  continue;
	}
	else
	  keys[i].replace(j,1,str0);
      }
    }
    j++;
  }
  for(subi=submenus.begin(), i=0; subi!=submenus.end(); subi++, i++){
    c=keys[i][0];
    if(c){
      (*subi).second->vars[HOTKEY_VAR]=String("")+c;
    }
  }
}