3

We are producing configuration files for a production system. The configuration files have a dynamic set of variables. Optional values and other values that only need to exist based on other values.

The system using these configuration files are depending on the parameters coming in the expected order. The current system is storing the sequence in the backend database. This ensures that value order is being preserved. However, it creates the challenge that any component that finds the need to introduce an optional variable that wasn't already in the database, must also find its "neighbors" in the database. This is more knowledge that shouldn't be necessary to merely add a variable. In addition, the neighbors may themselves be optional and not in the database.

In addition, the sorting order isn't really data. The order for any value set is always given. For example if the set is ["Cat1","Cat3","Dog2","Pete","Dog8","Cat2"], I know that the only correct order is "Pete","Cat1","Cat2","Cat3","Dog8","Dog2"

Let's say that the order followed these fules.

  • All labels not starting with "Cat" or "Dog", in alphabetical order.
  • All labels starting with "Cat" in alphabetical order.
  • All labels starting with "Dog" in reverse alphabetical order.

I find it hard to express such ruleset in code in a structured way.

In this particular case, this seem like something that would do the job:

finalOrder= initOrder.CategorizePrefix(
   new[]{Prefix="*", Next=Sort(d=>d.Label)},
   new[]{Prefix="Cat", Next=Sort(d=>d.Label)}
   new[]{Prefix="Dog", Next=SortReverse(d=>d.Label)}

But what if I needed a third/fourth level or another subcategorization?

It seems to me that a solution that implemented a composition model on top of IOrderedEnumerable such that every step would be able to pass a presort to its children would be more flexible. The data would decide which child to invoke for each subset in the IOrderedEnumerable.

But I don't quite understand how the invocation model of CreateOrderedEnumerable() would be implemented when the ThenBy step is conditional depending on the data.

9
  • Can you give an example for the hierarchical set of rules? The current example of sorting in categories and appending the results looks like being unrelated to the hierarchical sorting problem and might be worth a Q&A on its own. Mixing two problems in one makes it actually hard to understand what you are after and to give you a useful answer.
    – Doc Brown
    Jan 19 at 8:35
  • 1
    why cant you just codify the rules into a Icomparable or comparer class and sort any list?
    – Ewan
    Jan 19 at 10:00
  • 1
    @Tormod: clarifications should be edited into the question (and not in some terse addtional "Edit" section below). Just improve your question text, ideally by improving the examples. Other readers should have a chance to understand your question without reading alls the comments. Maybe I will answer this based on what you wrote, but I am still unsure if I really understood your problem correctly.
    – Doc Brown
    Jan 19 at 10:21
  • 3
    OOOf Don't invent new languages for business rules, you are heading down a rabbit hole. just code the rule and write tests for it.
    – Ewan
    Jan 19 at 10:37
  • 1
    "I aim to implement a common framework" is blowing the exercise of sorting a list well out of proportion. You're building a skyscraper so you can keep your car out of the rain. Save yourself a lot of headaches and build yourself a carport instead.
    – Flater
    Jan 23 at 3:59

4 Answers 4

7

How to tackle your specific example

In cases where you have individual rules for each category, those categories must be known at programming time. Things might become more complicated with dynamic categories, dynamic number of subcategories, and dynamic rules, but let me focus on the given example.

First, I would separate splitting into categories from the sorting problem. This leads to a subdivision into the following sub-problems:

  1. Splitting the data into different categories ("Cat", "Dog", "Default"). A function which does that may be called like this:

     IEnumerable<T>[] categories 
         =  Categorize(items, new[]("Cat*", "Dog*", "*"));
    

    How you define and implement the prefix filter syntax is up to you and your specific needs, here I suggest to use a "*" as a placeholder for an arbitrary string. You can also use regular expressions here, if you need that.

    Note usage of an array is just a simplified example, could be also a dictionary indexed by "Cat*", "Dog*", "*", or some other list of key-value pairs. Note also the order of the category filters is important, the order in which these filter steps have to be applied might be a different order than the one required in step 3.

  2. Sorting the data in each category individually with an individual rule

        categories[0] = categories[0].OrderBy(d=>d.Label);
        categories[1] = categories[1].OrderByDescending(d=>d.Label);
        categories[2] = categories[2].OrderBy(d=>d.Label);
    

    (you could also provide indidividual comparers here, or loop over all categories any apply different sorters, dependent from some other criteria).

  3. Sorting the categories themselves (here "Default", "Cat", "Dog") and merge the data accordingly.

        return categories[2].Concat(categories[0]).Concat(categories[1])
    

    (I hardcoded this order because the example with 3 categories is very simple. In cases the category order follows more complicated rules, this may require some more logic to sort, for example, by the category name, or some assigned priority) .

For the case of more hierarchy levels, you can do this in a nested fashion - so in step 2, you may call another function for sorting the specific category using their subcategories, and that function will probably have a very similar structure.

Can this done be more generically?

Sure, it can. A generic function CategorizedSort<T> which does the above requires the following input paramaters:

  • the elements to be sorted

  • an ordered list of pairs of the form

    (string prefixFilter , Func<IEnumerable<T>, IEnumerable<T>> sorter)`
    

    (could be also Func<IEnumerable<string>, IEnumerable<string>> categoryFilter instead of string prefixFilter, if you need it even more generic)

  • an ordering function for the categories themselves (for step 3)

So in total:

IEnumerable<T> CategorizedSort(
    IEnumerable<T> items,
    IEnumerable<(string prefixFilter , Func<IEnumerable<T>, IEnumerable<T>> sorter)>,
    Func<IEnumerable<string>, IEnumerable<string>> categorySorter)
     {
         //...
     }

This is called like

orderedItems = CategorizedSort(
       items,
       new[]{("Cat*", cats => cats.OrderBy(d=>d.Label)),
             ("Dog*", dogs => dogs.OrderByDescending(d=>d.Label)),
             ("*", x => x.OrderBy(d.Label))
            },
        MyOrderFunctionForCategories);

For nested hierarchies, the individual sorter functors can call this CategorizedSort recursively.

However, this is a pretty complex signature for a very specialized use case. To justify such a function, the number of cases where you can apply it (and where it actually simplify things for the caller!) should be more than just once or twice.

Is the generic approach a good idea?

In reality, it may be simpler for users not to make use of such a - maybe overdesigned - CategorizedSort<T> function, but implement the steps individually. The latter will make it also a lot easier to deal with currently unforeseen cases.

If, however, you find yourself writing the same kind category sorting function five, six or more times, then it may be justified to look for a more generic approach and refactor the code. That might not lead to the function I scetched above - maybe you can implement parts of your problem as generic building bricks. I would, however, resist the urge to design such a framework up-front.

4
  • This is the sort of path I was heading down. I still hope to achieve some level of composition since the actual data is more complex than the OP. Additionally, several subcompositions would be possible to reuse etc. I'll upvote and do some more digging. And accept if this is the path I end up going down. Thank you.
    – Tormod
    Jan 19 at 11:29
  • @Tormod: see my edit.
    – Doc Brown
    Jan 19 at 11:49
  • I think I would challenge this on the basis of the suggested algorithm structure not being amenable to change/expansion. You hardcode both the category sort and the sort of categories. Although simple to read, It's no better than simply hard coding a comparison predicate, with Cat* coming after Dog* etc
    – Ewan
    Jan 19 at 14:46
  • 1
    @Ewan: you hardcode both the category sort and the sort of categories." em, no, my scetched generic approach does not hardcode this, it takes both as input, as well as the functors for splitting the labels into categories. And I have my doubts about the sensibility of this approach pretty much like you.
    – Doc Brown
    Jan 19 at 20:25
1

I don't know C# very well, so I hacked together Python example which, hopefully gives you the key idea of the solution. I know I could convert this to Java which I'm pretty sure means you can do something similar in C#. Here's your initial example list sorted:

from functools import cmp_to_key

class Normal:
    def __init__(self, value):
        self.value = value

    def __lt__(self, other):
        return self.value < other.value

    def __eq__(self, other):
        return self.value == other.value
    

class Cat:
    def __init__(self, value):
        self.value = value

    def __lt__(self, other):
        return self.value < other.value

    def __eq__(self, other):
        return self.value == other.value
    

class Dog:
    def __init__(self, value):
        self.value = value

    def __lt__(self, other):
        return self.value > other.value

    def __eq__(self, other):
        return self.value == other.value


# ranking order of categories
rankings = [Normal, Cat, Dog]


def factory(item):
    if item.startswith("Cat"):
        return Cat(item)
    elif item.startswith("Dog"):
        return Dog(item)
    else:
        return Normal(item)


def ranked_sorter(a, b):
    a_rank = rankings.index(type(a))
    b_rank = rankings.index(type(b))

    difference = a_rank - b_rank

    if difference == 0:
        if a < b:
            return -1
        elif a > b:
            return 1
        else:
            return 0
    else:
        return difference


items = ["Cat1","Cat3","Dog2","Pete","Dog8","Cat2"]
wrapped = list([factory(item) for item in items])

wrapped.sort(key=cmp_to_key(ranked_sorter))

print([item.value for item in wrapped])

If you want to add a category, you would need to simply:

  1. Create a new wrapper class
  2. Modify your factory method
  3. Add the type to the ranking order

If this isn't clear and/or you don't grok Python, let me know and I'll try to work something out.

I realized that you are working with LINQ which I have never bothered to learn but I understand it as being a roughly functional paradigm. I'm not going to learn now so here's the essential approach to what I am suggesting:

  1. Categorize your inputs
  2. Give each category a rank
  3. Sort by the category rank, then intra-category rules

Adendum

To DocBrown's point in the comments, the above code is overly verbose for this problem. I'm going to leave it as-is because it's easy to understand but here's an incremental immprovement:

# ranking order of categories
RANKINGS = ["Default", "Cat", "Dog"]

def reverse(a, b):
    return b < a

class Categorized:
    def __init__(self, category, value, ordering=None):
        self.category = category
        self.value = value
        self.ordering = ordering

    def __lt__(self, other: Categorized):
        self_rank = RANKINGS.index(self.category)
        other_rank = RANKINGS.index(other.category)

        difference = self_rank - other_rank

        if difference < 0:
            return True
        elif difference > 0:
            return False
        elif self.ordering is not None:
            return ordering(self.value, other.value)
        else:
            return self.value < other.value

    def __eq__(self, other):
        return self.category == other.category \
           and self.value == other.value


def factory(item):
    if item.startswith("Cat"):
        return Categorized("Cat", item)
    elif item.startswith("Dog"):
        return Categorized("Dog", item, reverse)
    else:
        return Categorized("Default", item)


items = ["Cat1","Cat3","Dog2","Pete","Dog8","Cat2"]
wrapped = list([factory(item) for item in items])

wrapped.sort()

print([item.value for item in wrapped])

With this version, you don't need a new class for each category. You would simply need to define a new category, update the factory in kind. If you have a special sorting rule, you can add another function which matches the signature of reverse.

3
  • So this code defines one class per category, and the only responsibilty of that ~10 lines of code per class is to encapsulate the comparator for the elements of the class. For my taste, this creates more boilerplate than necessary. Note this has nothing to do with Python vs. C# - in Python, one could write down the comparator using anonymous functions very similar to C# in a simple expression which requires less than half a line of code - with better readability.
    – Doc Brown
    Jan 20 at 5:41
  • @DocBrown I agree this could be slimmed down. I was mainly trying to get the idea across in a working example that I wrote in a bit of a rush. Essentially, the concept boils down to treating the type as the primary sorting feature.
    – JimmyJames
    Jan 22 at 15:25
  • @DocBrown I think the new example is better. Thoughts?
    – JimmyJames
    Jan 22 at 16:06
-1

Greenspun's tenth rule:

Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp.

I assume your system can save its configuration in the correct order to be able to load it afterwards.

This means all the information about configuration items order is already available.

It may not be available in an easy to exploit or explicit way, but it is there. It's probably defined implicitly in the order of the lines of code that save the parameters. That primary definition is sufficient.

Creating a secondary representation of this order in the form of rules is hazardous. How will you be sure that it matches the primary definition? That it stays in sync through all the next versions?

Here's a much simpler solution that doesn't require inventing a lispish domain specific langauge :

I assume your stuff is hierarchic, so there's a tree, with a .saveConfig() method on the root, that calls similar methods on all the branches in the correct order, etc.

Add a boolean parameter "templateMode" to this method, default false.

When templateMode == false, the current behavior is conserved.

When templateMode == true, it also saves all optional values and parameters. The values it saves is not important, that can be set to NULL. What matters is that it will save all the keys in the correct order. So the result is not a configuration file, but a fill-in-the-blanks configuration template.

You can then store this list of keys in a separate database table.

The sorting key for any item can simply be the row or line number.

You will have to implement this anyway in order to unit test your rules-based sorting, so why not just use it?

1
  • Yes, the ideal sorting is a given and the "true source" is of course the runtime system that uses these files. But this is comprised of many code bases in C, C++ and C#. I appreciate your concern about duplication. But there is no lack of proper examples. All it takes is a suite of unit tests that are given examples from the mother system and confirm that after sorting the original order is preserved. The problem is not to preserve input order, but to edit the set and then output in the same order that the mother system would.
    – Tormod
    Jan 22 at 12:12
-1

I'm prompted to write my own answer here because I think docs skims over some of the pitfalls.

Here is some sample code where we try to structure the "CategorySort" so that it can be modified as new requirements come in, or potentially be made dynamic so that a user can fiddle with the rules at runtime via the config.

  1. We introduce a class Category which allows us to give it the properties in our business logic. ie, sort direction and filter.

  2. We then make an ordered list of Categories so we can tell which comes first

  3. We add a sort predicate which first finds and compares the category, then applies the reverse sort if required.

This is all well and good, you can imagine an array of categories in some json config, where you can edit them, add new ones, fiddle with the order etc.

But you can see even here we run into the problem of the filter not being something that is easy to define. I've had to hard code it. You could use a regex instead, or maybe develop your own language or syntax, "*" means "matches anything", "default" matches none of the other categories

We should also consider other changes, what if a requirement comes in which is "if the value is a number sort numerically rather than alphabetically" for example? We would have to expand the Category class so we could somehow indicate this option.

The problem with this kind of thing is that there is no limit or scope to the possible rules when the rules are "business logic" The structure you create to store, in this case the configuration, must be complex enough to contain any possible business logic. Which is the same complexity as the programming language you are writing it in. You will end up having to have javascript functions in your config!

Instead it is a better approach to either just hard code the rules and have no dynamic config at all. OR, completely specify the setup in config. (ie put the correct order in the config)

code.

using System;
using System.Linq;
using System.Collections.Generic;
                    
public class Program
{
    static Category[] categories = new [] {
        new Category() {IsInCat = i => !i.StartsWith("Dog") && ! i.StartsWith("Cat")},
        new Category() {IsInCat = i => i.StartsWith("Cat")},
        new Category() {IsInCat = i => i.StartsWith("Dog"), SortDesc=true},
    };
    
    public static void Main()
    {
        var ordered = new List<string>(){"Cat1","Cat3","Dog2","Pete","Dog8","Cat2"};
        ordered.Sort(CategorySorter);
        Console.WriteLine(String.Join(",",ordered));
    }
    
    //write a bunch of tests for this
    public static int CategorySorter(string a, string b)
    {
        var catA = GetCat(a);
        var catB = GetCat(b);
        if(catA != catB)
        {
            return catA.CompareTo(catB); //if categories dont match then order by category
        }
        var comp =  a.CompareTo(b); //if in same cat then order alphabetically
        if(categories[catA].SortDesc) //unless its a reversed category
        {
            return comp * -1;
        }
        else
        {
            return comp;
        }
    }
    
    public static int GetCat(string a)
    {
        for(int i =0;i< categories.Length;i++)
        {
            if(categories[i].IsInCat(a))
            {
                return i;
            }
        }
        throw new Exception("no match");
    }
}

public class Category
{
    public Func<string,bool> IsInCat;
    public bool SortDesc;
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.