intlinkedhashmap.go

// Portions of this file are based on Apache Commons Collections,
// licensed under the Apache License, Version 2.0.
package intlinkedhashmap

import (
	"iter"
	"math"

	"github.com/bibenga/orderedmap"
	"github.com/bibenga/orderedmap/internal/hash"
	"github.com/bibenga/orderedmap/internal/utils"
)

type intLinkedHashMapEntry[K orderedmap.Integer, V any] struct {
	hashCode uint32
	key      K
	value    V
	next     *intLinkedHashMapEntry[K, V]
	before   *intLinkedHashMapEntry[K, V]
	after    *intLinkedHashMapEntry[K, V]
}

type IntLinkedHashMap[K orderedmap.Integer, V any] struct {
	modCount   uint64
	data       []*intLinkedHashMapEntry[K, V]
	header     *intLinkedHashMapEntry[K, V]
	size       int
	loadFactor float64
	threshold  int
}

var _ orderedmap.Map[int, int] = &IntLinkedHashMap[int, int]{}

// New creates a new IntLinkedHashMap with the specified
// initial capacity and load factor. It supports generic integer keys (K)
// and values of any type (V). The map preserves insertion order.
//
// Parameters:
//   - capacity: initial size of the map; use DefaultCapacity if unsure.
//   - loadFactor: determines when the map should resize; typically 0.75.
//
// Returns:
//   - a new Map[K,V] instance.
func New[K orderedmap.Integer, V any](capacity int, loadFactor float64) *IntLinkedHashMap[K, V] {
	if capacity < 0 {
		panic("initial capacity must be a non negative number")
	}
	if loadFactor <= 0.0 || math.IsNaN(loadFactor) {
		panic("load factor must be greater than 0")
	}
	m := IntLinkedHashMap[K, V]{
		loadFactor: loadFactor,
	}
	initialCapacity := m.calculateNewCapacity(capacity)
	m.threshold = m.calculateThreshold(initialCapacity, m.loadFactor)
	m.data = make([]*intLinkedHashMapEntry[K, V], initialCapacity)
	var emptyKey K
	var emptyValue V
	m.header = m.createEntry(nil, 0, emptyKey, emptyValue)
	m.header.before = m.header
	m.header.after = m.header
	return &m
}

// NewDefault creates a new IntLinkedHashMap with default
// capacity and load factor. It supports generic integer keys (K) and values
// of any type (V). Useful for quick initialization when defaults are sufficient.
//
// Returns:
//   - a new Map[K,V] instance.
func NewDefault[K orderedmap.Integer, V any]() orderedmap.Map[K, V] {
	return New[K, V](orderedmap.DefaultCapacity, orderedmap.DefaultLoadFactor)
}

func (m *IntLinkedHashMap[K, V]) calculateNewCapacity(proposedCapacity int) int {
	newCapacity := 1
	if proposedCapacity > orderedmap.MaxCapacity {
		newCapacity = orderedmap.MaxCapacity
	} else {
		for newCapacity < proposedCapacity {
			newCapacity <<= 1 // multiply by two
		}
		if newCapacity > orderedmap.MaxCapacity {
			newCapacity = orderedmap.MaxCapacity
		}
	}
	return newCapacity
}

func (m *IntLinkedHashMap[K, V]) calculateThreshold(newCapacity int, factor float64) int {
	return int(float64(newCapacity) * factor)
}

func (m *IntLinkedHashMap[K, V]) Size() int {
	return m.size
}

func (m *IntLinkedHashMap[K, V]) IsEmpty() bool {
	return m.size == 0
}

func (m *IntLinkedHashMap[K, V]) Clear() {
	// m.modCount++
	m.modCount++
	entry := m.header.after
	for entry != m.header {
		toDestory := entry
		entry = entry.after
		m.destroyEntry(toDestory)
	}

	clear(m.data)
	m.size = 0
	m.header.before = m.header
	m.header.after = m.header
}

func (m *IntLinkedHashMap[K, V]) Clone() orderedmap.Map[K, V] {
	cm := New[K, V](m.size, m.loadFactor)
	for k, v := range m.Items() {
		cm.Put(k, v)
	}
	return cm
}

func (m *IntLinkedHashMap[K, V]) Put(key K, value V) (V, bool) {
	hashCode := hash.MapHash32(hash.IntHash32(key))
	hashIndex := hash.MapHashIndex(hashCode, len(m.data))
	entry := m.data[hashIndex]
	for entry != nil {
		// if hashCode == entry.hashCode && && key == entry.key {
		if key == entry.key {
			oldValue := entry.value
			entry.value = value
			return oldValue, true
		}
		entry = entry.next
	}
	m.addMapping(hashIndex, hashCode, key, value)
	var empty V
	return empty, false
}

func (m *IntLinkedHashMap[K, V]) addMapping(hashIndex int, hashCode uint32, key K, value V) {
	m.modCount++
	entry := m.createEntry(m.data[hashIndex], hashCode, key, value)
	m.addEntry(entry, hashIndex)
	m.size++
	m.checkCapacity()
}

func (m *IntLinkedHashMap[K, V]) addEntry(entry *intLinkedHashMapEntry[K, V], hashIndex int) {
	entry.after = m.header
	entry.before = m.header.before
	m.header.before.after = entry
	m.header.before = entry
	m.data[hashIndex] = entry
}

func (m *IntLinkedHashMap[K, V]) createEntry(
	next *intLinkedHashMapEntry[K, V],
	hashCode uint32,
	key K,
	value V,
) *intLinkedHashMapEntry[K, V] {
	return &intLinkedHashMapEntry[K, V]{
		key:      key,
		value:    value,
		hashCode: hashCode,
		next:     next,
	}
}

func (m *IntLinkedHashMap[K, V]) checkCapacity() {
	if m.size >= m.threshold {
		newCapacity := len(m.data) * 2
		if newCapacity <= orderedmap.MaxCapacity {
			m.ensureCapacity(newCapacity)
		}
	}
}

func (m *IntLinkedHashMap[K, V]) ensureCapacity(newCapacity int) {
	oldCapacity := len(m.data)
	if newCapacity <= oldCapacity {
		return
	}
	if m.size == 0 {
		m.threshold = m.calculateThreshold(newCapacity, m.loadFactor)
		m.data = make([]*intLinkedHashMapEntry[K, V], newCapacity)
	} else {
		oldEntries := m.data
		newEntries := make([]*intLinkedHashMapEntry[K, V], newCapacity)
		m.modCount++
		for i := oldCapacity - 1; i >= 0; i-- {
			entry := oldEntries[i]
			if entry != nil {
				oldEntries[i] = nil // gc
				for entry != nil {
					next := entry.next
					hashIndex := hash.MapHashIndex(entry.hashCode, newCapacity)
					entry.next = newEntries[hashIndex]
					newEntries[hashIndex] = entry
					entry = next
				}
			}
		}
		m.threshold = m.calculateThreshold(newCapacity, m.loadFactor)
		m.data = newEntries
	}
}

func (m *IntLinkedHashMap[K, V]) ContainsKey(key K) bool {
	_, found := m.Get(key)
	return found
}

func (m *IntLinkedHashMap[K, V]) Get(key K) (V, bool) {
	hashCode := hash.MapHash32(hash.IntHash32(key))
	hashIndex := hash.MapHashIndex(hashCode, len(m.data))
	entry := m.data[hashIndex]
	for entry != nil {
		// if hashCode == entry.hashCode && key == entry.key {
		if key == entry.key {
			return entry.value, true
		}
		entry = entry.next
	}
	var empty V
	return empty, false
}

func (m *IntLinkedHashMap[K, V]) Delete(key K) (V, bool) {
	hashCode := hash.MapHash32(hash.IntHash32(key))
	hashIndex := hash.MapHashIndex(hashCode, len(m.data))
	entry := m.data[hashIndex]
	var previous *intLinkedHashMapEntry[K, V]
	for entry != nil {
		// if hashCode == entry.hashCode && && key == entry.key {
		if key == entry.key {
			oldValue := entry.value
			m.removeMapping(entry, hashIndex, previous)
			return oldValue, true
		}
		previous = entry
		entry = entry.next
	}
	var empty V
	return empty, false
}

func (m *IntLinkedHashMap[K, V]) removeMapping(
	entry *intLinkedHashMapEntry[K, V],
	hashIndex int,
	previous *intLinkedHashMapEntry[K, V],
) {
	m.modCount++
	m.removeEntry(entry, hashIndex, previous)
	m.size--
	m.destroyEntry(entry)
}

func (m *IntLinkedHashMap[K, V]) removeEntry(
	entry *intLinkedHashMapEntry[K, V],
	hashIndex int,
	previous *intLinkedHashMapEntry[K, V],
) {
	var emptyKey K
	var emptyValue V
	entry.key = emptyKey
	entry.value = emptyValue

	entry.before.after = entry.after
	entry.after.before = entry.before
	entry.after = nil
	entry.before = nil

	if previous == nil {
		m.data[hashIndex] = entry.next
	} else {
		previous.next = entry.next
	}
	entry.next = nil
}

func (m *IntLinkedHashMap[K, V]) destroyEntry(entry *intLinkedHashMapEntry[K, V]) {
	entry.next = nil
}

func (m *IntLinkedHashMap[K, V]) Keys() iter.Seq[K] {
	return func(yield func(K) bool) {
		expectedModCount := m.modCount
		entry := m.header.after
		for entry != m.header {
			if m.modCount != expectedModCount {
				panic("concurrent modification")
			}
			if !yield(entry.key) {
				return
			}
			entry = entry.after
		}
	}
}

func (m *IntLinkedHashMap[K, V]) Values() iter.Seq[V] {
	return func(yield func(V) bool) {
		expectedModCount := m.modCount
		entry := m.header.after
		for entry != m.header {
			if m.modCount != expectedModCount {
				panic("concurrent modification")
			}
			if !yield(entry.value) {
				return
			}
			entry = entry.after
		}
	}
}

func (m *IntLinkedHashMap[K, V]) Items() iter.Seq2[K, V] {
	return func(yield func(K, V) bool) {
		expectedModCount := m.modCount
		entry := m.header.after
		for entry != m.header {
			if m.modCount != expectedModCount {
				panic("concurrent modification")
			}
			if !yield(entry.key, entry.value) {
				return
			}
			entry = entry.after
		}
	}
}

func (m *IntLinkedHashMap[K, V]) String() string {
	return utils.MapToString("IntLinkedHashMap", m)
}