gitweb.ps.run Git - toc/blob - antlr4-cpp-runtime-4.9.2-source/runtime/src/misc/IntervalSet.h

   1 /* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved.
   2  * Use of this file is governed by the BSD 3-clause license that
   3  * can be found in the LICENSE.txt file in the project root.
   4  */
   5
   6 #pragma once
   7
   8 #include "misc/Interval.h"
   9 #include "Exceptions.h"
  10
  11 namespace antlr4 {
  12 namespace misc {
  13
  14   /**
  15    * This class implements the {@link IntSet} backed by a sorted array of
  16    * non-overlapping intervals. It is particularly efficient for representing
  17    * large collections of numbers, where the majority of elements appear as part
  18    * of a sequential range of numbers that are all part of the set. For example,
  19    * the set { 1, 2, 3, 4, 7, 8 } may be represented as { [1, 4], [7, 8] }.
  20    *
  21    * <p>
  22    * This class is able to represent sets containing any combination of values in
  23    * the range {@link Integer#MIN_VALUE} to {@link Integer#MAX_VALUE}
  24    * (inclusive).</p>
  25    */
  26   class ANTLR4CPP_PUBLIC IntervalSet {
  27   public:
  28     static IntervalSet const COMPLETE_CHAR_SET;
  29     static IntervalSet const EMPTY_SET;
  30
  31   private:
  32     /// The list of sorted, disjoint intervals.
  33     std::vector<Interval> _intervals;
  34
  35     explicit IntervalSet(std::vector<Interval>&& intervals);
  36
  37   public:
  38     IntervalSet();
  39     IntervalSet(IntervalSet const& set);
  40     IntervalSet(IntervalSet&& set);
  41
  42     template<typename T1, typename... T_NEXT>
  43     IntervalSet(int, T1 t1, T_NEXT&&... next) : IntervalSet() {
  44       // The first int argument is an ignored count for compatibility
  45       // with the previous varargs based interface.
  46       addItems(t1, std::forward<T_NEXT>(next)...);
  47     }
  48
  49     IntervalSet& operator=(IntervalSet const& set);
  50     IntervalSet& operator=(IntervalSet&& set);
  51
  52     /// Create a set with a single element, el.
  53     static IntervalSet of(ssize_t a);
  54
  55     /// Create a set with all ints within range [a..b] (inclusive)
  56     static IntervalSet of(ssize_t a, ssize_t b);
  57
  58     void clear();
  59
  60     /// Add a single element to the set.  An isolated element is stored
  61     /// as a range el..el.
  62     void add(ssize_t el);
  63
  64     /// Add interval; i.e., add all integers from a to b to set.
  65     /// If b<a, do nothing.
  66     /// Keep list in sorted order (by left range value).
  67     /// If overlap, combine ranges.  For example,
  68     /// If this is {1..5, 10..20}, adding 6..7 yields
  69     /// {1..5, 6..7, 10..20}.  Adding 4..8 yields {1..8, 10..20}.
  70     void add(ssize_t a, ssize_t b);
  71
  72     /// combine all sets in the array returned the or'd value
  73     static IntervalSet Or(const std::vector<IntervalSet> &sets);
  74
  75     // Copy on write so we can cache a..a intervals and sets of that.
  76     void add(const Interval &addition);
  77     IntervalSet& addAll(const IntervalSet &set);
  78
  79     template<typename T1, typename... T_NEXT>
  80     void addItems(T1 t1, T_NEXT&&... next) {
  81       add(t1);
  82       addItems(std::forward<T_NEXT>(next)...);
  83     }
  84
  85     IntervalSet complement(ssize_t minElement, ssize_t maxElement) const;
  86
  87     /// Given the set of possible values (rather than, say UNICODE or MAXINT),
  88     /// return a new set containing all elements in vocabulary, but not in
  89     /// this.  The computation is (vocabulary - this).
  90     ///
  91     /// 'this' is assumed to be either a subset or equal to vocabulary.
  92     IntervalSet complement(const IntervalSet &vocabulary) const;
  93
  94     /// Compute this-other via this&~other.
  95     /// Return a new set containing all elements in this but not in other.
  96     /// other is assumed to be a subset of this;
  97     /// anything that is in other but not in this will be ignored.
  98     IntervalSet subtract(const IntervalSet &other) const;
  99
 100     /**
 101      * Compute the set difference between two interval sets. The specific
 102      * operation is {@code left - right}. If either of the input sets is
 103      * {@code null}, it is treated as though it was an empty set.
 104      */
 105     static IntervalSet subtract(const IntervalSet &left, const IntervalSet &right);
 106
 107     IntervalSet Or(const IntervalSet &a) const;
 108
 109     /// Return a new set with the intersection of this set with other.  Because
 110     /// the intervals are sorted, we can use an iterator for each list and
 111     /// just walk them together.  This is roughly O(min(n,m)) for interval
 112     /// list lengths n and m.
 113     IntervalSet And(const IntervalSet &other) const;
 114
 115     /// Is el in any range of this set?
 116     bool contains(size_t el) const; // For mapping of e.g. Token::EOF to -1 etc.
 117     bool contains(ssize_t el) const;
 118
 119     /// return true if this set has no members
 120     bool isEmpty() const;
 121
 122     /// If this set is a single integer, return it otherwise Token.INVALID_TYPE.
 123     ssize_t getSingleElement() const;
 124
 125     /**
 126      * Returns the maximum value contained in the set.
 127      *
 128      * @return the maximum value contained in the set. If the set is empty, this
 129      * method returns {@link Token#INVALID_TYPE}.
 130      */
 131     ssize_t getMaxElement() const;
 132
 133     /**
 134      * Returns the minimum value contained in the set.
 135      *
 136      * @return the minimum value contained in the set. If the set is empty, this
 137      * method returns {@link Token#INVALID_TYPE}.
 138      */
 139     ssize_t getMinElement() const;
 140
 141     /// <summary>
 142     /// Return a list of Interval objects. </summary>
 143     std::vector<Interval> const& getIntervals() const;
 144
 145     size_t hashCode() const;
 146
 147     /// Are two IntervalSets equal?  Because all intervals are sorted
 148     ///  and disjoint, equals is a simple linear walk over both lists
 149     ///  to make sure they are the same.
 150     bool operator == (const IntervalSet &other) const;
 151     std::string toString() const;
 152     std::string toString(bool elemAreChar) const;
 153
 154     /**
 155      * @deprecated Use {@link #toString(Vocabulary)} instead.
 156      */
 157     std::string toString(const std::vector<std::string> &tokenNames) const;
 158     std::string toString(const dfa::Vocabulary &vocabulary) const;
 159
 160   protected:
 161     /**
 162      * @deprecated Use {@link #elementName(Vocabulary, int)} instead.
 163      */
 164     std::string elementName(const std::vector<std::string> &tokenNames, ssize_t a) const;
 165     std::string elementName(const dfa::Vocabulary &vocabulary, ssize_t a) const;
 166
 167   public:
 168     size_t size() const;
 169     std::vector<ssize_t> toList() const;
 170     std::set<ssize_t> toSet() const;
 171
 172     /// Get the ith element of ordered set.  Used only by RandomPhrase so
 173     /// don't bother to implement if you're not doing that for a new
 174     /// ANTLR code gen target.
 175     ssize_t get(size_t i) const;
 176     void remove(size_t el); // For mapping of e.g. Token::EOF to -1 etc.
 177     void remove(ssize_t el);
 178
 179   private:
 180     void addItems() { /* No-op */ }
 181   };
 182
 183 } // namespace atn
 184 } // namespace antlr4
 185
 186 // Hash function for IntervalSet.
 187
 188 namespace std {
 189   using antlr4::misc::IntervalSet;
 190
 191   template <> struct hash<IntervalSet>
 192   {
 193     size_t operator() (const IntervalSet &x) const
 194     {
 195       return x.hashCode();
 196     }
 197   };
 198 }