In Python, How can I get the next and previous key

Question

Okay, so this is a little hard to explain, but here goes:

I have a dictionary, which I'm adding content to. The content is a hashed username (key) with an IP address (value). I was putting the hashes into an order by running them against base 16, and then using Collection.orderedDict. So, the dictionary looked a little like this:

d = {'1234': '8.8.8.8', '2345':'0.0.0.0', '3213':'4.4.4.4', '4523':'1.1.1.1', '7654':'1.3.3.7', '9999':'127.0.0.1'}

What I needed was a mechanism that would allow me to pick one of those keys, and get the key/value item one higher and one lower. So, for example, If I were to pick 2345, the code would return the key:value combinations '1234:8.8.8.8' and '3213:4.4.4.4'

So, something like:

for i in d:
  while i < len(d)
   if i == '2345':
     print i.nextItem
     print i.previousItem
     break()

Answer 1

As seen in the OrderedDict source code, if you have a key and you want to find the next and prev in O(1) here's how you do that.

>>> from collections import OrderedDict
>>> d = OrderedDict([('aaaa', 'a',), ('bbbb', 'b'), ('cccc', 'c'), ('dddd', 'd'), ('eeee', 'e'), ('ffff', 'f')])
>>> i = 'eeee'
>>> link_prev, link_next, key = d._OrderedDict__map['eeee']
>>> print 'nextKey: ', link_next[2], 'prevKey: ', link_prev[2]
nextKey:  ffff prevKey:  dddd

This will give you next and prev by insertion order. If you add items in random order then just keep track of your items in sorted order.

Answer 2

Edit: OP now states that they are using OrderedDicts but the use case still requires this sort of approach.

Since dicts are not ordered you cannot directly do this. From your example, you are trying to reference the item like you would use a linked list.

A quick solution would be instead to extract the keys and sort them then iterate over that list:

keyList=sorted(d.keys())
for i,v in enumerate(keyList):
    if v=='eeee':
        print d[keyList[i+1]]
        print d[keyList[i-1]]

The keyList holds the order of your items and you have to go back to it to find out what the next/previous key is to get the next/previous value. You also have to check for i+1 being greater than the list length and i-1 being less than 0.

You can use an OrderedDict similarly but I believe that you still have to do the above with a separate list as OrderedDict doesn't have next/prev methods.

Answer 3

You could use a generic function, based on iterators, to get a moving window (taken from this question):

import itertools

def window(iterable, n=3):
    it = iter(iterable)
    result = tuple(itertools.islice(it, n))
    if len(result) == n:
        yield result
    for element in it:
        result = result[1:] + (element,)
        yield result

l = range(8)
for i in window(l, 3):
    print i

Using the above function with OrderedDict.items() will give you three (key, value) pairs, in order:

d = collections.OrderedDict(...)

for p_item, item, n_item in window(d.items()):
    p_key, p_value = p_item
    key, value = item
    # Or, if you don't care about the next value:
    n_key, _ = n_item

Of course using this function the first and last values will never be in the middle position (although this should not be difficult to do with some adaptation).

I think the biggest advantage is that it does not require table lookups in the previous and next keys, and also that it is generic and works with any iterable.

Answer 4

Try:

pos = 0
d = {'aaaa': 'a', 'bbbb':'b', 'cccc':'c', 'dddd':'d', 'eeee':'e', 'ffff':'f'}

for i in d:
    pos+=1
    if i == 'eeee':
        listForm = list(d.values())
        print(listForm[pos-1])
        print(listForm[pos+1])

As in @AdamKerz's answer enumerate seems pythonic, but if you are a beginner this code might help you understand it in an easy way.

And I think its faster + smaller compared to sorting followed by building list & then enumerating

Answer 5

Maybe it is an overkill, but you can keep Track of the Keys inserted with a Helper Class and according to that list, you can retrieve the Key for Previous or Next. Just don't forget to check for border conditions, if the objects is already first or last element. This way, you will not need to always resort the ordered list or search for the element.

from collections import OrderedDict

class Helper(object):
    """Helper Class for Keeping track of Insert Order"""
    def __init__(self, arg):
        super(Helper, self).__init__()

    dictContainer = dict()
    ordering = list()

    @staticmethod
    def addItem(dictItem):
        for key,value in dictItem.iteritems():
            print key,value
            Helper.ordering.append(key)
            Helper.dictContainer[key] = value

    @staticmethod
    def getPrevious(key):
        index = (Helper.ordering.index(key)-1)
        return Helper.dictContainer[Helper.ordering[index]]


#Your unordered dictionary
d = {'aaaa': 'a', 'bbbb':'b', 'cccc':'c', 'dddd':'d', 'eeee':'e', 'ffff':'f'}

#Create Order over keys
ordered = OrderedDict(sorted(d.items(), key=lambda t: t[0]))

#Push your ordered list to your Helper class
Helper.addItem(ordered)


#Get Previous of    
print Helper.getPrevious('eeee')
>>> d

Answer 6

You can store the keys and values in temp variable in prior, and can access previous and next key,value pair using index.

It is pretty dynamic, will work for any key you query. Please check this code :

d = {'1234': '8.8.8.8', '2345':'0.0.0.0', '3213':'4.4.4.4', '4523':'1.1.1.1', '7654':'1.3.3.7', '9999':'127.0.0.1'}
ch = raw_input('Pleasure Enter your choice : ')
keys = d.keys()
values = d.values()
#print keys, values
for k,v in d.iteritems():
    if k == ch:
        ind = d.keys().index(k)
        print keys[ind-1], ':',values[ind-1]
        print keys[ind+1], ':',values[ind+1]