// Call savePosition() on a reverse cursor without ever calling restorePosition().
    // May be useful to run this test under valgrind to verify there are no leaks.
    TEST( SortedDataInterface, SavePositionWithoutRestoreReversed ) {
        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface( false ) );

        {
            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
            ASSERT( sorted->isEmpty( opCtx.get() ) );
        }

        {
            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
            {
                WriteUnitOfWork uow( opCtx.get() );
                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc1, true ) );
                uow.commit();
            }
        }

        {
            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
            ASSERT_EQUALS( 1, sorted->numEntries( opCtx.get() ) );
        }

        {
            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), -1 ) );
            cursor->savePosition();
        }
    }

double get_statistics(const vector<int> & nodes, const vector<double> & scores, const int FLAG){
    double statistic = 0.0;
    const int size = nodes.size();

    if(FLAG == GD_STAT_MEAN){
        //compute average
        for(int i = 0; i < size; ++i){
            statistic += scores[nodes[i]];
        }

        statistic = statistic / double(size);
    }
    else if(FLAG == GD_STAT_STD){
        //compute standard deviation
        double mean = 0;
        for(int i = 0; i < size; ++i){
            mean += scores[nodes[i]];
        }
        mean = mean / double(size);

        double square_sum = 0;
        for(int i = 0; i < size; ++i){
            square_sum += pow((double)(scores[nodes[i]] - mean),2);
        }
        statistic = square_sum / double(size);

        statistic = sqrt(statistic);
    }
    else if(FLAG == GD_STAT_MED){
        //compute median - currently using builtin vector sort
        //Need to select sub-vector associated with nodes given in function call
        vector<double> sorted(size);
        for(int i = 0; i < size; ++i){
            sorted[i] = scores[nodes[i]];
        }

        sort(sorted.begin(), sorted.end());

        int middle = size / 2;
        if(size % 2 == 1){
            statistic = sorted[middle];
        }
        else {
            //Adjust downwards since we index from 0, not 1
            statistic = (sorted[middle] + sorted[middle - 1]) / 2;
        }
    }
    else if(FLAG == GD_STAT_COUNT){
        //Count number of non-negative scored vertices in bag.
        for(int i = 0; i < size; ++i){
            if(!(scores[nodes[i]] < 0)){
                statistic++;
            }
        }
    }
    else {
        fatal_error("Statistic must be one of GD_STAT_XXX from Util.h\n");
    }
    return statistic;
} // get_statistics

void MlSldaState::InitializeAssignments(bool random_init) {
  InitializeResponse();
  InitializeLength();

  LdawnState::InitializeAssignments(random_init);

  if (FLAGS_num_seed_docs > 0) {
    const gsl_vector* y = static_cast<lib_corpora::ReviewCorpus*>
      (corpus_.get())->train_ratings();
    boost::shared_ptr<gsl_permutation> sorted(gsl_permutation_alloc(y->size),
                                              gsl_permutation_free);
    boost::shared_ptr<gsl_permutation> rank(gsl_permutation_alloc(y->size),
                                            gsl_permutation_free);

    std::vector< std::vector<int> > num_seeds_used;
    num_seeds_used.resize(corpus_->num_languages());
    for (int ii = 0; ii < corpus_->num_languages(); ++ii) {
      num_seeds_used[ii].resize(num_topics_);
    }

    gsl_sort_vector_index(sorted.get(), y);
    gsl_permutation_inverse(rank.get(), sorted.get());

    // We add one for padding so we don't try to set a document to be equal to
    // the number of topics.
    double num_train = corpus_->num_train() + 1.0;
    int train_seen = 0;
    int num_docs = corpus_->num_docs();
    for (int dd = 0; dd < num_docs; ++dd) {
      MlSeqDoc* doc = corpus_->seq_doc(dd);
      int lang = doc->language();
      if (!corpus_->doc(dd)->is_test()) {
        // We don't assign to topic zero, so it can be stopwordy
        int val = (int) floor((num_topics_ - 1) *
                              rank->data[train_seen] / num_train) + 1;

        // Stop once we've used our limit of seed docs (too many leads to an
        // overfit initial state)
        if (num_seeds_used[lang][val] < FLAGS_num_seed_docs) {
          cout << "Initializing doc " << lang << " " << dd << " to " << val <<
            " score=" << truth_[dd] << endl;
          for (int jj = 0; jj < (int)topic_assignments_[dd].size(); ++jj) {
            int term = (*doc)[jj];
            const topicmod_projects_ldawn::WordPaths word =
              wordnet_->word(lang, term);
            int num_paths = word.size();
            if (num_paths > 0) {
              ChangePath(dd, jj, val, rand() % num_paths);
            } else {
              if (use_aux_topics())
                ChangeTopic(dd, jj, val);
            }
          }
          ++num_seeds_used[lang][val];
        }
        ++train_seen;
      }
    }
  }
}

void run(std::vector<uint32_t>* input, size_t k){
  std::vector<uint32_t> sorted(*input);  
  std::vector<uint32_t> copy(*input);  
  std::vector<uint32_t> tmp(input->size());  
  fast_sort<std::vector<uint32_t>,std::vector<uint32_t>>(&sorted, &tmp);
  size_t ind2 = findkth<std::vector<uint32_t>, IntCompare, false>(&copy, k);
  size_t ind1 = findkth<std::vector<uint32_t>, IntCompare, true>(&copy, k);
  // Verify it's the median
  if (sorted[k] != (*input)[ind2]) {
    print_array(input);
    print_array(&sorted);
    printf("findkth returned %lu\n", ind2); 
    printf("sorted[%lu]=%u but input[findkth(k=%lu)]=%u\n", k, sorted[k], k, (*input)[ind2]);
    PANIC("findkth (linear=false) returned wrong index\n");
  }
  if (sorted[k] != (*input)[ind1]) {
    print_array(input);
    print_array(&sorted);
    printf("findkth returned %lu\n", ind1); 
    printf("sorted[%lu]=%u but input[findkth(k=%lu)]=%u\n", k, sorted[k], k, (*input)[ind1]);
    PANIC("findkth (linear=true) returned wrong index\n");
  }
  // Verify we didn't mess with the array
  for (size_t i=0; i<input->size(); i++) {
    if ((*input)[i] != copy[i]) {
      print_array(input);
      print_array(&copy);
      PANIC("findkth modified array. Input array (first) != copy (second)")
    }
  }

void OptionParser::print_usage(OptionPrefix& root, FILE *fp) {
	static const char* blank29 = "                             "; // 29 spaces
	static const char* blank25 = blank29 + 4;                     // 25 spaces
	OStream OS(fp);

	std::set<OptionEntry*> sorted(root.begin(),root.end());

	for(std::set<OptionEntry*>::iterator i = sorted.begin(), e = sorted.end();
			i != e; ++i) {
		OptionEntry& oe = **i;
		OS << "    " << root.get_name();
		std::size_t name_len = root.size() + oe.print(OS);
		if (name_len < (25-1)) {
			OS << (blank25 + name_len);
		} else {
			OS << nl << blank29;
		}

		const char* c = oe.get_desc();
		for (std::size_t i = 29; *c != 0; c++, i++) {
			/* If we are at the end of the line, break it. */
			if (i == 80) {
				OS << nl << blank29;
				i = 29;
			}
			OS << *c;
		}
		OS << nl;
	}

}

    // Add multiple compound keys using a bulk builder.
    TEST( SortedDataInterface, BuilderAddMultipleCompoundKeys ) {
        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface( false ) );

        {
            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
            ASSERT( sorted->isEmpty( opCtx.get() ) );
        }

        {
            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
            scoped_ptr<SortedDataBuilderInterface> builder(
                    sorted->getBulkBuilder( opCtx.get(), true ) );

            ASSERT_OK( builder->addKey( compoundKey1a, loc1 ) );
            ASSERT_OK( builder->addKey( compoundKey1b, loc2 ) );
            ASSERT_OK( builder->addKey( compoundKey1c, loc4 ) );
            ASSERT_OK( builder->addKey( compoundKey2b, loc3 ) );
            ASSERT_OK( builder->addKey( compoundKey3a, loc5 ) );
            builder->commit( false );
        }

        {
            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
            ASSERT_EQUALS( 5, sorted->numEntries( opCtx.get() ) );
        }
    }

std::string Timer::Show() {
  std::string ret;

  if (Counters().empty()) return ret;

  auto const url = g_context->getRequestUrl(75);
  folly::format(&ret, "\nJIT timers for {}\n", url);

  auto const header = "{:<40} | {:>15} {:>15} {:>15}\n";
  auto const row    = "{:<40} | {:>15} {:>13,}us {:>13,}ns\n";
  folly::format(&ret, header, "name", "count", "total time", "average time");
  folly::format(&ret, "{:-^40}-+{:-^48}\n", "", "");

  std::map<std::string, Counter> sorted(s_counters->begin(), s_counters->end());
  for (auto const& pair : sorted) {
    auto& name = pair.first;
    auto& counter = pair.second;

    folly::format(&ret, row, name, counter.count, counter.total / 1000,
                  counter.mean());
  }

  ret += '\n';
  return ret;
}

// public, static
void Cvar::List( void ) {
	console.Print( PrintLevel::Normal, "Listing cvars...\n" );

	std::map<std::string, Cvar *> sorted( cvars.begin(), cvars.end() );
	std::vector<std::string> keyValues;
	keyValues.reserve( sorted.size() );

	Indent indent( 1 );
	size_t maxLen = 1u;
	for ( const auto &cvar : sorted ) {
		keyValues.push_back( String::Format( "%s = \"%s\"", cvar.first.c_str(), cvar.second->fullString.c_str() ) );
		const size_t len = strlen( keyValues.back().c_str() );
		if ( len > maxLen ) {
			maxLen = len;
		}
	}
	uint32_t i = 0;
	for ( const auto &cvar : sorted ) {
		console.Print( PrintLevel::Normal, "%-*s: %s\n",
			maxLen + 1,
			keyValues[i++].c_str(),
			cvar.second->description.c_str()
		);
	}
}

void NumMultinomialWRBInit(real *m, int l, int if_sorted, int **a_ptr,
                           real **p_ptr) {
  pair *tl;
  int i;
  real q;
  if (if_sorted) {
    tl = array2tuples(m, l);
  } else {
    tl = sorted(m, l, 1);
  }
  int f = 0;
  int r = l - 1;
  int *a = NumNewHugeIntVec(l);
  real *p = NumNewHugeVec(l);
  for (i = 0; i < l; i++) p[tl[i].key] = tl[i].val * l;
  while (1) {
    if (p[tl[f].key] > 1 && p[tl[r].key] < 1) {  // rear underflow
      q = 1 - p[tl[r].key];                      // underflow probability
      a[tl[r].key] = tl[f].key;                  // alias
      p[tl[f].key] -= q;                         // probability
      r--;
    } else if (p[tl[f].key] < 1 && p[tl[f + 1].key] > 1) {  // front underflow
      q = 1 - p[tl[f].key];
      a[tl[f].key] = tl[f + 1].key;
      p[tl[f + 1].key] -= q;
      f++;
    } else
      break;
  }
  free(tl);
  *p_ptr = p;
  *a_ptr = a;
  return;
}

// Collect regular file names recursively.
// Files found in 'exclude' are abandoned.
void collect(const string &path, vector<string> &files, set<string> &exclude) {
  struct dirent *entry;
  DIR *dp;
  if ((dp = opendir(path.c_str())) == NULL) {
    error("Util::fail open file: %s", path.c_str());
  }
  // TODO(billy): readdir_r should be thread safe to replace this
  while ((entry = readdir(dp))) {
    string name = string(entry->d_name);
    if (!name.length() || name[0] == '.')  // ignore hidden or special files
      continue;
    if (exclude.find(name) != exclude.end())
      continue;
    name = path+"/"+name;
    if (entry->d_type == DT_DIR) {
      collect(name, files, exclude);
    } else {
      files.push_back(name);
    }
  }
  set<string> sorted(files.begin(), files.end());
  files.clear();
  files.insert(files.begin(), sorted.begin(), sorted.end());

  closedir(dp);
  return;
}

void TableEditor::columnClicked(int col)
{
    if(!sorting()) return;
    //if(col==lastSortCol) asc=!asc; else lastSortCol=col,asc=TRUE;
    sortColumn(col,1,1);
	emit sorted();
}

bool
basic_counts_t::print_results() {
    std::cerr << TOOL_NAME << " results:\n";
    std::cerr << "Total counts:\n";
    std::cerr << std::setw(12) << total_instrs << " total (fetched) instructions\n";
    std::cerr << std::setw(12) << total_instrs_nofetch <<
        " total non-fetched instructions\n";
    std::cerr << std::setw(12) << total_prefetches << " total prefetches\n";
    std::cerr << std::setw(12) << total_loads << " total data loads\n";
    std::cerr << std::setw(12) << total_stores << " total data stores\n";
    std::cerr << std::setw(12) << total_threads << " total threads\n";
    std::cerr << std::setw(12) << total_sched_markers << " total scheduling markers\n";
    std::cerr << std::setw(12) << total_xfer_markers << " total transfer markers\n";
    std::cerr << std::setw(12) << total_other_markers << " total other markers\n";

    // Print the threads sorted by instrs.
    std::vector<std::pair<memref_tid_t, int_least64_t>> sorted(thread_instrs.begin(),
                                                               thread_instrs.end());
    std::sort(sorted.begin(), sorted.end(), cmp_val);
    for (const auto& keyvals : sorted) {
        memref_tid_t tid = keyvals.first;
        std::cerr << "Thread " << tid << " counts:\n";
        std::cerr << std::setw(12) << thread_instrs[tid] << " (fetched) instructions\n";
        std::cerr << std::setw(12) << thread_instrs_nofetch[tid] <<
            " non-fetched instructions\n";
        std::cerr << std::setw(12) << thread_prefetches[tid] << " prefetches\n";
        std::cerr << std::setw(12) << thread_loads[tid] << " data loads\n";
        std::cerr << std::setw(12) << thread_stores[tid] << " data stores\n";
        std::cerr << std::setw(12) << thread_sched_markers[tid] <<
            " scheduling markers\n";
        std::cerr << std::setw(12) << thread_xfer_markers[tid] << " transfer markers\n";
        std::cerr << std::setw(12) << thread_other_markers[tid] << " other markers\n";
    }
    return true;
}

void
DependencyResolverTest::simpleTest()
{
  DependencyResolver<int> resolver;

  int mat3 = 3;
  int mat1 = 1;
  int mat2 = 2;

  resolver.insertDependency(mat2, mat1);
  resolver.insertDependency(mat3, mat1);
  resolver.insertDependency(mat3, mat2);

  std::vector<int> sorted(3);
  sorted[0] = mat1;
  sorted[1] = mat2;
  sorted[2] = mat3;


  /*const std::vector<std::set<int> > & sets =*/
  resolver.getSortedValuesSets();

  std::sort(sorted.begin(), sorted.end(), resolver);
  CPPUNIT_ASSERT( sorted[0] == mat1);
  CPPUNIT_ASSERT( sorted[1] == mat2);
  CPPUNIT_ASSERT( sorted[2] == mat3);
}

int main(int argc, char **argv)
{
    srand(time(NULL));
    
    int numbers[SIZE];
    
    int i;
    for (i = 0; i < SIZE; ++i)
    {
        numbers[i] = rand() % (SIZE + 1); 
    }
    
    for (i = 0; i < SIZE; ++i)
    {
        printf("%d: %d\n", i, numbers[i]);
    }
    
    bubblesort (numbers, SIZE);
    
    assert( sorted(numbers, SIZE));
    
    return(0);
    

}

 int minDeletionSize(vector<string>& A) {
     int n = A.size();
     int result = 0;
     vector<bool> removed(A[0].size());
     int last = 0;
     for( int i = 0 ; i < n ; ++i ) A[i] = "a" + A[i];
     for( int i = 1 ; i < A[0].size() ; ++i ){
         bool b = false;
         bool allDif = true;
         for( int j = 1 ; j < n ; ++j ){
             if( A[j][last] == A[j - 1][last] && A[j][i] < A[j - 1][i] ){
                 b = true;
                 result++;
                 break;
             }
         }
         if( !b ){
             last = i;
         }else
             removed[i] = true;
         if( sorted(A, removed) ) break;
     }
     
     return result;
 }

	void Renderer::_renderCamera(Camera* cam)
	{
		RenderTarget* rt = cam->GetRenderTarget();
		if (!rt)
			return;
		cameraRendering = cam;

		rt->Bind();

		_setZWrite(true);
		_setZTest(true);
		glClearColor(0, 0, 0, 1);
		glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);

		std::vector<Renderable*> sorted(renderables.begin(), renderables.end());
		std::sort(sorted.begin(), sorted.end(), renderableCompare());
		std::vector<Renderable*>::iterator rIt;
		for (rIt = sorted.begin(); rIt != sorted.end(); rIt++)
		{
			(*rIt)->Update();
			//_render(cam, (*rIt));
			(*rIt)->Render(cam);
		}

		//Go through post-processes
		_renderPostProcess(rt->GetPostProcess());
	}

//Merge two vectors into one in sorted order
void merge(vector<int> *arr, int start, int mid, int end)
{
	vector<int> sorted((end - start) + 1);
	int sortPos = 0;
	int leftPos = start;
	int rightPos = mid+1;

	while(sortPos < sorted.size())
	{
		if(!leftPos > mid && !rightPos > end)
		{			
			if((*arr)[leftPos] < (*arr)[rightPos])
				sorted[sortPos++] = (*arr)[leftPos++];
			else
				sorted[sortPos++] = (*arr)[rightPos++];
		}
		else
		{
			if(!leftPos > mid)
				sorted[sortPos++] = (*arr)[leftPos++];
			else if(!rightPos > end)
				sorted[sortPos++] = (*arr)[rightPos++];
			else
				break;
		}
	}

	for(int i = 0; i < sorted.size(); i++)
	{
		(*arr)[start + i] = sorted[i];
	}
}

QStringList SessionChildItem::users() const
{
    SortedUserModel sorted(session()->prefixModes(), m_usermodel);
    QStringList names;
    for (int i = 0; i < sorted.rowCount(QModelIndex()); ++i)
        names += sorted.data(sorted.index(i, 0)).toString();
    return names;
}

int
HelpCmd::listCommands()
{
    for (const Command &cmd : sorted(Commands::list())) {
        out() << Cmd{cmd.getName()} << " -- " << cmd.getDescr() << '\n';
    }

    return EXIT_SUCCESS;
}

    // Call getDirection() on a reverse cursor and verify the result equals -1.
    TEST( SortedDataInterface, GetCursorDirectionReversed ) {
        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface( false ) );

        {
            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), -1 ) );
            ASSERT_EQUALS( -1, cursor->getDirection() );
        }
    }