# Copyright 2015 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.

import os
import sys
import unittest

import dag

class DagTestCase(unittest.TestCase):

  def MakeDag(self, links):
    """Make a graph from a description of links.

    Args:
      links: A list of (index, (successor index...)) tuples. Index must equal
        the location of the tuple in the list and are provided to make it easier
        to read.

    Returns:
      A list of Nodes.
    """
    nodes = []
    for i in xrange(len(links)):
      assert i == links[i][0]
      nodes.append(dag.Node(i))
    for l in links:
      for s in l[1]:
        nodes[l[0]].AddSuccessor(nodes[s])
    return nodes

  def SortedIndicies(self, graph, node_filter=None):
    return [n.Index() for n in dag.TopologicalSort(graph, node_filter)]

  def SuccessorIndicies(self, node):
    return [c.Index() for c in node.SortedSuccessors()]

  def test_SimpleSorting(self):
    graph = self.MakeDag([(0, (1,2)),
                          (1, (3,)),
                          (2, ()),
                          (3, (4,)),
                          (4, ()),
                          (5, (6,)),
                          (6, ())])
    self.assertEqual(self.SuccessorIndicies(graph[0]), [1, 2])
    self.assertEqual(self.SuccessorIndicies(graph[1]), [3])
    self.assertEqual(self.SuccessorIndicies(graph[2]), [])
    self.assertEqual(self.SuccessorIndicies(graph[3]), [4])
    self.assertEqual(self.SuccessorIndicies(graph[4]), [])
    self.assertEqual(self.SuccessorIndicies(graph[5]), [6])
    self.assertEqual(self.SuccessorIndicies(graph[6]), [])
    self.assertEqual(self.SortedIndicies(graph), [0, 5, 1, 2, 6, 3, 4])

  def test_SortSiblingsAreGrouped(self):
    graph = self.MakeDag([(0, (1, 2, 3)),
                          (1, (4,)),
                          (2, (5, 6)),
                          (3, (7, 8)),
                          (4, ()),
                          (5, ()),
                          (6, ()),
                          (7, ()),
                          (8, ())])
    self.assertEqual(self.SortedIndicies(graph), [0, 1, 2, 3, 4, 5, 6, 7, 8])

  def test_FilteredSorting(self):
    # 0 is a filtered-out root, which means the subgraph containing 1, 2, 3 and
    # 4 should be ignored. 5 is an unfiltered root, and the subgraph containing
    # 6, 7, 8 and 10 should be sorted. 9 and 11 are filtered out, and should
    # exclude the unfiltred node 12.
    graph = self.MakeDag([(0, (1,)),
                          (1, (2, 3)),
                          (2, ()),
                          (3, (4,)),
                          (4, ()),
                          (5, (6, 7)),
                          (6, (11,)),
                          (7, (8,)),
                          (8, (9, 10)),
                          (9, ()),
                          (10, ()),
                          (11, (12,)),
                          (12, ())])
    self.assertEqual(self.SortedIndicies(
        graph, lambda n: n.Index() not in (0, 3, 9, 11)),
                     [5, 6, 7, 8, 10])


if __name__ == '__main__':
  unittest.main()