Как реализовать класс Stack в C # с пред / постусловиями и инвариантами? - PullRequest
Новая
       48

Как реализовать класс Stack в C # с пред / постусловиями и инвариантами?

4 голосов
/ 06 октября 2011

Есть ли у кого-нибудь примеры или идеи о том, как / как лучше всего реализовать класс Stack в C #? Я понимаю, что класс Stack уже существует, но мне нужно понять, как на самом деле реализовать класс Stack.

Мне также нужен совет о том, как использовать Контракты в C # для определения предварительных условий, постусловий и инвариантов для этого класса. Я думаю, что раньше использовал нечто подобное при создании моделей в архитектуре ASP.NET MVC, но я не совсем уверен, что это то же самое и работает так же. (Я немного растерялся в предусловиях / постусловиях / инвариантах, если ты не мог уже сказать - пожалуйста, потерпи меня).

Мой главный вопрос - может ли кто-нибудь дать мне совет относительно правильного использования контрактов для такого класса, как стек.

Да, я выложил усилие: 

public interface IStack
{
        void Push(Object e);
        Object Pop();
        Object Top();
        void EnsureCapacity();
    }
}

   public class Stack : IStack
{
    private Object[] elements;
    private int size = 0;

    public Stack()
    {
        elements = new Object[0];
    }

    public void Push(Object e)
    {
        // check if this array capacity has been reached and increase if needed
        EnsureCapacity();
        elements[size++] = e;
    }

    public Object Pop()
    {
        // check if the method call is invalid for the object's current state
        if (size == 0) throw new InvalidOperationException("Stack.Pop");

        Object result = elements[--size];
        elements[size] = null;

        return result;
    }

    public Object Top()
    {
        // check if the method call is invalid for the object's current state
        if (size == 0) throw new InvalidOperationException("Stack.top");
        return elements[(size - 1)];
    }

    private void EnsureCapacity()
    {
        if (elements.Length == size)
        {
            Object[] oldElements = elements;
            elements = new Object[(2 * size + 1)];
        }
    }
}

Ответы [ 3 ]

1 голос
/ 06 октября 2011

Если хотите, чтобы начать использовать Microsoft Code Contracts, я однажды написал в блоге об этом .Этот пост охватывает самые базовые предпосылки, постусловия и инварианты.

Как краткое изложение понятий, вы можете думать о них следующим образом:

  • Предварительным условием является то, что должно быть верно до выполнения метода - что клиенты обещают вашему методу.
  • Инвариант - это то, что должно всегда оставаться публично истинным, когда речь идет о клиентах вашего класса.
  • Постусловие - это то, что должно быть верно после выполнения метода - что ваш метод обещает клиентам.

Итак, для моей стопки, легкая мысль, о которой можно подумать, может быть инвариантом.Если вы моделируете стек с помощью массива, вы можете объявить инвариант в классе, что массив никогда не устанавливается равным нулю, например, вы бы определили инвариантный метод: 

[ContractInvariantMethod]
private void ObjectInvariant()
{
   Contract.Invariant(elements != null);
}

Это выглядит таку вас уже есть предварительное условие для вашего метода pop - вы хотите сказать, что пользователь должен убедиться, что стек не пуст, когда он выполняет pop.Итак, в начале метода pop у вас будет: 

Contract.Requires(size > 0);

И, наконец, вы можете указать пост-условие для pop, этот размер всегда будет меньше, чем был до операции pop(вы можете получить более конкретную информацию, если хотите): 

Contract.Ensures(Contract.OldValue<int>(size) > size);

Удачи вам в этом - контракты классные и полезные.Это очень чистый способ кодирования.

1 голос
/ 06 октября 2011

Многие из коллекций, реализованных в c #, основаны на массивах. Вы можете использовать массив и добавлять элементы в конец, хранить индекс верхнего элемента и увеличивать его, пока новые элементы выдвигаются, конечно, массив должен будет «расширяться» (заменяться новым) динамически, когда появляются новые объекты и существует нет места для них в текущем массиве.

кодовые контракты имеют довольно хорошую документацию, доступную на http://research.microsoft.com/en-us/projects/contracts/userdoc.pdf

0 голосов
/ 06 октября 2011

Документ, на который ссылается @wiero, хорош.Если вы хотите понять использование и обоснование концепций, поддерживаемых реализацией CodeContracts, поищите информацию о «Проектировании по контракту», введение которой здесь:

http://en.wikipedia.org/wiki/Design_by_contract

Идея об этом стала популярной Бертраном Мейером в его книге «Построение объектно-ориентированного программного обеспечения», где она подробно обсуждается.Поскольку он торговал торговой маркой «Design By Contract» через свою компанию, другие реализации должны иметь другие названия (например, «CodeContracts»).

...