__normal_call bool_type find (
     data_type const&_data,
     list_type      &_list
     )
 {
     if (this->_lptr.empty()) return false;
     
 /*------------------------------- evaluate hash value */
     size_type _hpos = this->_hash(_data ) 
                     % this->_lptr.count();
                     
 /*------------------------------- scan list from head */
     item_type*_same = this->_lptr[_hpos] ;
 /*------------------------------- check exact matches */
     for( ; _same != nullptr; 
                 _same = _same->_next)
     {
         if (this->_pred(_same->_data,_data))
         {
             _list.push_tail(_same);
         }
     }
     
 /*---------------------------------- no matches found */
     return ( !_list.empty() );
 }

 void event_callback(const std::string type, const std::string data, const std::string extra)
 {
   event_record r;
   list_type::iterator record = list_.insert(list_.begin(), r);
   record->type = type;
   record->data = data;
   record->extra = extra;
 }

   static int index(list_type const & x, value_type const & v)
   {
      int i = 0;
      for(typename list_type::const_iterator it=x.begin(); it!=x.end(); ++it,++i)
      {
         if( *it == v ) return i;
      }

      PyErr_SetString(PyExc_ValueError, "Value not in the list");
      throw boost::python::error_already_set();
   }

list_type complement(const list_type& list, size_t max)
{
    list_type out;
    list_type::const_iterator li = list.begin();
    for (size_t i = 0; i < max; ++i)
    {
        if (li != list.end() && *li == i)
            ++li;
        else
            out.push_back(i);
    }
    return out;
}

 bool pop_type(const std::string& type)
 {
   for(list_type::iterator it = list_.begin();
       it != list_.end();
       it++)
   {
     if(it->type == type)
     {
       list_.erase(it);
       return true;
     }
   }
   return false;
 }

 int count_type(const std::string& type)
 {
   int count = 0;
   for(list_type::iterator it = list_.begin();
       it != list_.end();
       it++)
   {
     if(it->type == type)
     {
       count++;
     }
   }
   return count;
 }

 void flush()
 {
   if(state_index_ > last_update_sent_)
   {
     for(subscriber_list_type::iterator it = subscriber_list_.begin();
         it != subscriber_list_.end();
         it++)
     {
       send_updates(*it);
     }
     last_update_sent_ = state_index_;
     added_list_.clear();
     removed_list_.clear();
   }
 }

static void lb_create_cut(const par::communicator& comm, unsigned int num_cut,
                          unsigned int dimen, const list_type& pl, LBData& lbd)
{
#ifndef NDEBUG
        if (num_cut > pl.size()-1)
                throw std::runtime_error("Cannot create more cuts than points");
#endif
        const unsigned int my_rank = comm.rank();
        // const unsigned int num_proc = comm.size();

        std::vector<real> cut(num_cut);

        const unsigned int num_point = pl.size();
        unsigned int ipoint = 0;
        list_type::const_iterator pit = pl.begin();
        for (unsigned int icut=0; icut<num_cut; icut++) {
                const unsigned int target = std::round((num_point - ipoint) / (num_cut + 1 - icut));
                // std::cout << "icut=" << icut << ", target = " << target << std::endl;
                const unsigned int visited = ipoint;
                while ((ipoint - visited) < target) {
                        ++pit;
                        ipoint++;
                }
                const point_type& p = *pit;
                cut[icut] = p[dimen];
        }

        // allgather number of cuts on each proc
        lbd.recvcounts[my_rank] = cut.size();
        comm.allgather(lbd.recvcounts.data() + my_rank, 1, lbd.recvcounts.data(), 1);

        const unsigned int glob_num_cut =
                std::accumulate(lbd.recvcounts.begin(), lbd.recvcounts.end(), 0);

        // Resize cut (destroying existing cuts)
        lbd.cut.resize(glob_num_cut);

        lbd.rdispls[0] = 0;
        for (unsigned int i=1; i<lbd.rdispls.size(); i++)
                lbd.rdispls[i] = lbd.rdispls[i-1] + lbd.recvcounts[i-1];

        // allgatherv into lbd.pointcut
        comm.allgatherv(cut.data(), cut.size(), lbd.cut.data(),
                        lbd.recvcounts.data(), lbd.rdispls.data());

        // Sort the cuts
        std::sort(lbd.cut.begin(), lbd.cut.end());
}

    __normal_call bool_type circ_list (
        real_type *_ppos,
        iptr_type &_elem,
        list_type &_list,
        iptr_type  _hint  = null_flag()
        )
    {
        this->_work.clear();
    /*--------------------------- find enclosing tria */
        if (walk_mesh_node(_ppos, _elem, _hint))
		{
    /*------------------------------ bfs about cavity */
        typename tria_pred:: 
        template circ_pred<
             self_type >_pred( _ppos) ;
             
		walk_tria_list (_elem, +1, 
                        _pred, _work) ;
                        
    /*------------------------------ push index lists */
        _list.push_tail(_work.head(),
						_work.tend()) ;
						
		return (  true ) ;
        }
        
        return ( false ) ;
    }

list_type inverse(const list_type& src)
{
	typedef typename list_type::range_type range_type;
	typedef typename list_type::payload_type payload_type;
	typedef typename list_type::range_size_type range_size_type;
	typedef typename list_type::const_iterator const_iterator;
	list_type result( src.limit() );
	range_size_type last = 0;
	for ( const_iterator i = src.begin(); i != src.end(); ++i )
	{
		result.insert( range_type( last, i->begin() ) );
		last = i->end();
	}
	result.insert( range_type( last, src.limit() ) );
	return result;
}

   static void set(list_type & x, int i, value_type const & v)
   {
      if( i < 0 ) i += x.size();

      if( i >= 0 && i < (int)x.size() )
      {
         iter_type it = x.begin();
         for(int pos = 0; pos < i; ++pos) ++it;
         *it = v;
      }
      else
      {
         PyErr_SetString(PyExc_IndexError, "Index out of range");
         boost::python::throw_error_already_set();
      }
   }

void balance_set(PSTopology top, LBMethod method, unsigned int dimen, list_type& pl)
{
        const par::communicator& comm = par::comm_world();
        if (comm.size() == 1) return;

        const double start_time = par::wtime();

        if (top == PSTopology::Unary) {
                if (method == LBMethod::S2A2) lb_s2a21d(dimen, pl);
                else if (method == LBMethod::RCB) lb_rcb1d(dimen, pl);
                else throw std::runtime_error("Unknown load balancing method");
        }
        else if (top == PSTopology::Zoltan) {
                lb_zoltan(top, method, dimen, pl);
        }

        comm.barrier();
        const double end_time = par::wtime();

        LBData lbd(par::comm_world(), pl.size());
        const real imbalance = lb_calculate_imbalance(lbd);
        if (comm.rank() == 0) {
                std::cout << "Imbalance = " << imbalance << std::endl;
                std::cout << "LB time = "
                          << std::setprecision(6)
                          << (end_time - start_time) << std::endl;
        }
}

    //! Calculate rank of a subset A
    unsigned int rank(const list_type& list) const
    {
        list_type out(list.size());

        unsigned int max = 0;

        for (auto b : m_bases)
        {
            list_type::iterator end =
                std::set_intersection(list.begin(), list.end(),
                                      b.begin(), b.end(),
                                      out.begin());

            max = std::max<unsigned int>(max, end - out.begin());
        }

        return max;
    }

 void recompute_offset() {
         // Perform a scan(+)
         const list_type::size_type s = list.size();
         comm.scan(&s, &glob_offset_, par::sum());
         // Scan was inclusive, so must subtract off this value
         glob_offset_ -= s;
         // Set valid flag
         offset_valid = true;                
 }

static void lb_migrate_points(const par::communicator& comm, list_type& pl, LBData& lbd)
{
        const unsigned int num_proc = comm.size();
        const unsigned int dim = point_type::dim;

        // Sendcounts should be already filled
        // Perform alltoall for recvcounts from sendcounts
        lbd.recvcounts.resize(num_proc);
        comm.alltoall(lbd.sendcounts.data(), 1, lbd.recvcounts.data(), 1);

        // Resize the send buffer
        lbd.send.resize(pl.size() * dim);

        // Pack up the send buffer
        {
                unsigned int i = 0;
                for (const point_type& p : pl)
                        for (unsigned int d=0; d<dim; d++, i++)
                                lbd.send[i] = p[d];
        }

        // Offsets in memory (for alltoallv)
        lbd.sdispls[0] = 0;
        for (unsigned int i=1; i<num_proc; i++)
                lbd.sdispls[i] = lbd.sdispls[i-1] + lbd.sendcounts[i-1];

        lbd.rdispls[0] = 0;
        for (unsigned int i=1; i<num_proc; i++)
                lbd.rdispls[i] = lbd.rdispls[i-1] + lbd.recvcounts[i-1];

        // Create receive buffer
        const int total_recv = std::accumulate(lbd.recvcounts.begin(), lbd.recvcounts.end(), 0);
        lbd.recv.resize(total_recv);

        // Communicate points (alltoallv)
        comm.alltoallv(lbd.send.data(), lbd.sendcounts.data(), lbd.sdispls.data(),
                       lbd.recv.data(), lbd.recvcounts.data(), lbd.rdispls.data());

        // Clear out current points and reload from the receive buffer
        pl.clear();
        for (unsigned int i=0; i<lbd.recv.size(); i+=dim)
                pl.emplace_back(point_type(lbd.recv[i], lbd.recv[i+1]));
}

    //! test if a set of items contains a circuit
    bool   contains_circuit(const list_type& list) const
    {
        list_type out(list.size());

        for (auto c : m_circuits)
        {
            list_type::iterator end =
                std::set_intersection(list.begin(), list.end(),
                                      c.begin(), c.end(),
                                      out.begin());

            if (end == out.begin() + c.size())
            {
                //std::cout << "contains " << c << std::endl;
                return true;
            }
        }

        return false;
    }

	void
	shrink(_tMap& m, _func f)
	{
		yassume(!empty());

		auto& val(list_type::back());

		if(f)
			f(val);
		m.erase(val.first);
		list_type::pop_back();
	}

  void send_all(const ID& client_id)
  {
    update_packet msg;
    msg.type = update_packet::complete;
    msg.num_entries = list_.size();
    msg.start_index = 0;
    msg.end_index = state_index_;

    outbound_data<serializer::boost_serializer, update_packet> o_msg(msg);
    outbound_data<serializer::boost_serializer, list_type> o_list(list_);
    outbound_pair o_pair(o_msg, o_list);

    send_to_instance(client_id, header_packet::update, o_pair);
  }

	__normal_call void_type walk_tria (
		iptr_type  _tria ,
	    tria_pred  _pred ,
	    list_type &_list
		)
	{
		this->_work.clear()  ;  
    /*----------------------------------- bfs about _tria */
        walk_tria_list (_tria,    +1, 
                        _pred, _work) ;
                        
    /*----------------------------------- push index list */
		_list.push_tail(_work.head(),
						_work.tend()) ;
	}

 bool check_board(list_type const& list, std::size_t level)
 {
     for(std::size_t i = 0 ;i < level; ++i){
         if((list.at(i) == list.at(level))
             || (list.at(level) - list.at(i) == level - i)
             || (list.at(i) - list.at(level) == level - i))
             return false;
     }
     return true;
 }