how to check if the attribute of an instance is member of a queue in O(1)?

Question

I'm trying to design a Queue data structure with python 3.6

The queue has the aim to keep track node objects with these attributes:

class node(object):
    def __init__(self, state, parent):
        self.state = state
        self.parent = parent

I want avoid to incorporate nodes with the same state in the queue. So I design the following queue:

class queue(object):
    def __init__(self):
        self.list = []
        self.explored = set()

    def insert(self, element):
        self.list = [element] + self.list
        self.explored.add(str(element.state))
        return self.list

    def pop(self):
        oldest_element = self.list.pop()
        self.explored.remove(str(oldest_element.state))
        return oldest_element

    def empty(self):
       return len(self.list) == 0

    def check_member(self, other):
       return other in self.explored

In order to check if a state of a node is in the queue, I use the check_member method with the attribute state as a string type to see if is contained in the set with all the string state of the members. But this is still slowly.

So it is possible to check if an instance has the same attribute of another instance that could differ in other attributes? For example, two nodes, same state attributes but different parents attributes.

How can keep the order of the elements and still checking if some element is in the queue in O(1) without using the additional explored set?

Answer 1

You need a set/dict type object to achieve O(1) contains-check complexity. The easiest would be to use an OrderedDict as your underlying data container. Use state as key and the node as the value. That way, the states are enforced to be unique, and the order is maintained nonetheless:

from collections import OrderedDict

class queue(object):
    def __init__(self):
        self.q = OrderedDict()

    def insert(self, element):
        s = str(element.state)
        if s not in self.q:
             self.q[s] = element  # adds to the end

    def pop(self):
        return self.q.popitem(0)[1]  # returns the node from beginning

    def empty(self):
       return not self.q

    def check_member(self, element):
       return str(element.state) in self.q