问:
Designing Message class in Java
I'm writing a class for Message. Message comes with Header and Payload.

Header has following fields:

Version

Type

For Type "XYZ", the following Payloads are allowed.

Configuration

Metafile

where configuration can only be an HashMap of Key, value pairs.
And Metafile can only be a String (file contents)

Will Builder pattern suit here to build a message "Version:123, Type:XYZ, Configuration, HashMap" ? Or what is the best way to model this problem in Java?

答:
First of all, this is not a "problem" which needs "modelling".  This is just a syntax issue.

Secondly, why on earth would you even think of using a builder pattern for this?  Is it perhaps because you read "Clean Code", where on page 35 the author classifies methods into four categories, depending on whether they accept zero, one, two, or the incredibly high number of three arguments, with four arguments being, presumably, unthinkable?  Oh, never mind him, he was just being silly.

Things should be as simple as possible, but not simpler

-Albert Einstein

Methods should accept as few arguments as possible, but not fewer than what they need to do their job.

--Mike Nakis

The builder pattern is generally an overkill for messages, because what you usually want to do with a message is to instantiate it, fill it, and send it on its way using as few lines of code as possible. Ideally, just one line of code.

As a matter of fact, sending a message should look syntactically identical to placing a function call, and the fact that it does not look identical in most mainstream languages is a shortcoming of those languages. What we basically want to do is to place an asynchronous call. The fact that a message is to be used to achieve this is just an implementation detail which should be hidden from us, and the fact that we still have to waste our time dealing with implementation details like constructing, filling, and sending messages, (let alone defining and maintaining entire class hierarchies of messages,) just shows that languages still have a long way to go.

So, in lack of any better mechanisms, the task of instantiating, filling, and sending a message should not be any more complicated than this:

```<code>sendMessage( new MyMessage( 123, XYZ, configuration, metafile ) );
</code>```

Of course, the MyMessage class presumably extends some Message class, (which you are for some reason thinking of as a Header,) so the first statement of the constructor of MyMessage will be as follows:

```<code>super( version, type );
</code>```

Title: Designing Message class in Java

Body:
First of all, this is not a "problem" which needs "modelling".  This is just a syntax issue.

Secondly, why on earth would you even think of using a builder pattern for this?  Is it perhaps because you read "Clean Code", where on page 35 the author classifies methods into four categories, depending on whether they accept zero, one, two, or the incredibly high number of three arguments, with four arguments being, presumably, unthinkable?  Oh, never mind him, he was just being silly.

Things should be as simple as possible, but not simpler

-Albert Einstein

Methods should accept as few arguments as possible, but not fewer than what they need to do their job.

--Mike Nakis

The builder pattern is generally an overkill for messages, because what you usually want to do with a message is to instantiate it, fill it, and send it on its way using as few lines of code as possible. Ideally, just one line of code.

As a matter of fact, sending a message should look syntactically identical to placing a function call, and the fact that it does not look identical in most mainstream languages is a shortcoming of those languages. What we basically want to do is to place an asynchronous call. The fact that a message is to be used to achieve this is just an implementation detail which should be hidden from us, and the fact that we still have to waste our time dealing with implementation details like constructing, filling, and sending messages, (let alone defining and maintaining entire class hierarchies of messages,) just shows that languages still have a long way to go.

So, in lack of any better mechanisms, the task of instantiating, filling, and sending a message should not be any more complicated than this:

sendMessage( new MyMessage( 123, XYZ, configuration, metafile ) );

Of course, the MyMessage class presumably extends some Message class, (which you are for some reason thinking of as a Header,) so the first statement of the constructor of MyMessage will be as follows:

super( version, type );


问:
Can I test effectively javascript functions with a PHP unit-testing framework?
If I want to unit-test some of my javascript functions, would it be more efficient (and doable) to use the already installed PHP unit-testing framework, or should I use a javascript unit-testing framework?

EDIT: It seems I have to clarify things a bit. I'm using javascript for form validation. It seems that some logic doesn't work as I want it to be, and I thought to myself that would be a good point to begin to use unit-testing (something that came to my scope only recently). I already began to use SimpleTest on a little project of mine, but never to test logic that is generated client-side.

Now I know that SimpleTest have the possibility to emulate a browser for example. But I was wondering what other method would they be to unit-test my form validation. While I was searching for idea, I realized that there is also unit-testing framework for javascript, but after a bit of searching on some of the SE sites, I didn't find anything about use of PHP and Javascript Framework together, so I wondered how common such a situation it was, and how do other people manage in such an environment.

答: Why aren't you using Firebug? In particular there is an extension called Firesymfony that integrates PHP debugging support from the Symfony framework but there are other extensions that might be more suitable for what you are trying to do.</p>

ContentLicense: CC BY-SA 3.0

ContentLicense: CC BY-SA 2.5


问:
How do I deal with the following technical issue?
I am a Java Programmer and I am relatively new to Java(1 Year). I am working for a small startup company.

My problem is a bit strange and I am facing it a bit difficult to deal with and explain also.

My director in the company usually assigns some programming tasks on the product we are developing. He is not from Java background, but from databases background. Usually he cares about application configuration and pluggable architecture which is very much desirable.

What according to him is pluggable is obtaining object instances through Java Reflection. Always he insists us to write a class that reads an xml file where it is written which class has to be instantiated and do actual work
from that object instantiated using reflection. I tried to explain about DI frameworks such as Spring and Java EE CDI, but of no use.

And he thinks that whenever an xml file structure is changed, its parsing code or writing code need not be changed. We, the programmers, prefer using JAXB for marshalling and unmarshalling the xmls as it is intuitive.

Very frequently he complains that the code is slow, or the programmers are incapable of providing an architecture that allows absolutely no change in Java code but all changes in xml configuration/data are consumed by the application.

And every single possible decision we make are with his consent regarding finalising the xmls structure. Accordingly we code and develop things. But after some period he finds something else is fascinating and asks us to change the whole structure of the xml. Change in requirements is not a problem, but he thinks Java code need never be changed and keeps blaming that the programmers are incapable of writing code in such a way.

Is it really possible? How do we convince him or explain?

答:
1) Where your manager is right

Your manager wants a flexible architecture. To accomplish this, you have to design our code, that it is easily composed of pluggable components.

What according to him is pluggable is obtaining object instances through Java Reflection

That is a way to organize object creation and is how DI-frameworks do their job.
Typically you mark dependencies of an object using @Inject annotation. I do not see any sense in doing this by hand, when you have frameworks to do the job reliably.

he insists us to write a class that reads an xml file where it is written which class has to be instantiated and do actual reading from that object instantiated using reflection.

Sounds to me, that he wants to develop his own version of Spring with all the legacy pains of using XML for (container) configration

2) Where your manager is (terribly) wrong

And he thinks that whenever an xml file structure is changed, its parsing code or writing code need not be changed.

This sounds like a weird version of the open/closed principle, where a class should be open for extension, but closed for modification.

A better design would be to refactor the parsing behaviour out to an interface. Then you are able to keep your overall logic dealing with the result and handle different types of Parsers with different objects.

If you want to deal with different versions of your XML at the same time, you could design different parsers for each version. But if you only want to deal with a current version of your XML, it would make sense, to only update the code of the one parser, you have.

If you never refactor your code and only pile classes you end with a mess.

We, the programmers, prefer using JAXB for marshalling and unmarshalling the xmls as it is intuitive.

Which is - in short - perfectly fine.

Very frequently he complains that the code is slow, or the programmers are incapable of providing an architecture

As far as I see, the only one providing a messy architecture is your boss. Sorry, bro!
@ddyer gave you a hint, on how to convince your boss: Benchmarks - hard numbers / facts. Rewrite a part of the code and show the differences.

But after some period he finds something else is fascinating and asks us to change the whole structure of the xml.

That's how management (oftentimes) is.

tl;dr

What to do?

In case you want to convice your boss:

If your time allows it, rewrite the application (partially) or at least do a fast prototype which has the core elements of the application, benchmark it, show the numbers to your boss. Perhaps you could do a comparing code review of how the old codebase looks like and the new one. And speak with him about the differences.

But honestly: If you have the possibility - leave the company You are doing yourself a big favour.

This sounds like a very bad environment for productive work. You are the programmer(s) and you are in charge for the codebase not your manager; or if he feels so - and that's what came to my mind reading your story, he should do your job (alone). As a professional software developer you should stand up against your boss. But it depends on the possibilites to get a new job. Perhaps you are in a dilemma of quitting, but having no alternative.


问:
Can you implement "object-oriented" programming without the class keyword?
Say we want to provide an abstraction of an "account" in a bank. Here's one approach, using a function object in Python:

def account():
    """Return a dispatch dictionary representing a bank account.

    >>> a = account()
    >>> a['deposit'](100)
    100
    >>> a['withdraw'](90)
    10
    >>> a['withdraw'](90)
    'Insufficient funds'
    >>> a['balance']
    10
    """
    def withdraw(amount):
        if amount > dispatch['balance']:
            return 'Insufficient funds'
        dispatch['balance'] -= amount
        return dispatch['balance']
    def deposit(amount):
        dispatch['balance'] += amount
        return dispatch['balance']
    dispatch = {'balance': 0,
                'withdraw': withdraw,
                'deposit': deposit}
    return dispatch
```

<p>Here's another approach using type abstraction (i.e., <code>class</code> keyword in Python):</p>

<pre class="lang-py prettyprint-override"><code>class Account(object):
    """A bank account has a balance and an account holder.

    >>> a = Account('John')
    >>> a.deposit(100)
    100
    >>> a.withdraw(90)
    10
    >>> a.withdraw(90)
    'Insufficient funds'
    >>> a.balance
    10
    """

    def __init__(self, account_holder):
        self.balance = 0
        self.holder = account_holder

    def deposit(self, amount):
        """Add amount to balance."""
        self.balance = self.balance + amount
        return self.balance

    def withdraw(self, amount):
        """Subtract amount from balance if funds are available."""
        if amount > self.balance:
            return 'Insufficient funds'
        self.balance = self.balance - amount
        return self.balance
</code>```

My teacher started the topic "Object oriented programming" by introducing the class keyword, and showing us these bullet points:

Object-oriented programming

A method for organizing modular programs:

Abstraction barriers

Message passing

Bundling together information and related behavior

Do you think the first approach would suffice to satisfy the above definition? If yes, why do we need the class keyword to do object-oriented programming?

答:
I would agree that the first definition satisfies the three points your teacher made. I do not think we need the class keyword for anything. Under the covers, what else is an object but a data structure with with different types of data and functions to work with the data? Of course, the functions are data as well..

I would go even further and say that doing object oriented programming is not so much dependent on the keywords your language provides, you can do object oriented programming in C if you so wished! In fact, the linux kernel employs such techniques.

What you can infer from the class keyword here is, that the language provides support for this kind of construct out of the box, and you do not need to through all the hoops to re-implement the functionality yourself(which is pretty fun task in itself!). Not to mention all the syntactic sugar you might get as well.


答:
Congratulations! You rediscovered the well known fact that object orientation can be done without specific programming language support. It is basically the same way objects are introduced in Scheme in this classic text book. Note that Scheme does not have a class keyword or some kind of equivalent, and objects can be created without having even classes.

However, the object orientated paradigm was so successful that lots of languages - and Python is no exception - provide built-in support for it. This is simply to make it easier for developers to use the paradigm and to provide a standard form of object orientation for that language. It is essentially the same reason why lots of languages provide a for loop, though it could be emulated using a while loop with just one or two additional lines of code - simply ease of use.

Title: Can you implement "object-oriented" programming without the class keyword?

Body:
Say we want to provide an abstraction of an "account" in a bank. Here's one approach, using a function object in Python:

def account():
    """Return a dispatch dictionary representing a bank account.

    >>> a = account()
    >>> a['deposit'](100)
    100
    >>> a['withdraw'](90)
    10
    >>> a['withdraw'](90)
    'Insufficient funds'
    >>> a['balance']
    10
    """
    def withdraw(amount):
        if amount > dispatch['balance']:
            return 'Insufficient funds'
        dispatch['balance'] -= amount
        return dispatch['balance']
    def deposit(amount):
        dispatch['balance'] += amount
        return dispatch['balance']
    dispatch = {'balance': 0,
                'withdraw': withdraw,
                'deposit': deposit}
    return dispatch
```

<p>Here's another approach using type abstraction (i.e., <code>class</code> keyword in Python):</p>

<pre class="lang-py prettyprint-override"><code>class Account(object):
    """A bank account has a balance and an account holder.

    >>> a = Account('John')
    >>> a.deposit(100)
    100
    >>> a.withdraw(90)
    10
    >>> a.withdraw(90)
    'Insufficient funds'
    >>> a.balance
    10
    """

    def __init__(self, account_holder):
        self.balance = 0
        self.holder = account_holder

    def deposit(self, amount):
        """Add amount to balance."""
        self.balance = self.balance + amount
        return self.balance

    def withdraw(self, amount):
        """Subtract amount from balance if funds are available."""
        if amount > self.balance:
            return 'Insufficient funds'
        self.balance = self.balance - amount
        return self.balance
</code>```

My teacher started the topic "Object oriented programming" by introducing the class keyword, and showing us these bullet points:

Object-oriented programming

A method for organizing modular programs:

Abstraction barriers

Message passing

Bundling together information and related behavior

Do you think the first approach would suffice to satisfy the above definition? If yes, why do we need the class keyword to do object-oriented programming?


问:
Which are the significant algorithms for humankind in past decades?
Which world most important algorithms have contributed most to humankind in past decades?

I thought this is a good general knowledge for a developer to know about.

Update:

If possible, please keep the answer to a specific programming algorithm.

I would like to get a list of the most important ones, only one algorithm per answer.

Please consider to state why the algorithm is significant and important...

答:
The heap data structure and its associated algorithms for heap construction and maintenance.

And show some respect for quicksort. Even if it is not always the sort of choice, it is one of the fundamental algorithms in the historical development of computer science, and is a great vehicle for understanding recursion and algorithm analysis. It is beautiful, and yes, I love it.


问:
Semantically more appropriate package name than `util` for the following things?
As a strawman consider the package java.util it is a dumping ground for various classes that in most cases do not share anything in common other than the person that put them there was lazy or uninspired to come up with a more semantically correct package name for their class.

As but one example, take the class UUID what would have been a semantically correct package name for that class?

I am working on implementing my own UUID class to be more lightweight. I do not want to use me.myproject.util.UUID for my package name.

I considered me.myproject.rfc4122.UUID but that does not imply the semantic of the use of UUID.

I also considered me.myproject.uuid.UUID but I do not like the tautology in that, even though it is a popular approach in Python to put a class in a module with the same name, and packages in Java are not semantically equivalent to modules in Python.

I also considered me.myproject.UUID but rejected it because I do not want to pollute that part of the namespace with things that are not related. This just moves the problem up a level.

I also considered me.myproject.lib.UUID but this has no more semantic meaning than .util and just renames the problem.

semantics : the branch of linguistics and logic concerned with meaning.

答:
The problem with trying to put each class in a package which has a semantically correct name for that class is that it tends to lead to packages that contain very few classes, or sometimes even just one class.  This in turn leads to a multitude of packages.

A more pragmatic approach to package naming is to simply help you find stuff. Keeping frequently used stuff that you always know where to find all bunched up in one place keeps them out of the way and therefore makes it easier to find the more rarely used stuff.  So, you do not really need package names which are semantically correct for each one of the classes that they contain, you just need package names which are not semantically incorrect.  Obviously, the 'util' package name was chosen according to this line of thinking: it is not the semantically correct name for the classes it contains, but it is also not semantically incorrect, and that's good enough.

So, if this UUID type of yours is destined to only be used by this specific application, (as evidenced by the fact that you are planning to put it under 'myproject',) then it is probably part of the 'model' of your project. You should already have a 'model' package, containing the set of all classes that correspond to your persistent entities, many of which probably have relationships between them, with UUIDs probably being the means of implementing these relationships. Also, your UUIDs probably know how to persist themselves, right?  And also, your UUIDs can probably only be found as members of your model entities, right?  So, your model package is probably the best place for it.

Otherwise, if this UUID type of yours may be used in other projects too, then it needs to be seen as part of some framework.  So, it may live in the root source folder of that framework, or in some 'types' sub-package as MainMa suggested, or even in some sub-package of that framework called 'util' or 'misc'. Nothing wrong with that.


问:
Is is possible to write a "Brainfuck with variables" compiler?
I'm on a quest to write a LISP-ish language that compiles to Brainfuck. Well, it's a stack of intermediate compilers actually. Currently I'm trying to write the one that transforms this code:

a++b+a

into:

++>+<

It's standard Brainfuck, but with variables added.

The compiler is responsible for two things:

Assigning a and b some address in the memory, say, 0 and 1

Translating each occurrence of a and b into a number of <'s or >'s so the memory pointer ends up at the right location

Now, here's the thing: in order for the compiler to know how many <'s to put, it needs to know where the memory pointer currently points to. At first it points to 0, but as the code gets executed, the pointer moves around and to get to a you need to move relatively from where you're at.

So the only way to know the value of the memory pointer would be to execute the code and replace variable names as you go. "Oh, mempoint is now 4, I see an a and it's location is 1 so i need to move three places left: <<<"

If I close my eyes I can hear a voice saying: "you're trying to solve the Halting Problem"

So my question is: am I really? Is there any way around?

答:
Okay, to answer my own question, there is a way around.

Compile time vs. runtime

Calculating the number of <'s statically is indeed impossible, as few people have suggested. Sometimes whether code is executed depends on some input and there's no way around that. An example: ,[>]

So the only way to do it is to search for cells at runtime. If you're able to find the beginning of the memory space (address 0), you can just jump 2 times to the right to get to address 2.

Finding a zero is easy in Brainfuck: [<] # do something here

However, you don't want to stop at some arbitrary cell that happens to have the value 0, you need to make sure it's the actual beginning of the memory zero!

This is really inconvenient. Whichever value you choose to represent the starting address with, it can accidentally show up in the memory.

Dividing the memory space

So I divided the memory in what I call memory space and value space. Odd cells are values, even cells are "addresses". Well, there're not exactly unique numbers identifying cells, but more of a "ladder" that you use to move around.

Here's the layout of the memory, after it's mapped:

memory = [0, 0, 1, 0, 1, 0 ...]
     start ^     ^ addr   ^ value

Now every time you search for a location, you go left < once to enter the address space, then loop until you find a zero, then move right n times.

This schema requires you to fill the memory with alternating 1's and 0's before the program is executed. Given a fixed memory size, the compiler can generate code that does this for you.

This solution is not perfect. To begin with, you lose half of the memory. Filling it up with 1's is also annoying and costs you time at the start of each program.

Appendix: marking the start with a "1"

You might be thinking: why not invert the schema and mark address zero with a 1 and leave all other addresses to be 0? That way you don't need to fill up the memory with 1's.

Let's try.

The code we need, translated into words would be:

go left one cell to enter the address space

if the value is 0, then move left 2 cells (keep searching)

else (you've reached the start) go right N places

You need to write an if / then / else construct. In Brainfuck this means copying some values to temporary locations (we've got plenty of those!) then executing the correct branch, then cleaning up.

But in our case "executing the code" means "go to some other location and never come back" so it's impossible to clean up the temporary variables. And if they're not 0 you won't find the start again.

I tried to find a way around this but I couldn't.

Here's the code for the compiler: https://gist.github.com/whoeverest/3b15f2a06fc32333f342


问:
Getters with data conversion in Java VOs
I am working on a standard Spring application where DAO layer returns entities to service layer and service layer returns VOs to other services and controllers.

In a certain scenario, we have a VO that looks like this:

```<code>public class MyContainerVO{
    private Integer containerId;
    private String containerName;
    private List<ContainerChild> childList;

    //usual setters and setters

    public Map<String,String> getChildMap(){
        //creates a K,V map from the child list
        //with the key being child.getName() and value being child.getId()
    }
}
</code>```

I am confused whether this method getChildMap() should be in MyContainerVO or should it be moved to a utility class. I know that there should not be any business logic in the VO, but in my opinion the getChildMap() method only returns the data contained in MyContainerVO in a different format and thus does not qualify as business logic.

I could not find any answers in SO or programmers that deals with such scenario; most are about business logic in VOs that hit other classes creating close coupling which is a bad practice.

Kindly suggest what is the best approach in this scenario, or please point out some link that explains this in detail.

答:
On the first sight I think it should stay in the Value Object because of cohesion and encapsulation principles - getChildMap() method implementation is intimately connected to the implementation of MyContainerVO object so it should stay inside this object without necessarily exposing the implementation details (childList).

The problem here is that it's not really clear what MyContainerVO is and how is it used. For example, if List childList is commonly used outside of the MyContainerVO and we often need to get its childMap, we could make a case for creating Utility method for the conversion to map and use it everywhere to be consistent ... (or maybe creating Value Object just for this childList which would contain this method).


答:
Purpose of packages is to group classes according to some criteria (package by type/layer vs. package by feature etc.). I don't really see a point to create package for just one class - especially if you don't expect there will be other classes in this package in the future.

Also I think that "util" package name is not totally meaningless - it just groups classes by a specific criteria - for me "util" class means that it is not part of the domain of the application, but it's also not a part of the framework (it doesn't influence structure of the application). It's basically just an extension of (non)standard library.

In this case I wouldn't have a problem with putting this UUID class into "util" package. If there will be some other UUID-related utility classes (like separate class for generating UUIDs), it's easy to refactor and create "util.uuid" package for them (unless you're creating a library and UUID will be part of exposed interface, then you need to be a little bit "forward-thinking").

Title: Semantically more appropriate package name than `util` for the following things?

Body:
As a strawman consider the package java.util it is a dumping ground for various classes that in most cases do not share anything in common other than the person that put them there was lazy or uninspired to come up with a more semantically correct package name for their class.

As but one example, take the class UUID what would have been a semantically correct package name for that class?

I am working on implementing my own UUID class to be more lightweight. I do not want to use me.myproject.util.UUID for my package name.

I considered me.myproject.rfc4122.UUID but that does not imply the semantic of the use of UUID.

I also considered me.myproject.uuid.UUID but I do not like the tautology in that, even though it is a popular approach in Python to put a class in a module with the same name, and packages in Java are not semantically equivalent to modules in Python.

I also considered me.myproject.UUID but rejected it because I do not want to pollute that part of the namespace with things that are not related. This just moves the problem up a level.

I also considered me.myproject.lib.UUID but this has no more semantic meaning than .util and just renames the problem.

semantics : the branch of linguistics and logic concerned with meaning.


问:
Domain driven design, can two aggregates have the same root?
For the purpose of separating different functionality into different classes, I have two following Aggregates:

ActiveEmployee

AssignTask ()

ReassignManager ()

Deactivate (string reason)

InactiveEmployee

GetReasonForDeactivation ()

Reinstate ()

Both aggregates share the same root, dbo.Employee.

EmployeeID servers as a primary key for both Aggregates.

The repository instantiates the first one, or the second one based on a boolean flag dbo.Employee.IsActive.

Since I follow the rule that only one aggregate can be modified in one transaction, I will never encounter a situation where I load both aggregates with same ID, ending up with InactiveEmployee with ID 3 and ActiveEmployee with ID 3 in same transaction.

Is this good DDD? Does DDD allow for having two aggregates with same root?
Can we differentiate Aggregate types based on a flag?

UPDATE 1:

When I said that both aggregates share the same root, what I meant was that both Aggregates represent a row in dbo.Employee table.

In my understanding, a root of the Aggregate is the entity which is uniquely defined in our domain. It does not mean that that entity has to exist as a real class, it's identity is what matters. Every other Aggregate that wants to reference Inactive/ActiveEmployee will hold a reference to the EmployeeID, not the reference to object instance.

答:
You need to understand that DDD is not about primary keys, rows or tables - these are just means to implement it.

Aggregate root is usually implemented as a class, because you are expected to access all the functionality and data of the aggregate through the root. It therefore needs to have some behavior, something which primary key of the table can't have. Primary benefit of this is the encapsulation of aggregates - its logic is completely contained inside the aggregate and doesn't leak outside which greatly reduces the coupling (and as a consequence complexity) of the application.

It follows that each aggregate has its own aggregate root, so two aggregates can't have the same root (if they have, there is effectively just one aggregate).

In your case, you probably want to have two independent aggregates (ActiveEmployee, InactiveEmployee) which are backed by the same table (which is fine because it's totally out of DDD's scope). But then remember that there's actually no dbo.Employee entity in your domain model, it's just a table on a lower (persistence) layer.


问:
How to design for good abstractions using algebraic data type?
Every now and then I have peaked at Haskell Tutorials and found the Algebraic data types quite interesting. I took their purpose to be to represent types that have completely separable states. Sadly, I never got to write more Haskell than tutorial level projects, and so I never had to really design programs using this pattern.

Now I am writing some Rust, and I have algebraic datatypes (enums) in the toolbox. However, I am not very confident in using them.

Let me start with an example where I am confident that such an enum is a proper choice.

```<code>enum Tree {
    Leaf(i: String),
    Branch(Tree, Tree)
}
</code>```

The same example would be applicaple for an XML-like structures, etc.

With other data, I am not so confident about using enum types. Let's take a connection object

```<code>enum Connection {
    UnConnected(...),
    ConnectedConnection(....)
}
</code>```

Here we would have a Connection type with two possible values, one representing the state where a connection is not yet established, the other one could represent the state of a connected connection (and wrapping a connection handle for example).

The other possibility would be to introduce 2 types for a Connection-Template and a connected connection.

Another example that I found in rust code is that in the hyper library. There is the type Response that represents a HTTP response. It is a generic type.
Response<Fresh> represents the state where headers are not yet frozen. Once upon it is mapped to a Response<Streaming>, which can be used to write the body of the response. It seems like what Hyper models here with different types (Response<Fresh> vs Response<Streaming>) could have been modeled with enum types as well.

The approach with different types allows for more safety, Response<Fresh> does not implement streaming (I think) and Response<Streamimg> does.

Do you know of guidelines and best practices that guide through modelling logic in types properly?

答:
Even though you said algebraic data types, you seem to mostly be asking about sum types, so I will focus on those.  Product types are more common and more easily understood.

Sum types are most easily understood not by thinking about what you're modeling, but by thinking about the code that uses it.  People tend to think of sum types as representing states that are mutually exclusive, but this isn't the entire picture.  To use a sum type, you should also have a use for the encompassing type.  This represents an indeterminate state, where at the point of calling the function, you know you either have or need one of the term types, but you don't know which one.  If you always know which one statically, you should just create separate types.

For your Tree example, that means you should have functions that actually take or return a Tree.  As you traverse down the tree, you have this state where you don't know if the next node down is going to be a Leaf or a Branch, so you need a type that can be either.  If you only had functions that take or return Leafs or Branches, you wouldn't need a sum type.

Your Connection example is a completely different matter.  At some point, you have a connect function that takes in an Unconnected and returns a Connected.  At some later point, you have a disconnect function that does the reverse.  There is no point where you don't know statically if a connection is connected or not, therefore you don't need a type that can hold either.

If you have a hard time seeing appropriate situations to use sum types, my recommendation is to start out not using them.  If they are appropriate, at some point you'll hit a function that can't be written otherwise, then you can add it then.  Forcing a sum type when it's not needed leads to a lot of unnecessary pattern matching that could be much cleaner with separate functions.


答:
First of all, UUID (with uppercase) seems like a very bad idea for the package name or class name to me, from all the styles enforced one way or another all uppercase names are associated with the "constants".
Packages are intended to organise stuff, the easiest way to name a package is by the value of the classes that it holds:

you may choose to separate the classes by their bussines value, for example com.example.identifier;

or by their technical value, for example com.example.uuid.

Keep the IT simple


问:
How to best encapsulate features in code and enabling/disabling them at runtime?
I would like to be able to abstract each feature developed by the team in a way that it can be enabled or disabled at runtime by using a distributed shared configuration system. Features are small and deployed daily.

What practices can I use to maintain the code clean and avoid series of if/else cluttering the code ? The codebase is mostly Python, has anybody ever tried using decorators for this purpose ?

答:
So you effectively need (or just want?) to have two source codes for the pre-ticket and post-ticket situation - e.g. ticket modified behavior of one method, so you ideally want to be able to switch from the former implementation (pre-ticket) of the method to the new (post-ticket) implementation.

This can be done using polymorphism - you have some e.g. service class with some method - ticket changes the method - you do this by creating subclass of this service, override the method and change the implementation. Depending on the switch, you use either former class or new subclass. This switching can be done using e.g. DI injection, where classes are instantiated depending on the configuration. Because you need to be able to do switches in the runtime, you probably need to use proxies instead of real implementations as the injected dependencies.

Of course, things are more difficult once the application has some state. If you modify the classes with state, you need to be able to convert all instances from the old class to the new class and vice versa in runtime - that means you need to have some converters (for both ways), some global registry of all objects, and conversion process should probably be atomic (e.g. you need to "stop the world" of the application until conversion is complete) to ensure that there won't be any problems in the transition period.

Then there's the problem that tickets are often not independent from each other - what if ticket 1 modified method helloWorld(), week after ticket 2 modified the same method. First question is - on what base class did it implement the functionality - probably on the subclass from the ticket 1. Then you can turn off ticket 1 and enable ticket 2 - you have dependency between these tickets which should be somehow resolved (otherwise you can have broken system).

In the real world - this is crazy and don't do this. Feature switching is normal practice, but on a very different scale and granularity - sometimes parts of the functionality (modules) are switched on or off based on licensing, sometimes parts of the system have multiple implementation strategies, but these cases are usually well defined and justified and even then they are far from free in the terms of increased complexity, testing etc.


问:
Would it be good to have a readonly modifier for method level variables?
In C# you can use the readonly modifier for a class level field to indicate (to comipler and other DEVS) that once set it cannot be changed.

I'd quite like for the ability to mark a variable declared in a method to be readonly, so once set it cannot be changed.

Is there a way to do this? If not would be a good feature of C# or does it indicate that I my code is poorly constructed if I am wanting it?

Example:

```<code>public void DoSomthingGreat(string username)
{
    readonly bool isAdmin = GetTheIsAdminStateforUser(username);

    // do some stuff
    // now ask if the user is admin before doing something else,
    // knowing that the flag shouldn't have been changed by another DEV!
    if (isAdmin)
    {
        // Do some other stuff that only admins can do
    }
}
</code>```

答:
Java has this in the form of "final" modifier which can be used also on local variables.
It is definitely much less useful than final/readonly class-level fields, but whether it is useful at all is a matter of debate and personal style/preference.

On one hand, it can be used to guard against accidental assignments/typos, especially in more complicated methods (which should be arguably broken up/simplified anyway), on the other hand it brings a visual clutter to the source code. It would be much better if variables were readonly by default and you had to use modifier to enable its mutability.

One good use is to add final to local variables in complex/spaghetti code as the first step to reason about, understand and refactor bad code - it's not very invasive and it still provides some useful invariants about the code. In the well-designed code composed of short methods, benefits are smaller because you should be able to see what's going on on the first sight ...

From what I've seen, majority of Java code doesn't use final for local variables. Some major projects (e.g. Apache Http Client) use it though ...


问:
Lesser of two evils regarding return types
I'm implementing a system in PHP where values are represented with objects that implement an Amount interface.  I'm building two different implementations of this interface, one using a simple integer internally to represent the value being stored, and the other using GMP objects.

The interface method that's proving a sticking point is as follows:

```<code>/**
 * Get the amount being stored
 *
 * @return number
 */
public function getAmount ();
</code>```

(If you're not familiar with PHP documentation conventions, number means any type which can be considered numeric, which would mean either an integer or a float)

The idea is that in most cases the integer implementation will be used for performance and memory usage reasons, and you would only switch to the GMP implementation when number sizes start exceeding what you can put in an integer.  Overflow could be handled like this (in psuedo-code):

```<code>try
{
    $someAmount -> add ($otherAmount);
}
catch (OverFlowException $e)
{
    // Replace the overflowed Amount object with a BigAmount
    $someAmount = new BigAmount ($someAmount -> getValue ());

    // Retry the add
    $someAmount -> add ($otherAmount);
}
</code>```

My integer based implementation is very simple:

```<code>/**
 * @return integer
 */
public function getAmount ()
{
    return $this -> amount;
}
</code>```

However, as I started to implement the GMP version things started getting complicated:

```<code>/**
 * Get the amount as an integer or string
 *
 * This method will attempt to return the current value as an integer. If
 * the value being represented is beyond the range of a PHP integer then
 * it will return a string instead.
 *
 * @return number|string
 */
public function getAmount ()
{
    // If the value is within integer range then return an int
    if ((gmp_cmp ($this -> amount, PHP_INT_MAX) < 1)
    && (gmp_cmp ($this -> amount, PHP_INT_MAX * -1 - 1) > -1))
    {
        return gmp_intval ($this -> amount);
    } else {
        return gmp_strval ($this -> amount);
    }
}
</code>```

As I was implementing this, I realised it had some problems:

It doesn't always return the same type (resulting in a violation of the principle of least surprise)

It doesn't strictly conform to its interface (Also violating least surprise)

Getters are supposed to be extremely simple and this isn't

The obvious first solution was to simply return the GMP object, but that would mean that the object would never return what its interface says it should, and that this class would be returning objects instead of primitive types like the integer implementation does.

The second solution was for the getter to always return a string.  This would be only slightly more complex than returning the GMP object, and it would mean a primitive type was being returned, but we're still not conforming to the interface.

A third solution would be to have the getter throw an exception if the value can't be returned as an integer and provide an additional method for getting the value as a string.  This would fulfil the contract of the interface (if I changed the interface to indicate that an exception could be thrown if the value can't be returned as an integer), but would add an additional burden on programmers using the classes to deal with having to handle cases where numbers are too big for integers.

So in summary, I have a number of choices, none completely ideal:

Stick with the current solution, and have a method that can return different types

Have the method always return a GMP (which is not a primitive type and not the type the interface says)

Have the method always return a string (which is a primitive type but not the type the interface says)

Throw an exception if an integer can't be returned and supply an additional method for those cases (which meets the demands of the interface but would add requirements to handle it in consuming code)

Which approach would you consider to be best (or least worst), or is there another approach I've not considered?

答:
First 3 options break Liskov's substitution principle. Fourth one complicates the interface for the client.

Personally I think the easiest solution would be to declare the getAmount() method that it returns always string - then it works with both integer-based and GMP-based implementations.

Alternatively this might be a case of premature optimization - maybe it's just fine to compute everything in GMP and return GMP object always (of course interface should be declared accordingly).


问:
Expressing interface inheritance in natural language
In object-oriented programming, when you extend a class you establish an is-a relationship between a new subtype and its parent(s), i.e. B is an A (aka code inheritance). When you compose a class with the help of existing types, you establish a has-a relationship between the newly composed type and the types it comprises, i.e. B has an A (aka object composition).

In many languages (e.g. Java), you have yet another way of defining types, namely by means of interface inheritance. How does one express this notion in natural everyday language?

For example, when a class B implements interface A in Java, do you also say that B is an A? Or do you express this concept differently? E.g. B implements Serizalizable, therfore B is serializable (or in other words: B has the attribute of being serializable).

In asking this question, I am not so much interested in the theoretic differences between these OO concepts (for which topic there are already sufficiently many questions) but rather the differences between them when expressing them in natural language (for which topic there don't seem to be any questions available yet).

答:
Extending a class is not necessarily "code inheritance". If A is an abstract base class or an interface, then making B a subclass of it means it only inherits the interface of A. If A is concrete, then B would inherit the interface and maybe some code, depending on what B chooses to override.

So I believe the correct answer to your question is that inheriting from an interface, a concrete base class or an abstract base class would all result in an "is-a" relationship.

It may help to look up the Liskov Substitution Principle, as that is essentially the thorough, formal definition of what an "is-a relationship" is supposed to be.


问:
Why isn't gettext parameterized?
Currently:

translators are exposed to programming language detail

text is programming language specific (%s)

translators cannot change ordering of strings (for example: family name comes first in hungarian)

printf(gettext("My name is %s %s."), first, family);

msgid "My name is %s %s."

msgstr "A nevem %s %s."

Why not like this:

printf(gettext("My name is Peter Smith.",[("Peter",first),("Smith",family)]));

msgid "My name is Peter Smith." with "Peter","Smith"

msgstr "A nevem Smith Peter."

GUI can highlight that Smith and Peter are parameter-names and check their presence. One could use givenname and familyname instead.

Would this have much worse performance? Any other issue I overlooked?

答:
Proper localization is incredibly difficult. E.g. many languages feature complicated rules for declension that might change the root of the word, or depends on the grammatical gender of that word in the target language. My primary language is German, where articles are gendered. So a template "I'm holding a %s" would need to have three different German forms:

"Ich halte eine %s" for feminine words such as Blume (flower).

"Ich halte einen %s" for masculine words such as Schlüssel (key).

"Ich halte ein %s" for neutral words such as Band (ribbon).

In fact, the English indefinite article a/an depends on the starting sound of the following word, so even this case is difficult to represent in a localization system without a complicated rule engine.
Even within the indo-germanic group of languages (which share common grammatical features), there are unique cases that make it impossible to have a simple substitution-based translation tool.

So, can we have an ideal translation tool? Yes, by using a proper programming language rather than a substitution-based system. In such an architecture, we would associate each message key with a callback that is responsible for returning a properly localized string with equivalent meaning, depending on the context information passed into that callback. Unfortunately, this requires the translators to be programmers, and the language to have decent support for callbacks. Switching the language is not as simple as reading from a different translation file, instead it probably requires us to dynamically link to another library.

All of this complication is a good argument for not using perfect solutions, and rather doing something that works sufficiently well in most cases, especially when this translation engine has to work within the restrictions of C. If gettext were parameterized and included a complex template engine – it would still struggle to properly portray the whole wealth of human languages.

Names are a whole chapter of their own on difficulties of localization – partially because quite a lot cultures place the “family name” before the “given name”, but mostly because many people don't have exactly two names that fit exactly these two roles. 40 Falsehoods Programmers Believe About Names is an entertaining read on this topic. In the context of software systems, it would be best to stop distinguishing first and family names except as needed for legal reasons, and rather use a display name that contains the full name in any order or formatting that person prefers. Note that the correct name order depends on the person carrying that name, not on the context in which that name is being displayed in.

Title: Why isn't gettext parameterized?


问:
Understanding Bob Martin's Closed For Modification Explanation

“Closed for modification.” Extending the behavior of a module does not
  result in changes to the source or binary code of the module. The
  binary executable version of the module, whether in a linkable
  library, a DLL, or a Java .jar, remains untouched.

Hall, Gary McLean (2014-10-10). Adaptive Code via C#: Agile coding
  with design patterns and SOLID principles (Developer Reference) (p.
  208). Pearson Education. Kindle Edition.

In Adaptive Code via C#, the author quotes Robert C. Martin's explanation for Closed for Modification. How should we understand "The binary executable version of the module, whether in a linkable library, a DLL, or a Java .jar, remains untouched."

We can use staircase patterns for dependency tree in which interfaces and implementations are in different assemblies, and we can extend implementations in different assemblies, but not sure how reasonable this is. I don't think copying over the rest of the behavior to the new assembly makes sense. Can someone please visualize this explanation with an example.

答:
Can someone please visualize this explanation with an example.

Think of the strategy pattern, dependency injection etc. A simple example would be a logger which uses an interface for the actual output.

Once you defined the "business logic" of checking the correct loglevel etc, this class would live - once it is bug free - forever untouched. And since you abstracted the output-behaviour away, you could inject different implementations of output:

output to a file

output to an eventlog

logging to a database

logging in JSON-format

logging in XML

loging in BSON

The actual logger is closed for modification; it doesn't need to be modified.
New behaviour could be implemented via dependency injection.


答:
How does one express this notion in natural everyday language?

To make it short:

class inheritance describes a family of objects. In language terms, think of nouns.

Think of: vehicle, cars and bikes.

interface inheritance describes a set of unrelated objects, sharing common behaviour. In language terms think of adjectives.

Think of: able to fly, able to run etc.

Title: Expressing interface inheritance in natural language

Body:
In object-oriented programming, when you extend a class you establish an is-a relationship between a new subtype and its parent(s), i.e. B is an A (aka code inheritance). When you compose a class with the help of existing types, you establish a has-a relationship between the newly composed type and the types it comprises, i.e. B has an A (aka object composition).

In many languages (e.g. Java), you have yet another way of defining types, namely by means of interface inheritance. How does one express this notion in natural everyday language?

For example, when a class B implements interface A in Java, do you also say that B is an A? Or do you express this concept differently? E.g. B implements Serizalizable, therfore B is serializable (or in other words: B has the attribute of being serializable).

In asking this question, I am not so much interested in the theoretic differences between these OO concepts (for which topic there are already sufficiently many questions) but rather the differences between them when expressing them in natural language (for which topic there don't seem to be any questions available yet).


答:
I would like to be able to abstract each ticket developed by the team in a way that it can be enabled or disabled at runtime by using a distributed shared configuration system.

Ideally yes, everything. I won't go down this path, but I think being able to toggle immediately any change, at runtime, is a very powerful feature. I am just wondering if anybody had ever tried and has some experience to share.

Don't do this! Really!

1) There is no sense in doing so

What is the reason behind feature-toggling a bugfix? Does anybody want the errorneous behaviour back? I do not think so.

2) You end up cluttering your code with many unnecessary feature toggles and unmaintainable configuration.

3) Your code becomes as a whole a moving target. The more feature toggles you have,the greater is the risk of side effects from a bad constellation of different features / bugfixes toggled on/off.

To get me right: Feature toggles by itself are useful - no doubt.

I am not advocating against the toggles, but against using it for literally every change.

Title: How to best encapsulate features in code and enabling/disabling them at runtime?

Body:
I would like to be able to abstract each feature developed by the team in a way that it can be enabled or disabled at runtime by using a distributed shared configuration system. Features are small and deployed daily.

What practices can I use to maintain the code clean and avoid series of if/else cluttering the code ? The codebase is mostly Python, has anybody ever tried using decorators for this purpose ?


问:
Dijkstra function for navigation for disadvantaged
Is there a way we can write a function for Dijkstra to determine which node to enqueue and which to discard. This is for a navigation solution for people with disabilities where path to stairs may be shorter but not preferable to wheelchair bound individuals. The navigation solution should also support all individuals and only give a path discarding stairs if the specified user group is someone who is wheelchair bound etc. So basically i am attempting to write a function that checks if user group = wheelchair bound then removes the shortest path to stairs and gives the path to the nearest elevator. I am pretty new to this so any assistance would be very much appreciated.</p>

答:
Whenever you consider an edge for the first time in the algorithm, you determine which "distance" should be assumed for that edge. If the edge contains stairs, you adjust the "distance" accordingly, with much different adjustments for cars, bicycles, pedestrians, wheelchair users.

If the adjustment is difficult, you may postpone it and calculate the shortest path ignoring adjustments. Then if the shortest path contains any tricky edge (like stairs), you adjust the distance for that edge and repeat the whole calculation. So in the case that there are many stairs that are not on the shortest path anyway, you ignore them.

I wouldn't remove these edges from the graph, but just give them a reasonable penalty in the distance. Consider the situation where there is no way from A to B without stairs, but one stairs has ten steps and one has five steps. Or one path that is ten meters with stairs, and another that is ten miles without stairs.


问:
Kth selection routine - Floyd Algorithm 489
I have recently come across a promising Kth selection routine that reportedly outperforms quickselect the Floyd, Rivest Select routine.  This Wikipedia article provides a pseudocode version which I tried to translate to C.

The link to the actual paper with the code in ALGOL.

This is my translation of the code

```<code>void select(float array[], int left, int right, int k)
{
 #define sign(x) ((x > 0.0) ? 1 : ((x < 0.0) ? (-1) : 0))
 #define F_SWAP(a,b) { float temp=(a);(a)=(b);(b)=temp; }

    int n, i, j, ll, rr;
    int s, sd;
    float z, t;

    while (right > left)
    {
        // use select recursively to sample a smaller set of size s
        // the arbitrary constants 600 and 0.5 are used in the original
        // version to minimize execution time

        if (right - left > 600)
        {
            n = right - left + 1;
            i = k - left + 1;
            z = log(n);
            s = 0.5 * exp(2 * z/3);
            sd = 0.5 * sqrt(z * s * (n - s)/n) * sign(i - n/2);
            ll = max(left, k - i * s/n + sd);
            rr = min(right, k + (n - i) * s/n + sd);
            select(array, ll, rr, k);
        }
        // partition the elements between left and right around t
        t = array[k];
        i = left;
        j = right;

        F_SWAP(array[left],array[k]);

        if (array[right] > t)
        {
            F_SWAP(array[right],array[left]);//swap array[right] and array[left]
        }

        while (i < j)
        {
            F_SWAP(array[i],array[j]);
            i = i + 1;
            j = j -1;

            while (array[i] < t)
            {
                i = i + 1;
            }

            while (array[j] > t)
            {
                j = j - 1;
            }
        }

        if (array[left] == t)
        {
            F_SWAP (array[left], array[j])
        }
        else
        {
            j = j + 1;
            F_SWAP (array[j],array[right])
        }

        // adjust left and right towards the boundaries of the subset
        // containing the (k - left + 1)th smallest element
        if (j <= k)
        {
            left = j + 1;
        }
        if (k <= j)
        {
            right = j - 1;
        }
    }
 #undef sign
 #undef F_SWAP
}
</code>```

It seems to work ok, however, I have many questions about this routine which puzzle me.

First, according to what I have read, this routine is supposed to be faster than Hoare's QuickSelect and Wirth's Selection algorithms.  However, in my code it seems to be slower.

What exactly are the magic numbers 600 and .5 doing here? The pseudocode explains that they are arbitrary constants to minimize execution time.  Was that specific to the ALGOL language?

What exactly are the log, exponential, square root and Sigma performing to actually find the Kth position?

I think that the performance problem I am experiencing with my translation of this routine is probably due to exponent and logarithm.

答:
After fidgeting around with the code a bit, I've got some better results.  I went back to the original paper and ignored the wikipedia page.  I've compared the algorithm to other quick select routines with some great results.

Ok, here are the methods I have been playing with.  Note these are for floating point and also that I changed my method from a void.

Quick Select ver 1

```<code>float quickselect(float *arr, int length, int kTHvalue)
{
 #define F_SWAP(a, b) { tmp = arr[a]; arr[a] = arr[b]; arr[b] = tmp; }
    int i, st;
    float tmp;

    for (st = i = 0; i < length - 1; i++)
    {
        if (arr[i] > arr[length-1]) continue;
        F_SWAP(i, st);
        st++;
    }

    F_SWAP(length-1, st);
 #undef F_SWAP
    return kTHvalue == st   ?arr[st]
    :st > kTHvalue  ? quickselect(arr, st, kTHvalue)
        : quickselect(arr + st, length - st, kTHvalue - st);

}
</code>```

I think the original source is Rosetta code.  It works rather quickly, but after looking at some other codes, another quick select function was written.

Quick Select ver 2

```<code>float quickselect2(float *arr, int length, int kthLargest)
{
 #define F_SWAP(a, b) { tmp = a; a = b; b = tmp; }
    int left = 0;
    int right = length - 1;
    int pos;
    float tmp;

    for (int j = left; j < right; j++)
    {
        float pivot = arr[kthLargest];
        F_SWAP(arr[kthLargest], arr[right]);

        for (int i = pos = left; i < right; i++)
        {
            if (arr[i] < pivot)
            {
                F_SWAP(arr[i], arr[pos]);
                pos++;
            }
        }
        F_SWAP(arr[right], arr[pos]);
 #undef F_SWAP
        if (pos == kthLargest) break;
        if (pos < kthLargest) left = pos + 1;
        else right = pos - 1;
    }
    return arr[kthLargest];
}
</code>```

I looked around and found yet another quick select that had some good promise.  It was a quick select with a Median of 3

```<code>float quickselect_MO3(float *arr, const int length, const int kTHvalue)
{
 #define F_SWAP(a,b) { float temp=(a);(a)=(b);(b)=temp; }

    unsigned int low = 0;
    unsigned int high = length - 1;
    for (unsigned int j = low; j < high; j++)
    {

        if (high <= low) // One element only
            return arr[kTHvalue];

        if (high == low + 1)
        {  // Two elements only
            if (arr[low] > arr[high])
                F_SWAP(arr[low], arr[high]);
            return arr[kTHvalue];
        }

        //median of 3
        int middle = (low + high) / 2;
        if (arr[middle] > arr[high])
            F_SWAP(arr[middle], arr[high]);
        if (arr[low] > arr[high])
            F_SWAP(arr[low], arr[high]);
        if (arr[middle] > arr[low])
            F_SWAP(arr[middle], arr[low]);

        // Swap low item (now in position middle) into position (low+1)
        F_SWAP(arr[middle], arr[low+1]);

        // Nibble from each end towards middle, swapping items when stuck
        unsigned int ll = low + 1;
        unsigned int hh = high - 1;//unsigned int hh = high;

        for (unsigned int k = ll; k < hh; k++)
        {
            do ll++; while (arr[low] > arr[ll]);
            do hh--; while (arr[hh] > arr[low]);

            if (hh < ll)
                break;

            F_SWAP(arr[ll], arr[hh]);
        }

        // Swap middle item (in position low) back into correct position
        F_SWAP(arr[low], arr[hh]);

        // Re-set active partition
        if (hh <= kTHvalue)
            low = ll;
        if (hh >= kTHvalue)
            high = hh - 1;
    }
 #undef F_SWAP
}
</code>```

The Median of 3 is fast and rather impressive.

Next, with my rewritten (from the original ALGOL converted in the paper) Floyd Routine.

the Floyd median function ver 1

```<code>float select(float array[], int left, int right, int k)
{
 #define sign(x) ((x > 0.0) ? 1 : ((x < 0.0) ? (-1) : 0))
 #define F_SWAP(a,b) { float temp=(a);(a)=(b);(b)=temp; }

    int i;
    right = right - 1;

    while (right > left)
    {
        // use select recursively to sample a smaller set of size s
        // the arbitrary constants 600 and 0.5 are used in the original
        // version to minimize execution time

        if (right - left > right)
        {
            int n = right - left + 1;
            i = k - left + 1;
            float z = logf(n);
            float s = 0.5 * expf(2 * z/3);
            float sd = 0.5 * sqrtf(z * s * (n - s) / n) * sign(i - n / 2);
            int ll = max(left, k - 1 * s/n + sd);
            int rr = min(right, k + (n - 1) * s/n + sd);
            select(array, ll, rr, k);
        }
        // partition the elements between left and right around t
        float t = array[k];
        i = left;
        int j = right;

        F_SWAP(array[left],array[k]);

        if (array[right] > t)
        {
            F_SWAP(array[right],array[left]);
        }

        while (i < j)
        {
            F_SWAP(array[i],array[j]);
            i++;
            j--;

            while (array[i] < t)
            {
                i++;
            }

            while (array[j] > t)
            {
                j--;
            }
        }

        if (array[left] == t)
        {
            F_SWAP (array[left], array[j])
        }
        else
        {
            j++;
            F_SWAP (array[j],array[right])
        }

        // adjust left and right towards the boundaries of the subset
        // containing the (k - left + 1)th smallest element
        if (j <= k)
        {
            left = j + 1;
        }
        if (k <= j)
        {
            right = j - 1;
        }

    }
    return array[k];
 #undef sign
 #undef F_SWAP
}
</code>```

Finally, I decided to remove the Log function, Exponent and square root functions and got the same output and even a better time.

the Floyd median function ver 2

```<code>float select1(float array[], int left, int right, int k)
{
 #define sign(x) ((x > 0.0) ? 1 : ((x < 0.0) ? (-1) : 0))
 #define F_SWAP(a,b) { float temp=(a);(a)=(b);(b)=temp; }

    int i;
    right = right - 1;

    while (right > left)
    {
        // use select recursively to sample a smaller set of size s
        // the arbitrary constants 600 and 0.5 are used in the original
        // version to minimize execution time

        if (right - left > right)
        {
            int n = right - left + 1;
            i = k - left + 1;
            int s = (2 * n / 3);
            int sd = (n * s * (n - s) / n) * sign(i - n / 2);
            int ll = max(left, k - i * s / n + sd);
            int rr = min(right, k + (n - i) * s / n + sd);
            select1(array, ll, rr, k);
        }
        // partition the elements between left and right around t
        float t = array[k];
        i = left;
        int j = right;

        F_SWAP(array[left],array[k]);

        if (array[right] > t)
        {
            F_SWAP(array[right],array[left]);
        }

        while (i < j)
        {
            F_SWAP(array[i],array[j]);
            i++;
            j--;

            while (array[i] < t)
            {
                i++;
            }

            while (array[j] > t)
            {
                j--;
            }
        }

        if (array[left] == t)
        {
            F_SWAP (array[left], array[j])
        }
        else
        {
            j++;
            F_SWAP (array[j],array[right])
        }

        // adjust left and right towards the boundaries of the subset
        // containing the (k - left + 1)th smallest element
        if (j <= k)
        {
            left = j + 1;
        }
        if (k <= j)
        {
            right = j - 1;
        }

    }
    return array[k];
 #undef sign
 #undef F_SWAP
}
</code>```

Here is a chart of the results

EDIT
I coded the Floyd Routine with the median of 3 and updated the chart. It rates about the same speed as quick select with Median of 3, slightly slower.  It deserves a little more exploration.

```<code>float select3(float array[], int left, int right, int k)
{
 #define sign(x) ((x > 0.0) ? 1 : ((x < 0.0) ? (-1) : 0))
 #define F_SWAP(a,b) { float temp=(a);(a)=(b);(b)=temp; }

    int i;
    right = right - 1;

    while (right > left)
    {
        if( array[k] < array[left] ) F_SWAP(array[left],array[k]);
        if( array[right] < array[left] ) F_SWAP(array[left],array[right]);
        if( array[right] < array[k] ) F_SWAP(array[k],array[right]);

        if (right - left > right)
        {
            int n = right - left + 1;
            i = k - left + 1;
            int s = (2 * n / 3);
            int sd = (n * s * (n - s) / n) * sign(i - n / 2);
            int ll = max(left, k - i * s / n + sd);
            int rr = min(right, k + (n - i) * s / n + sd);
            select1(array, ll, rr, k);
        }
        // partition the elements between left and right around t
        float t = array[k];
        i = left;
        int j = right;

        F_SWAP(array[left],array[k]);

        if (array[right] > t)
        {
            F_SWAP(array[right],array[left]);
        }

        while (i < j)
        {
            F_SWAP(array[i],array[j]);
            i++;
            j--;

            while (array[i] < t)
            {
                i++;
            }

            while (array[j] > t)
            {
                j--;
            }
        }

        if (array[left] == t)
        {
            F_SWAP (array[left], array[j])
        }
        else
        {
            j++;
            F_SWAP (array[j],array[right])
        }

        // adjust left and right towards the boundaries of the subset
        // containing the (k - left + 1)th smallest element
        if (j <= k)
        {
            left = j + 1;
        }
        if (k <= j)
        {
            right = j - 1;
        }

    }
    return array[k];
 #undef sign
 #undef F_SWAP
}
</code>```

As you can see, the Floyd routine is faster than any of the quick selects other than the version with the median of 3.  I don't see why the median of 3 could not be added to the Floyd routine and I will look at that next.  As for the Floyd routine, of course removing the floating point log, exp and sqrt functions speeds up the routine.

I still haven't figured out why Floyd put it there in the first place.

edit 6-7-15
Here is the non-recursive version, runs at the same speed as the recursive version.

```<code>float select7MO3(float array[], const int length, const int kTHvalue)
{
 #define sign(x) ((x > 0) ? 1 : ((x < 0) ? (-1) : 0))
 #define F_SWAP(a,b) { float temp=(a);(a)=(b);(b)=temp; }

    int left = 0;
    int i;
    int right = length - 1;
    int rr = right;
    int ll = left;

    while (right > left)
    {
        if( array[kTHvalue] < array[left] ) F_SWAP(array[left],array[kTHvalue]);
        if( array[right] < array[left] ) F_SWAP(array[left],array[right]);
        if( array[right] < array[kTHvalue] ) F_SWAP(array[kTHvalue],array[right]);

        if ((right - left) > kTHvalue)
        {
            int n = right - left + 1;
            i = kTHvalue - left + 1;
            int s = (2 * n / 3);
            int sd = (n * s * (n - s) / n) * sign(i - n);
            ll = max(left, kTHvalue - i * s / n + sd);
            rr = min(right, kTHvalue + (n - i) * s / n + sd);
        }
        // partition the elements between left and right around t
        float t = array[kTHvalue];
        i = left;
        int j = right;

        F_SWAP(array[left],array[kTHvalue]);

        if (array[right] > t)
        {
            F_SWAP(array[right],array[left]);
        }

        while (i < j)
        {
            F_SWAP(array[i],array[j]);
            i++;
            j--;

            while (array[i] < t)
            {
                i++;
            }

            while (array[j] > t)
            {
                j--;
            }
        }

        if (array[left] == t)
        {
            i--;
            F_SWAP (array[left], array[j])
        }
        else
        {
            j++;
            F_SWAP (array[j],array[right])
        }

        // adjust left and right towards the boundaries of the subset
        // containing the (k - left + 1)th smallest element
        if (j <= kTHvalue)
        {
            left = j + 1;
        }
        else if (kTHvalue <= j)
        {
            right = j - 1;
        }

    }
    return array[kTHvalue];
 #undef sign
 #undef F_SWAP
}
</code>```

edit 6-13-15

I experimented some more with the Floyd selection routine and started to compare his routine against N. Wirth selection routine.  An idea came across, what would happen if I combined his routine with Floyd's routine.  This is what I came up with.

```<code>float FloydWirth_kth(float arr[], const int length, const int kTHvalue)
{
#define F_SWAP(a,b) { float temp=(a);(a)=(b);(b)=temp; }
#define SIGNUM(x) ((x) < 0 ? -1 : ((x) > 0 ? 1 : (x)))

    int left = 0;
    int right = length - 1;
    int left2 = 0;
    int right2 = length - 1;

    //while (left < right)
    while (left < right)
    {
        if( arr[right2] < arr[left2] ) F_SWAP(arr[left2],arr[right2]);
        if( arr[right2] < arr[kTHvalue] ) F_SWAP(arr[kTHvalue],arr[right2]);
        if( arr[kTHvalue] < arr[left2] ) F_SWAP(arr[left2],arr[kTHvalue]);

        int rightleft = right - left;

        if (rightleft < kTHvalue)
        {
            int n = right - left + 1;
            int ii = kTHvalue - left + 1;
            int s = (n + n) / 3;
            int sd = (n * s * (n - s) / n) * SIGNUM(ii - n / 2);
            int left2 = max(left, kTHvalue - ii * s / n + sd);
            int right2 = min(right, kTHvalue + (n - ii) * s / n + sd);
        }

        float x=arr[kTHvalue];

        while ((right2 > kTHvalue) && (left2 < kTHvalue))
        {
            do
            {
                left2++;
            }while (arr[left2] < x);

            do
            {
                right2--;
            }while (arr[right2] > x);

            //F_SWAP(arr[left2],arr[right2]);
            F_SWAP(arr[left2],arr[right2]);
        }
        left2++;
        right2--;

        if (right2 < kTHvalue)
        {
            while (arr[left2]<x)
            {
                left2++;
            }
            left = left2;
            right2 = right;
        }

        if (kTHvalue < left2)
        {
            while (x < arr[right2])
            {
                right2--;
            }

            right = right2;
            left2 = left;
        }

        if( arr[left] < arr[right] ) F_SWAP(arr[right],arr[left]);
    }

#undef F_SWAP
#undef SIGNUM
    return arr[kTHvalue];
}
</code>```

The speed difference is amazing (well at least to me).  Here is a chart showing the speeds of the various routines.

OwnerDisplayName: Andy Dansby

Body:
After fidgeting around with the code a bit, I've got some better results.  I went back to the original paper and ignored the wikipedia page.  I've compared the algorithm to other quick select routines with some great results.

Ok, here are the methods I have been playing with.  Note these are for floating point and also that I changed my method from a void.

Quick Select ver 1

float quickselect(float *arr, int length, int kTHvalue)
{
 #define F_SWAP(a, b) { tmp = arr[a]; arr[a] = arr[b]; arr[b] = tmp; }
    int i, st;
    float tmp;

    for (st = i = 0; i < length - 1; i++)
    {
        if (arr[i] > arr[length-1]) continue;
        F_SWAP(i, st);
        st++;
    }

    F_SWAP(length-1, st);
 #undef F_SWAP
    return kTHvalue == st   ?arr[st]
    :st > kTHvalue  ? quickselect(arr, st, kTHvalue)
        : quickselect(arr + st, length - st, kTHvalue - st);

}

I think the original source is Rosetta code.  It works rather quickly, but after looking at some other codes, another quick select function was written.

Quick Select ver 2

float quickselect2(float *arr, int length, int kthLargest)
{
 #define F_SWAP(a, b) { tmp = a; a = b; b = tmp; }
    int left = 0;
    int right = length - 1;
    int pos;
    float tmp;

    for (int j = left; j < right; j++)
    {
        float pivot = arr[kthLargest];
        F_SWAP(arr[kthLargest], arr[right]);

        for (int i = pos = left; i < right; i++)
        {
            if (arr[i] < pivot)
            {
                F_SWAP(arr[i], arr[pos]);
                pos++;
            }
        }
        F_SWAP(arr[right], arr[pos]);
 #undef F_SWAP
        if (pos == kthLargest) break;
        if (pos < kthLargest) left = pos + 1;
        else right = pos - 1;
    }
    return arr[kthLargest];
}

I looked around and found yet another quick select that had some good promise.  It was a quick select with a Median of 3

float quickselect_MO3(float *arr, const int length, const int kTHvalue)
{
 #define F_SWAP(a,b) { float temp=(a);(a)=(b);(b)=temp; }

    unsigned int low = 0;
    unsigned int high = length - 1;
    for (unsigned int j = low; j < high; j++)
    {

        if (high <= low) // One element only
            return arr[kTHvalue];

        if (high == low + 1)
        {  // Two elements only
            if (arr[low] > arr[high])
                F_SWAP(arr[low], arr[high]);
            return arr[kTHvalue];
        }

        //median of 3
        int middle = (low + high) / 2;
        if (arr[middle] > arr[high])
            F_SWAP(arr[middle], arr[high]);
        if (arr[low] > arr[high])
            F_SWAP(arr[low], arr[high]);
        if (arr[middle] > arr[low])
            F_SWAP(arr[middle], arr[low]);

        // Swap low item (now in position middle) into position (low+1)
        F_SWAP(arr[middle], arr[low+1]);

        // Nibble from each end towards middle, swapping items when stuck
        unsigned int ll = low + 1;
        unsigned int hh = high - 1;//unsigned int hh = high;

        for (unsigned int k = ll; k < hh; k++)
        {
            do ll++; while (arr[low] > arr[ll]);
            do hh--; while (arr[hh] > arr[low]);

            if (hh < ll)
                break;

            F_SWAP(arr[ll], arr[hh]);
        }

        // Swap middle item (in position low) back into correct position
        F_SWAP(arr[low], arr[hh]);

        // Re-set active partition
        if (hh <= kTHvalue)
            low = ll;
        if (hh >= kTHvalue)
            high = hh - 1;
    }
 #undef F_SWAP
}

The Median of 3 is fast and rather impressive.

Next, with my rewritten (from the original ALGOL converted in the paper) Floyd Routine.

the Floyd median function ver 1

float select(float array[], int left, int right, int k)
{
 #define sign(x) ((x > 0.0) ? 1 : ((x < 0.0) ? (-1) : 0))
 #define F_SWAP(a,b) { float temp=(a);(a)=(b);(b)=temp; }

    int i;
    right = right - 1;

    while (right > left)
    {
        // use select recursively to sample a smaller set of size s
        // the arbitrary constants 600 and 0.5 are used in the original
        // version to minimize execution time

        if (right - left > right)
        {
            int n = right - left + 1;
            i = k - left + 1;
            float z = logf(n);
            float s = 0.5 * expf(2 * z/3);
            float sd = 0.5 * sqrtf(z * s * (n - s) / n) * sign(i - n / 2);
            int ll = max(left, k - 1 * s/n + sd);
            int rr = min(right, k + (n - 1) * s/n + sd);
            select(array, ll, rr, k);
        }
        // partition the elements between left and right around t
        float t = array[k];
        i = left;
        int j = right;

        F_SWAP(array[left],array[k]);

        if (array[right] > t)
        {
            F_SWAP(array[right],array[left]);
        }

        while (i < j)
        {
            F_SWAP(array[i],array[j]);
            i++;
            j--;

            while (array[i] < t)
            {
                i++;
            }

            while (array[j] > t)
            {
                j--;
            }
        }

        if (array[left] == t)
        {
            F_SWAP (array[left], array[j])
        }
        else
        {
            j++;
            F_SWAP (array[j],array[right])
        }

        // adjust left and right towards the boundaries of the subset
        // containing the (k - left + 1)th smallest element
        if (j <= k)
        {
            left = j + 1;
        }
        if (k <= j)
        {
            right = j - 1;
        }

    }
    return array[k];
 #undef sign
 #undef F_SWAP
}

Finally, I decided to remove the Log function, Exponent and square root functions and got the same output and even a better time.

the Floyd median function ver 2

float select1(float array[], int left, int right, int k)
{
 #define sign(x) ((x > 0.0) ? 1 : ((x < 0.0) ? (-1) : 0))
 #define F_SWAP(a,b) { float temp=(a);(a)=(b);(b)=temp; }

    int i;
    right = right - 1;

    while (right > left)
    {
        // use select recursively to sample a smaller set of size s
        // the arbitrary constants 600 and 0.5 are used in the original
        // version to minimize execution time

        if (right - left > right)
        {
            int n = right - left + 1;
            i = k - left + 1;
            int s = (2 * n / 3);
            int sd = (n * s * (n - s) / n) * sign(i - n / 2);
            int ll = max(left, k - i * s / n + sd);
            int rr = min(right, k + (n - i) * s / n + sd);
            select1(array, ll, rr, k);
        }
        // partition the elements between left and right around t
        float t = array[k];
        i = left;
        int j = right;

        F_SWAP(array[left],array[k]);

        if (array[right] > t)
        {
            F_SWAP(array[right],array[left]);
        }

        while (i < j)
        {
            F_SWAP(array[i],array[j]);
            i++;
            j--;

            while (array[i] < t)
            {
                i++;
            }

            while (array[j] > t)
            {
                j--;
            }
        }

        if (array[left] == t)
        {
            F_SWAP (array[left], array[j])
        }
        else
        {
            j++;
            F_SWAP (array[j],array[right])
        }

        // adjust left and right towards the boundaries of the subset
        // containing the (k - left + 1)th smallest element
        if (j <= k)
        {
            left = j + 1;
        }
        if (k <= j)
        {
            right = j - 1;
        }

    }
    return array[k];
 #undef sign
 #undef F_SWAP
}

Here is a chart of the results

EDIT
I coded the Floyd Routine with the median of 3 and updated the chart. It rates about the same speed as quick select with Median of 3, slightly slower.  It deserves a little more exploration.

float select3(float array[], int left, int right, int k)
{
 #define sign(x) ((x > 0.0) ? 1 : ((x < 0.0) ? (-1) : 0))
 #define F_SWAP(a,b) { float temp=(a);(a)=(b);(b)=temp; }

    int i;
    right = right - 1;

    while (right > left)
    {
        if( array[k] < array[left] ) F_SWAP(array[left],array[k]);
        if( array[right] < array[left] ) F_SWAP(array[left],array[right]);
        if( array[right] < array[k] ) F_SWAP(array[k],array[right]);

        if (right - left > right)
        {
            int n = right - left + 1;
            i = k - left + 1;
            int s = (2 * n / 3);
            int sd = (n * s * (n - s) / n) * sign(i - n / 2);
            int ll = max(left, k - i * s / n + sd);
            int rr = min(right, k + (n - i) * s / n + sd);
            select1(array, ll, rr, k);
        }
        // partition the elements between left and right around t
        float t = array[k];
        i = left;
        int j = right;

        F_SWAP(array[left],array[k]);

        if (array[right] > t)
        {
            F_SWAP(array[right],array[left]);
        }

        while (i < j)
        {
            F_SWAP(array[i],array[j]);
            i++;
            j--;

            while (array[i] < t)
            {
                i++;
            }

            while (array[j] > t)
            {
                j--;
            }
        }

        if (array[left] == t)
        {
            F_SWAP (array[left], array[j])
        }
        else
        {
            j++;
            F_SWAP (array[j],array[right])
        }

        // adjust left and right towards the boundaries of the subset
        // containing the (k - left + 1)th smallest element
        if (j <= k)
        {
            left = j + 1;
        }
        if (k <= j)
        {
            right = j - 1;
        }

    }
    return array[k];
 #undef sign
 #undef F_SWAP
}

As you can see, the Floyd routine is faster than any of the quick selects other than the version with the median of 3.  I don't see why the median of 3 could not be added to the Floyd routine and I will look at that next.  As for the Floyd routine, of course removing the floating point log, exp and sqrt functions speeds up the routine.

I still haven't figured out why Floyd put it there in the first place.

edit 6-7-15
Here is the non-recursive version, runs at the same speed as the recursive version.

float select7MO3(float array[], const int length, const int kTHvalue)
{
 #define sign(x) ((x > 0) ? 1 : ((x < 0) ? (-1) : 0))
 #define F_SWAP(a,b) { float temp=(a);(a)=(b);(b)=temp; }

    int left = 0;
    int i;
    int right = length - 1;
    int rr = right;
    int ll = left;

    while (right > left)
    {
        if( array[kTHvalue] < array[left] ) F_SWAP(array[left],array[kTHvalue]);
        if( array[right] < array[left] ) F_SWAP(array[left],array[right]);
        if( array[right] < array[kTHvalue] ) F_SWAP(array[kTHvalue],array[right]);

        if ((right - left) > kTHvalue)
        {
            int n = right - left + 1;
            i = kTHvalue - left + 1;
            int s = (2 * n / 3);
            int sd = (n * s * (n - s) / n) * sign(i - n);
            ll = max(left, kTHvalue - i * s / n + sd);
            rr = min(right, kTHvalue + (n - i) * s / n + sd);
        }
        // partition the elements between left and right around t
        float t = array[kTHvalue];
        i = left;
        int j = right;

        F_SWAP(array[left],array[kTHvalue]);

        if (array[right] > t)
        {
            F_SWAP(array[right],array[left]);
        }

        while (i < j)
        {
            F_SWAP(array[i],array[j]);
            i++;
            j--;

            while (array[i] < t)
            {
                i++;
            }

            while (array[j] > t)
            {
                j--;
            }
        }

        if (array[left] == t)
        {
            i--;
            F_SWAP (array[left], array[j])
        }
        else
        {
            j++;
            F_SWAP (array[j],array[right])
        }

        // adjust left and right towards the boundaries of the subset
        // containing the (k - left + 1)th smallest element
        if (j <= kTHvalue)
        {
            left = j + 1;
        }
        else if (kTHvalue <= j)
        {
            right = j - 1;
        }

    }
    return array[kTHvalue];
 #undef sign
 #undef F_SWAP
}

edit 6-13-15

I experimented some more with the Floyd selection routine and started to compare his routine against N. Wirth selection routine.  An idea came across, what would happen if I combined his routine with Floyd's routine.  This is what I came up with.

float FloydWirth_kth(float arr[], const int length, const int kTHvalue)
{
#define F_SWAP(a,b) { float temp=(a);(a)=(b);(b)=temp; }
#define SIGNUM(x) ((x) < 0 ? -1 : ((x) > 0 ? 1 : (x)))

    int left = 0;
    int right = length - 1;
    int left2 = 0;
    int right2 = length - 1;

    //while (left < right)
    while (left < right)
    {
        if( arr[right2] < arr[left2] ) F_SWAP(arr[left2],arr[right2]);
        if( arr[right2] < arr[kTHvalue] ) F_SWAP(arr[kTHvalue],arr[right2]);
        if( arr[kTHvalue] < arr[left2] ) F_SWAP(arr[left2],arr[kTHvalue]);

        int rightleft = right - left;

        if (rightleft < kTHvalue)
        {
            int n = right - left + 1;
            int ii = kTHvalue - left + 1;
            int s = (n + n) / 3;
            int sd = (n * s * (n - s) / n) * SIGNUM(ii - n / 2);
            int left2 = max(left, kTHvalue - ii * s / n + sd);
            int right2 = min(right, kTHvalue + (n - ii) * s / n + sd);
        }

        float x=arr[kTHvalue];

        while ((right2 > kTHvalue) && (left2 < kTHvalue))
        {
            do
            {
                left2++;
            }while (arr[left2] < x);

            do
            {
                right2--;
            }while (arr[right2] > x);

            //F_SWAP(arr[left2],arr[right2]);
            F_SWAP(arr[left2],arr[right2]);
        }
        left2++;
        right2--;

        if (right2 < kTHvalue)
        {
            while (arr[left2]<x)
            {
                left2++;
            }
            left = left2;
            right2 = right;
        }

        if (kTHvalue < left2)
        {
            while (x < arr[right2])
            {
                right2--;
            }

            right = right2;
            left2 = left;
        }

        if( arr[left] < arr[right] ) F_SWAP(arr[right],arr[left]);
    }

#undef F_SWAP
#undef SIGNUM
    return arr[kTHvalue];
}

The speed difference is amazing (well at least to me).  Here is a chart showing the speeds of the various routines.


问:
Is it ever ok to remove the original license from a file
I have a library I maintain. It is a java library that I originally forked from someone else. They added a BSD license statement to the top of EVERY file. Including files that have no real logic.. Like files that only have a property, and a getter & setter for the property.

For example:

```<code>public class Boy {
    private String name;

    public String getName() {
        return this.name;
    }

    public void setName(String name) {
        this.name = name;
    }
}
</code>```

As this library grows sometimes I have to add new properties to the existing files and add new getters and setters to go along with them. This is boring so I wrote some code that will auto generate all of these (lets call them DataObjects). There are literally 1000s of these DataObjects.

I release all my code under Apache 2.0 Since my script is now generating from scratch all of these DataObjects is it OK for me to license these DataObjects as Apache 2.0 with the original creators name removed, or do I have to make sure to leave the license intact for what they created making sure to only add new properties with getters and setters to those files?

Please note I have no intentions of removing their name or license from files that actually contain logic, Im only interested in these DataObjects

答:
Well, let's look at what the BSD license itself says:

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.

Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

Retaining or reproducing the copyright notice is literally the only thing the license requires of you*, so I think it's fairly safe to assume that you should not remove it (unless of course you have express written permission from the original author). Even if this license wasn't legally binding, it might not reflect well on you or your project if you did remove it.

I would just give your script a list of files the original author wrote so it can automagically regenerate the original license statement on them, then use your preferred Apache one on all the new files unique to your project. As far as I know, there's nothing wrong with adding Apache-licensed code alongside BSD-licensed code, since the BSD isn't one of those "infectious" licenses.

Edit: Just to be thorough, the technically correct answer to your question in its most general form is "Yes, if that license does not prohibit it." Most of the open source licenses I know of have a provision specifically saying you cannot do this, so in practice the answer will almost always be "No", but if for some reason you were modifying WTFPL'd software instead, then you would be totally free to throw out the existing license statements.

*You didn't specify which BSD license, so I'm assuming the 2-clause version for this answer. The additional clause in the 3-clause version probably doesn't affect your question.