// Copyright 2018 Google Inc. All Rights Reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS-IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//

// Author: ericv@google.com (Eric Veach)

#include "s2/s2builderutil_lax_polygon_layer.h"

#include <algorithm>
#include <memory>
#include "s2/third_party/absl/memory/memory.h"
#include "s2/s2builderutil_find_polygon_degeneracies.h"
#include "s2/s2debug.h"

using std::vector;

using EdgeType = S2Builder::EdgeType;
using Graph = S2Builder::Graph;
using GraphOptions = S2Builder::GraphOptions;
using Label = S2Builder::Label;

using DegenerateEdges = GraphOptions::DegenerateEdges;
using DuplicateEdges = GraphOptions::DuplicateEdges;
using SiblingPairs = GraphOptions::SiblingPairs;

using Edge = Graph::Edge;
using EdgeId = Graph::EdgeId;
using InputEdgeIdSetId = Graph::InputEdgeIdSetId;
using LoopType = Graph::LoopType;

namespace s2builderutil {

using DegenerateBoundaries = LaxPolygonLayer::Options::DegenerateBoundaries;

LaxPolygonLayer::LaxPolygonLayer(S2LaxPolygonShape* polygon,
                                 const Options& options) {
  Init(polygon, nullptr, nullptr, options);
}

LaxPolygonLayer::LaxPolygonLayer(
    S2LaxPolygonShape* polygon, LabelSetIds* label_set_ids,
    IdSetLexicon* label_set_lexicon, const Options& options) {
  Init(polygon, label_set_ids, label_set_lexicon, options);
}

void LaxPolygonLayer::Init(
    S2LaxPolygonShape* polygon, LabelSetIds* label_set_ids,
    IdSetLexicon* label_set_lexicon, const Options& options) {
  S2_DCHECK_EQ(label_set_ids == nullptr, label_set_lexicon == nullptr);
  polygon_ = polygon;
  label_set_ids_ = label_set_ids;
  label_set_lexicon_ = label_set_lexicon;
  options_ = options;
}

GraphOptions LaxPolygonLayer::graph_options() const {
  if (options_.degenerate_boundaries() == DegenerateBoundaries::DISCARD) {
    // There should not be any duplicate edges, but if there are then we keep
    // them since this yields more comprehensible error messages.
    return GraphOptions(options_.edge_type(), DegenerateEdges::DISCARD,
                        DuplicateEdges::KEEP, SiblingPairs::DISCARD);
  } else {
    // Keep at most one copy of each sibling pair and each isolated vertex.
    // We need DuplicateEdges::MERGE because DegenerateEdges::DISCARD_EXCESS
    // can still keep multiple copies (it only discards degenerate edges that
    // are connected to non-degenerate edges).
    return GraphOptions(options_.edge_type(), DegenerateEdges::DISCARD_EXCESS,
                        DuplicateEdges::MERGE, SiblingPairs::DISCARD_EXCESS);
  }
}

void LaxPolygonLayer::AppendPolygonLoops(
    const Graph& g, const vector<Graph::EdgeLoop>& edge_loops,
    vector<vector<S2Point>>* loops) const {
  for (const auto& edge_loop : edge_loops) {
    vector<S2Point> vertices;
    vertices.reserve(edge_loop.size());
    for (auto edge_id : edge_loop) {
      vertices.push_back(g.vertex(g.edge(edge_id).first));
    }
    loops->push_back(std::move(vertices));
  }
}

void LaxPolygonLayer::AppendEdgeLabels(
    const Graph& g,
    const vector<Graph::EdgeLoop>& edge_loops) {
  if (!label_set_ids_) return;

  vector<Label> labels;  // Temporary storage for labels.
  Graph::LabelFetcher fetcher(g, options_.edge_type());
  for (const auto& edge_loop : edge_loops) {
    vector<LabelSetId> loop_label_set_ids;
    loop_label_set_ids.reserve(edge_loop.size());
    for (auto edge_id : edge_loop) {
      fetcher.Fetch(edge_id, &labels);
      loop_label_set_ids.push_back(label_set_lexicon_->Add(labels));
    }
    label_set_ids_->push_back(std::move(loop_label_set_ids));
  }
}

// Returns all edges of "g" except for those identified by "edges_to_discard".
static void DiscardEdges(const Graph& g, const vector<EdgeId>& edges_to_discard,
                         vector<Edge>* new_edges,
                         vector<InputEdgeIdSetId>* new_input_edge_id_set_ids) {
  S2_DCHECK(std::is_sorted(edges_to_discard.begin(), edges_to_discard.end()));
  new_edges->clear();
  new_input_edge_id_set_ids->clear();
  new_edges->reserve(g.num_edges());
  new_input_edge_id_set_ids->reserve(g.num_edges());
  auto it = edges_to_discard.begin();
  for (int e = 0; e < g.num_edges(); ++e) {
    if (it != edges_to_discard.end() && e == *it) {
      ++it;
    } else {
      new_edges->push_back(g.edge(e));
      new_input_edge_id_set_ids->push_back(g.input_edge_id_set_id(e));
    }
  }
  S2_DCHECK(it == edges_to_discard.end());
}

static void MaybeAddFullLoop(
    const Graph& g, vector<vector<S2Point>>* loops, S2Error* error) {
  if (g.IsFullPolygon(error)) {
    loops->push_back({});  // Full loop.
  }
}
void LaxPolygonLayer::BuildDirected(Graph g, S2Error* error) {
  // Some cases are implemented by constructing a new graph with certain
  // degenerate edges removed (overwriting "g").  "new_edges" is where the
  // edges for the new graph are stored.
  vector<Edge> new_edges;
  vector<InputEdgeIdSetId> new_input_edge_id_set_ids;
  vector<vector<S2Point>> loops;
  auto degenerate_boundaries = options_.degenerate_boundaries();
  if (degenerate_boundaries == DegenerateBoundaries::DISCARD) {
    // This is the easiest case, since there are no degeneracies.
    if (g.num_edges() == 0) MaybeAddFullLoop(g, &loops, error);
  } else if (degenerate_boundaries == DegenerateBoundaries::KEEP) {
    // S2LaxPolygonShape doesn't need to distinguish degenerate shells from
    // holes except when the entire graph is degenerate, in which case we need
    // to decide whether it represents an empty polygons possibly with
    // degenerate shells, or a full polygon possibly with degenerate holes.
    if (s2builderutil::IsFullyDegenerate(g)) {
      MaybeAddFullLoop(g, &loops, error);
    }
  } else {
    // For DISCARD_SHELLS and DISCARD_HOLES we first determine whether any
    // degenerate loops of the given type exist, and if so we construct a new
    // graph with those edges removed (overwriting "g").
    bool discard_holes =
        (degenerate_boundaries == DegenerateBoundaries::DISCARD_HOLES);
    auto degeneracies = s2builderutil::FindPolygonDegeneracies(g, error);
    if (!error->ok()) return;
    if (degeneracies.size() == g.num_edges()) {
      if (degeneracies.empty()) {
        MaybeAddFullLoop(g, &loops, error);
      } else if (degeneracies[0].is_hole) {
        loops.push_back({});  // Full loop.
      }
    }
    vector<EdgeId> edges_to_discard;
    for (auto degeneracy : degeneracies) {
      if (degeneracy.is_hole == discard_holes) {
        edges_to_discard.push_back(degeneracy.edge_id);
      }
    }
    if (!edges_to_discard.empty()) {
      // Construct a new graph that discards the unwanted edges.
      std::sort(edges_to_discard.begin(), edges_to_discard.end());
      DiscardEdges(g, edges_to_discard, &new_edges, &new_input_edge_id_set_ids);
      g = Graph(g.options(), &g.vertices(),
                &new_edges, &new_input_edge_id_set_ids,
                &g.input_edge_id_set_lexicon(), &g.label_set_ids(),
                &g.label_set_lexicon(), g.is_full_polygon_predicate());
    }
  }
  vector<Graph::EdgeLoop> edge_loops;
  if (!g.GetDirectedLoops(LoopType::CIRCUIT, &edge_loops, error)) {
    return;
  }
  AppendPolygonLoops(g, edge_loops, &loops);
  AppendEdgeLabels(g, edge_loops);
  vector<Graph::EdgeLoop>().swap(edge_loops);  // Release memory
  vector<Edge>().swap(new_edges);
  vector<InputEdgeIdSetId>().swap(new_input_edge_id_set_ids);
  polygon_->Init(loops);
}

void LaxPolygonLayer::Build(const Graph& g, S2Error* error) {
  if (label_set_ids_) label_set_ids_->clear();
  if (g.options().edge_type() == EdgeType::DIRECTED) {
    BuildDirected(g, error);
  } else {
    error->Init(S2Error::UNIMPLEMENTED, "Undirected edges not supported yet");
  }
}

}  // namespace s2builderutil