Validate the order of a List<string> by custom strings

Question

I have a test where I have to validate the order of items in a List based on a pre-defined hierarchy that is being given to me as part of my assignment. Here it is below.

1. Cat
2. Dog
3. Horse
4. Elephant

The items in the list would only ever be those four types, but the size of list is not limited. The list will be passed in as part of the method. There can be multiple of each or none at all. The below two list would be valid:

1. Cat
2. Cat
3. Dog
4. Elephant

This would not.

1. Elephant
2. Dog
3. Horse
4. Cat

Below is what I have so far, and I feel as though there is a much more elegant solution. In particular, I would like to minimize the amount of bools and if statements I am using.

public bool ValidateAnimalOrder(List<string> listOfAnimals)
{
    bool catExists = false;
    bool dogExists = false;
    bool horseExists = false;
    bool elephantExists = false;

    for (int x = 0; x < listOfAnimals.Count; x++)
    {
        if (listOfAnimals[x] == "Cat")
        {
            catExists = true;
            if(dogExists || horseExists || elephantExists)
            {
                return false;
            }
        }
        if (listOfAnimals[x] == "Dog")
        {
            dogExists = true;
            if (horseExists || elephantExists)
            {
                return false;
            }
        }
        if (listOfAnimals[x] == "Horse")
        {
            horseExists = true;
            if (elephantExists)
            {
                return false;
            }
        }
        if (listOfAnimals[x] == "Elephant")
        {
            elephantExists = true;
        }

    }

    return true;
}

Answer 1

Dictionary

I'd prefer to store animal names and their "values" in a dictionary.

private static readonly Dictionary<string, int> AnimalValues = new Dictionary<string, int>
        {
            { "Cat", 1 },
            { "Dog", 2 },
            { "Horse", 3 },
            { "Elephant", 4 }
        };

Then the validation method will look like:

public static bool IsValidAnimalOrder(IEnumerable<string> animalNames)
{
    int prevValue = 0;
    foreach (string animalName in animalNames)
    {
        int curValue;
        if (!AnimalValues.TryGetValue(animalName, out curValue))
        {
            // If the animal's name is absent in the dictionary.
            return false;
        }
        if (curValue < prevValue)
        {
            // If the current animal's value less than the previous one.
            return false;
        }
        prevValue = curValue;
    }
    return true;
}

---

switch

Alternative way is to use the switch operator instead of a dictionary as follows:

public static bool IsValidAnimalOrder(IEnumerable<string> animalNames)
{
    int prevValue = 0;
    foreach (string animalName in animalNames)
    {
        int curValue;
        switch (animalName)
        {
            case "Cat":
                curValue = 1;
                break;
            case "Dog":
                curValue = 2;
                break;
            case "Horse":
                curValue = 3;
                break;
            case "Elephant":
                curValue = 4;
                break;
            default:
                // If the animal's name is not listed above.
                return false;
        }
        if (curValue < prevValue)
        {
            // If the current animal's value less than the previous.
            return false;
        }
        prevValue = curValue;
    }
    return true;
}

---

IEnumerable<T> problem

As @Mat's Mug♦ mentioned, IEnumerable<T> doesn't guarantee the order of its elements. So you could change argument type to IList<T> or IReadOnlyList<T>. But this will reject another enumerations with the specified order: IOrderedEnumerable<T> and IOrderedQueryable<T>.
As a workaround you could make the method above private and declare public overloads accepting all the suitable enumeration types above as argument:

public static bool IsValidAnimalOrder(IReadOnlyList<string> animalNames)
{
    return IsValidAnimalOrder((IEnumerable<string>)animalNames);
}

public static bool IsValidAnimalOrder(IOrderedEnumerable<string> animalNames)
{
    return IsValidAnimalOrder((IEnumerable<string>)animalNames);
}

public static bool IsValidAnimalOrder(IOrderedQueryable<string> animalNames)
{
    return IsValidAnimalOrder((IEnumerable<string>)animalNames);
}

Answer 2

listOfAnimals is how you pronounce List<Animal> out loud; a better name would be simply animalNames, and the function doesn't really need to work off a List<string> - a concrete type; it could just as well work with some string[] array, no? Hence, I think your parameter type would be better off as an IReadOnlyList<string> - IEnumerable<string> would work too, but it doesn't guarantee the order of its elements, which is important here.

Also, by convention the method's name could be IsValidXxxx, because it's a bool:

public bool IsValidOrder(IReadOnlyList<string> animalNames)

But let's think outside the box a bit, just for fun. We want a custom way to compare strings. This looks like a job for an IComparer<string>, no?

I'll steal @Dmitry's dictionary here (an excellent idea BTW):

public class AnimalNameComparer : IComparer<string>
{
    private readonly Dictionary<string, int> _values = new Dictionary<string, int>
    {
        { "Cat", 1 },
        { "Dog", 2 },
        { "Horse", 3 },
        { "Elephant", 4 }
    };

    public int Compare(string x, string y)
    {
        if (!_values.ContainsKey(x) || !_values.ContainsKey(y))
        {
            throw new ArgumentOutOfRangeException();
        }

        return _values[x].CompareTo(_values[y]);
    }
}

The comparer throws an ArgumentOutOfRangeException if we give it an unknown animal name, otherwise returns the result of comparing the int value associated to each animal name. So far so good?

Good. Now let's get funky.

Imagine a simple function. It takes two strings: the current one being iterated, and one that's remembered from the previous iteration.

The function then uses the AnimalNameComparer to compare these two strings; if the current string is (per the comparer) "smaller than or equal to" the previous string, then it returns the current - otherwise it returns an empty string; if we reach the end of our list and the result is an empty string, the order isn't "valid".

With LINQ's Aggregate extension method, we can completely inline this logic (here, I've split it on two lines to reduce horizontal scrolling a bit):

private static readonly IComparer<string> Comparer = new AnimalNameComparer();
public static bool IsValidOrder(IReadOnlyList<string> animalNames)
{
    !string.IsNullOrEmpty(animalNames.Aggregate((previous, current) => 
        Comparer.Compare(previous, current) <= 0 ? current : string.Empty));
}

And as a bonus the caller can now use a catch block and chose to act differently when an "illegal animal" is present in the input. Or, you can wrap the animalNames.Aggregate call in a try/catch block and return false, if you want to do that.

Note that this traverses the entire source; @Dmitry's solution returns as soon as possible - this LINQ solution is just to illustrate an alternative approach, and is harder to read and understand than a straightforward foreach loop, which should be preferred in this case.

Answer 3

If you use an enum for the animals then the code is virtually a one-liner. Here's an example:

enum Animal
{ 
    Cat = 1,
    Dog = 2,
    Horse = 3,
    Elephant = 4,
}

To validate the order use this simple extension:

static class Extensions 
{
    public static bool HasValidOrder(this IEnumerable<Animal> animals) 
    {
        return animals.SequenceEqual(animals.OrderBy(x => x));
    }
}

You could also use strings but ten you'd need to parse the values and then sort them before you compare the collections.

Usage:

var animals1 = new List<Animal> 
{
    Animal.Cat,
    Animal.Cat,
    Animal.Dog,
    Animal.Elephant
};

var animals2 = new List<Animal>
{
    Animal.Elephant,
    Animal.Cat,
    Animal.Dog,
    Animal.Cat,
};

var result1 = animals1.HasValidOrder(); // true
var result2 = animals2.HasValidOrder(); // false

---

ValidateAnimalOrder

Usually when a method's name is ValidateX then it throws an exeption if the validation fails. In your case it would be better to call it HasValidOrder because it returns a bool.

Answer 4

First, let's define a method to figure out whether a list follows another list order:

    public static bool IsValidOrder<T>(this IEnumerable<T> items, IEnumerable<T> order)
    {
        IEnumerator<T> orderEnumerator = order.GetEnumerator();
        orderEnumerator.MoveNext();
        return items.All(item => orderEnumerator.ReadUntilGet(item));
    }

    public static bool ReadUntilGet<T>(this IEnumerator<T> enumerator, T item)
    {
        return enumerator.Current.Equals(item) ||
            (enumerator.MoveNext() && enumerator.ReadUntilGet(item));
    }

The ReadUntilGet<T> method check if the current is equals to the T item, if it is not it moves the enumerator to the next position and calls itself recursively until it finds the T item, then it returns true. If it reaches the end of the enumerator without finding the T item, it returns false.

The LINQ All<T> method check if all elements of a sequence satisfy a condition. Since we call the ReadUntilGet<T> method inside the condition, it is called on each item from the list. And the enumerator moves on each new item on the list. If it return false in any of them, the All method return false.

Since the animals can contain names which string representation is not equal to a enum identifier it's better to use strings to define the order, as @Mat'sMug pointed out.

We can define the order in a list. Notice that numbers indicating the order are not needed because the order of the list is guaranteed to remain the same (the IEnumerable<T> interface just iterates, it does not change ordering, AFAIK. At this answer it's said otherwise, would you care to explain? I don't have enough reputation to comment):

    public static IEnumerable<string> AnimalOrder { get; } = new List<string>
    {
        "Cat",
        "Horse",
        "Dog",
        "Elephant",
        "Great white shark"
    };

So, your method would be:

    public bool ValidateAnimalOrder(List<string> listOfAnimals)
    {
        return listOfAnimals.IsValidOrder(AnimalOrder);
    }

Note that this method iterate just once on both lists and returns as soon as possible (because the All method returns on the first item that doesn't match).

Answer 5

I think your solution is quite OK, it is doing what you want it to do. You can sharpen the if-statements a little by using else if for all if's but the first, because an animal can only be one kind. Alternatively you can experiment with a switch-statement instead which will make the code more clear. By the way: you don't need the flag for cats (catExists) because it's the 'lowest' level of animal type.

You solution with a switch statement instead of if's:

static bool ValidateAnimalOrder(List<string> listOfAnimals)
{
  bool dogExists = false;
  bool horseExists = false;
  bool elephantExists = false;


  foreach (var animal in listOfAnimals)
  {
    switch (animal)
    {
      case "Cat":
        if (dogExists || horseExists || elephantExists)
        {
          return false;
        }
        break;
      case "Dog":
        dogExists = true;
        if (horseExists || elephantExists)
        {
          return false;
        }
        break;
      case "Horse":
        horseExists = true;
        if (elephantExists)
        {
          return false;
        }
        break;
      case "Elephant":
        elephantExists = true;
        break;
      default:
        throw new Exception($"Wrong kind of animal: {animal}");
    }
  }

  return true;
}

A more 'advanced' approach could be the following, where I use a little Linq and an enum of Animals:

// The valid Animal Types
enum Animals
{
  None = -1,
  Cat = 0,
  Dog = 1,
  Horse = 2,
  Elephant = 3
}

static bool ValidateAnimalOrder(List<string> listOfAnimals)
{
  // One flag for each animal type
  bool[] flags = new bool[Enum.GetValues(typeof(Animals)).Length];

  foreach (var animal in listOfAnimals)
  {
    // Converts the current animal name string to an integer index
    Animals animalType;
    if (Enum.TryParse<Animals>(animal, out animalType))
    {
      int index = (int)animalType;

      // If flags has an entry > index which is true, then the order of the list is invalid
      if (flags.Skip(index + 1).Any(f => f))
        return false;

      // The current animal flag is set to true
      flags[index] = true;
    }
    else
    {
      throw new Exception($"Wrong kind of animal: {animal}");
    }
  }

  return true;
}

An even more condensed solution could be:

// The valid Animal Types
enum Animals
{
  Cat = 0,
  Dog = 1,
  Horse = 2,
  Elephant = 3
}


static bool ValidateAnimalOrder2(List<string> listOfAnimals)
{
  Animals lastAnimal = Animals.None;

  foreach (var animal in listOfAnimals)
  {
    // Converts the current animal name string to an Animals enum
    Animals curAnimal;
    if (Enum.TryParse<Animals>(animal, out curAnimal))
    {
      // If the current animal is a 'smaller' animal than the last, then the list is invalid
      if (curAnimal < lastAnimal)
        return false;

      lastAnimal = curAnimal;
    }
    else
    {
      throw new Exception($"Wrong kind of animal: {animal}");
    }
  }

  return true;
}

or:

static bool ValidateAnimalOrder3(List<string> listOfAnimals)
{
  Animals lastAnimal = Animals.None;

  foreach (var curAnimal in listOfAnimals.ConvertAll<Animals>((a) => (Animals)Enum.Parse(typeof(Animals), a)))
  {
    // If the current animal is a 'smaller' animal than the last, then the list is invalid
    if (curAnimal < lastAnimal)
      return false;

    lastAnimal = curAnimal;
  }

  return true;
}