bool Serialization::save(std::multiset<Event *, Cmp_event_day> &events)
{
    //Save file to disk
    QFile file("events.txt");
    if(!file.open(QIODevice::WriteOnly))
    {
        qDebug() << "Could not open file";
        return false;
    }

    //create output stream
    QDataStream out (&file);
    //set output version
    out.setVersion(QDataStream::Qt_4_8);

    //iteration
    std::multiset<Event *>::iterator it;
    for ( it=events.begin() ; it != events.end(); it++ )
        out << **it;

    //Finito! flush the stream to the file and close
    file.flush();
    file.close();
    return true;
}

void Tptp::checkLetBinding(const std::vector<Expr>& bvlist, Expr lhs, Expr rhs,
                           bool formula) {
  if (lhs.getKind() != CVC4::kind::APPLY_UF) {
    parseError("malformed let: LHS must be a flat function application");
  }
  const std::multiset<CVC4::Expr> vars{lhs.begin(), lhs.end()};
  if(formula && !lhs.getType().isBoolean()) {
    parseError("malformed let: LHS must be formula");
  }
  for (const CVC4::Expr& var : vars) {
    if (var.hasOperator()) {
      parseError("malformed let: LHS must be flat, illegal child: " +
                 var.toString());
    }
  }

  // ensure all let-bound variables appear on the LHS, and appear only once
  for (const Expr& bound_var : bvlist) {
    const size_t count = vars.count(bound_var);
    if (count == 0) {
      parseError(
          "malformed let: LHS must make use of all quantified variables, "
          "missing `" +
          bound_var.toString() + "'");
    } else if (count >= 2) {
      parseError("malformed let: LHS cannot use same bound variable twice: " +
                 bound_var.toString());
    }
  }
}

inline bool greater_than_strict(std::multiset< int > multiset1, std::multiset< int > multiset2, unsigned int id1, unsigned int id2){

			std::multiset< int >::iterator multiset1_itr = multiset1.begin(), multiset2_itr = multiset2.begin();
			int fi,fj;

 			for ( fi = multiset1.size(),fj = multiset2.size(); fi>0 && fj>0 ;fi--,fj--)
			{
 
				if (*multiset1_itr == *multiset2_itr)
				{
					multiset1_itr++ , multiset2_itr++;
				}
				else {
				
 					//return *multiset1_itr < *multiset2_itr ; //ascending
					return *multiset1_itr > *multiset2_itr ;//descending
				}
			}

			//Haven't returned yet and the foor loop exited, so that means the two input multiset have equal entries atleast the common portions 
 			if (fi==fj)
 			{
				//If they are equal, that means the relevance multiset is exactly the same, in that case we need to enforce stricter ordering based on node ids
				return id1> id2; //Descending
 			}
			//return (fi<fj);//asecending
			return (fi>fj);//descending

};

/**
 A = x1 or x2 or ... xn
 create cnf to create an Equility.
 * @brief Solver::SatBaseClass::createTseitinOr
 * @param vars x1, ..., xn
 * @return A
*/
uint Solver::SatBaseClass::createTseitinOr(std::multiset<literal>& vars){
    if(vars.size() == 0) return getFalseVar();
    if(vars.size() == 1) return (*vars.begin()).varId;
    uint A(++countVars);
// if A is true, then one of the xi must be true
    result << "-" << A << " ";
    for(const literal& t: vars){
        if(t.positiv){
            result << t.varId << " ";
        }else {
            result << "-" << t.varId << " ";
        }
    }
    result << "0" << std::endl;
    countClausel++;

// if one of the xi is true then A is true
    for(const literal& t: vars){
        result << A << " ";
        if(t.positiv){
            result << "-" << t.varId << " 0" << std::endl;
        } else {
            result << t.varId << " 0" << std::endl;
        }
        countClausel++;
    }
    return A;
}

void populateMultiset(std::multiset<sdEvent*, sdEventCompare> eventSet) {
    std::multiset <sdEvent*, sdEventCompare>::iterator eit = eventSet.begin();
    while(eit != eventSet.end()) {
        sdEvent* event = *eit;
        std::cout << "   " << event->getTime() << ":" << event->getDescriptorAsString() << " " << event->getValueAsString() << std::endl;
        eit++;
    }
}

static bool find_and_remove(std::multiset<std::string>& files,
		const std::string& filename)
{
	std::multiset<std::string>::iterator ptr;
	if ( (ptr = files.find(filename)) != files.end())
	{
		//erase(filename) erases *all* entries with that key
		files.erase(ptr);
		return true;
	}
	return false;
}

bool TrajectoryEvaluator::checkTrajectoriesForCollision(const std::multiset<PolyTraj2D, PolyTraj2D::CompPolyTraj2D>& traj_set,
    const std::map<int, Vehicle>& predicted_obstacles, const std::string set_name,
    std::multiset<PolyTraj2D>::const_iterator& best_traj, double& longest_time_to_collision) {

  bool collision = true, found_maybe = false;
  double collision_time;
  longest_time_to_collision = 0;
  std::multiset<PolyTraj2D>::const_iterator it_traj;
  uint32_t j = 0;
  for (it_traj = traj_set.begin(), j = 0; it_traj != traj_set.end(); it_traj++, j++) {

    TrjOccupancyState_t static_collision = TRJ_BLOCKED;
    if (obstacle_map_) {
      pthread_mutex_lock(&obstacle_map_mutex_);
      static_collision = checkCollisionStatic(it_traj->trajectory2D_); // TODO: add collision_time and longest_time_to_collision to static check
      pthread_mutex_unlock(&obstacle_map_mutex_);

      if (static_collision==TRJ_BLOCKED) {
        continue;
      }
//      std::vector<driving_common::TrajectoryPoint2D>::const_iterator tit = it_traj->trajectory2D_.begin(), tit_end = it_traj->trajectory2D_.end();
//      bool zero_velocity=true;
//      for(; tit!=tit_end; tit++) {
//      if(std::abs((*tit).v)>.01) {zero_velocity=false; break;}
//      }
//      if(zero_velocity) {continue;}
    }

    if (!checkCollisionOfTrajectoriesDynamic(it_traj->trajectory2D_, predicted_obstacles, collision_time)) {
      if (j != 0) {std::cout << j << "th trajectory (" << set_name << ") of " << traj_set.size() << " is free.\n";}
      longest_time_to_collision = std::numeric_limits<double>::infinity();
        // we found a collision-free trajectory regardless if it's in maybe range or not
      collision = false;
        // if we did not find any free before or we found a free now and had a maybe before => update best trajectory
      if(!found_maybe || static_collision==TRJ_FREE) {best_traj = it_traj;}
        // if there are only maybes we want the one that was found first since it's the best :-)
        // otherwise we found a free one and are done
      if(static_collision==TRJ_MAYBE_BLOCKED) {found_maybe=true;}
      else {
        break;
      }
    }
    else {
      if (collision_time > longest_time_to_collision) {
        longest_time_to_collision = collision_time;
        best_traj = it_traj;
      }
    }
  }

  return collision;
}

		virtual Json::Value judgeStatus()
		{
			Json::Value ret;
			ret["runningCnt"]=runningCnt;
			ret["totDumpCmdCnt"]=totCnt;
			ret["preserveCnt"]=preserveCnt;
			ret["boardingPass"]=Json::Value();
			pthread_mutex_lock(&cntLock);
			for (std::multiset<int>::iterator i=boardingPass.begin(); i!=boardingPass.end(); i++)
				ret["boardingPass"].append(*i);
			pthread_mutex_unlock(&cntLock);
			return ret;
		}

unsigned LyricsMatchGrader::catagoryGrader(const std::multiset<std::string>& lyrics,
										   const std::string& queryWord) const
{
	unsigned int grade = DEFAULT_GRADE;
	size_t wordOccourences = lyrics.count(queryWord);

	if(QUERY_WORD_NOT_FOUND_FLAG != lyrics.count(queryWord))
	{
		grade = (this->getGradingCatagoryWeight()) * (wordOccourences);
	}

	return grade;
}

int plPXPhysicalControllerCore::SweepControllerPath(const hsPoint3& startPos, const hsPoint3& endPos, hsBool vsDynamics, hsBool vsStatics, 
                            uint32_t& vsSimGroups, std::multiset< plControllerSweepRecord >& WhatWasHitOut)
{
    NxCapsule tempCap;
    tempCap.p0 =plPXConvert::Point( startPos);
    tempCap.p0.z = tempCap.p0.z + fPreferedRadius;
    tempCap.radius = fPreferedRadius ;
    tempCap.p1 = tempCap.p0;
    tempCap.p1.z = tempCap.p1.z + fPreferedHeight;

    NxVec3 vec;
    vec.x = endPos.fX - startPos.fX;
    vec.y = endPos.fY - startPos.fY;
    vec.z = endPos.fZ - startPos.fZ;

    int numberofHits = 0;
    int HitsReturned = 0;
    WhatWasHitOut.clear();
    NxScene *myscene = plSimulationMgr::GetInstance()->GetScene(fWorldKey);
    NxSweepQueryHit whatdidIhit[10];
    unsigned int flags = NX_SF_ALL_HITS;
    if(vsDynamics)
        flags |= NX_SF_DYNAMICS;
    if(vsStatics)
        flags |= NX_SF_STATICS;
    numberofHits = myscene->linearCapsuleSweep(tempCap, vec, flags, nil, 10, whatdidIhit, nil, vsSimGroups);
    if(numberofHits)
    {//we hit a dynamic object lets make sure it is not animatable
        for(int i=0; i<numberofHits; i++)
        {
            plControllerSweepRecord CurrentHit;
            CurrentHit.ObjHit=(plPhysical*)whatdidIhit[i].hitShape->getActor().userData;
            CurrentHit.Norm.fX = whatdidIhit[i].normal.x;
            CurrentHit.Norm.fY = whatdidIhit[i].normal.y;
            CurrentHit.Norm.fZ = whatdidIhit[i].normal.z;
            if(CurrentHit.ObjHit != nil)
            {
                hsPoint3 where;
                where.fX = whatdidIhit[i].point.x;
                where.fY = whatdidIhit[i].point.y;
                where.fZ = whatdidIhit[i].point.z;
                CurrentHit.locHit = where;
                CurrentHit.TimeHit = whatdidIhit[i].t ;
                WhatWasHitOut.insert(CurrentHit);
                HitsReturned++;
            }
        }
    }

    return HitsReturned;
}

inline void converter<point_t>::knot_insertion(
    point_container_t& P,
    std::multiset<typename point_t::value_type>& knots,
    std::size_t order) const {
  //typedef typename point_t::value_type value_type;
  std::set<value_type> unique(knots.begin(), knots.end());

  for (typename std::set<value_type>::const_iterator i = unique.begin();
       i != unique.end();
       ++i) {
    if (knots.count(*i) < order - 1) {
      knot_insertion(P, knots, order, *i);
    }
  }
}

void ExtremalQuery3BSP<Real>::CreateBSPTree (
    std::multiset<SphericalArc>& arcs, std::vector<SphericalArc>& nodes)
{
    // The tree has at least a root.
    mTreeDepth = 1;

    typename std::multiset<SphericalArc>::reverse_iterator iter;
    for (iter = arcs.rbegin(); iter != arcs.rend(); ++iter)
    {
        InsertArc(*iter, nodes);
    }

    // The leaf nodes are not counted in the traversal of InsertArc.  The
    // depth must be incremented to account for leaves.
    ++mTreeDepth;
}

//回溯法求解
std::multiset<int> knapsack(std::multiset<std::pair<int,int> >& products,int maxLoad){
  int N=products.size();
  int *w = new int[N+1];
  int *v = new int[N+1];
  int *IDs = new int[N+1];
  w[0]=0;v[0]=0;
  int i=1;
  for(auto p : products){
    w[i]=v[i]=p.second;
    IDs[i]=p.first;
    i++;
  }
  int *flag= new int[N+1]; //flag[i][j]表示在容量为j的时候是否将第i件物品放入背包
  for (int i = 0; i < N+1; i++) flag[i]=0;
  zero_one_pack(maxLoad, w, v, flag, N);
  //cout << "需要放入的物品如下" << endl;
  multiset<int> sol;
  for (int i = 1; i <= N; i++) {
    if (flag[i] == 1)
      sol.insert(IDs[i]);
      //cout << i << "重量为" << w[i] << ", 价值为" << v[i] << endl;
  }
  //cout << "总的价值为: " << total_value << endl;
  delete w;
  delete v;
  delete flag;
  delete IDs;
  return sol;
}

 void operator()(clmdep_msgpack::object::with_zone& o, const std::multiset<T, Compare, Alloc>& v) const {
     o.type = clmdep_msgpack::type::ARRAY;
     if (v.empty()) {
         o.via.array.ptr = nullptr;
         o.via.array.size = 0;
     } else {
         uint32_t size = checked_get_container_size(v.size());
         clmdep_msgpack::object* p = static_cast<clmdep_msgpack::object*>(o.zone.allocate_align(sizeof(clmdep_msgpack::object)*size));
         clmdep_msgpack::object* const pend = p + size;
         o.via.array.ptr = p;
         o.via.array.size = size;
         typename std::multiset<T, Compare, Alloc>::const_iterator it(v.begin());
         do {
             *p = clmdep_msgpack::object(*it, o.zone);
             ++p;
             ++it;
         } while(p < pend);
     }
 }

void f_multiset() {
  std::multiset<int> C;
  std::multiset<int>::iterator MSetI1 = C.begin();
  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: use auto when declaring iterators
  // CHECK-FIXES: auto MSetI1 = C.begin();

  std::multiset<int>::reverse_iterator MSetI2 = C.rbegin();
  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: use auto when declaring iterators
  // CHECK-FIXES: auto MSetI2 = C.rbegin();

  const std::multiset<int> D;
  std::multiset<int>::const_iterator MSetI3 = D.begin();
  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: use auto when declaring iterators
  // CHECK-FIXES: auto MSetI3 = D.begin();

  std::multiset<int>::const_reverse_iterator MSetI4 = D.rbegin();
  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: use auto when declaring iterators
  // CHECK-FIXES: auto MSetI4 = D.rbegin();
}

//if return is 0 then neither greater or equal, if returned 1 then equal, if 2 then greater
inline int equal_and_greater(std::multiset< int > multiset1, std::multiset< int > multiset2){

			std::multiset< int >::iterator multiset1_itr = multiset1.begin(), multiset2_itr = multiset2.begin();
			int fi,fj;
 
			for ( fi = multiset1.size(),fj = multiset2.size(); fi>0 && fj>0 ;fi--,fj--)
			{
				if (*multiset1_itr == *multiset2_itr)
				{
					multiset1_itr++ ; multiset2_itr++;  
				}
				else {
					return ((*multiset1_itr > *multiset2_itr) ? 2 : (*multiset1_itr == *multiset2_itr)?  1 : 0) ;
				}
 			}
			
			return (fi < fj) ? 0: (fi > fj) ? 2: 1;

};

void Comparer::SortTree(Node *p, std::multiset<Node *, NCompare> &setNodes)
{
	std::vector<Node *> temp;
	setNodes.insert(p);
	temp = p->getChildren();
	for (auto node : temp)
	{
		SortTree(node, setNodes);
	}
	temp.clear();
}

inline std::multiset<T>& operator>> (object o, std::multiset<T>& v)
{
	if(o.type != type::ARRAY) { throw type_error(); }
	object* p = o.via.array.ptr + o.via.array.size;
	object* const pbegin = o.via.array.ptr;
	while(p > pbegin) {
		--p;
		v.insert(p->as<T>());
	}
	return v;
}

inline bool greater_than(std::multiset< int > multiset1, std::multiset< int > multiset2){

			std::multiset< int >::iterator multiset1_itr = multiset1.begin(), multiset2_itr = multiset2.begin();
			int fi,fj;

 			for ( fi = multiset1.size(),fj = multiset2.size(); fi>0 && fj>0 ;fi--,fj--)
			{
 
				if (*multiset1_itr == *multiset2_itr)
				{
					multiset1_itr++ , multiset2_itr++;
				}
				else {
				
 					//return *multiset1_itr < *multiset2_itr ; //ascending
					return *multiset1_itr > *multiset2_itr ;//descending
				}
			}

			//Haven't returned yet and the foor loop exited, so that means the two input multiset have equal entries atleast the common portions 
 			//return (fi<fj);//asecending
			return (fi>fj);//descending
};

int main()
{
    typedef test_compare<std::less<int> > C;
    const std::multiset<int, C> m(C(3));
    assert(m.empty());
    assert(m.begin() == m.end());
    assert(m.key_comp() == C(3));
    assert(m.value_comp() == C(3));
}