arrow/compute/ordering.h

0001 // Licensed to the Apache Software Foundation (ASF) under one
0002 // or more contributor license agreements.  See the NOTICE file
0003 // distributed with this work for additional information
0004 // regarding copyright ownership.  The ASF licenses this file
0005 // to you under the Apache License, Version 2.0 (the
0006 // "License"); you may not use this file except in compliance
0007 // with the License.  You may obtain a copy of the License at
0008 //
0009 //   http://www.apache.org/licenses/LICENSE-2.0
0010 //
0011 // Unless required by applicable law or agreed to in writing,
0012 // software distributed under the License is distributed on an
0013 // "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
0014 // KIND, either express or implied.  See the License for the
0015 // specific language governing permissions and limitations
0016 // under the License.
0017
0018 #pragma once
0019
0020 #include <string>
0021 #include <vector>
0022
0023 #include "arrow/type.h"
0024 #include "arrow/util/compare.h"
0025 #include "arrow/util/visibility.h"
0026
0027 namespace arrow {
0028 namespace compute {
0029
0030 enum class SortOrder {
0031   /// Arrange values in increasing order
0032   Ascending,
0033   /// Arrange values in decreasing order
0034   Descending,
0035 };
0036
0037 enum class NullPlacement {
0038   /// Place nulls and NaNs before any non-null values.
0039   /// NaNs will come after nulls.
0040   AtStart,
0041   /// Place nulls and NaNs after any non-null values.
0042   /// NaNs will come before nulls.
0043   AtEnd,
0044 };
0045
0046 /// \brief One sort key for PartitionNthIndices (TODO) and SortIndices
0047 class ARROW_EXPORT SortKey : public util::EqualityComparable<SortKey> {
0048  public:
0049   explicit SortKey(FieldRef target, SortOrder order = SortOrder::Ascending)
0050       : target(std::move(target)), order(order) {}
0051
0052   bool Equals(const SortKey& other) const;
0053   std::string ToString() const;
0054
0055   /// A FieldRef targeting the sort column.
0056   FieldRef target;
0057   /// How to order by this sort key.
0058   SortOrder order;
0059 };
0060
0061 class ARROW_EXPORT Ordering : public util::EqualityComparable<Ordering> {
0062  public:
0063   Ordering(std::vector<SortKey> sort_keys,
0064            NullPlacement null_placement = NullPlacement::AtStart)
0065       : sort_keys_(std::move(sort_keys)), null_placement_(null_placement) {}
0066   /// true if data ordered by other is also ordered by this
0067   ///
0068   /// For example, if data is ordered by [a, b, c] then it is also ordered
0069   /// by [a, b] but not by [b, c] or [a, b, c, d].
0070   ///
0071   /// [a, b].IsSuborderOf([a, b, c]) - true
0072   /// [a, b, c].IsSuborderOf([a, b, c]) - true
0073   /// [b, c].IsSuborderOf([a, b, c]) - false
0074   /// [a, b, c, d].IsSuborderOf([a, b, c]) - false
0075   ///
0076   /// The implicit ordering is not a suborder of any other ordering and
0077   /// no other ordering is a suborder of it.  The implicit ordering is not a
0078   /// suborder of itself.
0079   ///
0080   /// The unordered ordering is a suborder of all other orderings but no
0081   /// other ordering is a suborder of it.  The unordered ordering is a suborder
0082   /// of itself.
0083   ///
0084   /// The unordered ordering is a suborder of the implicit ordering.
0085   bool IsSuborderOf(const Ordering& other) const;
0086
0087   bool Equals(const Ordering& other) const;
0088   std::string ToString() const;
0089
0090   bool is_implicit() const { return is_implicit_; }
0091   bool is_unordered() const { return !is_implicit_ && sort_keys_.empty(); }
0092
0093   const std::vector<SortKey>& sort_keys() const { return sort_keys_; }
0094   NullPlacement null_placement() const { return null_placement_; }
0095
0096   static const Ordering& Implicit() {
0097     static const Ordering kImplicit(true);
0098     return kImplicit;
0099   }
0100
0101   static const Ordering& Unordered() {
0102     static const Ordering kUnordered(false);
0103     // It is also possible to get an unordered ordering by passing in an empty vector
0104     // using the normal constructor.  This is ok and useful when ordering comes from user
0105     // input.
0106     return kUnordered;
0107   }
0108
0109  private:
0110   explicit Ordering(bool is_implicit)
0111       : null_placement_(NullPlacement::AtStart), is_implicit_(is_implicit) {}
0112   /// Column key(s) to order by and how to order by these sort keys.
0113   std::vector<SortKey> sort_keys_;
0114   /// Whether nulls and NaNs are placed at the start or at the end
0115   NullPlacement null_placement_;
0116   bool is_implicit_ = false;
0117 };
0118
0119 }  // namespace compute
0120 }  // namespace arrow