scala - HashMap OLD

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
package lib
class KeyValue[K, V](val key: K, val value: V) {
override def toString(): String = "(" + key + ", " + value + ")";
}
class HashMap[K, V>:Null] private (val lengthOfList: Int, val arrayOfBoxes: List[List[KeyValue[K,V]]]) {
def this(capacity: Int) = this(capacity, Nil);
private def hFunc(key: K) : Int = {
key.hashCode() % lengthOfList;
}
private def forIsEmpty(curNum: Int) : Boolean = {
if (curNum < lengthOfList) {
if (arrayOfBoxes(curNum) == Nil)
forIsEmpty(curNum+1)
else
false
} else true
}
def isEmpty() : Boolean = {
if (arrayOfBoxes == Nil || forIsEmpty(0)) true
else false
}
private def forContainsKey(list: List[KeyValue[K, V]], curNum: Int, key: K) : Boolean = {
//if (list(curNum) != Nil) {
if (curNum < list.length) {
if ((list(curNum)).key == key)
true
else
forContainsKey(list, curNum+1, key)
} else false
}
def containsKey(key: K) : Boolean = {
if (isEmpty()) false
else if (arrayOfBoxes(hFunc(key)) == Nil)
false
else {
forContainsKey(arrayOfBoxes(hFunc(key)), 0, key)
}
}
private def forGetValue(list: List[KeyValue[K, V]], curNum: Int, key: K) : V = {
//if (list(curNum) != Nil) {
if (curNum < list.length) {
if ((list(curNum)).key == key)
list(curNum).value
else
forGetValue(list, curNum+1, key)
} else null
}
def getValue(key: K) : V = {
if (!containsKey(key)) null
else {
forGetValue(arrayOfBoxes(hFunc(key)), 0, key)
}
}
private def initEmptyMap(numOfList: Int, curNum: Int, key: K, value: V) : List[List[KeyValue[K,V]]] = {
if (curNum < lengthOfList) {
if (numOfList == curNum) {
val pair = new KeyValue[K, V](key, value);
val list: List[KeyValue[K, V]] = pair :: Nil;
list :: initEmptyMap(numOfList, curNum+1, key, value)
} else Nil :: initEmptyMap(numOfList, curNum+1, key, value)
} else Nil
}
private def initMap(numOfList: Int, curNum: Int, key: K, value: V) : List[List[KeyValue[K,V]]] = {
if (curNum < lengthOfList) {
if (numOfList == curNum) {
val pair = new KeyValue[K, V](key, value);
val oldList: List[KeyValue[K, V]] = arrayOfBoxes(hFunc(key));
val newList: List[KeyValue[K, V]] = pair :: oldList;
newList :: initMap(numOfList, curNum+1, key, value);
} else arrayOfBoxes(curNum) :: initMap(numOfList, curNum+1, key, value);
} else Nil;
}
def insert(key: K, value: V) : HashMap[K, V] = {
if (arrayOfBoxes == Nil || forIsEmpty(0)) {
new HashMap[K, V](lengthOfList, initEmptyMap(hFunc(key), 0, key, value))
} else {
if (containsKey(key)) this
else new HashMap[K, V](lengthOfList, initMap(hFunc(key), 0, key, value))
}
}
private def deletePair(curNum: Int, key: K, oldList: List[KeyValue[K, V]]) : List[KeyValue[K, V]] = {
if (curNum < oldList.length) {
if (oldList(curNum).key == key) {
deletePair(curNum+1, key, oldList)
} else {
oldList(curNum) :: deletePair(curNum+1, key, oldList)
}
} else Nil
}
private def initMapForDelete(numOfList: Int, curNum: Int, key: K) : List[List[KeyValue[K,V]]] = {
if (curNum < lengthOfList) {
if (numOfList == curNum) {
val newList: List[KeyValue[K, V]] = deletePair(0, key, arrayOfBoxes(numOfList));
newList :: initMapForDelete(numOfList, curNum+1, key);
} else arrayOfBoxes(curNum) :: initMapForDelete(numOfList, curNum+1, key);
} else Nil;
}
def delete(key: K) : HashMap[K, V] = {
if (arrayOfBoxes == Nil || forIsEmpty(0)) this
else {
if (!containsKey(key)) this
else new HashMap[K, V](lengthOfList, initMapForDelete(hFunc(key), 0, key))
}
}
override def toString(): String = arrayOfBoxes.toString();
}