import brewer2mpl
import pandas as pd
import matplotlib.pyplot as plt
import matplotlib.gridspec as gridspec
import scipy.spatial.distance as distance
import scipy.cluster.hierarchy as sch

# font size for figures
rcParams.update({'font.size': 16})
# Arial font
rc('font',**{'family':'sans-serif','sans-serif':['Arial']})

# helper for cleaning up axes by removing ticks, tick labels, frame, etc.
def clean_axis(ax):
    """Remove ticks, tick labels, and frame from axis"""
    ax.get_xaxis().set_ticks([])
    ax.get_yaxis().set_ticks([])
    for sp in ax.spines.values():
        sp.set_visible(False)

# test data
testL = []
# 5 samples from one group
for i in range(5):
    # 20 measurements from normal with mean 10, stdev 2
    testL.append(random.normal(10,2,20))
# 8 samples from another group
for i in range(8):
    # 20 measurements from normal with mean 4, stdev 4
    testL.append(random.normal(4,4,20))

# permute test data and make dataframe
testA = array(testL)[random.permutation(range(len(testL)))]
testDF = pd.DataFrame(testA)

testDF.shape

# look at raw data
axi = imshow(testDF,interpolation='nearest',cmap=cm.RdBu)
ax = axi.get_axes()
clean_axis(ax)

# calculate pairwise distances for rows
pairwise_dists = distance.squareform(distance.pdist(testDF))
print 'Number of rows: {0}'.format(testDF.shape[0])
print 'Size of distance matrix: {0}'.format(pairwise_dists.shape)

# cluster
clusters = sch.linkage(pairwise_dists,method='complete')

# dendrogram
den = sch.dendrogram(clusters)

# make dendrograms black rather than letting scipy color them
sch.set_link_color_palette(['black'])
# or 
den = sch.dendrogram(clusters,color_threshold=np.inf)

# dendrogram without plot
den = sch.dendrogram(clusters,color_threshold=np.inf,no_plot=True)

den['leaves']

axi = imshow(testDF.ix[den['leaves']],interpolation='nearest',cmap=cm.RdBu)
ax = axi.get_axes()
clean_axis(ax)

fig = plt.figure()
heatmapGS = gridspec.GridSpec(1,2,wspace=0.0,hspace=0.0,width_ratios=[0.25,1])

### row dendrogram ###
denAX = fig.add_subplot(heatmapGS[0,0])
denD = sch.dendrogram(clusters,color_threshold=np.inf,orientation='right')
clean_axis(denAX)

### heatmap ###
heatmapAX = fig.add_subplot(heatmapGS[0,1])
axi = heatmapAX.imshow(testDF.ix[den['leaves']],interpolation='nearest',aspect='auto',origin='lower',cmap=cm.RdBu)
clean_axis(heatmapAX)

# rename row clusters
row_clusters = clusters

# calculate pairwise distances for columns
col_pairwise_dists = distance.squareform(distance.pdist(testDF.T))
# cluster
col_clusters = sch.linkage(col_pairwise_dists,method='complete')

# plot the results
fig = plt.figure()
heatmapGS = gridspec.GridSpec(2,2,wspace=0.0,hspace=0.0,width_ratios=[0.25,1],height_ratios=[0.25,1])

### col dendrogram ####
col_denAX = fig.add_subplot(heatmapGS[0,1])
col_denD = sch.dendrogram(col_clusters,color_threshold=np.inf)
clean_axis(col_denAX)

### row dendrogram ###
row_denAX = fig.add_subplot(heatmapGS[1,0])
row_denD = sch.dendrogram(row_clusters,color_threshold=np.inf,orientation='right')
clean_axis(row_denAX)

### heatmap ###
heatmapAX = fig.add_subplot(heatmapGS[1,1])
axi = heatmapAX.imshow(testDF.ix[den['leaves'],col_denD['leaves']],interpolation='nearest',aspect='auto',origin='lower',cmap=cm.RdBu)
clean_axis(heatmapAX)

fig.tight_layout()

testDF.index = [ 'Sample ' + str(x) for x in testDF.index ]
testDF.columns = [ 'c' + str(x) for x in testDF.columns ]

# heatmap with row names
fig = plt.figure()
heatmapGS = gridspec.GridSpec(2,2,wspace=0.0,hspace=0.0,width_ratios=[0.25,1],height_ratios=[0.25,1])

### col dendrogram ###
col_denAX = fig.add_subplot(heatmapGS[0,1])
col_denD = sch.dendrogram(col_clusters,color_threshold=np.inf)
clean_axis(col_denAX)

### row dendrogram ###
row_denAX = fig.add_subplot(heatmapGS[1,0])
row_denD = sch.dendrogram(row_clusters,color_threshold=np.inf,orientation='right')
clean_axis(row_denAX)

### heatmap ###
heatmapAX = fig.add_subplot(heatmapGS[1,1])
axi = heatmapAX.imshow(testDF.ix[den['leaves'],col_denD['leaves']],interpolation='nearest',aspect='auto',origin='lower',cmap=cm.RdBu)
clean_axis(heatmapAX)

## row labels ##
heatmapAX.set_yticks(arange(testDF.shape[0]))
heatmapAX.yaxis.set_ticks_position('right')
heatmapAX.set_yticklabels(testDF.index[row_denD['leaves']])
# remove the tick lines
for l in heatmapAX.get_xticklines() + heatmapAX.get_yticklines(): 
    l.set_markersize(0)

fig.tight_layout()

# heatmap with row names
fig = plt.figure()
heatmapGS = gridspec.GridSpec(2,2,wspace=0.0,hspace=0.0,width_ratios=[0.25,1],height_ratios=[0.25,1])

### col dendrogram ###
col_denAX = fig.add_subplot(heatmapGS[0,1])
col_denD = sch.dendrogram(col_clusters,color_threshold=np.inf)
clean_axis(col_denAX)

### row dendrogram ###
row_denAX = fig.add_subplot(heatmapGS[1,0])
row_denD = sch.dendrogram(row_clusters,color_threshold=np.inf,orientation='right')
clean_axis(row_denAX)

### heatmap ####
heatmapAX = fig.add_subplot(heatmapGS[1,1])
axi = heatmapAX.imshow(testDF.ix[row_denD['leaves'],col_denD['leaves']],interpolation='nearest',aspect='auto',origin='lower',cmap=cm.RdBu)
clean_axis(heatmapAX)

## row labels ##
heatmapAX.set_yticks(arange(testDF.shape[0]))
heatmapAX.yaxis.set_ticks_position('right')
heatmapAX.set_yticklabels(testDF.index[row_denD['leaves']])

## col labels ##
heatmapAX.set_xticks(arange(testDF.shape[1]))
xlabelsL = heatmapAX.set_xticklabels(testDF.columns[col_denD['leaves']])
# rotate labels 90 degrees
for label in xlabelsL:
    label.set_rotation(90)
# remove the tick lines
for l in heatmapAX.get_xticklines() + heatmapAX.get_yticklines(): 
    l.set_markersize(0)

fig.tight_layout()

# heatmap with row names
fig = plt.figure(figsize=(12,8))
heatmapGS = gridspec.GridSpec(2,2,wspace=0.0,hspace=0.0,width_ratios=[0.25,1],height_ratios=[0.25,1])

### col dendrogram ###
col_denAX = fig.add_subplot(heatmapGS[0,1])
col_denD = sch.dendrogram(col_clusters,color_threshold=np.inf)
clean_axis(col_denAX)

### row dendrogram ###
row_denAX = fig.add_subplot(heatmapGS[1,0])
row_denD = sch.dendrogram(row_clusters,color_threshold=np.inf,orientation='right')
clean_axis(row_denAX)

### heatmap ####
heatmapAX = fig.add_subplot(heatmapGS[1,1])
axi = heatmapAX.imshow(testDF.ix[row_denD['leaves'],col_denD['leaves']],interpolation='nearest',aspect='auto',origin='lower',cmap=cm.RdBu)
clean_axis(heatmapAX)

## row labels ##
heatmapAX.set_yticks(arange(testDF.shape[0]))
heatmapAX.yaxis.set_ticks_position('right')
heatmapAX.set_yticklabels(testDF.index[row_denD['leaves']])

## col labels ##
heatmapAX.set_xticks(arange(testDF.shape[1]))
xlabelsL = heatmapAX.set_xticklabels(testDF.columns[col_denD['leaves']])
# rotate labels 90 degrees
for label in xlabelsL:
    label.set_rotation(90)
# remove the tick lines
for l in heatmapAX.get_xticklines() + heatmapAX.get_yticklines(): 
    l.set_markersize(0)

### scale colorbar ###
scale_cbGSSS = gridspec.GridSpecFromSubplotSpec(1,2,subplot_spec=heatmapGS[0,0],wspace=0.0,hspace=0.0)
scale_cbAX = fig.add_subplot(scale_cbGSSS[0,0]) # colorbar for scale in upper left corner
cb = fig.colorbar(axi,scale_cbAX) # note that we tell colorbar to use the scale_cbAX axis
cb.set_label('Measurements')
cb.ax.yaxis.set_ticks_position('left') # move ticks to left side of colorbar to avoid problems with tight_layout
cb.ax.yaxis.set_label_position('left') # move label to left side of colorbar to avoid problems with tight_layout
cb.outline.set_linewidth(0)

fig.tight_layout()

# make norm
vmin = np.floor(testDF.min().min())
vmax = np.ceil(testDF.max().max())
vmax = max([vmax,abs(vmin)]) # choose larger of vmin and vmax
vmin = vmax * -1
my_norm = mpl.colors.Normalize(vmin, vmax)

# heatmap with row names
fig = plt.figure(figsize=(12,8))
heatmapGS = gridspec.GridSpec(2,2,wspace=0.0,hspace=0.0,width_ratios=[0.25,1],height_ratios=[0.25,1])

### col dendrogram ###
col_denAX = fig.add_subplot(heatmapGS[0,1])
col_denD = sch.dendrogram(col_clusters,color_threshold=np.inf)
clean_axis(col_denAX)

### row dendrogram ###
row_denAX = fig.add_subplot(heatmapGS[1,0])
row_denD = sch.dendrogram(row_clusters,color_threshold=np.inf,orientation='right')
clean_axis(row_denAX)

### heatmap ####
heatmapAX = fig.add_subplot(heatmapGS[1,1])
axi = heatmapAX.imshow(testDF.ix[row_denD['leaves'],col_denD['leaves']],interpolation='nearest',aspect='auto',origin='lower',norm=my_norm,cmap=cm.RdBu)
clean_axis(heatmapAX)

## row labels ##
heatmapAX.set_yticks(arange(testDF.shape[0]))
heatmapAX.yaxis.set_ticks_position('right')
heatmapAX.set_yticklabels(testDF.index[row_denD['leaves']])

## col labels ##
heatmapAX.set_xticks(arange(testDF.shape[1]))
xlabelsL = heatmapAX.set_xticklabels(testDF.columns[col_denD['leaves']])
# rotate labels 90 degrees
for label in xlabelsL:
    label.set_rotation(90)
# remove the tick lines
for l in heatmapAX.get_xticklines() + heatmapAX.get_yticklines(): 
    l.set_markersize(0)

### scale colorbar ###
scale_cbGSSS = gridspec.GridSpecFromSubplotSpec(1,2,subplot_spec=heatmapGS[0,0],wspace=0.0,hspace=0.0)
scale_cbAX = fig.add_subplot(scale_cbGSSS[0,1]) # colorbar for scale in upper left corner
cb = fig.colorbar(axi,scale_cbAX) # note that we could pass the norm explicitly with norm=my_norm
cb.set_label('Measurements')
cb.ax.yaxis.set_ticks_position('left') # move ticks to left side of colorbar to avoid problems with tight_layout
cb.ax.yaxis.set_label_position('left') # move label to left side of colorbar to avoid problems with tight_layout
cb.outline.set_linewidth(0)
# make colorbar labels smaller
tickL = cb.ax.yaxis.get_ticklabels()
for t in tickL:
    t.set_fontsize(t.get_fontsize() - 3)

fig.tight_layout()

# run dendrogram without color_threshold=np.inf to define some clusters
row_cbSE = pd.Series([brewer2mpl.get_map('Set1','Qualitative',3).mpl_colors[0]] * (testDF.shape[0] / 2) + \
    [brewer2mpl.get_map('Set1','Qualitative',3).mpl_colors[1]] * (testDF.shape[0] / 2 + testDF.shape[0] % 2))
col_cbSE = pd.Series([brewer2mpl.get_map('Set2','Qualitative',3).mpl_colors[0]] * (testDF.shape[1] / 2) + \
    [brewer2mpl.get_map('Set2','Qualitative',3).mpl_colors[1]] * (testDF.shape[1] / 2 + testDF.shape[1] % 2))

# heatmap with row names
fig = plt.figure(figsize=(12,8))
heatmapGS = gridspec.GridSpec(2,2,wspace=0.0,hspace=0.0,width_ratios=[0.25,1],height_ratios=[0.25,1])

### col dendrogram ###
colGSSS = gridspec.GridSpecFromSubplotSpec(2,1,subplot_spec=heatmapGS[0,1],wspace=0.0,hspace=0.0,height_ratios=[1,0.25])
col_denAX = fig.add_subplot(colGSSS[0,0])
col_denD = sch.dendrogram(col_clusters,color_threshold=np.inf)
clean_axis(col_denAX)

### col colorbar ###
col_cbAX = fig.add_subplot(colGSSS[1,0])
col_axi = col_cbAX.imshow([list(col_cbSE.ix[col_denD['leaves']])],interpolation='nearest',aspect='auto',origin='lower')
clean_axis(col_cbAX)

### row dendrogram ###
rowGSSS = gridspec.GridSpecFromSubplotSpec(1,2,subplot_spec=heatmapGS[1,0],wspace=0.0,hspace=0.0,width_ratios=[1,0.25])
row_denAX = fig.add_subplot(rowGSSS[0,0])
row_denD = sch.dendrogram(row_clusters,color_threshold=np.inf,orientation='right')
clean_axis(row_denAX)

### row colorbar ###
row_cbAX = fig.add_subplot(rowGSSS[0,1])
row_axi = row_cbAX.imshow([ [x] for x in row_cbSE.ix[row_denD['leaves']].values ],interpolation='nearest',aspect='auto',origin='lower')
clean_axis(row_cbAX)

### heatmap ####
heatmapAX = fig.add_subplot(heatmapGS[1,1])
axi = heatmapAX.imshow(testDF.ix[row_denD['leaves'],col_denD['leaves']],interpolation='nearest',aspect='auto',origin='lower',norm=my_norm,cmap=cm.RdBu)
clean_axis(heatmapAX)

## row labels ##
heatmapAX.set_yticks(arange(testDF.shape[0]))
heatmapAX.yaxis.set_ticks_position('right')
heatmapAX.set_yticklabels(testDF.index[row_denD['leaves']])

## col labels ##
heatmapAX.set_xticks(arange(testDF.shape[1]))
xlabelsL = heatmapAX.set_xticklabels(testDF.columns[col_denD['leaves']])
# rotate labels 90 degrees
for label in xlabelsL:
    label.set_rotation(90)
# remove the tick lines
for l in heatmapAX.get_xticklines() + heatmapAX.get_yticklines(): 
    l.set_markersize(0)

### scale colorbar ###
scale_cbGSSS = gridspec.GridSpecFromSubplotSpec(1,2,subplot_spec=heatmapGS[0,0],wspace=0.0,hspace=0.0)
scale_cbAX = fig.add_subplot(scale_cbGSSS[0,1]) # colorbar for scale in upper left corner
cb = fig.colorbar(axi,scale_cbAX) # note that we could pass the norm explicitly with norm=my_norm
cb.set_label('Measurements')
cb.ax.yaxis.set_ticks_position('left') # move ticks to left side of colorbar to avoid problems with tight_layout
cb.ax.yaxis.set_label_position('left') # move label to left side of colorbar to avoid problems with tight_layout
cb.outline.set_linewidth(0)
# make colorbar labels smaller
tickL = cb.ax.yaxis.get_ticklabels()
for t in tickL:
    t.set_fontsize(t.get_fontsize() - 3)

fig.tight_layout()

# heatmap with row names
fig = plt.figure(figsize=(12,8))
heatmapGS = gridspec.GridSpec(2,2,wspace=0.0,hspace=0.0,width_ratios=[0.25,1],height_ratios=[0.25,1])

### col dendrogram ###
colGSSS = gridspec.GridSpecFromSubplotSpec(2,1,subplot_spec=heatmapGS[0,1],wspace=0.0,hspace=0.1,height_ratios=[1,0.15])
col_denAX = fig.add_subplot(colGSSS[0,0])
col_denD = sch.dendrogram(col_clusters,color_threshold=np.inf)
clean_axis(col_denAX)

### col colorbar ###
col_cbAX = fig.add_subplot(colGSSS[1,0])
col_axi = col_cbAX.imshow([list(col_cbSE.ix[col_denD['leaves']])],interpolation='nearest',aspect='auto',origin='lower')
clean_axis(col_cbAX)

### row dendrogram ###
rowGSSS = gridspec.GridSpecFromSubplotSpec(1,2,subplot_spec=heatmapGS[1,0],wspace=0.1,hspace=0.0,width_ratios=[1,0.15])
row_denAX = fig.add_subplot(rowGSSS[0,0])
row_denD = sch.dendrogram(row_clusters,color_threshold=np.inf,orientation='right')
clean_axis(row_denAX)

### row colorbar ###
row_cbAX = fig.add_subplot(rowGSSS[0,1])
row_axi = row_cbAX.imshow([ [x] for x in row_cbSE.ix[row_denD['leaves']].values ],interpolation='nearest',aspect='auto',origin='lower')
clean_axis(row_cbAX)

### heatmap ####
heatmapAX = fig.add_subplot(heatmapGS[1,1])
axi = heatmapAX.imshow(testDF.ix[row_denD['leaves'],col_denD['leaves']],interpolation='nearest',aspect='auto',origin='lower',norm=my_norm,cmap=cm.RdBu)
clean_axis(heatmapAX)

## row labels ##
heatmapAX.set_yticks(arange(testDF.shape[0]))
heatmapAX.yaxis.set_ticks_position('right') 
heatmapAX.set_yticklabels(testDF.index[row_denD['leaves']])

## col labels ##
heatmapAX.set_xticks(arange(testDF.shape[1]))
xlabelsL = heatmapAX.set_xticklabels(testDF.columns[col_denD['leaves']])
# rotate labels 90 degrees
for label in xlabelsL:
    label.set_rotation(90)
# remove the tick lines
for l in heatmapAX.get_xticklines() + heatmapAX.get_yticklines(): 
    l.set_markersize(0)

### scale colorbar ###
scale_cbGSSS = gridspec.GridSpecFromSubplotSpec(1,3,subplot_spec=heatmapGS[0,0],wspace=0.0,hspace=0.0)
scale_cbAX = fig.add_subplot(scale_cbGSSS[0,1]) # colorbar for scale in upper left corner
cb = fig.colorbar(axi,scale_cbAX) # note that we could pass the norm explicitly with norm=my_norm
cb.set_label('Measurements')
cb.ax.yaxis.set_ticks_position('left') # move ticks to left side of colorbar to avoid problems with tight_layout
cb.ax.yaxis.set_label_position('left') # move label to left side of colorbar to avoid problems with tight_layout
cb.outline.set_linewidth(0)
# make colorbar labels smaller
tickL = cb.ax.yaxis.get_ticklabels()
for t in tickL:
    t.set_fontsize(t.get_fontsize() - 3)

#fig.tight_layout()
heatmapGS.tight_layout(fig,h_pad=0.1,w_pad=0.5)

# heatmap with row names
fig = plt.figure(figsize=(12,8))
heatmapGS = gridspec.GridSpec(3,3,wspace=0.0,hspace=0.0,width_ratios=[0.25,0.05,1],height_ratios=[0.25,0.05,1])

### col dendrogram ###
colGSSS = gridspec.GridSpecFromSubplotSpec(2,1,subplot_spec=heatmapGS[0,1],wspace=0.0,hspace=0.1,height_ratios=[1,0.15])
col_denAX = fig.add_subplot(heatmapGS[0,2])
col_denD = sch.dendrogram(col_clusters,color_threshold=np.inf)
clean_axis(col_denAX)

### col colorbar ###
col_cbAX = fig.add_subplot(heatmapGS[1,2])
col_axi = col_cbAX.imshow([list(col_cbSE.ix[col_denD['leaves']])],interpolation='nearest',aspect='auto',origin='lower')
clean_axis(col_cbAX)

### row dendrogram ###
row_denAX = fig.add_subplot(heatmapGS[2,0])
row_denD = sch.dendrogram(row_clusters,color_threshold=np.inf,orientation='right')
clean_axis(row_denAX)

### row colorbar ###
row_cbAX = fig.add_subplot(heatmapGS[2,1])
row_axi = row_cbAX.imshow([ [x] for x in row_cbSE.ix[row_denD['leaves']].values ],interpolation='nearest',aspect='auto',origin='lower')
clean_axis(row_cbAX)

### heatmap ####
heatmapAX = fig.add_subplot(heatmapGS[2,2])
axi = heatmapAX.imshow(testDF.ix[row_denD['leaves'],col_denD['leaves']],interpolation='nearest',aspect='auto',origin='lower',norm=my_norm,cmap=cm.RdBu)
clean_axis(heatmapAX)

## row labels ##
heatmapAX.set_yticks(arange(testDF.shape[0]))
heatmapAX.yaxis.set_ticks_position('right') 
heatmapAX.set_yticklabels(testDF.index[row_denD['leaves']])

## col labels ##
heatmapAX.set_xticks(arange(testDF.shape[1]))
xlabelsL = heatmapAX.set_xticklabels(testDF.columns[col_denD['leaves']])
# rotate labels 90 degrees
for label in xlabelsL:
    label.set_rotation(90)
# remove the tick lines
for l in heatmapAX.get_xticklines() + heatmapAX.get_yticklines(): 
    l.set_markersize(0)

### scale colorbar ###
scale_cbAX = fig.add_subplot(heatmapGS[0:2,0]) # colorbar for scale in upper left corner
cb = fig.colorbar(axi,scale_cbAX) # note that we could pass the norm explicitly with norm=my_norm
cb.set_label('Measurements')
cb.ax.yaxis.set_ticks_position('left') # move ticks to left side of colorbar to avoid problems with tight_layout
cb.ax.yaxis.set_label_position('left') # move label to left side of colorbar to avoid problems with tight_layout
cb.outline.set_linewidth(0)
# make colorbar labels smaller
tickL = cb.ax.yaxis.get_ticklabels()
for t in tickL:
    t.set_fontsize(t.get_fontsize() - 3)

#fig.tight_layout()
heatmapGS.tight_layout(fig,h_pad=0.1,w_pad=0.5)

# Stop those who "Run All"
3 +

import brewer2mpl
import pandas as pd
import matplotlib.pyplot as plt
import matplotlib.gridspec as gridspec
import scipy.spatial.distance as distance
import scipy.cluster.hierarchy as sch

# helper for cleaning up axes by removing ticks, tick labels, frame, etc.
def clean_axis(ax):
    """Remove ticks, tick labels, and frame from axis"""
    ax.get_xaxis().set_ticks([])
    ax.get_yaxis().set_ticks([])
    for sp in ax.spines.values():
        sp.set_visible(False)

# make dendrograms black rather than letting scipy color them
sch.set_link_color_palette(['black'])

# calculate pairwise distances for rows
row_pairwise_dists = distance.squareform(distance.pdist(testDF))
# cluster
row_clusters = sch.linkage(row_pairwise_dists,method='complete')
# calculate pairwise distances for columns
col_pairwise_dists = distance.squareform(distance.pdist(testDF.T))
# cluster
col_clusters = sch.linkage(col_pairwise_dists,method='complete')

# run dendrogram without color_threshold=np.inf to define some clusters
row_cbSE = pd.Series([brewer2mpl.get_map('Set1','Qualitative',3).mpl_colors[0]] * (testDF.shape[0] / 2) + \
    [brewer2mpl.get_map('Set1','Qualitative',3).mpl_colors[1]] * (testDF.shape[0] / 2 + testDF.shape[0] % 2))
col_cbSE = pd.Series([brewer2mpl.get_map('Set2','Qualitative',3).mpl_colors[0]] * (testDF.shape[1] / 2) + \
    [brewer2mpl.get_map('Set2','Qualitative',3).mpl_colors[1]] * (testDF.shape[1] / 2 + testDF.shape[1] % 2))

# make norm
vmin = np.floor(testDF.min().min())
vmax = np.ceil(testDF.max().max())
vmax = max([vmax,abs(vmin)]) # choose larger of vmin and vmax
vmin = vmax * -1
my_norm = mpl.colors.Normalize(vmin, vmax)
The MIT License (MIT)

Copyright (c) 2014 Christopher DeBoever

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.