// Copyright 2013 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef EXTENSIONS_COMMON_PERMISSIONS_BASE_SET_OPERATORS_H_
#define EXTENSIONS_COMMON_PERMISSIONS_BASE_SET_OPERATORS_H_

#include <iterator>
#include <map>

#include "base/memory/linked_ptr.h"
#include "base/template_util.h"

namespace extensions {

// Traits for template paramater of |BaseSetOperators<T>|. Specializations
// should define |ElementType| for the type of elements to store in the set,
// and |EmementIDType| for the type of element identifiers.
template <typename T>
struct BaseSetOperatorsTraits {};

// Set operations shared by |APIPermissionSet| and |ManifestPermissionSet|.
//
// TODO(rpaquay): It would be nice to remove the need for the sub-classes and
// instead directly use this class where needed.
template <typename T>
class BaseSetOperators {
 public:
  typedef typename BaseSetOperatorsTraits<T>::ElementType ElementType;
  typedef typename BaseSetOperatorsTraits<T>::ElementIDType ElementIDType;
  typedef std::map<ElementIDType, linked_ptr<ElementType> > Map;

  class const_iterator :
    public std::iterator<std::input_iterator_tag, const ElementType*> {
   public:
    const_iterator(const typename Map::const_iterator& it) : it_(it) {}
    const_iterator(const const_iterator& ids_it) : it_(ids_it.it_) {}

    const_iterator& operator++() {
      ++it_;
      return *this;
    }

    const_iterator operator++(int) {
      const_iterator tmp(it_++);
      return tmp;
    }

    bool operator==(const const_iterator& rhs) const {
      return it_ == rhs.it_;
    }

    bool operator!=(const const_iterator& rhs) const {
      return it_ != rhs.it_;
    }

    const ElementType* operator*() const {
      return it_->second.get();
    }

    const ElementType* operator->() const {
      return it_->second.get();
    }

   private:
    typename Map::const_iterator it_;
  };

  BaseSetOperators() {
    // Ensure |T| is convertible to us, so we can safely downcast when calling
    // methods that must exist in |T|.
    COMPILE_ASSERT((base::is_convertible<T*, BaseSetOperators<T>*>::value),
                   U_ptr_must_implicitly_convert_to_T_ptr);
  }

  BaseSetOperators(const T& set) {
    this->operator=(set);
  }

  ~BaseSetOperators() {}

  T& operator=(const T& rhs) {
    return Assign(rhs);
  }

  bool operator==(const T& rhs) const {
    return Equal(rhs);
  }

  bool operator!=(const T& rhs) const {
    return !operator==(rhs);
  }

  T& Assign(const T& rhs) {
    const_iterator it = rhs.begin();
    const const_iterator end = rhs.end();
    while (it != end) {
      insert(it->Clone());
      ++it;
    }
    return *static_cast<T*>(this);
  }

  bool Equal(const T& rhs) const {
    const_iterator it = begin();
    const_iterator rhs_it = rhs.begin();
    const_iterator it_end = end();
    const_iterator rhs_it_end = rhs.end();

    while (it != it_end && rhs_it != rhs_it_end) {
      if (it->id() > rhs_it->id())
        return false;
      else if (it->id() < rhs_it->id())
        return false;
      else if (!it->Equal(*rhs_it))
        return false;
      ++it;
      ++rhs_it;
    }
    return it == it_end && rhs_it == rhs_it_end;
  }

  bool Contains(const T& rhs) const {
    const_iterator it1 = begin();
    const_iterator it2 = rhs.begin();
    const_iterator end1 = end();
    const_iterator end2 = rhs.end();

    while (it1 != end1 && it2 != end2) {
      if (it1->id() > it2->id()) {
        return false;
      } else if (it1->id() < it2->id()) {
        ++it1;
      } else {
          if (!it1->Contains(*it2))
            return false;
        ++it1;
        ++it2;
      }
    }

    return it2 == end2;
  }

  static void Difference(const T& set1, const T& set2, T* set3) {
    CHECK(set3);
    set3->clear();

    const_iterator it1 = set1.begin();
    const_iterator it2 = set2.begin();
    const const_iterator end1 = set1.end();
    const const_iterator end2 = set2.end();

    while (it1 != end1 && it2 != end2) {
      if (it1->id() < it2->id()) {
        set3->insert(it1->Clone());
        ++it1;
      } else if (it1->id() > it2->id()) {
        ++it2;
      } else {
        ElementType* p = it1->Diff(*it2);
        if (p)
          set3->insert(p);
        ++it1;
        ++it2;
      }
    }

    while (it1 != end1) {
      set3->insert(it1->Clone());
      ++it1;
    }
  }

  static void Intersection(const T& set1, const T& set2, T* set3) {
    DCHECK(set3);
    set3->clear();

    const_iterator it1 = set1.begin();
    const_iterator it2 = set2.begin();
    const const_iterator end1 = set1.end();
    const const_iterator end2 = set2.end();

    while (it1 != end1 && it2 != end2) {
      if (it1->id() < it2->id()) {
        ++it1;
      } else if (it1->id() > it2->id()) {
        ++it2;
      } else {
        ElementType* p = it1->Intersect(*it2);
        if (p)
          set3->insert(p);
        ++it1;
        ++it2;
      }
    }
  }

  static void Union(const T& set1, const T& set2, T* set3) {
    DCHECK(set3);
    set3->clear();

    const_iterator it1 = set1.begin();
    const_iterator it2 = set2.begin();
    const const_iterator end1 = set1.end();
    const const_iterator end2 = set2.end();

    while (true) {
      if (it1 == end1) {
        while (it2 != end2) {
          set3->insert(it2->Clone());
          ++it2;
        }
        break;
      }
      if (it2 == end2) {
        while (it1 != end1) {
          set3->insert(it1->Clone());
          ++it1;
        }
        break;
      }
      if (it1->id() < it2->id()) {
        set3->insert(it1->Clone());
        ++it1;
      } else if (it1->id() > it2->id()) {
        set3->insert(it2->Clone());
        ++it2;
      } else {
        set3->insert(it1->Union(*it2));
        ++it1;
        ++it2;
      }
    }
  }

  const_iterator begin() const {
    return const_iterator(map().begin());
  }

  const_iterator end() const {
    return map().end();
  }

  const_iterator find(ElementIDType id) const {
    return map().find(id);
  }

  size_t count(ElementIDType id) const {
    return map().count(id);
  }

  bool empty() const {
    return map().empty();
  }

  size_t erase(ElementIDType id) {
    return map().erase(id);
  }

  // Take ownership and insert |item| into the set.
  void insert(ElementType* item) {
    map_[item->id()].reset(item);
  }

  size_t size() const {
    return map().size();
  }

  const Map& map() const {
    return map_;
  }

  Map& map() {
    return map_;
  }

  void clear() {
    map_.clear();
  }

 private:
  Map map_;
};

}  // namespace extensions

#endif  // EXTENSIONS_COMMON_PERMISSIONS_BASE_SET_OPERATORS_H_