Hashtable in C++

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
124

//**************************************************************************
// CHashtable
//**************************************************************************

template<class TKey, class TValue>
class CHashtable {
  protected:
  template<class TKey, class TValue>
  class CHashvalue {
    public:
    TKey m_hKey;
    TValue m_hValue;
    
    CHashvalue() {}
    CHashvalue(const TKey& hKey, const TValue& hValue) {
      m_hKey = hKey;
      m_hValue = hValue; 
    }
  };
  
  private:
  CList<CHashvalue<TKey, TValue>> m_hObList;
  
  TValue m_hValue_Null;
  
  //-Initialisierung-------------------------------------------------------

  public:
  CHashtable(const TValue& hValue_Null) { m_hValue_Null = hValue_Null; }

  //-Funktionen------------------------------------------------------------

  void Add(const TKey& hKey, const TValue& hValue)  { m_hObList.AddTail(CHashvalue<TKey, TValue>(hKey, hValue)); }
  void Clear()  { m_hObList.RemoveAll(); }
  void Remove(const TKey& hKey);
  BOOL ContainsKey(const TKey& hKey);
  TValue GetValue(const TKey& hKey);
  POSITION GetHeadPosition()  { return m_hObList.GetHeadPosition(); }
  TValue GetNext(POSITION& rPosition)  { return m_hObList.GetNext(rPosition).m_hValue ; }
  TKey GetKey(POSITION& rPosition)  { return m_hObList.GetNext(rPosition).m_hKey ; }
  Int4 GetCount()  { return m_hObList.GetCount(); }
};

//-------------------------------------------------------------------------
// CHashtable::Remove
//-------------------------------------------------------------------------

template<class TKey, class TValue>
AFX_INLINE void CHashtable<TKey, TValue>::Remove(const TKey& hKey) {
  POSITION pos = m_hObList.GetHeadPosition();
  while (pos != NULL) {
    POSITION posOld = pos;
    CHashvalue<TKey, TValue> hHashvalue = m_hObList.GetNext(pos);
    if (hHashvalue.m_hKey == hKey) {
      m_hObList.RemoveAt(posOld);
      
      return;
    }
  }
}

//-------------------------------------------------------------------------
// CHashtable::ContainsKey
//-------------------------------------------------------------------------

template<class TKey, class TValue>
AFX_INLINE BOOL CHashtable<TKey, TValue>::ContainsKey(const TKey& hKey) {
  POSITION pos = m_hObList.GetHeadPosition();
  while (pos != NULL) {
    CHashvalue<TKey, TValue> hHashvalue = m_hObList.GetNext(pos);
    if (hHashvalue.m_hKey == hKey) {
      return TRUE;
    }
  }
  
  return FALSE;
}

//-------------------------------------------------------------------------
// CHashtable::GetValue
//-------------------------------------------------------------------------

template<class TKey, class TValue>
AFX_INLINE TValue CHashtable<TKey, TValue>::GetValue(const TKey& hKey) {
  POSITION pos = m_hObList.GetHeadPosition();
  while (pos != NULL) {
    CHashvalue<TKey, TValue> hHashvalue = m_hObList.GetNext(pos);
    if (hHashvalue.m_hKey == hKey) {
      return hHashvalue.m_hValue;
    }
  }
  
  return m_hValue_Null;
}


Kleine Beispiel:

    CHashtable<CString, CPoint*> ht_Points(NULL);
    ht_Points.Add("Punkt1", new CPoint(10, 20));
    ht_Points.Add("Punkt2", new CPoint(20, 30));
    ht_Points.Add("Punkt3", new CPoint(30, 40));
    
    CPoint* p1 = ht_Points.GetValue("Punkt1");
    CPoint* p2 = ht_Points.GetValue("Punkt2");
    CPoint* p3 = ht_Points.GetValue("Punkt3");
    
    ASSERT(ht_Points.GetValue("Punkt4") == NULL);

    CHashtable<int, CRect> ht_Rect(CRect(-1,-1,-1,-1));
    ht_Rect.Add(1, CRect(p1->x, p1->y, p1->x + 10, p1->y + 10));
    ht_Rect.Add(2, CRect(p2->x, p2->y, p2->x + 10, p2->y + 10));
    
    ASSERT(ht_Rect.GetValue(1).left == p1->x);
    ASSERT(ht_Rect.GetValue(2).right == p2->x + 10);
    ASSERT(
        ht_Rect.GetValue(3).left == -1 && 
        ht_Rect.GetValue(3).top == -1 && 
        ht_Rect.GetValue(3).right == -1 && 
        ht_Rect.GetValue(3).bottom == -1
    );
    
    delete p1;   delete p2;  delete p3;