# -*- coding: utf-8 -*-

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

import copy

from types import GeneratorType

# taken from Django.utils.datastructures

class SortedDict(dict):

"""

A dictionary that keeps its keys in the order in which they're inserted.

"""

def __new__(cls, *args, **kwargs):

instance = super(SortedDict, cls).__new__(cls, *args, **kwargs)

instance.keyOrder = []

return instance

def __init__(self, data=None):

if data is None:

data = {}

elif isinstance(data, GeneratorType):

# Unfortunately we need to be able to read a generator twice. Once

# to get the data into self with our super().__init__ call and a

# second time to setup keyOrder correctly

data = list(data)

super(SortedDict, self).__init__(data)

if isinstance(data, dict):

self.keyOrder = data.keys()

else:

self.keyOrder = []

seen = set()

for key, value in data:

if key not in seen:

self.keyOrder.append(key)

seen.add(key)

def __deepcopy__(self, memo):

return self.__class__([(key, copy.deepcopy(value, memo))

for key, value in self.iteritems()])

def __setitem__(self, key, value):

if key not in self:

self.keyOrder.append(key)

super(SortedDict, self).__setitem__(key, value)

def __delitem__(self, key):

super(SortedDict, self).__delitem__(key)

self.keyOrder.remove(key)

def __iter__(self):

return iter(self.keyOrder)

def pop(self, k, *args):

result = super(SortedDict, self).pop(k, *args)

try:

self.keyOrder.remove(k)

except ValueError:

# Key wasn't in the dictionary in the first place. No problem.

pass

return result

def popitem(self):

result = super(SortedDict, self).popitem()

self.keyOrder.remove(result[0])

return result

def items(self):

return zip(self.keyOrder, self.values())

def iteritems(self):

for key in self.keyOrder:

yield key, self[key]

def keys(self):

return self.keyOrder[:]

def iterkeys(self):

return iter(self.keyOrder)

def values(self):

return map(self.__getitem__, self.keyOrder)

def itervalues(self):

for key in self.keyOrder:

yield self[key]

def update(self, dict_):

for k, v in dict_.iteritems():

self[k] = v

def setdefault(self, key, default):

if key not in self:

self.keyOrder.append(key)

return super(SortedDict, self).setdefault(key, default)

def value_for_index(self, index):

"""Returns the value of the item at the given zero-based index."""

return self[self.keyOrder[index]]

def insert(self, index, key, value):

"""Inserts the key, value pair before the item with the given index."""

if key in self.keyOrder:

n = self.keyOrder.index(key)

del self.keyOrder[n]

if n < index:

index -= 1

self.keyOrder.insert(index, key)

super(SortedDict, self).__setitem__(key, value)

def copy(self):

"""Returns a copy of this object."""

# This way of initializing the copy means it works for subclasses, too.

obj = self.__class__(self)

obj.keyOrder = self.keyOrder[:]

return obj

def __repr__(self):

"""

Replaces the normal dict.__repr__ with a version that returns the keys

in their sorted order.

"""

return '{%s}' % ', '.join(['%r: %r' % (k, v) for k, v in self.items()])

def clear(self):

super(SortedDict, self).clear()

self.keyOrder = []