#
#

# Copyright (C) 2006, 2007, 2010, 2011 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.

"""Utility functions with algorithms.

"""

import re
import time
import itertools

from ganeti import compat
from ganeti.utils import text


_SORTER_GROUPS = 8
_SORTER_RE = re.compile("^%s(.*)$" % (_SORTER_GROUPS * r"(\D+|\d+)?"))


def UniqueSequence(seq):
  """Returns a list with unique elements.

  Element order is preserved.

  @type seq: sequence
  @param seq: the sequence with the source elements
  @rtype: list
  @return: list of unique elements from seq

  """
  seen = set()
  return [i for i in seq if i not in seen and not seen.add(i)]


def JoinDisjointDicts(dict_a, dict_b):
  """Joins dictionaries with no conflicting keys.

  Enforces the constraint that the two key sets must be disjoint, and then
  merges the two dictionaries in a new dictionary that is returned to the
  caller.

  @type dict_a: dict
  @param dict_a: the first dictionary
  @type dict_b: dict
  @param dict_b: the second dictionary
  @rtype: dict
  @return: a new dictionary containing all the key/value pairs contained in the
  two dictionaries.

  """
  assert not (set(dict_a) & set(dict_b)), ("Duplicate keys found while joining"
                                           " %s and %s" % (dict_a, dict_b))
  result = dict_a.copy()
  result.update(dict_b)
  return result


def FindDuplicates(seq):
  """Identifies duplicates in a list.

  Does not preserve element order.

  @type seq: sequence
  @param seq: Sequence with source elements
  @rtype: list
  @return: List of duplicate elements from seq

  """
  dup = set()
  seen = set()

  for item in seq:
    if item in seen:
      dup.add(item)
    else:
      seen.add(item)

  return list(dup)


def GetRepeatedKeys(*dicts):
  """Return the set of keys defined multiple times in the given dicts.

  >>> GetRepeatedKeys({"foo": 1, "bar": 2},
  ...                 {"foo": 5, "baz": 7}
  ...                )
  set("foo")

  @type dicts: dict
  @param dicts: The dictionaries to check for duplicate keys.
  @rtype: set
  @return: Keys used more than once across all dicts

  """
  if len(dicts) < 2:
    return set()

  keys = []
  for dictionary in dicts:
    keys.extend(dictionary)

  return set(FindDuplicates(keys))


def _NiceSortTryInt(val):
  """Attempts to convert a string to an integer.

  """
  if val and val.isdigit():
    return int(val)
  else:
    return val


def NiceSortKey(value):
  """Extract key for sorting.

  """
  return [_NiceSortTryInt(grp)
          for grp in _SORTER_RE.match(str(value)).groups()]


def NiceSort(values, key=None):
  """Sort a list of strings based on digit and non-digit groupings.

  Given a list of names C{['a1', 'a10', 'a11', 'a2']} this function
  will sort the list in the logical order C{['a1', 'a2', 'a10',
  'a11']}.

  The sort algorithm breaks each name in groups of either only-digits
  or no-digits. Only the first eight such groups are considered, and
  after that we just use what's left of the string.

  @type values: list
  @param values: the names to be sorted
  @type key: callable or None
  @param key: function of one argument to extract a comparison key from each
    list element, must return string
  @rtype: list
  @return: a copy of the name list sorted with our algorithm

  """
  if key is None:
    keyfunc = NiceSortKey
  else:
    keyfunc = lambda value: NiceSortKey(key(value))

  return sorted(values, key=keyfunc)


def InvertDict(dict_in):
  """Inverts the key/value mapping of a dict.

  @param dict_in: The dict to invert