CODEWITHSUNDEEP
c#arraysmultidimensional-array
liamzebedee
liamzebedee

Reputation: 14490

What is the best data storage type for a triangular array?

Is there an Array or Data Type (eg <List>) that supports the arranging of values (specifically strings) into a triangular shape like this...

1
2 3
4 5 6

In my above example, each of these numbers holds a value of 2 characters of a string. If my string was "Hello I am a cat", it would be split up into "He ll oI am ac at".

I want my program to store these values in an array similar to the triangle above - how could this be achieved? Is there a way to have the values moved around (e.g. 1=2 2=3 3=4).

Upvotes: 1

Views: 1648

Answers (2)

ICR
ICR

Reputation: 14162

The best physical data type to store this would be a list or an array. You can, however, quite easily write a class to abstract away calculating offsets etc.

public class Triangle<T> {
    private List<T> list = new List<T>();

    private int rows;
    public int Rows { get { return rows; } }

    private void CalculateRows() {
        rows = (int)Math.Ceiling(Math.Sqrt(list.Count * 2 + 0.25) - 0.5);
    }

    public void Add(T item) {
        list.Add(item);
        CalculateRows();
    }

    public T this[int column, int row] {
        get {
            if (row < 0 || row > Rows - 1) {
                throw new ArgumentOutOfRangeException("row");
            }

            if (column < 0 || column > row) {
                throw new ArgumentOutOfRangeException("column");
            }

            int rowOffset = row * (row + 1) / 2;
            return list[rowOffset + column];
        }
    }

    public int ColumnsForRow(int row) {
        if (row < 0 || row > Rows - 1) {
            throw new ArgumentOutOfRangeException("row");
        }

        if (row < Rows - 1) {
            return row + 1;
        }

        return list.Count - (row * (row + 1) / 2);
    }

    public void ShiftLeft() {
        list.Add(list[0]);
        list.RemoveAt(0);
    }

    public void ShiftRight() {
        list.Insert(0, list[list.Count - 1]);
        list.RemoveAt(list.Count - 1);
    }
}

Upvotes: 2

Stephen Chung
Stephen Chung

Reputation: 14605

What is wrong with just storing it in an array? The offsets are all defined (i.e., row #1 at 0, row #2 at 1, row #3 at 3 etc.) in a typical arithmetic sequence.

So, the array you'll have: [1, 2, 3, 4, 5, 6, ...]

Row #1 offset: 0;  // Base
Row #2 offset: (1) = 1;
Row #3 offset: (1 + 2) = 3;
Row #4 offset: (1 + 2 + 3) = 6;
Row #5 offset: (1 + 2 + 3 + 4) = 10;

And so on and so forth. The offset for row n is adding one through to n-1

The benefit is that, in building up this triangle, you can just keep "Add"-ing to the end of the array. If you split your string by some delimiter, the output of string.Split (an array) may even already be what you need!

To move/shift the elements, just add one element to the front! The offsets are all the same, but each element will be shifted to the next position!

Upvotes: 2

Related Questions