BUG: CategoricalIndex allowed reindexing duplicate sources
For consistency with normal indexes, `CategoricalIndex.reindex` should allow targets to be duplicated but not the sources. However, currently in allows the source to be duplicated but not the targets, which is exactly the wrong behaviour.

Most of the work here is fixing the tests, which in many cases explicitly check for the incorrect behaviour.

Fixes #25459 

(I can't run the full testsuite on my machine but the relevant categorical tests do seem to pass. Hoping that the GitHub CI infrastructure will pick up any other failures.)
Hello @batterseapower! Thanks for updating this PR. We checked the lines you've touched for [PEP 8](https://www.python.org/dev/peps/pep-0008) issues, and found:















There are currently no PEP 8 issues detected in this Pull Request. Cheers! :beers: 

##### Comment last updated at 2019-10-11 09:47:23 UTC Had to fix a couple of incidental Pandas bugs that were surfaced by the main fix.

1) `pd.Index([1, 1, 0, 2, 2]).union(pd.Index([0, 2, -1]))` would fail with an error about duplicates in the index. We now return `pd.Index([-1, ,0 1, 1, 2, 2])` (or `pd.Index([1, 1, 0, 2, 2, -1])` if `sort=False`) which is more consistent with the behaviour of `Index.intersection`

2) `pd.Index(['A', 'B']).get_indexer_non_unique(pd.Index([0]))` would fail, complaining with a `TypeError` about `'<' not supported between instances of 'str' and 'int'`. This is caused by over-aggressive use of `searchsorted`, solved by falling back to linear search Please let me know if this needs more work.. lgtm. cc @jbrockmendel @jschendel if any comments. LGTM thanks @batterseapower 