问:
Optimizing a file type for compare tools
Context:
I am developing a visual studio plugin that generates layer diagrams.
I want the tool to be able to produce an intermediate output, which is the data representation of what is being rendered in the diagram. The idea is that this serialized data can then be checked in together with the source code which would allow developers to more quickly see how architecture changes between commits. This would either be done through general diff tools (like git-diff) or a dedicated diff tool. However i want the file format to be optimized for the first, because of their accessibility. The data would be represented as a tree structure of nodes, where each node would have a name and a list of dependencies (other nodes represented by their path + name).

Question:
When designing a file format, are there things regarding what data interchange-format or syntax is used and the formatting of this syntax (use of line breaks for example) that would make different versions of the file easier or harder to compare using tools like git-diff. For example, ensuring that the tool sees a "rename" as a "rename" and not an "delete" followed by an unrelated "add".

答:
This sounds like a very cool idea. Can you make one for C++ (nudge-nudge)?

I've done something similar to this before as kind of a poor man's, humanly-supervised testing in rushed scenarios where I just outputted files from manually-executed tests outside of CI with the resulting output files submitted to version control. Then I'd inspect the file diffs to look for unanticipated changes (these were in approximation fields where the changes didn't necessarily indicate erroneous output, but should be monitored carefully).

I can only give some general suggestions without knowing the elaborate details, but my basic suggestion to start would be to favor a format that is as flat as possible.

That is, avoid something like XML here. XML can be great, but it's not necessarily the most diff-friendly or the easiest to read. There's ways to get the nested structure an XML file represents in a flat way. For example:

```<code><foo>
   <blah/>
   <bar>
      <baz/>
   </bar>
</foo>
<x>
   <y value="123"/>
</x>
</code>```

... might be represented in a flat way as:

```<code>[foo]
blah

[foo/bar]
baz

[x]
y = 123
</code>```

... something like this as a crude example. You can think of it kind of like a file system structure where stuff in [...] is a directory and the stuff below are like files within that directory. It'll be easier to control that way and have everything on its own line, easy to spot differences, etc.

Next easy step is just sort the entries in the file ("directories" at the top-level and "files" within a directory). That'll give your file format a lot of stability so that it doesn't just arbitrarily rearrange the contents of the file and totally screw up the diff, tagging way more lines as changed than necessary.

I think you can actually stop at this point. If you want to go further, you can start introducing extra whitespaces to leave room for new entries to be inserted within a "directory", e.g. (kind of like a growable array container implementation which has excess memory capacity to append elements to the end without a linear-time complexity reallocation and transfer of the previous contents), and even leave "tombstone" whitespace lines behind that you can reclaim when new things are inserted. That'll result in the minimal amount of shifting changes to the file in common cases in exchange for big shifts in rare cases, though I think it's really overkill and will come with the burden on your human readers to deal with excess and seemingly-arbitrary whitespaces. It's also far more complex since you'd have to inspect the previous files you made to modify them instead of just being able to overwrite them.

The sorting and flattening of the format is the easiest way to achieve a pretty good stability of a text format IMO for diff purposes. Last but not least, this is probably just common sense and something you already know upfront, but naturally it'd be good to grab various diff tools and test your outputs against them.

Body:
This sounds like a very cool idea. Can you make one for C++ (nudge-nudge)?

I've done something similar to this before as kind of a poor man's, humanly-supervised testing in rushed scenarios where I just outputted files from manually-executed tests outside of CI with the resulting output files submitted to version control. Then I'd inspect the file diffs to look for unanticipated changes (these were in approximation fields where the changes didn't necessarily indicate erroneous output, but should be monitored carefully).

I can only give some general suggestions without knowing the elaborate details, but my basic suggestion to start would be to favor a format that is as flat as possible.

That is, avoid something like XML here. XML can be great, but it's not necessarily the most diff-friendly or the easiest to read. There's ways to get the nested structure an XML file represents in a flat way. For example:

<foo>
   <blah/>
   <bar>
      <baz/>
   </bar>
</foo>
<x>
   <y value="123"/>
</x>

... might be represented in a flat way as:

[foo]
blah

[foo/bar]
baz

[x]
y = 123

... something like this as a crude example. You can think of it kind of like a file system structure where stuff in [...] is a directory and the stuff below are like files within that directory. It'll be easier to control that way and have everything on its own line, easy to spot differences, etc.

Next easy step is just sort the entries in the file ("directories" at the top-level and "files" within a directory). That'll give your file format a lot of stability so that it doesn't just arbitrarily rearrange the contents of the file and totally screw up the diff, tagging way more lines as changed than necessary.

I think you can actually stop at this point. If you want to go further, you can start introducing extra whitespaces to leave room for new entries to be inserted within a "directory", e.g. (kind of like a growable array container implementation which has excess memory capacity to append elements to the end without a linear-time complexity reallocation and transfer of the previous contents), and even leave "tombstone" whitespace lines behind that you can reclaim when new things are inserted. That'll result in the minimal amount of shifting changes to the file in common cases in exchange for big shifts in rare cases, though I think it's really overkill and will come with the burden on your human readers to deal with excess and seemingly-arbitrary whitespaces. It's also far more complex since you'd have to inspect the previous files you made to modify them instead of just being able to overwrite them.

The sorting and flattening of the format is the easiest way to achieve a pretty good stability of a text format IMO for diff purposes. Last but not least, this is probably just common sense and something you already know upfront, but naturally it'd be good to grab various diff tools and test your outputs against them.


问:
Is it true that calling _exit() instead of exit() won't prevent static destructors from being called?
On comp.lang.c++.moderated@googlegroups.com, Greg Herlihy posted the following extern "C" function:

```<code>extern "C"
{
    int func()
    {
        wchar_t memoryName[256];
        wchar_t mutexName[256];
        wchar_t eventName[256];
        mbstowcs(memoryName, "MemoryName", 256);
        mbstowcs(mutexName, "MutexName", 256);
        mbstowcs(eventName, "EventName", 256);
        std::wstring memoryString(memoryName);
        std::wstring mutexString(mutexName);
        std::wstring eventString(eventName);
        CDataTransferServer *srv = new CDataTransferServer();
        srv->Initialize(1, CC_SAMPLETYPE_MPEG4,128,256,64);
        printf("Inside entry point tester 1\n");
        srv->AddUser(5, memoryString, mutexString, eventString);
        printf("Inside entry point tester 2\n");
        delete srv;
        printf("Exiting entry point tester 3\n");
    }
}
</code>```

which is a g++ entry point different than main(int argc, char*argv[]).

Greg Herlihy then wrote:

Calling _exit() (which presumably should be "_Exit()") - does not "prevent"
  C++ global objects from being destroyed. The destruction of a C++ program's
  global objects is not inevitable. Instead a C++ program is responsible for
  destroying its own global objects - and can do so in one of two ways: the
  program returns from main() or it calls exit(). So a C++ program that fails
  to exit main() and neglects to call exit() before it terminates - will not
  have destroyed its global objects by the time it ended.

I don't believe that follows from what is written in the standard.

As far as I can see, when I call exit(), the spec guarantees that:

Destructors for objects with automatic storage duration
will not be called.

Destructors for objects with with static storage duration
will be called, in reverse order of construction.

The worrying thing is that the standard doesn't say anything about
    exit() or _exit(), so I'm relying on implementation-dependent behavior.

Not so. The C++ Standard specifies that calling exit() destroys global
  objects[3.6.3/1] And _Exit() is part of the C99 Standard (and will
  presumably be incorporated into the next C++ Standard by reference).

Right, the C++ standard says what exit() does, but it doesn't say what
_exit() or _Exit() do. And the C standard certainly doesn't say
anything about C++ destructors.

I don't see any implementation-defined behavior here. Calling _Exit() is no
  more likely to destroy a C++ program's global objects than calling printf()
  - or calling any other function that is not exit().

_exit() and _Exit() are specified not to call any functions registered
atexit() or on_exit(). However, that's not useful for C++ because the
C++ spec doesn't say by what means the runtime takes care of calling
destructors of objects with static storage duration. A compliant
implementation could use a mechanism other than atexit() or on_exit()
to invoke static destructors.

In other words, the C++ spec does not say anything all about the
behavior of _exit() or _Exit(). Therefore, I cannot make any assumptions
about whether or not calling either function will cause destructors
of static objects to run or not.

Any comments are welcome.

答:
In other words, the C++ spec does not say anything all about the
  behavior of _exit() or _Exit(). Therefore, I cannot make any
  assumptions about whether or not calling either function will cause
  destructors of static objects to run or not.

If we're talking about standard behavior, I'm afraid I don't know. It might very well simply be unspecified.

However, every compiler/platform I've encountered aligns with what Greg wrote, and it's kind of a stumbling point if you ever inject your own C standard runtime library (CRT) to find that static objects are neither initialized on startup nor destroyed on exit without doing this all manually. Destructors for globals/statics tend to be invoked in the atexit hook stage, and the main point of _exit is to bypass that whole process (and thereby typically bypass destruction of such objects).

It makes practical sense whether or not it's unspecified to avoid invoking destructors in this context, since to do so would kind of contradict the whole point of _exit (which is to avoid that kind of atexit cleanup phase). Even if alternate mechanisms were available within the language to invoke these destructors, probably such shutdown mechanisms would likewise be bypassed by _exit.

So it's kind of like the assumptions that std::vector is contiguous before the standard specified it. It ended up being a pretty reasonable assumption in practice since that was about the only practical way to end up with an implementation that conformed to its requirements.

Maybe a language lawyer could jump in here and clear things up, but I'd suspect that it's a very practical assumption that _exit avoids invoking destructors for globals/statics.

ContentLicense: CC BY-SA 3.0


问:
TDD: Write a separate test for object initialization or relying on other tests exercising it
This seems to be the common pattern that's emerging in some of the tests I've worked on lately.  We have a class, and quite often this is legacy code whose design can't be easily altered, which has a bunch of member variables.

There's some kind of "Initialize" or "Load" function which would put an object into a valid state. Only after it is initialized/loaded, are the members in the proper state so that other methods can be exercised.

So when we start writing tests, first test is "TestLoad" and all we put in there is exercising initialization logic. Then we might add one (or few) TestLoadFailureXXX tests and those are definitely valuable.

Then we start writing tests to verify other behaviors but all of them require the object to be loaded. So they all start by running exactly the same code as "TestLoad".

So my question: Is TestLoad even necessary? Do you take it out and let other tests simply exercise the loading? Or leave it so things are more explicit?

I know that each unit test function should have no (or as little as possible) overlap with other test functions, but it seems like in cases of loading, this is unavoidable. And whether we like it or not, if something in the loading code breaks, we will end up with a whole test suite of failures.

Is there another approach that I might be missing here?

Thank you for the responses. It definitely makes sense that you want to see "InitializationTest" and if that fails you know where to start looking.

In case it matters, this question is mostly about C++ and we use CppUnit framework. And now, thanks to sleske, I'll be constantly wishing that CppUnit supported test dependencies.  Might have to hack something in one of these days :)

答:
What I'm missing in the other answers is the following: when should you test the initialization method?

An important aspect here is: how complex is the initialization method? Is it simply assigning the arguments to attributes? Like this:

```<code>void initialize(Foo fooThingy, Bar barObject) {
    this.foo = fooThingy;
    this.bar = barObject;
    this.baz = "Initialized with a constant";
}
</code>```

If so, I would not bother testing it separately.

However, if the logic is quite complex, has a couple of edge-cases, etc, then I'd definitely write multiple tests for it. Both for the success and the failure cases.

For all the other tests, make sure to start off with a valid instance of the SUT (Subject Under Test), preferably constructed in a helper method. But since the initialize method is non-trivial it needs multiple tests.

Body:
What I'm missing in the other answers is the following: when should you test the initialization method?

An important aspect here is: how complex is the initialization method? Is it simply assigning the arguments to attributes? Like this:

void initialize(Foo fooThingy, Bar barObject) {
    this.foo = fooThingy;
    this.bar = barObject;
    this.baz = "Initialized with a constant";
}

If so, I would not bother testing it separately.

However, if the logic is quite complex, has a couple of edge-cases, etc, then I'd definitely write multiple tests for it. Both for the success and the failure cases.

For all the other tests, make sure to start off with a valid instance of the SUT (Subject Under Test), preferably constructed in a helper method. But since the initialize method is non-trivial it needs multiple tests.


问:
Does making a method static save memory on a class you'll have many instances of?
In response to Aaronaught's response to the question at:

Can't I just use all static methods?

Isn't less memory used for a static method? I am under the impression that each object instance carries around its own executable version of a non-static member function.

Regardless of how much overhead is involved in calling a static method, regardless of poor OO design, and possible headaches down the road, doesn't it use less memory at runtime?

Here is an example:

I make a vector of zero-initialized objects. Each object contains one piece of data (a triangle consisting of nine double's). Each object is populated in sequence from data read from a .stl file. Only one static method is needed. Proper OO design dictates that a method dealing with the the data directly should be distributed to each object. Here is the standard OO solution:

```<code>foreach(obj in vec) {
  obj.readFromFile(fileName);
}
</code>```

Each obj carries readFromFile's compiled code alongside the data!

Memory is more of a concern than performance in this case, and there is a LOT of data on a constrained system.

Solutions:

Namespace method (great for C++ but not possible in Java)

One static method in obj's class. Executable code is kept in one place at runtime. There is a small overhead to call the method.

A parent class from which obj is derived, which contains the private method readFromFile. Call with super.callPrivateMethod() which calls readFromFile. Messy, and still some memory overhead in each object.

Implement readFromFile outside obj's scope, so in vec's class or in the calling class. This, in my opinion, breaks data encapsulation.

I realize for large amounts of data one explicit object for each triangle is not the best approach. This is only an example.

答:
A method should be "static" (many languages use the term "class method" which is much better) if it doesn't refer to an instance of the class. It should be an instance method if it refers to an instance of the class. </p>

<p>Making a design decision based on the vague possibility of some memory savings instead of the proper use of class methods and instance methods is a very, very, very bad idea. </p>

Body:
A method should be "static" (many languages use the term "class method" which is much better) if it doesn't refer to an instance of the class. It should be an instance method if it refers to an instance of the class.

Making a design decision based on the vague possibility of some memory savings instead of the proper use of class methods and instance methods is a very, very, very bad idea.


答:
Right, the C++ standard says what exit() does, but it doesn't say what _exit() or _Exit() do.

From n3290 which, if I'm not mistaken, is the C++11 standard excepted minor last minute editorial changes:

The function _Exit(int status) has additional behavior in this International Standard:

The program is terminated without executing destructors for objects of automatic, thread, or static storage duration and without calling functions passed to atexit()

There is no description of _exit (but then the C standard does not describe _exit either).

Title: Is it true that calling _exit() instead of exit() won't prevent static destructors from being called?

Body:
On comp.lang.c++.moderated@googlegroups.com, Greg Herlihy posted the following extern "C" function:

```<code>extern "C"
{
    int func()
    {
        wchar_t memoryName[256];
        wchar_t mutexName[256];
        wchar_t eventName[256];
        mbstowcs(memoryName, "MemoryName", 256);
        mbstowcs(mutexName, "MutexName", 256);
        mbstowcs(eventName, "EventName", 256);
        std::wstring memoryString(memoryName);
        std::wstring mutexString(mutexName);
        std::wstring eventString(eventName);
        CDataTransferServer *srv = new CDataTransferServer();
        srv->Initialize(1, CC_SAMPLETYPE_MPEG4,128,256,64);
        printf("Inside entry point tester 1\n");
        srv->AddUser(5, memoryString, mutexString, eventString);
        printf("Inside entry point tester 2\n");
        delete srv;
        printf("Exiting entry point tester 3\n");
    }
}
</code>```

which is a g++ entry point different than main(int argc, char*argv[]).

Greg Herlihy then wrote:

Calling _exit() (which presumably should be "_Exit()") - does not "prevent"
  C++ global objects from being destroyed. The destruction of a C++ program's
  global objects is not inevitable. Instead a C++ program is responsible for
  destroying its own global objects - and can do so in one of two ways: the
  program returns from main() or it calls exit(). So a C++ program that fails
  to exit main() and neglects to call exit() before it terminates - will not
  have destroyed its global objects by the time it ended.

I don't believe that follows from what is written in the standard.

As far as I can see, when I call exit(), the spec guarantees that:

Destructors for objects with automatic storage duration
will not be called.

Destructors for objects with with static storage duration
will be called, in reverse order of construction.

The worrying thing is that the standard doesn't say anything about
    exit() or _exit(), so I'm relying on implementation-dependent behavior.

Not so. The C++ Standard specifies that calling exit() destroys global
  objects[3.6.3/1] And _Exit() is part of the C99 Standard (and will
  presumably be incorporated into the next C++ Standard by reference).

Right, the C++ standard says what exit() does, but it doesn't say what
_exit() or _Exit() do. And the C standard certainly doesn't say
anything about C++ destructors.

I don't see any implementation-defined behavior here. Calling _Exit() is no
  more likely to destroy a C++ program's global objects than calling printf()
  - or calling any other function that is not exit().

_exit() and _Exit() are specified not to call any functions registered
atexit() or on_exit(). However, that's not useful for C++ because the
C++ spec doesn't say by what means the runtime takes care of calling
destructors of objects with static storage duration. A compliant
implementation could use a mechanism other than atexit() or on_exit()
to invoke static destructors.

In other words, the C++ spec does not say anything all about the
behavior of _exit() or _Exit(). Therefore, I cannot make any assumptions
about whether or not calling either function will cause destructors
of static objects to run or not.

Any comments are welcome.


问:
How to architect frequent updates in No-sql db (Cassandra) - architecture
I'm storing some data in Cassandra, then after analyzing it puts in several table, I have its aggregation as daily, weekly, monthly, yearly basis. But after some time if some user reads the content I'm changing it in to read and unread status based on user activity.

But as per my current design either I need to update in all tables at-a-time (more than 5 tables and it may increase) or need create a single table for read unread but want to join the tables, Which is not recommending with nosql concept.

Any existing good architecture for it? I checked with lambda architecture but didn't get a good solution.

答:
Aggregated or analytical data is often immutable, that is, it represents a finalized view of data over a certain time period, or w/r/t to some transformational processing.

So perhaps some of your problem stems from post hoc alteration of this data. Denormalized data is common in Cassandra, but maybe it would make sense to maintain the individual items (with the user read/unread status) in one table, and then re-run the aggregation as often as needed, storing the results separately.

The aggregate data itself can be stored in a single table by adding a clustering key to your table, allowing queries to be executable against a single temporal chunk (day, month, year, etc.)

Cassandra Timeseries Data Modeling


问:
C++ : Lack of Standardization at the Binary Level
Why ISO/ANSI didn't standardize C++ at the binary level? There are many portability issues with C++, which is only because of lack of it's standardization at the binary level.

Don Box writes, (quoting from his book Essential COM, chapter COM As A Better C++)

C++ and Portability

  Once the decision is made to
  distribute a C++ class as a DLL, one
  is faced with one of the fundamental
  weaknesses of C++, that is, lack of
  standardization at the binary level.
  Although the ISO/ANSI C++ Draft
  Working Paper attempts to codify which
  programs will compile and what the
  semantic effects of running them will
  be, it makes no attempt to standardize
  the binary runtime model of C++. The
  first time this problem will become
  evident is when a client tries to link
  against the FastString DLL's import library from
  a C++ developement environment other
  than the one used to build the
  FastString DLL.

Are there more benefits Or loss of this lack of binary standardization?

答:
There are many portability issues with C++, which is only because of
  lack of it's standardization at the binary level.

I don't think it's quite this simple. The answers provided already provide excellent rationale as to the lack of focus on standardization, but C++ may be too rich of a language to be well-suited to genuinely compete with C as an ABI standard.

We can go into name mangling resulting from function overloading, vtable incompatibilities, incompatibilities with exceptions throw across module boundaries, etc. All of these are a real pain, and I do wish they could at least standardize vtable layouts.

But an ABI standard isn't just about making C++ dylibs produced in one compiler capable of being used by another binary built by a different compiler. ABI is used cross-languages. It would be nice if they could at least cover the first part, but there's no way I see C++ ever truly competing with C at the sort of universal ABI level so crucial for making the most widely-compatible dylibs.

Imagine a simple pair of functions exported like this:

```<code>void f(Foo foo);
void f(Bar bar, int val);
</code>```

... and imagine Foo and Bar were classes with parameterized constructors, copy constructors, move constructors, and non-trivial destructors.

Then take the scenario of a Python/Lua/C#/Java/Haskell/etc. developer trying to import this module and use it in their language.

First we'd need a name mangling standard for how to export symbols utilizing function overloading. This is an easier part. Yet it shouldn't really be name "mangling". Since users of the dylib have to look up symbols by name, the overloads here should lead to names which don't look like a complete mess. Maybe the symbol names could be like "f_Foo" "f_Bar_int" or something of that sort. We'd have to be sure they can't clash with a name actually defined by the developer, perhaps reserving some symbols/characters/conventions for ABI usage.

But now a tougher scenario. How does the Python developer, for example, invoke move constructors, copy constructors, and destructors? Maybe we could export those as part of the dylib. But what if Foo and Bar are exported in different modules? Should we duplicate the symbols and implementations associated in this dylib or not? I'd suggest we do, since it might get really annoying really fast otherwise to start having to get tangled up in multiple dylib interfaces just to create an object here, pass it here, copy one there, destroy it here. While the same basic concern could somewhat apply in C (just more manually/explicitly), C tends to avoid this just by nature of the way people program with it.

This is just a small sample of the awkwardness. What happens when one of the f functions above throws a BazException (also a C++ class with constructors and destructors and deriving std::exception) into JavaScript?

At best I think we can only hope to standardize an ABI that works from one binary produced by one C++ compiler to another binary produced by another. That would be great, of course, but I just wanted to point this out. Typically accompanying such concerns to distribute a generalized library that works cross-compilers is also often the desire to make it really generalized and compatible cross-languages.

Suggested Solution

My suggested solution after struggling to find ways to use C++ interfaces for APIs/ABIs for years with COM-style interfaces is to just become a "C/C++" (pun) developer.

Use C to create those universal ABIs, with C++ for the implementation. We can still do things like export functions that return pointers to opaque C++ classes with explicit functions to create and destroy such objects on the heap. Try to fall in love with that C aesthetic from an ABI perspective even if we're totally using C++ for the implementation. Abstract interfaces can be modeled using tables of function pointers. It's tedious to wrap this stuff up into a C API, but the benefits and the compatibility of the distribution that comes with that will tend to make it very worthwhile.

Then if we don't like using this interface so much directly (we probably shouldn't at least for RAII reasons), we can wrap it all we want in a statically-linked C++ library we ship with the SDK. C++ clients can use that.

Python clients won't want to use either a C or C++ interface directly as there's no ways to make those pythonique. They'll want to wrap it up into their own pythonique interfaces, so it's actually a good thing that we're just exporting a bare minimum C API/ABI to make that as easy as possible.

I think a lot of the C++ industry would benefit from doing this more rather than trying to stubbornly ship COM-style interfaces and so forth. It would also make all of our lives easier as users of these dylibs to not have to fuss about with awkward ABIs. C makes it simple, and the simplicity of it from an ABI perspective allows us to create APIs/ABIs that work naturally and with minimalism for all kinds of FFIs.

OwnerDisplayName: Nawaz

ContentLicense: CC BY-SA 2.5

Body:
There are many portability issues with C++, which is only because of
  lack of it's standardization at the binary level.

I don't think it's quite this simple. The answers provided already provide excellent rationale as to the lack of focus on standardization, but C++ may be too rich of a language to be well-suited to genuinely compete with C as an ABI standard.

We can go into name mangling resulting from function overloading, vtable incompatibilities, incompatibilities with exceptions throw across module boundaries, etc. All of these are a real pain, and I do wish they could at least standardize vtable layouts.

But an ABI standard isn't just about making C++ dylibs produced in one compiler capable of being used by another binary built by a different compiler. ABI is used cross-languages. It would be nice if they could at least cover the first part, but there's no way I see C++ ever truly competing with C at the sort of universal ABI level so crucial for making the most widely-compatible dylibs.

Imagine a simple pair of functions exported like this:

void f(Foo foo);
void f(Bar bar, int val);

... and imagine Foo and Bar were classes with parameterized constructors, copy constructors, move constructors, and non-trivial destructors.

Then take the scenario of a Python/Lua/C#/Java/Haskell/etc. developer trying to import this module and use it in their language.

First we'd need a name mangling standard for how to export symbols utilizing function overloading. This is an easier part. Yet it shouldn't really be name "mangling". Since users of the dylib have to look up symbols by name, the overloads here should lead to names which don't look like a complete mess. Maybe the symbol names could be like "f_Foo" "f_Bar_int" or something of that sort. We'd have to be sure they can't clash with a name actually defined by the developer, perhaps reserving some symbols/characters/conventions for ABI usage.

But now a tougher scenario. How does the Python developer, for example, invoke move constructors, copy constructors, and destructors? Maybe we could export those as part of the dylib. But what if Foo and Bar are exported in different modules? Should we duplicate the symbols and implementations associated in this dylib or not? I'd suggest we do, since it might get really annoying really fast otherwise to start having to get tangled up in multiple dylib interfaces just to create an object here, pass it here, copy one there, destroy it here. While the same basic concern could somewhat apply in C (just more manually/explicitly), C tends to avoid this just by nature of the way people program with it.

This is just a small sample of the awkwardness. What happens when one of the f functions above throws a BazException (also a C++ class with constructors and destructors and deriving std::exception) into JavaScript?

At best I think we can only hope to standardize an ABI that works from one binary produced by one C++ compiler to another binary produced by another. That would be great, of course, but I just wanted to point this out. Typically accompanying such concerns to distribute a generalized library that works cross-compilers is also often the desire to make it really generalized and compatible cross-languages.

Suggested Solution

My suggested solution after struggling to find ways to use C++ interfaces for APIs/ABIs for years with COM-style interfaces is to just become a "C/C++" (pun) developer.

Use C to create those universal ABIs, with C++ for the implementation. We can still do things like export functions that return pointers to opaque C++ classes with explicit functions to create and destroy such objects on the heap. Try to fall in love with that C aesthetic from an ABI perspective even if we're totally using C++ for the implementation. Abstract interfaces can be modeled using tables of function pointers. It's tedious to wrap this stuff up into a C API, but the benefits and the compatibility of the distribution that comes with that will tend to make it very worthwhile.

Then if we don't like using this interface so much directly (we probably shouldn't at least for RAII reasons), we can wrap it all we want in a statically-linked C++ library we ship with the SDK. C++ clients can use that.

Python clients won't want to use either a C or C++ interface directly as there's no ways to make those pythonique. They'll want to wrap it up into their own pythonique interfaces, so it's actually a good thing that we're just exporting a bare minimum C API/ABI to make that as easy as possible.

I think a lot of the C++ industry would benefit from doing this more rather than trying to stubbornly ship COM-style interfaces and so forth. It would also make all of our lives easier as users of these dylibs to not have to fuss about with awkward ABIs. C makes it simple, and the simplicity of it from an ABI perspective allows us to create APIs/ABIs that work naturally and with minimalism for all kinds of FFIs.


问:
Detecting surface faces of a huge 3D mesh/grid
I've written a module in my application that creates a mesh from existing coordinate and face data. The number of vertices in the mesh could easily exceed 10 million and the same goes for the faces.

The problem with the raw data is that the faces are defined by the coordinates of their vertices and not the index of the vertices in the vertex data. So the connectivity of face to vertex has to be extracted upon creation o the mesh.

One issue that is very important in this application is smooth rendering of this mesh in OpenGL. for this purpose, I need to detect the "surface" faces of this mesh, because rendering all the faces including the invisible ones makes the rendering process very time consuming and not practical.

In order to detect the outer surface of the mesh, I need to count how many elements each face belongs to. The faces that are only in one element are considered to be the surface faces and will be rendered. So I need to avoid having duplicate faces in the mesh.

Right now, I'm using a Tree with a comparator that sorts the vertices by X, then Y, then Z. Using this tree I can check for existence of each vertex and avoid adding duplicates and assign a unique id to each unique vertex. Another tree sorts the faces by the index of their vertices. This way duplicate faces are not added either. This setup works fine and I can detect the surfaces correctly using the connectivity of faces and elements.

But here's the problem; when the number of vertices and faces reaches 1e6 or more, these two trees can take up to 1~2 gigabytes of memory, which is very undesirable.

My questions are:

Is there a better algorithm to detect the surface faces of a huge mesh?

Is there a better data structure to achieve the desired outcome?

答:
First Tree

[...] these two trees can take up to 1~2 gigabytes of memory, which is
  very undesirable.

What I recommend here is going to seem odd and dumb, but it's playing to constants more rather than scalability. I've beaten professionally-written K-D trees with this dumb approach in C++ for tens of millions of vertices, but just for this peculiar case of finding duplicates points.

For the first tree (finding which vertex indices are associated to a face), build some NxNxN grid, say 100x100x100. That's going to result in 1,000,000 grid cells which sounds astronomical...

... except each grid cell just stores a single index: 4 megabytes -- phew!

```<code>// Don't actually use a class here (wasteful), using it for clarity.
class GridCell
{
    // Index to head node.
    int head;
}
</code>```

Each cell stores a pointer (index) to a grid node. A grid node looks like this:

```<code>// Don't actually use a class here (wasteful), using it for clarity.
class GridNode
{
    // Index to source vertex.
    int vertex;

    // Index to next node.
    int next;
}
</code>```

This means an overhead of 8 bytes per vertex. At 10 mil vertices, that comes out to 80 megabytes. We're basically modeling a singly-linked list per cell using just indices.

So your actual grid looks like this:

```<code>class Grid
{
    // 1,000,000 cells = 4 megabytes
    // Set these initially to -1 to indicate the end of the list.
    private int[][][] cells = new int[100][100][100];

    // 10,000,000 vertices = 40*2 = 80 megabytes
    private int[][] nodes = new int[num_verts][2];

    // Can use this to try inserting a new vertex.
    private int vertex_count = 0;

    // Grid extents (AABB)
    private float[] bmin = new float[3];
    private float[] bmax = new float[3];
}
</code>```

And that's it, 80 megabytes for 10 mil vertices plus 4 megabytes for a million cells plus 24 bytes for the bounding box (plus a trivial amount of memory for Java object metadata and possible padding for alignment). The total is just a little over 84 megabytes.

Now start off encompassing a bounding box for all the vertices you have. I wasn't sure if you had the vertex positions with the vertices in addition, or only face data. Either way, loop through either of those and compute a bounding box extents that fits everything and initialize your grid.

Next, start inserting each vertex into the grid at the cell it belongs. You can find the cell index for a dimension like so:

```<code>int grid_cell_x(float point_x)
{
    // Unit size of grid (bbox size divided by grid dimension).
    float grid_unit_x = (bmax[0] - bmin[0]) / 100.0f;

    // Return point position on grid (truncated to integer: floored).
    return (int)((point_x - bmin[0]) / grid_unit_x);
}
</code>```

... something like this (and hopefully not duplicated for all 3 dimensions, and with some pre-computed values if necessary to avoid division and stuff -- can micro-tune as needed).

When inserting the vertex, first search through this singly-linked list to see if there's a vertex in the same position. If so, skip and possibly return the index for the existing vertex. If the vertex with the same coordinates doesn't exist, then you can insert it to the list: simply set the next index of the grid node for the vertex to the grid cell head index, and then set the grid cell head index to the grid node index (just singly-linked list insertion using indices).

Pseudocode:

```<code>int grid_pos[3] = grid_index(vertex.position)
for each node in cell(grid_pos), n:
    if vertices[n.vertex].position == vertex.position:
        return n.vertex

add new node -- get node_index
node.next = flat_index(grid_pos)
node.vertex = vertex_index
cell(grid_pos).head = node_index
</code>```

Apologies, that's a really coarse example that leaves a lot to fill in between the lines. But I hope it's enough to fill in the rest. We're basically just searching through a singly-linked list for the grid cell in which a vertex lands looking for duplicated vertices. It only gets roundabout because we're using indices to avoid object overhead and also get a 32-bit size.

And tada -- you have a million-cell grid which only takes 84 megabytes for 10 million vertices. I've found this works better than octrees and k-d trees, including ones that I didn't write myself. It impressed people so much that we ended up replacing a k-d tree implementation with this seemingly-stupid solution in a commercial software. It even fares well for edge cases where you might think it won't, like a mesh with very uneven density (though there could be a really pathological case where these other spatial indexing structures could fare better, like a million vertices all near-coincident with one outlier vertex to mess up the whole thing in which it would almost certainly fare much worse).

You can also adjust the grid size, and it doesn't have to be uniform. 100x100x100 is a decent starting point, and should be pretty quick for even tens of millions of vertices (what I often test around). The solution I use is a little more complex than this adjusting the grid cell count based on mesh density and bounding box size, but it's still pretty simple.

Most of all, it's very predictable -- constant time 3-dimensional chained hash table-like searches, big old array to make it easy how much memory is used (and using very little even with so many cells).

So I'd suggest this. If not, k-d tree or octree works quite well, but you need to tune those (especially octree) and impose max depth limits and such to keep it from using explosive memory like the tree you are currently using.

Second Tree

For the second tree, a considerably better solution is simple. Don't use a tree at all to sort. Just use a big old array and sort that and then do a linear pass checking next elements for consecutive duplicate faces. A balanced BST is very wasteful if all you are going to use it for is to sort data one time and dispose of it.

Anyway, I hope this helps a bit. I glossed over some fine details for brevity, but it should be pretty easy to figure out.

Body:
First Tree

[...] these two trees can take up to 1~2 gigabytes of memory, which is
  very undesirable.

What I recommend here is going to seem odd and dumb, but it's playing to constants more rather than scalability. I've beaten professionally-written K-D trees with this dumb approach in C++ for tens of millions of vertices, but just for this peculiar case of finding duplicates points.

For the first tree (finding which vertex indices are associated to a face), build some NxNxN grid, say 100x100x100. That's going to result in 1,000,000 grid cells which sounds astronomical...

... except each grid cell just stores a single index: 4 megabytes -- phew!

// Don't actually use a class here (wasteful), using it for clarity.
class GridCell
{
    // Index to head node.
    int head;
}

Each cell stores a pointer (index) to a grid node. A grid node looks like this:

// Don't actually use a class here (wasteful), using it for clarity.
class GridNode
{
    // Index to source vertex.
    int vertex;

    // Index to next node.
    int next;
}

This means an overhead of 8 bytes per vertex. At 10 mil vertices, that comes out to 80 megabytes. We're basically modeling a singly-linked list per cell using just indices.

So your actual grid looks like this:

class Grid
{
    // 1,000,000 cells = 4 megabytes
    // Set these initially to -1 to indicate the end of the list.
    private int[][][] cells = new int[100][100][100];

    // 10,000,000 vertices = 40*2 = 80 megabytes
    private int[][] nodes = new int[num_verts][2];

    // Can use this to try inserting a new vertex.
    private int vertex_count = 0;

    // Grid extents (AABB)
    private float[] bmin = new float[3];
    private float[] bmax = new float[3];
}

And that's it, 80 megabytes for 10 mil vertices plus 4 megabytes for a million cells plus 24 bytes for the bounding box (plus a trivial amount of memory for Java object metadata and possible padding for alignment). The total is just a little over 84 megabytes.

Now start off encompassing a bounding box for all the vertices you have. I wasn't sure if you had the vertex positions with the vertices in addition, or only face data. Either way, loop through either of those and compute a bounding box extents that fits everything and initialize your grid.

Next, start inserting each vertex into the grid at the cell it belongs. You can find the cell index for a dimension like so:

int grid_cell_x(float point_x)
{
    // Unit size of grid (bbox size divided by grid dimension).
    float grid_unit_x = (bmax[0] - bmin[0]) / 100.0f;

    // Return point position on grid (truncated to integer: floored).
    return (int)((point_x - bmin[0]) / grid_unit_x);
}

... something like this (and hopefully not duplicated for all 3 dimensions, and with some pre-computed values if necessary to avoid division and stuff -- can micro-tune as needed).

When inserting the vertex, first search through this singly-linked list to see if there's a vertex in the same position. If so, skip and possibly return the index for the existing vertex. If the vertex with the same coordinates doesn't exist, then you can insert it to the list: simply set the next index of the grid node for the vertex to the grid cell head index, and then set the grid cell head index to the grid node index (just singly-linked list insertion using indices).

Pseudocode:

int grid_pos[3] = grid_index(vertex.position)
for each node in cell(grid_pos), n:
    if vertices[n.vertex].position == vertex.position:
        return n.vertex

add new node -- get node_index
node.next = flat_index(grid_pos)
node.vertex = vertex_index
cell(grid_pos).head = node_index

Apologies, that's a really coarse example that leaves a lot to fill in between the lines. But I hope it's enough to fill in the rest. We're basically just searching through a singly-linked list for the grid cell in which a vertex lands looking for duplicated vertices. It only gets roundabout because we're using indices to avoid object overhead and also get a 32-bit size.

And tada -- you have a million-cell grid which only takes 84 megabytes for 10 million vertices. I've found this works better than octrees and k-d trees, including ones that I didn't write myself. It impressed people so much that we ended up replacing a k-d tree implementation with this seemingly-stupid solution in a commercial software. It even fares well for edge cases where you might think it won't, like a mesh with very uneven density (though there could be a really pathological case where these other spatial indexing structures could fare better, like a million vertices all near-coincident with one outlier vertex to mess up the whole thing in which it would almost certainly fare much worse).

You can also adjust the grid size, and it doesn't have to be uniform. 100x100x100 is a decent starting point, and should be pretty quick for even tens of millions of vertices (what I often test around). The solution I use is a little more complex than this adjusting the grid cell count based on mesh density and bounding box size, but it's still pretty simple.

Most of all, it's very predictable -- constant time 3-dimensional chained hash table-like searches, big old array to make it easy how much memory is used (and using very little even with so many cells).

So I'd suggest this. If not, k-d tree or octree works quite well, but you need to tune those (especially octree) and impose max depth limits and such to keep it from using explosive memory like the tree you are currently using.

Second Tree

For the second tree, a considerably better solution is simple. Don't use a tree at all to sort. Just use a big old array and sort that and then do a linear pass checking next elements for consecutive duplicate faces. A balanced BST is very wasteful if all you are going to use it for is to sort data one time and dispose of it.

Anyway, I hope this helps a bit. I glossed over some fine details for brevity, but it should be pretty easy to figure out.


问:
Find path of steepest descent along with path length in a matrix
Came across this problem --
You are given a grid with numbers that represent the elevation at a particular point. From each box in the grid you can go north, south, east, west - but only if the elevation of the area you are going into is less than the one you are in, i.e. you can only descend. You can start anywhere on the map and you are looking for a starting point with the longest possible path down as measured by the number of boxes you visit. And if there are several paths down of the same length, you want to take the one with the steepest vertical drop, i.e. the largest difference between your starting elevation and your ending elevation.
Ex Grid:

```<code>4 8 7 3
2 5 9 3
6 3 2 5
4 4 1 6
</code>```

On this particular map the longest path down is of length=5 and it is: 9-5-3-2-1.

There is another path that is also length five: 8-5-3-2-1. dropping from 9 to 1(8) is a steeper drop than 8 to 1(7).
WAP to find the longest (and then steepest) path.

I've worked through Floyd Warshalls, DAG + Topological sorting, tried to think of DFS, though about DP, various things but I am not able to find a way to think through. Any pointers + simple pseudo code for approach would be helpful.

答:
A dynamic programming approach should work.

For each cell:

Reduce the problem of finding the best (longest, steepest slope) descending path from there to the problem of finding the best path from each of its neighbors that is smaller and then adding the step to that neighbor to get the best path from the cell in question.

Memo(r)ize the best path from each cell along the way.

Don't actually save an explicit path, only save the next cell on the path (that way the path is there, just implicitly).

That should run in time linear to the size of the matrix if you do it correctly... unless I'm misunderstanding the problem of course.

Code might look something like:

public class BestDynamicDescendingPathFinder {
    public static int[][] example = new int[][]{{4, 8, 7, 3},{2, 5, 9, 3},{6, 3, 2, 5},{4, 4, 1, 6}};

    public static void main(String[] args)
    {
        BestDynamicDescendingPathFinder finder = new BestDynamicDescendingPathFinder(example);
        System.out.println("Best overall: " + Arrays.toString(finder.find()));
        System.out.println("Best starting from some other cell: " + Arrays.toString(finder.unfoldBestPathFromCell(3, 3)));
    }

    private int[][] matrix;
    private PathInformation[][] informationForBestPathFromCellMemory;

    public BestDynamicDescendingPathFinder(int[][] aMatrix)
    {
        informationForBestPathFromCellMemory = new PathInformation[aMatrix.length][];
        matrix = new int[aMatrix.length][];

        for(int i = 0; i < aMatrix.length; i++)
        {
            informationForBestPathFromCellMemory[i] = new PathInformation[aMatrix[i].length];
            matrix[i] = new int[aMatrix[i].length];

            for(int j = 0; j < aMatrix[i].length; j++)
            {
                matrix[i][j] = aMatrix[i][j];
            }
        }
    }

    // find the best path by getting the best starting cell and unfolding the information for it
    public int[] find()
    {
        int currentBestStartingCellColumn = 0;
        int currentBestStartingCellRow = 0;
        for(int i = 0; i < matrix.length; i++)
        {
            for(int j = 0; j < matrix[i].length; j++)
            {
               if(getInformationForBestPathFromCell(i, j).compareTo(getInformationForBestPathFromCell(currentBestStartingCellColumn, currentBestStartingCellRow)) == 1){
                   currentBestStartingCellColumn = i;
                   currentBestStartingCellRow = j;
               }
            }
        }

        return unfoldBestPathFromCell(currentBestStartingCellColumn, currentBestStartingCellRow);
    }

    // unfold the best path (starting) from a cell by walking the PathInformation structures in memory
    private int[] unfoldBestPathFromCell(int colNum, int rowNum)
    {
        PathInformation currentCellInformation = getInformationForBestPathFromCell(colNum, rowNum);
        int[] path = new int[currentCellInformation.length];
        path[0] = matrix[colNum][rowNum];
        int idx = 1;

        while(currentCellInformation.length > 1)
        {
            path[idx] = matrix[currentCellInformation.nextCellColumn][currentCellInformation.nextCellRow];
            idx++;
            currentCellInformation = getInformationForBestPathFromCell(currentCellInformation.nextCellColumn, currentCellInformation.nextCellRow);
        }

        return path;
    }

    // get the information for the best path (starting) from a cell: from memory if available or calculate otherwise
    private PathInformation getInformationForBestPathFromCell(int colNum, int rowNum)
    {
        if(informationForBestPathFromCellMemory[colNum][rowNum] == null)
        {
            informationForBestPathFromCellMemory[colNum][rowNum] = calculateInformationForBestPathFromCell(colNum, rowNum);
        }
        return informationForBestPathFromCellMemory[colNum][rowNum];
    }

    // calculate the information for the best path (starting) from a cell by using the information for best paths from neighboring cells
    private PathInformation calculateInformationForBestPathFromCell(int colNum, int rowNum)
    {
        List<PathInformation> possiblePathsFromCell = new ArrayList<PathInformation>();
        if(colNum != 0 && matrix[colNum - 1][rowNum] < matrix[colNum][rowNum])
        {
            PathInformation p = getInformationForBestPathFromCell(colNum - 1, rowNum);
            possiblePathsFromCell.add(new PathInformation(p.length + 1, matrix[colNum][rowNum], p.endValue, colNum - 1, rowNum));
        }

        if(colNum != matrix.length - 1 && matrix[colNum + 1][rowNum] < matrix[colNum][rowNum])
        {
            PathInformation p = getInformationForBestPathFromCell(colNum + 1, rowNum);
            possiblePathsFromCell.add(new PathInformation(p.length + 1, matrix[colNum][rowNum], p.endValue, colNum + 1, rowNum));
        }

        if(rowNum != 0 && matrix[colNum][rowNum - 1] < matrix[colNum][rowNum])
        {
            PathInformation p = getInformationForBestPathFromCell(colNum, rowNum - 1);
            possiblePathsFromCell.add(new PathInformation(p.length + 1, matrix[colNum][rowNum], p.endValue, colNum, rowNum - 1));
        }

        if(rowNum != matrix[colNum].length -1 && matrix[colNum][rowNum + 1] < matrix[colNum][rowNum])
        {
            PathInformation p = getInformationForBestPathFromCell(colNum, rowNum + 1);
            possiblePathsFromCell.add(new PathInformation(p.length + 1, matrix[colNum][rowNum], p.endValue, colNum, rowNum + 1));
        }

        if(possiblePathsFromCell.isEmpty())
        {
            return new PathInformation(1, matrix[colNum][rowNum], matrix[colNum][rowNum], -1, -1);
        }

        return Collections.max(possiblePathsFromCell);
    }
}

public class PathInformation implements Comparable<PathInformation>
{
    int length;
    int startValue;
    int endValue;
    int nextCellColumn;
    int nextCellRow;

    public PathInformation(int length, int startValue, int endValue, int nextCellColumn, int nextCellRow)
    {
        this.length = length;
        this.startValue = startValue;
        this.endValue = endValue;
        this.nextCellColumn = nextCellColumn;
        this.nextCellRow = nextCellRow;
    }

    @Override
    public int compareTo(PathInformation other) {
        if(this.length < other.length || (this.length == other.length && this.startValue - this.endValue < other.startValue - other.endValue)){
            return -1;
        }
        if(this.length > other.length || (this.length == other.length && this.startValue - this.endValue > other.startValue - other.endValue)){
            return 1;
        }
        return 0;
    }
}
```


答:
A few observations about this problem.

You are looking for the longest path with the given constraint, so it is not helpful to use A* or Floyd-Warshall which are designed to find the shortest path.

In extreme cases, the path could contain all fields of the grid, e.g.:

```<code>1 2 3
8 9 4
7 6 5
</code>```

(here, the path forms a spiral, but other figures are possible.)

Therefore, an ideal algorithm cannot be better than O(n), which is also the same complexity as visiting each field once.

Given a field F and its surrounding fields N, E, S, W as far as they exist, we can calculate the path length L(F) as

```<code>       ⎧ 1 + F(M) if M exists
L(F) = ⎨
       ⎩ 0        otherwise
</code>```

where M ∈ {N, E, S, W} so that Value(M) < Value(F) and F(M) = max({F(X) | X ∈ {N, E, S, W}}). As pseudo-code:

```<code>def L(F):
  lower = {X for X in {N, E, S, W} if X.value < F.value}
  if lower.is_empty:
    return 0
  return 1 + max({ L(X) for X in lower})
</code>```

Proof of correctness is left as an exercise to the reader.

The function L(F) may be calculated using memoization. That is, we build a cache for L(F) so that each field is only calculated once. At the beginning, each calculation might involve the calculations for other fields as well, in the worst case all fields. Therefore, our memoized L(F) has complexity O(n) to O(1) depending on whether the cache already contains the necessary values. But on average over the whole cache complexity is O(1) (each value is computed only once, and is only requested a constant number of times).

So if we iterate over all fields and calculate the path length for that field, this iteration will be O(n). Therefore, this algorithm with memoization is ideal!

We cannot apply dynamic programming, since we do not know which fields would have to be calculated first. Well, we could sort all fields by their value and start calculating lowest first, but that would end up being more expensive and way more complicated than building the cache lazily.

While calculating L(F), we can also somehow keep track of the path that contains some field, and the currently longest paths. All of this will not affect the complexity.

Together, the following approach emerges:

each field in your matrix has three properties: value, length, and next field in the path.

as an implementation detail, you'll have to figure out how to retrieve the neighbour fields for a given field.

the length is lazily calculated.

when the M neighbour is selected, the next field is set to M. This might be problematic if more than one field has the properties of M, e.g. in this matrix:

```<code>1 2 3
4 9 8
5 8 9
</code>```

Starting from the 9s, it is not immediately clear which 8 should be part of the ideal path. Either you implement this to keep track of all possible paths (which does not affect the complexity), or you select the partial path with the steepest descent. This will require you to walk both paths which is not free but O(n). To avoid this, you can memoize the maximum slope as an additional property of each field.

By the way, that example shows a case where there are two solutions 9-8-3-2-1.

Pseudo-code:

record Field {
  value  : Int
  length : Count? = null
  next   : Field? = null
  slope  : Int?   = null
}

get-neighbours(f : Field): Set[Field] {
  ...
}

get-length(f : Field): Int {
  if f.length != null {
    return f.length
  }

  let next : Collection[Field] = get-neighbours(f)
    .where(x -> x.value < f.value) // must be smaller
    .max-by(x -> get-length(x)) // must have longest partial path
    .max-by(x -> x.slope) // prefer steepest path

  if next.is_empty {
    f.length = 0
    return f.length
  }

  let next = next.first // pick any field that satisfies all properties
  f.next = next
  f.slope = next.slope ?? f.value - next.value
  f.length = 1 + next.length
  return f.length
}

get-path(f: Field): Field generator {
  yield f
  if f.next != null {
    yield from get-path(f.next)
  }
}

let matrix : Array[height, Array[width, Field]] = {
  { Field(1), ... },
  ...,
}

// evaluate length for each field in matrix
// and keep track of longest paths

let mut longest = List()
let mut length = 0

for f in matrix {
  let l = get-lengh(f)
  if l > length {
    length = get-length(f)
    longest = List(f)
  }
  else if l == length {
    longest.add(f)
  }
}

// print out longest paths
for start in longest {
  println(List(get-path(start)))
}
```

Title: Find path of steepest descent along with path length in a matrix

Body:
Came across this problem --
You are given a grid with numbers that represent the elevation at a particular point. From each box in the grid you can go north, south, east, west - but only if the elevation of the area you are going into is less than the one you are in, i.e. you can only descend. You can start anywhere on the map and you are looking for a starting point with the longest possible path down as measured by the number of boxes you visit. And if there are several paths down of the same length, you want to take the one with the steepest vertical drop, i.e. the largest difference between your starting elevation and your ending elevation.
Ex Grid:

```<code>4 8 7 3
2 5 9 3
6 3 2 5
4 4 1 6
</code>```

On this particular map the longest path down is of length=5 and it is: 9-5-3-2-1.

There is another path that is also length five: 8-5-3-2-1. dropping from 9 to 1(8) is a steeper drop than 8 to 1(7).
WAP to find the longest (and then steepest) path.

I've worked through Floyd Warshalls, DAG + Topological sorting, tried to think of DFS, though about DP, various things but I am not able to find a way to think through. Any pointers + simple pseudo code for approach would be helpful.

Body:
A few observations about this problem.

You are looking for the longest path with the given constraint, so it is not helpful to use A* or Floyd-Warshall which are designed to find the shortest path.

In extreme cases, the path could contain all fields of the grid, e.g.:

1 2 3
8 9 4
7 6 5

(here, the path forms a spiral, but other figures are possible.)

Therefore, an ideal algorithm cannot be better than O(n), which is also the same complexity as visiting each field once.

Given a field F and its surrounding fields N, E, S, W as far as they exist, we can calculate the path length L(F) as

       ⎧ 1 + F(M) if M exists
L(F) = ⎨
       ⎩ 0        otherwise

where M ∈ {N, E, S, W} so that Value(M) < Value(F) and F(M) = max({F(X) | X ∈ {N, E, S, W}}). As pseudo-code:

def L(F):
  lower = {X for X in {N, E, S, W} if X.value < F.value}
  if lower.is_empty:
    return 0
  return 1 + max({ L(X) for X in lower})

Proof of correctness is left as an exercise to the reader.

The function L(F) may be calculated using memoization. That is, we build a cache for L(F) so that each field is only calculated once. At the beginning, each calculation might involve the calculations for other fields as well, in the worst case all fields. Therefore, our memoized L(F) has complexity O(n) to O(1) depending on whether the cache already contains the necessary values. But on average over the whole cache complexity is O(1) (each value is computed only once, and is only requested a constant number of times).

So if we iterate over all fields and calculate the path length for that field, this iteration will be O(n). Therefore, this algorithm with memoization is ideal!

We cannot apply dynamic programming, since we do not know which fields would have to be calculated first. Well, we could sort all fields by their value and start calculating lowest first, but that would end up being more expensive and way more complicated than building the cache lazily.

While calculating L(F), we can also somehow keep track of the path that contains some field, and the currently longest paths. All of this will not affect the complexity.

Together, the following approach emerges:

each field in your matrix has three properties: value, length, and next field in the path.

as an implementation detail, you'll have to figure out how to retrieve the neighbour fields for a given field.

the length is lazily calculated.

when the M neighbour is selected, the next field is set to M. This might be problematic if more than one field has the properties of M, e.g. in this matrix:

1 2 3
4 9 8
5 8 9

Starting from the 9s, it is not immediately clear which 8 should be part of the ideal path. Either you implement this to keep track of all possible paths (which does not affect the complexity), or you select the partial path with the steepest descent. This will require you to walk both paths which is not free but O(n). To avoid this, you can memoize the maximum slope as an additional property of each field.

By the way, that example shows a case where there are two solutions 9-8-3-2-1.

Pseudo-code:

record Field {
  value  : Int
  length : Count? = null
  next   : Field? = null
  slope  : Int?   = null
}

get-neighbours(f : Field): Set[Field] {
  ...
}

get-length(f : Field): Int {
  if f.length != null {
    return f.length
  }

  let next : Collection[Field] = get-neighbours(f)
    .where(x -> x.value < f.value) // must be smaller
    .max-by(x -> get-length(x)) // must have longest partial path
    .max-by(x -> x.slope) // prefer steepest path

  if next.is_empty {
    f.length = 0
    return f.length
  }

  let next = next.first // pick any field that satisfies all properties
  f.next = next
  f.slope = next.slope ?? f.value - next.value
  f.length = 1 + next.length
  return f.length
}

get-path(f: Field): Field generator {
  yield f
  if f.next != null {
    yield from get-path(f.next)
  }
}

let matrix : Array[height, Array[width, Field]] = {
  { Field(1), ... },
  ...,
}

// evaluate length for each field in matrix
// and keep track of longest paths

let mut longest = List()
let mut length = 0

for f in matrix {
  let l = get-lengh(f)
  if l > length {
    length = get-length(f)
    longest = List(f)
  }
  else if l == length {
    longest.add(f)
  }
}

// print out longest paths
for start in longest {
  println(List(get-path(start)))
}


问:
Is it better to team up with a graphical designer, or to piece out design work to a contractor?
I am clueless when it comes to graphical design but I am proficient in programming. If you are a programmer who lacks visual design skills, what has worked best for you -- to pair up with a graphic designer or to do all the programming and then piece out specific work?

I have done some piecing out of work but I am not completely satisfied because I see too much of my influence come out in the design.  I guess this happens since I have to be explicit in what I want with contractors, and they are limited in creativity by the architecture I have created.

It feels like having a partner would allow for greater collaboration, but I have read plenty of entrepreneur books that warn against partnerships.

答:
If you are a programmer who lacks visual design skills, what has
  worked best for you -- to pair up with a graphic designer or to do all
  the programming and then piece out specific work?

I worked as an indy dev for a long time before company work and I recommend the latter if you are on a tight budget and schedule and need to ship.

The trouble is that working with a designer upfront is ideal, but the collaboration overhead can be enormous, especially if they are great designers. Great designers will obsess over every detail, except their designs often won't communicate every detail down to every last function. You can end up having to read between the lines for all the mock-ups, and it starts to become unclear who the actual designer is when it comes to those subtle yet very important workflow decisions.

Working with Designers Upfront

A tricky thing that can occur is that you might get a designer who makes this beautiful, final-product-looking mockup rendered meticulously in Photoshop, e.g. It's good to actually avoid those types or at least train them upfront.

The problem in those cases is that you can end up spending all your time trying to make a drop shadow or a button bevel/rounding or font antialiasing match the look of Photoshop, e.g.

Ideally both your software design and the designer's graphic design evolve together, so it's great if you start with a designer upfront to have the designer keep his designs very loosy, sketchy, like "scribbled on a napkin" kind of loose. It needs to be highly collaborative, and ever more so in the very beginning. Both you and the designer have to be willing to evolve your designs and deviate quite a bit from the beginning "sketch", and there needs to be a very strong emphasis on "loose sketch".

It's also good to establish some constraints upfront so that you aren't trying to match the rendering capabilities of Photoshop or Illustrator, e.g. For whatever GUI toolkit you're using, you want to pay attention to its practical rendering capabilities, how it looks, and train the designer to make his designs match the capability (and even the encouraged usage/layouts) of your GUI kit.

If you're fighting the GUI kit to try to get your designs to match, either you need to train the designer of the system constraints more upfront or ditch the GUI kit and possibly even roll your own if you really want to get a perfect match. Ideally the designer actually sketches his design inside the GUI kit, but that may or may not be practical depending on your tools.

Working with Designers Late

I guess this happens since I have to be explicit in what I want with
  contractors, and they are limited in creativity by the architecture I
  have created.

This is not necessarily a bad thing. A great designer can make fantastic things out of tight constraints. Sometimes they even do better with tight constraints, like the sprite designers for Super Nintendo, Ridley Scott when he made Alien, etc. I actually would recommend this route if you are short on time/budget, and not be disappointed to see a lot of your imprint in the design.

Third Option: Develop Your Design Skills

I'm a horrid UI designer but I'm not a very wealthy programmer and never had the money to afford a UI designer.

Also my company experience didn't give me a good impression as to the cost (time and money-wise) to work with a dedicated one (even after going through several designers over a decade of time), though everyone's mileage may vary. It seems some people here have had great experiences working with designers so it may have just been that company setting (all the programmers hated working with the designers there and saw it largely as spending extraneous amounts of time on fussy details).

So I always tried to develop my design skills a little bit. An example of one of my little apps:

It got some nice responses as to the design, though that may be users just flattering me, and also because this application is a bit technical (visual programming with audio and images and video). Hopefully I didn't embarrass myself too much just there (I think it's reasonable but it might just be "programmer art").

If that doesn't look too horrible, I find the key is just to work with my limited design skills. Since I'm so horrible at it, I use minimal palettes, like some dark grey with no more than two or three main colors for selection highlights and things like that, take it easy on the gradients, use menus and stuff instead of lots of fancy dialogs, but don't make them scroll when possible. Basically I'm doing everything I can to hide the fact that I don't know what the heck I'm doing.

Usually when I see developer designs that seem really gross (not just to my eyes but to pretty much everyone), the programmers are probably no worse than me at design and very possibly much better but just too ambitious. They're putting fancy gradients all over the place, trying to make a very colorful design -- and that takes a lot of skill to get right. It's easier to kind of make a subdued design with a careful selection of a handful of colors to make things pop out, and that takes little design skill at all.

It's all organization as I see it. My designs might not actually look good but they're kind of tied with the functionality, and I focus on the things I can easily focus on as a programmer like keeping everything responsive, fast, low-memory, stutter-free. It seems to get a positive response, but I dunno.

Another thing is that if you work on an application where there's like a main focus area like a canvas or viewport or something, people are surprisingly generous with an incredibly minimalistic design here. Below I just kept it to menus and dialogs all the way and the users at least didn't seem to hate it even though there's not much of a "design" here at all (just a "start"-style menu and top-level menus and some basic popup dialogs that can be docked):

Here I really hid the fact that I don't know what I'm doing by just decorating the viewport with basic menus and stuff, but the artwork in the center makes it look kinda interesting without my "design intervention". So you can really, really subdue the design in those cases and let the beauty of the user's work pop out.

... It's not that hard to design a software that might at least fare reasonably well with an indy audience. I usually don't compete with big companies when I'm solo, so maybe people are just giving me a lot of leeway with my designs. Yet I think it's worth kind of developing your design skills a little teeny bit, if only to better communicate your intentions with the designer. I might have just made a jackass out of myself with these above images, but if not and they're not too bad, I found it takes no formal training or time at all to make these kinds of basic designs. All we need is restraint.


问:
Should I be using advanced techniques most of the time at my new job just because I can?
Simply put I'm new to the company, should I rather write advanced techniques with things like templates, std techniques..etc to make a first good impression and have my colleagues trust/be impressed at my work or should I be more concerned in writing more solid/based standard code for each current problem to be solved?

答:
It's easy to say, "No. Don't do that," or "just write maintainable code." It's easy to assume that any programmer in their right mind will gravitate toward the same obvious, simple, beautiful solution. But I'm here to tell you that's nonsense. The complexity (if we can call it that) of any project is determined by some hard-to-define dynamic including institutional culture, programming language culture, individual tastes, community tastes, and the changes in all of those things over time. Put simply, what's obvious today wasn't obvious yesterday and won't be obvious tomorrow. To me, that means the obvious way of doing things isn't.

In way of illustration, take a practice like DI. When I first started working on big projects, DI didn't exist. Then suddenly it was everywhere. I was confused. Why add a layer of indirection to straight-forward code? Where before it was easy to follow dependencies from implementation to implementation to implementation, now I had to navigate to an interface and figure out which concrete implementation I was dealing with. It wasn't obvious. But... it had its benefits. It made testing easier and, with a little luck, created a shift in thinking that made testing a primary concern. So, I like DI. But to say it's obvious and simple is a half-truth. It's obvious and simple given certain goals (testability, programming to an interface) but it's not obvious and simple to a new programmer.

As a less enterprise-y example, look at the Lua source code versus Linux kernel code. Both projects are very concerned with simplicity and performance and yet both projects look very, very different. How can that be if all good programmers arrive at the same simple solution? (I assure you that both projects enjoy the efforts of excellent programmers. Personally, I find the Lua source inspiring and delightful.)

What this means for you is that it's impossible for us to say if you should or shouldn't use "advanced" techniques. It really depends on your team and on your project. What's advanced for one team isn't for another. Pay close attention during code review. (You have code reviews, right?) If a team member or two comments that your code is a little complicated, process their feedback and try to make your code "locally idiomatic". If you're doing it right, it should be hard to tell who wrote which code in a project. Blend in. If that doesn't feel right, (it happens) maybe the project or team isn't for you.


问:
Do Virtual Machines (for execution of PL) operate on one contiguous array for their bytecode?
I have been reading every now and then on the virtual machines of programming languages like Java, Python and Lua. They all have a notion of bytecode, into which the source code is translated and that is excutable on a virtual machine (register or stack based).

Now on an x86 architecture, all code resides in RAM which is addressable using the CPU's address space. An instruction pointer register points to the position in memory that is currently executed. Jumps modify this instruction pointer register, but basically software in memory is linearized into one piece of RAM.

With Virtual Machines, I am not so certain. Before executing the virtual machine, is all bytecode copied/linked together into a contiguous array with all instructions? Or does the VM keep various modules in different bytecode pages that are swapped/exchanged as needed?

答:
Most VMs do not put all instructions into a single array, for various reasons:

Instructions might not have constant size, so a piece of memory might not be interpreted as a C-like array of instructions. OK, that's a bit pedantic. However, there are interpreters that don't use a sequence of opcodes, but a graph that's traversed during evaluation.

It's most sensible to have one bytecode structure per function or method. This makes it easy to attach metadata to a function, which makes debugging significantly easier. I've seen various approaches to this: there might be a metadata instruction that's otherwise a no-op, or a function might be represented as some object that contains a bytecode structure among other fields.

Using separate bytecode structures affords us more safety. If my VM contains a bug and doesn't stop at the end of the code unit, I might have an arbitrary code execution vulnerability. But if I have clear bounds for my bytecode structure, it's easier to detect when something is off. This is especially important if the VM allows jumps/gotos but wants to restrict them to inside the current function.

Most VMs support runtime loading of more code. This code has to be placed somewhere, and has to be made accessible to the rest of the code. Even more fun, some languages allow runtime code generation. That gets difficult if I have to fit that into a single non-growable array.


问:
How to prevent user from requesting API method multiple times in parallel?
Let's say we have an app where the users gain points and can exchange them for rewards. The exchange request, in pseudo-code, could look like this:

```<code>function exchangePointsForReward(userId, rewardId){
    user = getUser(userId)
    reward = getReward(rewardId)
    if (user.points >= reward.requiredPoints){
        giveRewardToUser(userId, rewardId)
        reduceUserPoints(userId, reward.requiredPoints)
    }
}
</code>```

But if we have a malicious user what stops them from crafting a request in their favorite programming language and sending it 20 times at the same time? Before the first request reaches reduceUserPoints() ten other might've already got as far as addNewReward(). Sure, the user's points at the end of the day might go deep into negative, but what stops the user from quickly grabbing the rewards and using them up? How can I ensure that only one operation can be executed for a user at the same time?

One solution I can think of is the operation tries to acquire a lock at the beginning of the operation and only a single lockable operation can run for a user at any moment:

```<code>function aquireLock(userId){
    lockId = getRandomLockId()
    database.query("UPDATE user SET lock={lockId} WHERE user={userId} AND lock IS NULL");
    return database.query("SELECT lock WHERE user = {userId}").first === lockId;
}

function exchangePointsForReward(userId, rewardId){
    if (!aquireLock(userId)){
        throw new Error("Failed to acquire lock");
    }
    user = getUser(userId)
    reward = getReward(rewardId)
    if (user.points >= reward.requiredPoints){
        giveRewardToUser(userId, rewardId)
        reduceUserPoints(userId, reward.requiredPoints)
    }
    releaseLock(userId);
}
</code>```

But is there any better strategy here? The question is database-agnostic.

答:
You can make reduceUserPoints check if the result would become negative and fail if so.

```<code>function exchangePointsForReward(userId, rewardId){
    user = getUser(userId)
    reward = getReward(rewardId)
    try{
        reduceUserPoints(userId, reward.requiredPoints) //throws if result would become negative
        giveRewardToUser(userId, rewardId)
    }catch(){
        //show error message to user
    }
}
</code>```

Key here is that the check gets rolled into the reduceUserPoints.

Another option is to use transactions that will give you the proper isolation and locking automatically.

Body:
You can make reduceUserPoints check if the result would become negative and fail if so.

function exchangePointsForReward(userId, rewardId){
    user = getUser(userId)
    reward = getReward(rewardId)
    try{
        reduceUserPoints(userId, reward.requiredPoints) //throws if result would become negative
        giveRewardToUser(userId, rewardId)
    }catch(){
        //show error message to user
    }
}

Key here is that the check gets rolled into the reduceUserPoints.

Another option is to use transactions that will give you the proper isolation and locking automatically.


答:
I think your locking strategy will work, although I'd suggest looking at a distributed lock manager (e.g., Apache's Helix project) instead of going to the database just to get a lock. This would ensure that users didn't get locked out if your service gets restarted mid-request.

Another possibility would be to bucket the user IDs to queue them to specific request handlers; this would serialize the parallel requests, but is probably more complicated and could lead to processing bottlenecks (at least until you got your configuration tuned).

Title: How to prevent user from requesting API method multiple times in parallel?

Body:
Let's say we have an app where the users gain points and can exchange them for rewards. The exchange request, in pseudo-code, could look like this:

```<code>function exchangePointsForReward(userId, rewardId){
    user = getUser(userId)
    reward = getReward(rewardId)
    if (user.points >= reward.requiredPoints){
        giveRewardToUser(userId, rewardId)
        reduceUserPoints(userId, reward.requiredPoints)
    }
}
</code>```

But if we have a malicious user what stops them from crafting a request in their favorite programming language and sending it 20 times at the same time? Before the first request reaches reduceUserPoints() ten other might've already got as far as addNewReward(). Sure, the user's points at the end of the day might go deep into negative, but what stops the user from quickly grabbing the rewards and using them up? How can I ensure that only one operation can be executed for a user at the same time?

One solution I can think of is the operation tries to acquire a lock at the beginning of the operation and only a single lockable operation can run for a user at any moment:

```<code>function aquireLock(userId){
    lockId = getRandomLockId()
    database.query("UPDATE user SET lock={lockId} WHERE user={userId} AND lock IS NULL");
    return database.query("SELECT lock WHERE user = {userId}").first === lockId;
}

function exchangePointsForReward(userId, rewardId){
    if (!aquireLock(userId)){
        throw new Error("Failed to acquire lock");
    }
    user = getUser(userId)
    reward = getReward(rewardId)
    if (user.points >= reward.requiredPoints){
        giveRewardToUser(userId, rewardId)
        reduceUserPoints(userId, reward.requiredPoints)
    }
    releaseLock(userId);
}
</code>```

But is there any better strategy here? The question is database-agnostic.


问:
At what point in the process do you create the visual design?
I like to do a wireframe before I start coding and work from there. But when should I start worrying about the visual design? When should I consider the colours, the font, whether corners should be round or sharp, icon design, etc?

Is that the last thing to do before launch? Or is there any reason to work on it while you're still in the coding phase, or testing and debugging phase?

答:
If you're working solo and doing everything yourself, I'm actually going to suggest sort of the opposite of the popular route (if only to complement  Aaronaught's fine answer).

And I actually recommend doing like 75% or more of the GUI work for your application sort of upfront, earlier (but post architectural conception), kind of stub things in there, pseudo-RAD style. You don't have to get to the meticulous details like fonts and stuff, and can keep the icons using stock graphics or just labels like "X". It's more about a sense of UI "completeness" than beauty. Maybe I would say, "very incomplete" from an aesthetic aspect, but mostly complete in terms of having all the major UI elements there.

SE vs. Psychology

The main reason is not software engineering discipline. This is actually quite a violation of it. It makes the most sense from an SE standpoint to prioritize the stable designs (high efferent couplings, low afferent couplings, when UIs tend to be among the most unstable designs).

The SE formula to prioritize stable designs is ideal for redoing the least amount of work as you progress, since UI frontends depend on backend, but not the other way around. If we had a fully-established frontend first, we might have to keep changing its code as the backend changes while we're finding some unanticipated needs for design changes here and there.

But there's just a morale/motivation/human psychology aspect to it. If you're like me, the hardest thing about working solo and not having the pressure of the company is just staying self-motivated. I have my little slumps.

It's hard to stay motivated if, after 2 months of coding, your application looks like a raw skeleton from the UI level and none of your kind of internal test users understand what they're even looking at with only screenshots of console outputs and very barebones UI.

If you're like me, my notion of "software progress" is unfortunately not too unlike the naive user, judging the progress of the application by how finished the UI looks. It shouldn't be, as I ideally just have the discipline to measure my progress without looking for that kind of casing, "shell" that decorates the unfinished backend. But I don't do this perfectly, I subconsciously judge things by that front-end as many users do, and I get depressed when that perception is one of slow progress. When it looks promising, it keeps me motivated.

So I actually feel like it's easier from a self-motivation standpoint to kind of get that GUI established upfront (but not little details, just the overall idea).

The other reason I like this is that, counter-intutively, I tend to do a lot more juggling of the UI and backend when I'm trying to do it the more formal SE way. Even though I've tried this hardcore SE prioritization strategy where I tried to do the minimal work for the UI, I found myself constantly doing a little bit of it here and there with the UI inching in progress a little bit each day, and the time added up. By getting the bulk of it out of the way upfront, you can go in long bursts filling in your application's functionality and start measuring progress by what things stubbed into the UI are left to implement. There might be some backend changes that require you to change the front-end you established upfront -- there's always interruptions like that, but overall I found myself juggling the UI code less (YMMV).

The UI starts to become like an implicit "todo" list in this case (though not an excuse to avoid having an external one as well).

The only problem with this is that the UI design tends to drive the
  backend design, which is usually not what you want. If you find that
  your backend work is driving the UI design, you need better decoupling
  (i.e. View Models).

From Robert, I very much agree. It's kind of a blur to me always when working on my own. I apply a strict adherence of the MVC, but a trouble I always found is that the model can become very complete while the view is so rough, or I'm trying to evolve them together and juggling a lot.

It may also be a bit unique to my situation. I work in areas like games and audio and kind of "visual applications" where my UIs are all proprietary (somewhat of a standard aesthetic in these areas) so I'm rolling all my widgets, async UI thread, event handlers, alpha blitting pixels, rasterizing antialised shapes, font rendering engine, bevel and emboss filters on small graphics, property system with reflection (for MVC), async signals and slots, retina display support etc. all by hand while simultaneously juggling low-level audio processing, image compositing, video filtering, raytracing, localization, mesh algorithms, particle systems, undo system, non-destructive pipeline, scripting engine, SDK, etc. So the "view" part is actually considerably more work than usual in my case. My apps look kind of unusual like this:

In the early stages (first few months) of this project I got really depressed, since I was looking at stuff like this:

... with only one button in that entire sidebar for the paint tab, e.g., and there were times I was just tempted to quit working on the project because the UI looked so incomplete even though a lot of the backend was mature. I started reversing that strategy and seeking a more complete UI in the middle of the project (just buttons and stuff stubbed in to kind of capture the final product's overall UI-level functions) and that really helped my motivation.


问:
Debugging mutually recursive functions
We have a class in which mainly data processing(XML nodes) is done by mainly 3 methods. Now code in itself strictly follows DRY principle. For e.g.

Process Children (reads data from child nodes)

Process Choose Element (conditional data check)

Extract Single Field (extract data from single node with no children)

To give you overview ,Say we reach node A, then we call ProcessChildren() and if any children is  Choose then we would call ProcessChoose(). Then we would call recursively ProcessChildren() result and so worth.
Though this code is easy to read and overall bugs are removed but debugging is very difficult since one functions to another and so on.
Is there any way we could remove this debugging hurdle so that debugging is easy?

答:
Debugging is easy when you don't need it at all.

You have three methods. If each of them is correct, you likely won't need to debug a combination of them.

Split the three methods into smaller parts, each clearly defined. Do this until the correctness of each part is completely obvious, because of its simplicity.

Write unit tests for each method. Cover both correct and incorrect input. Pay attention to corner cases.

You have done this, but you still have trouble understanding what's up?

Maybe debugging by manually stepping through each line is too slow, you lose track of what's happening.

Add large amounts of logging to your methods. Log the arguments passed, all the interesting intermediate state (which you should have as little as possible), maybe some context like neighboring nodes of the XML tree. Make sure line numbers are logged.

Try to use conditional breakpoints, so that the debugger activates only when something interesting is happening.

Chances are that looking at the detailed log would give you a better picture than constantly changing variables in the debugger window.

Title: Debugging mutually recursive functions


问:
How to solve circular dependency?
I have three classes that are circular dependant to each other:

TestExecuter execute requests of TestScenario  and save a report file using ReportGenerator class.
So:

TestExecuter depends on ReportGenerator to generate the report

ReportGenerator depends on TestScenario and on parameters set from TestExecuter.

TestScenario depends on TestExecuter.

Can't figure out how to remove thoses dependencies.

public class TestExecuter {

  ReportGenerator reportGenerator;

  public void getReportGenerator() {
     reportGenerator = ReportGenerator.getInstance();
     reportGenerator.setParams(this.params);
     /* this.params several parameters from TestExecuter class example this.owner */
  }

  public void setTestScenario (TestScenario  ts) {
     reportGenerator.setTestScenario(ts);
  }

  public void saveReport() {
     reportGenerator.saveReport();
  }

  public void executeRequest() {
    /* do things */
  }
}
```

<pre class="lang-java prettyprint-override"><code>public class ReportGenerator{
    public static ReportGenerator getInstance(){}
    public void setParams(String params){}
    public void setTestScenario (TestScenario ts){}
    public void saveReport(){}
}
</code>```

public class TestScenario {

    TestExecuter testExecuter;

    public TestScenario(TestExecuter te) {
        this.testExecuter=te;
    }

    public void execute() {
        testExecuter.executeRequest();
    }
}
```

<pre class="lang-java prettyprint-override"><code>public class Main {
    public static void main(String [] args) {
      TestExecuter te = new TestExecuter();
      TestScenario ts = new TestScenario(te);

      ts.execute();
      te.getReportGenerator();
      te.setTestScenario(ts);
      te.saveReport()
    }
}
</code>```

EDIT: in response to an answer, more details about my TestScenario class:

public class TestScenario {
    private LinkedList<Test> testList;
    TestExecuter testExecuter;

    public TestScenario(TestExecuter te) {
        this.testExecuter=te;
    }

    public void execute() {
        for (Test test: testList) {
            testExecuter.executeRequest(test);
        }
    }
}

public class Test {
  private String testName;
  private String testResult;
}

public class ReportData {
/*shall have all information of the TestScenario including the list of Test */
    }
```

<p>An example of the xml file to be generated in case of a scenario containing two tests:</p>

<pre class="lang-java prettyprint-override"><code><testScenario name="scenario1">
   <test name="test1">
     <result>false</result>
   </test>
   <test name="test1">
     <result>true</result>
   </test>
</testScenario >
</code>```

答:
Since TestExecutor only uses ReportGenerator internally, you should be able to define an interface for it, and refer to the interface in TestScenario. Then TestExecutor depends on ReportGenerator, ReportGenerator depends on TestScenario, and TestScenario depends on ITestExecutor, which doesn't depend on anything.

Ideally you'd be defining interfaces for all your classes and expressing dependencies through them, but this is the smallest change which will solve your problem.

Title: How to solve circular dependency?