RxCpp
The Reactive Extensions for Native (RxCpp) is a library for composing asynchronous and event-based programs using observable sequences and LINQ-style query operators in both C and C++.
linq_groupby.hpp
Go to the documentation of this file.
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_GROUPBY_HPP)
4 #define CPPLINQ_LINQ_GROUPBY_HPP
5 #pragma once
6 
7 namespace cpplinq
8 {
9 
10 template <class Iter, class Key>
11 struct group
12 {
13  Key key;
14  Iter start;
15  Iter fin;
16 
17  typedef Iter iterator;
18  typedef Iter const_iterator;
19 
20  group(){}
21 
22  group(const Key& key) : key(key)
23  {
24  }
25 
26  Iter begin() const { return start; }
27  Iter end() const { return fin; }
28 };
29 
31 {
32  template <class T>
33  bool operator()(const T& a, const T& b) const {
34  return a == b;
35  }
36 };
38 {
39  template<class T>
40  bool operator()(const T& a, const T& b) const {
41  return a < b;
42  }
43 };
44 
45 // progressively constructs grouping as user iterates over groups and elements
46 // within each group. Performs this task by building a std::list of element
47 // iterators with equal elements within each group.
48 //
49 // invariants:
50 // - relative order of groups corresponds to relative order of each group's first
51 // element, as they appeared in the input sequence.
52 // - relative order of elements within a group correspond to relative order
53 // as they appeared in the input sequence.
54 //
55 // requires:
56 // Iter must be a forward iterator.
57 template <class Collection, class KeyFn, class Compare = default_less>
59 {
60  typedef typename Collection::cursor
61  inner_cursor;
62 
63  typedef typename util::result_of<KeyFn(typename inner_cursor::element_type)>::type
64  key_type;
65 
66  typedef std::list<typename inner_cursor::element_type>
67  element_list_type;
68 
70  group_type;
71 
72  typedef std::list<group_type>
73  group_list_type;
74 
75 private:
76  struct impl_t
77  {
78  // TODO: would be faster to use a chunked list, where
79  // pointers are invalidated but iterators are not. Need
80  // benchmarks first
81 
82  element_list_type elements;
83  std::list<group_type> groups;
84  std::map<key_type, group_type*, Compare> groupIndex;
85 
86 
87 
88  KeyFn keySelector;
89  Compare comp;
90 
91  impl_t(inner_cursor cur,
92  KeyFn keySelector,
93  Compare comp = Compare())
94  : keySelector(keySelector)
95  , groupIndex(comp)
96  {
97  // TODO: make lazy
98  insert_all(std::move(cur));
99  }
100 
101  void insert_all(inner_cursor cur)
102  {
103  while(!cur.empty()) {
104  insert(cur.get());
105  cur.inc();
106  }
107  }
108  void insert(typename inner_cursor::reference_type element)
109  {
110  key_type key = keySelector(element);
111  auto groupPos = groupIndex.find(key);
112  if(groupPos == groupIndex.end()) {
113  // new group
114  bool firstGroup = groups.empty();
115 
116  elements.push_back(element);
117  if(!firstGroup) {
118  // pop new element out of previous group
119  --groups.back().fin;
120  }
121 
122  // build new group
123  groups.push_back(group_type(key));
124  group_type& newGroup = groups.back();
125 
126  groupIndex.insert( std::make_pair(key, &newGroup) );
127 
128  newGroup.fin = elements.end();
129  --(newGroup.start = newGroup.fin);
130  } else {
131  // add to existing group at end
132  elements.insert(groupPos->second->end(), element);
133  }
134  }
135  };
136 
137 public:
138  struct cursor {
139  typedef group_type
141 
142  typedef element_type
144 
145  typedef forward_cursor_tag
147 
148  cursor(inner_cursor cur,
149  KeyFn keyFn,
150  Compare comp = Compare())
151  {
152  impl.reset(new impl_t(cur, keyFn, comp));
153  inner = impl->groups.begin();
154  fin = impl->groups.end();
155  }
156 
157  void forget() { } // nop on forward-only cursors
158  bool empty() const {
159  return inner == fin;
160  }
161  void inc() {
162  if (inner == fin) {
163  throw std::logic_error("attempt to iterate past end of range");
164  }
165  ++inner;
166  }
167  reference_type get() const {
168  return *inner;
169  }
170 
171  private:
172  std::shared_ptr<impl_t> impl;
173  typename std::list<group_type>::iterator inner;
174  typename std::list<group_type>::iterator fin;
175  };
176 
177  linq_groupby(Collection c,
178  KeyFn keyFn,
179  Compare comp = Compare())
180  : c(c), keyFn(keyFn), comp(comp)
181  {
182  }
183 
184  cursor get_cursor() const { return cursor(c.get_cursor(), keyFn, comp); }
185 
186 private:
187  Collection c;
188  KeyFn keyFn;
189  Compare comp;
190 };
191 
192 }
193 
194 #endif // !defined(CPPLINQ_LINQ_GROUPBY_HPP)
195 
Iter fin
Definition: linq_groupby.hpp:15
bool operator()(const T &a, const T &b) const
Definition: linq_groupby.hpp:33
bool empty() const
Definition: linq_groupby.hpp:158
Iter start
Definition: linq_groupby.hpp:14
Iter begin() const
Definition: linq_groupby.hpp:26
Iter iterator
Definition: linq_groupby.hpp:17
cursor get_cursor() const
Definition: linq_groupby.hpp:184
forward_cursor_tag cursor_category
Definition: linq_groupby.hpp:146
group_type element_type
Definition: linq_groupby.hpp:140
Key key
Definition: linq_groupby.hpp:13
Definition: linq_groupby.hpp:37
linq_groupby(Collection c, KeyFn keyFn, Compare comp=Compare())
Definition: linq_groupby.hpp:177
Definition: linq_groupby.hpp:138
Iter end() const
Definition: linq_groupby.hpp:27
Definition: linq.hpp:186
Definition: linq_cursor.hpp:64
void inc()
Definition: linq_groupby.hpp:161
group(const Key &key)
Definition: linq_groupby.hpp:22
element_type reference_type
Definition: linq_groupby.hpp:143
Definition: linq_groupby.hpp:11
group()
Definition: linq_groupby.hpp:20
Definition: linq_groupby.hpp:30
cursor(inner_cursor cur, KeyFn keyFn, Compare comp=Compare())
Definition: linq_groupby.hpp:148
void forget()
Definition: linq_groupby.hpp:157
Definition: linq_groupby.hpp:58
bool operator()(const T &a, const T &b) const
Definition: linq_groupby.hpp:40
Iter const_iterator
Definition: linq_groupby.hpp:18