void ibis::array_t<T>::sort(array_t<uint32_t>& ind) const {
    const size_t na = size();
    size_t ni = ind.size();
    bool keepind = (ni > 0);
    for (size_t j = 0; keepind && j < ni; ++ j)
	keepind = (ind[j] < na);
    if (! keepind) { // initalize ind to [0:na-1]
	ni = na;
	ind.resize(na);
	for (size_t i = 0; i < na; ++i)
	    ind[i] = i;
    }
    if (ni < 2) { // no need to sort
	return;
    }
    if (ni > 0xFFFFFFFFUL) { // do not support arrays of this size?
	ind.clear();
	return;
    }

    // call qsort to do the actual work
    qsort(ind, 0, ni);
#if DEBUG+0 > 1 || _DEBUG+0 > 1
    ibis::util::logger lg(4);
    lg.buffer() << "DEBUG -- sort(ind[" << ni << "])";
    for (size_t i = 0; i < ni; ++i)
	lg.buffer() << "\nind[" << i << "]=" << ind[i] << "\t"
		    << m_begin[ind[i]];
#endif
} // sort

void ibis::array_t<T>::stableSort(array_t<uint32_t>& ind) const {
    if (size() > 2) {
	if (size() > 0xFFFFFFFFUL) {
	    ind.clear();
	    return;
	}

	array_t<T> tmp1, tmp2;
	array_t<uint32_t> itmp;
	tmp1.deepCopy(*this);
	ibis::array_t<T>::stableSort(tmp1, ind, tmp2, itmp);
    }
    else if (size() == 2) {
	ind.resize(2);
	if (m_begin[1] < m_begin[0]) {
	    const T tmp = m_begin[1];
	    m_begin[1] = m_begin[0];
	    m_begin[0] = tmp;
	    ind[0] = 1;
	    ind[1] = 0;
	}
	else {
	    ind[0] = 0;
	    ind[1] = 1;
	}
    }
    else if (size() == 1) {
	ind.resize(1);
	ind[0] = 0;
    }
    else {
	ind.clear();
    }
} // stableSort

/// Write the buffer out directly.
///
/// @ntoe This function is intended to be used by dictionary::write and
/// must satisfy the following conditions.  There must be only one buffer,
/// and the raw_ must be ordered in that buffer.  Under these conditions,
/// we can write the buffer using a single sequential write operations,
/// which should reduce the I/O time.  The easiest way to satisfy these
/// conditions is to invoke mergeBuffers.
int ibis::dictionary::writeBuffer(FILE *fptr, uint32_t nkeys,
                                  array_t<uint64_t> &pos,
                                  array_t<uint32_t> &qos) const {
    size_t ierr;
    pos[0] = 24 + 8 * (nkeys+1) + 4 * nkeys;
    for (unsigned j = 0; j < nkeys; ++ j)
        pos[j+1] += pos[j];

    ierr = fwrite(pos.begin(), sizeof(uint64_t), nkeys+1, fptr);
    LOGGER(ierr != (int)(nkeys+1) && ibis::gVerbose > 1)
        << "Warning -- dictionary::writeBuffer failed to write the offsets, "
        "expected fwrite to return " << nkeys+1 << ", but got " << ierr;

    ierr = fwrite(qos.begin(), sizeof(uint32_t), nkeys, fptr);
    LOGGER(ierr != (int)(nkeys) && ibis::gVerbose > 1)
        << "Warning -- dictionary::writeBuffer failed to write the keys, "
        "expected fwrite to return " << nkeys << ", but got " << ierr;

    const char *buff = buffer_[0];
    size_t sz = pos[nkeys] - pos[0];
    while (sz > 0) {  // a large buffer may need multuple fwrite calls
        ierr = fwrite(buff, 1, sz, fptr);
        if (ierr > 0U && ierr <= sz) {
            buff += ierr;
            sz -= ierr;
        }
        else {
            LOGGER(ibis::gVerbose > 1)
                << "Warning -- dictionary::writeBuffer failed to write the "
                "buffer, fwrite retruned 0";
            return -6;
        }
    }
    return 0;
} // ibis::dictionary::writeBuffer

    explicit const_array_ref_t( const array_t& array) : array_( const_cast<array_t*>( &array))
    {
        // preconditions
        assert( core::type_traits<value_type>::type() == array.type());

        if( core::type_traits<value_type>::type() != array.type())
            throw core::bad_type_cast( array.type(), core::type_traits<value_type>::type());
    }

array_t permutate(array_t &p, array_t &d) {
	array_t r;
	r.reserve(d.size());
	
	for (unsigned i = 0; i < p.size(); i += 1) {
		r.push_back(d[p[i]-1]);
	}
	
	return r;
}

 double Eval(double h, const array_t &a)
 {
     assert(a.size()>0);
     double v = S0 - a[1] * h;
     if(a.size()>1)
     {
         v -= a[2] * h*h;
     }
     return v;
 }

void replace_placeholder(array_t& expression, name_t name, const any_regular_t& value)
{
    for (std::size_t i = 0; i < expression.size(); ++i) {
        name_t element_name;
        if (expression[i].cast<name_t>(element_name) && element_name == name) {
            expression[i] = value;
            expression.erase(expression.begin() + i + 1);
        }
    }
}

//  argument_list = expression { "," expression }.
bool expression_parser::is_argument_list(array_t& expression_stack) {
    if (!is_expression(expression_stack))
        return false;

    std::size_t count = 1;

    while (is_token(comma_k)) {
        require_expression(expression_stack);
        ++count;
    }

    expression_stack.push_back(any_regular_t(double(count)));
    expression_stack.push_back(any_regular_t(array_k));

    return true;
}

	void dump(array_t path)
	{
		std::cout << "== length " << path.size() << std::endl;
		for (auto& item : path){
			std::cout << "->" << dict[item->word_id];
		}
		std::cout << std::endl;
	}

//  named_argument_list = named_argument { "," named_argument }.
bool expression_parser::is_named_argument_list(array_t& expression_stack) {
    if (!is_named_argument(expression_stack))
        return false;

    std::size_t count = 1;

    while (is_token(comma_k)) {
        if (!is_named_argument(expression_stack))
            throw_exception("Named argument required.");

        ++count;
    }

    expression_stack.push_back(any_regular_t(double(count)));
    expression_stack.push_back(any_regular_t(dictionary_k));

    return true;
}

    /** Indexing operator. */
    inline value_type operator()(uint8_t x, uint8_t y, uint8_t z) const
    {
        assert(size() == volume());
        assert(x < length());
        assert(y < length());
        assert(z < length());

        return array_t::operator[](x + y * length() + z * area());
    }

void ibis::array_t<T>::deepCopy(const array_t<T>& rhs) {
    if (rhs.actual != 0 && rhs.m_begin != 0 && rhs.m_end != 0) {
	if (actual != 0 && actual->inUse() < 2U &&
	    actual->end() >= rhs.size() * sizeof(T) + actual->begin()) {
	    // already has enough memory allocated, stay with it
	    const size_t n = rhs.size();
	    m_begin = (T*)(actual->begin());
	    m_end = m_begin + n;
	    for (size_t i = 0; i < n; ++ i)
		m_begin[i] = rhs[i];
	}
	else {
	    array_t<T> tmp(rhs.size()); // allocate memory
	    for (size_t i = 0; i < rhs.size(); ++ i)
		tmp[i] = rhs[i];
	    swap(tmp);
	}
    }
} // ibis::array_t<T>::deepCopy

bool expression_parser::is_postfix_expression(array_t& expression_stack) {
    if (!is_primary_expression(expression_stack))
        return false;

    while (true) {
        if (is_token(open_bracket_k)) {
            require_expression(expression_stack);
            require_token(close_bracket_k);
        } else if (is_token(dot_k)) {
            any_regular_t result;
            require_token(identifier_k, result);
            expression_stack.push_back(result);
        } else
            break;

        expression_stack.push_back(any_regular_t(index_k));
    }

    return true;
}

//  variable_or_function = identifier ["(" [argument_expression_list] ")"].
bool expression_parser::is_variable_or_function(array_t& expression_stack) {
    any_regular_t result;

    if (!is_token(identifier_k, result))
        return false;

    if (is_token(open_parenthesis_k)) {
        // If there are no parameters then set the parameters to an empty array.
        if (!is_argument_expression_list(expression_stack))
            expression_stack.push_back(any_regular_t(adobe::array_t()));

        require_token(close_parenthesis_k);
        expression_stack.push_back(result);
        expression_stack.push_back(any_regular_t(function_k));
    } else {
        expression_stack.push_back(result);
        expression_stack.push_back(any_regular_t(variable_k));
    }

    return true;
}

amqp_field_value_t TableValueImpl::generate_field_value::operator()(const array_t &value) const
{
  amqp_field_value_t v;
  v.kind = AMQP_FIELD_KIND_ARRAY;
  v.value.array.num_entries = value.size();
  v.value.array.entries = (amqp_field_value_t*)amqp_pool_alloc(&pool,
                                                               sizeof(amqp_field_value_t)*value.size());
  if (NULL == v.value.array.entries)
  {
    throw std::bad_alloc();
  }
  
  amqp_field_value_t *output_iterator = v.value.array.entries;
  for (array_t::const_iterator it = value.begin();
       it != value.end(); ++it, ++output_iterator)
  {
    *output_iterator = boost::apply_visitor(generate_field_value(pool),
                                            it->m_impl->m_value);
  }
  return v;
}

/*
 * Find an object in the array
 * @parm1 comparable_t: the object
 * @parm2 array_t: the array
 * @return int:
 *      true if the comparable item is in the array
 *      false if the comparable item is not in the array
 */
int locate(comparable_t obj, array_t arr)
{
	int low;
	int mid;
	int high;

	low = 0;
	high = arr->get_count(arr)-1;
	
	while (low <= high) {
		mid = low + (high - low) / 2;
		if (!(arr->compare(obj, arr->lookup(mid, arr))))
			return 1;
		else if (arr->compare(obj, arr->lookup(mid, arr)) < 0)
			high = mid - 1;
		else
			low = mid + 1;
	}

	return 0;
}

bool sorted (array_t &v) {
	int prev = v[0];
	
	for (unsigned i = 1; i < v.size(); i += 1) {
		if (v[i] < prev)
			return false;
		
		prev = v[i];
	}
	
	return true;
}

	void find_path(const std::string& from, const std::string& to)
	{
		auto first = std::find_if(words.begin(), words.end(), [&from](const std::shared_ptr<Item>& item)->bool { return dict[item->word_id] == from; });
		if (first == words.end()) {
			std::cout << "missing " << from << std::endl;
			return;
		}

		auto second = std::find_if(words.begin(), words.end(), [&to](const std::shared_ptr<Item>& item)->bool { return dict[item->word_id] == to; });
		if (second == words.end()){
			std::cout << "missing " << to << std::endl;
			return;
		}


		auto l = *first;
		auto r = *second;

		visited_t visited;
		array_t path;
		std::size_t lenmax = 11;
		find_item(lenmax, l, r, path, visited);

		std::cout << "hit_reached " << hit_reached << std::endl;
	}

	void find_item(std::size_t& lenmax, const array_t::value_type& from, const array_t::value_type& to, array_t& path = array_t(), visited_t& visited = visited_t())
	{
		if (path.size() > lenmax)
			return;

		path.push_back(from);
		if (from->word_id == to->word_id)
		{
			lenmax = path.size() - 2;
			dump(path);
			return;
		}

		visited.insert(std::make_pair(from->word_id, 1));

		for (auto& s : from->similar) {

			auto hit = visited.find(s->word_id);
			if (hit != visited.end() && hit->second > 12535000) {
				hit_reached++;
				continue;
			}

			if (hit != visited.end())
				hit->second++;

			// исключить зацикливание
			if (std::find(path.begin(), path.end(), s) != path.end())
				continue;

			array_t another;
			another = path;
			find_item(lenmax, s, to, another, visited);
		}
	}

    bool test_expression(const lexer_t& lexer,
                         const expression_parser_rules_t& parser_rules,
                         array_t& new_parsed_expression,
                         adobe_parser_t adobe_parse,
                         const std::string& expression)
    {
        std::cout << "expression: \"" << expression << "\"\n";
        array_t original_parsed_expression;
        bool original_parse_failed = false;
        try {
            original_parsed_expression = adobe_parse(expression);
        } catch (const stream_error_t&) {
            original_parse_failed = true;
        }
        if (original_parse_failed)
            std::cout << "original: <parse failure>\n";
        else
            std::cout << "original: " << original_parsed_expression << "\n";
        using boost::spirit::qi::phrase_parse;
        text_iterator_t it(expression.begin());
        detail::s_text_it = &it;
        detail::s_begin = it;
        detail::s_end = text_iterator_t(expression.end());
        detail::s_filename = "test_expression";
        token_iterator_t iter = lexer.begin(it, detail::s_end);
        token_iterator_t end = lexer.end();
        bool new_parse_failed =
            !phrase_parse(iter,
                          end,
                          parser_rules.expression(boost::phoenix::ref(new_parsed_expression)),
                          boost::spirit::qi::in_state("WS")[lexer.self]);
        if (new_parse_failed)
            std::cout << "new:      <parse failure>\n";
        else
            std::cout << "new:      " << new_parsed_expression << "\n";
        bool pass =
            original_parse_failed && new_parse_failed ||
            new_parsed_expression == original_parsed_expression;
        std::cout << (pass ? "PASS" : "FAIL") << "\n";

        if (!pass) {
            std::cout << "original (verbose):\n";
            verbose_dump(original_parsed_expression);
            std::cout << "new (verbose):\n";
            verbose_dump(new_parsed_expression);
        }

        std::cout << "\n";
        new_parsed_expression.clear();

        return pass;
    }