mirror of
https://github.com/Halofreak1990/XFXFramework
synced 2024-12-26 13:49:34 +01:00
7e74ae8683
Added TypeInfo for all relevant types Added comments Updated DependencyProperty to work with System::Type Fixed casing on PropertyMetadata
659 lines
18 KiB
C++
659 lines
18 KiB
C++
/*****************************************************************************
|
|
* Dictionary.h *
|
|
* *
|
|
* XFX System::Collections::Generic::Dictionary class definition file *
|
|
* Copyright (c) XFX Team. All Rights Reserved *
|
|
*****************************************************************************/
|
|
#ifndef _SYSTEM_COLLECTIONS_GENERIC_DICTIONARY_
|
|
#define _SYSTEM_COLLECTIONS_GENERIC_DICTIONARY_
|
|
|
|
#include <System/Array.h>
|
|
#include <System/String.h>
|
|
#include "EqualityComparer.h"
|
|
#include "Interfaces.h"
|
|
#include "KeyValuePair.h"
|
|
#include "List.h"
|
|
|
|
#include <sassert.h>
|
|
|
|
namespace System
|
|
{
|
|
namespace Collections
|
|
{
|
|
namespace Generic
|
|
{
|
|
/**
|
|
* Represents a collection of keys and values.
|
|
*/
|
|
template <class TKey, class TValue>
|
|
class Dictionary : public IDictionary<TKey, TValue>, public ICollection<KeyValuePair<TKey, TValue> >, public IEnumerable<KeyValuePair<TKey, TValue> >, public Object
|
|
{
|
|
private:
|
|
template <class UKey, class UValue>
|
|
struct Entry
|
|
{
|
|
UKey Key;
|
|
UValue Value;
|
|
Entry* next;
|
|
|
|
Entry(UKey key, UValue value)
|
|
: Key(key), Value(value), next(NULL)
|
|
{
|
|
}
|
|
};
|
|
static const int defaultCapacity = 4;
|
|
|
|
IEqualityComparer<TKey>* comparer;
|
|
int _count;
|
|
Entry<TKey, TValue>** _internalStorage;
|
|
int _size;
|
|
int _version;
|
|
|
|
void Add(const KeyValuePair<TKey, TValue>& keyValuePair);
|
|
bool Contains(const KeyValuePair<TKey, TValue>& keyValuePair) const;
|
|
void CopyTo(KeyValuePair<TKey, TValue> array[], const int index) const;
|
|
void EnsureCapacity(int capacity);
|
|
Entry<TKey, TValue>* FindEntry(const TKey& key) const;
|
|
bool Remove(const KeyValuePair<TKey, TValue>& keyValuePair);
|
|
void Initialize(const int capacity);
|
|
//void Insert(const TKey& key, const TValue& value, const bool add);
|
|
void Resize();
|
|
|
|
public:
|
|
/**
|
|
* Represents the collection of keys in a Dictionary<,>.
|
|
*/
|
|
template <class UKey, class UValue>
|
|
class KeyCollection : public ICollection<UKey>
|
|
{
|
|
private:
|
|
Dictionary<UKey, UValue> const * const _dictionary;
|
|
|
|
public:
|
|
int Count() const;
|
|
bool IsReadOnly() const { return true; }
|
|
|
|
KeyCollection(Dictionary<UKey, UValue> const * const dictionary);
|
|
|
|
void Add(const UKey& item);
|
|
void Clear();
|
|
bool Contains(const UKey& item) const;
|
|
void CopyTo(UKey array[], const int arrayIndex) const;
|
|
bool Remove(const UKey& item);
|
|
};
|
|
|
|
/**
|
|
* Represents the collection of values in a Dictionary<,>.
|
|
*/
|
|
template <class UKey, class UValue>
|
|
class ValueCollection : public ICollection<UValue>
|
|
{
|
|
private:
|
|
Dictionary<UKey, UValue> const * const _dictionary;
|
|
|
|
public:
|
|
int Count() const;
|
|
bool IsReadOnly() const { return true; }
|
|
|
|
ValueCollection(Dictionary<UKey, UValue> const * const dictionary);
|
|
|
|
void Add(const UValue& item);
|
|
void Clear();
|
|
bool Contains(const UValue& item) const;
|
|
void CopyTo(UValue array[], const int arrayIndex) const;
|
|
bool Remove(const UValue& item);
|
|
};
|
|
|
|
public:
|
|
IEqualityComparer<TKey>* getComparer() const;
|
|
|
|
int Count() const;
|
|
bool IsReadOnly() const;
|
|
KeyCollection<TKey, TValue>* getKeys() const;
|
|
ValueCollection<TKey, TValue>* getValues() const;
|
|
TValue& operator[](const TKey& key);
|
|
|
|
Dictionary();
|
|
Dictionary(const IDictionary<TKey, TValue>* dictionary);
|
|
Dictionary(const int capacity);
|
|
virtual ~Dictionary();
|
|
|
|
void Add(const TKey& key, const TValue& value);
|
|
void Clear();
|
|
bool ContainsKey(const TKey& key) const;
|
|
bool ContainsValue(const TValue& value) const;
|
|
IEnumerator<KeyValuePair<TKey, TValue> >* GetEnumerator();
|
|
static const Type& GetType();
|
|
bool Remove(const TKey& key);
|
|
bool TryGetValue(const TKey& key, out TValue value) const;
|
|
|
|
private:
|
|
struct DictionaryEnumerator : IEnumerator<KeyValuePair<TKey, TValue> >
|
|
{
|
|
private:
|
|
Dictionary<TKey, TValue>* _parentDictionary;
|
|
Entry<TKey, TValue>* currentEntry;
|
|
|
|
public:
|
|
DictionaryEnumerator(Dictionary<TKey, TValue>* _parentDictionary);
|
|
|
|
KeyValuePair<TKey, TValue>& Current() const;
|
|
bool MoveNext();
|
|
void Reset();
|
|
};
|
|
};
|
|
|
|
///////////////////////////////////////////////////////////////////
|
|
|
|
template <class TKey, class TValue>
|
|
int Dictionary<TKey, TValue>::Count() const
|
|
{
|
|
return _count;
|
|
}
|
|
|
|
template <class TKey, class TValue>
|
|
bool Dictionary<TKey, TValue>::IsReadOnly() const
|
|
{
|
|
return false;
|
|
}
|
|
|
|
template <class TKey, class TValue>
|
|
Dictionary<TKey, TValue>::KeyCollection<TKey, TValue>* Dictionary<TKey, TValue>::getKeys() const
|
|
{
|
|
return new KeyCollection<TKey, TValue>(this);
|
|
}
|
|
|
|
template <class TKey, class TValue>
|
|
Dictionary<TKey, TValue>::ValueCollection<TKey, TValue>* Dictionary<TKey, TValue>::getValues() const
|
|
{
|
|
return new ValueCollection<TKey, TValue>(this);
|
|
}
|
|
|
|
template <class TKey, class TValue>
|
|
Dictionary<TKey, TValue>::Dictionary()
|
|
: _count(0), _size(defaultCapacity), _version(0)
|
|
{
|
|
_internalStorage = new Entry<TKey, TValue>*[defaultCapacity];
|
|
|
|
for (int i = 0; i < _size; i++)
|
|
_internalStorage[i] = NULL;
|
|
}
|
|
|
|
template <class TKey, class TValue>
|
|
Dictionary<TKey, TValue>::Dictionary(const IDictionary<TKey, TValue>* dictionary)
|
|
: _count(0), _size(dictionary->Keys()->Count()), _version(0)
|
|
{
|
|
_internalStorage = new Entry<TKey, TValue>*[_size];
|
|
|
|
IEnumerator<KeyValuePair<TKey, TValue> >* enumerator = dictionary->GetEnumerator();
|
|
enumerator->Reset();
|
|
|
|
while (enumerator->MoveNext())
|
|
{
|
|
this->Add(enumerator->Current());
|
|
}
|
|
}
|
|
|
|
template <class TKey, class TValue>
|
|
Dictionary<TKey, TValue>::Dictionary(const int capacity)
|
|
: _count(0), _size(capacity), _version(0)
|
|
{
|
|
_internalStorage = new Entry<TKey, TValue>*[capacity];
|
|
|
|
for (int i = 0; i < _size; i++)
|
|
_internalStorage[i] = NULL;
|
|
}
|
|
|
|
template <class TKey, class TValue>
|
|
Dictionary<TKey, TValue>::~Dictionary()
|
|
{
|
|
for (int i = 0; i < _size; i++)
|
|
{
|
|
if (_internalStorage[i] != NULL)
|
|
{
|
|
Entry<TKey, TValue>* prevEntry = NULL;
|
|
Entry<TKey, TValue>* entry = _internalStorage[i];
|
|
while (entry != NULL)
|
|
{
|
|
prevEntry = entry;
|
|
entry = entry->next;
|
|
delete prevEntry;
|
|
}
|
|
}
|
|
}
|
|
|
|
delete[] _internalStorage;
|
|
}
|
|
|
|
template <class TKey, class TValue>
|
|
void Dictionary<TKey, TValue>::Add(const TKey& key, const TValue& value)
|
|
{
|
|
int hash = key.GetHashCode() % _size;
|
|
|
|
if (_internalStorage[hash] == NULL)
|
|
_internalStorage[hash] = new Entry<TKey, TValue>(TKey(key), TValue(value));
|
|
else
|
|
{
|
|
Entry<TKey, TValue>* entry = _internalStorage[hash];
|
|
while (entry->next != NULL)
|
|
entry = entry->next;
|
|
|
|
if (entry->Key == key)
|
|
return; // throw error
|
|
else
|
|
entry->next = new Entry<TKey, TValue>(TKey(key), TValue(value));
|
|
}
|
|
|
|
_count++;
|
|
}
|
|
|
|
template <class TKey, class TValue>
|
|
void Dictionary<TKey, TValue>::Add(const KeyValuePair<TKey, TValue>& keyValuePair)
|
|
{
|
|
int hash = keyValuePair.Key.GetHashCode() % _size;
|
|
|
|
if (_internalStorage[hash] == NULL)
|
|
_internalStorage[hash] = new Entry<TKey, TValue>(keyValuePair.Key, keyValuePair.Value);
|
|
else
|
|
{
|
|
Entry<TKey, TValue>* entry = _internalStorage[hash];
|
|
while (entry->next != NULL)
|
|
entry = entry->next;
|
|
|
|
if (entry->Key == keyValuePair.Key)
|
|
return; // throw error
|
|
else
|
|
entry->next = new Entry<TKey, TValue>(keyValuePair.Key, keyValuePair.Value);
|
|
}
|
|
|
|
_count++;
|
|
}
|
|
|
|
template <class TKey, class TValue>
|
|
bool Dictionary<TKey, TValue>::Contains(const KeyValuePair<TKey, TValue>& keyValuePair) const
|
|
{
|
|
// TODO: implement
|
|
return false;
|
|
}
|
|
|
|
template <class TKey, class TValue>
|
|
bool Dictionary<TKey, TValue>::ContainsKey(const TKey& key) const
|
|
{
|
|
int hash = key.GetHashCode() % _size;
|
|
|
|
if (_internalStorage[hash] != NULL)
|
|
{
|
|
Entry<TKey, TValue>* entry = _internalStorage[hash];
|
|
while (entry->next != NULL)
|
|
entry = entry->next;
|
|
|
|
return (entry->Key == key);
|
|
}
|
|
return false;
|
|
}
|
|
|
|
template <class TKey, class TValue>
|
|
bool Dictionary<TKey, TValue>::ContainsValue(const TValue& value) const
|
|
{
|
|
// TODO: implement
|
|
return false;
|
|
}
|
|
|
|
template <class TKey, class TValue>
|
|
void Dictionary<TKey, TValue>::CopyTo(KeyValuePair<TKey, TValue> array[], const int arrayIndex) const
|
|
{
|
|
sassert(false, "Function not implemented.");
|
|
}
|
|
|
|
template <class TKey, class TValue>
|
|
void Dictionary<TKey, TValue>::EnsureCapacity(int capacity)
|
|
{
|
|
/*if (_actualSize < capacity)
|
|
{
|
|
int num = (_size == 0) ? defaultCapacity : _size * 2;
|
|
if (num > 0x7fefffff)
|
|
{
|
|
num = 0x7fefffff;
|
|
}
|
|
if (num < capacity)
|
|
{
|
|
num = capacity;
|
|
}
|
|
|
|
if (num != _size)
|
|
{
|
|
if (num > 0)
|
|
{
|
|
Entry<TKey, TValue>** destinationArray = new Entry<TKey, TValue>*[num];
|
|
if (_count > 0)
|
|
{
|
|
for(int i = 0; i < _count; i++)
|
|
{
|
|
destinationArray[i] = entries[i];
|
|
}
|
|
}
|
|
delete[] entries;
|
|
entries = destinationArray;
|
|
}
|
|
else
|
|
{
|
|
delete[] entries;
|
|
entries = new Entry<TKey, TValue>*[0];
|
|
|
|
}
|
|
_size = num;
|
|
}
|
|
}*/
|
|
}
|
|
|
|
template <class TKey, class TValue>
|
|
Dictionary<TKey, TValue>::Entry<TKey, TValue>* Dictionary<TKey, TValue>::FindEntry(const TKey& key) const
|
|
{
|
|
// TODO: implement
|
|
/*for (Entry<TKey, TValue>* e = *entries; e != NULL; e = e->next)
|
|
{
|
|
if (e->key == key)
|
|
return e;
|
|
}*/
|
|
return NULL;
|
|
}
|
|
|
|
template <class TKey, class TValue>
|
|
const Type& Dictionary<TKey, TValue>::GetType()
|
|
{
|
|
static const Type DictionaryTypeInfo("Dictionary", "System::Collections::Generic::Dictionary", TypeCode::Object, true);
|
|
|
|
return DictionaryTypeInfo;
|
|
}
|
|
|
|
//template <class TKey, class TValue>
|
|
//void Dictionary<TKey, TValue>::Insert(const TKey& key, const TValue& value, const bool add)
|
|
//{
|
|
// Entry<TKey, TValue>* e = FindEntry(key);
|
|
|
|
// if (e)
|
|
// {
|
|
// sassert(!add, "Attempting to add duplicate Key/Value pair to dictionary.");
|
|
|
|
// e->value = value;
|
|
// return;
|
|
// }
|
|
|
|
// while(e->next != NULL)
|
|
// {
|
|
// e = e->next;
|
|
// }
|
|
|
|
// // e now points to the last element in the list
|
|
// e->next = new Entry<TKey, TValue>();
|
|
// e = e->next;
|
|
// e->key = key;
|
|
// e->value = value;
|
|
// e->next = NULL;
|
|
|
|
// _count++;
|
|
//}
|
|
|
|
template <class TKey, class TValue>
|
|
bool Dictionary<TKey, TValue>::Remove(const KeyValuePair<TKey, TValue>& keyValuePair)
|
|
{
|
|
Entry<TKey, TValue>* e = FindEntry(keyValuePair.Key);
|
|
|
|
if (e)
|
|
{
|
|
// TODO: implement
|
|
return true;
|
|
}
|
|
|
|
return false;
|
|
}
|
|
|
|
template <class TKey, class TValue>
|
|
template <class UKey, class UValue>
|
|
int Dictionary<TKey, TValue>::KeyCollection<UKey, UValue>::Count() const
|
|
{
|
|
return _dictionary->Count();
|
|
}
|
|
|
|
template <class TKey, class TValue>
|
|
template <class UKey, class UValue>
|
|
Dictionary<TKey, TValue>::KeyCollection<UKey, UValue>::KeyCollection(Dictionary<UKey, UValue> const * const dictionary)
|
|
: _dictionary(dictionary)
|
|
{
|
|
}
|
|
|
|
template <class TKey, class TValue>
|
|
template <class UKey, class UValue>
|
|
void Dictionary<TKey, TValue>::KeyCollection<UKey, UValue>::Add(const UKey& item)
|
|
{
|
|
sassert(false, "Adding keys directly to the Dictionary::Keycollection is not supported.");
|
|
|
|
return;
|
|
}
|
|
|
|
template <class TKey, class TValue>
|
|
template <class UKey, class UValue>
|
|
void Dictionary<TKey, TValue>::KeyCollection<UKey, UValue>::Clear()
|
|
{
|
|
sassert(false, "Directly clearing the Dictionary::KeyCollection is not supported.");
|
|
|
|
return;
|
|
}
|
|
|
|
template <class TKey, class TValue>
|
|
template <class UKey, class UValue>
|
|
bool Dictionary<TKey, TValue>::KeyCollection<UKey, UValue>::Contains(const UKey& item) const
|
|
{
|
|
return _dictionary->ContainsKey(item);
|
|
}
|
|
|
|
template <class TKey, class TValue>
|
|
template <class UKey, class UValue>
|
|
void Dictionary<TKey, TValue>::KeyCollection<UKey, UValue>::CopyTo(UKey array[], const int arrayIndex) const
|
|
{
|
|
sassert(array != NULL, String::Format("array; %s", FrameworkResources::ArgumentNull_Generic));
|
|
|
|
sassert(arrayIndex >= 0, String::Format("arrayIndex; %s", FrameworkResources::ArgumentOutOfRange_NeedNonNegNum));
|
|
|
|
// TODO: implement
|
|
}
|
|
|
|
template <class TKey, class TValue>
|
|
template <class UKey, class UValue>
|
|
bool Dictionary<TKey, TValue>::KeyCollection<UKey, UValue>::Remove(const UKey& item)
|
|
{
|
|
sassert(false, "Removing keys directly from the Dictionary::KeyCollection is not supported.");
|
|
|
|
return false;
|
|
}
|
|
|
|
template <class TKey, class TValue>
|
|
template <class UKey, class UValue>
|
|
Dictionary<TKey, TValue>::ValueCollection<UKey, UValue>::ValueCollection(Dictionary<UKey, UValue> const * const dictionary)
|
|
: _dictionary(dictionary)
|
|
{
|
|
}
|
|
|
|
template <class TKey, class TValue>
|
|
template <class UKey, class UValue>
|
|
int Dictionary<TKey, TValue>::ValueCollection<UKey, UValue>::Count() const
|
|
{
|
|
return _dictionary->Count();
|
|
}
|
|
|
|
template <class TKey, class TValue>
|
|
template <class UKey, class UValue>
|
|
void Dictionary<TKey, TValue>::ValueCollection<UKey, UValue>::Add(const UValue& item)
|
|
{
|
|
sassert(false, "Adding values directly to the Dictionary::Valuecollection is not supported.");
|
|
|
|
return;
|
|
}
|
|
|
|
template <class TKey, class TValue>
|
|
template <class UKey, class UValue>
|
|
void Dictionary<TKey, TValue>::ValueCollection<UKey, UValue>::Clear()
|
|
{
|
|
sassert(false, "Directly clearing the Dictionary::ValueCollection is not supported.");
|
|
|
|
return;
|
|
}
|
|
|
|
template <class TKey, class TValue>
|
|
template <class UKey, class UValue>
|
|
bool Dictionary<TKey, TValue>::ValueCollection<UKey, UValue>::Contains(const UValue& item) const
|
|
{
|
|
return _dictionary->ContainsValue(item);
|
|
}
|
|
|
|
template <class TKey, class TValue>
|
|
template <class UKey, class UValue>
|
|
void Dictionary<TKey, TValue>::ValueCollection<UKey, UValue>::CopyTo(UValue array[], const int arrayIndex) const
|
|
{
|
|
sassert(array != NULL, String::Format("array; %s", FrameworkResources::ArgumentNull_Generic));
|
|
|
|
sassert(arrayIndex >= 0, String::Format("arrayIndex; %s", FrameworkResources::ArgumentOutOfRange_NeedNonNegNum));
|
|
|
|
// TODO: implement
|
|
}
|
|
|
|
template <class TKey, class TValue>
|
|
template <class UKey, class UValue>
|
|
bool Dictionary<TKey, TValue>::ValueCollection<UKey, UValue>::Remove(const UValue& item)
|
|
{
|
|
sassert(false, "Removing values directly from the Dictionary::ValueCollection is not supported.");
|
|
|
|
return false;
|
|
}
|
|
|
|
template <class TKey, class TValue>
|
|
void Dictionary<TKey, TValue>::Clear()
|
|
{
|
|
for (int i = 0; i < _size; i++)
|
|
{
|
|
if (_internalStorage[i] != NULL)
|
|
{
|
|
Entry<TKey, TValue>* prevEntry = NULL;
|
|
Entry<TKey, TValue>* entry = _internalStorage[i];
|
|
while (entry != NULL)
|
|
{
|
|
prevEntry = entry;
|
|
entry = entry->next;
|
|
delete prevEntry;
|
|
}
|
|
}
|
|
}
|
|
|
|
_count = 0;
|
|
}
|
|
|
|
template <class TKey, class TValue>
|
|
IEnumerator<KeyValuePair<TKey, TValue> >* Dictionary<TKey, TValue>::GetEnumerator()
|
|
{
|
|
return new DictionaryEnumerator(this);
|
|
}
|
|
|
|
template <class TKey, class TValue>
|
|
bool Dictionary<TKey, TValue>::Remove(const TKey& key)
|
|
{
|
|
int hash = key.GetHashCode() % _size;
|
|
|
|
if (_internalStorage[hash] != NULL)
|
|
{
|
|
Entry<TKey, TValue>* prevEntry = NULL;
|
|
Entry<TKey, TValue>* entry = _internalStorage[hash];
|
|
while (entry->next != NULL && entry->Key != key)
|
|
{
|
|
prevEntry = entry;
|
|
entry = entry->next;
|
|
}
|
|
if (entry->Key == key)
|
|
{
|
|
if (prevEntry == NULL)
|
|
{
|
|
Entry<TKey, TValue>* nextEntry = entry->next;
|
|
delete entry;
|
|
_internalStorage[hash] = nextEntry;
|
|
}
|
|
else
|
|
{
|
|
Entry<TKey, TValue>* next = entry->next;
|
|
delete entry;
|
|
prevEntry->next = next;
|
|
}
|
|
return true;
|
|
}
|
|
}
|
|
|
|
return false;
|
|
}
|
|
|
|
template <class TKey, class TValue>
|
|
bool Dictionary<TKey, TValue>::TryGetValue(const TKey& key, out TValue value) const
|
|
{
|
|
int hash = key.GetHashCode() % _size;
|
|
|
|
if (_internalStorage[hash] != NULL)
|
|
{
|
|
// TODO: implement
|
|
return true;
|
|
}
|
|
return false;
|
|
}
|
|
|
|
template <class TKey, class TValue>
|
|
Dictionary<TKey, TValue>::DictionaryEnumerator::DictionaryEnumerator(Dictionary<TKey,TValue> *_parentDictionary)
|
|
: _parentDictionary(_parentDictionary)
|
|
{
|
|
}
|
|
|
|
template <class TKey, class TValue>
|
|
KeyValuePair<TKey, TValue>& Dictionary<TKey, TValue>::DictionaryEnumerator::Current() const
|
|
{
|
|
KeyValuePair<TKey, TValue>* kv = new KeyValuePair<TKey,TValue>(currentEntry->Key, currentEntry->Value);
|
|
return *kv;
|
|
}
|
|
|
|
template <class TKey, class TValue>
|
|
bool Dictionary<TKey, TValue>::DictionaryEnumerator::MoveNext()
|
|
{
|
|
// TODO: implement
|
|
/*bool canMove = ((Entry<TKey, TValue>*)*(_parentDictionary->entries))->next != null;
|
|
if (currentEntry == NULL)
|
|
currentEntry = *(_parentDictionary->entries);
|
|
else
|
|
currentEntry = currentEntry->next;*/
|
|
}
|
|
|
|
template <class TKey, class TValue>
|
|
void Dictionary<TKey, TValue>::DictionaryEnumerator::Reset()
|
|
{
|
|
currentEntry = NULL;
|
|
}
|
|
|
|
template <class TKey, class TValue>
|
|
TValue& Dictionary<TKey, TValue>::operator [](const TKey& key)
|
|
{
|
|
int hash = key.GetHashCode() % _size;
|
|
|
|
if (_internalStorage[hash] == NULL)
|
|
{
|
|
sassert(false, ""); // KeyNotFoundException
|
|
}
|
|
else
|
|
{
|
|
Entry<TKey, TValue>* entry = _internalStorage[hash];
|
|
while (entry != NULL && entry->Key != key)
|
|
entry = entry->next;
|
|
if (entry == NULL)
|
|
sassert(false, ""); // KeyNotFoundException
|
|
else
|
|
return entry->Value;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
#endif //_SYSTEM_COLLECTIONS_GENERIC_DICTIONARY_
|