Bistring

gistfile1.java

package com.os.cpnet.tool;

import java.util.Arrays;

import org.apache.commons.codec.binary.Base64;

public final class BitString implements Comparable<BitString> {
  public static final BitString ZERO = new BitString(new long[] {});
  public static final int SLOT_SIZE = 64;
  
  private long[] string;
  
  private BitString(long[] data) {
    string = compact(data);
  }
  
  public static BitString bfrom(byte[] dump) {
    if (dump == null) return ZERO;
    
    long[] data = new long[dump.length / 8];
    
    for (int i = 0; i < data.length; i++) {
      long c = 0L;
      for (int j = 0; j < 8; j++)
        c |= ((0xFFL & dump[i * 8 + j]) << (j * 8));
      
      data[i] = c;
    }
    
    return new BitString(data);
  }
  
  public static BitString from(String dump) {
    if (dump == null) return ZERO;
    
    return bfrom(Base64.decodeBase64(dump));
  }
  
  public byte[] bdump() {
    byte[] dmp = new byte[this.string.length * 8];
    for (int i = 0; i < this.string.length; i++)
      for (int j = 0; j < 8; j++)
        dmp[i * 8 + j] = (byte) ((this.string[i] & (0xFFL << (j * 8))) >>> (j * 8));
    
    return dmp;
  }
  
  public String dump() {
    return Base64.encodeBase64String(bdump());
  }
  
  private void ensure(int position) {
    if (string.length <= position) {
      long[] data = new long[position + 1];
      for (int i = 0; i < string.length; i++) data[i] = string[i];
      string = data;
    }
  }
  
  @Override
  public BitString clone() {
    long[] data = new long[string.length];
    for (int i = 0; i < string.length; i++) data[i] = string[i];
    
    return new BitString(data);
  }
  
  public BitString set(int... bits) {
    BitString clone = clone();
    
    for (int bit : bits) {
      int p = bit / SLOT_SIZE;
      int b = bit % SLOT_SIZE;
      
      clone.ensure(p);
      clone.string[p] |= 1L << b;
    }
    
    return clone;
  }
  
  public BitString remove(int... bits) {
    BitString clone = clone();
    
    for (int bit : bits) {
      int p = bit / SLOT_SIZE;
      int b = bit % SLOT_SIZE;
      
      clone.ensure(p);
      clone.string[p] &= ~(1L << b);
    }
    
    return clone;
  }
  
  public static long mask(int count) {
    if (count <= 0) return 0L;
    if (count > SLOT_SIZE) return -1L;
    
    return (1L << (count - 1)) | mask(count - 1);
  }
  
  public BitString rshift(int dif) {
    if (dif < 0) return lshift(-dif);
    if (dif > SLOT_SIZE) return rshift(SLOT_SIZE).rshift(dif - SLOT_SIZE);
    
    long mask = mask(dif);
    
    long[] data = new long[string.length];
    
    if (data.length > 0) {
      for (int i = 0; i < string.length - 1; i++) data[i] = ((string[i] & ~mask) >>> dif) | ((string[i + 1] & mask) << (SLOT_SIZE - dif));
      data[data.length - 1] = (string[data.length - 1] & ~mask) >>> dif;
    }

    return new BitString(data);
  }
  
  public BitString lshift(int dif) {
    if (dif < 0) return rshift(-dif);
    if (dif > SLOT_SIZE) return lshift(SLOT_SIZE).lshift(dif - SLOT_SIZE);
    
    long mask = mask(dif);
    
    long[] data = new long[string.length + 1];
    
    if (string.length > 0) {
      data[0] = (string[0] << dif) & ~mask;
      for (int i = 1; i < data.length - 1; i++) data[i] = ((string[i] << dif) & ~mask) | ((string[i - 1] >>> (SLOT_SIZE - dif)) & mask);
      data[data.length - 1] = (string[data.length - 2] >>> (SLOT_SIZE - dif)) & mask;
    }
    
    return new BitString(data);
  }
  
  public BitString and(BitString other) {
    int min = this.string.length < other.string.length ? this.string.length : other.string.length;
    
    long[] data = new long[min];
    for (int i = 0; i < min; i++) data[i] = this.string[i] & other.string[i];
    
    return new BitString(data);
  }
  
  public BitString and(long part, int position) {
    long[] data = new long[position + 1];
    if (this.string.length > position) data[position] = this.string[position] & part;
    
    return new BitString(data);
  }
  
  public BitString or(BitString other) {
    int min = this.string.length < other.string.length ? this.string.length : other.string.length;
    int max = this.string.length > other.string.length ? this.string.length : other.string.length;
    
    long[] data = new long[max];
    for (int i = 0; i < min; i++) data[i] = this.string[i] | other.string[i];
    
    for (int i = min; i < this.string.length; i++) data[i] = this.string[i];
    for (int i = min; i < other.string.length; i++) data[i] = other.string[i];
    
    return new BitString(data);
  }
  
  public BitString or(long part, int position) {
    int size = position >= this.string.length ? position + 1 : this.string.length;
    
    long[] data = new long[size];
    for (int i = 0; i < this.string.length; i++) data[i] = this.string[i];
    for (int i = this.string.length; i < data.length; i++) data[i] = 0L;
    
    data[position] |= part;
    
    return new BitString(data);
  }
  
  @Override
  public boolean equals(Object obj) {
    if (obj instanceof BitString) {
      BitString other = (BitString) obj;
      int min = this.string.length < other.string.length ? this.string.length : other.string.length;
      
      for (int i = 0; i < min; i++) if (this.string[i] != other.string[i]) return false;
      
      if (this.string.length != other.string.length) {
        for (int i = min; i < this.string.length; i++) if (this.string[i] != 0) return false;
        for (int i = min; i < other.string.length; i++) if (other.string[i] != 0) return false;
      }
      
      return true;
    } else return false;
  }
  
  public int[] serialize() {
    int[] j = new int[string.length * 2];
    for (int i = 0; i < string.length; i++) {
      j[i * 2 + 0] = (int) (string[i] & 0xFFFFFFFFL);
      j[i * 2 + 1] = (int) (string[i] >>> (SLOT_SIZE / 2));
    }
    
    return j;
  }
  
  @Override
  public String toString() {
    StringBuilder out = new StringBuilder();
    
    for (int i = 0; i < this.string.length; i++) {
      for (int j = 0; j < 64; j++) out.append((this.string[i] & (1L << j)) >>> j);
      out.append(" ");
    }
    
    return out.reverse().toString().trim();
  }

  @Override
  public int compareTo(BitString other) {
    int min = this.string.length < other.string.length ? this.string.length : other.string.length;
    
    for (int i = min; i < this.string.length; i++) if (this.string[i] != 0) return 1;
    for (int i = min; i < other.string.length; i++) if (other.string[i] != 0) return -1;
    
    for (int i = 0; i < min; i++) {
      if (this.string[i] > other.string[i]) return 1 * inverse(this.string[i], other.string[i]);
      else if (this.string[i] < other.string[i]) return -1 * inverse(this.string[i], other.string[i]);
    }
    
    return 0;
  }
  
  private static long[] compact(long[] data) {
    int cut = 0;
    for (int i = data.length - 1; i >= 0; i--) {
      if (data[i] == 0) cut++;
      else break;
    }
    
    return Arrays.copyOfRange(data, 0, data.length - cut);
  }
  
  private static int inverse(long l0, long l1) {
    if (l0 >= 0 && l1 >= 0) return 1;
    if (l0 < 0 && l1 < 0) return 1;
    return -1;
  }
}