/*
 * Ceph - scalable distributed file system
 *
 * Copyright (C) 2015 Red Hat, Inc
 *
 * This is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License version 2.1, as published by the Free Software
 * Foundation.  See file COPYING.
 *
 */
#ifndef CEPH_COMPACT_SET_H
#define CEPH_COMPACT_SET_H

#include "buffer.h"
#include "encoding.h"

#include <memory>
#include <set>

template <class T, class Set>
class compact_set_base {
protected:
  std::unique_ptr<Set> set;
  void alloc_internal() {
    if (!set)
      set.reset(new Set);
  }
  void free_internal() {
    set.reset();
  }
  template <class It>
  class iterator_base {
  private:
    const compact_set_base* set;
    It it;
    iterator_base() : set(0) { }
    iterator_base(const compact_set_base* s) : set(s) { }
    iterator_base(const compact_set_base* s, const It& i) : set(s), it(i) { }
    friend class compact_set_base;
  public:
    iterator_base(const iterator_base& o) {
      set = o.set;
      it = o.it;
    }
    bool operator==(const iterator_base& o) const {
      return (set == o.set) && (!set->set || it == o.it);
    }
    bool operator!=(const iterator_base& o) const {
      return !(*this == o);;
    }
    iterator_base& operator=(const iterator_base& o) {
      set->set = o.set;
      it = o.it;
      return *this;
    }
    iterator_base& operator++() {
      ++it;
      return *this;
    }
    iterator_base operator++(int) {
      iterator_base tmp = *this;
      ++it;
      return tmp;
    }
    iterator_base& operator--() {
      --it;
      return *this;
    }
    const T& operator*() {
      return *it;
    }
  };
public:
  class const_iterator : public iterator_base<typename Set::const_iterator> {
    public:
      const_iterator() { }
      const_iterator(const iterator_base<typename Set::const_iterator>& o)
	: iterator_base<typename Set::const_iterator>(o) { }
      const_iterator(const compact_set_base* s) : iterator_base<typename Set::const_iterator>(s) { }
      const_iterator(const compact_set_base* s, const typename Set::const_iterator& i)
	: iterator_base<typename Set::const_iterator>(s, i) { }
  };
  class iterator : public iterator_base<typename Set::iterator> {
    public:
      iterator() { }
      iterator(const iterator_base<typename Set::iterator>& o)
	: iterator_base<typename Set::iterator>(o) { }
      iterator(compact_set_base* s) : iterator_base<typename Set::iterator>(s) { }
      iterator(compact_set_base* s, const typename Set::iterator& i)
	: iterator_base<typename Set::iterator>(s, i) { }
      operator const_iterator() const {
	return const_iterator(this->set, this->it);
      }
  };
  class const_reverse_iterator : public iterator_base<typename Set::const_reverse_iterator> {
    public:
      const_reverse_iterator() { }
      const_reverse_iterator(const iterator_base<typename Set::const_reverse_iterator>& o)
	: iterator_base<typename Set::const_reverse_iterator>(o) { }
      const_reverse_iterator(const compact_set_base* s) : iterator_base<typename Set::const_reverse_iterator>(s) { }
      const_reverse_iterator(const compact_set_base* s, const typename Set::const_reverse_iterator& i)
	: iterator_base<typename Set::const_reverse_iterator>(s, i) { }
  };
  class reverse_iterator : public iterator_base<typename Set::reverse_iterator> {
    public:
      reverse_iterator() { }
      reverse_iterator(const iterator_base<typename Set::reverse_iterator>& o)
	: iterator_base<typename Set::reverse_iterator>(o) { }
      reverse_iterator(compact_set_base* s) : iterator_base<typename Set::reverse_iterator>(s) { }
      reverse_iterator(compact_set_base* s, const typename Set::reverse_iterator& i)
	: iterator_base<typename Set::reverse_iterator>(s, i) { }
      operator const_iterator() const {
	return const_iterator(this->set, this->it);
      }
  };

  compact_set_base() {}
  compact_set_base(const compact_set_base& o) {
    if (o.set) {
      alloc_internal();
      *set = *o.set;
    }
  }
  ~compact_set_base() {}


  bool empty() const {
    return !set || set->empty();
  }
  size_t size() const {
    return set ? set->size() : 0;
  }
  bool operator==(const compact_set_base& o) const {
    return (empty() && o.empty()) || (set && o.set && *set == *o.set);
  }
  bool operator!=(const compact_set_base& o) const {
    return !(*this == o);
  }
  size_t count(const T& t) const {
    return set ? set->count(t) : 0;
  }
  iterator erase (iterator p) {
    if (set) {
      ceph_assert(this == p.set);
      auto it = set->erase(p.it);
      if (set->empty()) {
        free_internal();
        return iterator(this);
      } else {
        return iterator(this, it);
      }
    } else {
      return iterator(this);
    }
  }
  size_t erase (const T& t) {
    if (!set)
      return 0;
    size_t r = set->erase(t);
    if (set->empty())
      free_internal();
    return r;
  }
  void clear() {
    free_internal();
  }
  void swap(compact_set_base& o) {
    set.swap(o.set);
  }
  compact_set_base& operator=(const compact_set_base& o) {
    if (o.set) {
      alloc_internal();
      *set = *o.set;
    } else
      free_internal();
    return *this;
  }
  std::pair<iterator,bool> insert(const T& t) {
    alloc_internal();
    std::pair<typename Set::iterator,bool> r = set->insert(t);
    return std::make_pair(iterator(this, r.first), r.second);
  }
  template <class... Args>
  std::pair<iterator,bool> emplace ( Args&&... args ) {
    alloc_internal();
    auto em = set->emplace(std::forward<Args>(args)...);
    return std::pair<iterator,bool>(iterator(this, em.first), em.second);
  }

  iterator begin() {
   if (!set)
     return iterator(this);
   return iterator(this, set->begin());
  }
  iterator end() {
   if (!set)
     return iterator(this);
   return iterator(this, set->end());
  }
  reverse_iterator rbegin() {
   if (!set)
     return reverse_iterator(this);
   return reverse_iterator(this, set->rbegin());
  }
  reverse_iterator rend() {
   if (!set)
     return reverse_iterator(this);
   return reverse_iterator(this, set->rend());
  }
  iterator find(const T& t) {
    if (!set)
      return iterator(this);
    return iterator(this, set->find(t));
  }
  iterator lower_bound(const T& t) {
    if (!set)
      return iterator(this);
    return iterator(this, set->lower_bound(t));
  }
  iterator upper_bound(const T& t) {
    if (!set)
      return iterator(this);
    return iterator(this, set->upper_bound(t));
  }
  const_iterator begin() const {
   if (!set)
     return const_iterator(this);
   return const_iterator(this, set->begin());
  }
  const_iterator end() const {
   if (!set)
     return const_iterator(this);
   return const_iterator(this, set->end());
  }
  const_reverse_iterator rbegin() const {
   if (!set)
     return const_reverse_iterator(this);
   return const_reverse_iterator(this, set->rbegin());
  }
  const_reverse_iterator rend() const {
   if (!set)
     return const_reverse_iterator(this);
   return const_reverse_iterator(this, set->rend());
  }
  const_iterator find(const T& t) const {
    if (!set)
      return const_iterator(this);
    return const_iterator(this, set->find(t));
  }
  const_iterator lower_bound(const T& t) const {
    if (!set)
      return const_iterator(this);
    return const_iterator(this, set->lower_bound(t));
  }
  const_iterator upper_bound(const T& t) const {
    if (!set)
      return const_iterator(this);
    return const_iterator(this, set->upper_bound(t));
  }
  void encode(ceph::buffer::list &bl) const {
    using ceph::encode;
    if (set)
      encode(*set, bl);
    else
      encode((uint32_t)0, bl);
  }
  void decode(ceph::buffer::list::const_iterator& p) {
    using ceph::decode;
    uint32_t n;
    decode(n, p);
    if (n > 0) {
      alloc_internal();
      ceph::decode_nohead(n, *set, p);
    } else
      free_internal();
  }
};

template<class T, class Set>
inline void encode(const compact_set_base<T, Set>& m, ceph::buffer::list& bl) {
  m.encode(bl);
}
template<class T, class Set>
inline void decode(compact_set_base<T, Set>& m, ceph::buffer::list::const_iterator& p) {
  m.decode(p);
}

template <class T, class Compare = std::less<T>, class Alloc = std::allocator<T> >
class compact_set : public compact_set_base<T, std::set<T, Compare, Alloc> > {
};

template <class T, class Compare = std::less<T>, class Alloc = std::allocator<T> >
inline std::ostream& operator<<(std::ostream& out, const compact_set<T,Compare,Alloc>& s)
{
  bool first = true;
  for (auto &v : s) {
    if (!first)
      out << ",";
    out << v;
    first = false;
  }
  return out;
}
#endif