1 // Copyright (c) Microsoft Open Technologies, Inc. All rights reserved. See License.txt in the project root for license information. 2 3 #if !defined(CPPLINQ_LINQ_CURSOR_HPP) 4 #define CPPLINQ_LINQ_CURSOR_HPP 5 #pragma once 6 7 #include <cstddef> 8 9 /// cursors 10 /// ---------- 11 /// It should be noted that CppLinq uses a slightly different iterator concept, one where iterators 12 /// know their extents. This sacrificed some generality, but it adds convenience and improves 13 /// some performance in some cases. Notably, captures need only be stored once instead of twice in 14 /// most use cases. 15 /// 16 /// Cursors and Ranges are always classes. 17 /// 18 /// To get a cursor from a range: 19 /// 20 /// get_cursor(range) -> cur 21 /// 22 /// Unlike boost ranges, CppLinq cursors are mutated directly, and may "shed state" as they are 23 /// mutated. For example, a GroupBy range will drop references to earlier groups, possibly 24 /// permitting freeing them. 25 /// 26 /// Onepass cursor 27 /// =========== 28 /// - empty(cur) -> bool : at end of sequence 29 /// - inc(cur) 30 /// - get(cur) -> T 31 /// - copy ctor : duplicate reference to seek position 32 /// 33 /// Forward cursor 34 /// ============= 35 /// - copy ctor : true duplicate of seek position 36 /// 37 /// Bidirectional cursor 38 /// ==================== 39 /// - forget() : notes the current element as the new 'begin' point 40 /// - atbegin(cur) -> bool 41 /// - dec(cur) 42 /// 43 /// Random access cursor 44 /// ==================== 45 /// - skip(cur, n) 46 /// - position(cur) -> n 47 /// - size(cur) -> n 48 /// - truncate(n) : keep only n more elements 49 /// 50 /// As well, cursors must define the appropriate type/typedefs: 51 /// - cursor_category :: { onepass_cursor_tag, forward_cursor_tag, bidirectional_cursor_tag, random_access_cursor_tag } 52 /// - element_type 53 /// - reference_type : if writable, element_type& or such. else, == element_type 54 /// - 55 56 57 58 namespace cpplinq { 59 60 // used to identify cursor-based collections 61 struct collection_tag {}; 62 63 struct onepass_cursor_tag {}; 64 struct forward_cursor_tag : onepass_cursor_tag {}; 65 struct bidirectional_cursor_tag : forward_cursor_tag {}; 66 struct random_access_cursor_tag : bidirectional_cursor_tag {}; 67 68 struct noread_cursor_tag {}; // TODO: remove if not used 69 struct readonly_cursor_tag : noread_cursor_tag {}; 70 struct readwrite_cursor_tag : readonly_cursor_tag {}; 71 72 73 74 // standard cursor adaptors 75 76 namespace util 77 { 78 namespace detail 79 { 80 template <std::size_t n> struct type_to_size { char value[n]; }; 81 82 type_to_size<1> get_category_from_iterator(std::input_iterator_tag); 83 type_to_size<2> get_category_from_iterator(std::forward_iterator_tag); 84 type_to_size<3> get_category_from_iterator(std::bidirectional_iterator_tag); 85 type_to_size<4> get_category_from_iterator(std::random_access_iterator_tag); 86 } 87 88 template <std::size_t> 89 struct iter_to_cursor_category_; 90 91 template <class Iter> 92 struct iter_to_cursor_category 93 { 94 static const std::size_t catIx = sizeof(detail::get_category_from_iterator(typename std::iterator_traits<Iter>::iterator_category()) /*.value*/ ); 95 typedef typename iter_to_cursor_category_<catIx>::type type; 96 }; 97 98 template <> struct iter_to_cursor_category_<1> { typedef onepass_cursor_tag type; }; 99 template <> struct iter_to_cursor_category_<2> { typedef forward_cursor_tag type; }; 100 template <> struct iter_to_cursor_category_<3> { typedef bidirectional_cursor_tag type; }; 101 template <> struct iter_to_cursor_category_<4> { typedef random_access_cursor_tag type; }; 102 103 104 // Note: returns false if no partial order exists between two 105 // particular iterator categories, such as with some of the boost categories 106 template <class Cat1, class Cat2> 107 struct less_or_equal_cursor_category 108 { 109 private: 110 typedef char yes; 111 typedef struct { char c1,c2; } no; 112 static yes invoke(Cat1); 113 static no invoke(...); 114 public: 115 enum { value = (sizeof(invoke(Cat2())) == sizeof(yes)) }; 116 }; 117 118 // Return the weaker of the two iterator categories. Make sure 119 // a non-standard category is in the second argument position, as 120 // this metafunction will default to the first value if the order is undefined 121 template <class Cat1, class Cat2, class Cat3 = void> 122 struct min_cursor_category : min_cursor_category<typename min_cursor_category<Cat1, Cat2>::type, Cat3> 123 { 124 }; 125 126 template <class Cat1, class Cat2> 127 struct min_cursor_category<Cat1, Cat2> 128 : std::conditional< 129 less_or_equal_cursor_category<Cat2, Cat1>::value, 130 Cat2, 131 Cat1> 132 { 133 }; 134 135 template <class Collection> 136 struct cursor_type { 137 typedef decltype(cursor(*static_cast<Collection*>(0))) type; 138 }; 139 } 140 141 // simultaniously models a cursor and a cursor-collection 142 template <class Iterator> 143 class iter_cursor : collection_tag { 144 public: 145 146 typedef iter_cursor cursor; 147 148 typedef typename std::remove_reference<typename std::iterator_traits<Iterator>::value_type>::type 149 element_type; 150 typedef typename std::iterator_traits<Iterator>::reference 151 reference_type; 152 typedef typename util::iter_to_cursor_category<Iterator>::type 153 cursor_category; 154 155 void forget() { start = current; } 156 bool empty() const { return current == fin; } 157 void inc() { 158 if (current == fin) 159 throw std::logic_error("inc past end"); 160 ++current; 161 } 162 typename std::iterator_traits<Iterator>::reference get() const { return *current; } 163 164 bool atbegin() const { return current == start; } 165 void dec() { 166 if (current == start) 167 throw std::logic_error("dec past begin"); 168 --current; 169 } 170 171 void skip(std::ptrdiff_t n) { current += n; } 172 std::size_t size() { return fin-start; } 173 void position() { return current-start; } 174 void truncate(std::size_t n) { 175 if (n > fin-current) { 176 fin = current + n; 177 } 178 } 179 180 181 iter_cursor(Iterator start, Iterator fin) 182 : current(start) 183 , start(start) 184 , fin(std::move(fin)) 185 { 186 } 187 188 iter_cursor(Iterator start, Iterator fin, Iterator current) 189 : current(std::move(current)) 190 , start(std::move(start)) 191 , fin(std::move(fin)) 192 { 193 } 194 195 iter_cursor get_cursor() const { return *this; } 196 197 private: 198 Iterator current; 199 Iterator start, fin; 200 }; 201 202 203 template <class T> 204 struct cursor_interface 205 { 206 virtual bool empty() const = 0; 207 virtual void inc() = 0; 208 virtual cursor_interface* copy() const = 0; 209 210 virtual T get() const = 0; 211 212 virtual ~cursor_interface() {} 213 }; 214 215 template <class T> 216 class dynamic_cursor : collection_tag 217 { 218 template <class Cur> 219 struct instance : cursor_interface<T> 220 { 221 Cur innerCursor; 222 223 instance(Cur cursor) : innerCursor(std::move(cursor)) 224 { 225 } 226 virtual bool empty() const 227 { 228 return innerCursor.empty(); 229 } 230 virtual void inc() 231 { 232 innerCursor.inc(); 233 } 234 virtual T get() const 235 { 236 return innerCursor.get(); 237 } 238 virtual cursor_interface<T>* copy() const 239 { 240 return new instance(*this); 241 } 242 }; 243 244 std::unique_ptr<cursor_interface<T>> myCur; 245 246 public: 247 typedef forward_cursor_tag cursor_category; // TODO: not strictly true! 248 typedef typename std::remove_reference<T>::type element_type; 249 typedef T reference_type; 250 251 dynamic_cursor() {} 252 253 dynamic_cursor(const dynamic_cursor& other) 254 : myCur(other.myCur ? other.myCur->copy() : nullptr) 255 { 256 } 257 258 dynamic_cursor(dynamic_cursor&& other) 259 : myCur(other.myCur.release()) 260 { 261 } 262 263 template <class Cursor> 264 dynamic_cursor(Cursor cursor) 265 : myCur(new instance<Cursor>(std::move(cursor))) 266 { 267 } 268 269 template <class Iterator> 270 dynamic_cursor(Iterator start, Iterator end) 271 { 272 *this = iter_cursor<Iterator>(start, end); 273 } 274 275 bool empty() const { return !myCur || myCur->empty(); } 276 void inc() { myCur->inc(); } 277 T get() const { return myCur->get(); } 278 279 dynamic_cursor& operator=(dynamic_cursor other) 280 { 281 std::swap(myCur, other.myCur); 282 return *this; 283 } 284 }; 285 286 template <class T> 287 struct container_interface 288 { 289 virtual dynamic_cursor<T> get_cursor() const = 0; 290 }; 291 292 template <class T> 293 class dynamic_collection 294 { 295 std::shared_ptr< container_interface<T> > container; 296 297 template <class Container> 298 struct instance : container_interface<T> 299 { 300 Container c; 301 302 instance(Container c) : c(c) 303 { 304 } 305 306 dynamic_cursor<T> get_cursor() const 307 { 308 return c.get_cursor(); 309 } 310 }; 311 312 public: 313 typedef dynamic_cursor<T> cursor; 314 315 dynamic_collection() {} 316 317 dynamic_collection(const dynamic_collection& other) 318 : container(other.container) 319 { 320 } 321 322 // container or query 323 template <class Container> 324 dynamic_collection(Container c) 325 : container(new instance<Container>(c)) 326 { 327 } 328 329 // container or query 330 template <class Iterator> 331 dynamic_collection(Iterator begin, Iterator end) 332 : container(new instance< iter_cursor<Iterator> >(iter_cursor<Iterator>(begin, end))) 333 { 334 } 335 336 dynamic_cursor<T> get_cursor() const { 337 return container ? container->get_cursor() : dynamic_cursor<T>(); 338 } 339 }; 340 } 341 342 #endif // !defined(CPPLINQ_LINQ_CURSOR_HPP 343
