#! /usr/bin/python3
# ==================================================================
# Ring Data Structure (a ring of beads)
#
# User objects are held in a ring that has no begining or end. There
# is a "pointer" that "points" to one of the objects. The "pointer"
# can be move around the ring.
#
# Notes:
# 1. I have no idea what this data structure could be use for.
# I did it because it was fun.
#
# ==================================================================
#
# In this code the class Bead is external to the class Ring.
# Bead could be an internal class of the Ring class. Making
# the class Bead internal means the user only deals with
# their objects and the Ring class. This could make things
# simpler for the user?
#
# ==================================================================
# To create a PyDoc html file:
#
# pydoc -w ring
#
# To run a web server (port 2001) for the documentation
# for the modules in the current directory:
#
# python3 -m pydoc -p 2001
#
# ==================================================================
class Bead():
'''
Ring bead class definition
Bead is a helper class for the ring class. It is generally
not used by the users.
Beads hold the objects the user inserts into the ring. The
ring can contain a mixture of objects because the ring does
not have knowledge of object internals. Objects are the
responsibility of the user.
Attributes:
obj user defined object
forward next bead in the forward direction
backward next bead in the backward direction
Bead methods:
__init__ create a bead
'''
# ---- init ring bead ------------------------------------------
def __init__(self,obj):
'''
Create a bead.
'''
self.obj = obj
self.forward = self
self.backward = self
class Ring():
'''
Ring class definition
Beads hold the objects the user inserts into the ring. The
ring can contain a mixture of objects because the ring does
not have knowledge of object internals. Objects are the
responsibility of the user.
A ring always has a "pointer" pointing to one of the ring beads
or "None" if there are no ring beads. This bead is called the
ring's current bead.
The ring's beads are not maintained in any particular order.
They are in the order the user inserts them.
Why have beads?
Beads allow the ring to know nothing about the objects
it contains and therefore imposes no requirements on the
objects in the ring.
Attributes:
bead ring's current bead
count number of beads in the ring
Ring methods:
__init__ create a ring
insert insert a bead into the ring
forward move forward one bead
backward move backward one bead
fetch return the object in the ring's current bead
locate locate a specific object in the ring
if found, make it the ring's current bead
delete delete the ring's current bead
display_ring display (print) the ring
'''
# ---- init ring -----------------------------------------------
def __init__(self):
'''
Create a ring.
Attributes:
bead = none
count = 0
'''
self.bead = None # ring's current bead
self.count = 0 # not required but nice to know
# ---- insert new bead -----------------------------------------
# ---- before or after the current ring bead -------------------
def insert(self,obj,before = True):
'''
Insert a new bead into the ring.
If the 'before' flag is True, the new bead is inserted
before (forward) the ring's current bead. If the
'before' flag is False, the new bead is inserted behind
(backward) the ring's current bead.
'''
if self.bead == None:
self.bead = Bead(obj)
else:
b = Bead(obj) # new bead
cb = self.bead # ring's current bead
fb = self.bead.forward # ring's current bead.forward
bb = self.bead.backward # ring's current bead.backward
if before:
b.forward = fb
b.backward = cb
fb.backward = b
cb.forward = b
else:
b.backward = bb
b.forward = cb
bb.forward = b
cb.backward = b
self.count += 1
# ---- move forward one bead -----------------------------------
# ---- the bead becomes the ring's current bead ----------------
def forward(self):
'''
Move forward one bead.
Return False if there is no current bead, else
return True.
'''
if self.bead == None:
return False
else:
self.bead = self.bead.forward
return True
# ---- move backward one bead ----------------------------------
# ---- the bead becomes the ring's current bead ----------------
def backward(self):
'''
Move backward one bead.
Return False if there is no current bead, else
return True.
'''
if self.bead == None:
return False
else:
self.bead = self.bead.backward
return True
# ---- return current bead's obj -------------------------------
def fetch(self):
'''
Return the object contained in the ring's current bead.
If there is no currernt bead return None.
'''
if self.bead == None:
return None
else:
return self.bead.obj
# ---- locate object -------------------------------------------
def locate(self,val,f):
'''
Locate a specific object in the ring.
If found, make the found bead the ring's current bead
and return True, else return False.
Because the ring knows nothing about the objects stored
in it, the user must pass in a function to do the
matching test.
Parameters:
val value to be locate
f function (user supplied) to compare a user
object with the val passed to this method.
'''
if self.bead == None:
return False
b = self.bead # current bead
sb = b # starting bead
while True:
if f(b.obj,val):
self.bead = b
return True
if b.forward is sb:
break
b = b.forward
return False
# ---- delete bead ---------------------------------------------
def delete(self):
'''
Delete the ring's current bead.
If there is no current bead return False, else return True.
'''
if self.bead == None:
return False
b = self.bead
fb = b.forward
bb = b.backward
# ---- only one bead in the ring?
if self.count < 2:
self.bead = None
b.forward = None
b.backward = None
self.count = 0
return True
bb.forward = fb
fb.backward = bb
b.forward = None
b.backward = None
self.bead = fb
self.count -= 1
return True
# ---- display ring --------------------------------------------
# ---- Because the ring knows nothing about the object's it ----
# ---- contains, you must pass in a function that knows --------
# ---- how to display information about the object's. ----------
def display_ring(self,f):
'''
Print all of the beads in the ring.
Because the ring knows nothing about the objects it
contains, the user must pass in a function to return
an object's information as a string. (The size of the
display string should be limited. See the code.)
Parameters:
f user defined function that returns a
user defined data value for a object.
'''
print('Ring bead count is {}\n'.format(self.count))
if self.bead == None: return
b = self.bead # current bead
sb = b # starting bead
while True:
print('------------------------------')
print('bead obj = {}'.format(f(b.obj)))
print('forward obj = {}'.format(f(b.forward.obj)))
print('backward obj = {}'.format(f(b.backward.obj)))
if b.forward == sb:
break
b = b.forward
return
# ------------------------------------------------------------------
# main testing
# ------------------------------------------------------------------
if __name__ == '__main__':
###############################################################
# ---- support functions --------------------------------------
def get_user_input(prompt):
'''
Prompt the user and return their input
'''
return input(prompt)
def pause_program():
'''
pause the program until the user is ready
'''
get_user_input('\nPress enter to continue: ')
def display_obj(obj,msg=''):
'''
Display object information
'''
if msg: print(msg)
print('obj {}'.format('None' if not obj else obj.data))
def return_obj_data(obj):
'''
Return data from an object
'''
print('return_obj_data({}'.
format('None' if not obj else obj.data))
return 'None' if not obj else obj.data
def match_obj(obj,val):
'''
Match object data
'''
##print('match_obj({},{})'.format(obj.data,val))
return True if obj.data == val else False
################################################################
# ---- test object class
class testobj():
def __init__(self,data):
self.data = data
# ---- display object
def display_obj(obj,msg=''):
if msg: print(msg)
print('obj {}'.format('None' if not obj else obj.data))
def return_obj_data(obj):
return 'None' if not obj else obj.data
#???????????????????????????????????????????????????????????????
# ---- some special tests --------------------------------------
#
#objx = testobj(333)
#
#rng = Ring()
#
#print('---- empty ring (no beads) ----------------')
#display_obj(rng.fetch())
#print('---- delete current bead ------------------')
#o = rng.delete()
#print('True' if o else 'False')
#print('---- display ring -------------------------')
#rng.display_ring(return_obj_data)
#
#print('\n')
#
#print('---- ring with one bead -------------------')
#print('---- insert obj (333) ---------------------')
#rng.insert(objx)
#display_obj(rng.fetch())
#print('---- display ring -------------------------')
#rng.display_ring(return_obj_data)
#print('---- delete current bead ------------------')
#o = rng.delete()
#print('True' if o else 'False')
#print('---- display ring -------------------------')
#rng.display_ring(return_obj_data)
#
#quit()
#???????????????????????????????????????????????????????????????
# ---- create test objects
obj1 = testobj(100)
obj2 = testobj(200)
obj3 = testobj(300)
obj4 = testobj(400)
obj5 = testobj(500)
obj6 = testobj(150)
obj7 = testobj(250)
# ---- create ring
rng = Ring()
# --------------------------------------------------------------
# ---- insert and display some objects
print('---- insert obj --')
rng.insert(obj1)
display_obj(rng.fetch(),'--- cur obj -----')
print('---- insert obj --')
rng.insert(obj2)
print('---- forward -----')
rng.forward()
display_obj(rng.fetch(),'--- cur obj -----')
print('---- backward ----')
rng.backward()
display_obj(rng.fetch(),'--- cur obj -----')
print('---- insert obj --')
rng.insert(obj3,False)
print('---- backward ----')
rng.backward()
display_obj(rng.fetch(),'--- cur obj -----')
print('\n------------------------------------------')
print(' display ring')
print('------------------------------------------\n')
rng.display_ring(return_obj_data)
print('\n------------------------------------------')
print(' insert more objects and display the ring')
print(' display the modified ring')
print('------------------------------------------\n')
rng.insert(obj4)
rng.insert(obj5,False)
rng.display_ring(return_obj_data)
print('\n------------------------------------------')
print(" delete the ring's current bead")
print(" display the modified ring")
print('------------------------------------------\n')
rng.delete()
rng.display_ring(return_obj_data)
print('\n------------------------------------------')
print(" search the ring for an object")
print('------------------------------------------')
while True:
val = get_user_input('\nEnter obj value: ')
sval = val.strip()
if sval == '': break
if sval.isdigit() != True:
print('\nIllegal value entered ({})'.format(sval))
pause_program()
continue
ival = int(sval)
tf = rng.locate(ival,match_obj)
if tf:
print('\nFound the object {} in the ring'
.format(ival))
print("It is now the ring's current bead")
display_obj(rng.fetch(),'\n--- cur obj -----')
else:
print('\nDid not find the object {} in the ring'
.format(ival))
print("The ring's current bead did not change")
display_obj(rng.fetch(),'\n--- cur obj -----')