tpl_dynMapTree.H

/* Aleph-w

     / \  | | ___ _ __ | |__      __      __
    / _ \ | |/ _ \ '_ \| '_ \ ____\ \ /\ / / Data structures & Algorithms
   / ___ \| |  __/ |_) | | | |_____\ V  V /  version 1.9b
  /_/   \_\_|\___| .__/|_| |_|      \_/\_/   https://github.com/lrleon/Aleph-w
                 |_|         

  This file is part of Aleph-w library

  Copyright (c) 2002-2018 Leandro Rabindranath Leon & Alejandro Mujica

  This program is free software: you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation, either version 3 of the License, or
  (at your option) any later version.

  This program is distributed in the hope that it will be useful, but
  WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with this program. If not, see <https://www.gnu.org/licenses/>.
*/
# ifndef TPL_DYNMAPTREE_H
# define TPL_DYNMAPTREE_H

# include <tpl_dynSetTree.H>
 
using namespace Aleph;

namespace Aleph {

template <
  typename Key, typename Data,
  template <typename, class> class Tree = Avl_Tree,
  class Compare                         = Aleph::less<Key>>
class DynMapTree : 
    public DynSetTree<std::pair<Key, Data>, Tree,
                      Dft_Pair_Cmp<Key, Data, Compare>>
{
  using Pair = std::pair<Key, Data>;

  using Base =
    DynSetTree<std::pair<Key, Data>, Tree, Dft_Pair_Cmp<Key, Data, Compare>>;

public:

  using Base::Base;

  DynMapTree(const DynList<Key> & keys)
  {
    keys.for_each([this] (auto & k) { this->insert(make_pair(k, Data())); });
  }

  DynMapTree() {}

  using Key_Type = Key;

  using Item_Type = Key;

  using Value_Type = Data ;

  // using Base::Base;  // no more need. But I don't remember why I put it
  using Base::insert;

  static Data & get_data(const Key & key) noexcept
  {
    return key_to_pair<Key, Data>(&const_cast<Key&>(key))->second;    
  }

  static const Key & get_key(Data * data_ptr) noexcept
  {
    return data_to_pair<Key, Data>(data_ptr)->first;
  }

  Pair * insert(const Key & key, const Data & data)
  {
    return this->Base::insert(Pair(key, data));
  }

  Pair * insert(const Key & key, Data && data = Data())
  {
    return this->Base::insert(Pair(key, std::forward<Data>(data)));
  }
  
  Pair * insert(Key && key, const Data & data)
  {
    return this->Base::insert(Pair(std::forward<Key>(key), data));
  }

  Pair * insert(Key && key, Data && data = Data())
  {
    return this->Base::insert(Pair(std::forward<Key>(key), 
                                   std::forward<Data>(data)));
  }

  Pair * append(const Key & key, const Data & data)
  {
    return this->Base::insert(Pair(key, data));
  }

  Pair * append(const Key & key, Data && data = Data())
  {
    return this->Base::insert(Pair(key, std::forward<Data>(data)));
  }
  
  Pair * append(Key && key, const Data & data)
  {
    return this->Base::insert(Pair(std::forward<Key>(key), data));
  }

  Pair * append(Key && key, Data && data = Data())
  {
    return this->Base::insert(Pair(std::forward<Key>(key), 
                                   std::forward<Data>(data)));
  }

  Pair * put(const Key & key, const Data & data)
  {
    return insert(key, data);
  }

  Pair * put(const Key & key, Data && data)
  {
    return insert(key, std::forward<Data>(data));
  }

  Pair * put(Key && key, const Data & data)
  {
    return insert(std::forward<Key>(key), data);
  }

  Pair * put(Key && key, Data && data)
  {
    return insert(std::forward<Key>(key), std::forward<Data>(data));
  }

  Data remove(const Key & key)
  {
    Pair p(key, Data());
    return this->del(p).second;
  }

  Data remove(Key && key)
  {
    return this->del(forward<Key>(key), Data()).second;
  }

  Pair * search(const Key & key) const noexcept
  {
    return this->Base::search(Pair(key, Data()));
  }

  Pair * search(Key && key) const noexcept
  {
    return this->Base::search(Pair(move(key), Data()));
  }

  bool has(const Key & key) const noexcept { return search(key) != nullptr; }

  bool has(Key && key) const noexcept { return search(move(key)) != nullptr; }

  bool contains(const Key & key) const noexcept { return has(key); }

  bool contains(Key && key) const noexcept { return has(move(key)); }
  
  Data & find(const Key & key) 
  { 
    return this->Base::find(Pair(key, Data())).second;
  }

  const Data & find(const Key & key) const
  { 
    return this->Base::find(Pair(key, Data())).second;
  }

  Data & operator [] (const Key & key)
  { 
    return this->search_or_insert(Pair(key, Data()))->second;
  }

  const Data & operator [] (const Key & key) const
  {
    return this->find(key);
  }

  Data & operator [] (Key && key)
  { 
    return this->search_or_insert(Pair(move(key), Data()))->second;
  }

  const Data & operator [] (Key && key) const
  {
    return this->find(move(key));
  }

  using Iterator = typename Base::Iterator;

  DynList<Key> keys() const
  {
    return this->template maps<Key>([] (auto p) { return p.first; });
  }

  DynList<Data> values() const
  {
    return this->template maps<Data>([] (auto p) { return p.second; });
  }

  DynList<Data*> values_ptr()
  {
    DynList<Data*> ret;
    for (Iterator it(*this); it.has_curr(); it.next_ne())
      ret.append(&it.get_curr_ne().second);
    return ret;
  }

  DynList<Pair*> items_ptr()
  {
    DynList<Pair*> ret;
    for (Iterator it(*this); it.has_curr(); it.next_ne())
      ret.append(&it.get_curr_ne());
    return ret;
  }
};
} // end namespace Aleph


# include <tpl_binTree.H>
# include <tpl_avl.H>
# include <tpl_rb_tree.H>
# include <tpl_rand_tree.H>
# include <tpl_treap.H>
# include <tpl_treapRk.H>
# include <tpl_splay_tree.H>

namespace Aleph {
  template <typename Key, typename Type, class Compare = Aleph::less<Key> >
  class DynMapBinTree : public DynMapTree<Key, Type, BinTree, Compare> {};

  template <typename Key, typename Type, class Compare = Aleph::less<Key> >
  class DynMapAvlTree : public DynMapTree<Key, Type, Avl_Tree, Compare> {};
    template <typename Key, typename Type, class Compare = Aleph::less<Key> >
    class DynMapRbTree : public DynMapTree<Key, Type, Rb_Tree, Compare>
    { /* empty */ };

    template <typename Key, typename Type, class Compare = Aleph::less<Key> >
    class DynMapRandTree : public DynMapTree<Key, Type, Rand_Tree, Compare>
    { /* empty */ };

    template <typename Key, typename Type, class Compare = Aleph::less<Key> >
    class DynMapTreap : public DynMapTree<Key, Type, Treap, Compare>
    { /* empty */ };

    template <typename Key, typename Type, class Compare = Aleph::less<Key> >
    class DynMapTreapRk : public DynMapTree<Key, Type, Treap_Rk, Compare>
    { /* empty */ };

    template <typename Key, typename Type, class Compare = Aleph::less<Key> >
    class DynMapSplayTree : public DynMapTree<Key, Type, Splay_Tree, Compare>
    { /* empty */ };

  template <typename T, class Op, class C>
DynMapTree<typename C::Item_Type, T> map_unify(const C & c, Op op)
{
  DynMapTree<typename C::Item_Type, T> ret;
  for (auto it = c.get_it(); it.has_curr(); it.next_ne())
    {
      const auto & curr = it.get_curr_ne();
      ret.insert(curr, op(curr));
    }
  return ret;
}

} // end namespace Aleph

# endif /* TPL_DYNMAPTREE_H */