Indexed Array by more than one element

Question

In C#, I'm currently using a SortedSet to get indexing on a structure which consists of three fields:

public struct ChannelId : IComparable<ChannelId>
{
    public int ChanNumber;
    public Tower ChanTower;
    public double AvailableProbability;

    public int CompareTo(ChannelId other)
    { return other.AvailableProbability.CompareTo(AvailableProbability); }
}

(Yes, the CompareTo function is written right. I want it in the reversed order.) So, I want some sort of collection/structure that can index by two fields here, (ChanNumber as well). Is there a way to do this?

Do you want a `SortedSet` that is sorted first by one field, and then by another one? Can you exemplify the kind of "indexing" you need? Note that your struct is a ***mutable value type***. Some people consider them evil. — Jeppe Stig Nielsen, Jan 28 '14 at 09:30

score 1 · Answer 1 · answered Jan 28 '14 at 09:11

1

You can create two sets, using custom comparer:

class ChanNumberComparer : IComparer<ChannelId>
{
    public int Compare(ChannelId x, ChannelId y)
    {
        return y.ChanNumber.CompareTo(x.ChanNumber);
    }
}

Use it in SortedSet constructor

answered Jan 28 '14 at 09:11

astef

8,575
4
56
95

To modify this, I'd have to modify both copies, which defeats the entire purpose of indexing: to increase performance. My writes are significant compared to the reads. – Hameer Abbasi Jan 28 '14 at 09:16
@HameerAbbasi Do you know what index actually is? It is a sorted copy of original collection. There's no way not to avoid second insert operation if you want second index. – astef Jan 28 '14 at 09:30
But that's how an index works. For example, in the database, when you modify the table, every index must be updated separately. You are basically asking for this to be hidden in the implementation so you don't see it. If you want it indexed by (ChanNumber, ChanTower) then you can have 1 set and implement a custom compare on 2 fields. But if you want it indexed by ChanNumber, and also separately indexed by ChanTower, you need a second index. – svinja Jan 28 '14 at 09:30
I realize that. It's removing that's the issue, since probability may not be unique. Removing would still be O(n) rather than O(log n) – Hameer Abbasi Jan 28 '14 at 10:09
@HameerAbbasi Can you explain in more detail what's the problem with removing? – astef Jan 28 '14 at 10:17

Rick Love · Answer 2 · 2014-01-28T09:35:58.040

I assume you need to be able to lookup the ChannelId based on the ChanNumber and ChanTower.

However, I believe the class name is a misnomer.

I would create two classes:

class ChannelID:

int ChanNumber
Tower ChanTower

class Channel:

ChannelID ChanID
double AvailableProbability

Then, a dictionary would work well for your needs:

Dictionary<ChannelID, Channel>

You would need to implement the GetHashCode and Equals method for the ChannelID. Then you simply would create a new ChannelID object as a lookup to get your Channel object in the dictionary where you can get the AvailableProbability value.

Full code below:

using System;
using System.Collections.Generic;
using System.Linq;

namespace Test
{
    class ChannelTest
    {
        public static void Test()
        {
            var dict = new Dictionary<ChannelID, Channel>();

            var a = new Channel(new ChannelID(0, Tower.A), 0.5);
            var b = new Channel(new ChannelID(7, Tower.B), 0.35);

            dict.Add(a.ChanID, a);
            dict.Add(b.ChanID, b);

            // To get a channel from the ID
            // Just create a new ID object with the same values
            var aRef = dict[new ChannelID(0, Tower.A)];
            var bRef = dict[new ChannelID(7, Tower.B)];

            // If you want the sorted channels - use linq
            // This will give you the best 10
            var sorted = dict.Values.OrderByDescending(c => c.AvailableProbability).Take(10).ToList();

        }
    }

    class ChannelID
    {
        public int ChanNumber { get; private set; }
        public Tower ChanTower { get; private set; }

        public ChannelID(int chanNumber, Tower chanTower)
        {
            ChanNumber = chanNumber;
            ChanTower = chanTower;
        }

        public override bool Equals(object obj)
        {
            if (!(obj is ChannelID))
            {
                return false;
            }

            var o = (ChannelID)obj;

            return this.ChanNumber == o.ChanNumber
                && this.ChanTower == o.ChanTower;
        }

        public override int GetHashCode()
        {
            // Using random prime multipliers to get a good hash code distribution
            // http://stackoverflow.com/questions/263400/what-is-the-best-algorithm-for-an-overridden-system-object-gethashcode
            return 17
                + 23 * this.ChanNumber.GetHashCode()
                + 23 * this.ChanTower.GetHashCode();
        }
    }

    class Channel : IComparable<Channel>
    {
        public ChannelID ChanID { get; private set; }
        public double AvailableProbability { get; private set; }

        public Channel(ChannelID chanID, double availableProbability)
        {
            ChanID = chanID;
            AvailableProbability = availableProbability;
        }

        public int CompareTo(Channel other)
        { return other.AvailableProbability.CompareTo(AvailableProbability); }
    }

    enum Tower
    {
        A,
        B,
        C
    }
}

Indexed Array by more than one element

2 Answers2