# This software carries the following license:
#
# Modified BSD license
# 
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions are met:
# 
# 1. Redistributions of source code must retain the above copyright notice,
# this list of conditions and the following disclaimer.
# 
# 2. Redistributions in binary form must reproduce the above copyright notice,
# this list of conditions and the following disclaimer in the documentation
# and/or other materials provided with the distribution.
# 
# 3. The name of the author may not be used to endorse or promote products
# derived from this software without specific prior written permission.
# 
# THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED
# WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
# MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO
# EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
# PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
# OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
# WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
# OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
# ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
#
# Steinar Knutsen

"""DCLMatcher 1.4

This modules provides table lookups in a style similar to the DCL command
line in VMS. That is: A substring matching the start of a word is accepted
as an identifier as long as it is long enough to provide uniqueness. The
matching is case insensitive.

Example usage:
>>> a={'aaaa':1,'abbb':2,'abcc':3,'abcd':4}
>>> b=DCLMatcher.DCLMatcher(a)
>>> b['aa']
1
>>> b['a']
Traceback (innermost last):
  File "<stdin>", line 1, in ?
  File "DCLMatcher.py", line 70, in __getitem__
    return self.findref(key).value
  File "DCLMatcher.py", line 112, in findref
    raise AmbiguiousQuery
AmbiguiousQuery
>>> b['aaab']
Traceback (innermost last):
  File "<stdin>", line 1, in ?
  File "DCLMatcher.py", line 70, in __getitem__
    return self.findref(key).value
  File "DCLMatcher.py", line 108, in findref
    raise KeyMismatch
KeyMismatch
>>> b['a'] = 8
Traceback (innermost last):
  File "<stdin>", line 1, in ?
  File "DCLMatcher.py", line 88, in __setitem__
    raise AmbiguiousKeytable
AmbiguiousKeytable
>>> b['aaab']=9
>>> b['aaab']  
9

Key mismatch means the start of the key is a valid identifier to a single
entry, but it the end of does not match the rest of the entry's key.

A query with a key longer than the keys in the DCLMatcher object's internal
table will always result in KeyError exception, even if the start of the
query-string is a valid identifier.
"""
from string import lower
from types import StringType

AmbiguiousKeytable = "AmbiguiousKeytable"
AmbiguiousQuery = "AmbiguiousQuery"
KeyMismatch = "KeyMismatch"

class DCLMatcher:
	def __init__(self, initdict):
		items = initdict.items()
		keys, values = map(lambda x: x[0], items), map(lambda x: x[1], items)
		self.keytable = []
		self.valuetable = []
		for i in range(len(keys)):
			assert type(keys[i]) == StringType and len(keys[i]) > 0
			self.keytable.append(tuple(lower(keys[i])))
			self.valuetable.append(infopackage(keys[i], values[i]))
		for key in keys:
			try:
				self.findindex(lower(key))
			except:
				raise AmbiguiousKeytable

	def __getitem__(self, key):
		return self.findref(key).value

	def __setitem__(self, key, value):
		assert type(key) == StringType and len(key) > 0
		try:
			i = self.findindex(key)
		except AmbiguiousQuery:
			raise AmbiguiousQuery
		except:
			pkey = tuple(lower(key))
			self.keytable.append(pkey)
			self.valuetable.append(infopackage(key, value))
			try:                                   # Expensive, but necessary
				for key in self.keys():
					self.findindex(key)
			except:
				self.keytable.pop()
				self.valuetable.pop()
				raise AmbiguiousKeytable
		else:
			orgkey = self.valuetable[i].realkey
			self.valuetable[i] = infopackage(orgkey, value)
		

	def __delitem__(self, key):
		i = self.findindex(key)
		del self.valuetable[i]
		del self.keytable[i]

	def copy(self):
		return DCLMatcher(self)

	def get(key, value=0):
		try:
			return self[key]
		except:
			return value

	def has_key(self, key):
		try:
			self[key]
		except:
			return 0
		else:
			return 1

	def items(self):
		items = []
		for i in range(len(self.valuetable)):
			items.append((self.valuetable[i].realkey, self.valuetable[i].value))
		return items

	def keys(self):
		keys = []
		for entry in self.valuetable:
			keys.append(entry.realkey)
		return keys

	def update(self, dclmatcher):
		for i in range(len(dclmatcher.keytable)):
			self[dclmatcher.valuetable[i].realkey] = dclmatcher.valuetable[i]

	def values(self):
		values = []
		for entry in self.valuetable:
			values.append(entry.value)
		return values

	def findref(self, key):
		return self.valuetable[self.findindex(key)]

	def findindex(self, key):
		assert len(key) > 0
		reflist = []
		key = tuple(lower(key))
		for i in range(len(self.keytable)):
			if key[0] == self.keytable[i][0] and len(key) <= len(self.keytable[i]):
				reflist.append(i)
		if len(reflist) == 1:
			if not key == self.keytable[reflist[0]][:len(key)]:
				raise KeyMismatch
			else:
				return reflist[0] # Mainly to catch single-chr keys.
		for i in range(1, len(key), 1):
			# Traverse the reflist in reverse order to be able to delete references
			for j in range(len(reflist)-1, -1, -1):
				if self.keytable[reflist[j]][i] != key[i]:
					del reflist[j]
			if len(reflist) == 0:
				raise KeyError
			elif len(reflist) == 1:
				if not key == self.keytable[reflist[0]][:len(key)]:
					raise KeyMismatch
				else:
					return reflist[0]
		# If we get to here, we couldn't find a unique key or any key at all
		if len(reflist) == 0:
			raise KeyError
		else:
			raise AmbiguiousQuery

class infopackage:
	def __init__(self, realkey, value):
		self.realkey, self.value = realkey, value