Cursor API Proposal
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <utility> | |
template <typename T> using some_iterator_type = T*; | |
template <typename T> struct ptr {}; // from mongo ptr.h | |
// Defining concepts using struct syntax. These are like interfaces, but not in | |
// the virtual-dispatch sense. Actual Cursor implementations must have an API | |
// that is usable as-if it had these signatures, even if the types don't match. | |
#define concept struct | |
// Something that either has a value or doesn't. | |
// Examples: | |
// T* | |
// boost::optional<T> | |
template <typename T> | |
concept OptionLike { | |
// Value initialization (not necessarily default initialization) | |
// results in an empty OptionLike. | |
OptionLike() {} | |
// Copyable | |
OptionLike(const OptionLike&); | |
// true if there is a value, false otherwise. | |
explicit operator bool(); | |
T& operator*(); | |
T* operator->(); | |
// Returns of const version may or may not be const-qualified | |
const T& operator*() const; | |
const T* operator->() const; | |
}; | |
// Cursors are named after similar STL iterator concepts. | |
// See http://en.cppreference.com/w/cpp/iterator. | |
// The most basic cursor. It represents a single pass over a sequence. | |
// Caller takes ownership of result. | |
// Examples: | |
// Aggregation stages | |
// Query stages | |
// Python generators | |
template <typename T> | |
concept InputCursor { | |
template <typename U> | |
using option_type = OptionLike<U>; | |
// If T is "unowned" it is only valid until the next call to any method | |
// unless otherwise specified. It also be invalidated when the Cursor is | |
// destroyed. | |
// Legal to call repeatedly after a false value is returned. | |
OptionLike<T> next(); | |
}; | |
int example(InputCursor<int> cursor) { | |
int total = 0; | |
while (auto next = cursor.next()) { | |
total += *next; | |
} | |
return total; | |
} | |
// An InputCursor that can report its current position repeatedly. | |
// May be thought of as a "buffered" InputCursor. | |
// A thin wrapper can convert any InputCursor to a ForwardCursor. | |
// These can also be translated to STL iterators used by range-for loops. | |
// Example: | |
// Today's RecordIterator | |
template <typename T> | |
concept ForwardCursor : InputCursor<T> { | |
// Returns the last value from next(). | |
// Illegal to call before first call to next(). | |
// Does not invalidate "unowned data" | |
// Non-const versions may also be provided. | |
OptionLike<T> curr() const; | |
}; | |
// ForwardCursors are usable with range-for loops. | |
template <typename T> some_iterator_type<T> begin(ForwardCursor<T>& cursor); | |
template <typename T> some_iterator_type<T> end(const ForwardCursor<T>& cursor); | |
// Pointers to ForwardCursors (including smart_ptrs) are as well. | |
template <typename T> some_iterator_type<T> begin(ptr<ForwardCursor<T>> cursor); | |
template <typename T> some_iterator_type<T> end(ptr<const ForwardCursor<T>> cursor); | |
int example(ForwardCursor<int> cursor) { | |
int total = 0; | |
for (auto&& val : cursor) { // works even if cursor is a temporary. | |
total += val; | |
} | |
return total; | |
} | |
// Can go forward and backwards. | |
template <typename T> | |
concept BidirectionalCursor : ForwardCursor<T> { | |
OptionLike<T> prev(); | |
}; | |
// A BidirectionalCursor over a pair-like type representing keys and values. | |
// A generic wrapper around BidiCursor<pair<K,V>> will be provided, but | |
// implementations may write their own versions if they can be more efficient. | |
// KV versions of ForwardCursor and InputCursor are also possible. | |
// Examples: | |
// Todays SortedDataInterface::Cursor | |
template <typename K, typename V, typename PairType=std::pair<K,V>> | |
concept KVBidirectionalCursor : BidirectionalCursor<PairType> { | |
OptionLike<K> nextKey(); | |
OptionLike<V> nextVal(); | |
OptionLike<K> prevKey(); | |
OptionLike<V> prevVal(); | |
// Do not invalidate "unowned data" | |
const K& currKey(); | |
const V& currVal(); | |
}; | |
enum RelativePosition { | |
Before = -1, | |
Unspecified = 0, // Intentionally evaluates as false | |
Exact, | |
After, | |
}; | |
// Allows seeking to an arbitrary key in sub-linear time. | |
template <typename K, typename V, typename PairType=std::pair<K,V>> | |
concept RandomAccessCursor : KVBidirectionalCursor<K, V, PairType> { | |
OptionLike<K> seekToFirstKey(); | |
OptionLike<K> seekToLastKey(); | |
// Seek to a key | |
// | |
// If the key is not found, the cursor will be repositioned to the nearest | |
// location based on the value of ifNotFound: | |
// Before: The closest location before 'key', or OptionLike() if none. | |
// After: The closest location after 'key', or OptionLike() if none. | |
// Exact: OptionLike(). Cursor is left unpositioned. | |
// Unspecified: Any of the above (impl may make most efficient choice). | |
OptionLike<K> seek(const K& key, RelativePosition ifNotFound = Exact); | |
}; | |
// Something that can be frozen to prepare for underlying state changes. | |
concept Freezeable { | |
// Prepare for state changes in underlying data. | |
// It is safe to call freeze multiple times in a row. | |
// No other method (excluding destructor) may be called until thawed. | |
void freeze(); | |
// Recover from potential state changes in underlying data. | |
// If false is returned, nothing other than the destructor or freeze/thaw | |
// may be called until the next seek. | |
// | |
// After thawing it is illegal to call curr() before the next call to a | |
// reposition method(). | |
bool thaw(); | |
}; | |
// FreezableRandomAccessCursors provide a more capable thaw method(). | |
// Example: | |
// Future RecordIterator? | |
// Future SortedDataInterface::Cursor? | |
template <typename K, typename V, typename PairType=std::pair<K,V>> | |
concept FreezeableRandomAccessCursor : RandomAccessCursor<K, V, PairType> | |
, Freezeable { | |
// Recover from potential state changes in underlying data. | |
// | |
// Returns the RelativePosition of the new location to the | |
// location before being frozen. If Before or After is returned, | |
// the cursor is still logically positioned where it was, so the | |
// next call to next() or prev() will return the new position. | |
// | |
// It is only legal to call curr() if Equal is returned. | |
// | |
// If Unspecified is returned, the cursor is unpositioned, so nothing other | |
// than the destructor or freeze/thaw may be called until the next seek. | |
// | |
// NOTE: this is API-compatible with FreezableInputCursor::thaw(). | |
RelativePosition thaw(RelativePosition ifNotFound = Exact); | |
// Prepare this cursor to be used again, but don't position it. | |
// One of the seek() methods must be used to seek the cursor. | |
bool thawUnpositioned(); | |
}; | |
// Any Cursor where modifications to values are applied to the underlying data. | |
// Example: | |
// Cusors over non-const containers. | |
template <typename T> | |
concept MutableCursor : ForwardCursor<T> { | |
// It must use a bare T* for OptionLike<T> | |
template <typename U> using option_type = U*; | |
}; | |
void example(MutableCursor<int> cursor) { | |
// These two loops are equivalent: | |
while (auto next = cursor.next()) { *next = 0; } | |
for (auto& next : cursor) { next = 0; } | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment