#include <stdlib.h>
#include <string.h>
#include "hashtable.h"

ulong hash_func(char *arKey)
{
    register ulong hash = 5381;
    int      nKeyLength = strlen(arKey);

    for (; nKeyLength >= 8; nKeyLength -= 8) {
        hash = ((hash << 5) + hash) + *arKey++;
        hash = ((hash << 5) + hash) + *arKey++;
        hash = ((hash << 5) + hash) + *arKey++;
        hash = ((hash << 5) + hash) + *arKey++;
        hash = ((hash << 5) + hash) + *arKey++;
        hash = ((hash << 5) + hash) + *arKey++;
        hash = ((hash << 5) + hash) + *arKey++;
        hash = ((hash << 5) + hash) + *arKey++;
    }
    switch (nKeyLength) {
        case 7: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
        case 6: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
        case 5: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
        case 4: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
        case 3: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
        case 2: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
        case 1: hash = ((hash << 5) + hash) + *arKey++; break;
        case 0: break;
        default:
                break;
    }
    return hash;
}

#define CONNECT_TO_BUCKET_DLLIST(element, list_head) do{    \
    (element)->pNext = (list_head);                         \
    (element)->pLast = NULL;                                \
    if ((element)->pNext) {                                 \
        (element)->pNext->pLast = (element);                \
    }                                                       \
}while(0);

#define CONNECT_TO_GLOBAL_DLLIST(element, ht)    do{        \
    (element)->pListLast = (ht)->pListTail;                 \
    (ht)->pListTail = (element);                            \
    (element)->pListNext = NULL;                            \
    if ((element)->pListLast != NULL) {                     \
        (element)->pListLast->pListNext = (element);        \
    }                                                       \
    if (!(ht)->pListHead) {                                 \
        (ht)->pListHead = (element);                        \
    }                                                       \
    if ((ht)->pInternalPointer == NULL) {                   \
        (ht)->pInternalPointer = (element);                 \
    }                                                       \
}while(0);


int hash_init(HashTable *ht, uint nSize)
{
    uint i = 3;
    if (nSize >= 0x80000000) {
        ht->nTableSize = 0x80000000;
    } else {
        while ((1U << i) < nSize) {
            i++;
        }
        ht->nTableSize = 1 << i;
    }
    ht->arBuckets = (Bucket **) malloc(ht->nTableSize * sizeof(Bucket *));
    memset(ht->arBuckets,0,ht->nTableSize);
    ht->nTableMask = ht->nTableSize - 1;                        
    ht->pListHead = NULL;
    ht->pListTail = NULL;
    ht->pInternalPointer = NULL;
    ht->nNumOfElements = 0;
    return SUCCESS;
}

void hash_free(HashTable *ht)
{
    Bucket *p, *q;
    p = ht->pListHead;
    while (p != NULL) {
        q = p;
        p = p->pListNext;
        free(q->pData);
        free(q->arKey);
        free(q);
        q = NULL;
    }
    if (ht->nTableMask) {
        free(ht->arBuckets);
        ht->arBuckets = NULL;
    }
    free(ht);
    ht = NULL;
}

int hash_add(HashTable *ht, char *arKey, void *pData, int nDataSize)
{
    ulong h;
    uint nIndex;
    Bucket *p;
    void * pDataCopy = NULL;
    char * pKeyCopy  = NULL;
    int keyLength = strlen((char*)arKey);
    if (keyLength <= 0)
        return FAILURE;

    h = hash_func(arKey);
    nIndex = h & ht->nTableMask;
    p = ht->arBuckets[nIndex];
    pDataCopy = (void *)malloc(sizeof(nDataSize));
    memcpy(pDataCopy,pData,nDataSize);
    while (p != NULL) {
        if (p->arKey == arKey || ((p->keyLength == keyLength) && !memcmp(p->arKey, arKey, keyLength))) {
                free(p->pData);
                p->pData = pDataCopy;
                p->dataLength = nDataSize;
                return SUCCESS;
        }
        p = p->pNext;
    }
    p = (Bucket *) malloc(sizeof(Bucket));
    if (!p) {
        return FAILURE;
    }
    pKeyCopy = (char*) malloc(sizeof(keyLength));
    memcpy(pKeyCopy,arKey,keyLength);
    p->h = h;
    p->arKey = pKeyCopy;
    p->keyLength = keyLength;
    p->pData = pDataCopy;
    p->dataLength = nDataSize;
    CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
    CONNECT_TO_GLOBAL_DLLIST(p, ht);
    ht->arBuckets[nIndex] = p;
    ht->nNumOfElements++;
    return SUCCESS;
}

int hash_del(HashTable *ht, char *arKey)
{
    ulong h;
    uint nIndex;
    Bucket *p;
    int keyLength = strlen(arKey);
    if (keyLength <= 0)
        return FAILURE;

    h = hash_func(arKey);
    nIndex = h & ht->nTableMask;
    p = ht->arBuckets[nIndex];
    while (p != NULL) {
        if (p->arKey == arKey || ((p->keyLength == keyLength) && !memcmp(p->arKey, arKey, keyLength))) {
            if (p == ht->arBuckets[nIndex]) {
                ht->arBuckets[nIndex] = p->pNext;
            } else {
                p->pLast->pNext = p->pNext;
            }
            if (p->pNext) {
                p->pNext->pLast = p->pLast;
            }
            if (p->pListLast != NULL) {
                p->pListLast->pListNext = p->pListNext;
            } else { 
                ht->pListHead = p->pListNext;
            }
            if (p->pListNext != NULL) {
                p->pListNext->pListLast = p->pListLast;
            } else {
                ht->pListTail = p->pListLast;
            }
            if (ht->pInternalPointer == p) {
                ht->pInternalPointer = p->pListNext;
            }
            free(p->pData);
            free(p->arKey);
            free(p);
            p = NULL;
            ht->nNumOfElements--;
            return SUCCESS;
        }
        p = p->pNext;
    }
    return FAILURE;
}


int hash_find(HashTable *ht, char *arKey, void **pData)
{
    ulong h;
    uint nIndex;
    Bucket *p;
    int keyLength = strlen(arKey);
    if (keyLength<=0)
        return FAILURE;

    h = hash_func(arKey);
    nIndex = h & ht->nTableMask;
    p = ht->arBuckets[nIndex];
    while (p != NULL) {
        if (p->arKey == arKey || ((p->keyLength == keyLength) && !memcmp(p->arKey, arKey, keyLength))) {
            *pData = malloc(p->dataLength);
            memcpy(*pData,p->pData,p->dataLength);
            return SUCCESS;
        }
        p = p->pNext;
    }
    return FAILURE;
}

int hash_exists(HashTable *ht, char *arKey)
{
    ulong h;
    uint nIndex;
    Bucket *p;
    int keyLength = strlen(arKey);
    if (keyLength<=0)
        return FAILURE;

    h = hash_func(arKey);
    nIndex = h & ht->nTableMask;

    p = ht->arBuckets[nIndex];
    while (p != NULL) {
        if (p->arKey == arKey || ((p->keyLength == keyLength) && !memcmp(p->arKey, arKey, keyLength))) {
                return EXISTS;
        }
        p = p->pNext;
    }
    return NOTEXISTS;
}

int hash_num_elements(HashTable *ht)
{
    return ht->nNumOfElements;
}

#ifndef HASH_TABLE
#define HASH_TABLE

#define ulong unsigned long
#define uint  unsigned int

#define SUCCESS      0
#define EXISTS       1
#define FAILURE     -1
#define NOTEXISTS   -2

#define reset(ht)       ((ht)->pInternalPointer = (ht)->pListHead)
#define next(ht)        ((ht)->pInternalPointer = (ht)->pInternalPointer->pListNext)
#define isnotend(ht)    ((ht)->pInternalPointer != NULL)
#define key(ht)         ((ht)->pInternalPointer->arKey)
#define value(ht)       ((ht)->pInternalPointer->pData)
#define foreach(k,v,ht) for (reset(ht); isnotend(ht)&&(k=key(ht))&&(v=value(ht)); next(ht))


typedef struct bucket {
    ulong  h;
    char  *arKey;
    int    keyLength;
    void  *pData;
    int    dataLength;
    struct bucket *pListNext;
    struct bucket *pListLast;
    struct bucket *pNext;
    struct bucket *pLast;
} Bucket;

typedef struct _hashtable {
    uint    nTableSize;
    uint    nTableMask;
    uint    nNumOfElements;
    Bucket *pInternalPointer;
    Bucket *pListHead;
    Bucket *pListTail;
    Bucket **arBuckets;
} HashTable;

int hash_init(HashTable *ht, uint nSize);
void hash_free(HashTable *ht);

int hash_add(HashTable *ht, char *arKey, void *pData, int nDataSize);
int hash_del(HashTable *ht, char *arKey);
int hash_find(HashTable *ht, char *arKey, void **pData);
int hash_exists(HashTable *ht, char *arKey);
int hash_num_elements(HashTable *ht);

#endif

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "heap.h"

/* ----------------------------------
 * Default Compare Function for Heap
 * ---------------------------------- */
int default_heap_cmp_fn(int* m, int* n){
    int i = *m - *n;
    return i > 0 ? 1 : (i < 0 ? -1 : 0);
}

/* ----------------------------------
 * Create and Return a Heap Structor
 * ---------------------------------- */
Heap * heap_create(int size){
    if (size < 2){
        fprintf(stderr,"too small size no need heap\n");
        return NULL;

    }

    Heap * hp = (Heap*)malloc(sizeof(Heap));
    hp->len = 0;
    hp->size = size;
    hp->data = (void**)malloc(sizeof(void*) * size);
    memset(hp->data,0,sizeof(void*) * size);
    hp->heap_cmp_fn = (HEAP_CMP_FN)&default_heap_cmp_fn;

    return hp;
}


#define HEAP_ADJUST(hp,l) do {                                             \
    int lt = l;                                                            \
    int i  = lt + lt + 1;                                                  \
    int r  = hp->len - 1;                                                  \
    void * t = hp->data[lt];                                               \
    do {                                                                   \
        if ((i<r) && (hp->heap_cmp_fn(hp->data[i], hp->data[i+1]) > 0)){   \
            i += 1;                                                        \
        }                                                                  \
        if (hp->heap_cmp_fn(t,hp->data[i]) <= 0){                          \
            break;                                                         \
        }                                                                  \
        hp->data[lt] = hp->data[i];                                        \
        lt = i;                                                            \
        i += i + 1;                                                        \
    }while (i <= r);                                                       \
    hp->data[lt] = t;                                                      \
} while (0);                                                               \


/* ----------------------------------
 * Add an Element into the Heap
 * ---------------------------------- */
void * heap_add(Heap * hp, void * pdata){
    if (hp->len < hp->size){
        hp->data[hp->len] = pdata;
        hp->len += 1;
        if (hp->len >= hp->size){
            int l = hp->len / 2;
            while(--l >= 0){
                HEAP_ADJUST(hp,l);
            }
        }
        return NULL;
    }
    void * top = hp->data[0];
    if (hp->heap_cmp_fn(top,pdata) < 0){
        hp->data[0] = pdata;
        HEAP_ADJUST(hp,0);
        return top;
    }
    return pdata;
}


/* ----------------------------------
 * Free the Heap Memory Space
 * ---------------------------------- */
void   heap_free(Heap * hp){
    if (hp->data){
        for (int i = 0; i < hp->len; i++){
            free(hp->data[i]);
            hp->data[i] = NULL;
        }
        free(hp->data);
        hp->data = NULL;
    }
    free(hp);
}

#ifndef HEAP_H
#define HEAP_H

/* ------------------------------
 * Data Define for Heap Structor
 * Oh This is just a Min Heap!!!
 * ------------------------------ */

typedef int (*HEAP_CMP_FN)(void *, void*);

typedef struct _heap {
    int len;
    int size;
    void ** data;
    HEAP_CMP_FN heap_cmp_fn;
} Heap;


/* ---------------------------------------------
 * Interface Function Define for Heap Operation
 * --------------------------------------------- */


Heap * heap_create(int size);
void * heap_add(Heap * hp, void * pdata);
void   heap_free(Heap * hp);

#endif

#!/home/admin/bin/bash_bin/bash_4

if [ $# -ne 2 ]; then
    echo "please input the trans input file";
    exit 1;
fi

trans_file=$1;
min_support=$2;

if [ "x$trans_file" == "x" ]; then
    echo "the input file can not be null";
    exit 2;
fi

if [ ! -f "$trans_file" ]; then
    echo "trans should be a existed data file"
    exit 3;
fi

if [ -z "$min_support" ]; then
    echo "please specify the min support for the freq-2 items"
    exit 4;
fi

## get the freq-1 items and the frequents for each of them

declare -A freq_1;

for line in `cat $trans_file`
do
    currentItemArray=(${line//,/ });
    for i in ${currentItemArray[@]}
    do
        if [ -z ${freq_1[$i]} ]; then
            freq_1[$i]=1;
        else
            ((freq_1[$i]+=1));
        fi
    done
done

for k in ${!freq_1[@]}
do
    if [ ${freq_1[$k]} -lt $min_support ]; then
        unset freq_1[$k];
    fi
done



### sort the freq_1 using external sort commond

declare -a freq_1_sorted_item;
freq_1_sorted_length=0;

for i in `
    for i in ${!freq_1[@]}
    do
        echo "$i,${freq_1[$i]}"
    done | sort -s -t ',' -k 2 -nr
`
do
    freq_1_sorted_item[$freq_1_sorted_length]=${i%%,*};
    ((freq_1_sorted_length+=1));
done


### Generate the FP-Tree using a one dimensional array with a virtual root node
### The element with struct {itemName:Support:Child:Next:Parent}
### The virtual root node is {NULL:0:0:0:0} that the only Child filed will not be '0'.
### Because it has no parent and no sibling nodes and no support.

declare -a FP_TREE;          ## this is the fp_tree
declare -A Node_Index;       ## the index of each freq_1 item

### push the virtual root node
FP_TREE[0]="NULL:0:0:0:0";

### scan the trans file again and also the last time.
### and generate the fp_tree

for line in `cat $trans_file`
do
    ### scan the sorted freq_1 items
    ### no need to sort the original trans input line....

    current_node_index=0;
    for freq_1_item in ${freq_1_sorted_item[@]}
    do
        if [[ ",$line," == *",$freq_1_item,"* ]]; then     
            current_node_line=${FP_TREE[$current_node_index]};
            current_node_info=(${current_node_line//:/ });
            child_index=${current_node_info[2]};
            if [  "$child_index" == "0" ]; then

                ### add a new node as the first left child of the current node
                new_node="$freq_1_item:1:0:0:$current_node_index";
                FP_TREE_LENGTH=${#FP_TREE[@]};
                FP_TREE[$FP_TREE_LENGTH]=$new_node;

                ### update the child pointer of the current node
                current_node_info[2]=$FP_TREE_LENGTH;
                tmp_line=${current_node_info[*]};
                FP_TREE[$current_node_index]=${tmp_line// /:};
                current_node_index=$FP_TREE_LENGTH;
                Node_Index[$freq_1_item]="${Node_Index[$freq_1_item]}:$current_node_index";
            else 
                while :
                do
                    child_node_line=${FP_TREE[$child_index]};
                    child_node_info=(${child_node_line//:/ });

                    ### find a existed node match the current freq_1_item
                    if [ "${child_node_info[0]}" == "$freq_1_item" ]; then
                        ((child_node_info[1]+=1));
                        tmp_line=${child_node_info[*]};
                        FP_TREE[$child_index]=${tmp_line// /:};
                        current_node_index=$child_index;
                        break;
                    fi 
                    next_index=${child_node_info[3]};
                    if [  "$next_index" == "0" ]; then

                        ### add a new node as the last child of the current node
                        ### and also means the next node of the current last child node of the current node
                        new_node="$freq_1_item:1:0:0:$current_node_index";
                        FP_TREE_LENGTH=${#FP_TREE[@]};
                        FP_TREE[$FP_TREE_LENGTH]=$new_node;

                        ### update the next pointer of the current last child of the current node
                        child_node_info[3]=$FP_TREE_LENGTH;
                        tmp_line=${child_node_info[*]};
                        FP_TREE[$child_index]=${tmp_line// /:};
                        current_node_index=$FP_TREE_LENGTH;
                        Node_Index[$freq_1_item]="${Node_Index[$freq_1_item]}:$current_node_index";
                        break;
                    fi
                    child_index=$next_index;
                done
            fi
        fi
    done
done    ### FP_TREE Done!!!!!

fp_tree_length=${#FP_TREE[@]};

for((i=0;i<fp_tree_length;i++))
do
    echo "$i->${FP_TREE[$i]}";
done
echo

### get the freq_2 items and their support from the FP_TREE!!!

declare -A item_4_freq2;

for freq_1_item in ${freq_1_sorted_item[@]}
do
    treeIndex_item=${Node_Index[$freq_1_item]};
    indexs=(${treeIndex_item//:/ });
    base_support=0;
    for index in ${indexs[@]}
    do
        p_node_line=${FP_TREE[$index]};
        p_node_info=(${p_node_line//:/ });
        current_path_support=${p_node_info[1]};
        ((base_support+=$current_path_support));
        index=${p_node_info[4]};
        ## search the parent node until the root
        while [  "$index" != "0" ]
        do
            p_node_line=${FP_TREE[$index]};
            p_node_info=(${p_node_line//:/ });
            p_item=${p_node_info[0]};
            if [ -n "${item_4_freq2[$p_item]}"  ]; then
                ((item_4_freq2[$p_item]+=$current_path_support));
            else
                item_4_freq2[$p_item]=$current_path_support;
            fi
            index=${p_node_info[4]};
        done
    done
    for key in ${!item_4_freq2[@]}
    do
        freq_2_items_support=0;
        [ $base_support -lt ${item_4_freq2[$key]} ] && ((freq_2_items_support=$base_support)) || ((freq_2_items_support=${item_4_freq2[$key]}));
        if [ $freq_2_items_support -ge $min_support ]; then
            echo "$freq_1_item,$key:$freq_2_items_support";
        fi
        unset item_4_freq2[$key];
    done
done

public class Singleton {  
  private static class SingletonHolder{
       final static Singleton  instance= new Singleton ();
  } 
  private Singleton(){};
 
  public static Singleton getInstance() {
        return SingletonHolder.instance;
  }

}

public class Singleton {

	private volatile static Singleton singleton;
	
	private Singleton(){ }
	
	public static Singleton getInstance(){
		// 双重检查加锁
		if(singleton==null){
			synchronized(Singleton.class){
				// 延迟实例化,需要时才创建
				if(singleton==null)
					singleton = new Singleton();
			}
		}
		return singleton;
	}
}

char *php_strtoupper(char *s, size_t len)
{
    unsigned char *c, *e;
    
    c = (unsigned char *)s; 
    e = (unsigned char *)c+len;

    while (c < e) { 
        *c = toupper(*c);
        c++; 
    }    
    return s;
}

    result_len = input_len * mult;
    result = (char *)safe_emalloc(input_len, mult, 1);
    
    /* Heavy optimization for situations where input string is 1 byte long */
    if (input_len == 1) { 
        memset(result, *(input_str), mult); 
    } else {
        char *s, *e, *ee; 
        int l=0; 
        memcpy(result, input_str, input_len);
        s = result;
        e = result + input_len;
        ee = result + result_len;

        while (e<ee) {
            l = (e-s) < (ee-e) ? (e-s) : (ee-e);
            memmove(e, s, l);
            e += l;
        }
    }

    result[result_len] = '\0';

    /** 
     *  
     * @author chenzhuzuo 
     * 回溯法解决数字拆分问题 
     * 问题描述： 
     *  整数的分划问题。  
        如，对于正整数n=6，可以分划为：  
        6  
        5+1  
        4+2, 4+1+1  
        3+3, 3+2+1, 3+1+1+1  
        2+2+2, 2+2+1+1, 2+1+1+1+1  
        1+1+1+1+1+1+1  
        现在的问题是，对于给定的正整数n,编写算法打印所有划分。 
        用户从键盘输入 n （范围1~10） 
    程序输出该整数的所有划分。 
     * 
     * 
     *以前做这个题时一直找不到好的思路，在网上也看了一下别人的做法，更多的是使用递归的算法， 
     *看了还是不太明白，这几天研究了一下回溯算法，做了几个比较经典的题目，感觉本题可以用求 
     *子集和的思路来解决，就试了一下，最后还是做出来了，不过效率不是很高。经过今天的学习 
     *，感觉回溯法确实很难懂，但是一旦你弄懂了，回溯法可以说是万能的，真的很好用 
     */  
    public class ShuziChaiFei {  
      
        /** 
         * @param args 
         */  
        public static void main(String[] args) {  
            printResult(6);  
        }  
        /** 
         *  
         * @param n对n进行拆分 
         */  
        private static void printResult(int n){  
            int a[]= new int[n+1];//用于记录每个数出现的个数（1=<i<=n）;  
            for(int i=0;i<=n;i++){  
                a[i]=0;  
            }  
            int sum=0;  
            int k = 1;  
            while(k>=1){  
                a[k] += 1;  
                sum+=k;  
                if(sum==n){//如果当前的和等于n则获得一个解，输出  
                    for(int i=1;i<=k;i++){  
                        int m=1;  
                        //a[i]等值表示i在这个解中出现的次数  
                        while(m<=a[i]){  
                            if(m==a[i]&&i==k){  
                                System.out.print(i);  
                                m++;  
                                  
                                }  
                                else{  
                                    System.out.print(i+"+");  
                                    m++;  
                                      
                                }  
                        }  
                    }  
                    a[k]++;//继续搜索解空间  
                    sum+=k;  
                    System.out.println();  
                }  
                else if(sum>n){  
                    sum -= k;  
                    a[k] -=1;  
                    k++;  
                }  
                //当k>n时进行回溯  
                if(k>n){  
                    k--;  
                    while(a[k]>0){  
                        sum=sum-a[k]*k;  
                        k--;  
                    }  
                    while(a[k]==0){  
                        k--;  
                        if(k<1){  
                            return;  
                        }  
                    }  
                    sum -= k;  
                    a[k]--;  
                    k++;  
                      
                }  
            }  
        }  
      
    }