答:
First thing is to know the partitions of the number 5 (the team size you want to assembly). There are algorithms to generate the partitions of a number but since the number is small and fixed you don't need to worry about it. The partitions of 5 are: {5}, {4,1}, {3,2}, {3,1,1}, {2,2,1), {2,1,1,1}, and {1,1,1,1,1}.

Make 5 lobby lists (L1,L2,L3,L4,L5). One for each lobby size. Each element will contain:
1) the lobby id
2) the time in queue
3) the sum of the ranks of the players that compose the lobby
L1 is the list of all lobbies of size 1, L2 is the list of all lobbies of size 2 and so on.

Now you make a list T of all possible teams of 5 people that you can assembly from the 5 lists of lobbies. To build that list you loop through the lists L1,...L5 according to the partitions of 5.

```<code>team {
    int partition_type;
    int lobby_index[5]; //each lobby_index value will mean a different thing depending on the value of partition_type
}

team_index = 0

//partition case 0: {5}
for (i5=0; i5<n5; i5++) do
    //in the case of partition_type==0, only the first index is used and it is an index in the list of lobbies of size 5
    Team[team_index++] = new team(partition_type = 0, lobby_index[0] = i5)
end

//partition case 1: {4,1}
for (i4=0; i4<n4; i4++) do
    for (i1=0; i1<n1; i1++) do
        //in the case of partition_type==1, the first index is an index in the list of lobbies of size 4 and the second is an index in the list of size 1
        Team[team_index++] = new team(partition_type = 1, lobby_index[0] = i4, lobby_index[1] = i1)
    end
end

//partition case 2: {3,2}
for (i3=0; i3<n3; i3++) do
    for (i2=0; i2<n2; i2++) do
        Team[team_index++] = new team(partition_type = 2, lobby_index[0] = i3, lobby_index[1] = i2)
    end
end

//partition case 3: {3,1,1}
for (i3=0; i3<n3; i3++) do
    for (i1a=0; i1a<n1-1; i1a++) do // 0 <= i1a < i1b < n1
        for (i1b=i1a+1; i1b<n1; i1b++) do
            Team[team_index++] = new team(partition_type = 3, lobby_index[0] = i3, lobby_index[1] = i1a, lobby_index[2] = i1b)
        end
    end
end

//partition case 4: {2,2,1)
for (i2a=0; i2a<n2-1; i2a++) do  // 0 <= i2a < i2b < n2
    for (i2b=i2a+1; i2b<n2; i2b++) do
        for (i1=0; i1<n1; i1++) do
            Team[team_index++] = new team(partition_type = 4, lobby_index[0] = i2a, lobby_index[1] = i2b, lobby_index[2] = i1)
        end
    end
end

//partition case 5: {2,1,1,1}
for (i2=0; i2<n2; i2++) do
    for (i1a=0; i1a<n1-2; i1a++) do  // 0 <= i1a < i1b < i1c < n1
        for (i1b=i1a+1; i1b<n1-1; i1b++) do
            for (i1c=i1b+1; i1c<n1; i1c++) do
                Team[team_index++] = new team(partition_type = 5,     lobby_index[0] = i2, lobby_index[1] = i1a, lobby_index[2] = i1b, lobby_index[3] = i1c)
            end
        end
    end
end

//partition case 6: {1,1,1,1,1}
for (i1a=0; i1a<n1-4; i1a++) do  // 0 <= i1a < i1b < i1c < i1d < n1
    for (i1b=i1a+1; i1b<n1-3; i1b++) do
        for (i1c=i1b+1; i1c<n1-2; i1c++) do
            for (i1d=i1c+1; i1d<n1-1; i1d++) do
                for (i1e=i1d+1; i1e<n1; i1e++) do
                    Team[team_index++] = new team(partition_type = 6, lobby_index[0] = i1a, lobby_index[1] = i1b, lobby_index[2] = i1c, lobby_index[3] = i1d, lobby_index[4] = i1e))
            end
        end
    end
end
</code>```

To calculate the rank of a Team[30] (just showing one case):

```<code>if Team[30].partition_type==2 then
    i3 = Team[30].lobby_index[0]
    i2 = Team[30].lobby_index[1]
    rank = ( (L3[i3].rank) + (L2[i2].rank) ) / 5
end
</code>```

Have 2 copies of T (or at least make sure you can traverse it in 2 different ways). One ordered by the average rank of that team and the other copy ordered by the average time in queue.

Now traverse the list T ordered by queue times from higher to lower. The first element is the one that has the priority to find a game first because their members are waiting for longer in average. Check the rank average of this team. Now use the rank value you found to determine all the teams that are +/- 1.5 from its rank. This is easily done by using the teams list T copy ordered by ranking. Now you just need to check if any of the teams in the rank range does not include any lobby of the current team (since one lobby can't be in both teams).

If there is such a team them you just found a game (if there are more than one pick then one with highest queue time). Remove all lobbies involved from their lists and recalculate all teams again. If not them get the next team in the list ordered by queue time and test again. Once you traverse all the queue time list you wait until the list of queues change and do all again.

Title: Algorithm and data structure to match groups of users (1-5 each) into 2 balanced sets of 5 users

Body:
I'm building a matchmaking queueing service for a 5v5 team-based game.

I have a large set of users that are grouped into unique lobbies comprised of 1-5 users each. Each user has an integer based rank from 1-16. These ranks will eventually be converted to a trueskill rating, but for now, we're sticking with integers since we're importing the rankings from an existing system that is already quite accurate.

So we have lobbies of up to 5 people, and we want to create balanced matches between 10 people (5v5), combining these various lobbies in a way that is balanced and equivalent to 2 sets of 5 people. Lobbies can't be split up and the rank differential between users in a lobby can't exceed 4.

I can design the data structure in any way. Currently, I have a hash object of lobbies and a hash object of users that refer to each other.

I'm not looking for code, or even necessarily pseudocode. I'm just looking for a place to start. I'm a little lost on how I can efficiently and properly combine lobbies of various sizes into 5v5 matches, while ensuring that those two teams are sufficiently balanced in ranks (+-1.5 ranks).

Body:
First thing is to know the partitions of the number 5 (the team size you want to assembly). There are algorithms to generate the partitions of a number but since the number is small and fixed you don't need to worry about it. The partitions of 5 are: {5}, {4,1}, {3,2}, {3,1,1}, {2,2,1), {2,1,1,1}, and {1,1,1,1,1}.

Make 5 lobby lists (L1,L2,L3,L4,L5). One for each lobby size. Each element will contain:
1) the lobby id
2) the time in queue
3) the sum of the ranks of the players that compose the lobby
L1 is the list of all lobbies of size 1, L2 is the list of all lobbies of size 2 and so on.

Now you make a list T of all possible teams of 5 people that you can assembly from the 5 lists of lobbies. To build that list you loop through the lists L1,...L5 according to the partitions of 5.

team {
    int partition_type;
    int lobby_index[5]; //each lobby_index value will mean a different thing depending on the value of partition_type
}

team_index = 0

//partition case 0: {5}
for (i5=0; i5<n5; i5++) do
    //in the case of partition_type==0, only the first index is used and it is an index in the list of lobbies of size 5
    Team[team_index++] = new team(partition_type = 0, lobby_index[0] = i5)
end

//partition case 1: {4,1}
for (i4=0; i4<n4; i4++) do
    for (i1=0; i1<n1; i1++) do
        //in the case of partition_type==1, the first index is an index in the list of lobbies of size 4 and the second is an index in the list of size 1
        Team[team_index++] = new team(partition_type = 1, lobby_index[0] = i4, lobby_index[1] = i1)
    end
end

//partition case 2: {3,2}
for (i3=0; i3<n3; i3++) do
    for (i2=0; i2<n2; i2++) do
        Team[team_index++] = new team(partition_type = 2, lobby_index[0] = i3, lobby_index[1] = i2)
    end
end

//partition case 3: {3,1,1}
for (i3=0; i3<n3; i3++) do
    for (i1a=0; i1a<n1-1; i1a++) do // 0 <= i1a < i1b < n1
        for (i1b=i1a+1; i1b<n1; i1b++) do
            Team[team_index++] = new team(partition_type = 3, lobby_index[0] = i3, lobby_index[1] = i1a, lobby_index[2] = i1b)
        end
    end
end

//partition case 4: {2,2,1)
for (i2a=0; i2a<n2-1; i2a++) do  // 0 <= i2a < i2b < n2
    for (i2b=i2a+1; i2b<n2; i2b++) do
        for (i1=0; i1<n1; i1++) do
            Team[team_index++] = new team(partition_type = 4, lobby_index[0] = i2a, lobby_index[1] = i2b, lobby_index[2] = i1)
        end
    end
end

//partition case 5: {2,1,1,1}
for (i2=0; i2<n2; i2++) do
    for (i1a=0; i1a<n1-2; i1a++) do  // 0 <= i1a < i1b < i1c < n1
        for (i1b=i1a+1; i1b<n1-1; i1b++) do
            for (i1c=i1b+1; i1c<n1; i1c++) do
                Team[team_index++] = new team(partition_type = 5,     lobby_index[0] = i2, lobby_index[1] = i1a, lobby_index[2] = i1b, lobby_index[3] = i1c)
            end
        end
    end
end

//partition case 6: {1,1,1,1,1}
for (i1a=0; i1a<n1-4; i1a++) do  // 0 <= i1a < i1b < i1c < i1d < n1
    for (i1b=i1a+1; i1b<n1-3; i1b++) do
        for (i1c=i1b+1; i1c<n1-2; i1c++) do
            for (i1d=i1c+1; i1d<n1-1; i1d++) do
                for (i1e=i1d+1; i1e<n1; i1e++) do
                    Team[team_index++] = new team(partition_type = 6, lobby_index[0] = i1a, lobby_index[1] = i1b, lobby_index[2] = i1c, lobby_index[3] = i1d, lobby_index[4] = i1e))
            end
        end
    end
end

To calculate the rank of a Team[30] (just showing one case):

if Team[30].partition_type==2 then
    i3 = Team[30].lobby_index[0]
    i2 = Team[30].lobby_index[1]
    rank = ( (L3[i3].rank) + (L2[i2].rank) ) / 5
end

Have 2 copies of T (or at least make sure you can traverse it in 2 different ways). One ordered by the average rank of that team and the other copy ordered by the average time in queue.

Now traverse the list T ordered by queue times from higher to lower. The first element is the one that has the priority to find a game first because their members are waiting for longer in average. Check the rank average of this team. Now use the rank value you found to determine all the teams that are +/- 1.5 from its rank. This is easily done by using the teams list T copy ordered by ranking. Now you just need to check if any of the teams in the rank range does not include any lobby of the current team (since one lobby can't be in both teams).

If there is such a team them you just found a game (if there are more than one pick then one with highest queue time). Remove all lobbies involved from their lists and recalculate all teams again. If not them get the next team in the list ordered by queue time and test again. Once you traverse all the queue time list you wait until the list of queues change and do all again.


问:
Functional programming and Text adventures
This is mostly a theoretical question about FP, but I'll take text adventures (like old-school Zork) to illustrate my point. I'd like to know your opinions on how would you model a stateful simulation with FP.

Text adventures really seem to call for OOP. For example, all the "rooms" are instances of a Room class, you can have a basic Item class and interfaces like Item<Pickable> for things you can carry and so on.

World modeling in FP works differently, especially if you want to enforce immutability in a world that must mutate as the game progresses (objects are moved, enemies are defeated, the scoring grows, the player changes its location). I imagine a single big object World that has it all: what are the rooms you can explore, how they are linked, what the player is carrying, what levers have been triggered.

I think that a pure approach would be to basically pass this big object to any function and have it returned by them (possibly modified). For example, i have a moveToRoom function that gets World and returns it with World.player.location changed to the new room, World.rooms[new_room].visited = True and so on.

Even if this is the more "correct" way, it seems to be enforcing pureness for the sake of it. Depending on the programming language, passing this potentially very big World object back and forth may be expensive. Also, every function may need to have access to any World object. For example, a room may be accessible or not depending on a lever triggered in another room because it may be flooded, but if the player carries a life jacket, it can enter it anyway. A monster may be aggressive or not depending on whether the player has slayered his cousin in another room . This means that the roomCanBeEntered function needs to access World.player.invetory and World.rooms, describeMonster needs to access World.monsters and so on (basically, you must pass the whole load around). This really seems to me to call for a global variable, even if this is all but good programming style especially in FP.

How would you solve this problem?

答:
The real solution is not by collecting everything to a big World object, and then passing it around. Instead, you're recommended to accurately specify the type of the function you're dealing with. Here's some examples:

```<code>BAD:
   f :: (World, Int) -> World

Good:
   f :: (Int,Int,Int,Int) -> World
</code>```

The bad example is trying to modify existing object, but the good example is trying to create a world from the state space your game has. Basically, to create a world, you need to know all the data that is required to select the correct world.

ContentLicense: CC BY-SA 3.0

Body:
The real solution is not by collecting everything to a big World object, and then passing it around. Instead, you're recommended to accurately specify the type of the function you're dealing with. Here's some examples:

BAD:
   f :: (World, Int) -> World

Good:
   f :: (Int,Int,Int,Int) -> World

The bad example is trying to modify existing object, but the good example is trying to create a world from the state space your game has. Basically, to create a world, you need to know all the data that is required to select the correct world.


问:
Code review and testing in the process
I am thinking about the software development process of my team, more specifically, I am thinking about tests and  code review into our development process.
I came to the conclusion that, in order to validate a development task, the development done has to be tested by one tester, and the code has to be reviewed, either by me or by another developer.

I don't see any difference between reviewing the code first or testing it first, if any validation fails, the task has to be modified, and therefore re-tested, and re-reviewed. That's why I would like that once a task has been finished by a developer, it can be assigned to both a tester and a reviewer, and everyone can do their part of the validation when they have time.

However, in our tool (Jira), we can only have one status (like IN TEST) for a task and one assignee (the tester), but we cannot have two status IN TEST & PENDING REVIEW with one assignee for each. Therefore, here are my two questions :

Is there any drawback to assigning two different person at the same time to validate the same task? It looks strange to me that Jira doesn't allow this to be done if it is a good practice.

If you consider it as a valid process, how can I implement it into Jira in a simple way?

答:
There is one drawback:

Assigning both tasks in parallel (to two different people) may result in wasted effort, if both end up working in parallel (and reject the change).

Consider (measure) how much the two kinds of tasks cost, and how likely they are to result in further changes before acceptance.  With those numbers available, you can estimate if it clearly makes sense to schedule one of the two tasks first, and the other one only if the first is passed.

Title: Code review and testing in the process


问:
JEE MVC, controller calls the interface instead of the interface implementation
I'm following this tutorial: http://wiki4.caucho.com/Building_a_simple_listing_in_JSP It creates a basic web application in Eclipse using the MVC pattern with Resin as the web container.  Here's the part I don't understand.

For the model, it creates a POJO, Interface and Interface Implementation. The data represents a Book.  When we get to the controller, it creates a simple servlet. It calls the interface instead of the interface implementation. How does the interface to execute the implementation class?  Also what if there were two impl classes, how would the interface know which to call?

答:
The controller has a variable that can have a reference to any object of the interface type. The interface implementation class you speak of implements the interface, therefore it is a type of that interface.

This means that variable can have a reference to an object of that class.

This tutorial utilizes CDI which is something called a Dependency Injection framework. This allows you to configure beans in your application that automatically are instantiated and assigned to properties (variables like the one of type interface) for use by other beans. It is creating the object of the interface implementation class and adding it to your controller for you.


问:
How is a state machine different from any other computer program?
I have seen several implementations of "State Machines" on github. As far as I understand, a state machine takes input that may or may not transform its state into one of a finite set of other states. How is that different from any other computer program?</p>

答:
From a theoretical point of view, it's not different at all. Of course, from a theoretical point of view you can write any program in assembly language and it'll work just as well.

While the computer your code is running on may be mathematically equivalent to a very, very complicated state machine, as is any other program that runs on any other computer, there are many problems whose most elegant solution is a simple finite state machine whose states and transitions have domain-specific meanings that the programmer came up with (as opposed to the compiler or the hardware designer).

For instance, one classic way of implementing regular expressions is to interpret the regular expression as a specification for a finite state machine, build such a machine, then feed it strings to accept or reject. More generally, any time you want an object in your program to always have one of a finite number of states, and enforce that transitions between those states always happen in specific ways, building a state machine might be the most elegant solution.


答:
If you want to be really pedantic, every computer program is a Finite State Machine, because even if you convert all matter in the entire universe into a computer, it will still only have finite memory, thus a finite amount of states, and a finite amount of transitions between those states.

State Machines are models, just like Lambda Calculus, Turing Machines, Random-Access Machines, Actor Systems, Object Systems, and so on. Some problems lend themselves to being modeled by a state machine, some don't.

Business Processes were often modeled as State Machines even before computers existed. They lend themselves naturally to that kind of thinking.

Title: How is a state machine different from any other computer program?

Body: I have seen several implementations of "State Machines" on github. As far as I understand, a state machine takes input that may or may not transform its state into one of a finite set of other states. How is that different from any other computer program?</p>


问:
How to use Guice for an effective API Design?
I am creating a base API in JavaSE, which includes modules like MVP architecture, Service & Repository Layer, Event Model to fire events between presenter etc.

I am trying to implement all best practices of Software Design. Recently, I read about Dependency Injection & its advantages and decided to use Guice as DI framework.

After spending two days learning Guice, I am still confused with some design issues.

If I create an injector using Guice.createInjector(modules) with the core modules of my API,

How to make this injector instance available to my other API classes? Can an injector be injected and is it a good practice?

How to make this injector instance available to API user, so that they can use this injector to create instances?

Should I even make it available to API user, as it may be a bad practice?

Hence using it for AOP approach like this and custom injections

Is creating injectors a heavyweight operation, if so should there be only a few injectors per application?

Should injectors be created on startup stage of the application or could be created in between without affecting the application performance?

Edit

To understand usage of Provider instead of injecting injector here is an short MVP example:

```<code>interface ProductModel {

  // Some method declarations

}

interface ProductView {

  // Some method declarations

}

class ProductPresenter {

  // Using Guice for constructor injection
  @Inject
  ProductPresenter(ProductModel model, ProductView view) {
    this.model = model;
    this.view = view;
  }

}

class ProductViewImpl implements ProductView {

  // Method Implementations

}

class ProductModelImpl implements ProductModel {

  // Method Implementations

}
</code>```

Now, as understood from below answers to use Provider<X> instead of injecting injector, here is the Provider class.

```<code>class ProductPresenterProvider implements Provider<ProductPresenter> {

  ProductPresenter get() {
    // But, How to provide the ProductPresenter without model and view instances!
  }

}
</code>```

答:
Ok, those are many questions you have and I guess some of the points can be approached in more than one way.

Creating the injector is not cheap. Guice will do some analysis to detect errors as well as create all singletons. So you should create the injector at startup.

I usually have a single injector for my application.

Regarding your question 1.:

Yes the injector can be injected. But I see it as a bad practice. Reason for this is that calls to injector.getInstance() and injector.injectMembers() make it hard to reason about the dependencies of a class.

if you need to create more than one instance or you need to control the time when an instance is created inject a Provider instead of X.

if the object you want to create needs both runtime parameters and dependencies use assisted inject.

for many kinds of objects (like DTO, POJO and alike) its absolutely ok to create them by calling new or a conventional factory.

In this sense the injector is implicitly available to any instance created by Guice this includes the API user.

And finally AOP.
Aspects are a powerful feature but also can hide some of the business logic I suggest to use them only for very repetitive tasks which all developers know well.

Also take into account that aspects only work on:

instances created by Guice

non private, non static, non private methods

Finally, Guice won't inform you if you add an annotation to either of the above. Your aspect will silently be ignored


答:
As the other answers pointed out, there is nothing special about state machines. However, it is frequently beneficial to explicitly state that our program implements a FSM.

Programming consists to a good deal of finding suitable abstractions for a problem. Using an abstraction implies speaking in terms of the abstraction rather than in terms of the implementation. Many processes are inherently stateful, for example the sign-up process on a website, or the check-out process in an e-commerce application. If I were to model those processes, I would draw boxes connected by arrows onto a whiteboard – a state diagram. Here, a state machine would be a kind of design pattern and talking about state machines would clearly communicate my intent to colleagues.

Imperative programs are inherently stateful so we don't always notice when we introduce state. E.g. in the C language, certain language constructs such as the semicolon operator mark a “sequence point”, which is a state transition and enforces ordering between operations. Things are different in environments such as pure functional languages such as Haskell or when using stateless protocols such as HTTP. Suddenly, any state must become explicit, and explicitly phrasing our design as a state machine can make it more manageable.

Finite state machines play an important role in parsing, since they correspond to regular expressions. Manually implementing some regular expression can result in extremely hairy code, which at its worst isn't even correct. When we realize that we are implementing a state machine, we can use a variety of known implementation techniques to help us. For example, we could make the state explicit and store the current state in a variable. Alternatively, we can make the state implicit through control flow on our language. I have done both in different circumstances, but stating that we are implementing a state machine (which features restricted state transitions, a start state, known end states, no recursion, and no implicit state through persistent data allocation) rather than an unrestricted program makes it easier to implement and understand.

I would rarely use a state machine library, since all programming languages I know make it easy to correctly and efficiently express a state machine in that language. But there are exceptions: while deterministic automata are easy to implement, nondeterministic automata are fairly nontrivial, since the state machine may be in multiple states at the same time. Using a library that implements NFAs or rewrites them lets me ignore these difficulties and focus on stuff that actually matters.

Beyond the uses of state machines as a design and state machines in computer science and language theory, there aren't really that many uses. Stateful logic circuits come to mind. The main use of state machines for a programmer is learning to think in terms of states and state transitions. Where does my program have implicit states? Did I correctly implement all state transitions? Did I miss something and open up an invalid state? Such thinking becomes especially relevant again in object-oriented programming, since the member fields of an object correspond to state, and methods may effect state transitions. I would hesitate to explicitly implement a state machine in an object, but a state machine can nevertheless be a suitable mental model for the behaviour.

The main reason to write a state machine library is to make sure you've understood the topic, but in most applications you would not need them or rather hand-roll them.


问:
Loops to create nested loops
Is there a way to use a loop to create more nested loops? E.g. Doing this

```<code>for (int i = 0; i < iterations; i++)
            {
                //Do stuff
                for (int ii = 0; ii < iterations; ii++)
                {
                    // Do stuff
                    for (int iii = 0; iii < iterations; iii++)
                    {
                        //Do Stuff
                    }
                }
            }
</code>```

but allowing the user to change how many nested loops you want during run-time.

This allows me to know the depth I am on, while also resetting the "i" counter back to 0, allowing me to do the exact same thing over again, but with a different depth value.

答:
There is a way! You can solve such problems with recursion (https://en.wikipedia.org/wiki/Recursion_%28computer_science%29).

In your case it would look something like this (pseudocode):

```<code>function doStuff(int depth) {
    if(depth > USER_DEFINED_DEPTH)
        return;
    //Do stuff
    doStuff(depth + 1);
}

doStuff(0);
</code>```

Title: Loops to create nested loops

Body:
There is a way! You can solve such problems with recursion (https://en.wikipedia.org/wiki/Recursion_%28computer_science%29).

In your case it would look something like this (pseudocode):

function doStuff(int depth) {
    if(depth > USER_DEFINED_DEPTH)
        return;
    //Do stuff
    doStuff(depth + 1);
}

doStuff(0);


问:
shared or raw pointer c++
I am developing a noSQL database and currently moving the code from C to C++.

It have class Pair, which contains a raw pointer to a memory blob.

```<code>class Pair {
  Blob* blob;
  ...
};
</code>```

Then if you add this Pair to the List class, the List class stores this raw pointer internally, without copying. In order not to leak memory, the List notifies the Pair not to delete the raw pointer.

```<code>class Pair {
  Blob* _blob;
  bool _owns_blob;

public:
  Pair(Blob* blob, bool owns_blob = true)
    : _blob(blob), _owns_blob(owns_blob) {}
  ~Pair() { if (_owns_blob) delete _blob; }
  ...
  Blob* blob() { return _blob; }
  void disown() { _owns_blob = false; }
};

void List::put(Pair& p) {
  store_blob(p.blob());
  p.disown();
}
</code>```

Because of this notification, I can not use a method signature like this:

```<code>List.put(const Pair &p)
</code>```

and I will need to pass by value or by non-const reference.

Later if you request the data, the program creates a new Pair and includes the raw pointer inside, and also instructs the Pair not to delete the pointer:

```<code>Pair List::get(...) {
  return Pair(get_blob(), false);
}
</code>```

Would this model benefit from shared pointers? How would this affect the speed and memory consumption?

答:
I'm no C++-Expert, but in the last days I did some research around "smart" pointers, so maybe I can help you:

Shared pointers may help you in this situation, but they may be just a too easy way out of a situation where it is not too clear in the first place who the data really belongs to. Accessing a shared pointer is cheap, but copying it has a small penalty since there has to be some reference counting to be done in the background.

If you are programming in c++11, try redesign your classes (if possible) using unique_ptr with move semantics which come at no overhead.

Title: shared or raw pointer c++


答:
It's a bad practice to inject an injector, or otherwise pass it round in some way that makes it accessible to code outside of startup. That confuses what's going on; do that and when something goes wrong, you have to debug your code via debugging the dependency injection state.

The right, static, way to do things is to inject either a hand-written factory object, or a Provider. The difference being that the latter will set the created object up as a DI object, i.e. processing @Inject annotations.

Internally, the implementation of a provider presumably uses the injector, but as it is only doing it for a single thing it is easier to reason about and debug. And if you draw the dependency graph for your system, because Provider is Provider<X>, you should get the actual graph of logical dependencies with your class depending on X. Not a mess with a 'magic happens' node at a single injector used for everything.

Note that when you do this, you don't need to supply a binding or implementation for the Provider; it has built-in default.

Title: How to use Guice for an effective API Design?

Body:
I am creating a base API in JavaSE, which includes modules like MVP architecture, Service & Repository Layer, Event Model to fire events between presenter etc.

I am trying to implement all best practices of Software Design. Recently, I read about Dependency Injection & its advantages and decided to use Guice as DI framework.

After spending two days learning Guice, I am still confused with some design issues.

If I create an injector using Guice.createInjector(modules) with the core modules of my API,

How to make this injector instance available to my other API classes? Can an injector be injected and is it a good practice?

How to make this injector instance available to API user, so that they can use this injector to create instances?

Should I even make it available to API user, as it may be a bad practice?

Hence using it for AOP approach like this and custom injections

Is creating injectors a heavyweight operation, if so should there be only a few injectors per application?

Should injectors be created on startup stage of the application or could be created in between without affecting the application performance?

Edit

To understand usage of Provider instead of injecting injector here is an short MVP example:

```<code>interface ProductModel {

  // Some method declarations

}

interface ProductView {

  // Some method declarations

}

class ProductPresenter {

  // Using Guice for constructor injection
  @Inject
  ProductPresenter(ProductModel model, ProductView view) {
    this.model = model;
    this.view = view;
  }

}

class ProductViewImpl implements ProductView {

  // Method Implementations

}

class ProductModelImpl implements ProductModel {

  // Method Implementations

}
</code>```

Now, as understood from below answers to use Provider<X> instead of injecting injector, here is the Provider class.

```<code>class ProductPresenterProvider implements Provider<ProductPresenter> {

  ProductPresenter get() {
    // But, How to provide the ProductPresenter without model and view instances!
  }

}
</code>```


问:
Design: .NET web app architecture problem
I'm taking my first foray into .NET and I'm designing a web app that's heavy on other web services right now. I'm intending to do the following:

Take user input (a USDOT number)

Request data from a public, government API on that DOT number (provided it is not available in local storage)

Commit to DB (if needed)

Pass to a risk score calculator which:

Breaks apart the data and looks for red flags (like if the carrier has no authority) and other risks

Passes the risk determination back to the view so the user can make an informed decision about the carrier.

The application will be questionnaire style and I'm going to rely on user input, but there's a few critical factors that can be generated immediately without any input. If these factors return something bad the user is probably going to stop there because they have what they need to make a decision on  the carrier. So there will be an initial call / return on critical factors, then a more in-depth call / return that evaluates user response to questions.

I expect an integer risk score to be returned, so I can give the user a "high/medium/low risk" along with individual recommendations to help make an informed decision.

I found a great example app called AccountAtAGlance by Dan Wahlin (https://github.com/DanWahlin/AccountAtAGlance). I'm impressed by how much I retained from pluralsight and the books I am reading, because I understood most of his example app with ease.

I'm struggling with the best way to implement passing the data from the Carrier model into the Risk Score Calculator and the Risk Score Calculator passing it back to the Controller and I'm looking for help.

My file structure is basically mimicing the AccountAtAGlance example.

Right now my idea is as follows:

Make RiskScoreRepository.cs available to the controller and have it call RiskScoreRepository.GetCarrierRisk(int dotnumber)

Here's where I get stuck: GetCarrierRisk calls something so it can evaluate the initial risk and return it to the controller.

So, a couple of questions I have:

Is a repository the appropriate place for GetCarrierRisk?
Where should GetCarrierRisk go to get the data evaluated and returned? This is what I'm referring to as the Risk Score Calculator. Should it possibly be a RiskScoreEngine? Similar to https://github.com/DanWahlin/AccountAtAGlance/blob/master/AccountAtAGlance.Repository/Helpers/StockEngine.cs?

I'm thinking it's better, for testability, to have each risk factor (like if the carrier has authority and if the carrier has inspections) to have its own method that accepts a raw value and returns the appropriate risk. But then how does the request flow into these methods? Does GetCarrierRisk make a bunch of calls to the Risk Score Calculator and put the return into something like a List that gets passed to the controller?

答:
You should split 'getting information' from 'assessing information'

You have (at the moment) two sources of info, the USDOT result and the form. I would recomend you compile these results into a RiskInfo object which you can pass to a CalcRisk engine.

CalcRisk should be a purely in memory stateless calculation so you can unit test it extensively.

I would consider calling the same engine for both full and partial RiskInfo information. this makes your testing harder but the workflow simple. You will prob add more information to RiskInfo as the product develops so you dont want artificial seperation of 'initial calc' and 'full calc' because then later youll have 'full calc with extra' and so on.

I would use repositories, but I would keep them away from the calc logic eg:

```<code>namespace Risk
{
    /// <summary>
    /// the information you get back from the US gov about a dot number
    /// </summary>
    public class USDOTReport
    { }

    /// <summary>
    /// the information you collect from your form
    /// </summary>
    public class FormInformation
    {
        public int USDOTNumber { get; set; }
    }

    /// <summary>
    /// a data access layer for saving and retrieving usdotreports from/to a database
    /// </summary>
    public interface IUSDOTRepository
    {
        USDOTReport Get(string id);
        void Save(USDOTReport report);
    }

    /// <summary>
    /// encapsulate the USDOT webservice so you can make calls to get reports
    /// </summary>
    public interface IUSDOTService
    {
        USDOTReport Get(int usDotNumber);
    }

    /// <summary>
    /// a repository for storing/retrieving form info on a database
    /// </summary>
    public interface IFormInfoRepository
    {
        FormInformation Get(string id);
        void Save(FormInformation forminfo);
    }

    /// <summary>
    /// a combined risk information object which includes all the data you might use calculating the risk info result
    /// </summary>
    public class RiskInfo_v1
    {
        public USDOTReport DotReport { get; set; }
        public FormInformation Form { get; set; }
    }

    /// <summary>
    /// the result of a risk calculation
    /// </summary>
    public class RiskInfoResult
    {
        double RiskScore { get; set; }
    }

    /// <summary>
    /// Risk calculators should calculate the riskinforesult soley from the riskinfo object
    /// </summary>
    public interface IRiskCalculator_v1
    {
        RiskInfoResult CalculateRisk(RiskInfo_v1 RiskInfo);
    }

    /// <summary>
    /// this is your top level applicaiton or website
    /// </summary>
    public class RiskCalcService
    {
        IFormInfoRepository repoForm;
        IUSDOTRepository repoDot;
        IRiskCalculator_v1 riskCalculator;
        IUSDOTService dotService;

        public RiskInfoResult CalcRisk(FormInformation formInfoSoFar)
        {
            //save form
            repoForm.Save(formInfoSoFar);

            //get dotreport
            USDOTReport report = dotService.Get(formInfoSoFar.USDOTNumber);

            //save it
            repoDot.Save(report);

            //create the risk info
            RiskInfo_v1 ri = new RiskInfo_v1()
            {
                DotReport = report,
                Form = formInfoSoFar
            };

            //calc risk
            RiskInfoResult result = riskCalculator.CalculateRisk(ri);

            return result;
        }

    }
}
</code>```

Body:
You should split 'getting information' from 'assessing information'

You have (at the moment) two sources of info, the USDOT result and the form. I would recomend you compile these results into a RiskInfo object which you can pass to a CalcRisk engine.

CalcRisk should be a purely in memory stateless calculation so you can unit test it extensively.

I would consider calling the same engine for both full and partial RiskInfo information. this makes your testing harder but the workflow simple. You will prob add more information to RiskInfo as the product develops so you dont want artificial seperation of 'initial calc' and 'full calc' because then later youll have 'full calc with extra' and so on.

I would use repositories, but I would keep them away from the calc logic eg:

namespace Risk
{
    /// <summary>
    /// the information you get back from the US gov about a dot number
    /// </summary>
    public class USDOTReport
    { }

    /// <summary>
    /// the information you collect from your form
    /// </summary>
    public class FormInformation
    {
        public int USDOTNumber { get; set; }
    }

    /// <summary>
    /// a data access layer for saving and retrieving usdotreports from/to a database
    /// </summary>
    public interface IUSDOTRepository
    {
        USDOTReport Get(string id);
        void Save(USDOTReport report);
    }

    /// <summary>
    /// encapsulate the USDOT webservice so you can make calls to get reports
    /// </summary>
    public interface IUSDOTService
    {
        USDOTReport Get(int usDotNumber);
    }

    /// <summary>
    /// a repository for storing/retrieving form info on a database
    /// </summary>
    public interface IFormInfoRepository
    {
        FormInformation Get(string id);
        void Save(FormInformation forminfo);
    }

    /// <summary>
    /// a combined risk information object which includes all the data you might use calculating the risk info result
    /// </summary>
    public class RiskInfo_v1
    {
        public USDOTReport DotReport { get; set; }
        public FormInformation Form { get; set; }
    }

    /// <summary>
    /// the result of a risk calculation
    /// </summary>
    public class RiskInfoResult
    {
        double RiskScore { get; set; }
    }

    /// <summary>
    /// Risk calculators should calculate the riskinforesult soley from the riskinfo object
    /// </summary>
    public interface IRiskCalculator_v1
    {
        RiskInfoResult CalculateRisk(RiskInfo_v1 RiskInfo);
    }

    /// <summary>
    /// this is your top level applicaiton or website
    /// </summary>
    public class RiskCalcService
    {
        IFormInfoRepository repoForm;
        IUSDOTRepository repoDot;
        IRiskCalculator_v1 riskCalculator;
        IUSDOTService dotService;

        public RiskInfoResult CalcRisk(FormInformation formInfoSoFar)
        {
            //save form
            repoForm.Save(formInfoSoFar);

            //get dotreport
            USDOTReport report = dotService.Get(formInfoSoFar.USDOTNumber);

            //save it
            repoDot.Save(report);

            //create the risk info
            RiskInfo_v1 ri = new RiskInfo_v1()
            {
                DotReport = report,
                Form = formInfoSoFar
            };

            //calc risk
            RiskInfoResult result = riskCalculator.CalculateRisk(ri);

            return result;
        }

    }
}


答:
a state machine takes input that may or may not transform its state into one of a finite set of other states. How is that different from any other computer program?

Some answers here emphasise that in our (probably) finite universe everything is finite, all computer programs run in finite time, therefore technically everything is a finite-state machine. That's "technically correct (the best kind of correct)", but also completely missing the point.

The essence is this: -- Some computer programs require more working memory when they get larger and more complex inputs. Some don't.

If you realize this, you will get a theoretical-informatical insight that may allow you to write more efficient and elegant programs when you encounter the given kind of problem. It will also allow you to recognize the kind of problem where this may apply.

Here are two toy examples:

Problem 1: A program receives a list of characters on standard input. After all characters are processed, the program must print whether the number of "x" characters in the input was odd or even.

Problem 2: A program receives a list of characters on standard input. After all characters are processed, the program must print whether the number of "x" characters in the input was smaller, equal, or greater than the number of "y" characters.

You may want to stop reading now, solve the problems in your favorite programming language (or just a pseudocode), and return later.

...

The important thing you may have noticed is the following: To implement the solution to problem 1 properly, you only need one bit of memory. You don't have to calculate how many "x"'s you have already processed -- only whether the number of "x"'s processed so far was odd or even. When you encounter another "x", flip the bit. At the end of the program, look at the bit and print the answer.

Does your input contain dozen characters? Thousands of characters? Googolplex characters (hypothetically speaking, of course)? Does not matter; one bit of working memory will still be enough.

You cannot do the same thing with problem 2. When reading the characters, you have to remember the difference between the number of already processed "x"'s and "y"'s; otherwise you can't print the correct answer reliably. You may realize that you actually don't need to remember both the numbers of "x"'s and "y"'s -- only their difference, so far; one integer value that you will increase when you encounter another "x", and decrease when you encounter another "y" -- but still, if you decide to use e.g. 32 bits of memory to keep this value, you may get an input (several billions of characters long) that you cannot process correctly with the given limited amount of memory.

This is what we mean by saying that the problem 1 can be solved by a "state machine", and problem 2 cannot. A limited amount of memory is enough for an input of any size.

(Of course, you could also write an inefficient solution to the problem 1, where you would try to count all the "x"'s, and then you might also get an out-of-memory problem. But the difference is that an efficient solution to the problem 1 exists, while a similarly efficient solution to the problem 2 does not.)

Why is this important in real life?

First, unlike with these two toy examples, the dilemma may not be between literally one bit and one integer value, but between some large and some even larger data structure. Sometimes the "even larger" data structure does not fit in the computer memory, or sufficiently slows down the program, even for realistic inputs.

Second, the solution using the state machine will probably be much faster. Also it will scale linearly with the length of input; that is, processing 10-times longer input will require 10-times more time (as opposed to e.g. 100-times more time). That's a desired property when you need to process a lot of data.

Third, limited vs unlimited memory usage has an impact on security. If you write a program that only requires limited memory, you don't have to worry about memory overflows and how they could potentially be abused to compromise the security of the whole system.

Fourth, this is part of what should be a standard computer science curriculum in any decent school: formal languages, authomata, computational complexity, et cetera. To understand the larger picture behind computer design, as opposed to merely "uhh, I put some pieces of code from internet together, I really hope it works, but I can't tell for sure" approach.

To take advantage of this theory, you don't really need any special machine, any framework or library... you only need to realize "oh, this part of the problem can actually be solved using a finite amount of memory" and write your program (in your favorite programming language) accordingly. But in some situations it is better to use an existing library, so you don't have to reinvent the wheel.


问:
ScrumMaster rotation with multiple scrum masters and teams
I'm currently working in a project where we discuss the question whether it is a good idea or not to rotate the scrum masters through all teams.

We have different teams for ONE project. The context where they work in is the same. They only switch teams for a couple of weeks. We hope to benefit from each ScrumMaster as they have new influences on other teams and maybe can resolve problems others couldn't.

In detail we want each scrum master to assist every team for a couple of weeks. I didn't find any literature about that topic, but only about rotating the scrum master role in a team.

Is this is a good/bad idea?

答:
The Scrum Master Manifesto suggests to have one Scrum Master for one team only. While this subject is debatable for many and economic reasons, many people support the idea of dedicated Scrum Masters.

The main reason for a dedicated Scrum Master is the organizational overhead it takes to handle multiple projects. Context switches are expensive. The role of the Scrum Master is to remove impediments. But if the Scrum Master needs a half or full day of catching up whenever s/he switches teams, s/he pretty much becomes an impediment him/herself. I understand that this doesn't seem to be much of a problem in your case though.

I guess whether it's a good or bad idea depends on why you think of doing it. What is the benefit you hope to gain from doing that? If you can put that to a measurable experiment, why not just try for a limited time and evaluate the outcome.

An alternative I can think of is having the Scrum Masters meet frequently to talk about challenges they face and coach each other. At Spotify, they have guilds for that.


问:
I believe I have mixed C and C++ code when I shouldn't have; Is this a problem and how to rectify?
Background/Scenario

I started writing a CLI application purely in C (my first proper C or C++ program that wasn't "Hello World" or a variation thereof). Around midway through I was working with "strings" of user input (char arrays) and I discovered the C++ string streamer object. I saw that I could save code using these, so I used them through the application. This means that I have changed the file extension to .cpp and now compile the app with g++ instead of gcc. So based on this, I would say the application is now technically a C++ application (although 90%+ of the code is written in what I would call C, as there is lots of cross-over between the two language given my limited experience of the two). It is a single .cpp file around 900 lines long.

Important Factors

I want the program to be free (as in money) and freely distributable and usable for all to have. My concern is that someone will look at the code and think something to the effect of:

Oh look at the coding, it's awful, this program can't help me

When potentially it could! Another matter is the code being efficient (it is a program for testing Ethernet connectivity). There should be no parts of the code that are so inefficient that they can severely hinder the performance of the application or its output. However, I think that is a question for Stack Overflow when asking for help with specific functions, methods, object calls, etc.

My question

Having (in my opinion) mixed C and C++ where perhaps I shouldn't. Should I look to rewrite it all in C++ (by this, I mean implement more C++ objects and methods where perhaps I have coded something in a C style that can be condensed using newer C++ techniques), or remove the use of string streamer objects and bring it all "back" to C code? Is there a correct approach here? I am lost and need some guidance on how to keep this application "Good" in the eyes of the masses, so they will use it and benefit from it.

The Code - Update

Here is a link to the code. It is circa 40% comments, I comment nearly every line until I feel more fluent. In the copy I have linked to though, I have removed pretty much all the comments. I hope this doesn't make it too hard to read. I am hoping though that no one should need to fully understand it. If I have made fatal design flaws though, I am hoping they should be identifiable easily. I should also mention, I am writing a couple of Ubuntu desktops and laptops. I'm not intending to port the code to other operating systems.

答:
The accepted answer mentions only the pros of converting C to idiomatic C++, as if C++ code would be in some absolute sense better than C code. I agree with other answers that it's probably unnecessary to do any drastic changes to the mixed code if it isn't broken.

Whether mixing C and C++ is sustainable depends on how the mixing is done. Subtle bugs can be introduced for example when exceptions are raised in C-code (which isn't exception safe), causing memory leaks or data corruptions. Safer and quite common way is to wrap C-libraries or interfaces in classes, or use them in some other kind of isolation in a C++ project.

Before you decide to rewrite your whole project to idiomatic C++ (or C), you should be aware that many of the changes presented in other answers can make your program slower, or cause other unwanted effects. For example:

changing stack-allocated C-strings to std::strings can cause unnecessary heap  allocations

changing raw pointers to some shared pointer types (like std::shared_ptr) causes access overhead due to reference counting, internal virtual member functions and thread safety

standard library streams are slower than C counterparts

careless usage of RAII classes, like containers, can cause unnecessary operations, especially when move semantics of C++11 can't be used

templates can cause longer compile times, unclear compile errors, code bloat and portability issues between compilers

writing exception-safe code is difficult, which makes introducing subtle bugs during the conversion easy

it's tricker to use C++ code from a shared library than plain C

C++ is not as widely supported as e.g. C89

To conclude, converting from mixed C and C++ code to idiomatic C++ should be seen as a tradeoff which has a lot more to it than just implementation time and enlargening your toolbox with seemingly convenient features. Therefore it's very hard to give an answer for the general case other than "it depends".


问:
Lambda Return Type Inference
Writing my own JVM compiler, I am facing a giant problem that I am desperately unable to solve:

Lambda Return Type Inference

1. Overview of the compiler lifecycle

More specifically, the order in which things should happen in a compiler to make this work correctly. First of all, as probably every compiler, mine is divided in several phases that run on the AST and do the work. After tokenizing, parsing and building the ast, the following phases happen in that order:

RESOLVE_TYPES - Links type tokens to their classes

RESOLVE - Links fields and methods

CHECK_TYPES - Re-checks types (boxing, ...), Infers generic type arguments

CHECK - More uninteresting semantic checks that could be skipped in a perfect world

The phases in question are RESOLVE and CHECK_TYPES. The first resolves method calls and field accesses / assignments as well as their callees and arguments, basically everything important. Between the two, something happens that I call withType. Basically, the context in which an expression appears calls the withType method of the expression with the type it expects the expression to have.

Example

Consider this method and an invocation:

```<code>class List[E]
{
    public List[U] mapped(Function[E, U] mapper) = ...
}

List[String] list = [ "a", "b", "c" ]
var list2 = list.mapped { s => s.toUpperCase }
</code>```

What the compiler does

This is what is going to happen in my compiler now (we ignore what happens with the List class):

Read File, Tokenize, Parse - nothing spectacular

Resolve Types - nothing special, link all explicit types (List[String])

Resolve - link method calls

It is known that list has the type List[String], so we can search that for methods called mapped. Iterate through all methods in the class, and if the name matches the method name, continue with argument types. This works like this: The argument type is Function[E, U], so call isType(Function[E, U]) on the argument { s => s.toUpperCase }.
The Statement List { } delegates the call to the lambda expression, which checks if the type has a functional method.

```<code>interface Function[T, R]
{
    R apply(T par1) // <-- Here it is
}
</code>```

Now, link the method and the type Function[E, U] to the lambda expression.

Check Types - Infer the type arguments of generic types

We start with Function[E, U]. It is known that E is a type parameter of the generic type List[E], which is also the type of the callee, but more concrete: List[String]. That means that E can be inferred to String. But here comes the problem: Since we need E for the type of the lambda parameter s, it was not possible to resolve the lambda body, i.e. s.toUpperCase. Because of that, it is not possible to infer U at the moment, so the compiler continues without inferring the right type (it simply uses any, which is java.lang.Object). That means that our inferred type is now Function[String, any].

In the next step, the compiler calls the withType method of the lambda expression, which updates the type stored in the lambda AST node. Now we can actually call lambda.checkTypes, which will a) infer the type of s to String and b) call resolve (!), withType and checkTypes on the lambda body, allowing us to compute the return type of the lambda.

2. The problem

As you can see, although we now have the type of the lambda parameter s and the return type of the lambda (String), the type of the lambda is still Function[String, any], which means the result of the call to mapped and therefore the type of the variable list2 is List[any]. However, since the return type of the lambda is actually String, this is not the correct type (since List is invariant on E, the types are not even compatible). The generic type system of the compiler is not advanced enough to make things like

```<code>List[String] list2 = list.mapped { s => s.toUpperCase }
</code>```

impossible, but neither variant is technically correct as long as the lambda type gets inferred to Function[String, any] while it is actually Function[String, String].

Furthermore, consider this expression:

```<code>int length = list.mapped(s => s.replace("a", "")).getFirst.length
</code>```

The call to mapped returns a List[any], therefore getFirst returns an any, which does not have a length member. Normally, one would expect this expression to work, and in fact lambda expressions work like this in Java and Scala (which makes things a little simpler by enforcing their built-in function types, disallowing FunctionInterfaces).

3. The question

Now that you know the details of my compiler lifecycle, type inference and lambda expressions in my programming language, is there any way I could restructure it to make lambda return type inference work correctly? Although they have very different compiler phases and -lifecycles, Java 8 and Scala have to do similar things after all as well.

4. My potential solution

I was able to come up with at least a sort of solution that covers around 10% of the problem, which would be to infer types in RESOLVE so the lambda can actually call resolve of its body in resolve instead of checkTypes. That means that the return type of the lambda is known after resolve and further calls in the chain have the proper callee type (e.g., the getFirst method). However, I am unsure if that would be possible with my current type inference system. Any opinion / advice is greatly appreciated.

Compiler Source Code:

GitHub Repository

IType class

GenericType class

Method class (inferType around line 880)

IValue class

LambdaExpression class

View at own risk, 90k lines of code.

答:
Your problem is that you link method calls before the program is fully type-checked. In a complicated language with subtype polymorphism and parametric polymorphism, you cannot do any kind of linking before you know the type (or in the case of subtyping, the type bounds) of an expression. The solution is to introduce type variables for expressions of (initially) unknown type, and properly unify type variables with concrete types. If you cannot resolve a type variable, that's an error and not an invitation to deduce the most general type.

A proper type inferer would look at the code

```<code>var list2 = list.mapped { s => s.toUpperCase }
</code>```

in the static environment

```<code>list : List[String]
List[E]#mapped[U] : (E => U) => List[U]
String#toUpperCase : () => String
</code>```

like this:

infer var list2 = list.mapped { s => s.toUpperCase }

infer list.mapped { s => s.toUpperCase }

infer list

known to be List[String]

save E = String to the static environment for this expression.

resolves to List[E]#mapped[U]

introduce variable $U for U.

known to be (E => $U) => List[$U]

unify arguments: (E => $U) >: typeof({ s => s.toUpperCase })

infer { s => s.toUpperCase }

introduce variables $a, $b

known to be $a => $b

unify (E => $U) >: ($a => $b): E <: $a and $b <: $U. Technically, these are just type bounds, but let's consider them equal.

save E = $a, $b = $U to the static environment for this expression

save s : $a to the static environment for this expression

infer s.toUpperCase

infer s

known to be String

infer .toUpperCase.

matches String#toUpperCase

known to be () => String

is String

unify String <: $b, but lets consider them equal

save $b = String to the static environment for this expression

is ($a => $b) = (String => String)

already unified (E => $U) >: ($a => $b).

is List[$U] = List[String]

infer var list2

introduce variable $c

save list2 : $c into the static environment for this scope

is $c

unify $c >: List[String], but let's consider them equal

save $c = List[String] into the static environment

After this round of type inference, asking the static environment for the type of list2 gives us List[String]. The above steps roughly follow along the type inference steps for a Hindley-Milner type system, but note that you are probably dealing with subtyping, which makes type inference far more complicated: unifying a type only provides us bounds on the type and very rarely a concrete type. In the above example, I ignored these details and always unified the types as equals.

The second major problem is infering the type of the object on which to dispatch for a method call. In this example, I always tried to infer the type of the object before resolving the method call. However, this is not necessary. A method List[E]#mapper[U] : (E => U) => List[U] could also be viewed as a free function .mapper[E, U]: (List[E], E => U) => List[U]. In other words, the implicit this argument is transformed to an explicit argument. This allows us use type variables for the invocant variable, and makes it easier to deal with a set of overloads. Consider the following example:

```<code>static env:
  .add[E]    : (List[E], E) => void
  .add[E]    : (List[E], List[E]) => void
  .add[K, V] : (Map[K, V], K, V) => void
  .add       : (Integer, Integer) => Integer
  a          : $a
  b          : $b

expression:
    a.add(b)
</code>```

when type-infering that expression, we initially only know that this is some kind of .add call, but we do not know which one – we cannot resolve it at this point. We have to unify each of the possible types with the given types. If one unification fails, we remove that possibility from the set of overloads.

infer a.add(b)

candidate (List[E], E) => void

variable $c for E

unify arguments

$a = List[$c]

$b = $c

is void

candidate (List[E], List[E]) => void

variable $c for E

unify arguments

$a = List[$c]

$b = List[$c]

is void

candidate (Map[K, V], K, V) => void

variable $c for K

variable $d for V

unify arguments

$a = Map[$c, $d]

$b = $c

ERROR: no argument for V-parameter

discard candidate

candidate (Integer, Integer) => Integer

unifiy arguments

$a = Integer

$b = Integer

is Integer

So after doing a round of type inference, we are still left with a number of choices. Some languages employ some ranking mechanism, e.g. methods on subtypes are preferred over methods on supertypes. In our example, there is no sensible ranking. If you want your type-checker to be moderately well-performing, you should issue a compiler exception here, e.g.

```<code>foo.sourcefile:42:3 error: could not resolve call to method `add`
    a.add(b)
      ^
    candidates are:
    List[E]#add(E elem)
    List[E]#add(List[E] elems)
    Integer#add(Integer rhs)
</code>```

Likewise, you should display an error when the set of possible methods is empty after attempting unification.

Note that for a different static environment, the the set of possible solutions would only contain one method which you could bind to. E.g.:

```<code>a : List[$c]
b : $c
</code>```

Since the call can be resolved unambiguously in that case, we can continue doing type inference for the rest of the compilation unit in hopes of resolving the $c type variable.

Depending on how you implement generics, you could link the method call directly after successfully infering the type for the call. If you need to know the value of the type variable $c, you need to wait until type inference for the compilation unit has completed, and can do linking in a second pass. This is now easy to do since all expressions are already annotated with their inferred type.

Title: Lambda Return Type Inference

Body:
Your problem is that you link method calls before the program is fully type-checked. In a complicated language with subtype polymorphism and parametric polymorphism, you cannot do any kind of linking before you know the type (or in the case of subtyping, the type bounds) of an expression. The solution is to introduce type variables for expressions of (initially) unknown type, and properly unify type variables with concrete types. If you cannot resolve a type variable, that's an error and not an invitation to deduce the most general type.

A proper type inferer would look at the code

var list2 = list.mapped { s => s.toUpperCase }

in the static environment

list : List[String]
List[E]#mapped[U] : (E => U) => List[U]
String#toUpperCase : () => String

like this:

infer var list2 = list.mapped { s => s.toUpperCase }

infer list.mapped { s => s.toUpperCase }

infer list

known to be List[String]

save E = String to the static environment for this expression.

resolves to List[E]#mapped[U]

introduce variable $U for U.

known to be (E => $U) => List[$U]

unify arguments: (E => $U) >: typeof({ s => s.toUpperCase })

infer { s => s.toUpperCase }

introduce variables $a, $b

known to be $a => $b

unify (E => $U) >: ($a => $b): E <: $a and $b <: $U. Technically, these are just type bounds, but let's consider them equal.

save E = $a, $b = $U to the static environment for this expression

save s : $a to the static environment for this expression

infer s.toUpperCase

infer s

known to be String

infer .toUpperCase.

matches String#toUpperCase

known to be () => String

is String

unify String <: $b, but lets consider them equal

save $b = String to the static environment for this expression

is ($a => $b) = (String => String)

already unified (E => $U) >: ($a => $b).

is List[$U] = List[String]

infer var list2

introduce variable $c

save list2 : $c into the static environment for this scope

is $c

unify $c >: List[String], but let's consider them equal

save $c = List[String] into the static environment

After this round of type inference, asking the static environment for the type of list2 gives us List[String]. The above steps roughly follow along the type inference steps for a Hindley-Milner type system, but note that you are probably dealing with subtyping, which makes type inference far more complicated: unifying a type only provides us bounds on the type and very rarely a concrete type. In the above example, I ignored these details and always unified the types as equals.

The second major problem is infering the type of the object on which to dispatch for a method call. In this example, I always tried to infer the type of the object before resolving the method call. However, this is not necessary. A method List[E]#mapper[U] : (E => U) => List[U] could also be viewed as a free function .mapper[E, U]: (List[E], E => U) => List[U]. In other words, the implicit this argument is transformed to an explicit argument. This allows us use type variables for the invocant variable, and makes it easier to deal with a set of overloads. Consider the following example:

static env:
  .add[E]    : (List[E], E) => void
  .add[E]    : (List[E], List[E]) => void
  .add[K, V] : (Map[K, V], K, V) => void
  .add       : (Integer, Integer) => Integer
  a          : $a
  b          : $b

expression:
    a.add(b)

when type-infering that expression, we initially only know that this is some kind of .add call, but we do not know which one – we cannot resolve it at this point. We have to unify each of the possible types with the given types. If one unification fails, we remove that possibility from the set of overloads.

infer a.add(b)

candidate (List[E], E) => void

variable $c for E

unify arguments

$a = List[$c]

$b = $c

is void

candidate (List[E], List[E]) => void

variable $c for E

unify arguments

$a = List[$c]

$b = List[$c]

is void

candidate (Map[K, V], K, V) => void

variable $c for K

variable $d for V

unify arguments

$a = Map[$c, $d]

$b = $c

ERROR: no argument for V-parameter

discard candidate

candidate (Integer, Integer) => Integer

unifiy arguments

$a = Integer

$b = Integer

is Integer

So after doing a round of type inference, we are still left with a number of choices. Some languages employ some ranking mechanism, e.g. methods on subtypes are preferred over methods on supertypes. In our example, there is no sensible ranking. If you want your type-checker to be moderately well-performing, you should issue a compiler exception here, e.g.

foo.sourcefile:42:3 error: could not resolve call to method `add`
    a.add(b)
      ^
    candidates are:
    List[E]#add(E elem)
    List[E]#add(List[E] elems)
    Integer#add(Integer rhs)

Likewise, you should display an error when the set of possible methods is empty after attempting unification.

Note that for a different static environment, the the set of possible solutions would only contain one method which you could bind to. E.g.:

a : List[$c]
b : $c

Since the call can be resolved unambiguously in that case, we can continue doing type inference for the rest of the compilation unit in hopes of resolving the $c type variable.

Depending on how you implement generics, you could link the method call directly after successfully infering the type for the call. If you need to know the value of the type variable $c, you need to wait until type inference for the compilation unit has completed, and can do linking in a second pass. This is now easy to do since all expressions are already annotated with their inferred type.


问:
Reducing boilerplate in class that implements interfaces through composition
I have a class: A that is a composite of a number of smaller classes, B, Cand D.

B, C, and D implement interfaces IB, IC, and ID respectively.

Since A supports all the functionality of B, C and D, A implements IB, IC and ID as well, but this unfortunately leads to a lot of re-routing in the implementation of A

Like so:

```<code>interface IB
{
    int Foo {get;}
}

public class B : IB
{
    public int Foo {get {return 5;}}
}

interface IC
{
    void Bar();
}

public class C : IC
{
    public void Bar()
    {
    }
}

interface ID
{
    string Bash{get; set;}
}

public class D: ID
{
    public string Bash {get;set;}
}

class A : IB, IC, ID
{
    private B b = new B();
    private C c = new C();
    private D d = new D();

    public int Foo {get {return b.Foo}}

    public A(string bash)
    {
        Bash = bash;
    }

    public void Bar()
    {
        c.Bar();
    }

    public string Bash
    {
         get {return d.Bash;}
         set {d.Bash = value;}
    }
}
</code>```

Is there a way to get rid of any of this boilerplate redirection in A? B, C and D all implement different but common functionality, and I like that A implements IB, IC and ID because it means I can pass in Aitself as a dependency matching those interfaces, and don't have to expose the inner helper methods.

答:
Your class is doing too much, that's why you have to implement so much boilerplate. You say in the comments:

it feels more sensible to write Person.Walk() as opposed to Person.WalkHelper.Walk()

I disagree. The act of walking is likely to involve many rules and does not belong in the Person class - it belongs in a WalkingService class with a walk(IWalkable) method where Person implements IWalkable.

Always keep in mind the SOLID principles when you're writing code. The two that are most applicable here are Separation of Concerns (extract the walking code to a separate class) and Interface Segregation (split interfaces into specific tasks/functions/abilities). It sounds like you might have some of the I with your multiple interfaces but are then undoing all your good work by making one class implement them.


问:
If passwords are stored hashed, does that mean that theoretically there exists another password that could be used to log in?
From what I understand, in most sites, passwords are stored as a hash; not in their original form. This means that if the database is hacked into, the attacker will see the (nearly) useless hashes instead of the actual passwords.

For the website to authenticate your login attempt, it hashes your attempt of a password, and checks if it matches the stored hash. If they match, it logs you in, otherwise, it denies it.

I've read on many sites though that no hash algorithm can produce 100% unique hashes; collisions will always happen.

Does that mean that, theoretically, there exists another password that will give the same hash given a hash-function, which means there is potentially more than 1 password that could be used to log in with (although the other password would probably be near-random for a complicated hash-function)?

答:
There are in fact infinitely many passwords which produce the same hash. That is actually more or less the definition of what it means to be a hash function: reducing a larger (potentially infinite) input space into a smaller finite output space.

However, a "good" hash function will distribute the hash values among the input values in such a way that any similarity in the input does not translate into similarity in the output. For a cryptographic hash function, such as the ones used for password hashing, this requirement is even stronger.

What this means, basically, is that the passwords which have the same hash value tend to be very dissimilar. In particular, most tend to be very long, very unreadable, cryptic apparently random strings.


答:
What you're looking for is multiple inheritance.  However, neither C# nor Java have it.

You can extend B from A.  This will eliminate the need for a private field for B as well as the redirecting glue.  But you can only do this for one of B, C or D.

Now if you can make C inherit from B, and D from C then you only have to have A extend D... ;) -- just to be clear though, I'm not actually encouraging that in this example since there's no indication for it.

In C++ you'd be able to have A inherit from B, C, and D.

But multiple inheritance makes programs harder to reason over, and has its own problems; Further, there's often a clean way to avoid it.  Still, sometimes without it, one needs to make design tradeoffs between repeating boilerplate and how the object model is exposed.

It feels a bit like you're trying to mix composition and inheritance.  If this was C++, you could use a pure inheritance solution.  But since it isn't I'd recommend embracing composition.

Title: Reducing boilerplate in class that implements interfaces through composition

Body:
I have a class: A that is a composite of a number of smaller classes, B, Cand D.

B, C, and D implement interfaces IB, IC, and ID respectively.

Since A supports all the functionality of B, C and D, A implements IB, IC and ID as well, but this unfortunately leads to a lot of re-routing in the implementation of A

Like so:

```<code>interface IB
{
    int Foo {get;}
}

public class B : IB
{
    public int Foo {get {return 5;}}
}

interface IC
{
    void Bar();
}

public class C : IC
{
    public void Bar()
    {
    }
}

interface ID
{
    string Bash{get; set;}
}

public class D: ID
{
    public string Bash {get;set;}
}

class A : IB, IC, ID
{
    private B b = new B();
    private C c = new C();
    private D d = new D();

    public int Foo {get {return b.Foo}}

    public A(string bash)
    {
        Bash = bash;
    }

    public void Bar()
    {
        c.Bar();
    }

    public string Bash
    {
         get {return d.Bash;}
         set {d.Bash = value;}
    }
}
</code>```

Is there a way to get rid of any of this boilerplate redirection in A? B, C and D all implement different but common functionality, and I like that A implements IB, IC and ID because it means I can pass in Aitself as a dependency matching those interfaces, and don't have to expose the inner helper methods.


问:
Tricky architecture in C# involving a symmetric operation and a viewing class
I'm trying to build an architecture in C#, and I can't figure out a way to accomplish the task. Basically, there's a set of classes A, B, C and D that inherit from I. Each of these classes has an operation Foo that operates on one of the other classes, and returns an object of type R:

```<code>class A : I
{
    public R Foo(A a);
    public R Foo(B b);
    public R Foo(C c);
    public R Foo(D d);
}
class B : I
{
    public R Foo(A a);
    public R Foo(B b);
    public R Foo(C c);
    public R Foo(D d);
}
class C : I
{
    public R Foo(A a);
    public R Foo(B b);
    public R Foo(C c);
    public R Foo(D d);
}
class D : I
{
    public R Foo(A a);
    public R Foo(B b);
    public R Foo(C c);
    public R Foo(D d);
}
</code>```

This operation Foo is symmetric (i.e. a.Foo(b) == b.Foo(a), d.Foo(a) == a.Foo(d), etc.). (Of course, this means that we really only need to define Foo(A a) in A, Foo(A a) and Foo(B b) in B, and so on, but you get the idea).

If we introduce a new class E, it has to implement Foo for types A, B, C, D, and E.

```<code>class E : I
{
    public R Foo(A a);
    public R Foo(B b);
    public R Foo(C c);
    public R Foo(D d);
    public R Foo(E e);
}
</code>```

Obviously we can't externally add an implementation for public R Foo(E e) in each of the classes A, B, C, and D (well, not without extension methods), but since Foo is symmetric, a.Foo(e) == e.Foo(a), so we only really need to implement Foo(A a) in E.

Now the part that makes this really difficult for me at least, is there's also a "viewer" object V that contains a list of I's. V has to be able to perform the Foo operation between two I's without knowing their actual types. V only knows that the operation Foo exists between two I's. Theoretically, this is what it would look like:

```<code>class V {
    public R Foo(I i1, I i2)
    {
        // Check if i1 has an implementation for Foo taking
        // the type of i2.
        if (!i1.HasFoo(i2.GetType()))
        {
            // Do the same for i2 on i1.
            if (!i2.HasFoo(i1.GetType()))
                return null;
            return i2.Foo(i1);
        }
        return i1.Foo(i2);
    }
}
</code>```

Obviously this would never work, for the same reasons this doesn't work. I've thought about this for quite some time now, and I can't think of an architecture that satisfies these requirements in a clean way. I've thought up a number of convoluted methods that abuse generic types and strategy patterns and visitor patterns and the whole sh'bang, but nothing that isn't prone to bugs or overcomplicated.

How should I implement this, if it's even possible?

This is the actual, non-abstracted application. It's a collision detection engine, where the classes A, B, etc. are different geometries with fundamentally different properties (circle vs infinite line vs polygon, etc.). The different Foos are the different algorithms that test if two geometric shapes are colliding. V is an algorithmic container for a large number of these geometric objects (a quadtree or something).

答:
It sounds like your method Foo should not exist in your I subclasses.

As you mentioned, with your suggested approach adding a new I subclass violates the Open/Closed principle.

Instead, try moving Foo to a new class responsible for the symmetrical operation

```<code>abstract class SymmetricalFoo<T,U>
    where T : I
    where U : I
{
    public R Foo(T t, u u)
    {
        this.Bar(t, u);
    }
    public R Foo(U u, T u)
    {
        this.Bar(t, u);
    }
    protected abstract R Bar(T t, U u);
}
</code>```

And implement a concrete SymmetricalFoo for every I subclass pair.

This way when you add a new I subclass you won't need to modify existing classes.  You'll only need to create new SymmetricalFoos.

As for your V class.  This goes against my general hatred of the pattern... but I think you need an Abstract Factory.

Pass two instances of I subclasses to the factory a get the appropriate SymmetricalFoo as a result.

I'll leave the implementation of that factory to you (because I really dislike writing them!), but it will probably involve making the generic SymmetricalFoo<T,U> class implement a non-generic ISymmetricalFoo interface.

Body:
It sounds like your method Foo should not exist in your I subclasses.

As you mentioned, with your suggested approach adding a new I subclass violates the Open/Closed principle.

Instead, try moving Foo to a new class responsible for the symmetrical operation

abstract class SymmetricalFoo<T,U>
    where T : I
    where U : I
{
    public R Foo(T t, u u)
    {
        this.Bar(t, u);
    }
    public R Foo(U u, T u)
    {
        this.Bar(t, u);
    }
    protected abstract R Bar(T t, U u);
}

And implement a concrete SymmetricalFoo for every I subclass pair.

This way when you add a new I subclass you won't need to modify existing classes.  You'll only need to create new SymmetricalFoos.

As for your V class.  This goes against my general hatred of the pattern... but I think you need an Abstract Factory.

Pass two instances of I subclasses to the factory a get the appropriate SymmetricalFoo as a result.

I'll leave the implementation of that factory to you (because I really dislike writing them!), but it will probably involve making the generic SymmetricalFoo<T,U> class implement a non-generic ISymmetricalFoo interface.


答:
How should you implement it?

You should adopt some convention, like the class made last, gets to implement the behavior and the other one simply forwards the call. Ideally, you can implement them as static methods so that a method and its mirror live next to one another in code.

Yes, this means you have to modify the set when they're expanded. Annoying, but simple to do and unlikely to happen much.

C# can't really enforce symmetry like this easily. Your best bet is to just make the code do it and then punish programmers who break the rules.

Title: Tricky architecture in C# involving a symmetric operation and a viewing class

Body:
I'm trying to build an architecture in C#, and I can't figure out a way to accomplish the task. Basically, there's a set of classes A, B, C and D that inherit from I. Each of these classes has an operation Foo that operates on one of the other classes, and returns an object of type R:

```<code>class A : I
{
    public R Foo(A a);
    public R Foo(B b);
    public R Foo(C c);
    public R Foo(D d);
}
class B : I
{
    public R Foo(A a);
    public R Foo(B b);
    public R Foo(C c);
    public R Foo(D d);
}
class C : I
{
    public R Foo(A a);
    public R Foo(B b);
    public R Foo(C c);
    public R Foo(D d);
}
class D : I
{
    public R Foo(A a);
    public R Foo(B b);
    public R Foo(C c);
    public R Foo(D d);
}
</code>```

This operation Foo is symmetric (i.e. a.Foo(b) == b.Foo(a), d.Foo(a) == a.Foo(d), etc.). (Of course, this means that we really only need to define Foo(A a) in A, Foo(A a) and Foo(B b) in B, and so on, but you get the idea).

If we introduce a new class E, it has to implement Foo for types A, B, C, D, and E.

```<code>class E : I
{
    public R Foo(A a);
    public R Foo(B b);
    public R Foo(C c);
    public R Foo(D d);
    public R Foo(E e);
}
</code>```

Obviously we can't externally add an implementation for public R Foo(E e) in each of the classes A, B, C, and D (well, not without extension methods), but since Foo is symmetric, a.Foo(e) == e.Foo(a), so we only really need to implement Foo(A a) in E.

Now the part that makes this really difficult for me at least, is there's also a "viewer" object V that contains a list of I's. V has to be able to perform the Foo operation between two I's without knowing their actual types. V only knows that the operation Foo exists between two I's. Theoretically, this is what it would look like:

```<code>class V {
    public R Foo(I i1, I i2)
    {
        // Check if i1 has an implementation for Foo taking
        // the type of i2.
        if (!i1.HasFoo(i2.GetType()))
        {
            // Do the same for i2 on i1.
            if (!i2.HasFoo(i1.GetType()))
                return null;
            return i2.Foo(i1);
        }
        return i1.Foo(i2);
    }
}
</code>```

Obviously this would never work, for the same reasons this doesn't work. I've thought about this for quite some time now, and I can't think of an architecture that satisfies these requirements in a clean way. I've thought up a number of convoluted methods that abuse generic types and strategy patterns and visitor patterns and the whole sh'bang, but nothing that isn't prone to bugs or overcomplicated.

How should I implement this, if it's even possible?

This is the actual, non-abstracted application. It's a collision detection engine, where the classes A, B, etc. are different geometries with fundamentally different properties (circle vs infinite line vs polygon, etc.). The different Foos are the different algorithms that test if two geometric shapes are colliding. V is an algorithmic container for a large number of these geometric objects (a quadtree or something).


问:
What design pattern is this?
I'm struggling to come up with the name of a design pattern that I need to write about. I've been lead to think it was abstraction but apparently not.

Let's say I had a driver class which has a Drive method:

```<code>public void Drive()
{
    if(IsOnGasPedal)
    {
        //Lots of code
    }
    if(IsOnBrake)
    {
        //Lots of code
    }
    if(IsOnClutch)
    {
        //Lots of code
    }
}
</code>```

And I change the method to:

```<code>public void Drive()
{
    if(IsOnGasPedal)
    {
        Car.Gas()
    }
    if(IsOnBrake)
    {
        Car.Brake()
    }
    if(IsOnClutch)
    {
        Car.Clutch()
    }
}
</code>```

I have moved the complex and long code into separate methods in my Car property so that the Drive method is more organised. This is an example of refactoring but that is not the word. I thought it was either encapsulation or abstraction but I can't get any solid answers. What is this pattern called?

答:
Arguably it is simply the application of structured programming which was named long before design patterns were born.

As a refactoring, you can call what you have done 'Extract method'

Title: What design pattern is this?


答:
To be clear, none of "refactoring", "abstraction" or "encapsulation" are design patterns.

Neither is what you posted. As you say, it is a refactoring. Specifically, it is the one that Martin Fowler named Extract Method. The definition is "Turn the fragment into a method whose name explains the purpose of the method.", which is precisely what you are doing.

It does also fall under the definition of abstraction. Structure and Interpretation of Computer Programs, for example, describes this as:

[The means] by which compound elements can be named and manipulated as units.

Compound elements, in this case, would refer to the multiple expressions which make up the extracted methods.

Title: What design pattern is this?

Body:
I'm struggling to come up with the name of a design pattern that I need to write about. I've been lead to think it was abstraction but apparently not.

Let's say I had a driver class which has a Drive method:

```<code>public void Drive()
{
    if(IsOnGasPedal)
    {
        //Lots of code
    }
    if(IsOnBrake)
    {
        //Lots of code
    }
    if(IsOnClutch)
    {
        //Lots of code
    }
}
</code>```

And I change the method to:

```<code>public void Drive()
{
    if(IsOnGasPedal)
    {
        Car.Gas()
    }
    if(IsOnBrake)
    {
        Car.Brake()
    }
    if(IsOnClutch)
    {
        Car.Clutch()
    }
}
</code>```

I have moved the complex and long code into separate methods in my Car property so that the Drive method is more organised. This is an example of refactoring but that is not the word. I thought it was either encapsulation or abstraction but I can't get any solid answers. What is this pattern called?


问:
Cleanest way to represent three states, where one can hold a Key/Value pair, and the other two are empty markers
I'm writing a Hash Table that uses linear probing to resolve collisions.

I looked over how linear probing works, and it seems like to allow for deletions, I can't simply remove an element, since that may prevent a previously-collided element from being found post-deletion (since searching ends on an unoccupied cell).

I thought of wrapping the Key,Value pair in a class that just represents a state. 2 of the 3 states (say, Deleted and UnOccupied) are just acting as "markers"; they don't hold anything. The third state however (Occupied) needs to hold the pair.

The goal of this is to differentiate between cells that have always been empty, and cells that have have data previously deleted from them.

To illustrate what I wanted to do, if I were writing this in Haskell, I'd set it up as:

```<code>data CellState k v = Occ k v | Deleted | UnOcc
</code>```

Then I'd just need to pattern match against it to tell what the state of the cell is, and easily extract the pair if the cell is occupied.

I have to write this in Java though. I started writing up a set of classes for the 3 states that all inherit from a base class CellState, but then I thought it through, and I'm not sure how I would even use it since pattern-matching isn't supported in Java.

My second idea was to define 1 class that has key and value fields, and has a enumerated State field, with "getters" that can be used to check what the state of the cell is. If the user attempts to "get" from a CellState that isn't occupied, an exception would be thrown (similar to the behavior of Optional). The user could then use either an if-tree, or a switch to act on the cell based on its internal state.

The second idea seems more imperitive-styled, but still seems clumsy. This also allows for the possibility of an inconsistent state where a key and value are available, but it's marked as non-Occupied, or where it's marked as Occupied, but doesn't contain a pair. This isn't possible in the "Haskell solution".

By the way, this is for homework, so I can't simply not use linear probing, since that is an assignment requirement.

Is there a better way to go about doing this?

答:
Linear Probing is inherently restricted and has sub-optimal performance, and there's no good way around those problems. The only good uses for linear probing hash tables is when you are in a memory-restricted environment and cannot perform any allocations, or when you have a perfect hash function and can therefore know that no collisions will arise.

If you really have to provide deletion, then your ternary approach makes sense. In Java, we would use null for a free bucket, and the state of the bucket to mark it as occupied or deleted. E.g.:

class Bucket<K, V> {
  K key;
  V value;
  boolean occupied;
  Bucket(K key, V value) {
    this.key = key;
    this.value = value;
    occupied = true;
  }
  void free() {
    key = value = null;
    occupied = false;
  }
}

Bucket<K, V> buckets[] = ...;

V get(K key) {
  int i = hash(key);
  for (; i < buckets.length; ++i) {
    Bucket b = buckets[i];
    if (b == null) break;
    if (b.occupied && b.key == key) return b.value;
  }
  throw ...;
}

void delete(K key) {
  int i = hash(key);
  for (; i < buckets.length; ++i) {
    Bucket b = buckets[i];
    if (b == null) break;
    if (b.occupied && b.key == key) b.free();
  }
}
```

<p>An alternative would be to have each bucket link to the next bucket with the same hash, which is effectively a pre-allocated linked list. Note that each Bucket needs two pointers: one to the next bucket for the same hash as this entry, and one to the start of the list for the hash of this bucket – which is needed since when a bucket is filled, the entry may belong to a different list and not to this hash. Actually, this isn't using open addressing any more. It has the capacity restrictions of open addressing since each bucket can only hold one value, but all other properties are equivalent to the linked-list technique of collision resolution.</p>

<p>Example of structure:</p>

```hashTable.put("a", 1) // hash(a) = 1
hashTable.put("b", 1) // hash(b) = 1
hashTable.put("c", 2) // hash(c) = 2
hashTable.put("d", 1) // hash(d) = 1
hashTable.put("e", 3) // hash(e) = 3

// 0: start: / next: 3 key: "b" value: 1
// 1: start: 1 next: 0 key: "a" value: 1
// 2: start: 2 next: / key: "c" value: 2
// 3: start: 4 next: / key: "d" value: 1
// 4: start: / next: / key: "e" value: 3
```

<p>Algorithms sketch:</p>

```class Bucket<K, V> {
  K key = null;
  V value = null;
  Bucket<K, V> next = null;
  Bucket<K, V> start = null;
}

Bucket<K, V> buckets[] = ...;
// initialize buckets[] with empty buckets

V get(K key) {
  Bucket<K, V> b = buckets[hash(key)].start;
  for (; b != null; b = b.next) {
    if (b.key == key) return b.value;
  }
  throw ...;
}

void put(K key, V value) {
  Bucket<K, V> b = buckets[hash(key)];

  // case: first item in bucket
  if (b.start == null) {
    b.key = key;
    b.value = value;
    b.start = b;
    return;
  }

  // find bucket with key
  Bucket<K, V> p = null;
  b = b.start;
  for (; b != null; p = b, b = b.next) {
    // overwrite entry
    if (b.key == key) {
      b.value = value;
      return;
    }
  }

  // enter a new bucket into this list:
  b = getNextFreeBucket();
  p.next = b;
  b.key = key;
  b.value = value;
}

void delete(K key) {
  Bucket<K, V> p = null;
  Bucket<K, V> b = buckets[hash(key)].start;
  for (; b != null; p = b, b = b.next) {
    if (b.key == key) {
      b.key = null;
      b.value = null;
      if (p != null) p.next = b.next;
      b.next = null;
      return;
    }
  }
}
```

Body:
Linear Probing is inherently restricted and has sub-optimal performance, and there's no good way around those problems. The only good uses for linear probing hash tables is when you are in a memory-restricted environment and cannot perform any allocations, or when you have a perfect hash function and can therefore know that no collisions will arise.

If you really have to provide deletion, then your ternary approach makes sense. In Java, we would use null for a free bucket, and the state of the bucket to mark it as occupied or deleted. E.g.:

class Bucket<K, V> {
  K key;
  V value;
  boolean occupied;
  Bucket(K key, V value) {
    this.key = key;
    this.value = value;
    occupied = true;
  }
  void free() {
    key = value = null;
    occupied = false;
  }
}

Bucket<K, V> buckets[] = ...;

V get(K key) {
  int i = hash(key);
  for (; i < buckets.length; ++i) {
    Bucket b = buckets[i];
    if (b == null) break;
    if (b.occupied && b.key == key) return b.value;
  }
  throw ...;
}

void delete(K key) {
  int i = hash(key);
  for (; i < buckets.length; ++i) {
    Bucket b = buckets[i];
    if (b == null) break;
    if (b.occupied && b.key == key) b.free();
  }
}

An alternative would be to have each bucket link to the next bucket with the same hash, which is effectively a pre-allocated linked list. Note that each Bucket needs two pointers: one to the next bucket for the same hash as this entry, and one to the start of the list for the hash of this bucket – which is needed since when a bucket is filled, the entry may belong to a different list and not to this hash. Actually, this isn't using open addressing any more. It has the capacity restrictions of open addressing since each bucket can only hold one value, but all other properties are equivalent to the linked-list technique of collision resolution.

Example of structure:

hashTable.put("a", 1) // hash(a) = 1
hashTable.put("b", 1) // hash(b) = 1
hashTable.put("c", 2) // hash(c) = 2
hashTable.put("d", 1) // hash(d) = 1
hashTable.put("e", 3) // hash(e) = 3

// 0: start: / next: 3 key: "b" value: 1
// 1: start: 1 next: 0 key: "a" value: 1
// 2: start: 2 next: / key: "c" value: 2
// 3: start: 4 next: / key: "d" value: 1
// 4: start: / next: / key: "e" value: 3

Algorithms sketch:

class Bucket<K, V> {
  K key = null;
  V value = null;
  Bucket<K, V> next = null;
  Bucket<K, V> start = null;
}

Bucket<K, V> buckets[] = ...;
// initialize buckets[] with empty buckets

V get(K key) {
  Bucket<K, V> b = buckets[hash(key)].start;
  for (; b != null; b = b.next) {
    if (b.key == key) return b.value;
  }
  throw ...;
}

void put(K key, V value) {
  Bucket<K, V> b = buckets[hash(key)];

  // case: first item in bucket
  if (b.start == null) {
    b.key = key;
    b.value = value;
    b.start = b;
    return;
  }

  // find bucket with key
  Bucket<K, V> p = null;
  b = b.start;
  for (; b != null; p = b, b = b.next) {
    // overwrite entry
    if (b.key == key) {
      b.value = value;
      return;
    }
  }

  // enter a new bucket into this list:
  b = getNextFreeBucket();
  p.next = b;
  b.key = key;
  b.value = value;
}

void delete(K key) {
  Bucket<K, V> p = null;
  Bucket<K, V> b = buckets[hash(key)].start;
  for (; b != null; p = b, b = b.next) {
    if (b.key == key) {
      b.key = null;
      b.value = null;
      if (p != null) p.next = b.next;
      b.next = null;
      return;
    }
  }
}