Skip to content

@cire3791 /Main.cpp
Last active

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Evenly distribute new elements between existing queues in a vector.
#include <vector>
#include <queue>
#include <iostream>
#include <random>
#include <string>
#include "QueueManip.h"
void printSizes(const vector_type & v)
{
for ( unsigned i=0; i<v.size(); ++i )
std::cout << i << ": " << v[i].size() << '\n' ;
}
vector_type generateJagged(unsigned maxElements=10, unsigned minLength=0, unsigned maxLength=25)
{
static std::mt19937 gen((std::random_device()())) ;
std::uniform_int_distribution<unsigned> size_rng(minLength, maxLength) ;
vector_type v(maxElements) ;
for ( auto & element : v )
{
unsigned queueSize = size_rng(gen) ;
for ( unsigned i=0; i< queueSize; ++i )
element.push(int()) ;
}
return v ;
}
std::vector<int> generateElementsToAdd(unsigned elements)
{
return std::vector<int>(elements) ;
}
int main()
{
char const * prompt = "Add how many elements? " ;
unsigned input ;
while ( std::cout << prompt && std::cin >> input )
{
auto v = generateJagged() ;
printSizes(v) ;
std::cout << '\n' ;
addElements(v, generateElementsToAdd(input)) ;
printSizes(v) ;
std::cout << '\n' ;
}
}
#include <functional>
#include <queue>
#include <vector>
#include "QueueManip.h"
namespace {
typedef std::reference_wrapper<std::queue<int>> queue_ref_type ;
std::vector<queue_ref_type> bySize( vector_type& v )
{
std::vector<queue_ref_type> index ;
for ( auto & element : v )
index.emplace_back(element) ;
std::sort(index.begin(), index.end(),
[](queue_ref_type a, queue_ref_type b)
{ return a.get().size() < b.get().size() ; }) ;
return index ;
}
unsigned calculateMinimumSize( const std::vector<queue_ref_type>& queues, unsigned numToAdd )
{
unsigned index = 1 ;
unsigned free = 1 ;
unsigned occupied = queues.front().get().size() ;
unsigned prevSize = occupied ;
while ( index != queues.size() && free < numToAdd )
{
const unsigned curSize = queues[index].get().size() ;
occupied += curSize ;
free += (curSize-prevSize) * index ;
prevSize = curSize ;
++index ;
}
return (occupied + numToAdd) / index ;
}
}
void addElements( vector_type& container, const std::vector<int>& elements )
{
if ( container.size() == 0 )
return ;
auto indexed = bySize(container) ;
auto minimumSize = calculateMinimumSize(indexed, elements.size()) ;
unsigned added = 0 ;
auto it = indexed.begin() ;
while ( it != indexed.end() && added < elements.size() )
{
std::queue<int>& queue = *it ;
if ( queue.size() < minimumSize )
queue.push(elements[added++]) ;
else
++it ;
}
// (indexed.size() > elements.size()-added) should be true here.
it = indexed.begin();
while ( added < elements.size() )
{
std::queue<int>& queue = *it++ ;
queue.push(elements[added++]) ;
}
}
#ifndef EMS_QUEUEMANIP_H_
#define EMS_QUEUEMANIP_H_
typedef std::vector<std::queue<int>> vector_type ;
void addElements( vector_type& container, const std::vector<int>& elements );
#endif
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.