cc/gapic/interval_list.h - platform/tools/gpu - Git at Google

 /*
  * Copyright (C) 2016 The Android Open Source Project
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
  *      http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */

 #ifndef GAPIC_INTERVAL_LIST_H
 #define GAPIC_INTERVAL_LIST_H

 #include <algorithm>
 #include <vector>

 namespace gapic {

 // Interval represents a single interval range of type T.
 // This is the default interval type to be used by IntervalList<T>.
 template <typename T>
 struct Interval {
     typedef T interval_unit_type;

     inline T    start() const { return mStart; }
     inline T    end()   const { return mEnd; }
     inline void adjust(T start, T end) { mStart = start; mEnd = end; }

     T mStart; // The index of the first item in the interval range.
     T mEnd;   // The index of the one-past the last item in the interval range.
 };

 // Interval equality operator.
 template <typename T>
 inline bool operator == (const Interval<T>& lhs, const Interval<T>& rhs) {
     return lhs.start() == rhs.start() && lhs.end() == rhs.end();
 }

 // Range is a stl-compatibile iteratable that allows iteration over all
 // memory-contiguous elements of type T between a start and end pointer.
 template <typename T>
 class Range {
 public:
     typedef T value_type;
     typedef const T* const_iterator;

     // Constructs the iterable with a pointer to the first element in the list
     // and a pointer to one-past the last element in the list.
     inline Range(const T* start, const T* end) : mStart(start), mEnd(end) {}

     // begin() returns the pointer to the first element in the list.
     inline const T* begin() const { return mStart; }
     // end() returns the pointer to one-past the last element in the list.
     inline const T* end() const { return mEnd; }
     // size() returns the number of items in the list.
     inline const size_t size() const { return mEnd - mStart; }
 private:
     const T* mStart;
     const T* mEnd;
 };

 // CustomIntervalList holds a ascendingly-sorted list of custom interval types.
 // Intervals can be added to the list using merge(), where they may be merged
 // with existing intervals if the spans are within the specified merge-threshold.
 // Intervals can also be added to the list using replace(), where any completely
 // overlapping intervals are removed and partially overlapping intervals are
 // trimmed, before inserting the new interval.
 // CustomIntervalList supports for-range looping.
 template <typename T>
 class CustomIntervalList {
 public:
     typedef T                              value_type;
     typedef const T*                       const_iterator;
     typedef typename T::interval_unit_type interval_unit_type;

     // Constructs an CustomIntervalList with a default merge threshold of 1.
     inline CustomIntervalList();

     // intersect returns a iterable range covering all the intervals that
     // intersect the span between start and end.
     inline Range<T> intersect(interval_unit_type start, interval_unit_type end) const;

     // replace removes and/or trims any intervals overlapping i and then adds i
     // to this list. No merging is performed.
     inline void replace(const T& i);

     // merge adds the interval i to this list, merging any overlapping intervals.
     inline void merge(const T& i);

     // setMergeThreshold sets the edge-distance threshold for merging intervals when
     // calling merge(). Intervals will merge if: edge-distance < threshold.
     // Examples:
     // • A threshold of 0 will require intervals to overlap before they are merged.
     // • A threshold of 1 will merge intervals if they overlap or touch edges.
     // • A threshold of 2 will merge intervals as described above, and those with a
     //   single unit gap.
     // Changing the merge thresholds will not affect any existing intervals in the list.
     inline void setMergeThreshold(interval_unit_type threshold);

     // clear removes all intervals from the list.
     inline void clear();

     // count returns the number of intervals in the list.
     inline uint32_t count() const;

     // begin() returns the pointer to the first interval in the list.
     inline const T* begin() const;

     // end() returns the pointer to one-past the last interval in the list.
     inline const T* end() const;

 protected:
     // rangeFirst returns the index of the first interval + bias that touches or
     // exceeds start.
     inline ssize_t rangeFirst(interval_unit_type start, interval_unit_type bias) const;

     // rangeLast returns the index of the last interval that touches or
     // is less than end + bias.
     inline ssize_t rangeLast(interval_unit_type end, interval_unit_type bias) const;

     std::vector< T > mIntervals;
     interval_unit_type mMergeBias;
 };

 template<typename T>
 CustomIntervalList<T>::CustomIntervalList() : mMergeBias(0) {}

 template<typename T>
 inline Range<T> CustomIntervalList<T>::intersect(interval_unit_type start, interval_unit_type end) const {
     auto first = begin() + rangeFirst(start, -1);
     auto last  = begin() + rangeLast(end, -1);
     return Range<T>(first, last+1);
 }

 template<typename T>
 inline void CustomIntervalList<T>::replace(const T& i) {
     auto first = rangeFirst(i.start(), mMergeBias);
     auto last  = rangeLast(i.end(), mMergeBias);

     if (first <= last) {
         bool trimTail = mIntervals[first].start() < i.start();
         bool trimHead = mIntervals[last].end() > i.end();

         if (first == last && trimTail && trimHead) {
             // i sits within a single interval. Split it into two.
             //           ┏━━━━━━━━━━━━━━┓
             //           ┗━━━━━━━━━━━━━━┛
             //━━━━━━━━━━━┳═─═─═─═─═─═─═─┳━━━━━━━━━━━
             //━━━━━━━━━━━┻─═─═─═─═─═─═─═┻━━━━━━━━━━━
             auto interval = mIntervals.begin() + first;
             mIntervals.insert(interval, *interval);
             last++;
         }
         if (trimTail) {
             // Trim end of first interval.
             //           ┏━━━━━━━━━━━━━━━━
             //           ┗━━━━━━━━━━━━━━━━
             //━━━━━━━━━━━┳═─═─╗
             //━━━━━━━━━━━┻─═─═┘
             auto interval = mIntervals.begin() + first;
             interval->adjust(interval->start(), i.start());
             first++; // Don't erase the first interval.
         }
         if (trimHead) {
             // Trim front of last interval.
             //━━━━━━━━━━━━━━━━┓
             //━━━━━━━━━━━━━━━━┛
             //           ┌═─═─┳━━━━━━━━━━━
             //           ╚─═─═┻━━━━━━━━━━━
             auto interval = mIntervals.begin() + last;
             interval->adjust(i.end(), interval->end());
             last--; // Don't erase the last interval.
         }
         if (first <= last) {
             auto from = mIntervals.begin() + first;
             auto to = mIntervals.begin() + last + 1;
             mIntervals.erase(from, to);
         }
     }
     mIntervals.insert(mIntervals.begin() + first, i);
 }

 template<typename T>
 inline void CustomIntervalList<T>::merge(const T& i) {
     auto first = rangeFirst(i.start(), mMergeBias);
     auto last  = rangeLast(i.end(), mMergeBias);
     auto from = mIntervals.begin() + first;
     if (first <= last) {
         auto to = mIntervals.begin() + last;
         auto low = std::min(from->start(), i.start());
         auto high = std::max(to->end(), i.end());
         mIntervals.erase(from, to);
         from->adjust(low, high);
     } else {
         mIntervals.insert(from, i);
     }
 }

 template<typename T>
 inline void CustomIntervalList<T>::setMergeThreshold(interval_unit_type threshold) {
     mMergeBias = threshold - 1;
 }

 template<typename T>
 inline void CustomIntervalList<T>::clear() {
     mIntervals.clear();
 }

 template<typename T>
 inline uint32_t CustomIntervalList<T>::count() const {
     return mIntervals.size();
 }

 template<typename T>
 inline const T* CustomIntervalList<T>::begin() const {
     if (count() > 0) {
         return &mIntervals[0];
     } else {
         return nullptr;
     }
 }

 template<typename T>
 inline const T* CustomIntervalList<T>::end() const {
     size_t c = mIntervals.size();
     if (c > 0) {
         return &mIntervals[c];
     } else {
         return nullptr;
     }
 }

 template<typename T>
 inline ssize_t CustomIntervalList<T>::rangeFirst(interval_unit_type start, interval_unit_type bias) const {
     ssize_t l = 0;
     ssize_t h = mIntervals.size();
     while (l != h) {
         ssize_t m = (l + h) / 2;
         if (mIntervals[m].end() + bias >= start) {
             h = m;
         } else {
             l = m + 1;
         }
     }
     return l;
 }

 template<typename T>
 inline ssize_t CustomIntervalList<T>::rangeLast(interval_unit_type end, interval_unit_type bias) const {
     ssize_t l = -1;
     ssize_t h = mIntervals.size() - 1;
     while (l != h) {
         ssize_t m = (l + h + 1) / 2;
         if (mIntervals[m].start() <= end + bias) {
             l = m;
         } else {
             h = m - 1;
         }
     }
     return l;
 }

 // IntervalList holds a ascendingly-sorted list of Interval<T>s.
 // See CustomIntervalList for more information.
 template <typename T>
 class IntervalList : public CustomIntervalList< Interval<T> > {};

 } // namespace gapic

 #endif // GAPIC_INTERVAL_LIST_H
	/*
	* Copyright (C) 2016 The Android Open Source Project
	*
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/

	#ifndef GAPIC_INTERVAL_LIST_H
	#define GAPIC_INTERVAL_LIST_H

	#include <algorithm>
	#include <vector>

	namespace gapic {

	// Interval represents a single interval range of type T.
	// This is the default interval type to be used by IntervalList<T>.
	template <typename T>
	struct Interval {
	typedef T interval_unit_type;

	inline T start() const { return mStart; }
	inline T end() const { return mEnd; }
	inline void adjust(T start, T end) { mStart = start; mEnd = end; }

	T mStart; // The index of the first item in the interval range.
	T mEnd; // The index of the one-past the last item in the interval range.
	};

	// Interval equality operator.
	template <typename T>
	inline bool operator == (const Interval<T>& lhs, const Interval<T>& rhs) {
	return lhs.start() == rhs.start() && lhs.end() == rhs.end();
	}

	// Range is a stl-compatibile iteratable that allows iteration over all
	// memory-contiguous elements of type T between a start and end pointer.
	template <typename T>
	class Range {
	public:
	typedef T value_type;
	typedef const T* const_iterator;

	// Constructs the iterable with a pointer to the first element in the list
	// and a pointer to one-past the last element in the list.
	inline Range(const T* start, const T* end) : mStart(start), mEnd(end) {}

	// begin() returns the pointer to the first element in the list.
	inline const T* begin() const { return mStart; }
	// end() returns the pointer to one-past the last element in the list.
	inline const T* end() const { return mEnd; }
	// size() returns the number of items in the list.
	inline const size_t size() const { return mEnd - mStart; }
	private:
	const T* mStart;
	const T* mEnd;
	};

	// CustomIntervalList holds a ascendingly-sorted list of custom interval types.
	// Intervals can be added to the list using merge(), where they may be merged
	// with existing intervals if the spans are within the specified merge-threshold.
	// Intervals can also be added to the list using replace(), where any completely
	// overlapping intervals are removed and partially overlapping intervals are
	// trimmed, before inserting the new interval.
	// CustomIntervalList supports for-range looping.
	template <typename T>
	class CustomIntervalList {
	public:
	typedef T value_type;
	typedef const T* const_iterator;
	typedef typename T::interval_unit_type interval_unit_type;

	// Constructs an CustomIntervalList with a default merge threshold of 1.
	inline CustomIntervalList();

	// intersect returns a iterable range covering all the intervals that
	// intersect the span between start and end.
	inline Range<T> intersect(interval_unit_type start, interval_unit_type end) const;

	// replace removes and/or trims any intervals overlapping i and then adds i
	// to this list. No merging is performed.
	inline void replace(const T& i);

	// merge adds the interval i to this list, merging any overlapping intervals.
	inline void merge(const T& i);

	// setMergeThreshold sets the edge-distance threshold for merging intervals when
	// calling merge(). Intervals will merge if: edge-distance < threshold.
	// Examples:
	// • A threshold of 0 will require intervals to overlap before they are merged.
	// • A threshold of 1 will merge intervals if they overlap or touch edges.
	// • A threshold of 2 will merge intervals as described above, and those with a
	// single unit gap.
	// Changing the merge thresholds will not affect any existing intervals in the list.
	inline void setMergeThreshold(interval_unit_type threshold);

	// clear removes all intervals from the list.
	inline void clear();

	// count returns the number of intervals in the list.
	inline uint32_t count() const;

	// begin() returns the pointer to the first interval in the list.
	inline const T* begin() const;

	// end() returns the pointer to one-past the last interval in the list.
	inline const T* end() const;

	protected:
	// rangeFirst returns the index of the first interval + bias that touches or
	// exceeds start.
	inline ssize_t rangeFirst(interval_unit_type start, interval_unit_type bias) const;

	// rangeLast returns the index of the last interval that touches or
	// is less than end + bias.
	inline ssize_t rangeLast(interval_unit_type end, interval_unit_type bias) const;

	std::vector< T > mIntervals;
	interval_unit_type mMergeBias;
	};

	template<typename T>
	CustomIntervalList<T>::CustomIntervalList() : mMergeBias(0) {}

	template<typename T>
	inline Range<T> CustomIntervalList<T>::intersect(interval_unit_type start, interval_unit_type end) const {
	auto first = begin() + rangeFirst(start, -1);
	auto last = begin() + rangeLast(end, -1);
	return Range<T>(first, last+1);
	}

	template<typename T>
	inline void CustomIntervalList<T>::replace(const T& i) {
	auto first = rangeFirst(i.start(), mMergeBias);
	auto last = rangeLast(i.end(), mMergeBias);

	if (first <= last) {
	bool trimTail = mIntervals[first].start() < i.start();
	bool trimHead = mIntervals[last].end() > i.end();

	if (first == last && trimTail && trimHead) {
	// i sits within a single interval. Split it into two.
	// ┏━━━━━━━━━━━━━━┓
	// ┗━━━━━━━━━━━━━━┛
	//━━━━━━━━━━━┳═─═─═─═─═─═─═─┳━━━━━━━━━━━
	//━━━━━━━━━━━┻─═─═─═─═─═─═─═┻━━━━━━━━━━━
	auto interval = mIntervals.begin() + first;
	mIntervals.insert(interval, *interval);
	last++;
	}
	if (trimTail) {
	// Trim end of first interval.
	// ┏━━━━━━━━━━━━━━━━
	// ┗━━━━━━━━━━━━━━━━
	//━━━━━━━━━━━┳═─═─╗
	//━━━━━━━━━━━┻─═─═┘
	auto interval = mIntervals.begin() + first;
	interval->adjust(interval->start(), i.start());
	first++; // Don't erase the first interval.
	}
	if (trimHead) {
	// Trim front of last interval.
	//━━━━━━━━━━━━━━━━┓
	//━━━━━━━━━━━━━━━━┛
	// ┌═─═─┳━━━━━━━━━━━
	// ╚─═─═┻━━━━━━━━━━━
	auto interval = mIntervals.begin() + last;
	interval->adjust(i.end(), interval->end());
	last--; // Don't erase the last interval.
	}
	if (first <= last) {
	auto from = mIntervals.begin() + first;
	auto to = mIntervals.begin() + last + 1;
	mIntervals.erase(from, to);
	}
	}
	mIntervals.insert(mIntervals.begin() + first, i);
	}

	template<typename T>
	inline void CustomIntervalList<T>::merge(const T& i) {
	auto first = rangeFirst(i.start(), mMergeBias);
	auto last = rangeLast(i.end(), mMergeBias);
	auto from = mIntervals.begin() + first;
	if (first <= last) {
	auto to = mIntervals.begin() + last;
	auto low = std::min(from->start(), i.start());
	auto high = std::max(to->end(), i.end());
	mIntervals.erase(from, to);
	from->adjust(low, high);
	} else {
	mIntervals.insert(from, i);
	}
	}

	template<typename T>
	inline void CustomIntervalList<T>::setMergeThreshold(interval_unit_type threshold) {
	mMergeBias = threshold - 1;
	}

	template<typename T>
	inline void CustomIntervalList<T>::clear() {
	mIntervals.clear();
	}

	template<typename T>
	inline uint32_t CustomIntervalList<T>::count() const {
	return mIntervals.size();
	}

	template<typename T>
	inline const T* CustomIntervalList<T>::begin() const {
	if (count() > 0) {
	return &mIntervals[0];
	} else {
	return nullptr;
	}
	}

	template<typename T>
	inline const T* CustomIntervalList<T>::end() const {
	size_t c = mIntervals.size();
	if (c > 0) {
	return &mIntervals[c];
	} else {
	return nullptr;
	}
	}

	template<typename T>
	inline ssize_t CustomIntervalList<T>::rangeFirst(interval_unit_type start, interval_unit_type bias) const {
	ssize_t l = 0;
	ssize_t h = mIntervals.size();
	while (l != h) {
	ssize_t m = (l + h) / 2;
	if (mIntervals[m].end() + bias >= start) {
	h = m;
	} else {
	l = m + 1;
	}
	}
	return l;
	}

	template<typename T>
	inline ssize_t CustomIntervalList<T>::rangeLast(interval_unit_type end, interval_unit_type bias) const {
	ssize_t l = -1;
	ssize_t h = mIntervals.size() - 1;
	while (l != h) {
	ssize_t m = (l + h + 1) / 2;
	if (mIntervals[m].start() <= end + bias) {
	l = m;
	} else {
	h = m - 1;
	}
	}
	return l;
	}

	// IntervalList holds a ascendingly-sorted list of Interval<T>s.
	// See CustomIntervalList for more information.
	template <typename T>
	class IntervalList : public CustomIntervalList< Interval<T> > {};

	} // namespace gapic

	#endif // GAPIC_INTERVAL_LIST_H