/// Check that any two present nodes are connected by a path of present nodes
bool all_characters_connected(const Tree& T,dynamic_bitset<> present,const vector<int>& _ignore) {
  assert(present.size() == T.n_nodes());

  //--------- set the ignored nodes to 'not present' -----------//
  dynamic_bitset<> ignore(present.size());
  for(int i=0;i<_ignore.size();i++) {
    int n = _ignore[i];
    present[n] = false;
    ignore[n] = true;
  }

  //---------- for each internal node... -------------//
  for(int n1=T.n_leaves(); n1<T.n_nodes(); n1++) {

    if (present[n1] or ignore[n1]) continue;
      
    //------- if it is '-' and not ignored ... -------//
    vector<const_nodeview> neighbors;
    append(T[n1].neighbors(),neighbors);
    assert(neighbors.size() == 3);

    //---- check the three attatched subtrees ... ----//
    int total=0;
    for(int i=0;i<neighbors.size();i++) {
      dynamic_bitset<> group = T.partition(n1,neighbors[i]);
      if (present.intersects(group))
	total++;
    }

    //----- nodes should be present in only one. -----//
    if (total > 1)
      return false;
  }
  return true;
}

static
bool can_die_early(const NGHolder &g, const vector<StateInfo> &info,
                   const dynamic_bitset<> &s,
                   map<dynamic_bitset<>, u32> &visited, u32 age_limit) {
    if (contains(visited, s) && visited[s] >= age_limit) {
        /* we have already (or are in the process) of visiting here with a
         * looser limit. */
        return false;
    }
    visited[s] = age_limit;

    if (s.none()) {
        DEBUG_PRINTF("dead\n");
        return true;
    }

    if (age_limit == 0) {
        return false;
    }

    dynamic_bitset<> all_succ(s.size());
    step(g, info, s, &all_succ);
    all_succ.reset(NODE_START_DOTSTAR);

    for (u32 i = 0; i < N_CHARS; i++) {
        dynamic_bitset<> next = all_succ;
        filter_by_reach(info, &next, CharReach(i));
        if (can_die_early(g, info, next, visited, age_limit - 1)) {
            return true;
        }
    }

    return false;
}

void connect_all_characters(const Tree& T,dynamic_bitset<>& present)
{
  assert(present.size() == T.n_nodes());
  
  //---------- for each internal node... -------------//
  for(int n1=T.n_leaves(); n1<T.n_nodes(); n1++) 
  {
    if (present[n1]) continue;

    //------- if it is '-' and not ignored ... -------//
    vector<const_nodeview> neighbors;
    append(T[n1].neighbors(),neighbors);
    assert(neighbors.size() == 3);

    //---- check the three attatched subtrees ... ----//
    int total=0;
    for(int i=0;i<neighbors.size();i++)
    {
      dynamic_bitset<> group = T.partition(n1,neighbors[i]);
      if (present.intersects(group))
	total++;
    }

    if (total > 1)
      present[n1] = true;
  }
  assert(all_characters_connected(T,present,vector<int>()));
}

void print(const dynamic_bitset<>& items, ostream& out) {
	out << "{ ";
	for(dynamic_bitset<>::size_type i = items.find_first(); i != items.npos; i = items.find_next(i)){
		out << i << " ";
	}
	out << "} -- " << items.count() << endl;
}

uint32_t cFixedAlloc::findFirstOf(bool check, dynamic_bitset<>& bit) {
	for ( int i = 0; i < bit.size(); ++i ) {
		if ( bit[i] == check )	return i;
	}

	return bit.size() + 1;
}

Partition::Partition(const vector<string>& n,const dynamic_bitset<>& g,const dynamic_bitset<>& mask) 
  :names(n),group1((~ g) & mask),group2(g & mask)
{
  assert(n.size() == g.size());
  assert(g.size() == mask.size());
  assert(not group1.intersects(group2));
}

vector<int> diffset_for_single_item(dynamic_bitset<> tids) {
    vector<int> diffset;
    dynamic_bitset<>::size_type size = tids.size();
    for (dynamic_bitset<>::size_type i = 0; i < size; ++i)
        if ( ! tids.test(i))
            diffset.push_back(i);
    return diffset;
}

static
std::string dumpStates(const dynamic_bitset<> &s) {
    std::ostringstream oss;
    for (size_t i = s.find_first(); i != s.npos; i = s.find_next(i)) {
        oss << i << " ";
    }
    return oss.str();
}

static
flat_set<NFAVertex> getVertices(const dynamic_bitset<> &in,
                                const vector<StateInfo> &info) {
    flat_set<NFAVertex> out;
    for (size_t i = in.find_first(); i != in.npos; i = in.find_next(i)) {
        out.insert(info[i].vertex);
    }
    return out;
}

static
void step(const NGHolder &g, const vector<StateInfo> &info,
          const dynamic_bitset<> &in, dynamic_bitset<> *out) {
    out->reset();
    for (size_t i = in.find_first(); i != in.npos; i = in.find_next(i)) {
        NFAVertex u = info[i].vertex;
        for (auto v : adjacent_vertices_range(u, g)) {
            out->set(g[v].index);
        }
    }
}

typename allocator<T>::dynamic_bitset allocator<T>::free_memory(const dynamic_bitset & memfree,
	                                                        dynamic_bitset && mask)
{
	assert(memfree.size() == mask.size());
	assert(memfree.count() + mask.count() <= memfree.size());
	auto res = memfree | mask;
#	if DEBUG_SMA_TRACE_BITSET
	std::cout << "a=memfree: " << memfree << std::endl;
	std::cout << "b=   mask: " << mask << std::endl;
	std::cout << "r=  a | b: " << res << std::endl;
#	endif
	assert(memfree.count() + mask.count() == res.count());
	return res;
}

bool 
compare_complete_partitions::operator()(const dynamic_bitset<>& p1,
					const dynamic_bitset<>& p2) const
{
  assert(p1.size() == p2.size());

  for(int i=0;i<p1.size();i++) {
    if (p2[i] and not p1[i])
      return true;
    if (p1[i] and not p2[i])
      return false;
  }
  return false;
}

		/// \brief Marks the specified arc as being used.
		void use(const Tilewire& inTilewire1, const Tilewire& inTilewire2) {
			// extract the tile indexes
			TileIndex tileIndex1 = inTilewire1.getTileIndex();
			TileIndex tileIndex2 = inTilewire2.getTileIndex();
			// ensure that these tilewires belong to the same tile
			/// \todo Throw a meaningful exception.
			if(tileIndex1 != tileIndex2) throw InvalidArcException(Arc(inTilewire1, inTilewire2));

			// make sure we have a bitset for this tile
			dynamic_bitset* bitset = mBitsets[tileIndex1];
			if(bitset == 0) {
				// determine how many arcs are in this tile
				const TileInfo& tileInfo = mTiles.getTileInfo(tileIndex1);
				TileTypeIndex type = tileInfo.getTypeIndex();
				const Array<const WireInfo>& wires = mTiles.getWireInfo(type);
				if(wires.getSize() == 0) return;
				const WireInfo& wireInfo = mTiles.getWireInfo(type, WireIndex(wires.getSize() - 1));
				// caution: we have to add the regular and irregular sink count from the last wire
				size_t size = wireInfo.getArcOffset() + wireInfo.getSinks().getSize() 
					+ wireInfo.getIrregularSinks().getSize() 
					+ wireInfo.getRoutethroughSinks().getSize()
					+ wireInfo.getTiedSinks().getSize();
				bitset = mBitsets[tileIndex1] = new dynamic_bitset(size);
				// track the statistics
				mTileUsageCount++;
				mBitCount += size;
			}

			// set the bit and mark the tile dirty
			bitset->set(getArcOffset(inTilewire1, inTilewire2));
			mTileDirty.set(tileIndex1, true);
		}

bool A_constant(alignment A1, alignment A2, const dynamic_bitset<>& ignore) {
  assert(A1.n_sequences() == A2.n_sequences());

  // equality holds if we have internal node sequences -- otherwise ignore is larger
  assert(A1.n_sequences() <= ignore.size());

  // convert to feature-number notation
  ublas::matrix<int> M1 = M(A1);
  ublas::matrix<int> M2 = M(A2);

  // lookup and cache the column each feature is in
  vector< vector< int> > column_indices = column_lookup(A2);

  //----- Check that the sequence lengths match ------//
  for(int i=0;i<M1.size2();i++) {
    if (ignore[i]) continue;

    if (A1.seqlength(i) != A2.seqlength(i))
      return false;
  }

  //----- Check that each homology in A1 is in A2 -----//
  for(int column=0; column<A1.length(); column++)
    for(int s1=0; s1 < A1.n_sequences(); s1++) {
      if (ignore[s1]) continue;
      for(int s2=s1+1; s2 < A1.n_sequences(); s2++) {
	if (ignore[s2]) continue;
	if (not A_match(M1,column,s1,s2,M2,column_indices))
	  return false;
      }
    }

  return true;
}

void StreamGenerator::setBitstreamBits(dynamic_bitset<>& bitStream,
                                       int num, size_t bitsetIndex, size_t numIndex) {

    unsigned int size = sizeof (unsigned int)*8;
    if (numIndex < size) {

        if (bitsetIndex < bitStream.size()) {
            bitStream[bitsetIndex] = (num >> numIndex) & 0x1;
            setBitstreamBits(bitStream, num, bitsetIndex + 1, numIndex + 1);
        }
    }

		/// \brief Marks all arcs as being unused, without releasing the bitset objects.
		/// \details This capability allows the tracer to track the wires that it has visited while 
		///		processing a particular net, and then to start again from scratch without incurring 
		///		allocation and construction overheads.
		void clear(void) {
			// iterate over all of the tiles
			size_t tileCount = mBitsets.getSize();
			for(TileIndex i; i < tileCount; i++) {
				// skip this tile if it isn't dirty
				if(!mTileDirty[i]) continue;
				// mark the tile clean
				mTileDirty.reset(i);
				// look up the bitset for this tile
				dynamic_bitset* bitset = mBitsets[i];
				// skip tiles without an associated bitset (should never happen for dirty tiles)
				if(bitset == 0) continue;
				// clear the entire bitset
				bitset->reset();
			}
		}

		/// \brief Marks the specified arc as being unused.
		void release(const Tilewire& inTilewire1, const Tilewire& inTilewire2) {
			// extract the tile indexes
			TileIndex tileIndex1 = inTilewire1.getTileIndex();
			TileIndex tileIndex2 = inTilewire2.getTileIndex();
			// ensure that these tilewires belong to the same tile
			/// \todo Throw a meaningful exception.
			if(tileIndex1 != tileIndex2) throw -1;

			// if there is no entry for the tile, the arc is already implicitly unused.
			dynamic_bitset* bitset = mBitsets[tileIndex1];
			if(bitset == 0) return;

			// otherwise clear the bit and mark the tile dirty
			bitset->set(getArcOffset(inTilewire1, inTilewire2), false);
			mTileDirty.set(tileIndex1, true);
		}

Partition::Partition(const vector<string>& n,const dynamic_bitset<>& g) 
  :names(n),group1(g),group2(~g)
{
  assert(n.size() == g.size());
  assert(not group1.intersects(group2));
}

	// functions
		/// \brief Size the wire usage according to the number of device tiles.
		void autosize(void) {
			// release any existing bitsets
			for(TileCount i; i < mBitsets.getSize(); i++) {
				if(mBitsets[i] != 0) { delete mBitsets[i]; mBitsets[i] = 0; }
				mTileDirty.reset(i);
			}
			// resize for the new dimensions
			TileCount tileCount = mTiles.getTileCount();
			mBitsets.setSize(tileCount);
			for(TileCount i; i < tileCount; i++) mBitsets[i] = 0;
			mTileDirty.resize(tileCount);
		}