// Copyright 2016 Google Inc. All Rights Reserved.

//

// Licensed under the Apache License, Version 2.0 (the "License");

// you may not use this file except in compliance with the License.

// You may obtain a copy of the License at

//

//     http://www.apache.org/licenses/LICENSE-2.0

//

// Unless required by applicable law or agreed to in writing, software

// distributed under the License is distributed on an "AS-IS" BASIS,

// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

// See the License for the specific language governing permissions and

// limitations under the License.

//

// Author: ericv@google.com (Eric Veach)

#ifndef S2_ID_SET_LEXICON_H_

#define S2_ID_SET_LEXICON_H_

#include <cstddef>

#include <iterator>

#include <limits>

#include <vector>

#include "s2/base/integral_types.h"

#include "s2/base/logging.h"

#include "s2/sequence_lexicon.h"

// IdSetLexicon is a class for compactly representing sets of non-negative

// integers such as array indices ("id sets").  It is especially suitable when

// either (1) there are many duplicate sets, or (2) there are many singleton

// or empty sets.  See also ValueLexicon and SequenceLexicon.

//

// Each distinct id set is mapped to a 32-bit integer.  Empty and singleton

// sets take up no additional space whatsoever; the set itself is represented

// by the unique id assigned to the set. Sets of size 2 or more occupy about

// 11 bytes per set plus 4 bytes per element (as compared to 24 bytes per set

// plus 4 bytes per element for std::vector).  Duplicate sets are

// automatically eliminated.  Note also that id sets are referred to using

// 32-bit integers rather than 64-bit pointers.

//

// This class is especially useful in conjunction with ValueLexicon<T>.  For

// example, suppose that you want to label objects with a set of strings.  You

// could use a ValueLexicon<string> to map the strings to "label ids" (32-bit

// integers), and then use IdSetLexicon to map each set of labels to a "label

// set id".  Each reference to that label set then takes up only 4 bytes.

//

// Example usage:

//

//   ValueLexicon<string> labels_;

//   IdSetLexicon label_sets_;

//

//   int32 GetLabelSet(const vector<string>& label_strings) {

//     vector<int32> label_ids;

//     for (const auto& str : label_strings) {

//       label_ids.push_back(labels_.Add(str));

//     }

//     return label_sets_.Add(label_ids);

//   }

//

//   int label_set_id = GetLabelSet(...);

//   for (auto id : label_sets_.id_set(label_set_id)) {

//     S2_LOG(INFO) << id;

//   }

//

// This class is similar to SequenceLexicon, except:

//

// 1. Empty and singleton sets are represented implicitly; they use no space.

// 2. Sets are represented rather than sequences; values are reordered to be in

//    sorted order, and duplicates are removed.

// 3. The values must be 32-bit non-negative integers (only).

class IdSetLexicon {

 public:

  IdSetLexicon();

  ~IdSetLexicon();

  // IdSetLexicon is movable and copyable.

  IdSetLexicon(const IdSetLexicon&);

  IdSetLexicon& operator=(const IdSetLexicon&);

  IdSetLexicon(IdSetLexicon&&);

  IdSetLexicon& operator=(IdSetLexicon&&);

  // Clears all data from the lexicon.

  void Clear();

  // Add the given set of integers to the lexicon if it is not already

  // present, and return the unique id for this set.  "begin" and "end" are

  // forward iterators over a sequence of values that can be converted to

  // non-negative 32-bit integers.  The values are automatically sorted and

  // duplicates are removed.  Returns a signed integer representing this set.

  //

  // REQUIRES: All values in [begin, end) are non-negative 32-bit integers.

  template <class FwdIterator>

  int32 Add(FwdIterator begin, FwdIterator end);

  // Add the given set of integers to the lexicon if it is not already

  // present, and return the unique id for this set.  This is a convenience

  // method equivalent to Add(std::begin(container), std::end(container)).

  template <class Container>

  int32 Add(const Container& container);

  // Convenience method that returns the unique id for a singleton set.

  // Note that because singleton sets take up no space, this method is

  // const.  Equivalent to calling Add(&id, &id + 1).

  int32 AddSingleton(int32 id) const;

  // Convenience method that returns the unique id for the empty set.  Note

  // that because the empty set takes up no space and has a fixed id, this

  // method is static.  Equivalent to calling Add() with an empty container.

  static int32 EmptySetId();

  // Iterator type; please treat this as an opaque forward iterator.

  using Iterator = const int32*;

  // This class represents a set of integers stored in the IdSetLexicon.

  class IdSet {

   public:

    using value_type = const int32;

    Iterator begin() const;

    Iterator end() const;

    size_t size() const;

   private:

    friend class IdSetLexicon;

    IdSet();

    IdSet(Iterator begin, Iterator end);

    explicit IdSet(int32 singleton_id);

    Iterator begin_, end_;

    int32 singleton_id_;

  };

  // Return the set of integers corresponding to an id returned by Add().

  IdSet id_set(int32 set_id) const;

 private:

  // Choose kEmptySetId to be the last id that will ever be generated.

  // (Non-negative ids are reserved for singleton sets.)

  static constexpr int32 kEmptySetId = std::numeric_limits<int32>::min();

  int32 AddInternal(std::vector<int32>* ids);

  SequenceLexicon<int32> id_sets_;

  std::vector<int32> tmp_;  // temporary storage used during Add()

};

//////////////////   Implementation details follow   ////////////////////

inline IdSetLexicon::Iterator IdSetLexicon::IdSet::begin() const {

  return begin_;

}

inline IdSetLexicon::Iterator IdSetLexicon::IdSet::end() const {

  return end_;

}

inline size_t IdSetLexicon::IdSet::size() const {

  return end_ - begin_;

}

inline IdSetLexicon::IdSet::IdSet()

    : begin_(&singleton_id_), end_(begin_) {

}

inline IdSetLexicon::IdSet::IdSet(Iterator begin, Iterator end)

    : begin_(begin), end_(end) {

}

inline IdSetLexicon::IdSet::IdSet(int32 singleton_id)

    : begin_(&singleton_id_), end_(&singleton_id_ + 1),

      singleton_id_(singleton_id) {

}

inline int32 IdSetLexicon::AddSingleton(int32 id) const {

  S2_DCHECK_GE(id, 0);

  S2_DCHECK_LE(id, std::numeric_limits<int32>::max());

  // Singleton sets are represented by their element.

  return id;

}

/*static*/ inline int32 IdSetLexicon::EmptySetId() {

  return kEmptySetId;

}

template <class FwdIterator>

int32 IdSetLexicon::Add(FwdIterator begin, FwdIterator end) {

  tmp_.clear();

  for (; begin != end; ++begin) {

    S2_DCHECK_GE(*begin, 0);

    S2_DCHECK_LE(*begin, std::numeric_limits<int32>::max());

    tmp_.push_back(*begin);

  }

  return AddInternal(&tmp_);

}

template <class Container>

int32 IdSetLexicon::Add(const Container& container) {

  return Add(std::begin(container), std::end(container));

}

#endif  // S2_ID_SET_LEXICON_H_