Skip to content

Instantly share code, notes, and snippets.

@RedBeard0531
Created February 20, 2015 23:08
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save RedBeard0531/b5439967b8cc6013392e to your computer and use it in GitHub Desktop.
Cursor API Proposal
#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