Home | History | Annotate | Download | only in cpplinq 
      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 
     30 struct default_equality
     31 {
     32     template <class T>
     33     bool operator()(const T& a, const T& b) const {
     34         return a == b;
     35     }
     36 };
     37 struct default_less
     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>
     58 class linq_groupby
     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 
     69     typedef group<typename element_list_type::iterator, key_type>
     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
    140             element_type;
    141 
    142         typedef element_type
    143             reference_type;
    144 
    145         typedef forward_cursor_tag
    146             cursor_category;
    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 
    196