tpl_indexArc.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_INDEXARC_H
# define TPL_INDEXARC_H

# include <tpl_dynSetTree.H>
# include <tpl_graph.H>

using namespace Aleph;

namespace Aleph
{


  template <
    class GT,
    template <class /* Key */, class /* Compare */> class Tree = Rand_Tree,
    class SA = Dft_Show_Arc<GT>
    >
  class IndexArc
  {
  private:

    typedef typename GT::Arc GT_Arc;
    typedef typename GT::Node GT_Node;
    typedef typename GT::Arc_Type GT_Arc_Type;
    typedef typename GT::Node_Type GT_Node_Type;

    typedef std::pair<void*, void*> Node_Pair;

    struct Cmp_Arc
    {
      bool operator () (GT_Arc * a1, GT_Arc * a2) const
      {
        if (a1->src_node < a2->src_node)
          return true;

        return not (a2->src_node < a1->src_node) and a1->tgt_node < a2->tgt_node;
      }
    };

    GT & g;
    DynSetTree <GT_Arc *, Tree, Cmp_Arc> index;
    SA & sa;

  public:

    GT_Arc * insert(GT_Arc * e)
    {
      return *index.put(e);
    }

    GT_Arc * search(void * src, void * tgt)
    {
      GT_Arc arc;
      arc.src_node = src;
      arc.tgt_node = tgt;

      GT_Arc ** ret_val = index.search(&arc);

      if (ret_val != nullptr)
        return *ret_val;

      if (g.is_digraph())
        return nullptr;

      std::swap(arc.src_node, arc.tgt_node);
      ret_val = index.search(&arc);

      if (ret_val == nullptr)
        return nullptr;

      assert(((src == (*ret_val)->src_node) and (tgt == (*ret_val)->tgt_node)) or
             ((tgt == (*ret_val)->src_node) and (src == (*ret_val)->tgt_node)));

      return *ret_val;
    }

    GT_Arc * search_directed(void * src, void * tgt)
    {
      GT_Arc arc;
      arc.src_node = src;
      arc.tgt_node = tgt;

      GT_Arc ** ret_val = index.search(&arc);

      return ret_val != nullptr ? *ret_val : nullptr;
    }

    GT_Arc * search(GT_Arc * a)
    {
      return search(a->src_node, a->tgt_node);
    }

    GT_Arc * insert_in_graph(GT_Node * src, GT_Node * tgt,
                             const GT_Arc_Type & info)
    {
      GT_Arc * a = search(src, tgt);

      if (a != nullptr)
        throw std::domain_error("There is already in arc between these nodes");

      a = g.insert_arc(src, tgt, info);
      insert(a);

      return a;
    }

    GT_Arc * insert_in_graph(GT_Node * src, GT_Node * tgt,
                             GT_Arc_Type && info = GT_Arc_Type())
    {
      GT_Arc * a = search(src, tgt);

      if (a != nullptr)
        throw std::domain_error("There is already in arc between these nodes");

      a = g.insert_arc(src, tgt, std::forward<GT_Arc_Type>(info));
      insert(a);

      return a;
    }

    void remove(GT_Arc * e)
    {
      index.remove(e);
    }

    void remove_from_graph(GT_Arc * a)
    {
      remove(a);
      g.remove_arc(a);
    }

    void clear_index()
    {
      index.empty();
    }

    void build_index()
    {
      for (Arc_Iterator<GT, SA> it(g, sa); it.has_curr(); it.next_ne())
        {
          GT_Arc * a = it.get_curr_ne();
          if (search(a) != a)
            insert(a);
        }
    }

  private:

    void init()
    {
      for (Arc_Iterator<GT, SA> it(g, sa); it.has_curr(); it.next_ne())
        insert(it.get_curr_ne());
    }

  public:

    IndexArc(GT & __g, bool with_init = true, SA && __sa = SA()) 
      : g(__g), sa(__sa)
    {
      if (with_init)
        init();
    }

    IndexArc(GT & __g, bool with_init, SA & __sa) : g(__g), sa(__sa)
    {
      if (with_init)
        init();
    }

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

}

# endif