int edjs_TreeNodeLocate(edjs_tree_node *root, edjs_tree_node *n, edjs_tree_node **found, int (*comparator)(edjs_tree_node *, edjs_tree_node *)) {
    int comp = 0;

    if (NULL == root) {
        *found = NULL;
        return 0;
    }

    comp = comparator(root, n); //strcmp (root->file_location, n->file_location);
    while((comp > 0 && NULL != root->left) || (comp < 0 && NULL != root->right)) {
        if (comp > 0) {
            //returns NULL when root->left is null
            //ret = edjs_module_insert_helper(root->left, n);
            if (NULL != root->left)
                root = root->left;
        }
        else if (comp < 0) {
            //returns NULL when root->right is null
            //ret = edjs_module_insert_helper(root->right, n);
            if (NULL != root->right)
                root = root->right;
        }
        comp = comparator(root, n); //strcmp (root->file_location, n->file_location);
    } 

    *found = root;
    return comp;
}

  static int partition(T* array, int pivot, int length, C comparator) {
    int left_index = -1;
    int right_index = length;
    T pivot_val = array[pivot];

    while (true) {
      do {
        left_index++;
      } while (comparator(array[left_index], pivot_val) == -1);
      do {
        right_index--;
      } while (comparator(array[right_index], pivot_val) == 1);

      if (left_index < right_index) {
        if (!idempotent || comparator(array[left_index], array[right_index]) != 0) {
          swap(array, left_index, right_index);
        }
      } else {
        return right_index;
      }
    }

    ShouldNotReachHere();
    return 0;
  }

// Assuming list has been sorted already, insert new_link to
// keep the list sorted according to the same comparison function.
// Comparison function is the same as used by sort, i.e. uses double
// indirection. Time is O(1) to add to beginning or end.
// Time is linear to add pre-sorted items to an empty list.
void ELIST2::add_sorted(int comparator(const void*, const void*),
                        ELIST2_LINK* new_link) {
  // Check for adding at the end.
  if (last == NULL || comparator(&last, &new_link) < 0) {
    if (last == NULL) {
      new_link->next = new_link;
      new_link->prev = new_link;
    } else {
      new_link->next = last->next;
      new_link->prev = last;
      last->next = new_link;
      new_link->next->prev = new_link;
    }
    last = new_link;
  } else {
    // Need to use an iterator.
    ELIST2_ITERATOR it(this);
    for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
      ELIST2_LINK* link = it.data();
      if (comparator(&link, &new_link) > 0)
        break;
    }
    if (it.cycled_list())
      it.add_to_end(new_link);
    else
      it.add_before_then_move(new_link);
  }
}

// Assuming list has been sorted already, insert new_link to
// keep the list sorted according to the same comparison function.
// Comparision function is the same as used by sort, i.e. uses double
// indirection. Time is O(1) to add to beginning or end.
// Time is linear to add pre-sorted items to an empty list.
// If unique is set to true and comparator() returns 0 (an entry with the
// same information as the one contained in new_link is already in the
// list) - new_link is not added to the list and the function returns the
// pointer to the identical entry that already exists in the list
// (otherwise the function returns new_link).
ELIST_LINK *ELIST::add_sorted_and_find(
    int comparator(const void*, const void*),
    bool unique, ELIST_LINK* new_link) {
  // Check for adding at the end.
  if (last == NULL || comparator(&last, &new_link) < 0) {
    if (last == NULL) {
      new_link->next = new_link;
    } else {
      new_link->next = last->next;
      last->next = new_link;
    }
    last = new_link;
  } else {
    // Need to use an iterator.
    ELIST_ITERATOR it(this);
    for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
      ELIST_LINK* link = it.data();
      int compare = comparator(&link, &new_link);
      if (compare > 0) {
        break;
      } else if (unique && compare == 0) {
        return link;
      }
    }
    if (it.cycled_list())
      it.add_to_end(new_link);
    else
      it.add_before_then_move(new_link);
  }
  return new_link;
}

    inline void add(RobustPoint const& incoming_point,
                    RobustPoint const& outgoing_point,
                    RobustPoint const& intersection_point,
                    int turn_index, int operation_index,
                    segment_identifier const& seg_id)
    {
        geometry::equal_to<RobustPoint> comparator;
        if (comparator(incoming_point, intersection_point))
        {
            return;
        }
        if (comparator(outgoing_point, intersection_point))
        {
            return;
        }

        AngleInfo info;
        info.seg_id = seg_id;
        info.turn_index = turn_index;
        info.operation_index = operation_index;
        info.intersection_point = intersection_point;

        {
            info.point = incoming_point;
            info.incoming = true;
            m_angles.push_back(info);
        }
        {
            info.point = outgoing_point;
            info.incoming = false;
            m_angles.push_back(info);
        }
    }

// Assuming list has been sorted already, insert new_data to
// keep the list sorted according to the same comparison function.
// Comparision function is the same as used by sort, i.e. uses double
// indirection. Time is O(1) to add to beginning or end.
// Time is linear to add pre-sorted items to an empty list.
// If unique, then don't add duplicate entries.
// Returns true if the element was added to the list.
bool CLIST::add_sorted(int comparator(const void*, const void*),
                       bool unique, void* new_data) {
  // Check for adding at the end.
  if (last == NULL || comparator(&last->data, &new_data) < 0) {
    CLIST_LINK* new_element = new CLIST_LINK;
    new_element->data = new_data;
    if (last == NULL) {
      new_element->next = new_element;
    } else {
      new_element->next = last->next;
      last->next = new_element;
    }
    last = new_element;
    return true;
  } else if (!unique || last->data != new_data) {
    // Need to use an iterator.
    CLIST_ITERATOR it(this);
    for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
      void* data = it.data();
      if (data == new_data && unique)
        return false;
      if (comparator(&data, &new_data) > 0)
        break;
    }
    if (it.cycled_list())
      it.add_to_end(new_data);
    else
      it.add_before_then_move(new_data);
    return true;
  }
  return false;
}

/**
 * Perform a merge of two sort partitions.
 *
 * @param sd         The sort descriptor.
 * @param comparator The comparator used to compare elements.
 * @param strings    The input strings.
 * @param working    A working array used for the merge operations.
 * @param left       The left bound for the merge.
 * @param mid        The midpoint for the merge.
 * @param right      The right bound of merge (inclusive).
 */
void StemClass::merge(SortData *sd, int (*comparator)(SortData *, RexxString *, RexxString *), RexxString **strings, RexxString **working, size_t left, size_t mid, size_t right)
{
    size_t leftEnd = mid - 1;
    // merging

    // if arrays are already sorted - no merge
    if (comparator(sd, strings[leftEnd], strings[mid]) <= 0) {
        return;
    }

    size_t leftCursor = left;
    size_t rightCursor = mid;
    size_t workingPosition = left;

    // use merging with exponential search
    do
    {
        RexxString *fromVal = strings[leftCursor];
        RexxString *rightVal = strings[rightCursor];
        if (comparator(sd, fromVal, rightVal) <= 0)
        {
            size_t leftInsertion = find(sd, comparator, strings, rightVal, -1, leftCursor + 1, leftEnd);
            size_t toCopy = leftInsertion - leftCursor + 1;
            arraycopy(strings, leftCursor, working, workingPosition, toCopy);
            workingPosition += toCopy;
            working[workingPosition++] = rightVal;
            // now we've added this
            rightCursor++;
            // step over the section we just copied...which might be
            // all of the remaining section
            leftCursor = leftInsertion + 1;
        }
        else
        {
            size_t rightInsertion = find(sd, comparator, strings, fromVal, 0, rightCursor + 1, right);
            size_t toCopy = rightInsertion - rightCursor + 1;
            arraycopy(strings, rightCursor, working, workingPosition, toCopy);
            workingPosition += toCopy;
            // insert the right-hand value
            working[workingPosition++] = fromVal;
            leftCursor++;
            rightCursor = rightInsertion + 1;
        }
    } while (right >= rightCursor && mid > leftCursor);

    // copy rest of array.  If we've not used up the left hand side,
    // we copy that.  Otherwise, there are items on the right side
    if (leftCursor < mid)
    {
        arraycopy(strings, leftCursor, working, workingPosition, mid - leftCursor);
    }
    else
    {
        arraycopy(strings, rightCursor, working, workingPosition, right - rightCursor + 1);
    }

    arraycopy(working, left, strings, left, right - left + 1);
}

static
void assert_heap_property(struct array* vals, unsigned int index, unsigned int max,
                          int(*comparator)(const void* l, const void* r)) {
    if (index < max) {
        assert(comparator(array_get(vals, index), array_get(vals, LEFT(index))));
        assert(comparator(array_get(vals, index), array_get(vals, RIGHT(index))));
        assert_heap_property(vals, LEFT(index), max, comparator);
        assert_heap_property(vals, RIGHT(index), max, comparator);
    }
}

//----------------------------------------------------------------------------------
// BVH node
BVHNode::BVHNode(const HitableListRef &aList, float aTime0, float aTime1)
{
	size_t n = aList->list().size();
	
	// pick an axis to sort along
	int axis = static_cast<int>(3.0f * randFloat());

	// sort along the chosen axis
	switch (axis)
	{
	case 0:	// x
		std::sort(aList->list().begin(), aList->list().end(), comparator(0));
		break;
	case 1: // y
		std::sort(aList->list().begin(), aList->list().end(), comparator(1));
		break;
	case 2: // z
		std::sort(aList->list().begin(), aList->list().end(), comparator(2));
		break;
	default:
		break;
	}

	if (n == 1) // one element
	{
		mLeft = mRight = aList->list().at(0);
	}
	if (n == 2) // two elements
	{
		mLeft = aList->list().at(0);
		mRight = aList->list().at(1);
	}
	else // split in half
	{
		size_t half_size = aList->list().size() / 2;
		std::vector<HitableRef> lowerHalf(aList->list().begin(), aList->list().begin() + half_size);
		std::vector<HitableRef> upperHalf(aList->list().begin() + half_size, aList->list().end());

		HitableListRef low = HitableList::create(lowerHalf);
		HitableListRef high = HitableList::create(upperHalf);

		mLeft = create(low, aTime0, aTime1);
		mRight = create(high, aTime0, aTime1);
	}

	AABB boxLeft;
	AABB boxRight;
	if (!mLeft->boundingBox(aTime0, aTime1, boxLeft) || !mRight->boundingBox(aTime0, aTime1, boxRight))
	{
		std::cerr << "No bounding box in BVH node constructor." << std::endl;
	}
	mBox = enclosingBox(boxLeft, boxRight);
}

void *mybsearch(const void *key, const  void *base, size_t num, size_t size,
	int (*comparator) (const void *, const void *))
{
    if (comparator(base, base + (num-1)*size) > 1)
	return 0;
    int mid = (num-1)/2;
    if (comparator(base+mid*size, key) > 0)
	return bsearch(key, base,              mid-1,      size, comparator);
    if (comparator(base+mid*size, key) < 0)
	return bsearch(key, base+(mid+1)*size, size-mid+1, size, comparator);
    return (void *) base+mid;
}

    void DocumentSourceSort::populate() {
        /* make sure we've got a sort key */
        verify(vSortKey.size());

        /* track and warn about how much physical memory has been used */
        DocMemMonitor dmm(this);

        /* pull everything from the underlying source */
        for(bool hasNext = !pSource->eof(); hasNext;
            hasNext = pSource->advance()) {
            intrusive_ptr<Document> pDocument(pSource->getCurrent());
            documents.push_back(pDocument);

            dmm.addToTotal(pDocument->getApproximateSize());
        }

        /* sort the list */
        Comparator comparator(this);
        sort(documents.begin(), documents.end(), comparator);

        /* start the sort iterator */
        docIterator = documents.begin();

        if (docIterator != documents.end())
            pCurrent = *docIterator;
        populated = true;
    }

inline void add_incoming_and_outgoing_angles(
                RobustPoint const& intersection_point, // rescaled
                Turn const& turn,
                Pieces const& pieces, // using rescaled offsets of it
                int operation_index,
                segment_identifier seg_id,
                Info& info)
{
    segment_identifier real_seg_id = seg_id;
    geometry::equal_to<RobustPoint> comparator;

    // Move backward and forward
    RobustPoint direction_points[2];
    for (int i = 0; i < 2; i++)
    {
        int index = turn.operations[operation_index].index_in_robust_ring;
        int piece_index = turn.operations[operation_index].piece_index;
        while(comparator(pieces[piece_index].robust_ring[index], intersection_point))
        {
            move_index(pieces, index, piece_index, i == 0 ? -1 : 1);
        }
        direction_points[i] = pieces[piece_index].robust_ring[index];
    }

    info.add(direction_points[0], direction_points[1], intersection_point,
        turn.turn_index, operation_index, real_seg_id);
}

    inline bool on_offsetted(Point const& point, Piece const& piece) const
    {
        typedef typename strategy::side::services::default_strategy
            <
                typename cs_tag<Point>::type
            >::type side_strategy;
        geometry::equal_to<Point> comparator;

        for (int i = 1; i < piece.offsetted_count; i++)
        {
            Point const& previous = piece.robust_ring[i - 1];
            Point const& current = piece.robust_ring[i];

            // The robust ring contains duplicates, avoid applying side on them (will be 0)
            if (! comparator(previous, current))
            {
                int const side = side_strategy::apply(previous, current, point);
                if (side == 0)
                {
                    // Collinear, check if projection falls on it
                    if (projection_on_segment(point, previous, current))
                    {
                        return true;
                    }
                }
            }
        }
        return false;
    }

void test_with_ax(std::string const& wkt,
        std::string const& expected,
        T const& adt,
        T const& xdt)
{
    typedef typename bg::point_type<Geometry>::type point_type;
    typedef bg::strategy::distance::detail::projected_point_ax<> ax_type;
    typedef typename bg::strategy::distance::services::return_type
    <
        bg::strategy::distance::detail::projected_point_ax<>,
        point_type,
        point_type
    >::type return_type;

    typedef bg::strategy::distance::detail::projected_point_ax_less
    <
        return_type
    > comparator_type;

    typedef bg::strategy::simplify::detail::douglas_peucker
    <
        point_type,
        bg::strategy::distance::detail::projected_point_ax<>,
        comparator_type
    > dp_ax;

    return_type max_distance(adt, xdt);
    comparator_type comparator(max_distance);
    dp_ax strategy(comparator);

    test_geometry<Geometry>(wkt, expected, max_distance, strategy);
}

    static inline analyse_result apply(Turn const& turn, Piece const& piece)
    {
        typedef typename Turn::robust_point_type point_type;
        analyse_result code = check_helper_segments(turn, piece);
        if (code != analyse_continue)
        {
            return code;
        }

        geometry::equal_to<point_type> comparator;

        if (piece.offsetted_count > 8)
        {
            // If the offset contains some points and is monotonic, we try
            // to avoid walking all points linearly.
            // We try it only once.
            if (piece.is_monotonic_increasing[0])
            {
                code = check_monotonic(turn, piece, geometry::less<point_type, 0>());
                if (code != analyse_continue) return code;
            }
            else if (piece.is_monotonic_increasing[1])
            {
                code = check_monotonic(turn, piece, geometry::less<point_type, 1>());
                if (code != analyse_continue) return code;
            }
            else if (piece.is_monotonic_decreasing[0])
            {
                code = check_monotonic(turn, piece, geometry::greater<point_type, 0>());
                if (code != analyse_continue) return code;
            }
            else if (piece.is_monotonic_decreasing[1])
            {
                code = check_monotonic(turn, piece, geometry::greater<point_type, 1>());
                if (code != analyse_continue) return code;
            }
        }

        // It is small or not monotonic, walk linearly through offset
        // TODO: this will be combined with winding strategy

        for (int i = 1; i < piece.offsetted_count; i++)
        {
            point_type const& previous = piece.robust_ring[i - 1];
            point_type const& current = piece.robust_ring[i];

            // The robust ring can contain duplicates
            // (on which any side or side-value would return 0)
            if (! comparator(previous, current))
            {
                code = check_segment(previous, current, turn, false);
                if (code != analyse_continue)
                {
                    return code;
                }
            }
        }

        return analyse_unknown;
    }

int main(int argc, char *argv[])
{
	std::map<std::string, std::string>	aoptions;
	const int param = parse_options(argc, argv, aoptions);

	if (settings::REF_VIDEO == "")
	{
		std::cerr << "[ERROR] Reference video not specified" << std::endl;
		std::cerr << std::endl;
		print_help();
	}

	std::string output = settings::OUTPUT;
	if(settings::OUTPUT == ""){
		output = "result.json";
	}

	Qpsnr comparator(output, settings::REF_VIDEO.c_str(), settings::VIDEO_SIZE_W, settings::VIDEO_SIZE_H );

	for(int i = param; i < argc; ++i)
	{
		comparator.addVideo( argv[i] );
	}

	// print some infos
	//LOG_INFO << "Skip frames: " << ((settings::SKIP_FRAMES > 0) ? settings::SKIP_FRAMES : 0) << std::endl;
	//LOG_INFO << "Max frames: " << ((settings::MAX_FRAMES > 0) ? settings::MAX_FRAMES : 0) << std::endl;
	// create the stats analyzer (like the psnr)
	LOG_INFO << "Analyzer set: " << settings::ANALYZER << std::endl;
	comparator.initAnalyser( settings::ANALYZER.c_str(), aoptions );
		
	comparator.process();
}

void *fbt_partition(void *begin, size_t num, size_t pivot, size_t size, int (*comparator)(const void *, const void *)) {
  /* Move pivot to begin of array */
  fbt_swap_mem(begin, (char *)begin + (size * pivot), size);
  
  void *insert_pos = (char *)begin + size;
  size_t cur = 1;
  
  /* Iterate over all elements and swap elements smaller than the pivot to the
   * left side */
  while (cur < num) {
    void *cur_ptr = (char *)begin + cur * size;
    
    if (comparator(cur_ptr, begin) < 0) {
      fbt_swap_mem(cur_ptr, insert_pos, size);
      insert_pos = (char *)insert_pos + size;
    }
    
    cur += 1;
  }
  
  /* Swap back pivot */
  fbt_swap_mem(begin, (char *)insert_pos - size, size);
  
  return (char *)insert_pos - size;
}

//extra vector
vector<Interval> merge2(vector<Interval>& intervals) 
{
    if (0 == intervals.size())
    {
        return intervals;
    }

    sort(intervals.begin(), intervals.end(), comparator());
    
    vector<Interval>ret;
          
    for ( int i = 0; i < intervals.size(); i++)
    {
        if ( ret.empty() || ret.back().end < intervals[i].start)
        {
            ret.push_back(intervals[i]);
        }
        else
        {
            ret.back().end = max(ret.back().end, intervals[i].end);
        }
        
    }
    return ret;
}

void NodeActionsExecutor::findActionNodes(Node& inNodeToAnalyze, 
                                          std::set<NodeAction*>& outActions)
{
   ActionsStorage::iterator it;
   Node* analyzedNode = &inNodeToAnalyze;

   bool foundActionNode = false;
   while ((analyzedNode != NULL) && (foundActionNode == false))
   {
      it = std::find_if( m_actions.begin(), m_actions.end(), comparator(*analyzedNode) );
      if (it != m_actions.end())
      {
         outActions.insert(it->second);
         foundActionNode = true;
      }

      if (analyzedNode->hasParentNode())
      {
         analyzedNode = analyzedNode->getParentNode();
      }
      else
      {
         analyzedNode = NULL;
      }
   }
}

GSList *
g_slist_agregate(GSList * list, GCompareFunc comparator)
{
	GSList *resL2 = NULL;	/*a list of lists of chunk_info_t */
	GSList *sorted = NULL;	/*a list of chunk_info_t */
	GSList *cursor1 = NULL;
	GSList *last_agregate = NULL;

	if (!list)
		return NULL;

	sorted = g_slist_copy(list);
	if (!sorted)
		return NULL;
	sorted = g_slist_sort(sorted, comparator);
	if (!sorted)
		return NULL;

	for (cursor1 = sorted; cursor1; cursor1 = cursor1->next) {
		if (!cursor1->data)
			continue;
		if (last_agregate && 0 > comparator(last_agregate->data, cursor1->data)) {
			resL2 = g_slist_prepend(resL2, last_agregate);
			last_agregate = NULL;
		}
		last_agregate = g_slist_prepend(last_agregate, cursor1->data);
	}

	if (last_agregate)
		resL2 = g_slist_prepend(resL2, last_agregate);

	g_slist_free (sorted);
	return g_slist_reverse(resL2);
}