Qt 4.8
qorderby.cpp
Go to the documentation of this file.
1 /****************************************************************************
2 **
3 ** Copyright (C) 2014 Digia Plc and/or its subsidiary(-ies).
4 ** Contact: http://www.qt-project.org/legal
5 **
6 ** This file is part of the QtXmlPatterns module of the Qt Toolkit.
7 **
8 ** $QT_BEGIN_LICENSE:LGPL$
9 ** Commercial License Usage
10 ** Licensees holding valid commercial Qt licenses may use this file in
11 ** accordance with the commercial license agreement provided with the
12 ** Software or, alternatively, in accordance with the terms contained in
13 ** a written agreement between you and Digia. For licensing terms and
14 ** conditions see http://qt.digia.com/licensing. For further information
15 ** use the contact form at http://qt.digia.com/contact-us.
16 **
17 ** GNU Lesser General Public License Usage
18 ** Alternatively, this file may be used under the terms of the GNU Lesser
19 ** General Public License version 2.1 as published by the Free Software
20 ** Foundation and appearing in the file LICENSE.LGPL included in the
21 ** packaging of this file. Please review the following information to
22 ** ensure the GNU Lesser General Public License version 2.1 requirements
23 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
24 **
25 ** In addition, as a special exception, Digia gives you certain additional
26 ** rights. These rights are described in the Digia Qt LGPL Exception
27 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
28 **
29 ** GNU General Public License Usage
30 ** Alternatively, this file may be used under the terms of the GNU
31 ** General Public License version 3.0 as published by the Free Software
32 ** Foundation and appearing in the file LICENSE.GPL included in the
33 ** packaging of this file. Please review the following information to
34 ** ensure the GNU General Public License version 3.0 requirements will be
35 ** met: http://www.gnu.org/copyleft/gpl.html.
36 **
37 **
38 ** $QT_END_LICENSE$
39 **
40 ****************************************************************************/
41 
42 #include <QtAlgorithms>
43 
44 #include "qcommonsequencetypes_p.h"
45 #include "qnodebuilder_p.h"
46 #include "qschemanumeric_p.h"
47 #include "qpatternistlocale_p.h"
48 #include "qreturnorderby_p.h"
49 #include "qsorttuple_p.h"
51 
52 #include "qorderby_p.h"
53 
55 
56 using namespace QPatternist;
57 
58 OrderBy::OrderBy(const Stability stability,
59  const OrderSpec::Vector &aOrderSpecs,
60  const Expression::Ptr &op,
61  ReturnOrderBy *const returnOrderBy) : SingleContainer(op)
62  , m_stability(stability)
63  , m_orderSpecs(aOrderSpecs)
64  , m_returnOrderBy(returnOrderBy)
65 {
67 }
68 
70  const StaticContext::Ptr &context)
71 {
72  m_expr = source;
73  const ItemType::Ptr t(source->staticType()->itemType());
74  prepareComparison(fetchComparator(t, t, context));
75 }
76 
84 template<>
85 class qLess<Item::List>
86 {
87 private:
88 
89  static inline bool isNaN(const Item &i)
90  {
91  return BuiltinTypes::xsDouble->xdtTypeMatches(i.type()) &&
92  i.as<Numeric>()->isNaN();
93  }
94 
95 public:
96  inline qLess(const OrderBy::OrderSpec::Vector &orderspecs,
97  const DynamicContext::Ptr &context) : m_orderSpecs(orderspecs)
98  , m_context(context)
99  {
101  Q_ASSERT(context);
102  }
103 
104  inline bool operator()(const Item &item1, const Item &item2) const
105  {
106  const SortTuple *const s1 = item1.as<SortTuple>();
107  const SortTuple *const s2 = item2.as<SortTuple>();
108 
109  const Item::Vector &sortKeys1 = s1->sortKeys();
110  const Item::Vector &sortKeys2 = s2->sortKeys();
111  const int len = sortKeys1.count();
112  Q_ASSERT(sortKeys1.count() == sortKeys2.count());
113 
114  for(int i = 0; i < len; ++i)
115  {
116  const Item &i1 = sortKeys1.at(i);
117  const Item &i2 = sortKeys2.at(i);
118  const OrderBy::OrderSpec &orderSpec = m_orderSpecs.at(i);
119 
120  if(!i1)
121  {
122  if(i2 && !isNaN(i2))
123  {
124  /* We got ((), item()). */
127  }
128  else
129  return false;
130  }
131 
132  if(!i2)
133  {
134  if(i1 && !isNaN(i1))
135  /* We got (item(), ()). */
138  else
139  return false;
140  }
141 
144  const AtomicComparator::ComparisonResult result = orderSpec.detailedFlexibleCompare(i1, i2, m_context);
145 
146  switch(result)
147  {
149  return orderSpec.direction == OrderBy::OrderSpec::Ascending;
151  return orderSpec.direction != OrderBy::OrderSpec::Ascending;
153  continue;
155  Q_ASSERT_X(false, Q_FUNC_INFO, "This code path assume values are always comparable.");
156  }
157  }
158 
159  return false;
160  }
161 
162 private:
163  /* Yes, we store references here. */
166 };
167 
169  const DynamicContext::Ptr &) const
170 {
171  return i.as<SortTuple>()->value();
172 }
173 
175 {
176  Item::List tuples(m_operand->evaluateSequence(context)->toList());
177 
178  const qLess<Item::List> sorter(m_orderSpecs, context);
179 
181 
182  /* On one hand we could just disregard stability and always use qStableSort(), but maybe qSort()
183  * is a bit faster? */
184  if(m_stability == StableOrder)
185  qStableSort(tuples.begin(), tuples.end(), sorter);
186  else
187  {
189  qSort(tuples.begin(), tuples.end(), sorter);
190  }
191 
192  return makeSequenceMappingIterator<Item>(ConstPtr(this),
193  makeListIterator(tuples),
194  context);
195 }
196 
198  const SequenceType::Ptr &reqType)
199 {
200  m_returnOrderBy->setStay(true);
201 
202  /* It's important we do the typeCheck() before calling OrderSpec::prepare(), since
203  * atomizers must first be inserted. */
204  const Expression::Ptr me(SingleContainer::typeCheck(context, reqType));
205 
207  const int len = ops.count();
208  Q_ASSERT(ops.count() > 1);
209  Q_ASSERT(m_orderSpecs.count() == ops.count() - 1);
210 
211  for(int i = 1; i < len; ++i)
212  m_orderSpecs[i - 1].prepare(ops.at(i), context);
213 
214  return me;
215 
216  /* It's not meaningful to sort a single item or less, so rewrite ourselves
217  * away if that is the case. This is an optimization. */
218  /* TODO: How do we remove ReturnOrderBy?
219  if(Cardinality::zeroOrOne().isMatch(m_operand->staticType()->cardinality()))
220  return m_operand->typeCheck(context, reqType);
221  else
222  return SingleContainer::typeCheck(context, reqType);
223  */
224 }
225 
227 {
229 }
230 
232 {
233  /* If we only will produce one item, there's no point in sorting. */
235  return SingleContainer::compress(context);
236  else
237  {
238  m_returnOrderBy->setStay(false);
239  return m_operand->compress(context);
240  }
241 }
242 
244 {
245  return m_operand->staticType();
246 }
247 
249 {
250  SequenceType::List result;
252  return result;
253 }
254 
257 {
258  return visitor->visit(this);
259 }
260 
static bool isNaN(const Item &i)
Definition: qorderby.cpp:89
#define QT_END_NAMESPACE
This macro expands to.
Definition: qglobal.h:90
Item::Iterator::Ptr mapToSequence(const Item &i, const DynamicContext::Ptr &context) const
Definition: qorderby.cpp:168
const Stability m_stability
Definition: qorderby_p.h:170
virtual Properties properties() const
Definition: qorderby.cpp:226
static const SequenceType::Ptr ZeroOrMoreItems
int count(const T &t) const
Returns the number of occurrences of value in the vector.
Definition: qvector.h:742
Together with OrderBy, it implements XQuery 1.0&#39;s order by expression.
const DynamicContext::Ptr & m_context
Definition: qorderby.cpp:165
QList< Expression::Ptr > List
LessThan qLess()
Definition: qalgorithms.h:146
ReturnOrderBy *const m_returnOrderBy
Definition: qorderby_p.h:172
virtual Expression::Ptr typeCheck(const StaticContext::Ptr &context, const SequenceType::Ptr &reqType)
Definition: qexpression.cpp:70
QAbstractXmlForwardIterator< T >::Ptr makeListIterator(const QList< T > &list)
int count(const T &t) const
Returns the number of occurrences of value in the list.
Definition: qlist.h:891
#define Q_ASSERT(cond)
Definition: qglobal.h:1823
virtual Item::Iterator::Ptr evaluateSequence(const DynamicContext::Ptr &context) const
Definition: qorderby.cpp:174
Functor used by Qt&#39;s qSort() and qStableSort(). Used for FLWOR&#39;s order by expression.
Definition: qorderby.cpp:85
virtual Expression::Ptr compress(const StaticContext::Ptr &context)
void setStay(const bool a)
void append(const T &t)
Inserts value at the end of the list.
Definition: qlist.h:507
virtual SequenceType::List expectedOperandTypes() const
Definition: qorderby.cpp:248
#define QT_BEGIN_NAMESPACE
This macro expands to.
Definition: qglobal.h:89
virtual Expression::List operands() const
StaticContext::OrderingEmptySequence orderingEmptySequence
Definition: qorderby_p.h:137
QExplicitlySharedDataPointer< const OrderBy > ConstPtr
Definition: qorderby_p.h:168
OrderSpec::Vector m_orderSpecs
Definition: qorderby_p.h:171
void prepare(const Expression::Ptr &source, const StaticContext::Ptr &context)
Definition: qorderby.cpp:69
The namespace for the internal API of QtXmlPatterns.
static const AtomicType::Ptr xsDouble
QVector< Item > Vector
Definition: qitem_p.h:200
virtual Cardinality cardinality() const =0
QExplicitlySharedDataPointer< ItemType > type() const
Returns the ItemType this Item is of.
Definition: qitem_p.h:365
void qSort(RandomAccessIterator start, RandomAccessIterator end)
Definition: qalgorithms.h:177
virtual SequenceType::Ptr staticType() const
Definition: qorderby.cpp:243
const T & at(int i) const
Returns the item at index position i in the vector.
Definition: qvector.h:350
void qStableSort(RandomAccessIterator start, RandomAccessIterator end)
Definition: qalgorithms.h:202
Represents a value and its sort keys in FLOWR&#39;s order by clause.
Definition: qsorttuple_p.h:81
virtual ExpressionVisitorResult::Ptr accept(const ExpressionVisitor::Ptr &visitor) const
Definition: qorderby.cpp:256
virtual SequenceType::Ptr staticType() const =0
#define Q_ASSERT_X(cond, where, what)
Definition: qglobal.h:1837
Contains functions used for formatting arguments, such as keywords and paths, in translated strings...
Represents an item in the XPath 2.0 Data Model.
Definition: qitem_p.h:182
Base class for all numeric values.
OrderBy(const Stability stability, const OrderSpec::Vector &orderSpecs, const Expression::Ptr &operand, ReturnOrderBy *const returnOrderBy)
Definition: qorderby.cpp:58
Contains class Numeric. This file was originally called qnumeric_p.h, but various build systems canno...
const Item::Vector & sortKeys() const
Definition: qsorttuple_p.h:128
virtual Properties properties() const
virtual Expression::Ptr typeCheck(const StaticContext::Ptr &context, const SequenceType::Ptr &reqType)
Definition: qorderby.cpp:197
virtual bool isNaN() const =0
virtual Expression::Ptr compress(const StaticContext::Ptr &context)
Definition: qorderby.cpp:231
bool isEmpty() const
Returns true if the vector has size 0; otherwise returns false.
Definition: qvector.h:139
AtomicComparator::ComparisonResult detailedFlexibleCompare(const Item &it1, const Item &it2, const DynamicContext::Ptr &context) const
like flexibleCompare(), but returns the result as an AtomicComparator::Operator instead of bool...
The QFlags class provides a type-safe way of storing OR-combinations of enum values.
Definition: qglobal.h:2313
virtual ItemType::Ptr itemType() const =0
TCastTarget * as() const
Definition: qitem_p.h:278
bool operator()(const Item &item1, const Item &item2) const
Definition: qorderby.cpp:104
const OrderBy::OrderSpec::Vector & m_orderSpecs
Definition: qorderby.cpp:164
qLess(const OrderBy::OrderSpec::Vector &orderspecs, const DynamicContext::Ptr &context)
Definition: qorderby.cpp:96
virtual Item::Iterator::Ptr evaluateSequence(const DynamicContext::Ptr &context) const
Base class for expressions that has exactly one operand.
#define Q_FUNC_INFO
Definition: qglobal.h:1871