//
//  twohash/twohash.clay - two-hashed, unordered set/map containers
//
//  Copyright (c) 2010 Marc Fauconneau
//
// Permission is hereby granted, free of charge, to any person or organization
// obtaining a copy of the software and accompanying documentation covered by
// this license (the "Software") to use, reproduce, display, distribute,
// execute, and transmit the Software, and to prepare derivative works of the
// Software, and to permit third-parties to whom the Software is furnished to
// do so, all subject to the following:
//
// The copyright notices in the Software and this entire statement, including
// the above license grant, this restriction and the following disclaimer,
// must be included in all copies of the Software, in whole or in part, and
// all derivative works of the Software, unless such copies or derivative
// works are solely in the form of machine-executable object code generated by
// a source language processor.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
// SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
// FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
// ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
// DEALINGS IN THE SOFTWARE.

import twohash.implementation.*;

//
// Types
//

record HashSet[K]
(
    data: TwoHash[SetEntry[K]],
);

record HashMap[K, V]
(
    data: TwoHash[MapEntry[K, V]],
);

record SetVector[K]
(
    data: TwoHash[SetVectorEntry[K]],
    sentinel: Pointer[SetVectorEntry[K]],
);

private record SetEntry[K]
(
    key: K,
);

private record MapEntry[K, V]
(
    key: K,
    value: V,
);

private record SetVectorEntry[K]
(
    key: K,
    next: Pointer[SetVectorEntry[K]],
    prev: Pointer[SetVectorEntry[K]],
);

[T]
private Entry?(static T) = false;

[K]
overload Entry?(static SetEntry[K]) = true;

[K, V]
overload Entry?(static MapEntry[K, V]) = true;

[K]
overload Entry?(static SetVectorEntry[K]) = true;

[T]
private HashSetLike?(static T) = false;

[K]
overload HashSetLike?(static HashSet[K]) = true;

[K]
overload HashSetLike?(static SetVector[K]) = true;

//
// Type predicates
//

[T]
private Hashtable?(static T) = false;

[T | RecordWithField?(T, static #data) and TwoHash?(Type(typeToLValue(T).data))]
overload Hashtable?(static T) = true;

[T | Hashtable?(T)]
overload EntryType(static T) = EntryType(Type(typeToLValue(T).data));

//
// Entry semantics
//
// (copied from records.clay)

/*
[T | Entry?(T)]
overload RegularRecord?(static T) = false;

[T | Entry?(T)]
overload destroy(a:T)
{
    ..for (x in recordFields(a))
    destroy(x);
}

[T | Entry?(T)]
overload moveUnsafe(src:T) --> returned:T {
    alias n = RecordFieldCount(T);
    ..for (i in staticIntegers(static n))
        staticIndex(returned, i) <-- moveUnsafe(staticIndex(src, i));
}

[T | Entry?(T)]
overload resetUnsafe(a:T) {
    ..for (x in recordFields(a))
        resetUnsafe(x);
}
*/

//
// size
//

[Hash | Hashtable?(Hash)]
overload size(a: Hash) = a.data.size;

//
// lookup
//

[K, Hash | HashSetLike?(Hash)]
overload lookup(a: HashSet[K], key: K)
{
    var pEntry = pEntryAt(a.data, key);
    return not null(pEntry);
}

[K, V]
overload lookup(a: HashMap[K, V], key: K)
{
    var pEntry = pEntryAt(a.data, key);
    if (null?(pEntry))
        return null(V);
    return &pEntry^.value;
}

//
// put
//

[K, Hash | HashSetLike?(Hash)]
overload put(a: Hash, key: K, b: Bool) 
{
    var pEntry = pEntryAt(a.data, key);
    if (not null?(pEntry) or not b)
    {
        if (not b) freeEntry(a.data, pEntry);
        return;
    }
    var pEntry = allocateEntryAt(a.data, key, EntryType(Hash)(a, key));
}

[K, V]
overload put(a: HashMap[K, V], key: K, forward value: V) 
{
    var pEntry = pEntryAt(a.data, key);
    if (not null?(pEntry)) 
    {
        pEntry^.value = value;
        return;
    }
    var pEntry = allocateEntryAt(a.data, key, MapEntry[K, V](key, value));
}

//
// index
//

// !! has different semantics (non-ref return)
[K, Hash | HashSetLike?(Hash)]
overload index(a: HashSet[K], key: K)
{
    var pEntry = pEntryAt(a.data, key);
    if (not null?(pEntry))
        return true;
    return false;
}

[K, V]
overload index(a: HashMap[K, V], key: K)
{
    var pEntry = pEntryAt(a.data, key);
    if (not null?(pEntry))
        return ref pEntry^.value;
    var pEntry = allocateEntryAt(a.data, key, MapEntry[K, V](key, V()));
    return ref pEntry^.value;
}

//
// remove
//

[K, Hash | Hashtable?(Hash)]
overload remove(a: Hash, key: K)
{
    var pEntry = pEntryAt(a.data, key);
    if (null?(pEntry))
        return false;
    freeEntry(a.data, pEntry);
    return true;
}

//
// items
//

define itemFromEntry;

[Hash | Hashtable?(Hash)]
overload items(a: Hash) = TwoHashEntries[EntryType(Hash), itemFromEntry](a.data);

[K]
overload itemFromEntry(entry: SetEntry[K]) = entry.key, true;

[K, V]
overload itemFromEntry(entry: MapEntry[K, V]) = entry.key, entry.value;

//
// Entry match
//

[E, K]
overload keyMatch?(entry: E, key: K) = entry.key == key;

[E]
overload entryHash(entry: E) = largeHash(entry.key);

//
// SetVector stuff
//

[K]
overload SetVector[K]() --> set: SetVector[K]
{
    set.data <-- TwoHash[SetVectorEntry[K]]();
    set.sentinel = allocateRawMemory(SetVectorEntry[K], 1);
    resetUnsafe(set.sentinel^.key);
    set.sentinel^.next = set.sentinel;
    set.sentinel^.prev = set.sentinel;
}

[K]
overload destroy(set: SetVector[K])
{
    destroy(set.data);
    destroy(set.sentinel);
}

[K]
overload SetVectorEntry[K](a: SetVector[K], key: K) --> entry: SetVectorEntry[K]
{
    ref sentinel = a.sentinel;
    entry.key <-- move(key);
    entry.next = sentinel;
    entry.prev = sentinel^.prev;
    entry.next^.prev = &entry;
    entry.prev^.next = &entry;
}

[K]
overload destroy(entry: SetVectorEntry[K])
{
    destroy(entry.key);
    entry.prev^.next = entry.next;
    entry.next^.prev = entry.prev;
}

[K]
overload resetUnsafe(a: SetVectorEntry[K])
{
    a.prev = &a;
    a.next = &a;
}

[K]
overload moveEntry(src: SetVectorEntry[K], th) --> entry: SetVectorEntry[K]
{
    entry <-- move(src);
    entry.prev^.next = &entry;
    entry.next^.prev = &entry;
}


[K]
overload items(a: SetVector[K]) = SetVectorItems(a.sentinel, a.sentinel);

private record SetVectorItems[K]
(
    current: Pointer[SetVectorEntry[K]],
    sentinel: Pointer[SetVectorEntry[K]],
);

[K]
overload iterator(i: SetVectorItems[K]) = i;

[K]
overload hasNext?(i: SetVectorItems[K]) = (i.current^.next != i.sentinel);

[K]
overload next(i: SetVectorItems[K])
{
    i.current = i.current^.next;
    return ref i.current^.key;
}

//
// misc
//

[K]
overload SetEntry[K](a: HashSet[K], key: K) = SetEntry[K](key);

[K,V]
inline overload hash(m:HashMap[K,V]) = hashSequence(mapped((a,b) => [a,b], items(m)));
[K]
inline overload hash(s:HashSet[K]) = hashSequence(mapped((a,b) => [a,b], items(s)));
