mirror of
https://github.com/ultimatepp/ultimatepp.git
synced 2026-05-16 06:05:58 -06:00
195 lines
7.4 KiB
C++
195 lines
7.4 KiB
C++
struct IndexCommon {
|
|
enum { HIBIT = 0x80000000 };
|
|
|
|
struct Hash : Moveable<Hash> {
|
|
int next; // also link for unlinked items...
|
|
dword hash;
|
|
int prev;
|
|
};
|
|
|
|
int *map;
|
|
Hash *hash;
|
|
dword mask;
|
|
int unlinked;
|
|
|
|
|
|
static int empty[1];
|
|
|
|
static dword Smear(hash_t h) { return FoldHash(h) | HIBIT; }
|
|
|
|
void Link(int& m, Hash& hh, int ii);
|
|
void Link(int ii, dword sh);
|
|
void Del(int& m, Hash& hh, int ii);
|
|
void Ins(int& m, Hash& hh, int ii);
|
|
|
|
void MakeMap(int count);
|
|
void Remap(int count);
|
|
void Reindex(int count);
|
|
void GrowMap(int count);
|
|
void FreeMap();
|
|
void Free();
|
|
|
|
void Set(int ii, dword h);
|
|
|
|
Vector<int> GetUnlinked() const;
|
|
|
|
void Clear();
|
|
void Trim(int n, int count);
|
|
void Sweep(int n);
|
|
void Reserve(int n);
|
|
void Shrink();
|
|
void AdjustMap(int count, int alloc);
|
|
|
|
void Copy(const IndexCommon& b, int count);
|
|
void Pick(IndexCommon& b);
|
|
void Swap(IndexCommon& b);
|
|
|
|
IndexCommon();
|
|
~IndexCommon();
|
|
};
|
|
|
|
template <class K, class T, class V> class AMap;
|
|
|
|
template <class T>
|
|
class Index : MoveableAndDeepCopyOption<Index<T>>, IndexCommon {
|
|
Vector<T> key;
|
|
|
|
static dword Smear(const T& k) { return IndexCommon::Smear(GetHashValue(k)); }
|
|
|
|
int FindFrom(int i, dword sh, const T& k, int end) const;
|
|
int FindBack(int i, dword sh, const T& k, int end) const;
|
|
|
|
|
|
void ReallocHash(int n);
|
|
template <typename U> void GrowAdd(U&& k, dword sh);
|
|
template <typename U> void AddS(int& m, U&& k, dword sh);
|
|
template <typename U> void AddS(U&& k, dword sh);
|
|
|
|
template <class OP, class U> int FindAdd(U&& k, OP add_op);
|
|
template <class U> int FindPut0(U&& k);
|
|
|
|
template <typename U> int Put0(U&& k, dword sh);
|
|
template <typename U> void Set0(int i, U&& k);
|
|
|
|
template <typename, typename, typename> friend class AMap;
|
|
|
|
void FixHash(bool makemap = true);
|
|
|
|
public:
|
|
void Add(const T& k) { AddS(k, Smear(k)); }
|
|
void Add(T&& k) { AddS(pick(k), Smear(k)); }
|
|
Index& operator<<(const T& x) { Add(x); return *this; }
|
|
Index& operator<<(T&& x) { Add(pick(x)); return *this; }
|
|
|
|
int Find(const T& k) const;
|
|
int FindNext(int i) const;
|
|
int FindLast(const T& k) const;
|
|
int FindPrev(int i) const;
|
|
|
|
int FindAdd(const T& k) { return FindAdd(k, []{}); }
|
|
int FindAdd(T&& k) { return FindAdd(pick(k), []{}); }
|
|
|
|
int Put(const T& k) { return Put0(k, Smear(k)); }
|
|
int Put(T&& k) { return Put0(pick(k), Smear(k)); }
|
|
int FindPut(const T& k) { return FindPut0(k); }
|
|
int FindPut(T&& k) { return FindPut0(pick(k)); }
|
|
|
|
void Unlink(int i);
|
|
int UnlinkKey(const T& k);
|
|
bool IsUnlinked(int i) const { return hash[i].hash == 0; }
|
|
bool HasUnlinked() const { return unlinked >= 0; }
|
|
Vector<int> GetUnlinked() const { return IndexCommon::GetUnlinked(); }
|
|
|
|
void Sweep();
|
|
|
|
void Set(int i, const T& k) { Set0(i, k); }
|
|
void Set(int i, T&& k) { Set0(i, pick(k)); }
|
|
|
|
const T& operator[](int i) const { return key[i]; }
|
|
int GetCount() const { return key.GetCount(); }
|
|
bool IsEmpty() const { return key.IsEmpty(); }
|
|
|
|
void Clear() { key.Clear(); IndexCommon::Clear(); }
|
|
|
|
void Trim(int n = 0) { IndexCommon::Trim(n, GetCount()); key.Trim(n); }
|
|
void Drop(int n = 1) { Trim(GetCount() - 1); }
|
|
const T& Top() const { return key.Top(); }
|
|
T Pop() { T x = pick(Top()); Drop(); return x; }
|
|
|
|
void Reserve(int n);
|
|
void Shrink();
|
|
int GetAlloc() const { return key.GetAlloc(); }
|
|
|
|
Vector<T> PickKeys() { Vector<T> r = pick(key); Clear(); return r; }
|
|
const Vector<T>& GetKeys() const { return key; }
|
|
|
|
void Remove(const int *sorted_list, int count);
|
|
void Remove(const Vector<int>& sorted_list) { Remove(sorted_list, sorted_list.GetCount()); }
|
|
template <typename Pred> void RemoveIf(Pred p) { Remove(FindAlli(key, p)); }
|
|
|
|
Index() {}
|
|
Index(Index&& s) : key(pick(s.key)) { IndexCommon::Pick(s); }
|
|
Index(const Index& s, int) : key(s.key, 0) { ReallocHash(0); IndexCommon::Copy(s, key.GetCount()); } // TODO: Unlinked!
|
|
explicit Index(Vector<T>&& s) : key(pick(s)) { FixHash(); }
|
|
Index(const Vector<T>& s, int) : key(s, 0) { FixHash(); }
|
|
|
|
Index& operator=(Vector<T>&& x) { key = pick(x); FixHash(); return *this; }
|
|
Index& operator=(Index<T>&& x) { key = pick(x.key); IndexCommon::Pick(x); return *this; }
|
|
|
|
Index(std::initializer_list<T> init) : key(init) { FixHash(); }
|
|
|
|
void Serialize(Stream& s);
|
|
void Xmlize(XmlIO& xio, const char *itemtag = "key");
|
|
void Jsonize(JsonIO& jio);
|
|
String ToString() const;
|
|
template <class B> bool operator==(const B& b) const { return IsEqualRange(*this, b); }
|
|
#ifndef CPP_20
|
|
template <class B> bool operator!=(const B& b) const { return !operator==(b); }
|
|
#endif
|
|
template <class B> int Compare(const B& b) const { return CompareRanges(*this, b); }
|
|
template <class B> bool operator<=(const B& x) const { return Compare(x) <= 0; }
|
|
template <class B> bool operator>=(const B& x) const { return Compare(x) >= 0; }
|
|
template <class B> bool operator<(const B& x) const { return Compare(x) < 0; }
|
|
template <class B> bool operator>(const B& x) const { return Compare(x) > 0; }
|
|
|
|
// Standard container interface
|
|
typedef ConstIteratorOf<Vector<T>> ConstIterator;
|
|
ConstIterator begin() const { return key.begin(); }
|
|
ConstIterator end() const { return key.end(); }
|
|
|
|
friend void Swap(Index& a, Index& b) { a.IndexCommon::Swap(b); UPP::Swap(a.key, b.key); }
|
|
|
|
// deprecated:
|
|
#ifdef DEPRECATED
|
|
T& Insert(int i, const T& k) { key.Insert(i, k); FixHash(); return key[i]; }
|
|
void Remove(int i, int count) { key.Remove(i, count); FixHash(); }
|
|
void Remove(int i) { Remove(i, 1); }
|
|
int RemoveKey(const T& k) { int i = Find(k); if(i >= 0) Remove(i); return i; }
|
|
|
|
unsigned GetHash(int i) const { return hash[i].hash; }
|
|
|
|
Index& operator<<=(const Vector<T>& s) { *this = clone(s); return *this; }
|
|
typedef T ValueType;
|
|
typedef Vector<T> ValueContainer;
|
|
ConstIterator GetIter(int pos) const { return key.GetIter(pos); }
|
|
|
|
void ClearIndex() {}
|
|
void Reindex(int n) {}
|
|
void Reindex() {}
|
|
|
|
typedef T value_type;
|
|
typedef ConstIterator const_iterator;
|
|
typedef const T& const_reference;
|
|
typedef int size_type;
|
|
typedef int difference_type;
|
|
const_iterator Begin() const { return begin(); }
|
|
const_iterator End() const { return end(); }
|
|
void clear() { Clear(); }
|
|
size_type size() { return GetCount(); }
|
|
bool empty() const { return IsEmpty(); }
|
|
#endif
|
|
|
|
#ifdef _DEBUG
|
|
String Dump() const;
|
|
#endif
|
|
};
|