71 lines
1.7 KiB
C++
71 lines
1.7 KiB
C++
#pragma once
|
|
//DO NOT INCLUDE SORTEDMAPITERATOR
|
|
#include <vector>
|
|
//DO NOT CHANGE THIS PART
|
|
typedef int TKey;
|
|
typedef int TValue;
|
|
#include <utility>
|
|
typedef std::pair<TKey, TValue> TElem;
|
|
#define NULL_TVALUE -111111
|
|
#define NULL_TPAIR pair<TKey, TValue>(-111111, -111111);
|
|
class SMIterator;
|
|
typedef bool(*Relation)(TKey, TKey);
|
|
|
|
class Node {
|
|
public:
|
|
TElem element;
|
|
Node* next;
|
|
Node(TElem e) {
|
|
element = e;
|
|
next = nullptr;
|
|
}
|
|
Node(TElem e, Node* n) {
|
|
element = e;
|
|
next = n;
|
|
}
|
|
bool operator==(Node* n) {
|
|
return this->element.first == n->element.first;
|
|
}
|
|
};
|
|
|
|
|
|
class SortedMap {
|
|
friend class SMIterator;
|
|
private:
|
|
//TODO - Representation
|
|
Node* head;
|
|
Relation relation;
|
|
int length;
|
|
public:
|
|
|
|
// implicit constructor
|
|
SortedMap(Relation r);
|
|
|
|
// adds a pair (key,value) to the map
|
|
//if the key already exists in the map, then the value associated to the key is replaced by the new value and the old value is returned
|
|
//if the key SMes not exist, a new pair is added and the value null is returned
|
|
TValue add(TKey c, TValue v);
|
|
|
|
//searches for the key and returns the value associated with the key if the map contains the key or null: NULL_TVALUE otherwise
|
|
TValue search(TKey c) const;
|
|
|
|
|
|
//removes a key from the map and returns the value associated with the key if the key existed ot null: NULL_TVALUE otherwise
|
|
TValue remove(TKey c);
|
|
|
|
//returns the number of pairs (key,value) from the map
|
|
int size() const;
|
|
|
|
//checks whether the map is empty or not
|
|
bool isEmpty() const;
|
|
|
|
// return the iterator for the map
|
|
// the iterator will return the keys following the order given by the relation
|
|
SMIterator iterator() const;
|
|
|
|
// destructor
|
|
~SortedMap();
|
|
|
|
std::vector<TValue> valueBag();
|
|
};
|