问:
Why do we need frameworks for dependency injection?
I've been reading up more on the Inversion of Control principle and Dependency Injection as an implementation of it and am pretty sure I understand it.

It seems to be basically saying 'don't declare your class members' instantiations within the class'. Rather that the instantiations should be passed in and assigned through the constructor; 'injected' into the class from an outside source.

If it's this simple, which it seems to be, why do we need frameworks like spring or guice that implement this with annotations? Am I missing something fundamental here? I'm really struggling to understand what the use of Dependency Injection frameworks are.

Edit: About the possible duplicate, I believe my question is more unique as it is asking about DI frameworks in general, not just Spring. Spring is not just a DI framework, so there are many reasons that someone would want to use Spring that aren't related to DI.

答:
With spring, it is mostly a matter of convenience.

If you have class TopLevel which is constructs class MiddleLevel which constructs class LowLevel, and you realize you need a new constructor parameter on LowLevel, you have to also add it to TopLevel, and to MiddleLevel, simply so that when it is time for MiddleLevel to construct a LowLevel the value will be available so that it can be passed to its constructor.  With spring, you just add an annotation.

Also, with spring, it is possible to define the dependencies in an  external configuration file instead of xml, and this supposedly gives you the ability to generate a new system with an entirely different wiring "without changing any code".  (IMHO this is completely misdirected, because altering xml is not that much different from altering code, and actually, code usually has far better error checking and type checking than xml does.)

Another thing is that many people are afraid of constructors; they don't understand them, they don't like them, they'd rather not use them.


问:
Do people in non-English-speaking countries code in English?
I've heard it said (by coworkers) that everyone "codes in English" regardless of where they're from. I find that difficult to believe, however I wouldn't be surprised if, for most programming languages, the supported character set is relatively narrow.

Have you ever worked in a country where English is not the primary language?

If so, what did their code look like?

答:
I am from Denmark, and even though many of the technical terms translates nicely to danish, it is the norm to use the english terms (though some tend to ONLY use the danish terms, but I guess you see them everywhere).

Personally, I code in English; Meaning that all my comments, my variables, classes and so on, are in English. I do this because it makes it so much easier. If I want to make my code public, everybody can read and understand the program. If I am going to help out a friend with a code-example, I don't have to translate the comments beforehand.

ContentLicense: CC BY-SA 3.0

ContentLicense: CC BY-SA 2.5


答:
We don't need the frameworks. It is entirely possible to implement dependency injection manually, even for a relatively large project.

On the other hand, using a framework makes it easier, particularly one based on annotations or automatic detection of dependencies, as it makes the process simpler: if I decide that I need a new dependency in a class, all I have to do is add it to the constructor (or declare a setter)  and the object is injected - I don't need to change any instantiation code.

Also, frameworks often contain other useful functionality. Spring, for example, contains a useful framework for aspect oriented programing, including declarative transaction demarcation (which is extremely handy) and a variety of adapter implementations that make many 3rd party libraries easier to integrate.

Title: Why do we need frameworks for dependency injection?

Body:
I've been reading up more on the Inversion of Control principle and Dependency Injection as an implementation of it and am pretty sure I understand it.

It seems to be basically saying 'don't declare your class members' instantiations within the class'. Rather that the instantiations should be passed in and assigned through the constructor; 'injected' into the class from an outside source.

If it's this simple, which it seems to be, why do we need frameworks like spring or guice that implement this with annotations? Am I missing something fundamental here? I'm really struggling to understand what the use of Dependency Injection frameworks are.

Edit: About the possible duplicate, I believe my question is more unique as it is asking about DI frameworks in general, not just Spring. Spring is not just a DI framework, so there are many reasons that someone would want to use Spring that aren't related to DI.


问:
Illusory code duplication
The usual instinct is to remove any code duplication that you see in the code. However, I found myself in a situation where the duplication is illusory.

To describe the situation in more details: I am developing a web application, and most views are basically the same - they display a list of items which the user can scroll and choose from, a second list that contains selected items, and a "Save" button to save the new list.

It seemed to me that the problem is easy. However, each and every view has its own quirks - sometimes you need to recalculate something, sometimes you must store some additional data etc. These, I solved by inserting callback hooks in the main logic code.

There are so many minute differences between the views that it is becoming less and less maintainable, because I need to provide callbacks for basically all functionality, and the main logic starts to look like a huge sequence of callback invocations. In the end I am not saving any time or code, because every view has its own code that is executed - all in callbacks.

The problems are:

the differences are so minute that the code looks almost exactly alike in all views,

there are so many differences that when you look at the details, to code is not a bit alike

How should I handle this situation?

Is having core logic composed entirely of callback calls a good solution?

Or should I rather duplicate the code and drop the complexity of callback-based code?

答:
One issue might be that you are providing an interface (theoretical interface, not language feature) to only a single level of the functionality:

```<code>A(a,b,c) //a,b,c are your callbacks or other dependencies
</code>```

Instead of multiple levels depending on how much control is required:

```<code>//high level
A(a,b,c)
//lower
A myA(a,b)
B(myA,c)
//even lower
A myA(a)
B myB(myA,b)
C myC(myB,c)
//all the way down to you just having to write the code yourself
</code>```

As far as I understood, you only expose the high level interface (A), hiding the implementation details (the other things there).

Hiding implementation details has advantages, and you just found a disadvantage - control is limited, unless you explicitly add features for every single thing that would have been possible when directly using the low level interface(s).

So, you have two options. Either you only use the low level interface, use the low level interface because the high level interface was too much work to maintain, or expose both high and low level interfaces. The only sensible option is to offer both high and low level interfaces (and everything inbetween), assuming you want to avoid redundant code.

Then when writing another one of your things, you look at all the available functionality you have written that far (countless possibilities, up to you to decide which ones might be reused) and piece them together.

Use a single object where you need little control.

Use the lowest level functionality when some weirdness needs to happen.

Its also not very black-and-white. Maybe your big high level class CAN reasonably cover all the possible use cases. Maybe the use cases are so varying that nothing but the lowest level primitive functionality suffices. Up to you to find the balance.

Title: Illusory code duplication

Body:
One issue might be that you are providing an interface (theoretical interface, not language feature) to only a single level of the functionality:

A(a,b,c) //a,b,c are your callbacks or other dependencies

Instead of multiple levels depending on how much control is required:

//high level
A(a,b,c)
//lower
A myA(a,b)
B(myA,c)
//even lower
A myA(a)
B myB(myA,b)
C myC(myB,c)
//all the way down to you just having to write the code yourself

As far as I understood, you only expose the high level interface (A), hiding the implementation details (the other things there).

Hiding implementation details has advantages, and you just found a disadvantage - control is limited, unless you explicitly add features for every single thing that would have been possible when directly using the low level interface(s).

So, you have two options. Either you only use the low level interface, use the low level interface because the high level interface was too much work to maintain, or expose both high and low level interfaces. The only sensible option is to offer both high and low level interfaces (and everything inbetween), assuming you want to avoid redundant code.

Then when writing another one of your things, you look at all the available functionality you have written that far (countless possibilities, up to you to decide which ones might be reused) and piece them together.

Use a single object where you need little control.

Use the lowest level functionality when some weirdness needs to happen.

Its also not very black-and-white. Maybe your big high level class CAN reasonably cover all the possible use cases. Maybe the use cases are so varying that nothing but the lowest level primitive functionality suffices. Up to you to find the balance.


答:
Why do we need DI (Dependency Injection) at all?

The DI mechanism separates object production from object consumption. The dependecies an object needs are delivered transparently from the outside. The advantage of the mechanism is clear: You could anytime swap out dependencies, e.g. usìng a Null Object for testing purposes.

How is it done?

There are several ways to achieve the goal:

Injecting dependencies via constructor injection

Injection via getter/setter

Interface Injection

Do we need DI frameworks?

No. Not at all. You could simply pass all instances to other objects manually. If you have a small application, there is no need for a spring container.

But on the other hand, frameworks give you a helping hand, managing objects:

They help you wiring up complex object relationships. You have to write no boilerplate code, to generate instances and pass them to the appropriate objects

They help you control when an object is created: you could create instances during application bootstrapping, but in some cases a lazy creation - only when needed - is better

They help you control how many instances are created: one per application lifetime or one per request (in case you are doing web-programming)

If you project has an appropriate size - if you feel the need to write less boilerplate code - it totally makes sense using a (DI-) framework. There are more pros than cons.


问:
Pattern for interface between sequence executing object(s) and sequence configuration objects
My motivating case is hardware test automation. We have several different testers (benches of lab equipment that connect to the "device under test" (DUT)), and we write test configuration files which instruct the tester what series of tests to perform. The tests performed take in parameters from the configuration as well.

At the moment the coupling between these is higher than I'd like, so I'm trying to find a good pattern to keep the logic for how we perform tests ("tester" object(s)) separate from what tests we wish to perform in any particular run (the configuration objects).

The best I've come up with so far is as follows (syntax not verified, just getting the idea across):

```<code>class TestStepConfig
{
    string Name;
    // Parameters are tuple of parameter name to parameter value. If parameter is not truly a string, it will be converted to int, float, etc later.
    IReadOnlyList<Tuple<string, string>> Parameters;
}

interface ITester
{
    // Return value is any data coming back from the test. First tuple element is result name, second is result value (I.E. "Voltage","5.0")
    List<Tuple<string, string>> RunTestStep(TestStepConfig config);
}

class NaiveSequencer
{

    List<TestStepConfig> configs;
    ITester tester;

    void RunFullTest()
    {
        foreach (var config in configs)
            tester.RunTestStep(config);
    }

}
</code>```

The idea is that each tester has a set of atomic test steps it can run. It knows these steps by name, and the steps take in a set of parameters as per the Parameters field of the TestStepConfig. So, you pass in a TestStepConfig with the name of the desired step and the desired parameters, and the tester performs that test step.

Thus, all any configuration scheme needs to do is determine which TestStepConfigs to feed into the tester, and all the tester needs to understand is how to execute these atomic TestSteps.

What has me wary of this solution is that the "TestStepConfig" looks uncomfortably like re-implementing a method call ("Name" of method, "Parameters" to pass in). I don't want to implement the testers as an actual set of specific "test this, test that" methods because:

There may be many, many such test steps available (anywhere from 20
to over 100), leading to extremely large, rigid objects.

Many of these tests may or may not be available depending on the
particular configuration of the bench (what equipment is available,
etc).

How a TestStep of a particular name is executed may change

depending on the setup (what part is being tested, etc)

I need to be able to perform sequences of tests with many different
testers, and I can't be re-writing the sequencing algorithms every
time there's a new tester just because it has a different interface

For these reason and more, the TestSteps I feel are much better modeled as a group of something similar to a Command Pattern (but with execute-time parameters) brought together by a factory and placed into a generic implementation of a ITester object, rather than modeled as compile-time methods of the Tester.

Has anyone had to deal with a case like this before? Is there a better pattern than the one I've proposed above?

答:
Has anyone had to deal with a case like this before?

Your bench/test configuration is more complex than I've dealt with, but it is the same problem, just more layers of construction.

Warning: Do not get caught up in inventing framework to genericise and abstract any structure, any test, any time.

Identify, classify, and organize every test

Whether a test is a single method or a series of methods, or a class composite, they're all tests and each test should be explictly identifiable.

Each test should be designed to run by itself. It may run as part of a series of consecutive tests but each identifiable test must be fundamentally independent.

Coding too soon

Thinking in terms of "methods" is too narrow, too sub-atomic as it were. That is why you're seeing "the coupling between these is higher than I'd like." Get the logical organization and the code framework will emerge from that.

Test Structure Observations

TestBenches - create a config section.

TestBench is probably the top of the structure.  This can also act as a namespace, tests in different testbenches can have the same name.

Structure will be directly reflected in the config file elements.

Test order in the config file is execution order.

Factory Observations

You will have an abstract factory. You may have the builder pattern depending on the dynamics of constructing any given test.

The abstract factory structure will map directly to the config file structure. It knows the structure. It will necessarily be tightly coupled to the config file.

Config element names will be converted to enums. The various enums will reflect the config structure. For example TestBenchXFactory will use a Xtests enum. This effectively validates the XML elements before we attempt to use it.

OO observations

Lots of passing the buck but it is all dead simple code until we get to construction of concrete, dynamic test objects.

The number of factories may seem excessive or totally unnecessary. However, We're minimizing coupling of layer construction

Adding, removing tests may seem like Open/Closed principle violation, but "frankly my dear, I don't give a damn."

Good adherence to single responsibility principle in the factory classes makes change easy. Again, Each logical test is independent

```<code><BenchTests>
    <!- BenchTestFactory gets <BenchTests> as a parameter -->
    <!- builds a BenchTestCollection. Instantiate sBenchTestXFactory, etc. -->
    <!- Adds concrete `BenchTest`s to the collection. -->
    <TestBenchX>
        <!- `BenchTestXFactory` gets `<TestBenchX>` element as a parameter -->
        <!- instantiates `BenchTestX` object. Builds each test, adds to `BenchTestX`. -->
        <!- Certain tests may need their own builder -->
        <Test1 param1 = 2 param2 = "Hello".. />
        <Test2 />
        <ComplexTest ... >
            <Test1>
            <Test5>
        </ComplexTest>
    </TestBenchX>

    <TestBenchY>
    </TestBenchY>
</BenchTests>
</code>```

The classes

From the above looks like we have:

```<code>public class testBenchCollection {
    List<TestBench> TestBenches;

    public void AddBench ( TestBench newBench ) {}

    public void Execute(){
        foreach( TestBench bench in testBenches )
            bench.Execute();
    }
}

public abstract class TestBench {
    List<Test> testCollection;

    public virtual Execute(){
        foreeach( Test aTest in testCollection )
            aTest.Execute();
    }

    public void AddTest( Test newTest )
}

public abstract class Test {
    public virtual Execute(params object[] myParms ){}
}

public enum TestBench{ X, Y, Z }
public enum GlobalTests { eenie, meenie, minee, moe }
public enum XTests { test1, testToo }
public enum YTests { Larry, Moe, CurleyJoe, test1 }
</code>```

Body:
Has anyone had to deal with a case like this before?

Your bench/test configuration is more complex than I've dealt with, but it is the same problem, just more layers of construction.

Warning: Do not get caught up in inventing framework to genericise and abstract any structure, any test, any time.

Identify, classify, and organize every test

Whether a test is a single method or a series of methods, or a class composite, they're all tests and each test should be explictly identifiable.

Each test should be designed to run by itself. It may run as part of a series of consecutive tests but each identifiable test must be fundamentally independent.

Coding too soon

Thinking in terms of "methods" is too narrow, too sub-atomic as it were. That is why you're seeing "the coupling between these is higher than I'd like." Get the logical organization and the code framework will emerge from that.

Test Structure Observations

TestBenches - create a config section.

TestBench is probably the top of the structure.  This can also act as a namespace, tests in different testbenches can have the same name.

Structure will be directly reflected in the config file elements.

Test order in the config file is execution order.

Factory Observations

You will have an abstract factory. You may have the builder pattern depending on the dynamics of constructing any given test.

The abstract factory structure will map directly to the config file structure. It knows the structure. It will necessarily be tightly coupled to the config file.

Config element names will be converted to enums. The various enums will reflect the config structure. For example TestBenchXFactory will use a Xtests enum. This effectively validates the XML elements before we attempt to use it.

OO observations

Lots of passing the buck but it is all dead simple code until we get to construction of concrete, dynamic test objects.

The number of factories may seem excessive or totally unnecessary. However, We're minimizing coupling of layer construction

Adding, removing tests may seem like Open/Closed principle violation, but "frankly my dear, I don't give a damn."

Good adherence to single responsibility principle in the factory classes makes change easy. Again, Each logical test is independent

<BenchTests>
    <!- BenchTestFactory gets <BenchTests> as a parameter -->
    <!- builds a BenchTestCollection. Instantiate sBenchTestXFactory, etc. -->
    <!- Adds concrete `BenchTest`s to the collection. -->
    <TestBenchX>
        <!- `BenchTestXFactory` gets `<TestBenchX>` element as a parameter -->
        <!- instantiates `BenchTestX` object. Builds each test, adds to `BenchTestX`. -->
        <!- Certain tests may need their own builder -->
        <Test1 param1 = 2 param2 = "Hello".. />
        <Test2 />
        <ComplexTest ... >
            <Test1>
            <Test5>
        </ComplexTest>
    </TestBenchX>

    <TestBenchY>
    </TestBenchY>
</BenchTests>

The classes

From the above looks like we have:

public class testBenchCollection {
    List<TestBench> TestBenches;

    public void AddBench ( TestBench newBench ) {}

    public void Execute(){
        foreach( TestBench bench in testBenches )
            bench.Execute();
    }
}

public abstract class TestBench {
    List<Test> testCollection;

    public virtual Execute(){
        foreeach( Test aTest in testCollection )
            aTest.Execute();
    }

    public void AddTest( Test newTest )
}

public abstract class Test {
    public virtual Execute(params object[] myParms ){}
}

public enum TestBench{ X, Y, Z }
public enum GlobalTests { eenie, meenie, minee, moe }
public enum XTests { test1, testToo }
public enum YTests { Larry, Moe, CurleyJoe, test1 }


问:
Best way to deal with Hibernate 1->Many relationship over REST/JSON service
Problem: A Hibernate bi-directional One-to-Many relationship does not map easily to JSON. If default (Jackson) mapping is used there is an infinite recursion issue as the parent contains the children each of which contains a reference to the parent. The easiest way I've found to fix this is to mark the Many end attribute as @JsonIgnore. This means that the JSON gets generated as expected. However, when the objects are sent over a REST POST (for example) this means the ManyToOne references get lost. At present I just have the REST service reconstruct the references before persisting the data, but I'm wondering if there is a recommended way to do this automatically (using the Spring REST architecture).

To illustrate, here are some code snippets:

The parent Entity:

```<code>@Entity
@Table(name = "wine_case")
public class WineCase {
    @Id @GeneratedValue(strategy = GenerationType.AUTO)
    private Integer id;

    @OneToMany(fetch = FetchType.EAGER, cascade = CascadeType.ALL, mappedBy = "wineCase")
    private List<CaseContent> caseContents;
}
</code>```

The child Entity:

```<code>@Entity
@Table(name = "case_content")
public class CaseContent {
    @Id @GeneratedValue(strategy = GenerationType.AUTO)
    private Integer id;

    @ManyToOne(fetch = FetchType.EAGER)
    @JoinColumn(name = "wine_case_id", nullable = false)
    @JsonIgnore
    private WineCase wineCase;
}
</code>```

The method in the REST controller which receives the request, and needs to rebuild the relationships back from CaseContent to WineCase:

```<code>@RequestMapping(method = RequestMethod.POST)
@ResponseStatus(HttpStatus.CREATED)
public @ResponseBody
WineCase createWineCase(@RequestBody WineCase wineCase, HttpServletResponse response) {
    wineCase.setId(null);
    wineCase.getCaseContents().forEach((cc) -> cc.setWineCase(wineCase));
    entityManager.persist(wineCase);
    response.setHeader("Location", "/winecases/" + wineCase.getId());
    return wineCase;
}
</code>```

答: Have a look at your JSON library's options - there should be a way to make it identify objects that it has already serialised and emit a back-reference instead of serializing the object again. This is almost certainly the simplest solution to your problem.</p>


问:
Is static universally "evil" for unit testing and if so why does Resharper recommend it?
I have found that there are only 3 ways to unit test (mock/stub) dependencies that are static in C#.NET:

Moles

TypeMock

JustMock

Given that two of these are not free and one has not hit release 1.0, mocking static stuff is not too easy.

Does that make static methods and such "evil" (in the unit testing sense)?  And if so, why does resharper want me to make anything that can be static, static? (Assuming resharper is not also "evil".)

Clarification:
I am talking about the scenario when you want to unit test a method and that method calls a static method in a different unit/class.  By most definitions of unit testing, if you just let the method under test call the static method in the other unit/class then you are not unit testing, you are integration testing.  (Useful, but not a unit test.)

答:
If the static method is called from inside other method, it is not possible to prevent or substitute such a call. This means, these two methods make a single Unit; Unit test of any kind tests them both.

And if this static method talks to Internet, connects databases, shows GUI popups or otherwise converts the Unit test into complete mess, it just does without any easy work around. A method that calls such the static method is not testable without refactoring, even if it has lots of purely computational code that would highly benefit from being unit tested.


问:
Gödel's Incompleteness Theorem and Algorithms
According to Gödel's incompleteness theorem, not every problem can be solved using algorithms. How do we know if a problem can be solved using algorithm?

How do we know that NP problems are algorithmically solvable?

答:
Equivalence of Gödel's incompleteness theorem and the halting problem

Proving undecidability of the halting problem and deducing Gödel's first incompleteness theorem from it is actually in many ways the best approach when giving a class in which one introduces (or can assume) both first-order logic and computability. I think it's both faster this way and easier to understand. Therefore it seems rather pointless to prove the halting problem via Gödel's incompleteness theorem, but it can be done.

Proof sketch:

Suppose the halting problem is decidable. We will construct a counter-example to Gödel's theorem, i.e. a complete recursive extension of Peano Arithmetic.

Peano Arithmetic is of course incomplete, but it is recursive (i.e. the set of its axioms is recursive=computable), and so the set of all consequences of Peano Arithmetic is recursively=computably enumerable and therefore (given that the halting problem is decidable) computable.

Using some natural enumeration of all sentences of the language of Peano Arithmetic, we can take the smallest sentence φ such that neither φ nor its negation ¬φ is a consequence of the axioms. We then add φ to the axioms. (Or ¬φ. It doesn't matter because the result will be consistent either way.) With one more axiom we have more consequences. If the theory is still not complete, we can take the sentence that is now the smallest one such that neither itself nor its negation follows from the (new) axioms, and add this sentence to the axioms. And so on.

The process will either stop when we have found a completion by adding finitely many sentences, or we will have to add infinitely many sentences. But even then it's easy to see that the resulting theory is complete.

But is it still recursive? Yes, provided that we could find each minimal φ that was independent of the previous axioms by using an algorithm (and always the same one). Checking this is where the real difficulty of the proof lies, but it should be rather straightforward.

Though not as straightforward as proving the undecidability of the halting problem directly. ☐

Impact of the halting problem on real-life computing

Yes, this is a real problem. Deciding whether an arbitrary given computer program will halt is a key problem for which we would love to have an algorithm. It's unfortunate that none can exist.

If the halting problem were decidable (and there were no feasibility issues), then this would no doubt change the practical aspects of computing significantly. Even today there exist compilers that reject programs which won't halt on every possible input. The problem is that these compilers cannot work perfectly and have to approximate. One option is for them to try proving that for some input the program doesn't halt, and to accept every program for which they can't find a problem. In practice this can work quite well, catching most programmer errors that lead to infinite loops; but there is no absolute guarantee. The other option is for them to try proving that the program halts for every input, and reject a program if they can't prove it. The problem with this is that such compilers will always reject some programs that do actually halt on every input. And this is not just an issue of rewriting the program differently: It can be proved that no matter how good the heuristics of such a compiler, there will always be computable problems for which it doesn't accept any algorithm at all.

A corollary of the undecidability of the halting problem is the fact that you cannot decide whether a complicated system for synchronisation between threads or processes is OK, or whether deadlocks can occur. Each time you are faced with a frozen application window, you can blame undecidability of the halting problem.

How do we know if a problem has an algorithm?

We know there is an algorithm, when we have found an algorithm. Basically it's as easy as this. And we know that there is no algorithm if we can prove that such an algorithm would lead to a mathematical contradiction. The typical way that one proves there is no algorithm for a problem is by showing that such an algorithm could be used to decide the halting problem.

Theoretically this leaves a class of problems for which we can neither provide an algorithm (yet?) nor prove non-existence of an algorithm (yet?). I think in practice this has never happened so far. I think such problems are known to exist, but it seems likely that they are all so weird that humans simply have no use for any of them. Yet. This may change at some point in the future as we learn to ask our computers more sophisticated questions.

How do we know that NP problems have algorithms?

This is easy. We know this because it's part of the definition. By "NP problem" you may have meant "NP-complete problem", but even this doesn't make a difference because it means belonging to the hardest class of NP problems. So let's look at how NP is defined.

A problem is in P if there exists an algorithm for it which gives the correct solution for every input in time that is bounded from above by a polynomial of the input length. This class of problems is interesting because it's easy to handle in the theory and we found that in practice the coefficients and exponents of the polynomials usually don't get too big. (There are exceptions. E.g., there is an algorithm for tree-decompositions of graphs that runs in linear time but is completely useless in practice because the coefficient is enormous.)

A problem is in NP if there is a non-deterministic algorithm (i.e. sometimes branching or not based on coin throws) which for every single input has a chance to find the correct solution in time bounded by a polynomial in the input, but if it isn't lucky may run forever. It is easy to see how to turn this into an algorithm that tries out all possibilities until it stops with the correct solution after time at most exponential in the input length. (Hint: breadth-first search among the possible coin throw sequences.) So every NP problem has an exponential algorithm, and thus in particular an algorithm.

Almost all problems of practical importance are not just decidable, they are in fact in NP. If the question whether P=NP should ever get a positive solution, this would either provide us with faster algorithms for a lot of problems, or with a lot of additional examples showing that the polynomials needed for a problem in P can be so unwieldy as to be useless in practice.

Note on spelling

Please, please, please don't just drop the two dots off German umlauts. Accents in French, Spanish, Italian and many other languages were added at some point to make certain words distinguishable or give pronunciation hints. But the two dots in German are originally abbreviations for an e following the base letter. You don't have to use umlauts in English, but if you don't you must use the e like this: Goedel. Otherwise it's not just poor typography, it's a spelling mistake. (Yes, even in English. Only poorly edited English-speaking media such as parts of the sports press get this wrong.)


问:
Customer Authentication in a website
Just to be clear, by authentication I don't mean user-authentication, but I want to make sure that my app is running on the customer's server and in a defined time-span.

Some of our customers use our web apps in their Intranet and on their own servers, on the other hand some of them use Hosting services and they don't own any server machine.

With that said, I'm looking for ways to make sure about customer's Identity. I don't want them to be able to xcopy the app, also I'd like to have some kind of time-expiration limit.

In traditional desktop apps we could use USB security tokens, but their not usable with hosting providers.

It seems that we have to make a central authentication server. I'm a little confused about possible options, so any suggestion about where to start is welcome.

答:
This is a very complex thing. What you need is a licensing mechanism where you create for example a key based on unique system information like servername, mac address, company name, cpu id, etc. You can also have a compbination of those information. After that you need to create a "key generator" and in your software read this information, verify on each startup if they are identical and run the software. Additionally you can add a time information for the expiration date, or days which the user can use your app.

But (and this is my personal opinion) you dont need to develop a super complex licensing mechanism. Nearly everthing is breakable. The question is: is your software worth to put so much effort in cracking your licensing mechanism? Is you app designed for small, mid size or large companies? How expensive is your app?

Here is an SO article on that. Search for 'licensing', 'software licensing [development language]' , 'key generator' ...

Title: Customer Authentication in a website


问:
Link to ISO doc? Complexity of unordered_map operations in C++::stl
In different forums, I have found the statement that in C++::stl, insert and find for unordered_map have guaranteed amortized time complexity O(1). This puzzles me, and I would like to see the official document (perhaps ISO) to see exactly what is being demanded. Could someone provide me with the link?

Here is why I think that guaranteed time complexity amortized O(1) may not be possible. Please correct me if I say something wrong, as I am not an experienced programmer. The best way to implement an unordered map is through the use of a hash table. It seems reasonable towant to use keys that are strings of length at most 1000. Let's assume that the alphabet has size 26. Then we are possibly dealing with more than 26^1000 different strings. Any hash function would need to give an array index ranging over 2^64 possible indices. However, any hash function from a set of size 26^1000 to a set of size 2^64 must result in at least one array index having more than exp(600) strings that  all hash to that same array index. So, unless there is some special information about the special nature of the strings to be hashed, one cannot choose a hash function that is guaranteed to work for a chained hash table. For an open hash table, with probes, my argument is not complete, but it seems to be enough to make one worry about guarantees.

Given a specific hashing scheme (not necessarily one found in a textbook), is it possible to choose a sequence of strings (all of length 1000) such that the time to insert increases linearly with the number of strings?

答:
Stack Overflow explains the background in a way that might help you understand why the standard just says "it is so". The proposal discusses it in slightly mroe detail (search for 'compexity').

Control of Hash Resizing

The time required for looking up an element by key k is c1 + c2 n,
  where c1 and c2 are constants, and where n is the number of elements
  in the bucket indexed by k's hash code. If the hash function is well
  chosen, and elements are evenly distributed between buckets, this is
  approximately c1 + c2 N/B, where N is the number of elements in the
  container and B is the bucket count. If the bucket count is taken as a
  constant, then the asymptotic complexity for element lookup is O(N).

To maintain average case complexity O(1) for lookup, the bucket count
  must grow as elements are added to the hash table; on average the
  bucket count must be proportional to N. Another way of putting this is
  that the load factor, N/B, must be approximately constant.
  ...

Your second question is easy, any hashing scheme that returns the same constant every time will require a bucket insert every time, and with a linear-time insert (via choice of bucket scheme) you get linear time.


答:
Cplusplus.com* states the following about std::undered_map::operator[] § Complexity:

Average case: constant.

Worst case: linear in container size.

May trigger a rehash if an element is inserted (not included in the complexity above).

It states that on average the complexity is O(1); but in worst case as with your identifiers constructed to generate colliding hashes the performance might be linear as you reasoned yourself.

In addition when reserving more space than bucket_count*max_load_factor a rehash is triggered.  insert and map["key"] = value may also trigger a rehash.  The rehash'es complexity is:

In case of rehash,

Average case: linear in container size.

Worst case: quadratic in container size.

TLDR

The OP is correct about the complexity. The standard states this, the OP has overlooked it.  Yes it is possible to construct a sequence of keys that would generate terrible performance; security.SE may have something useful to say about that.

This is the link to International C++ standard - n3242.pdf (i.e. ISO/IEC 14882:2011)

*) I'm not sure if Cplusplus.com is the canonical reference for ISO/IEC 14882:2011 but they appear to follow it quite closesly

Title: Link to ISO doc? Complexity of unordered_map operations in C++::stl

Body:
In different forums, I have found the statement that in C++::stl, insert and find for unordered_map have guaranteed amortized time complexity O(1). This puzzles me, and I would like to see the official document (perhaps ISO) to see exactly what is being demanded. Could someone provide me with the link?

Here is why I think that guaranteed time complexity amortized O(1) may not be possible. Please correct me if I say something wrong, as I am not an experienced programmer. The best way to implement an unordered map is through the use of a hash table. It seems reasonable towant to use keys that are strings of length at most 1000. Let's assume that the alphabet has size 26. Then we are possibly dealing with more than 26^1000 different strings. Any hash function would need to give an array index ranging over 2^64 possible indices. However, any hash function from a set of size 26^1000 to a set of size 2^64 must result in at least one array index having more than exp(600) strings that  all hash to that same array index. So, unless there is some special information about the special nature of the strings to be hashed, one cannot choose a hash function that is guaranteed to work for a chained hash table. For an open hash table, with probes, my argument is not complete, but it seems to be enough to make one worry about guarantees.

Given a specific hashing scheme (not necessarily one found in a textbook), is it possible to choose a sequence of strings (all of length 1000) such that the time to insert increases linearly with the number of strings?


答:
Hash tables are fairly complicated data structures, and depending on how you implement them performance will vary. Also, some implementations can easily be tricked to enter a worst case. No matter how you implement a hash table, the worst case for insertion and retrieval will be O(n). However, hash tables still have very attractive complexity for the average case, especially when using chaining for collision resolution which I will analyze in the rest of this answer.

First, a bit of terminology. A hash table consists of k buckets (storage locations) and contains n key-value pairs. We can now calculate the load factor f = n/k. This load factor also approximately (for small f) corresponds to the probability that when we insert an element, the addressed bucket is already in use.[1] The load factor f is also the expected number of elements in a bucket! Therefore, retrieval for a hash table is not O(1) but really O(f) on average – the worst case O(n) still holds.

[1]: To be precise, the probability of at least one collision upon insertion of an element is pc = 1 - (1 - 1/k)n due to the birthday paradox.

To be really pedantic, the average case is O(f) = O(n/k) = O(n) for a fixed k. This is bad, since it defeats the whole point of using a hash table. Therefore, implementations use dynamic resizing to limit the load factor to some constant value, typically fmax = 0.7 ± 0.1. Whenever our load factor reaches that limit, we reallocate the hash table to double that size k, which also halves the load factor! Each reallocation is O(n), but it only happens every 1/n insertions. So while each individual insertion can take up to O(n), the cost spread out over all insertion is O(1) – the amortized complexity. It is therefore correct to say that a hash table with chaining and dynamic resizing has O(1) amortized complexity in the average case for insertion and retrieval.

There are still some assumptions here: the hash function must be uniform (that is, must use its entire codomain with roughly equal probability), and must have negligible cost. For variable-sized key types, this might not be given, so that it would be more correct to state that insertion and retrieval is O(h(key)). However, this complexity is independent from the data structure but rather a property of the data, so that we should (mostly) ignore it when analyzing the data structure.

Your argument is based on the pigeonhole principle and is correct, but not meaningful.

So, unless there is some special information about the special nature of the strings to be hashed, one cannot choose a hash function that is guaranteed to work for a chained hash table.

Any hash function that fulfils certain properties will work. In fact, since the hash function is used to derive a bucket index, it does not have a codomain of size 264 but actually only of size k. However, hash collisions are expected and can be resolved in a manner that maintains the O(1) complexity. To resolve a hash collision, the un-hashed key is stored along with the value in the bucket. Upon retrieval, the retrieval key is compared with the stored key for equality. If a bucket contains more than one entry, we compare against all stored keys. This is effectively a linear search, but as shown above it is O(1) on average when using dynamic resizing, and it correctly handles hash collisions.

Given a specific hashing scheme […], is it possible to choose a sequence of strings […] such that the time to insert increases linearly with the number of strings?

Yes, if we trigger the worst case such that all strings have the same hash. E.g. when using strlen() as a hash function (which is not advisable since its not an uniform hash on most data), then using lots of strings of the same length as keys in the table will all map to the same bucket, regardless of the size of the hash table. Since this could be used in denial-of-service attacks, some hash table implementations use randomized hash functions where the worst case cannot be predicted by an attacker. This is not possible in C++, but the std::unordered_map allows you to provide a custom hash function as a template parameter if you are aware of certain properties of your keys.

But again, this is only the worst case. As mentioned above the discussion of average complexity assumes that the hash function is in fact uniform.


问:
Coded UI test Automation Technique
How is coded UI testing technique more favorable than any other testing technique? What is the main advantage of using a coded UI test?</p>

答:
There's no one reason why teams use GUI tests as part of their integration or system testing programme, and no test type is best in all situations. A quick list of advantages based on an article by Alvin Alexander:

Finding regression errors.

Letting human GUI testers ("domain experts") get back to their normal jobs instead of running tests a robot should be running.

Covering for application areas that don't have unit tests.

Detecting differences in behaviour between platforms

Where I've used GUI testing most extensively was when we had to support a complex GUI across a large matrix of systems. We had a Windows desktop app that had to run on XP, Vista, 7 and a couple of MS server OS's, with a few extras due to service packs. Since we interacted with Microsoft office those variations were multiplied by the Office versions we supported. So every release had to have a test script several hours long run on each of 20-odd combinations. That's just not feasible to do without an array of virtual machines and a GUI testing tool.

We recorded a number of sessions of real users, and had business analysts generate their own tests, plus the test team added their own. Even with regular pruning of the test scripts it took hours to run the full set.

Note that there are two broad categories of tools. "Universal" tools record mouse clicks/keystrokes and compare screenshots. "Inspection" tools  interrogate the program under test to both find controls and read results. Many tools can do both, and some have libraries that you can build into your program to facilitate testing. Screenshot comparisons are always available but very fragile (in XP enabling keyboard language switching makes the taskbar one pixel higher, as an example of something that broke a whole series of our tests). But smart tools can trip up if controls are moved, renamed or the control type changes.

Title: Coded UI test Automation Technique


答: Consider the test pyramid In the top is UI. In the context of wpf with mvvm this means you unit test your model as much as possible. Then you unit test your view model as much as possible. This leaves a little bit of the UI untested and this is where coded ui test comes in. So a little bit of coded ui test would probably be a goood thing. If you use it too much you will test too much and the tests will be slow. Basicly just test that perperties are mapper properly to the view model.</p>

Title: Coded UI test Automation Technique

Body: How is coded UI testing technique more favorable than any other testing technique? What is the main advantage of using a coded UI test?</p>


问:
Inheritance or type field when designing class
I have to model a store with all kinds of articles. The user has to be able to filter these articles by type, price, ... . The store would contain a list of Article objects.

I've been stuck on whether to implement the Article class with a type field or to subclass new articles from the Article class.

Biggest problem I see when implementing with inheritance is the filtering by type. I'm going to have to lookup which type my derived objects in the Article list are, which would either require that every derived class has a getType() function or I'd have to use reflection to get the class name and work with that, both of which kinda defeats the purpose of inheritance. To access the specific fields of each derived class, i'd first have to filter by type and then downcast all Article objects of the correct type to that type to be able to access their specific fields. I have no idea if this is considered a good design.

On the other hand, I had the idea to have the Article class have a type field and a Map to represent it's data. I would then have to ensure that the necessary (key, value) pairs are added to the map for each different type and maintain an ENUM for the fields of each different type. Article would become an incredibly flexible class this way so I'd have to make sure my factory method's for each type would ensure the right pairs are added to the info map depending on the type. It would also require more discipline from the coder using the Article class to only access the map keys that are defined for that particular type.

I could also just keep different derived objects in different lists in the shop, but then I'd have to add a list every time I'd add a new article which isn't good for maintainability.

Any extra arguments for any of the possibilities that could help me decide would be appreciated.

答:
Using a type filed is a code smell.

Using a map for the articles properties may give you too much flexibility.  We should always strive for flexible designs; so too much flexibility, is that possible?  Yes it is, as you point out now you will have to check at other places that the articles satisfy the requirements of their "article type" which might lead to scattering this functionality all over the system and also scatter the differences in behaviour of different article types all over the system.

oop intends to concentrate the type specific behaviour of classes in the class, when you choose to use type fields and maps of properties you will need to ensure that the constrains on the different types are enforced in some other well designed mechanism.  Sometimes you might need that flexiblity.

Using the type field for filtering articles is not bad, you could even allow extend it by allowing articles to have multiple types so that users might have improved search functionality.


问:
Database multiple database query each time
I'm writing a rest service. For each request I use about 4-8 queries.

Should I try to refactor those into a single query?

答:
It very much depends on the data.

However what you really really want to avoid is getting a number of rows from one query and then for each row firing of a second query for each row returned. In this situation a single join query will perform an order of magnitude faster than several individual queries.


问:
What are the advantages of matrix multiplication over individual variables (graphics)?
I am learning OpenGL and the tutorials (1, 2) I'm reading teach me that to scale/rotate/translate an object you have to know matrix multiplication. Why? Instead of 3x3 matrix you can use 6 floats: scale_x, scale_y, sin_a, cos_a, mov_x and mov_y. They would result in...

Less GPU and CPU usage (matrix multiplication takes 9 multiplications and 6 additions while individual variables need 6 multiplications and 4 additions. Also, if you want to move object, instead of having to multiply whole matrix you get to only change values of two floats.

Less memory bandwidth (1/3 cut!)

Easier to manipulate (at least in C, no need for matrix manipulation functions)

Easier information extraction to get object rotation or offset or scale

The only disadvantages that I know of are:

You cannot change the order of transformations, most importantly, rotation around some point, not the origin of the coordinate plain. You can simulate it, though, by altering mov_x and mov_y accordingly.

More code. You could put them into an array though, but that would mean you would lose the ability to update them one by one and only could update them all or the beginning of array, not the middle or the end. I could be wrong on this, though.

Could someone tell me what am I missing?

Edit: added my shader below.

```<code>#version 330

layout (location = 0) in vec2 pos;
layout (location = 1) in vec3 clr_in;

uniform float osclx, oscly, osina, ocosa, omovx, omovy;
uniform float msclx, mscly, msina, mcosa, mmovx, mmovy;
float oldx, oldy, x, y;

out vec3 clr_out;

void main() {
    x = pos.x;
    y = pos.y;

    x = x * oscly;
    y = y * osclx;
    oldx = x;
    oldy = y;
    x = oldx * ocosa - oldy * osina;
    y = oldx * osina + oldy * ocosa;
    x = x + omovx;
    y = y + omovy;

    x = x * msclx;
    y = y * mscly;
    oldx = x;
    oldy = y;
    x = oldx * mcosa - oldy * msina;
    y = oldx * msina + oldy * mcosa;
    x = x + mmovx;
    y = y + mmovy;

    gl_Position = vec4(x, y, 0.0f, 1.0f);
    clr_out = clr_in; }
</code>```

答:
There're several good reasons for representing transforms as matrices:

Vectors are used a lot in 3D graphics;

Matrices are efficient data structures to store multiple vectors;

The modern graphics pipeline is shader-based and requires the client application to send data quickly (e.g. buffers);

The client can use a single function call to send the transform matrix to a single uniform in the vertex shader, while your proposed approach would require multiple independent vertex uniforms and the client to issue multiple function calls before reaching something like glDrawArrays or equivalent --which keeps the GPU idle for longer and makes it less efficient

The math is simpler to perform and less error prone than your proposed approach (compare your complicated shader there vs something simpler like gl_Position = projection_matrix * view_matrix * model_matrix * position_vector;)

With matrices, you can accumulate transforms into a single matrix and reduce the number of math operations significantly in many cases (e.g. gl_Position = pvm_matrix * position_vector;)

Ultimately, I think it's fallacious to think that you're being more efficient. The math operations to translate/rotate/scale will be the same regardless of how you look at it, and your code looks significantly more complex than it needs to be. Why should you (or worse, those maintaining your code) have to keep track of 16 uniforms for a 4x4 matrix (and make OpenGL calls to send data for each one) when you could only keep track of 1 uniform and have a single OpenGL call per matrix? I wouldn't want to work on that kind of code.

Also, a lot of the efficiency in 3D graphics comes from the GPU's parallelism and its ability to consume data quickly. The hardware is already optimized to handle certain common cases, and using matrices as a data structure to store transformations is so common that they have their own data types built into GLSL (e.g. mat4). It's like asking "Why are 3D models always built using triangles when I could use _____ geometric shape instead?". Because there're many advantages to using triangles[1] and the hardware is already optimized for them.

[1] For example, triangles being co-planar allow some graphics algorithms to be simpler and not worry about corner cases (e.g. clipping, etc)

ContentLicense: CC BY-SA 4.0


问:
How does branch coverage handle loops?
I know how code coverage works in general, and I know what branch coverage is. But I can not seem to find an explanation for how branch coverage handles loops.

Does it work like path coverage? Where a loop which runs 10 times is a different path from the exact same loop running 11 times. Or would those two cases be the same thing in branch coverage?

答:
Branch coverage and path coverage are distinct concepts.

Branch coverage

To measure branch coverage, we look for all the points where branching can take place. At each branching point, both branches should have been executed at least once. E.g. in this pseudo-code:

```<code>A
if B:
  C
else:
  D
E
if F:
  G
I
</code>```

we have two branch points – the if B and if F conditionals. To get full branch coverage, each of these conditionals should execute the true and false branch, i.e. both B and F would have to each be false and true each. A test plan could be:

```<code>Run 1:
  B = false
  F = false
  # executes A B _ D E F _ I
Run 2:
  B = true
  F = true
  # executes A B C _ E F G I
</code>```

As you can see, full branch coverage implies full statement coverage.

When dealing with loops, it might be helpful to “compile” it to a more low-level representation that only has conditionals and gotos. E.g.:

// C99 code
A;
for (int i = 0; i < length; ++i)
  B;
C;
```

<p>could be understood as</p>

<pre class="lang-c prettyprint-override"><code>// Block 1
  A;
  int i = 0;

// Block 2
loop_start:
  if (!(i < length))
    goto loop_end;  // -> Block 4

// Block 3
  B;
  ++i;
  goto loop_start;

// Block 4
loop_end:
  C;
</code>```

There is only one conditional here, in block 2. So to get full branch coverage, it must once evaluate both false and true. A test plan could be:

```<code>Run 1:
  length = 1
  # executes B1 B2 B3 B2 B4
</code>```

So the loop condition will evaluate to both true and false with this test plan. But clearly, this is not a satisfactory test: what happens when the loop is skipped altogether (e.g. with length = 0)? What happens if the loop body modifies some state, will it still work with hundreds of iterations?

Path coverage

When we group the code into a control flow graph, path coverage measures the fraction of paths taken from all possible paths. Path coverage implies branch coverage. When we look back at the first example, we could get branch coverage with only two test cases. But to get path coverage we will need 4 cases: two for each path through the first conditional, multiplied by two cases for the second conditional:

```<code>Run 1:
  B = false
  F = false
  # executes A B _ D E F _ I
Run 2:
  B = false
  F = true
  # executes A B _ D E F G I
Run 3:
  B = true
  F = false
  # executes A B C _ E F _ I
Run 4:
  B = true
  F = true
  # executes A B C _ E F G I
</code>```

When our control flow graph includes loops, there are in general infinitely many possible paths. In some cases, the number of loop iterations is bounded by a constant and can be tested, but in general this is not the case. Since complete path coverage is useful but not reachable, we tend to use other coverage metrics.

When I write tests, I tend to ignore full path coverage for loops (path coverage for simple conditionals is still very useful). However, multiple paths could be grouped into equivalence classes for testing – running the code with 0, 1, 2, and “many” iterations should be a decent approximation. A possible test plan:

```<code>Run 1:
  length = 0
  # executes B1 B2 B5
Run 2:
  length = 1
  # executes B1 B2 B3 B2 B5
Run 3:
  length = 2
  # executes B1 B2 B3 B2 B3 B2 B5
Run 4:
  length = 123
  # executes B1 B2 B3 B2 B3 ... B2 B3 B2 B5
</code>```

There are also formal code metrics that allow us to quantify loop tests, such as Linear code sequence and jump-coverage. However, I have never used it.

Testing loops via recursion

When loops are expressed as recursion, the loop is not explicit and thus “hidden” from path coverage. Is this a problem? Kind of. The loop is still present in the control flow graph of the program as whole, but not in the CFG of the recursive function.

However, it is far easier to show that the loop is correct when expressed recursively. We can test the base cases, and a non-base case. Since each non-base-case result is constructed from the base cases (which we have already shown to be correct), then the function as whole can be presumed to be correct. This is analogue to the proof by induction technique, except that tests aren't proofs of correctness, but merely examples of correctness.

Title: How does branch coverage handle loops?

Body:
Branch coverage and path coverage are distinct concepts.

Branch coverage

To measure branch coverage, we look for all the points where branching can take place. At each branching point, both branches should have been executed at least once. E.g. in this pseudo-code:

A
if B:
  C
else:
  D
E
if F:
  G
I

we have two branch points – the if B and if F conditionals. To get full branch coverage, each of these conditionals should execute the true and false branch, i.e. both B and F would have to each be false and true each. A test plan could be:

Run 1:
  B = false
  F = false
  # executes A B _ D E F _ I
Run 2:
  B = true
  F = true
  # executes A B C _ E F G I

As you can see, full branch coverage implies full statement coverage.

When dealing with loops, it might be helpful to “compile” it to a more low-level representation that only has conditionals and gotos. E.g.:

// C99 code
A;
for (int i = 0; i < length; ++i)
  B;
C;

could be understood as

// Block 1
  A;
  int i = 0;

// Block 2
loop_start:
  if (!(i < length))
    goto loop_end;  // -> Block 4

// Block 3
  B;
  ++i;
  goto loop_start;

// Block 4
loop_end:
  C;

There is only one conditional here, in block 2. So to get full branch coverage, it must once evaluate both false and true. A test plan could be:

Run 1:
  length = 1
  # executes B1 B2 B3 B2 B4

So the loop condition will evaluate to both true and false with this test plan. But clearly, this is not a satisfactory test: what happens when the loop is skipped altogether (e.g. with length = 0)? What happens if the loop body modifies some state, will it still work with hundreds of iterations?

Path coverage

When we group the code into a control flow graph, path coverage measures the fraction of paths taken from all possible paths. Path coverage implies branch coverage. When we look back at the first example, we could get branch coverage with only two test cases. But to get path coverage we will need 4 cases: two for each path through the first conditional, multiplied by two cases for the second conditional:

Run 1:
  B = false
  F = false
  # executes A B _ D E F _ I
Run 2:
  B = false
  F = true
  # executes A B _ D E F G I
Run 3:
  B = true
  F = false
  # executes A B C _ E F _ I
Run 4:
  B = true
  F = true
  # executes A B C _ E F G I

When our control flow graph includes loops, there are in general infinitely many possible paths. In some cases, the number of loop iterations is bounded by a constant and can be tested, but in general this is not the case. Since complete path coverage is useful but not reachable, we tend to use other coverage metrics.

When I write tests, I tend to ignore full path coverage for loops (path coverage for simple conditionals is still very useful). However, multiple paths could be grouped into equivalence classes for testing – running the code with 0, 1, 2, and “many” iterations should be a decent approximation. A possible test plan:

Run 1:
  length = 0
  # executes B1 B2 B5
Run 2:
  length = 1
  # executes B1 B2 B3 B2 B5
Run 3:
  length = 2
  # executes B1 B2 B3 B2 B3 B2 B5
Run 4:
  length = 123
  # executes B1 B2 B3 B2 B3 ... B2 B3 B2 B5

There are also formal code metrics that allow us to quantify loop tests, such as Linear code sequence and jump-coverage. However, I have never used it.

Testing loops via recursion

When loops are expressed as recursion, the loop is not explicit and thus “hidden” from path coverage. Is this a problem? Kind of. The loop is still present in the control flow graph of the program as whole, but not in the CFG of the recursive function.

However, it is far easier to show that the loop is correct when expressed recursively. We can test the base cases, and a non-base case. Since each non-base-case result is constructed from the base cases (which we have already shown to be correct), then the function as whole can be presumed to be correct. This is analogue to the proof by induction technique, except that tests aren't proofs of correctness, but merely examples of correctness.


问:
How do you encode Algebraic Data Types in a C#- or Java-like language?
There are some problems which are easily solved by Algebraic Data Types, for example a List type can be very succinctly expressed as:

```<code>data ConsList a = Empty | ConsCell a (ConsList a)

consmap f Empty          = Empty
consmap f (ConsCell a b) = ConsCell (f a) (consmap f b)

l = ConsCell 1 (ConsCell 2 (ConsCell 3 Empty))
consmap (+1) l
</code>```

This particular example is in Haskell, but it would be similar in other languages with native support for Algebraic Data Types.

It turns out that there is an obvious mapping to OO-style subtyping: the datatype becomes an abstract base class and every data constructor becomes a concrete subclass. Here's an example in Scala:

```<code>sealed abstract class ConsList[+T] {
  def map[U](f: T => U): ConsList[U]
}

object Empty extends ConsList[Nothing] {
  override def map[U](f: Nothing => U) = this
}

final class ConsCell[T](first: T, rest: ConsList[T]) extends ConsList[T] {
  override def map[U](f: T => U) = new ConsCell(f(first), rest.map(f))
}

val l = new ConsCell(1, new ConsCell(2, new ConsCell(3, Empty)))
l.map(1+)
</code>```

The only thing needed beyond naive subclassing is a way to seal classes, i.e. a way to make it impossible to add subclasses to a hierarchy.

How would you approach this problem in a language like C# or Java? The two stumbling blocks I found when trying to use Algebraic Data Types in C# were:

I couldn't figure out what the bottom type is called in C# (i.e. I couldn't figure out what to put into class Empty : ConsList< ??? >)

I couldn't figure out a way to seal ConsList so that no subclasses can be added to the hierarchy

What would be the most idiomatic way to implement Algebraic Data Types in C# and/or Java? Or, if it isn't possible, what would be the idiomatic replacement?

答:
The data type ConsList can be represented as an interface. The interface exposes a single deconstruct method which allows you to "deconstruct" a value of that type - that is, to handle each of the possible constructors. Calls to a deconstruct method are analogous to a case of form in Haskell or ML.

```<code>interface ConsList<A> {
  <R> R deconstruct(
    Function<Unit, R> emptyCase,
    Function<Pair<A,ConsList<A>>, R> consCase
  );
}
</code>```

The deconstruct method takes a "callback" function for each constructor in the ADT. In our case, it takes a function for the empty list case, and another function for the "cons cell" case.

Each callback function accepts as arguments the values which are accepted by the constructor. So the "empty list" case takes no arguments, but the "cons cell" case takes two arguments: the head and the tail of the list.

We can encode these "multiple arguments" using Tuple classes, or using currying. In this example, I chose to use a simple Pair class.

The interface is implemented once for each constructor. First, we have the implementation for the "empty list". The deconstruct implementation simply calls the emptyCase callback function.

```<code>class ConsListEmpty<A> implements ConsList<A> {
  public ConsListEmpty() {}

  public <R> R deconstruct(
    Function<Unit, R> emptyCase,
    Function<Pair<A,ConsList<A>>, R> consCase
  ) {
    return emptyCase.apply(new Unit());
  }
}
</code>```

Then we implement the "cons cell" case similarly. This time the class has properties: the head and tail of the non-empty list. In the deconstruct implementation, those properties are passed to the consCase callback function.

```<code>class ConsListConsCell<A> implements ConsList<A> {
  private A head;
  private ConsList<A> tail;

  public ConsListCons(A head, ConsList<A> tail) {
    this.head = head;
    this.tail = tail;
  }

  public <R> R deconstruct(
    Function<Unit, R> emptyCase,
    Function<Pair<A,ConsList<A>>, R> consCase
  ) {
    return consCase.apply(new Pair<A,ConsList<A>>(this.head, this.tail));
  }
}
</code>```

Here is an example of using this encoding of ADTs: we can write a reduce function which is the usual fold over lists.

```<code><T> T reduce(Function<Pair<T,A>,T> reducer, T initial, ConsList<T> l) {
  return l.deconstruct(
    ((unit) -> initial),
    ((t) -> reduce(reducer, reducer.apply(initial, t.v1), t.v2))
  );
}
</code>```

This is analogous to this implementation in Haskell:

```<code>reduce reducer initial l = case l of
  Empty -> initial
  Cons t_v1 t_v2  -> reduce reducer (reducer initial t_v1) t_v2
</code>```

Body:
The data type ConsList<A> can be represented as an interface. The interface exposes a single deconstruct method which allows you to "deconstruct" a value of that type - that is, to handle each of the possible constructors. Calls to a deconstruct method are analogous to a case of form in Haskell or ML.

interface ConsList<A> {
  <R> R deconstruct(
    Function<Unit, R> emptyCase,
    Function<Pair<A,ConsList<A>>, R> consCase
  );
}

The deconstruct method takes a "callback" function for each constructor in the ADT. In our case, it takes a function for the empty list case, and another function for the "cons cell" case.

Each callback function accepts as arguments the values which are accepted by the constructor. So the "empty list" case takes no arguments, but the "cons cell" case takes two arguments: the head and the tail of the list.

We can encode these "multiple arguments" using Tuple classes, or using currying. In this example, I chose to use a simple Pair class.

The interface is implemented once for each constructor. First, we have the implementation for the "empty list". The deconstruct implementation simply calls the emptyCase callback function.

class ConsListEmpty<A> implements ConsList<A> {
  public ConsListEmpty() {}

  public <R> R deconstruct(
    Function<Unit, R> emptyCase,
    Function<Pair<A,ConsList<A>>, R> consCase
  ) {
    return emptyCase.apply(new Unit());
  }
}

Then we implement the "cons cell" case similarly. This time the class has properties: the head and tail of the non-empty list. In the deconstruct implementation, those properties are passed to the consCase callback function.

class ConsListConsCell<A> implements ConsList<A> {
  private A head;
  private ConsList<A> tail;

  public ConsListCons(A head, ConsList<A> tail) {
    this.head = head;
    this.tail = tail;
  }

  public <R> R deconstruct(
    Function<Unit, R> emptyCase,
    Function<Pair<A,ConsList<A>>, R> consCase
  ) {
    return consCase.apply(new Pair<A,ConsList<A>>(this.head, this.tail));
  }
}

Here is an example of using this encoding of ADTs: we can write a reduce function which is the usual fold over lists.

<T> T reduce(Function<Pair<T,A>,T> reducer, T initial, ConsList<T> l) {
  return l.deconstruct(
    ((unit) -> initial),
    ((t) -> reduce(reducer, reducer.apply(initial, t.v1), t.v2))
  );
}

This is analogous to this implementation in Haskell:

reduce reducer initial l = case l of
  Empty -> initial
  Cons t_v1 t_v2  -> reduce reducer (reducer initial t_v1) t_v2


问:
Git branching from a feature branch to work on a subfeature
We're currently in the following situation, where a feature branch has been branched for a sub-feature branch (like, working on backend and frontend things for the same feature):

```<code>o
|
o development
|\
| o feature-a
| |
| o
| |\
| | o feature-a-sub
| | |
| | |
|  \
|   o merged feature-a into feature-a-sub
|  /
o feature-a-sub merged into development
| |
| o feature-a with future work on it
|
o development
</code>```

A developer first merged feature-a into his feature-a-sub branch to be up-to-date, and then merged his feature-a-sub into development. Whereas the initial feature-a branch is still existent, and not yet finished.

In my point of view, this yields the problem that the feature-a branch is now rendered obsolete, as all changes are merged into feature-a-sub and then into development. In addition, work has continued on feature-a, which leads to future merge conflicts and a lot of manual labor.

Where did we take the wrong turn, and how would a proper workflow with less trouble look like?

答:
One should only merge to and from parent branch.  For feature-a-sub, this is feature-a, not development.

Merging to the grandparent branch means that the reason that the parent branch was created hasn't been fulfilled, and yes, as noted this does create future problems where development continues on feature-a and development leading to an increased divergence of the code lines and more conflicts down the road.

This was assuming that feature-a-sub depended on the code in feature-a.  If feature-a-sub was instead independent of feature-a, it shouldn't have been branched from feature-a at all and instead should have been branched (and merged) into development.

If feature-a needed feature-a-sub to work (not sure it did as feature-a continued work without a merge of feature-a-sub into it), and feature-a-sub was independent of feature-a, feature-a-sub should instead have been feature-b with a branch from development, a merge back into development, and then either a merge of development or feature-b (if one doesn't want to pick up other changes from development) into feature-a.

The workflow should either be:

```<code>o
|
o development
|\
| o feature-a
| |
| o
| |\
| | o feature-a-sub
| | |
| | |
| | |
| | o merged feature-a into feature-a-sub
| |/
| o feature-a-sub merged into feature-a
| |
| o feature-a with future work on it
|
o development
</code>```

or

```<code>o
|
o development
|\
| \
|  \
|   o feature-a
|\  |
| b | feature-b
| | |
| | |
| | |
| b | feature-b complete
|/ \|
o   o feature-b merged to development and feature-a
|   |
|   o feature-a with future work on it
</code>```

Related - a favorite read of mine on the philosophy of branching: Advanced SCM Branching Strategies.  While the white paper is targeted to centralized version control systems, the ideas behind the roles each branch can take are important in making sure you understand what is going on and can reason about what should be done next with any given branch.

Body:
One should only merge to and from parent branch.  For feature-a-sub, this is feature-a, not development.

Merging to the grandparent branch means that the reason that the parent branch was created hasn't been fulfilled, and yes, as noted this does create future problems where development continues on feature-a and development leading to an increased divergence of the code lines and more conflicts down the road.

This was assuming that feature-a-sub depended on the code in feature-a.  If feature-a-sub was instead independent of feature-a, it shouldn't have been branched from feature-a at all and instead should have been branched (and merged) into development.

If feature-a needed feature-a-sub to work (not sure it did as feature-a continued work without a merge of feature-a-sub into it), and feature-a-sub was independent of feature-a, feature-a-sub should instead have been feature-b with a branch from development, a merge back into development, and then either a merge of development or feature-b (if one doesn't want to pick up other changes from development) into feature-a.

The workflow should either be:

o
|
o development
|\
| o feature-a
| |
| o
| |\
| | o feature-a-sub
| | |
| | |
| | |
| | o merged feature-a into feature-a-sub
| |/
| o feature-a-sub merged into feature-a
| |
| o feature-a with future work on it
|
o development

or

o
|
o development
|\
| \
|  \
|   o feature-a
|\  |
| b | feature-b
| | |
| | |
| | |
| b | feature-b complete
|/ \|
o   o feature-b merged to development and feature-a
|   |
|   o feature-a with future work on it

Related - a favorite read of mine on the philosophy of branching: Advanced SCM Branching Strategies.  While the white paper is targeted to centralized version control systems, the ideas behind the roles each branch can take are important in making sure you understand what is going on and can reason about what should be done next with any given branch.


答:
It's important to remember that you don't need to create classes for different objects because they're different objects, you need to do it for when THE WAY YOU INTERACT with those objects is different.

For example, you have a "pencil" and a "stapler" in your Article store. for the purposes of purveying a pencil or a stapler to a purchaser, there is absolutely no difference between them.

If you have a "stapler" and a "music file download" then you have two objects that YOU have to treat differently...one is physical inventory (perhaps) and the other is not.  One requires shipping, one requires downloading.

Sometimes this is hard to tease apart. The appearance of different attributes on the object can seem to indicate a different class type, for example that stapler may be "color=red" and it makes no sense to have a download with "color=red".

Again, to sum up:  defining classes in a system is all about the differentiation in how you will interact with them, not in how different those objects might be.

Title: Inheritance or type field when designing class

Body:
I have to model a store with all kinds of articles. The user has to be able to filter these articles by type, price, ... . The store would contain a list of Article objects.

I've been stuck on whether to implement the Article class with a type field or to subclass new articles from the Article class.

Biggest problem I see when implementing with inheritance is the filtering by type. I'm going to have to lookup which type my derived objects in the Article list are, which would either require that every derived class has a getType() function or I'd have to use reflection to get the class name and work with that, both of which kinda defeats the purpose of inheritance. To access the specific fields of each derived class, i'd first have to filter by type and then downcast all Article objects of the correct type to that type to be able to access their specific fields. I have no idea if this is considered a good design.

On the other hand, I had the idea to have the Article class have a type field and a Map to represent it's data. I would then have to ensure that the necessary (key, value) pairs are added to the map for each different type and maintain an ENUM for the fields of each different type. Article would become an incredibly flexible class this way so I'd have to make sure my factory method's for each type would ensure the right pairs are added to the info map depending on the type. It would also require more discipline from the coder using the Article class to only access the map keys that are defined for that particular type.

I could also just keep different derived objects in different lists in the shop, but then I'd have to add a list every time I'd add a new article which isn't good for maintainability.

Any extra arguments for any of the possibilities that could help me decide would be appreciated.


问:
Direct Dependency Injection and Logger
Lets say I use Dependency Injection and don't use a DI framework. So the injection is direct rather automatic. How I should handle the logger class? All the objects, (thousands) should have a Logger reference in their constructors? (We don't consider Singletons and Service Locater as they hide the dependency, and are pathological liars.)</p>

答:
You basically have two options.

Use the composition relationship

You would't pass a class implementing a Log interface to a class, but you would create an abstract class where, in its constructor, you directly initialize it's protected Log member with new instance of your class implementing the Log interface.

All classed which need to use the logger will then inherit this class and if you at any time in the future need to change the procedure of loggin mechanism, you can just swap out the one new in your base abstract class to a new logger and the change will be propagated throughout all your classes.

Use static methods

Logging is such a simple task, it produces no side effects. It merely opens a stream to log (be it a database or a file) and flushes the log contents there.

Because of its simplicity, logger can go into the utilities package.

However, there is one problem. If you, at any time in the future, decide, you want to change the way processes are logged, you will have to alter the logger class and its logging methods. In this process you are either very likely to lose the initial logging mechanism or going to comment out code for the initial procedures, which will make your code messy.

Where I work, we use the first approach - a simple logging interface, containing methods like logInfo or logError and have classes implement the interface.

Even though we usually restrain from the composition relationship, because it is hard to mock, the logger class, as I have said, is so simple, we have made an exception for it, because we still like it a tad more than having a static logger.

Title: Direct Dependency Injection and Logger


答:
How I should handle the logger class?

You should instantiate it and inject it into stuff that needs it.

All the objects, (thousands) should have a Logger reference in their constructors?

So what? If those objects need to log, then they need to get that dependency somewhere.

I would argue that have such pervasive dependencies is a smell, even for logging.

Title: Direct Dependency Injection and Logger

Body: Lets say I use Dependency Injection and don't use a DI framework. So the injection is direct rather automatic. How I should handle the logger class? All the objects, (thousands) should have a Logger reference in their constructors? (We don't consider Singletons and Service Locater as they hide the dependency, and are pathological liars.)</p>


答:
Do you know all possible types at compile time? Is it possible that your code needs to handle types that you never heard of? In that case you cannot have a class for that type.

Do you have more categories than just "type" for which you would want to create a different class? You might end up with a lot of classes. Ever seen a car manufacturer claiming that you can buy 9 billion different variations of a car? You better not try to create a class for each variation.

Whether class or typefield is better depends on the situation. And there will be borderline cases where neither is much better than the other, and it's a matter of taste.


问:
Function or class design in library API for efficient object reuse
I am currently building a library in C++11, where I spent a lot of time trying to design a good interface. After some small redesigns along the way, I've ended up with a design that I am happy with. The main public interface only consists of two functions in a namespace (ignoring extra utility functions etc.).

Later I found that I needed to create some objects based on a bitflag parameter given in one of the functions. Both functions can be expected to be called very often (e.g. to process each frame of a video) where the flags are unlikely to change. So to avoid repeated object creation I made a utility function for reusing those objects based on the bitflag parameter (a simplistic object cache function with a static container of shared_ptr objects inside it if you're wondering). A cache class of some kind would probably be better, but I digress.

I now face the following design decision: Should I keep my functions or should I redesign my library around a main class instead?

I really like the simplicity of my two functions and creating an entire class feels like overengineering, and functions make more sense for the interface I feel. The main class would also have to coordinate processing calls (e.g. to process image frames), with subsequent getters to retrieve information.

On the other hand, a class will make reuse of objects more intuitive, do away with a bunch of function friend declarations, and better represent dependencies between multiple calls, whereas the functions would have a common dependency on object reuse which feels less intuitive since they are separate functions, but can perhaps work if designed correctly behind the scenes.

答:
Neither.

Instead, consider making your code reentrant again:

Put all the costly but reusable state in a class.

Take that as an argument by reference, and clean up the interface to get rid of whatever you thus duplicated.

(Whether you add a member forwarding to the free function is yours to decide.)

Add a convenience-function encapsulating both steps with the same interface and name as the old function had to preserve API and ABI compatibility, maybe with a [[deprecated]]-mark if you consider removing it in the future.


问:
Running time of the specified Bubble Sort Algorithm
I have been working on a few algorithm questions the last few days, and one bubble sort problem in particular has been giving me headaches.

```<code>for (k=1; k <= A.length - 1; k++) {         //Line 1
   for (m=1; m <= A.length - k; m++) {      //Line 2
      if (A[m-1] > A[m]) {                  //Line 3
        Swap (A[m-1], A[m]);                //Line 4
}
</code>```

Now, I am supposed to find the running time of this algorithm in the worst case scenario, and I know that it is O(n^2), but the problem I am having is finding out how many times is each line executed.

For example, line 1 is going to take n units of time, while line 4 depends on the complexity of function Swap. However, line 2 on the other hand is going to take [(n-1) * ?] units of time (I tried finding out exactly and I got (n-1)*n)
and I am stomped with finding how to do the IF statement, but I assume it will take (? - 1) times. IF anyone could give me an explanation on how to do this, I would greatly appreciate it.

答:
Don't worry about the if statement.  If your data is random, you can assume that the if statement will be true about half the time, but you don't need to care about that.  The basic rule of thumb for this type of analysis is very simple: count loops.  When it comes down to it, what's going to determine how long your algorithm runs is how many times the if statement in its entirety runs.

That's why big-O is expressed as an asymptote.  You have 2 nested loops, and as the size of the data set increases, the total runtime is weighted more and more heavily on the square of the size, therefore the time complexity is on the order of n^2.  To visualize this, remember that statistically, you expect the if statement to be true half the time.  Try graphing 0.5(x^2), and then graph (x^2), and see how the 1/2 scaling becomes less and less important as x grows larger and larger.


问:
Possibility of retrieving X value after Bitwise OR operator

Z = X ∨ Y

(where X, Y, Z are 96bits binary numbers)

If I have "Z" value and "Y" value. Are there any possibilities to retrieve "X" value from "Z"?

What I know is it is possible to do this with XOR operator, but is it same with OR operator?

答:
Each bit in the result is the result of an operation on the corresponding bits in the two operands.

For XOR:

```<code>X ^ Y = Z                 Y ^ Z = X
0 ^ 0 = 0                 0 ^ 0 = 0
0 ^ 1 = 1   --inverse->   1 ^ 1 = 0
1 ^ 0 = 1                 0 ^ 1 = 1
1 ^ 1 = 0                 1 ^ 0 = 1
</code>```

Given a pair of bits from Y and Z, you can determine the value of that X's bit must've had.

For inclusive OR:

```<code>X | Y = Z                 Y ¤ Z = X
0 | 0 = 0                 0 ¤ 0 = 0
0 | 1 = 1   --inverse->   1 ¤ 1 = 0
1 | 0 = 1                 0 ¤ 1 = 1
1 | 1 = 1                 1 ¤ 1 = 1
</code>```

We can see here that for the case of Y=1 Z=1, X could be either 0 and 1.
For the two other cases, you can determine the value of X.

The answer is that some of the bits of X can be reconstituted, but for any of the indeterminate cases, you will end up with indeterminate values.

Body:
Each bit in the result is the result of an operation on the corresponding bits in the two operands.

For XOR:

X ^ Y = Z                 Y ^ Z = X
0 ^ 0 = 0                 0 ^ 0 = 0
0 ^ 1 = 1   --inverse->   1 ^ 1 = 0
1 ^ 0 = 1                 0 ^ 1 = 1
1 ^ 1 = 0                 1 ^ 0 = 1

Given a pair of bits from Y and Z, you can determine the value of that X's bit must've had.

For inclusive OR:

X | Y = Z                 Y ¤ Z = X
0 | 0 = 0                 0 ¤ 0 = 0
0 | 1 = 1   --inverse->   1 ¤ 1 = 0
1 | 0 = 1                 0 ¤ 1 = 1
1 | 1 = 1                 1 ¤ 1 = 1

We can see here that for the case of Y=1 Z=1, X could be either 0 and 1.
For the two other cases, you can determine the value of X.

The answer is that some of the bits of X can be reconstituted, but for any of the indeterminate cases, you will end up with indeterminate values.


问:
Arguments againts checking-in binary files into SCMs
I work for a company that primarily builds Java applications and I'm trying to convince everybody to stop checking-in binary files (dependencies and final products) to SCM.

They know it is a bad practice but they think that "it works" and it is not really a problem even when many people know about Maven and other tools for building besides Ant. Both PMs and programmers (around 50 people) are ready to listen to any argument against and even acknowledge that it is a waste of backup space but I want to be really convincing because the habit change would involve a lot of effort. What arguments do you use to support a change?

Edit: Okay, it makes sense to make a distinction between files that almost do not change, like dependencies, and generated files. Even so, I'm interested in reasons against the latter.

答:
One of the primary advantages of using SCMs is that you can reconstruct your system from anytime in the past. So there is no point is storing your final build in your SCM because you can just check out the revision number and build it.

You mention dependencies...
Your SCM should be set up so that you can do a clean checkout to a new machine (with dev environment), hit build and you should be able to build your system without needing to install anything else. So keeping binary dependencies in your SCM is a good idea. Libraries rarely change so they won't take up much room.

Almost no one does this.


问:
Ruby on Rails database using static lookup tables or constant strings
In some ruby on rails projects, I have seen instances where strings are used instead of a foreign key reference to a lookup table.

I usually code in C#/SQL Server and use lookup tables, but am not particularly experienced in ruby on rails.

So my question is, should I be using strings instead of lookup tables in my ruby on rails web project (mysql and active record)? Is this something specific to ruby on rails, or to dynamically typed languages? Or for some particular circumstances? Or is it just bad database design?

By lookup tables I mean, like the following

UserStatus

```
Id    Name
1     Active
2     Disabled
```

User

```
Id    Username               UserStatusId
1     john.smith@gmail.com   1
1     jane.smith@gmail.com   2
```

Whereas with just strings

User

```
Id    Username               UserStatus
1     john.smith@gmail.com   active
1     jane.smith@gmail.com   disabled
```

答: You can also use the ActiveHash Gem to create a static Model from a YAML/JSON file.</p>


问:
Is there an reason to call the base constructor of object?
I wonder if there is any reason to call the base constructor when inheriting from object.

```<code>class Foo
{
    public Foo()
        : base() // calling the Object constructor
    {
        // Foo construct here
    }
}
</code>```

Is there a way to inject code into the base constructor? Object doesn't seem to have multiple constructors.

答:
There is no need to explicitly call the base constructor in this situation. The base constructor is automatically called if it has no parameters. So the code is equivalent to just doing:

```<code>class Foo
{
    public Foo()
    {
        // Foo construct here
    }
}
</code>```

: base is only needed if the base class needs parameters passed to its constructor.

Body:
There is no need to explicitly call the base constructor in this situation. The base constructor is automatically called if it has no parameters. So the code is equivalent to just doing:

class Foo
{
    public Foo()
    {
        // Foo construct here
    }
}

: base is only needed if the base class needs parameters passed to its constructor.


问:
To god (class) or not to god?
I'm working on a project that requires several different users in the system, all of which have overlapping responsibilities; we've isolated two possible ways of tackling this problem, but we're unsure which of them are the most correct way of going about it.

Option 1: Create a virtual super-class for all the user-classes to inherit from. This super-class will have a boolean field for each of the responsibilities, allowing us to toggle which of the sub-classes have which responsibility.

Pros

One single class for all the sub-classes to inherit from, letting us toggle responsibilities via boolean fields

Cons:

It's essentially a god-class, which means it holds too much responsibility

Option 2: Create nineteen (19) interfaces, each representing one of the available responsibilities, and then have each of the user-classes inherit from this pool of interfaces in order to determine their responsibilities.

Pros

It allows us to seperate the concerns into several interfaces

Cons

We'll be in over our heads with interfaces, making it difficult to keep track of

So which is the best way of doing it, or is there perhaps a better way?

To elaborate my question I'm including the graphic below; it showcases the relations between the different parts of the system and the different users.

R means read access and RW means read + write access.

As you can see it's a bit of a mess of interlacing attributes.

答:
Option 3: Create individual objects corresponding to specific responsibilities, and then have each user hold a collection of these.

The collection of responsibilities for a user will contain only the responsibilities assigned to the user, i.e. you don't need an object to indicate the lack of a responsibility.

You worry it is "overkill" to create 19 classes for 19 responsibilities, but actually it is the simplest solution. If you indicate the same with 19 boolean fields on the base class, you have the same number of semantic entities, but a much more complex system overall, since each new responsibility increases the complexity of all user classes. By having the responsibilities as objects separate from the user, a new responsibility will not affect the user classes at all, but only the specific parts of the program which check for this specific responsibility.

Also, you can easily separate the assignment of responsibilities into a configuration. This would be quite tricky with option 1 and impossible with option 2.

Note: If you need to distinguish between read and read/write you need more that 19 boolean fields or 19 interfaces. For option 1 you need tri-state enumerations rather than booleans. For option 2 you need 38 distinct interfaces. For option 3 you can have a boolean flag on each responsibility which indicate if it is read or read/write.

Title: To god (class) or not to god?


答:
I'd opt for option 3, use composition.

Depending on what you are doing with the responsibilities, you might be able to use an enum for them:

```<code>public enum Responsibilities
{
    Responsibility1,
    Responsibility2,
    ...
}
</code>```

Then your user class might be something like:

```<code>public class User
{
    private List<Responsibilities> _responsibilities =
        List<Responsibilities>();

    public void AddResponsibility(Responsibilities responsibility) =>
        _responsibilities.Add(responsibility);

    public bool HasResponsibility(Responsibilities responsibility) =>
        responsibilities.Contains(responsibility);
}
</code>```

If your need logic behind each responsibility, replace the enum with an IResponsibility interface and have each responsibility class implement that interface.

Title: To god (class) or not to god?

Body:
I'm working on a project that requires several different users in the system, all of which have overlapping responsibilities; we've isolated two possible ways of tackling this problem, but we're unsure which of them are the most correct way of going about it.

Option 1: Create a virtual super-class for all the user-classes to inherit from. This super-class will have a boolean field for each of the responsibilities, allowing us to toggle which of the sub-classes have which responsibility.

Pros

One single class for all the sub-classes to inherit from, letting us toggle responsibilities via boolean fields

Cons:

It's essentially a god-class, which means it holds too much responsibility

Option 2: Create nineteen (19) interfaces, each representing one of the available responsibilities, and then have each of the user-classes inherit from this pool of interfaces in order to determine their responsibilities.

Pros

It allows us to seperate the concerns into several interfaces

Cons

We'll be in over our heads with interfaces, making it difficult to keep track of

So which is the best way of doing it, or is there perhaps a better way?

To elaborate my question I'm including the graphic below; it showcases the relations between the different parts of the system and the different users.

R means read access and RW means read + write access.

As you can see it's a bit of a mess of interlacing attributes.

Body:
I'd opt for option 3, use composition.

Depending on what you are doing with the responsibilities, you might be able to use an enum for them:

public enum Responsibilities
{
    Responsibility1,
    Responsibility2,
    ...
}

Then your user class might be something like:

public class User
{
    private List<Responsibilities> _responsibilities =
        List<Responsibilities>();

    public void AddResponsibility(Responsibilities responsibility) =>
        _responsibilities.Add(responsibility);

    public bool HasResponsibility(Responsibilities responsibility) =>
        responsibilities.Contains(responsibility);
}

If your need logic behind each responsibility, replace the enum with an IResponsibility interface and have each responsibility class implement that interface.