void
edit_env_rep::local_update (hashmap<string,tree>& old_patch,
			    hashmap<string,tree>& change)
{
  old_patch->pre_patch (back, env);
  old_patch->post_patch (change, env);
  change= invert (back, env);
}

language
ad_hoc_language (language base, tree hyphs) {
  static hashmap<tree,int> abbrevs;
  if (!abbrevs->contains (hyphs))
    abbrevs (hyphs)= N (abbrevs);
  string name= base->res_name * "-" * as_string (abbrevs [hyphs]);
  if (language::instances -> contains (name)) return language (name);
  return tm_new<ad_hoc_language_rep> (name, base, hyphs);
}

void
window_delete (int win) {
    static hashmap<int,bool> busy (false);
    if (busy->contains (win)) return;
    busy (win)= true;
    ASSERT (window_table->contains (win), "window does not exist");
    widget pww= window_table [win];
    window_table->reset (win);
    send_destroy (pww);
    destroy_window_widget (pww);
    busy (win)= false;
}

static void
parse_other_op_index (hashmap<string,string>& t, string s, int& pos) {
  int i;
  i=13 ;
  if( i > N(s) ) i=N(s) ;
  for (i=13; i >= 1; i--) {
    string r=s(pos,pos+i);
    if (t->contains(r) && (t(r)=="op index")) {
      pos=pos+i; return; }
    if (t->contains(r) && (t(r)=="operator")) {
      return; }
    if (t->contains(r) && (t(r)=="op assign")) {
      return; }
  }
}

Future<http::Response> MetricsProcess::__snapshot(
    const http::Request& request,
    const hashmap<string, Future<double> >& metrics,
    const hashmap<string, Option<Statistics<double> > >& statistics)
{
  JSON::Object object;

  foreachpair (const string& key, const Future<double>& value, metrics) {
    // Value.
    if (value.isReady()) {
      object.values[key] = value.get();
    }

    // Statistics.
    Option<Statistics<double> > statistics_ = statistics.get(key).get();

    if (statistics_.isSome()) {
      object.values[key + "/count"] = statistics_.get().count;
      object.values[key + "/min"] = statistics_.get().min;
      object.values[key + "/max"] = statistics_.get().max;
      object.values[key + "/p50"] = statistics_.get().p50;
      object.values[key + "/p90"] = statistics_.get().p90;
      object.values[key + "/p95"] = statistics_.get().p95;
      object.values[key + "/p99"] = statistics_.get().p99;
      object.values[key + "/p999"] = statistics_.get().p999;
      object.values[key + "/p9999"] = statistics_.get().p9999;
    }
  }

  return http::OK(object, request.query.get("jsonp"));
}

Future<hashmap<string, double>> MetricsProcess::__snapshot(
    const Option<Duration>& timeout,
    const hashmap<string, Future<double>>& metrics,
    const hashmap<string, Option<Statistics<double>>>& statistics)
{
  hashmap<string, double> snapshot;

  foreachpair (const string& key, const Future<double>& value, metrics) {
    // TODO(dhamon): Maybe add the failure message for this metric to the
    // response if value.isFailed().
    if (value.isPending()) {
      CHECK_SOME(timeout);
      VLOG(1) << "Exceeded timeout of " << timeout.get()
              << " when attempting to get metric '" << key << "'";
    } else if (value.isReady()) {
      snapshot[key] = value.get();
    }

    Option<Statistics<double>> statistics_ = statistics.get(key).get();

    if (statistics_.isSome()) {
      snapshot[key + "/count"] = static_cast<double>(statistics_.get().count);
      snapshot[key + "/min"] = statistics_.get().min;
      snapshot[key + "/max"] = statistics_.get().max;
      snapshot[key + "/p50"] = statistics_.get().p50;
      snapshot[key + "/p90"] = statistics_.get().p90;
      snapshot[key + "/p95"] = statistics_.get().p95;
      snapshot[key + "/p99"] = statistics_.get().p99;
      snapshot[key + "/p999"] = statistics_.get().p999;
      snapshot[key + "/p9999"] = statistics_.get().p9999;
    }
  }

  return snapshot;
}

tree
texmacs_invarianted (tree t, tree p, int c, string src,
                     hashmap<tree,tree> corr,
                     hashmap<tree,tree> pred,
                     hashmap<tree,tree> succ) {
  if (corr->contains (t)) {
    tree oids= corr[t], ids (TUPLE);
    for (int i=0; i<N(oids); i++) {
      int b, e;
      if (get_range (oids[i], b, e, src)) ids << oids[i];
    }
    if (N(ids) >= 1) {
      tree id= texmacs_best_match (ids, p, c, corr, pred, succ);
      if (id != tree (UNINIT)) return compound ("ilx", id);
    }
  }
  if (is_atomic (t)) return t;
  else {
    int i, n= N(t);
    tree r (t, n);
    for (i=0; i<n; i++)
      r[i]= texmacs_invarianted (t[i], t, i, src, corr, pred, succ);
    return r;
  }
}

std::string stringify(const hashmap<K, V>& map)
{
  std::ostringstream out;
  out << "{ ";
  typename hashmap<K, V>::const_iterator iterator = map.begin();
  while (iterator != map.end()) {
    out << stringify(iterator->first);
    out << ": ";
    out << stringify(iterator->second);
    if (++iterator != map.end()) {
      out << ", ";
    }
  }
  out << " }";
  return out.str();
}

// Returns P_i(perm)
inline unsigned short getPval(perm_t perm, int i, const hashmap &Phashmap) {
  // if (Phashmap.getpayload(perm) == NULL) { // !!
  //   cout<<"perm read failed: "<<endl;
  //   displayperm(perm);
  // }
  // assert(Phashmap.getpayload(perm) != NULL); // !!
  return ((unsigned short*)Phashmap.getpayload(perm))[i];
}

static void
get_subtree_paths (tree t, path p, hashmap<tree,path>& h) {
  if (h->contains (t)) h (t)= path (-1);
  else h (t)= p;
  if (is_compound (t))
    for (int i=0; i<N(t); i++)
      get_subtree_paths (t[i], p * i, h);
}

void hashmap_iterator_remove(id self) {
    hashmap_iterator itr = cast(hashmap_iterator, self);
    hashmap hm = cast(hashmap, itr->host);
    assert (itr->aux != NULL);
    hashmap_entry curr = cast(hashmap_entry, itr->aux);
    hm->remove(hm, curr->key);
    itr->aux = NULL;
}

static void
parse_constant (hashmap<string,string>& t, string s, int& pos) {
  int i=pos;
  if (pos>=N(s)) return;
  while ((i<N(s)) && belongs_to_identifier (s[i])) i++;
  string r= s (pos, i);
  if (t->contains (r) && t(r)=="#2060c0") { pos=i; return; }
}

array<int>
get_hyphens (string s,
             hashmap<string,string> patterns,
             hashmap<string,string> hyphenations, bool utf8) {
  ASSERT (N(s) != 0, "hyphenation of empty string");

  if (utf8) s= cork_to_utf8 (s);

  if (hyphenations->contains (s)) {
    string h= hyphenations [s];
    array<int> penalty (str_length (s, utf8)-1);
    int i=0, j=0;
    while (h[j] == '-') j++;
    i++; goto_next_char (h, j, utf8);
    while (i < N(penalty)+1) {
      penalty[i-1]= HYPH_INVALID;
      while (j < N(h) && h[j] == '-') {
        penalty[i-1]= HYPH_STD;
        j++;
      }
      i++;
      goto_next_char (h, j, utf8);
    }
    //cout << s << " --> " << penalty << "\n";
    return penalty;
  }
  else {
    s= "." * lower_case (s) * ".";
    // cout << s << "\n";
    int i, j, k, l, m, len;
    array<int> T (str_length (s, utf8)+1);
    for (i=0; i<N(T); i++) T[i]=0;
    for (len=1; len < MAX_SEARCH; len++)
      for (i=0, l=0; i<N(s) - len; goto_next_char (s, i, utf8), l++) {
        string r= patterns [s (i, i+len)];
        if (!(r == "?")) {
          // cout << "  " << s (i, i+len) << " => " << r << "\n";
          for (j=0, k=0; j<=len; j++, k++) {
            if ((k<N(r)) && (r[k]>='0') && (r[k]<='9')) {
              m=((int) r[k])-((int) '0');
              k++;
            }
            else m=0;
            if (m>T[l+j]) T[l+j]=m;
          }
        }
      }

    array<int> penalty (N(T)-4);
    for (i=2; i < N(T)-4; i++)
      penalty [i-2]= (((T[i]&1)==1)? HYPH_STD: HYPH_INVALID);
    if (N(penalty)>0) penalty[0] = penalty[N(penalty)-1] = HYPH_INVALID;
    if (N(penalty)>1) penalty[1] = penalty[N(penalty)-2] = HYPH_INVALID;
    if (N(penalty)>2) penalty[N(penalty)-3] = HYPH_INVALID;
    // cout << s << " --> " << penalty << "\n";
    return penalty;
  }
}

void
edit_env_rep::local_end (hashmap<string,tree>& prev_back) {
  int i=0, n=back->n;
  for (; i<n; i++) {
    list<hashentry<string,tree> > l=back->a[i];
    for (; !is_nil(l); l=l->next)
      prev_back->write_back (l->item.key, back);
  }
  back= prev_back;
}

// SPIMI-1: write current postings to intermediate files
//
//   {word}  =>  {ndoc => [doc][frq]}
// pst.trm.x       pst.doc.x         
//
// where x is the id of current intermediate file
//
void IndexWriter::flushPSTBlk(hashmap<string, vector<pair<int, int> > >&pst, int turn) {
  ofstream ftrm, fdoc;
  string prefix = path+"/"+POSTINGS_FILE;

  ftrm.open((prefix+".trm."+itoa(turn)).c_str(), ios::binary);
  fdoc.open((prefix+".doc."+itoa(turn)).c_str(), ios::binary);

  hashmap<string, vector<pair<int, int> > >::iterator it;
  vector<pair<int, int> >::iterator jt;
  vector<string> list;
  for (it = pst.begin(); it != pst.end(); ++it) {
    list.push_back(it->first);
  }
  sort(list.begin(), list.end());

  for (unsigned i = 0; i < list.size(); ++i) {
    it = pst.find(list[i]);
    string &term = list[i]; 
    int ndoc = it->second.size(), cnt = 0, accum = 0;

    for (jt = it->second.begin(); jt != it->second.end(); ++jt) {
      int did = jt->first;
      int frq = jt->second;
      didbuf[cnt] = did;
      frqbuf[cnt] = frq;
      accum += frq;
      assert(accum > 0 || !(cout << accum << endl));
      cnt++;
    }
    fwrite(fdoc, &ndoc, sizeof(ndoc));
    fwrite(fdoc, didbuf, sizeof(didbuf[0])*ndoc);
    fwrite(fdoc, frqbuf, sizeof(frqbuf[0])*ndoc);

    TermAttr attr;
    attr.str = term;
    attr.df = ndoc;
    attr.cf = accum;
    attr.flush(ftrm);
  }
  ftrm.close();
  fdoc.close();
}

text_property
oriental_language_rep::advance (tree t, int& pos) {
  string s= t->label;
  if (pos == N(s)) return &tp_normal_rep;

  if (s[pos] == ' ') {
    pos++;
    return &tp_space_rep;
  }

  if (pos < N(s) && !test (s, pos, "<#")) {
    while (pos < N(s) && s[pos] != ' ' && !test (s, pos, "<#"))
      tm_char_forwards (s, pos);
    return &tp_cjk_no_break_rep;
  }

  int start= pos;
  tm_char_forwards (s, pos);
  string c= s (start, pos);
  int next= pos;
  tm_char_forwards (s, next);
  string x= s (pos, next);

  if (punct->contains (c)) {
    if (punct->contains (x) || pos == N(s))
      return &tp_cjk_no_break_period_rep;
    else return &tp_cjk_period_rep;
  }
  else {
    if (punct->contains (x) || pos == N(s))
      return &tp_cjk_no_break_rep;
    else return &tp_cjk_normal_rep;
  }
}

void
unregister_pointer (string id, observer which) {
  // cout << "Unregister: " << id << " -> " << which << "\n";
  // cout << "Unregister: " << id << " -> " << obtain_tree (which) << "\n";
  list<observer>& l1= id_resolve (id);
  l1= remove (l1, which);
  if (is_nil (l1)) id_resolve->reset (id);
  list<string>& l2= pointer_resolve (which);
  l2= remove (l2, id);
  if (is_nil (l2)) pointer_resolve->reset (which);
}

 std::vector<int> search(std::string s){
     if (s.length() == 0) {
         return indexes;
     }else{
         char first = s.at(0);
         if (children.find(first) != children.end()) {
             std::string remain(s.substr(1));
             return children[first]->search(remain);
         }
     }
     
     std::vector<int> tmp;
     return tmp;
 }

 void insertString(std::string s, int index){
     indexes.push_back(index);
     if (s.size()>0) {
         value = s.at(0);
         std::shared_ptr<SuffixTreeNode> child;
         if (children.find(value) != children.end()) {
             child = children[value];
         }else{
             child.reset(new SuffixTreeNode());
             children[value] = child;
         }
         std::string remain(s.substr(1));
         child->insertString(remain, index);
     }
 }

  foreach (const Future<TaskStatus>& taskStatus, taskStatuses) {
    AWAIT_READY(taskStatus);

    Option<TaskState> taskState = taskStates.get(taskStatus->task_id());
    ASSERT_SOME(taskState);

    switch (taskState.get()) {
      case TASK_STAGING: {
        ASSERT_EQ(TASK_STARTING, taskStatus->state())
          << taskStatus->DebugString();

        taskStates[taskStatus->task_id()] = TASK_STARTING;
        break;
      }
      case TASK_STARTING: {
        ASSERT_EQ(TASK_RUNNING, taskStatus->state())
          << taskStatus->DebugString();

        taskStates[taskStatus->task_id()] = TASK_RUNNING;
        break;
      }
      default: {
        FAIL() << "Unexpected task update: " << taskStatus->DebugString();
        break;
      }
    }
  }