#!/usr/bin/python
#

# Copyright (C) 2011, 2012 Google Inc.
# All rights reserved.
#
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions are
# met:
#
# 1. Redistributions of source code must retain the above copyright notice,
# this list of conditions and the following disclaimer.
#
# 2. Redistributions in binary form must reproduce the above copyright
# notice, this list of conditions and the following disclaimer in the
# documentation and/or other materials provided with the distribution.
#
# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
# IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
# TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
# PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
# CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
# EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
# PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
# PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
# LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
# NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
# SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.


"""Script for testing ganeti.utils.algo"""

import unittest
import random
import operator

from ganeti import constants
from ganeti import compat
from ganeti.utils import algo

import testutils


class TestUniqueSequence(unittest.TestCase):
  """Test case for UniqueSequence"""

  def _test(self, input, expected):
    self.assertEqual(algo.UniqueSequence(input), expected)

  def runTest(self):
    # Ordered input
    self._test([1, 2, 3], [1, 2, 3])
    self._test([1, 1, 2, 2, 3, 3], [1, 2, 3])
    self._test([1, 2, 2, 3], [1, 2, 3])
    self._test([1, 2, 3, 3], [1, 2, 3])

    # Unordered input
    self._test([1, 2, 3, 1, 2, 3], [1, 2, 3])
    self._test([1, 1, 2, 3, 3, 1, 2], [1, 2, 3])

    # Strings
    self._test(["a", "a"], ["a"])
    self._test(["a", "b"], ["a", "b"])
    self._test(["a", "b", "a"], ["a", "b"])


class TestFindDuplicates(unittest.TestCase):
  """Test case for FindDuplicates"""

  def _Test(self, seq, expected):
    result = algo.FindDuplicates(seq)
    self.assertEqual(result, algo.UniqueSequence(result))
    self.assertEqual(set(result), set(expected))

  def test(self):
    self._Test([], [])
    self._Test([1, 2, 3], [])
    self._Test([9, 8, 8, 0, 5, 1, 7, 0, 6, 7], [8, 0, 7])
    for exp in [[1, 2, 3], [3, 2, 1]]:
      self._Test([1, 1, 2, 2, 3, 3], exp)

    self._Test(["A", "a", "B"], [])
    self._Test(["a", "A", "a", "B"], ["a"])
    self._Test("Hello World out there!", ["e", " ", "o", "r", "t", "l"])

    self._Test(self._Gen(False), [])
    self._Test(self._Gen(True), range(1, 10))

  @staticmethod
  def _Gen(dup):
    for i in range(10):
      yield i
      if dup:
        for _ in range(i):
          yield i


class TestNiceSort(unittest.TestCase):
  def test(self):
    self.assertEqual(algo.NiceSort([]), [])
    self.assertEqual(algo.NiceSort(["foo"]), ["foo"])
    self.assertEqual(algo.NiceSort(["bar", ""]), ["", "bar"])
    self.assertEqual(algo.NiceSort([",", "."]), [",", "."])
    self.assertEqual(algo.NiceSort(["0.1", "0.2"]), ["0.1", "0.2"])
    self.assertEqual(algo.NiceSort(["0;099", "0,099", "0.1", "0.2"]),
                     ["0,099", "0.1", "0.2", "0;099"])

    data = ["a0", "a1", "a99", "a20", "a2", "b10", "b70", "b00", "0000"]
    self.assertEqual(algo.NiceSort(data),
                     ["0000", "a0", "a1", "a2", "a20", "a99",
                      "b00", "b10", "b70"])

    data = ["a0-0", "a1-0", "a99-10", "a20-3", "a0-4", "a99-3", "a09-2",
            "Z", "a9-1", "A", "b"]
    self.assertEqual(algo.NiceSort(data),
                     ["A", "Z", "a0-0", "a0-4", "a1-0", "a9-1", "a09-2",
                      "a20-3", "a99-3", "a99-10", "b"])
    self.assertEqual(algo.NiceSort(data, key=str.lower),
                     ["A", "a0-0", "a0-4", "a1-0", "a9-1", "a09-2",
                      "a20-3", "a99-3", "a99-10", "b", "Z"])
    self.assertEqual(algo.NiceSort(data, key=str.upper),
                     ["A", "a0-0", "a0-4", "a1-0", "a9-1", "a09-2",
                      "a20-3", "a99-3", "a99-10", "b", "Z"])

  def testLargeA(self):
    data = [
      "Eegah9ei", "xij88brTulHYAv8IEOyU", "3jTwJPtrXOY22bwL2YoW",
      "Z8Ljf1Pf5eBfNg171wJR", "WvNJd91OoXvLzdEiEXa6", "uHXAyYYftCSG1o7qcCqe",
      "xpIUJeVT1Rp", "KOt7vn1dWXi", "a07h8feON165N67PIE", "bH4Q7aCu3PUPjK3JtH",
      "cPRi0lM7HLnSuWA2G9", "KVQqLPDjcPjf8T3oyzjcOsfkb",
      "guKJkXnkULealVC8CyF1xefym", "pqF8dkU5B1cMnyZuREaSOADYx",
      ]
    self.assertEqual(algo.NiceSort(data), [
      "3jTwJPtrXOY22bwL2YoW", "Eegah9ei", "KOt7vn1dWXi",
      "KVQqLPDjcPjf8T3oyzjcOsfkb", "WvNJd91OoXvLzdEiEXa6",
      "Z8Ljf1Pf5eBfNg171wJR", "a07h8feON165N67PIE", "bH4Q7aCu3PUPjK3JtH",
      "cPRi0lM7HLnSuWA2G9", "guKJkXnkULealVC8CyF1xefym",
      "pqF8dkU5B1cMnyZuREaSOADYx", "uHXAyYYftCSG1o7qcCqe",
      "xij88brTulHYAv8IEOyU", "xpIUJeVT1Rp"
      ])

  def testLargeB(self):
    data = [
      "inst-0.0.0.0-0.0.0.0",
      "inst-0.1.0.0-0.0.0.0",
      "inst-0.2.0.0-0.0.0.0",
      "inst-0.2.1.0-0.0.0.0",
      "inst-0.2.2.0-0.0.0.0",
      "inst-0.2.2.0-0.0.0.9",
      "inst-0.2.2.0-0.0.3.9",
      "inst-0.2.2.0-0.2.0.9",
      "inst-0.2.2.0-0.9.0.9",
      "inst-0.20.2.0-0.0.0.0",
      "inst-0.20.2.0-0.9.0.9",
      "inst-10.020.2.0-0.9.0.10",
      "inst-15.020.2.0-0.9.1.00",
      "inst-100.020.2.0-0.9.0.9",

      # Only the last group, not converted to a number anymore, differs
      "inst-100.020.2.0a999",
      "inst-100.020.2.0b000",
      "inst-100.020.2.0c10",
      "inst-100.020.2.0c101",
      "inst-100.020.2.0c2",
      "inst-100.020.2.0c20",
      "inst-100.020.2.0c3",
      "inst-100.020.2.0c39123",
      ]

    rnd = random.Random(16205)
    for _ in range(10):
      testdata = data[:]
      rnd.shuffle(testdata)
      assert testdata != data
      self.assertEqual(algo.NiceSort(testdata), data)

  class _CallCount:
    def __init__(self, fn):
      self.count = 0
      self.fn = fn

    def __call__(self, *args):
      self.count += 1
      return self.fn(*args)

  def testKeyfuncA(self):
    # Generate some random numbers
    rnd = random.Random(21131)
    numbers = [rnd.randint(0, 10000) for _ in range(999)]
    assert numbers != sorted(numbers)

    # Convert to hex
    data = [hex(i) for i in numbers]
    datacopy = data[:]

    keyfn = self._CallCount(lambda value: str(int(value, 16)))

    # Sort with key function converting hex to decimal
    result = algo.NiceSort(data, key=keyfn)

    self.assertEqual([hex(i) for i in sorted(numbers)], result)
    self.assertEqual(data, datacopy, msg="Input data was modified in NiceSort")
    self.assertEqual(keyfn.count, len(numbers),
                     msg="Key function was not called once per value")

  class _TestData:
    def __init__(self, name, value):
      self.name = name
      self.value = value

  def testKeyfuncB(self):
    rnd = random.Random(27396)
    data = []
    for i in range(123):
      v1 = rnd.randint(0, 5)
      v2 = rnd.randint(0, 5)
      data.append(self._TestData("inst-%s-%s-%s" % (v1, v2, i),
                                 (v1, v2, i)))
    rnd.shuffle(data)
    assert data != sorted(data, key=operator.attrgetter("name"))

    keyfn = self._CallCount(operator.attrgetter("name"))

    # Sort by name
    result = algo.NiceSort(data, key=keyfn)

    self.assertEqual(result, sorted(data, key=operator.attrgetter("value")))
    self.assertEqual(keyfn.count, len(data),
                     msg="Key function was not called once per value")

  def testNiceSortKey(self):
    self.assertEqual(algo.NiceSortKey(""),
                     ([None] * algo._SORTER_GROUPS) + [""])
    self.assertEqual(algo.NiceSortKey("Hello World"),
                     ["Hello World"] +
                     ([None] * int(algo._SORTER_GROUPS - 1)) + [""])
    self.assertEqual(algo.NiceSortKey("node1.net75.bld3.example.com"),
                     ["node", 1, ".net", 75, ".bld", 3, ".example.com",
                      None, ""])


class TestInvertDict(unittest.TestCase):
  def testInvertDict(self):
    test_dict = { "foo": 1, "bar": 2, "baz": 5 }
    self.assertEqual(algo.InvertDict(test_dict),
                     { 1: "foo", 2: "bar", 5: "baz"})


class TestInsertAtPos(unittest.TestCase):
  def test(self):
    a = [1, 5, 6]
    b = [2, 3, 4]
    self.assertEqual(algo.InsertAtPos(a, 1, b), [1, 2, 3, 4, 5, 6])
    self.assertEqual(algo.InsertAtPos(a, 0, b), b + a)
    self.assertEqual(algo.InsertAtPos(a, len(a), b), a + b)
    self.assertEqual(algo.InsertAtPos(a, 2, b), [1, 5, 2, 3, 4, 6])


class TimeMock:
  def __init__(self, values):
    self.values = values

  def __call__(self):
    return self.values.pop(0)


class TestRunningTimeout(unittest.TestCase):
  def setUp(self):
    self.time_fn = TimeMock([0.0, 0.3, 4.6, 6.5])

  def testRemainingFloat(self):
    timeout = algo.RunningTimeout(5.0, True, _time_fn=self.time_fn)
    self.assertAlmostEqual(timeout.Remaining(), 4.7)
    self.assertAlmostEqual(timeout.Remaining(), 0.4)
    self.assertAlmostEqual(timeout.Remaining(), -1.5)

  def testRemaining(self):
    self.time_fn = TimeMock([0, 2, 4, 5, 6])
    timeout = algo.RunningTimeout(5, True, _time_fn=self.time_fn)
    self.assertEqual(timeout.Remaining(), 3)
    self.assertEqual(timeout.Remaining(), 1)
    self.assertEqual(timeout.Remaining(), 0)
    self.assertEqual(timeout.Remaining(), -1)

  def testRemainingNonNegative(self):
    timeout = algo.RunningTimeout(5.0, False, _time_fn=self.time_fn)
    self.assertAlmostEqual(timeout.Remaining(), 4.7)
    self.assertAlmostEqual(timeout.Remaining(), 0.4)
    self.assertEqual(timeout.Remaining(), 0.0)

  def testNegativeTimeout(self):
    self.assertRaises(ValueError, algo.RunningTimeout, -1.0, True)


class TestJoinDisjointDicts(unittest.TestCase):
  def setUp(self):
    self.non_empty_dict = {"a": 1, "b": 2}
    self.empty_dict = {}

  def testWithEmptyDicts(self):
    self.assertEqual(self.empty_dict, algo.JoinDisjointDicts(self.empty_dict,
      self.empty_dict))
    self.assertEqual(self.non_empty_dict, algo.JoinDisjointDicts(
      self.empty_dict, self.non_empty_dict))
    self.assertEqual(self.non_empty_dict, algo.JoinDisjointDicts(
      self.non_empty_dict, self.empty_dict))

  def testNonDisjoint(self):
    self.assertRaises(AssertionError, algo.JoinDisjointDicts,
      self.non_empty_dict, self.non_empty_dict)

  def testCommonCase(self):
    dict_a = {"TEST1": 1, "TEST2": 2}
    dict_b = {"TEST3": 3, "TEST4": 4}

    result = dict_a.copy()
    result.update(dict_b)

    self.assertEqual(result, algo.JoinDisjointDicts(dict_a, dict_b))
    self.assertEqual(result, algo.JoinDisjointDicts(dict_b, dict_a))


class TestSequenceToDict(unittest.TestCase):
  def testEmpty(self):
    self.assertEqual(algo.SequenceToDict([]), {})
    self.assertEqual(algo.SequenceToDict({}), {})

  def testSimple(self):
    data = [(i, str(i), "test%s" % i) for i in range(391)]
    self.assertEqual(algo.SequenceToDict(data),
      dict((i, (i, str(i), "test%s" % i))
           for i in range(391)))

  def testCustomKey(self):
    data = [(i, hex(i), "test%s" % i) for i in range(100)]
    self.assertEqual(algo.SequenceToDict(data, key=compat.snd),
      dict((hex(i), (i, hex(i), "test%s" % i))
           for i in range(100)))
    self.assertEqual(algo.SequenceToDict(data,
                                         key=lambda (a, b, val): hash(val)),
      dict((hash("test%s" % i), (i, hex(i), "test%s" % i))
           for i in range(100)))

  def testDuplicate(self):
    self.assertRaises(ValueError, algo.SequenceToDict,
                      [(0, 0), (0, 0)])
    self.assertRaises(ValueError, algo.SequenceToDict,
                      [(i, ) for i in range(200)] + [(10, )])


class TestFlatToDict(unittest.TestCase):
  def testNormal(self):
    data = [
      ("lv/xenvg", {"foo": "bar", "bar": "baz"}),
      ("lv/xenfoo", {"foo": "bar", "baz": "blubb"}),
      ("san/foo", {"ip": "127.0.0.1", "port": 1337}),
      ("san/blubb/blibb", 54),
      ]
    reference = {
      "lv": {
        "xenvg": {"foo": "bar", "bar": "baz"},
        "xenfoo": {"foo": "bar", "baz": "blubb"},
        },
      "san": {
        "foo": {"ip": "127.0.0.1", "port": 1337},
        "blubb": {"blibb": 54},
        },
      }
    self.assertEqual(algo.FlatToDict(data), reference)

  def testUnlikeDepth(self):
    data = [
      ("san/foo", {"ip": "127.0.0.1", "port": 1337}),
      ("san/foo/blubb", 23), # Another foo entry under san
      ("san/blubb/blibb", 54),
      ]
    self.assertRaises(AssertionError, algo.FlatToDict, data)


if __name__ == "__main__":
  testutils.GanetiTestProgram()