qsortを再帰を使わずに書く
そういうお題が某所で提供されたので、せっかくだから解いてみる。
ちなみに出題者の方は僕より数日早く自分で解かれたようだった。。。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ARR_SIZE (20)
#define SHUFFLE_NUM (1000)
typedef struct jobs {
struct jobs* prevjob;
int* start;
size_t size;
} job_t;
void testqs(size_t size);
void printarr(int* arr, size_t size);
void myqsort(int* arr, size_t size);
int getpivot(int a0, int a1, int a2);
int getpivot(int a0, int a1, int a2)
{
int retval = 0;
if(a0 > a1) {
if(a1 > a2) {
retval = a1;
}
else if(a0 > a2) {
retval = a2;
}
else {
retval = a0;
}
}
else if(a0 > a2) {
retval = a0;
}
else if(a1 > a2) {
retval = a2;
}
else {
retval = a1;
}
return retval;
}
void myqsort(int* arr, size_t size)
{
int* head;
int* bottom;
int sortsize;
int pivot;
int tmp;
int* sav_head;
int* sav_bottom;
job_t* nowjob;
job_t* addjob;
job_t* lastjob;
addjob = (job_t*)malloc(sizeof(job_t));
addjob->prevjob = NULL;
addjob->start = arr;
addjob->size = size;
lastjob = addjob;
while(lastjob != NULL) {
nowjob = lastjob;
head = nowjob->start;
sortsize = nowjob->size;
bottom = head + sortsize - 1;
sav_head = head;
sav_bottom = bottom;
lastjob = lastjob->prevjob;
free(nowjob);
if(sortsize < 2) {
}
else if(sortsize == 2) {
if(*head > *bottom) {
tmp = *head;
*head = *bottom;
*bottom = tmp;
}
}
else {
pivot = getpivot(*head, *(head+1), *(head+2));
while(head < bottom) {
if(*head > pivot) {
while(head < bottom) {
if(*bottom <= pivot) {
tmp = *head;
*head = *bottom;
*bottom = tmp;
bottom --;
head++;
break;
}
else {
bottom --;
}
}
}
else {
head++;
}
}
while(head <= sav_bottom) {
if( *head> pivot) {
break;
}
head++;
}
if(head > sav_head) {
addjob = (job_t*)malloc(sizeof(job_t));
addjob->prevjob = lastjob;
addjob->start = sav_head;
addjob->size = head - sav_head;
lastjob = addjob;
}
if(head < sav_bottom) {
addjob = (job_t*)malloc(sizeof(job_t));
addjob->prevjob = lastjob;
addjob->start = head;
addjob->size = sav_bottom - head + 1;
lastjob = addjob;
}
}
}
}
void testqs(size_t size)
{
int* arr;
int i;
int a, b;
int tmp;
arr = (int*)malloc(sizeof(int) * size);
memset(arr, 0, sizeof(int) * size);
for(i = 0; i < size; i++) {
arr[i] = i;
}
for(i = 0; i < SHUFFLE_NUM; i++) {
a = rand() % size;
b = rand() % size;
tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
printarr(arr, size);
myqsort(arr, ARR_SIZE);
printarr(arr, size);
free(arr);
}
void printarr(int* arr, size_t size)
{
int i;
for(i = 0; i < size -1; i++) {
printf("%d, ", arr[i]) ;
if ( i % 20 == 19 ) {
printf("\n");
}
}
printf("%d\n", arr[size - 1]);
}
int main(int argc, char** argv)
{
int i;
for(i=0; i< 10; i++) {
testqs(ARR_SIZE);
}
return 0;
}即席で作ったからコメント一切なし、
即席で作ったからmallocの返り値チェックなし、
作者の腕が悪いからコードは汚い
まあ、(たぶん(※))動いたからよしとしよう。
(※)適当なテストプログラム組んでみたらちゃんとソートされた。
walk NewBitmapFromImage()
今日遊んだコードはこれ
package main import ( "github.com/lxn/walk" . "github.com/lxn/walk/declarative" ) import ( _ "go.image/bmp" ) import ( "fmt" "image" "image/color" "os" "log" ) func imgfromfilename(filename string) (img image.Image, err error) { file, err := os.Open(filename) if err != nil { return nil, err } defer file.Close() img,_, err = image.Decode(file) if err != nil { fmt.Println("Decode") return nil, err } return img, nil } type myimage struct { img image.Image } func (mi myimage) ColorModel() color.Model { return mi.img.ColorModel() } func (mi myimage) Bounds() image.Rectangle { return mi.img.Bounds() } func (mi myimage) At(x, y int) color.Color { col := mi.img.At(x, y) r, g, b, _ := col.RGBA() return color.RGBA{uint8(r+0xff), uint8(g)^0xff , uint8(0x88- uint8(b)) , uint8(0xff)} } func main() { var iv *walk.ImageView img, err := imgfromfilename("../tombo_big2.bmp") if err != nil { log.Fatal(err) return } myimg := myimage{img} bitmap, err := walk.NewBitmapFromImage(myimg) if err != nil { fmt.Println("NewBitmapFromImage") log.Fatal(err) return } imgsize := bitmap.Size() MainWindow{ Title: "hello", Size: Size{ Width: imgsize.Width, Height: imgsize.Height, }, Layout: VBox{ MarginsZero: true, }, Children: []Widget { ImageView { AssignTo: &iv, Image: bitmap, MaxSize: Size{ Width: imgsize.Width, Height: imgsize.Height, }, MinSize: Size{ Width: imgsize.Width, Height: imgsize.Height, }, }, }, }.Run() }
下準備
このコードを動かす前に、ちょっとだけ下準備がいった。
goの標準ライブラリでは、bmpは扱わなくなったっぽい
というわけで、それをとってこようとがんばってみる。
んで、ここを探すと、
hg clone https://code.google.com/p/go.image/
ってやれって書いてあって、もちろんhgなんてコマンド入っていないわけで、ここからとってきた。僕が入れたのは、Setup installer の does not admin rights というの。adminで入れるのは極力避けたい。
で、適当にインストールして、hgコマンドでとってきた。とってきた先のディレクトリは、
%GOPATH%\srcの下。とりあえずこの辺においておいた。
コードの説明
import宣言で、さっきとってきたgo.image/bmpを読み込む。
どうも読み込むだけで、image.Decode()とすれば、bmpだったらそのデータを読み込んでくれた。なので、"_"がついている。
imgfromfilename()で、ファイルからimage.Imageのデータに変換。
それだけでは面白くないので、自分でmyimage{}構造体を作って、変換してみた。
このやり方は、チュートリアルの練習問題にあったので、それを真似てやってみた。
そうやって作った、image.Image型のデータを、walk.NewBitmapFromImage(myimg)として*Bitmap型に変換。これはwalk.Image型としてImageView構造体のImageにそのままつっこめる。
今まで面倒くさかったのでやってなかったエラーチェックを適当にしているが、うまく動かなかった名残。
ちなみにうまく動かなかった原因は、bmpファイルがサポートされてない形式のものだったかららしい。一度gimpで読み込んでエクスポートして、その際に、互換性のところの、「色空間の情報を書き込まない」にチェックを入れたらうまくいった。なので、"tombo_big2.bmp"となってる。
って、ここまでやってきたが、image.Image型を通さなくても実は*Bitmap型を適当にいじったりできないんかなぁ。。
そのうちやってみよう。
walk ImageView
今日遊んだコードはこんな感じ。
package main import ( "github.com/lxn/walk" . "github.com/lxn/walk/declarative" ) func main() { var iv *walk.ImageView img, _ := walk.NewImageFromFile("./tombo_big.bmp") imgsize := img.Size() MainWindow{ Title: "hello", Size: Size{ Width: imgsize.Width, Height: imgsize.Height, }, Layout: VBox{ MarginsZero: true, }, Children: []Widget { ImageView { AssignTo: &iv, Image: img, MaxSize: Size{ Width: imgsize.Width, Height: imgsize.Height, }, MinSize: Size{ Width: imgsize.Width, Height: imgsize.Height, }, }, }, }.Run() }
まず、画像ファイルを用意する。僕が用意したのはこれ
tombo_big.bmpというファイルで用意した。
# 01:26追記、画像ファイルを投稿したら自動でjpegになるのね。
# 元はbmpだったということで…。
そのファイルを、walk.NewImageFromFile()関数で開くと、walk.Image型のデータができる。
そのデータ(ここではimgという変数でおいてある)を、前回のTextEditの代わりにImageViewを使い、その構造体のメンバImageに代入。
そのほかは前回のTextEditと変わらず、あっけないほどに画像表示ができた。
変えた部分は、VBoxの中のMarginsZero。ここをtrueにしておくと、余白がなくなってなんとなく綺麗にみえた。
気をつけるところがあるとすれば、walk.Image型はimage.Image型と違うっぽいこと。
golangの標準ライブラリの画像変換のところは直接は使えないっぽい。
ただ、walk/bitmap.goに、NewBitmapFromImage()という関数があって、それは、image.Image型をwalkに使えるように変換してくれるっぽい。
MaxSizeとMinSizeはあいかわらず、Minはきちんと作用するけどMaxは変になる。
バグじゃないかと疑ってるんだけど、それを直そうとすると僕はゆーざからでべろっぱにクラスチェンジしないといけなくなる。できるだけゆーざでいたいので放置ということで。。
というわけで次の目標、NewBitmapFromImage()を使ってみる。
構造体とポインタの話
まあ、あたりまえっちゃあたりまえなんだろうけど、一応確かめておこうと思ったこと。
package main import "fmt" type hoge struct { a int b float64 s string }
構造体を適当に宣言しておく。
func main() { var h *hoge h = new(hoge) h.a = 5 h.b = 3.14 h.s = "hogehoge" fmt.Println(h.a,",",h.b,",",h.s) }
このコードは、ちゃんと動く。
でも、
h = new(hoge)
この一行を書かないと、コンパイルは通るけど実行時エラーが出て動かない。
ポインタ型を宣言してるけど、構造体の中身を確保していないから当然だろう。
で、main()関数の最初の二行を
h: = &hoge{}
とすると、動く。当然だといわれればそうなんだけど、構造体の確保って、Cでいう静的とか動的とか意識したら、どっちがいいんだろうと思ったりしたりするのかなぁ。と。
まあ、あんまり深く考えなくていいのかもしれないけど。。
ちょっとコードを書き足して、
func (h *hoge)print() { fmt.Println(h.a,",",h.b,",",h.s) }
こんなのを書いてみて、main()関数の終わりの方で
h.print()
って呼び出してみた。
やっぱり、var h *hogeだけでは動かないみたいでh=new(hoge)がいるようだし、
h:=&hoge{}
だったらちゃんと動いた。
よく考えたら当然なんだけど、実際手で納得してみたので日記行き。
walk PushButton
今日遊んだコードはこんな感じ
package main import ( "github.com/lxn/walk" . "github.com/lxn/walk/declarative" ) import ( "strings" ) func main() { var te1 *walk.TextEdit MainWindow{ Title: "hello", Size: Size{320, 480}, Layout: VBox{}, Children: []Widget { TextEdit { AssignTo: &te1, }, PushButton{ Text: "hello", ToolTipText: `put "hello"`, OnClicked: func() { text := te1.Text() text = strings.Join( []string{text, "hello"}, "") te1.SetText(text) }, }, }, }.Run() }
TextEditのところまでは昨日(だっけ)のとほぼ同じ。PushButtonをとりあえず使ってみた。
Textの部分は、ボタンに書かれる文字列が入る。
中身を見てみると、Property型となってて、さらに見てみると、interface{}型だった。つまり、どんな型の中身を入れても理論上問題はないみたい。実際にint型の123を入れてみたが、コンパイルは通った。
ただ、string型でないと実行時にエラーが起きた。結局string型しか入らないんだろう。なんでそんな仕様になってるかまだわからないけど、とりあえずそんな感じ。
ToolTipTextは、ここに文字列いれておくと、マウスカーソルを合わせたときに説明が出る。
OnClickedは、関数が入る。ボタン押されたときに処理をしてくれる。
中身はwalk.EventHandler型となってるけど、さらに中身を見たらfunc()ってなってたのできっとそうなんだろう。
引数はとれないと思う。だから、データを受け渡しするには、グローバル変数を使うか、今回のコードのようにfunc()を直書きするか、ここでやってるように構造体を作ってそれで処理するか、だと思う。
walk.TextEdit型のメソッドにText()や、SetText()がある。
Text()は、中に書かれているテキストがstring型で返る。
SetText(value string)は、valueの文字列をテキストエリアに表示させる。
他のメソッドもいっぱいあるみたいだけど、それはwalk/textedit.goに書いてあるみたい。
今日はこれだけで満足。
今度はイメージ表示とかできたらいいなぁ。。
構造体
golangの構造体の中に、他の構造体の宣言を入れられるみたい。
うまいこと説明できないけど
type hogebase struct { j int }
とりあえず先に(後でもいいけど)取り込む構造体を宣言してみる。
type hoge struct { hogebase i int str string }
で、こんな感じに、先に宣言したhogebaseを中に入れておくと
func main() { nanka := hoge { str: "string", } nanka.j = 5 //<--- }
あたかもjがnankaのメンバ変数になってるかのように扱うことができるみたい。
ただ、
nanka := hoge {
str: "string",
j: 5 // <---
}
これはコンパイルエラーになるみたい。初期化はできない、ということだろうか。
たぶんどこかに書いてあるだろうけど、へぇって思ったので日記行き。
walk Layout
今回遊んだコードはこれがベース。昨日(だったけ)作ったコードから少しだけ変えた。
package main import ( "github.com/lxn/walk" . "github.com/lxn/walk/declarative" ) func main() { var te1, te2 *walk.TextEdit MainWindow{ Title: "hello", Size: Size{320, 240}, Layout: HBox{}, Children: []Widget { TextEdit { AssignTo: &te1, }, TextEdit { AssignTo: &te2, }, }, }.Run() }
Layoutというのはインターフェイス型で、それを満たす構造体にHBoxとVBoxと、Gridというのがあるみたい。
どれも
type HBox struct { Margins Margins Spacing int MarginsZero bool SpacingZero bool }
という感じになってるみたいなんだけど、とりあえずはこの中身をいじるのはまた今度。
Gridはおいといて、'V'と'H'はVertical(垂直)とHorizontal(水平)の略であるのは想像に難くない。
前の日記に書き忘れたが、manifestファイルというのを書かないといけないみたい。
<?xml version="1.0" encoding="UTF-8" standalone="yes"?> <assembly xmlns="urn:schemas-microsoft-com:asm.v1" manifestVersion="1.0"> <assemblyIdentity version="1.0.0.0" processorArchitecture="*" name="SomeFunkyNameHere" type="win32"/> <dependency> <dependentAssembly> <assemblyIdentity type="win32" name="Microsoft.Windows.Common-Controls" version="6.0.0.0" processorArchitecture="*" publicKeyToken="6595b64144ccf1df" language="*"/> </dependentAssembly> </dependency> </assembly>
これをtestwalk.exe.manifestという名前で保存する。
どうも使い回しができるっぽいので、(実行ファイル名).manifestという名前でコピーして使ってる。
まあとりあえず、動かした結果がこれ。
テキストボックスが二つ横に並んでる。
そして
Layout: VBox{},と書き換えると
こんな感じになる。予想どおりVerticalとHorizontalだった。
Gridは試してみたら実行時エラーで動かなかったので、違う使い方かもしれない。
Childrenは、Widget型のスライスで、まあWidget型がいくつか並んでいるみたい。
そしてWidget型はインターフェイスで、とにかくたくさんの型が入るみたい。
今回使ったTextEdit型の構造体とか、今度使う予定のPushButton型とか、いろいろ。
とりあえずdeclarativeの下で
grep Widgetinfo *.go | grep func | less
とかしたらいっぱいでてきたので、まあそれくらいいっぱい型があるんだろう。
今日はこれぐらいで許してもらって、次はボタンを押してなんかできるようになるのが目標。
