Skip to content

Instantly share code, notes, and snippets.

@sasaki-shigeo
Created May 24, 2022 00:09
Show Gist options
  • Save sasaki-shigeo/b78e3778e42be8f324f869458fb4ab19 to your computer and use it in GitHub Desktop.
Save sasaki-shigeo/b78e3778e42be8f324f869458fb4ab19 to your computer and use it in GitHub Desktop.
Linear Search Table in Python and Ruby
from collections.abc import Mapping, MutableMapping
class Table(MutableMapping):
def __init__(self):
self.__table = [] # the internal table as a list of key-value pairs
def __len__(self):
return len(self.__table)
def __str__(self):
result = "{\n"
for kv in self.__table:
result += "\t" + str(kv[0]) + ": " + str(kv[1]) + ",\n"
result += "}"
return result
def __lin_search(self, key):
for ix in range(len(self.__table)):
if self.__table[ix][0] == key:
return ix
return -1
def __search(self, key):
return self.__lin_search(key)
def __contains(self, key):
return self.__search(key) != -1
def __getitem__(self, key):
for kv in self.__table:
if kv[0] == key:
return kv[1]
return self.__missing__(kv[0])
def get(self, key, defaultvalue=None):
for kv in self.__table:
if kv[0] == key:
return kv[1]
return defaultvalue
def __setitem__(self, key, value):
for kv in self.__table:
if kv[0] == key:
kv[1] = value
return
self.__table.append((key, value))
def __delitem__(self, key):
ix = self.__search(key)
if ix in range(len(self.__table)):
del self.__table[ix]
def __iter__(self):
return self.keys()
def keys(self):
for kv in self.__table:
yield kv[0]
def values(self):
for kv in self.__table:
yield kv[1]
def items(self):
for kv in self.__table:
yield kv
def main():
unitTest()
table = Table()
table["Japan"] = "Tokyo"
table["England"] = "London"
print(table)
del table["Japan"]
print(table)
def unitTest():
table = Table()
return table
if __name__ == "__main__":
main()
unitTest()
class Table
@table = [] # the list of key-value pairs
#
# utility funtion of the linear search
#
# Note: private functions in Ruby are visible to subclasses
#
private def _find(key)
@table.each_index{ |ix|
if @table[ix][0] == key
return ix
end
}
return -1
end
#
# Methods for Associative Arrays (as known as Dictionaries or Map)
#
def clear
@table = []
end
def length
return @table.length
end
def [](key)
ix = _find(key)
if key >= 0
@table[ix][1]
else
nil
end
end
def []=(key, value)
ix = _find(key)
if key >= 0
@table[ix][1] = value
else
@table.push([key, value])
end
end
def delete(key)
ix = _find(key)
value = nil
if key >= 0
value = @table[ix][1]
@table.delete
end
value
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment