text: //===--- BlotMapVector.h - Map vector with "blot" operation  ----*- C++ -*-===//
  //
  // This source file is part of the Swift.org open source project
  //
  // Copyright (c) 2014 - 2016 Apple Inc. and the Swift project authors
  // Licensed under Apache License v2.0 with Runtime Library Exception
  //
  // See http://swift.org/LICENSE.txt for license information
  // See http://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
  //
  //===----------------------------------------------------------------------===//
  
  #ifndef SWIFT_BASIC_BLOTMAPVECTOR_H
  #define SWIFT_BASIC_BLOTMAPVECTOR_H
  
  #include "llvm/ADT/DenseMap.h"
  #include "swift/Basic/LLVM.h"
  #include "swift/Basic/Range.h"
  #include <vector>
  
  namespace swift {
  
  template <typename KeyT, typename ValueT>
  bool compareKeyAgainstDefaultKey(const std::pair<KeyT, ValueT> &Pair) {
    return Pair.first == KeyT();
  }
  
  /// \brief An associative container with fast insertion-order (deterministic)
  /// iteration over its elements. Plus the special blot operation.
  template <typename KeyT, typename ValueT,
            typename MapTy = llvm::DenseMap<KeyT, size_t>,
            typename VectorTy = std::vector<Optional<std::pair<KeyT, ValueT>>>>
  class BlotMapVector {
      /// Map keys to indices in Vector.
      MapTy Map;
  
      /// Keys and values.
      VectorTy Vector;
  
    public:
      using iterator = typename VectorTy::iterator;
      using const_iterator = typename VectorTy::const_iterator;
      using key_type = KeyT;
      using mapped_type = ValueT;
  
      iterator begin() { return Vector.begin(); }
      iterator end() { return Vector.end(); }
      const_iterator begin() const { return Vector.begin(); }
      const_iterator end() const { return Vector.end(); }
  
      iterator_range<iterator> getItems() {
        return swift::make_range(begin(), end());
      }
  
      ValueT &operator[](const KeyT &Arg) {
        auto Pair = Map.insert(std::make_pair(Arg, size_t(0)));
        if (Pair.second) {
          size_t Num = Vector.size();
          Pair.first->second = Num;
          Vector.push_back({std::make_pair(Arg, ValueT())});
          return (*Vector[Num]).second;
        }
        return Vector[Pair.first->second].getValue().second;
      }
  
      std::pair<iterator, bool>
      insert(const std::pair<KeyT, ValueT> &InsertPair) {
        auto Pair = Map.insert(std::make_pair(InsertPair.first, size_t(0)));
        if (Pair.second) {
          size_t Num = Vector.size();
          Pair.first->second = Num;
          Vector.push_back(InsertPair);
          return std::make_pair(Vector.begin() + Num, true);
        }
        return std::make_pair(Vector.begin() + Pair.first->second, false);
      }
  
      iterator find(const KeyT &Key) {
        typename MapTy::iterator It = Map.find(Key);
        if (It == Map.end()) return Vector.end();
        auto Iter = Vector.begin() + It->second;
        if (!Iter->hasValue())
          return Vector.end();
        return Iter;
      }
  
      const_iterator find(const KeyT &Key) const {
        return const_cast<BlotMapVector &>(*this)->find(Key);
      }
  
      /// This is similar to erase, but instead of removing the element from the
      /// vector, it just zeros out the key in the vector. This leaves iterators
      /// intact, but clients must be prepared for zeroed-out keys when iterating.
      void erase(const KeyT &Key) { blot(Key); }
  
      /// This is similar to erase, but instead of removing the element from the
      /// vector, it just zeros out the key in the vector. This leaves iterators
      /// intact, but clients must be prepared for zeroed-out keys when iterating.
      void erase(iterator I) { erase((*I)->first); }
  
      /// This is similar to erase, but instead of removing the element from the
      /// vector, it just zeros out the key in the vector. This leaves iterators
      /// intact, but clients must be prepared for zeroed-out keys when iterating.
      void blot(const KeyT &Key) {
        typename MapTy::iterator It = Map.find(Key);
        if (It == Map.end()) return;
        Vector[It->second] = None;
        Map.erase(It);
      }
  
      void clear() {
        Map.clear();
        Vector.clear();
      }
  
      unsigned size() const { return Map.size(); }
  
      ValueT lookup(const KeyT &Val) const {
        auto Iter = Map.find(Val);
        if (Iter == Map.end())
          return ValueT();
        auto &P = Vector[Iter->second];
        if (!P.hasValue())
          return ValueT();
        return P->second;
      }
  
      size_t count(const KeyT &Val) const { return Map.count(Val); }
  
      bool empty() const { return Map.empty(); }
    };
  
    template <typename KeyT, typename ValueT, unsigned N,
              typename MapT = llvm::SmallDenseMap<KeyT, size_t, N>,
              typename VectorT =
                  llvm::SmallVector<Optional<std::pair<KeyT, ValueT>>, N>>
    class SmallBlotMapVector : public BlotMapVector<KeyT, ValueT, MapT, VectorT> {
  public:
    SmallBlotMapVector() {}
  };
  
  } // end namespace swift
  
  #endif
  