// Path: src/main/java/com/github/rinde/opt/localsearch/Insertions.java
// public static <T> ImmutableList<T> insert(List<T> originalList,
//     List<Integer> insertionIndices, T item) {
//   checkArgument(!insertionIndices.isEmpty(),
//     "At least one insertion index must be defined.");
//   int prev = 0;
//   final ImmutableList.Builder<T> builder = ImmutableList.<T>builder();
//   for (int i = 0; i < insertionIndices.size(); i++) {
//     final int cur = insertionIndices.get(i);
//     checkArgument(
//       cur >= 0 && cur <= originalList.size(),
//       "The specified indices must be >= 0 and <= %s (list size), it is %s.",
//       originalList.size(), cur);
//     checkArgument(cur >= prev,
//       "The specified indices must be in ascending order. Received %s.",
//       insertionIndices);
//     builder.addAll(originalList.subList(prev, cur));
//     builder.add(item);
//     prev = cur;
//   }
//   builder.addAll(originalList.subList(prev, originalList.size()));
//   return builder.build();
// }
// 
// Path: src/main/java/com/github/rinde/opt/localsearch/Insertions.java
// public static <T> ImmutableList<ImmutableList<T>> insertions(
//     ImmutableList<T> list, T item, int startIndex, int numOfInsertions) {
//   return ImmutableList.copyOf(insertionsIterator(list, item, startIndex,
//     numOfInsertions));
// }
// 
// Path: src/main/java/com/github/rinde/opt/localsearch/Insertions.java
// public static <T> Iterator<ImmutableList<T>> insertionsIterator(
//     ImmutableList<T> list, T item, int startIndex, int numOfInsertions) {
//   checkArgument(startIndex >= 0 && startIndex <= list.size(),
//     "startIndex must be >= 0 and <= %s (list size), it is %s.",
//     list.size(), startIndex);
//   checkArgument(numOfInsertions > 0, "numOfInsertions must be positive.");
//   return Iterators.transform(
//     new InsertionIndexGenerator(numOfInsertions, list.size(), startIndex),
//     new IndexToInsertionTransform<T>(list, item));
// }
// 
// Path: src/main/java/com/github/rinde/opt/localsearch/Insertions.java
// static class InsertionIndexGenerator implements Iterator<IntList> {
//   private final int[] insertionPositions;
//   private final int originalListSize;
//   private final long length;
//   private int index;
// 
//   InsertionIndexGenerator(int numOfInsertions, int listSize, int startIndex) {
//     checkArgument(startIndex <= listSize,
//       "startIndex (%s) must be <= listSize (%s).",
//       startIndex, listSize);
//     insertionPositions = new int[numOfInsertions];
//     for (int i = 0; i < insertionPositions.length; i++) {
//       insertionPositions[i] = startIndex;
//     }
//     originalListSize = listSize;
//     length = multichoose(listSize + 1 - startIndex, numOfInsertions);
//   }
// 
//   @Override
//   public boolean hasNext() {
//     return index < length;
//   }
// 
//   @Override
//   public IntList next() {
//     if (!hasNext()) {
//       throw new NoSuchElementException();
//     }
//     if (index > 0) {
//       for (int i = 0; i < insertionPositions.length; i++) {
//         if (insertionPositions[i] == originalListSize) {
//           insertionPositions[i - 1]++;
//           for (int j = i; j < insertionPositions.length; j++) {
//             insertionPositions[j] = insertionPositions[i - 1];
//           }
//           break;
//         } else if (i == insertionPositions.length - 1) {
//           insertionPositions[i]++;
//         }
//       }
//     }
//     index++;
//     return IntLists.unmodifiable(new IntArrayList(insertionPositions));
//   }
// 
//   @Deprecated
//   @Override
//   public void remove() {
//     throw new UnsupportedOperationException();
//   }
// }


import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableSet;
import it.unimi.dsi.fastutil.ints.IntList;
import static com.github.rinde.opt.localsearch.Insertions.insert;
import static com.github.rinde.opt.localsearch.Insertions.insertions;
import static com.github.rinde.opt.localsearch.Insertions.insertionsIterator;
import static com.google.common.collect.Sets.newHashSet;
import static java.util.Arrays.asList;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
import org.junit.Test;
import com.github.rinde.opt.localsearch.Insertions.InsertionIndexGenerator;
/*
 * Copyright (C) 2013-2016 Rinde van Lon, iMinds-DistriNet, KU Leuven
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *         http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package com.github.rinde.opt.localsearch;






/**
 * @author Rinde van Lon
 *
 */
public class InsertionsTest {

  static final String A = "A";
  static final String B = "B";
  static final String C = "C";
  static final String D = "D";
  static final String Z = "Z";

  /**
   * Tests whether all insertions are created.
   */
  @Test
  public void oneInsertions() {
    List<ImmutableList<String>> strings = insertions(
      ImmutableList.<String>of(), Z, 0, 1);
    assertEquals(1, strings.size());
    assertEquals(asList(Z), strings.get(0));

// Path: src/main/java/com/github/rinde/opt/localsearch/Insertions.java
// public static <T> ImmutableList<T> insert(List<T> originalList,
//     List<Integer> insertionIndices, T item) {
//   checkArgument(!insertionIndices.isEmpty(),
//     "At least one insertion index must be defined.");
//   int prev = 0;
//   final ImmutableList.Builder<T> builder = ImmutableList.<T>builder();
//   for (int i = 0; i < insertionIndices.size(); i++) {
//     final int cur = insertionIndices.get(i);
//     checkArgument(
//       cur >= 0 && cur <= originalList.size(),
//       "The specified indices must be >= 0 and <= %s (list size), it is %s.",
//       originalList.size(), cur);
//     checkArgument(cur >= prev,
//       "The specified indices must be in ascending order. Received %s.",
//       insertionIndices);
//     builder.addAll(originalList.subList(prev, cur));
//     builder.add(item);
//     prev = cur;
//   }
//   builder.addAll(originalList.subList(prev, originalList.size()));
//   return builder.build();
// }
// 
// Path: src/main/java/com/github/rinde/opt/localsearch/Insertions.java
// public static <T> ImmutableList<ImmutableList<T>> insertions(
//     ImmutableList<T> list, T item, int startIndex, int numOfInsertions) {
//   return ImmutableList.copyOf(insertionsIterator(list, item, startIndex,
//     numOfInsertions));
// }
// 
// Path: src/main/java/com/github/rinde/opt/localsearch/Insertions.java
// public static <T> Iterator<ImmutableList<T>> insertionsIterator(
//     ImmutableList<T> list, T item, int startIndex, int numOfInsertions) {
//   checkArgument(startIndex >= 0 && startIndex <= list.size(),
//     "startIndex must be >= 0 and <= %s (list size), it is %s.",
//     list.size(), startIndex);
//   checkArgument(numOfInsertions > 0, "numOfInsertions must be positive.");
//   return Iterators.transform(
//     new InsertionIndexGenerator(numOfInsertions, list.size(), startIndex),
//     new IndexToInsertionTransform<T>(list, item));
// }
// 
// Path: src/main/java/com/github/rinde/opt/localsearch/Insertions.java
// static class InsertionIndexGenerator implements Iterator<IntList> {
//   private final int[] insertionPositions;
//   private final int originalListSize;
//   private final long length;
//   private int index;
// 
//   InsertionIndexGenerator(int numOfInsertions, int listSize, int startIndex) {
//     checkArgument(startIndex <= listSize,
//       "startIndex (%s) must be <= listSize (%s).",
//       startIndex, listSize);
//     insertionPositions = new int[numOfInsertions];
//     for (int i = 0; i < insertionPositions.length; i++) {
//       insertionPositions[i] = startIndex;
//     }
//     originalListSize = listSize;
//     length = multichoose(listSize + 1 - startIndex, numOfInsertions);
//   }
// 
//   @Override
//   public boolean hasNext() {
//     return index < length;
//   }
// 
//   @Override
//   public IntList next() {
//     if (!hasNext()) {
//       throw new NoSuchElementException();
//     }
//     if (index > 0) {
//       for (int i = 0; i < insertionPositions.length; i++) {
//         if (insertionPositions[i] == originalListSize) {
//           insertionPositions[i - 1]++;
//           for (int j = i; j < insertionPositions.length; j++) {
//             insertionPositions[j] = insertionPositions[i - 1];
//           }
//           break;
//         } else if (i == insertionPositions.length - 1) {
//           insertionPositions[i]++;
//         }
//       }
//     }
//     index++;
//     return IntLists.unmodifiable(new IntArrayList(insertionPositions));
//   }
// 
//   @Deprecated
//   @Override
//   public void remove() {
//     throw new UnsupportedOperationException();
//   }
// }


// Path: src/test/java/com/github/rinde/opt/localsearch/InsertionsTest.java
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableSet;
import it.unimi.dsi.fastutil.ints.IntList;
import static com.github.rinde.opt.localsearch.Insertions.insert;
import static com.github.rinde.opt.localsearch.Insertions.insertions;
import static com.github.rinde.opt.localsearch.Insertions.insertionsIterator;
import static com.google.common.collect.Sets.newHashSet;
import static java.util.Arrays.asList;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
import org.junit.Test;
import com.github.rinde.opt.localsearch.Insertions.InsertionIndexGenerator;

/*
 * Copyright (C) 2013-2016 Rinde van Lon, iMinds-DistriNet, KU Leuven
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *         http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package com.github.rinde.opt.localsearch;






/**
 * @author Rinde van Lon
 *
 */
public class InsertionsTest {

  static final String A = "A";
  static final String B = "B";
  static final String C = "C";
  static final String D = "D";
  static final String Z = "Z";

  /**
   * Tests whether all insertions are created.
   */
  @Test
  public void oneInsertions() {
    List<ImmutableList<String>> strings = insertions(
      ImmutableList.<String>of(), Z, 0, 1);
    assertEquals(1, strings.size());
    assertEquals(asList(Z), strings.get(0));

    strings = insertions(ImmutableList.of(A), Z, 0, 1);