system_cmds-671.10.3.tar.gz

[apple/system_cmds.git] / CPPUtil / UtilTRange.hpp

//
//  UtilTRange.hpp
//  CPPUtil
//
//  Created by James McIlree on 4/14/13.
//  Copyright (c) 2013 Apple. All rights reserved.
//

#ifndef CPPUtil_UtilTRange_hpp
#define CPPUtil_UtilTRange_hpp

template <typename T>
class TRange {
    protected:
	T	_location;
	T	_length;

    public:
	TRange() : _location(0), _length(0) {}
	TRange(T location, T length) : _location(location), _length(length) {
		DEBUG_ONLY(validate());
	};

	bool operator==(const TRange &rhs) const 		{ return this->_location == rhs.location() && this->_length == rhs.length(); }

	bool operator!=(const TRange &rhs) const 		{ return !(*this == rhs); }

	bool operator<(const TRange& rhs) const			{ return this->_location < rhs.location(); }
	bool operator<(const TRange* rhs) const			{ return this->_location < rhs->location(); }

	const T location() const				{ return _location; }
	const T length() const					{ return _length; }
	const T max() const					{ return _location + _length; }

	void set_location(T location)				{ _location = location; DEBUG_ONLY(validate()); }
	void set_length(T length)				{ _length = length; DEBUG_ONLY(validate()); }
	void set_max(T max)					{ ASSERT(max >= _location, "Sanity"); _length = max - _location; }
	
	const bool contains(const TRange& other) const		{ return (other.location() >= location()) && (other.max() <= max()); }
	const bool contains(const T loc) const			{ return loc - _location < _length; } // Assumes unsigned!

	const bool intersects(const TRange& o) const		{ return this->location() < o.max() && o.location() < this->max(); }

	// "union" is a keyword :-(
	TRange union_range(const TRange& other) const {
		T maxend = (this->max() > other.max()) ? this->max() : other.max();
		T minloc = this->location() < other.location() ? this->location() : other.location();
		return TRange(minloc, maxend - minloc);
	}

	TRange intersection_range(const TRange& other) const {
		if (this->intersects(other)) {
			auto intersection_start = std::max(_location, other.location());
			auto intersection_end = std::min(max(), other.max());
			return TRange(intersection_start, intersection_end - intersection_start);
		}

		return TRange(T(0),T(0));
	}

	void validate() const					{ ASSERT((_location + _length >= _location) /*|| (_location + 1 == 0)*/, "range must not wrap"); }
};

template <typename TRANGE>
bool is_trange_vector_sorted_and_non_overlapping(const std::vector<TRANGE>& vec) {
	if (vec.size() > 1) {
		auto last_it = vec.begin();
		auto it = last_it + 1;

		while (it < vec.end()) {
			if (it < last_it)
				return false;
			
			if (last_it->intersects(*it))
				return false;
			
			last_it = it;
			it++;
		}
	}
	return true;
}

template <typename TRANGE>
bool is_trange_vector_sorted(const std::vector<TRANGE>& vec) {
	if (vec.size() > 1) {
		auto last_it = vec.begin();
		auto it = last_it + 1;

		while (it < vec.end()) {
			if (it < last_it)
				return false;

			last_it = it;
			it++;
		}
	}
	return true;
}

// NOTE!
//
// This produces an output vector with the
// intervals "flattened".
//
// IOW, this:
//
// vec1: XXXXXXXX       AAAAAAAAAA
//        YYYYYYYYYYY ZZZZZZZZZ
//
// becomes:
//
// res:  IIIIIIIIIIII IIIIIIIIIIII
//
// The input vector should be sorted.
//
template <typename TRANGE>
std::vector<TRANGE> trange_vector_union(std::vector<TRANGE>& input) {
	std::vector<TRANGE> union_vec;

	ASSERT(is_trange_vector_sorted(input), "Sanity");

	if (!input.empty()) {
		auto input_it = input.begin();
		union_vec.push_back(*input_it);
		while (++input_it < input.end()) {
			TRANGE union_range = union_vec.back();

			if (union_range.intersects(*input_it)) {
				union_vec.pop_back();
				union_vec.push_back(union_range.union_range(*input_it));
			} else {
				ASSERT(union_range < *input_it, "Out of order merging");
				union_vec.push_back(*input_it);
			}
		}
	}

	ASSERT(is_trange_vector_sorted_and_non_overlapping(union_vec), "union'd vector fails invariant");

	return union_vec;
}

// NOTE!
//
// This will coalesce intervals that intersect.
//
// IOW, given two input vectors:
//
// vec1:      XXXX           XXXX
// vec2:              XXX
//
// res:       XXXX    XXX    XXXX
//
// --------------------------------
//
// vec1:      XXXX         XX
// vec2:        XXXXXXXXXXXXXXX
//
// res:       XXXXXXXXXXXXXXXXX

template <typename TRANGE>
std::vector<TRANGE> trange_vector_union(std::vector<TRANGE>& vec1, std::vector<TRANGE>& vec2) {
	std::vector<TRANGE> union_vec;

	ASSERT(is_trange_vector_sorted_and_non_overlapping(vec1), "input vector violates invariants");
	ASSERT(is_trange_vector_sorted_and_non_overlapping(vec2), "input vector violates invariants");

	// while (not done)
	//     select next interval (lowest location)
	//     if intersects with last union_vec entry, union, pop_back, push_back
	//     else push_back

	auto vec1_it = vec1.begin();
	auto vec2_it = vec2.begin();

	while (uint32_t chose_vector = (((vec1_it != vec1.end()) ? 1 : 0) + ((vec2_it != vec2.end()) ? 2 : 0))) {
		//
		// This is a fancy "chose" algorithm
		//
		// vec1 == bit 1
		// vec2 == bit 2
		//
		decltype(vec1_it) merge_it;
		switch (chose_vector) {
			case 1:
				merge_it = vec1_it++;
				break;

			case 2:
				merge_it = vec2_it++;
				break;

			case 3:
				merge_it = (*vec1_it < * vec2_it) ? vec1_it++ : vec2_it++;
				break;

			default:
				ASSERT(false, "ShouldNotReachHere");
				return std::vector<TRANGE>();
		}

		if (union_vec.empty()) {
			union_vec.push_back(*merge_it);
		} else {
			TRANGE last_range = union_vec.back();

			if (last_range.intersects(*merge_it)) {
				union_vec.pop_back();
				union_vec.push_back(last_range.union_range(*merge_it));
			} else {
				ASSERT(last_range < *merge_it, "Out of order merging");
				union_vec.push_back(*merge_it);
			}
		}
	}

	ASSERT(is_trange_vector_sorted_and_non_overlapping(union_vec), "union'd vector fails invariant");

	return union_vec;
}

template <typename TRANGE>
std::vector<TRANGE> trange_vector_intersect(std::vector<TRANGE>& vec1, std::vector<TRANGE>& vec2) {
	std::vector<TRANGE> intersect_vec;

	ASSERT(is_trange_vector_sorted_and_non_overlapping(vec1), "input vector violates invariants");
	ASSERT(is_trange_vector_sorted_and_non_overlapping(vec2), "input vector violates invariants");

	auto vec1_it = vec1.begin();
	auto vec2_it = vec2.begin();

	// As soon as one vector empties, there can be no more intersections
	while (vec1_it != vec1.end() && vec2_it  != vec2.end()) {
		TRANGE temp = vec1_it->intersection_range(*vec2_it);
		if (temp.length() > 0) {
			intersect_vec.push_back(temp);
		}

		// We keep the interval that ends last

		if (vec1_it->max() > vec2_it->max()) {
			vec2_it++;
		} else {
			vec1_it++;
		}
	}

	ASSERT(is_trange_vector_sorted_and_non_overlapping(intersect_vec), "intersection vector fails invariant");

	return intersect_vec;
}

#endif