109 lines
2.7 KiB
Python
109 lines
2.7 KiB
Python
# coding=utf-8
|
|
|
|
import ctypes
|
|
|
|
|
|
NULL = 0
|
|
|
|
|
|
class Node:
|
|
|
|
|
|
def __init__(self, data, npx=NULL) -> None:
|
|
self.data = data
|
|
# npx means XOR of next and prev node
|
|
self.npx = npx
|
|
|
|
def __str__(self) -> str:
|
|
return "Node(data={}, npx={}, id={})".format(self.data, self.npx, id(self))
|
|
|
|
|
|
class XorList:
|
|
|
|
def __init__(self) -> None:
|
|
self.head = None
|
|
self.tail = None
|
|
self.__nodes = []
|
|
|
|
def xor(self, a, b):
|
|
"""
|
|
Return XORed value of node reference
|
|
"""
|
|
return a ^ b
|
|
|
|
def insert(self, data):
|
|
node = Node(data)
|
|
node_id = id(node)
|
|
# New node npx is XOR of current head and id(None)
|
|
# node.npx = self.xor(node_id, id(self.head))
|
|
node.npx = id(self.head)
|
|
|
|
if self.head is None:
|
|
# list is empty, set tail to the first node.
|
|
self.tail = node
|
|
else: # list is not empty, update npx of old head
|
|
old_head_npx = self.head.npx
|
|
self.head.npx = self.xor(node_id, old_head_npx)
|
|
# old_head_id = id(self.head)
|
|
# node.npx = self.xor(old_head_id, id(None))
|
|
|
|
self.__nodes.append(node)
|
|
self.head = node
|
|
|
|
def forward(self):
|
|
print("forward visit list")
|
|
prev_id = NULL
|
|
curr_node = self.head
|
|
|
|
if curr_node is None:
|
|
print("Empty linked_list")
|
|
return
|
|
|
|
while curr_node is not None:
|
|
print("Node: {}".format(curr_node))
|
|
# npx = prev ^ next
|
|
# prev ^ npx = prev ^ prev ^ next = next
|
|
# next ^ npx = next ^ prev ^ next = prev
|
|
next_id = self.xor(prev_id, curr_node.npx)
|
|
prev_id = id(curr_node)
|
|
curr_node = self.__type_cast(next_id)
|
|
|
|
def backward(self):
|
|
print("backward visit list")
|
|
rear_id = id(None)
|
|
curr_node = self.tail
|
|
|
|
if curr_node is None:
|
|
print("Empty list")
|
|
return
|
|
|
|
while curr_node is not None:
|
|
print("Node: {}".format(curr_node))
|
|
# TODO: Fix core dump
|
|
prev_id = self.xor(rear_id, curr_node.npx)
|
|
rear_id = id(curr_node)
|
|
curr_node = self.__type_cast(prev_id)
|
|
|
|
def __type_cast(self, obj_id):
|
|
"""
|
|
Returns a new instance of type points to the same memory
|
|
"""
|
|
py_obj = ctypes.cast(obj_id, ctypes.py_object)
|
|
if not py_obj:
|
|
return None
|
|
return py_obj.value
|
|
|
|
|
|
if __name__ == '__main__':
|
|
xor_list = XorList()
|
|
|
|
xor_list.insert(10)
|
|
xor_list.insert(20)
|
|
xor_list.insert(30)
|
|
xor_list.insert(40)
|
|
xor_list.insert(50)
|
|
|
|
xor_list.forward()
|
|
xor_list.backward()
|
|
|