C# Expand Dictionary or Hashtable to include Pop a

Question

Looking for structure that contains the benefits of a stack but the ability to only contain one item that matches a key.

For example Data comes in from various clients, I am only interested in the last piece of data from a particular client. So a dictionary would work very well. However I want to process the data from all the clients in a LIFO scenario, so a stack would be best.

Any ideas on combining the two?

Answer 1

There are several ways to interpret what you want. For instance when you Push a value with a key which already exists, what happens?

1. Existing item is popped, new one pushed,
2. Replace value for the existing item with the new data
3. Exception

If the LIFO aspect is the key consideration, you mainly need a modified Stack to associate a key with the data. A LinkedList would be another alternative.

Push/Pop on a List would require implementing it as Insert(0) and RemoveAt(0). This means the underlying array would be rebuilt for each and every operation. A Stack works inversely: new items are stored at the end of the array so it only has to be rebuilt periodically.

Depending on the size and amount of data, that may not matter.

In mentioning Dictionary it becomes unclear if you also want access by key; that is, you can Pop items, but also retrieve them by key. That seems at odds with the nature of a Stack. First, a class to associate a Key (name) with an item:

Class NameValuePair(Of T)
    Public Property Name As String
    Public Property Value As T

    Public Sub New(n As String, v As T)
        Name = n
        Value = v
    End Sub

    Public Sub New(n As String)
        Name = n
    End Sub

    Public Overrides Function ToString() As String
        Return String.Format("{0} ({1})", Name, Value.ToString)
    End Function
End Class

Then the stack-like collection. This will surely need work depending on the answers to the above and other unknowns. If the data size is small, I might stick with a List just for simplicity.

Public Class KeyedStack(Of T)
    Private myStack As Stack(Of NameValuePair(Of T))

    Public Sub New()
        myStack = New Stack(Of NameValuePair(Of T))
    End Sub

    Public Sub Push(key As String, value As T)
        Dim item = myStack.FirstOrDefault(Function(k) String.Compare(k.Name, key, True) = 0)
        If item IsNot Nothing Then
            ' replace
            item.Value = value
        Else
            myStack.Push(New NameValuePair(Of T)(key, value))
        End If
    End Sub

    Public Function Pop() As T
        ' todo check count
        Dim item = myStack.Pop
        Return item.Value
    End Function

    Public Function Peek() As T
        Return myStack.Peek().Value
    End Function

    ' ToDo: add Count, Contains, ContainsKey as needed
End Class

The keys are case-insensitive. The base Stack provides the ordering, while the NameValuePair provides the dictionary-like key.

If you needed Push to treat dupes as new items (they loose their old place):

' replace item as new
Public Sub PushAsNew(key As String, value As T)
    Dim tmp = myStack.ToList()
    Dim ndx = tmp.FindIndex(Function(k) String.Compare(k.Name, key, True) = 0)

    If ndx > -1 Then
        tmp.RemoveAt(ndx)
        myStack = New Stack(Of NameValuePair(Of T))(tmp.ToArray.Reverse)
    End If

    myStack.Push(New NameValuePair(Of T)(key, value))
End Sub

Since Stack items are not meant to be removed by index, it becomes pretty expensive to do so (stack to list to array to reversed array to new stack). A PopByKey method is equally expensive. Hopefully, you wont need it. Ulta simple testing:

Dim data = {"Alpha", "Beta", "Gamma", "Delta", "Echo", "Ziggy"}
Dim stacker = New KeyedStack(Of String)

For Each s As String In data
    stacker.Push(s(0), s)
Next
' result == Z, E, D, G, B, A order

stacker.Push("a", "Apple")
' item(5) is now {A, Apple} (key case ignored)

Dim item = stacker.Pop
' item == "Ziggy"

item = stacker.PopKey("g")
' new contents ==  E, D, B, A 
' item == "Gamma"

stacker.PushAsNew("B", "Bottle")
' new contents ==  B, E, D, A 

Answer 2

It seems like you want something that would be called HashStack<T>.

T would need to implement IEquatable<T> or override Equals and GetHashCode, or you can accept an IEqualityComparer<T>.

If you don't want to overcomplicate things, you'll need to implement IList<T> with Push method. The Add method will be called by Push and it'll need to evaluate if the item to be added is already in the stack by either calling item's GetHashCode/Equals or you can also maintain an internal HashSet<T> to optimize this check that has already implemented equality check (HashSet<T>.Add will return false if the item is already in the set...).

Items would need to be also stored in an internal List<T> to being able to get last item by insertion order.